TRƢỜNG ĐẠI HỌC CẦN THƠ
KHOA SƢ PHẠM
BỘ MÔN SP TOÁN HỌC
- - - - - - - - - -

LUẬN VĂN TỐT NGHIỆP

Đề tài:

BÀI TOÁN TÌM ĐƢỜNG ĐI
NGẮN NHẤT VÀ ỨNG DỤNG

Giáo viên hướng dẫn

Sinh viên thực hiện

ThS. Phạm Thị Vui

Lƣu Thị Hồng Trang
MSSV: B1200416
Lớp SP Toán K38

Cần Thơ, 2016


LỜI CẢM ƠN

Em xin chân thành gửi lời cảm ơn đến lãnh đạo nhà trƣờng, các Thầy Cô trong
trƣờng đã tạo điều kiện thuận lợi để em có thể học tập và rèn luyện trong những năm
học vừa qua, đặc biệt là Thầy Cô Khoa Sƣ phạm và trƣớc nhất là Thầy Cô Bộ môn Sƣ
phạm Toán đã tận tình giảng dạy, truyền thụ cho em những kiến thức cũng nhƣ những

kinh nghiệm quý báu để làm hành trang cho em trên con đƣờng giảng dạy và nâng cao
trình độ của mình sau này.
Em xin gửi lời cảm ơn sâu sắc đến cô Phạm Thị Vui, là giáo viên hƣớng dẫn luận
văn cho em. Nhờ sự hƣớng dẫn và giúp đỡ tận tình của cô đã giúp em hoàn thành tốt
luận văn này. Em xin gửi lời cảm ơn đến bạn bè, gia đình và mọi ngƣời xung quanh đã
động viên, ủng hộ và giúp đỡ em trong suốt quá trình học tập và hoàn thành luận văn
này.
Trong quá trình hoàn thành luận văn, tuy em đã cố gắng nổ lực nhƣng do thời
gian có hạn nên chắc chắn vẫn còn nhiều thiếu sót. Rất mong nhận đƣợc ý kiến góp ý
quý báu của các Thầy Cô và bạn đọc.
Cần Thơ, ngày tháng năm 2016
sinh viên thực hiện

Lƣu Thị Hồng Trang


Mục Lục

PHẦN MỞ ĐẦU .............................................................................................................. 1
1.1 Lý do chọn đề tài .................................................................................................... 1
1.2 Mục đích nghiên cứu .............................................................................................. 1
1.3 Phƣơng pháp nghiên cứu........................................................................................ 2
1.4 Phạm vi nghiên cứu ................................................................................................ 2
1.5 Nội dung của luận văn............................................................................................ 2
PHẦN NỘI DUNG .......................................................................................................... 3
Chƣơng 1 .......................................................................................................................... 3
KIẾN THỨC CHUẨN BỊ ................................................................................................ 3
1.1 Đồ thị ...................................................................................................................... 3
1.1.1 Sơ lƣợc về đồ thị ................................................................................................. 3
1.1.2 Một số khái niệm ................................................................................................. 3

1.1.3 Một số ví dụ về đồ thị ......................................................................................... 4
1.2 Một số khái niệm liên quan đến đồ thị ................................................................... 7
1.2.1 Cạnh bội và khuyên ............................................................................................. 7
1.2.2 Đơn đồ thị............................................................................................................ 7
1.2.3 Đa đồ thị .............................................................................................................. 8
1.2.4 Giả đồ thị ........................................................................................................... 10
1.2.5 Đồ thị có trọng số .............................................................................................. 10
1.2.6 Bậc của đỉnh trong đồ thị .................................................................................. 11
1.3 Biễu diễn đồ thị .................................................................................................... 14
1.3.1 Biễu điễn đồ thị bằng hình học ......................................................................... 14
1.3.2 Biểu diễn đồ thị bằng ma trận ........................................................................... 15
1.3.3 Biểu diễn đồ thị bằng bảng................................................................................ 19


1.4 Đƣờng đi – chu trình – tính liên thông trong đồ thị ............................................. 20
1.4.1 Đƣờng đi............................................................................................................ 20
1.4.3 Tính liên thông trong đồ thị .............................................................................. 21
Chƣơng 2 ........................................................................................................................ 25
BÀI TOÁN TÌM ĐƢỜNG ĐI NGẮN NHẤT ............................................................... 25
2.1 Bài Toán Tìm Đƣờng Đi Ngắn Nhất .................................................................... 25
2.1.1 Giới thiệu bài toán ............................................................................................. 25
2.1.2 Phát biểu bài toán tìm đƣờng đi ngắn nhất trên đồ thị ...................................... 25
2.1.3 Một số khái niệm ............................................................................................... 26
2.2 Thuật toán Dijkstra ............................................................................................... 27
2.2.1 Giới thiệu thuật toán Dijkstra ............................................................................ 27
2.2.2 Thuật toán Dijkstra ............................................................................................ 29
2.2.3 Ví dụ .................................................................................................................. 33
2.2.4 Định lí 1............................................................................................................. 39
2.2.5 Định lí 2............................................................................................................. 39
2.2.6 Định lí 3............................................................................................................. 41

2.2.7 Lƣu đồ thuật toán Dijkstra ................................................................................ 42
2.3 Thuật toán Ford-Bellman ..................................................................................... 43
2.3.1 Giới thiệu thuật toán Ford-Bellman .................................................................. 43
2.3.2 Tƣ tƣởng của thuật toán Ford-Bellman ............................................................. 44
2.3.3 Ví dụ .................................................................................................................. 45
2.3.4 Lƣu đồ thuật toán Ford-Bellman ....................................................................... 52
2.4 Thuật toán Hedetniemi ......................................................................................... 53
2.4.1 Giới thiệu thuật toán Hedetniemi ...................................................................... 53
2.4.2 Phép cộng hai ma trận Hedetniemi ................................................................... 53
2.4.3 Thuật toán Hedetniemi ...................................................................................... 54
2.4.5 Lƣu đồ thuật toán Hidetniemi ........................................................................... 57


2.5 Một số bài toán tìm đƣờng đi ngắn nhất mở rộng ................................................ 58
2.5.1 Bài toán 1 .......................................................................................................... 58
2.5.2 Bài toán 2 .......................................................................................................... 64
Chƣơng 3 ........................................................................................................................ 76
ỨNG DỤNG .................................................................................................................. 76
3.1 Tổng quan về ứng dụng của các bài toán tìm đƣờng đi ngắn nhất kết hợp với bản
đồ số ........................................................................................................................... 76
3.2 Bài toán xe buýt ................................................................................................... 77
3.2.1 Hiện trạng hệ thống xe buýt .............................................................................. 77
3.2.2 Cách thức đón xe buýt....................................................................................... 78
3.2.3 Chức năng chính và những yêu cầu cần có của ứng dụng WebGIS ................. 79
3.2.4 Tìm đƣờng đi ngắn nhất .................................................................................... 79
3.2.5 Tìm trạm dừng/nhà chờ gần nhất ...................................................................... 81
3.3 Bài toán xe taxi ..................................................................................................... 82
3.4 Công tác phòng cháy chữa cháy........................................................................... 85
3.5 Mở rộng của bài toán xe buýt............................................................................... 88
Kết Luận ......................................................................................................................... 94



Danh Mục Hình

Hình 1. 1: Đồ thị “lấn tổ” ................................................................................................. 4
Hình 1. 2: Đồ thị ảnh hƣởng ............................................................................................ 5
Hình 1. 3: Đồ thị biểu diễn kết quả của các cuộc thi đấu................................................. 6
Hình 1. 4: Đồ thị có ƣu tiên trƣớc sau .............................................................................. 7
Hình 1. 5: Đơn đồ thị vô hƣớng ....................................................................................... 8
Hình 1. 6: Đơn đồ thị có hƣớng ....................................................................................... 8
Hình 1. 7: Đa đồ thị vô hƣớng ......................................................................................... 9
Hình 1. 8: Đa đồ thị có hƣớng .......................................................................................... 9
Hình 1. 9: Giả đồ thị ....................................................................................................... 10
Hình 1. 10: Đồ thị biểu diễn khoảng cách đƣờng dây điện thoại giữa các thành phố .. 10
Hình 1. 11: Biểu diễn hình học của đồ thị vô hƣớng ..................................................... 14
Hình 1. 12: G là đồ thị liên thông, H không là đồ thị liên thông ................................... 22
Hình 1. 13: Đồ thị liên thông mạnh ............................................................................... 24
Hình 1. 14: Đồ thị liên thông yếu ................................................................................... 24
Hình 3. 1: Sơ đồ tƣơng tác giữa ngƣời dùng và hệ thông điều phối xe taxi .................. 83
Hình 3. 2: Sơ đồ tƣơng tác giữa khách hàng truyền thống và hệ thống điều phối xe taxi
........................................................................................................................................ 84
Hình 3. 3: Quá trình xử lí của hệ thống ứng dụng công nghệ GIS tìm đƣờng đi ngắn
nhất tới điểm cháy .......................................................................................................... 87
Hình 3. 4: Quá trình xử lí của hệ thống ứng dụng công nghệ GIS tìm vị trí trụ nƣớc gần
địa điểm cháy nhất ......................................................................................................... 88


PHẦN MỞ ĐẦU

1.1 Lý do chọn đề tài

Lý thuyết đồ thị là một trong những công cụ quan trọng có nhiều ứng dụng của
Toán rời rạc. Lý thuyết đồ thị sử dụng đồ thị để nghiên cứu, làm đơn giản hóa và giải
các bài toán trong khi việc giải bài toán đó bằng công cụ khác của toán học rất khó
khăn.
Tuy lý thuyết đồ thị đƣợc hình thành từ lâu, song nó vẫn còn ý nghĩa rất lớn đối
với hiện tại và ngày càng đƣợc cải tiến và mở rộng. Có thể nói nhà toán học Thụy Sỹ,
Leonhard Euler, là ngƣời có những ý tƣởng cơ bản đầu tiên cho sự ra đời của nó từ thế
kỉ 18. Ông đã dùng đồ thị để giải quyết bài toán cầu Konigsberg nổi tiếng. Cùng với sự
phát triển của khoa học kỹ thuật và công nghệ, nhiều bài toán về mô hình mạng giao
thông, mạng hàng không liên quan mật thiết tới lý thuyết đồ thị và thuật toán tìm kiếm
trên đồ thị.
Cùng với sự phát triển của xã hội, việc di chuyển cả về con ngƣời, hàng hóa và
thông tin, ... càng ngày càng gia tăng. Cùng với sự gia tăng đó thì yêu cầu cực tiểu về
chi phí, khoảng cách, thời gian,... cũng trở nên quan trọng hơn. Theo lý thuyết đồ thị đó
là bài toán tìm đƣờng đi ngắn nhất giữa các đỉnh của một đồ thị. Chẳng hạn, bài toán
tìm đƣờng bay ngắn nhất giữa các thành phố, bài toán tìm tuyến xe buýt từ địa điểm
này đến địa điểm kia sao cho tiết kiệm chi phí nhất, ...v.v... Bài toán tìm đƣờng đi ngắn
nhất càng trở nên cấp thiết và quan trọng đối với cả hiện tại và tƣơng lai.
Do sự quan trọng và cấp thiết của bài toán tìm đƣờng đi ngắn nhất nên đã có
nhiều nhà toán học đã đƣa ra nhiều thuật toán để giải và đƣợc vận dụng vào để giải
quyết nhiều bài toán thực tế. Trong đó các thuật toán đƣợc đƣa ra, có ba thuật toán
đƣợc nhắc đến nhiều nhất đó là thuật toán Dijkstra, thuật toán Ford-Bellman và thuật
toán Hedetniemi.
1.2 Mục đích nghiên cứu
Nội dung của luận văn là trình bày một số kiến thức cơ bản về lý thuyết đồ thị
liên quan đến bài toán tìm đƣờng đi ngắn nhất, giới thiệu bài toán tìm đƣờng đi ngắn

1



nhất và một số thuật toán để giải. Phần cuối cùng là một số ứng dụng thực tế áp dụng
thuật toán tìm đƣờng đi ngắn nhất.
1.3 Phƣơng pháp nghiên cứu
Tìm hiểu sách tham khảo, giáo trình, các bài báo cáo và một số website.
1.4 Phạm vi nghiên cứu
Luận văn tập trung trình bày một số thuật toán để giải quyết một số bài toán tìm
đƣờng đi ngắn nhất, làm sáng tỏ một số định lí có liên quan và ý tƣởng của ba thuật
toán Dijkstra, Ford-Bellman và Hedetniemi để giải quyết bài toán tìm đƣờng đi ngắn
nhất. Đồng thời, tìm hiểu và trình bày một số ứng dụng của thuật toán tìm đƣờng đi
ngắn nhất trong thực tế.
1.5 Nội dung của luận văn
Luận văn ngoài phần mở đầu, phần kết luận, tài liệu tham khảo thì còn có phần
nội dung gồm ba chƣơng:
Chương 1: Kiến thức chuẩn bị: Trình bày một số kiến thức cơ bản của đồ thị liên
quan đến bài toán và thuật toán tìm đƣờng đi ngắn nhất.
Chương 2: Bài toán tìm đường đi ngắn nhất: Giới thiệu bài toán tìm đƣờng đi
ngắn nhất. Trình bày ba thuật toán đó là Dijkstra, Ford-Bellman và Hedetniemi để giải
bài toán tìm đƣờng đi ngắn nhất.
Chương 3: Ứng dụng. Trình bày một số ứng dụng của thuật toán tìm đƣờng đi
ngắn nhất trong các bài toán thực tế hiện nay.
Tuy đã cố gắng tìm hiểu và soạn thảo, song do hạn chế về thời gian nên luận văn
tránh không khỏi thiếu sót. Rất mong nhận đƣợc sự đóng góp của quý thầy cô để luận
văn có thể hoàn thiện hơn.

2


PHẦN NỘI DUNG
Chƣơng 1
KIẾN THỨC CHUẨN BỊ

1.1 Đồ thị
1.1.1 Sơ lƣợc về đồ thị
Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh (vô hƣớng hoặc có hƣớng)
nối các đỉnh đó.
Có nhiều vấn đề thuộc các lĩnh vực rất khác nhau trong cuộc sống có thể đƣợc mô
hình hóa bằng đồ thị. Chẳng hạn, ngƣời ta có thể dùng đồ thị để biểu diễn sự cạnh tranh
giữa các loài trong một môi trƣờng sinh thái, dùng đồ thị để biểu diễn ai có ảnh hƣởng
lên ai trong một tổ chức nào đó, và cũng có thể dùng đồ thị để biểu diễn các kết cục
của cuộc thi đấu thể thao...
Nhiều lĩnh vực trong xã hội luôn tồn tại rất nhiều vấn đề và để giải quyết những
vấn đề này chúng ta cần phải áp dụng đến các công cụ của toán học. Chẳng hạn, bài
toán tính số các tổ hợp khác nhau của các chuyến bay giữa các thành phố trong một
mạng hàng không, để giải bài toán tìm đƣờng đi tham quan tất cả các đƣờng phố của
một thành phố sao cho mỗi đƣờng phố đi qua đúng một lần, bài toán tìm số các màu
cần thiết để tô các vùng khác nhau của một bản đồ sao cho các vùng có chung ranh giới
không bị trùng màu với nhau, và nhất là bài toán tìm đƣờng đi từ địa điểm này đến địa
điểm khác trong một thành phố sao cho thỏa mãn một trong các tiêu chí tiết kiệm nhất
về thời gian, nhiên liệu, khoảng cách... Để giải những bài toán dạng này sẽ trở nên dễ
dàng hơn rất nhiều nếu chúng ta áp dụng lý thuyết đồ thị trong khi việc áp dụng các
công cụ khác của toán học sẽ khó khăn hơn.
1.1.2 Một số khái niệm
Khái niệm 1: Đồ thị (graph) G  (V , E ) là một bộ phận gồm 2 tập hợp V và E ,
trong đó V   . Các phần tử của V là các đỉnh (vertices), các phần tử của E là các
cạnh (edges), mỗi cạnh tƣơng ứng với 2 đỉnh.

3


Khái niệm 2: Đồ thị có hƣớng là đồ thị có các cạnh đƣợc tạo bởi các cặp đỉnh có
thứ tự thuộc E .

Giả sử cạnh e đƣợc bắt đầu từ đỉnh u và kết thúc tại đỉnh v thì đỉnh u đƣợc gọi là
đỉnh đầu và v đƣợc gọi là đỉnh cuối. Hay nói cách khác, cạnh uv  vu .
Khái niệm 3: Đồ thị G '  (V ', E ') đƣợc gọi là một đồ thị con (subgraph) của đồ
thị G  (V , E ) nếu V '  V , E '  E .
Khái niệm 4: Đồ thị có số đỉnh và số cạnh hữu hạn đƣợc gọi là đồ thị hữu hạn
(finite graph), ngƣợc lại đƣợc gọi là đồ thị vô hạn (infinite graph).
Trong luận văn này, nếu không nói gì thêm, thì ta hiểu, đồ thị đƣợc cho là đồ thị
hữu hạn.
1.1.3 Một số ví dụ về đồ thị
a) Đồ thị “lấn tổ” (Niche Overlap) trong sinh thái học
Đồ thị “lấn tổ” là đồ thị đƣợc dùng để biểu diễn sự tƣơng tác qua lại giữa các loài
vật trong một hệ sinh thái. Chẳng hạn, sự cạnh tranh của các loài trong một hệ sinh thái
có thể mô hình hóa bằng đồ thị này. Mỗi loài đƣợc biểu diễn bằng một đỉnh. Một cạnh
vô hƣớng nối hai đỉnh nếu hai loài tƣơng ứng đƣợc biểu diễn bằng các đỉnh này là cạnh
tranh với nhau (cạnh tranh ở đây có thể là chúng có cùng chung nguồn thức ăn).
Ví dụ: Đồ thị lấn tổ giữa các loài

Hình 1. 1: Đồ thị “lấn tổ”

4


Từ đồ thị này, ta có thể thấy Sóc và chim gõ kiến là cạnh tranh thức ăn với nhau,
còn Quạ và Thú có túi thì không cạnh tranh thức ăn với nhau.
b) Đồ thị ảnh hƣởng
Khi nghiên cứu về công việc của một số bộ phận trong một công ty, công việc
của bộ phận này có thể ảnh hƣởng đến quyền hạn hoặc công việc của một hoặc một số
bộ phận khác và ngƣợc lại. Mỗi một bộ phận tƣơng ứng với một đỉnh. Khi quyền hạn
hoặc công việc của bộ phận này ảnh hƣởng lên quyền hạn hoặc công việc của bộ phận
kia thì có một cạnh có hƣớng đƣợc nối tƣơng ứng từ đỉnh này đến đỉnh kia. Đồ thị có

hƣớng này đƣợc gọi là đồ thị ảnh hƣởng.
Ví dụ: Cơ cấu tổ chức quản lí của công ty Bia cổ phần Hà Nội-Hải Phòng

Hình 1. 2: Đồ thị ảnh hƣởng
Từ đồ thị này, ta thấy cạnh Đại hội đồng cổ đông và Hội đồng quản trị, bắt đầu từ
đỉnh Đại hội đồng cổ đông và kết thúc tại đỉnh Hội đồng quản trị. Tức là, Đại hội cổ
đông có quyền và nhiệm vụ thông qua định hƣớng phát triển, quyết định các phƣơng án,
nhiệm vụ sản xuất kinh doanh; quyết định sửa đổi, bổ sung vốn điều lệ của Công ty;
bầu, miễn nhiệm, bãi nhiệm thành viên Hội đồng quản trị. Tƣơng tự, cạnh Ban giám
đốc và Phòng tổng hợp, Giám đốc điều hành quyết định các vấn đề liên quan đến hoạt
động sản xuất kinh doanh của Công ty, chịu trách nhiệm trƣớc Hội đồng quản trị về
việc thực hiện các quyền và nghĩa vụ đƣợc giao. Phòng tổng hợp đảm nhận và chịu
trách nhiệm trong công tác tham mƣu xây dựng cơ cấu tổ chức quản lý sản xuất kinh
5


doanh, quy hoạch cán bộ, lập kế hoạch đào tạo và tuyển dụng lao động, xây dựng định
mức lao động và đơn giá tiền lƣơng hàng năm; tham mƣu cho Ban giám đốc xây dựng
quy chế trả lƣơng, thƣởng.
c) Đồ thị biểu diễn kết quả của các cuộc thi đấu
Một cuộc thi đấu thể thao trong đó mỗi đội đấu với các đội khác. Kết quả của
cuộc thi đấu có thể đƣợc mô hình bằng một đồ thị có hƣớng trong đó mỗi đội tƣơng
ứng với một đỉnh. Khi đội này thắng đội kia thì có một cạnh có hƣớng tƣơng ứng đi từ
đỉnh đại diện cho đội này đến đỉnh đại diện cho đội kia. Đồ thị nhƣ vậy gọi là đồ thị
biểu diễn kết quả của các cuộc thi đấu.
Ví dụ: Kết quả của cuộc thi đấu bảng A, giải vô địch bóng đá Châu Âu năm 2016:
Đội này thắng đội kia, nếu tổng số điểm ghi bàn của đội này hơn đội kia bao gồm hai
lƣợt đấu.

Hình 1. 3: Đồ thị biểu diễn kết quả của các cuộc thi đấu

Từ đồ thị này, ta thấy đội tƣơng ứng Cộng Hòa Séc thắng Latvia. Tƣơng tự, đội
Iceland thắng Kazakhtan.
d) Đồ thị có ƣu tiên trƣớc sau
Trong khi thực hiện một công việc nào đó bao gồm một chuỗi các hoạt động khác
nhau. Các hoạt động này đƣợc sắp xếp theo một quy trình nhất định. Nghĩa là, để thực
hiện hoạt động 2 ta phải thực hiện hoạt động 1 trƣớc. Hay, để thực hiện đƣợc hoạt động
này ta cần phải thực hiện một hoặc nhiều hoạt động khác trƣớc đó. Mỗi một hoạt động

6


ta kí hiệu là một đỉnh, một cạnh có hƣớng tƣơng ứng với hai đỉnh. Đồ thị nhƣ vậy,
đƣợc gọi là đồ thị có ƣu tiên trƣớc sau.
Ví dụ: Quy trình sản xuất bánh Pía

Hình 1. 4: Đồ thị có ƣu tiên trƣớc sau
Từ đồ thị này ta thấy, để làm vỏ bánh thì chúng ta phải làm bột trƣớc. Tƣơng tự,
để phân phối sản phẩm ra thị trƣờng thì phải đƣa bánh vào hộp, đóng gói và kiểm tra
chất lƣợng trƣớc.
1.2 Một số khái niệm liên quan đến đồ thị
1.2.1 Cạnh bội và khuyên
Hai cạnh phân biệt cùng tƣơng ứng với một cặp đỉnh đƣợc gọi là hai cạnh song
song (paralleledges) hay cạnh bội.
Cạnh vv tƣơng ứng với 2 đỉnh trùng nhau gọi là một vòng hay khuyên (loop) tại v.
1.2.2 Đơn đồ thị
Đơn đồ thị G  (V , E ) là đồ thị không có khuyên và mỗi cặp đỉnh đƣợc nối với
nhau bằng không quá một cạnh.
Tức là, đồ thị không có khuyên (loop) và cạnh bội.
a) Đơn đồ thị vô hƣớng


7


Đơn đồ thị vô hướng G  (V , E ) là đơn đồ thị có các cạnh đƣợc tạo bởi các cặp
đỉnh không có thứ tự thuộc E .
Ví dụ: Đơn đồ thị vô hƣớng

Hình 1. 5: Đơn đồ thị vô hƣớng
b) Đơn đồ thị có hƣớng
Đơn đồ thị có hướng G=(V, E) là đơn đồ thị có các cạnh đƣợc tạo bởi các cặp
đỉnh có thứ tự thuộc E.
Nhận xét: Đơn đồ thị có hƣớng là một đồ thị có hƣớng, trong đó, nếu u và v là
hai đỉnh bất kì thuộc đồ thị thì chỉ đƣợc phép có tối đa một trong hai cạnh uv hoặc vu
và đồ thị không có khuyên (loop).
Ví dụ: Đơn đồ thị có hƣớng

Hình 1. 6: Đơn đồ thị có hƣớng
1.2.3 Đa đồ thị

8


Đa đồ thị G  (V , E ) là đồ thị có khuyên hoặc có ít nhất một cặp đỉnh đƣợc nối
với nhau bằng từ hai cạnh trở lên.
a) Đa đồ thị vô hƣớng
Đa đồ thị vô hướng G  (V , E ) là đa đồ thị có các cạnh đƣợc tạo bởi các cặp đỉnh
không có thứ tự thuộc E .
Ví dụ: Đa đồ thị vô hƣớng

Hình 1. 7: Đa đồ thị vô hƣớng

b) Đa đồ thị có hƣớng
Đa đồ thị có hướng G  (V , E ) là đa đồ thị có các cạnh đƣợc tạo bởi các cặp đỉnh
có thứ tự thuộc E .
Nhận xét: Đa đồ thị có hƣớng là một đồ thị có hƣớng, trong đó, đồ thị có khuyên
hoặc ít nhất có một cặp đỉnh u và v , là hai đỉnh của đồ thị có cả hai cạnh uv và vu .
Ví dụ: Đa đồ thị có hƣớng

Hình 1. 8: Đa đồ thị có hƣớng
9


1.2.4 Giả đồ thị
Giả đồ thị vô hướng (có hướng) là đồ thị vô hƣớng (có hƣớng) có chứa cạnh bội
và khuyên..
Ví dụ: Giả đồ thị

Hình 1. 9: Giả đồ thị
1.2.5 Đồ thị có trọng số
Cho đồ thị hữu hạn G  (V , E ) , với mỗi cạnh e  E đƣợc tạo bởi hai đỉnh u, v .
Ta đặt tƣơng ứng với một số thực w(u, v) và gọi là trọng số của e . Trọng số có thể là
độ dài khoảng cách, thời gian, chi phí, lợi nhuận,... Đồ thị có các cạnh đƣợc đặt tƣơng
ứng trọng số nhƣ trên đƣợc gọi là đồ thị có trọng số.
Ví dụ: Đồ thị biểu diễn khoảng cách đƣờng dây điện thoại giữa các thành phố.

Hình 1. 10: Đồ thị biểu diễn khoảng cách đƣờng dây điện thoại
giữa các thành phố

10



1.2.6 Bậc của đỉnh trong đồ thị
a) Đối với đồ thị vô hƣớng
Đỉnh v của đồ thị G đƣợc gọi là có bậc n nếu v kề với n đỉnh khác ( v là đầu mút
của n cạnh). Đỉnh u và v đƣợc gọi là kề nhau nếu có một cạnh nối hai đỉnh u và v .
Ký hiệu: deg(v) .
Chú ý:
- Mỗi khuyên (loop) tại đỉnh v đƣợc tính là 2 cạnh tới đỉnh v . Khi đó, đỉnh v có
bậc 2.
- Đỉnh có bậc 0 gọi là đỉnh cô lập (isolated vertex). Tức là, đỉnh không kề với các
đỉnh khác của đồ thị.
- Đỉnh có bậc 1 gọi là đỉnh treo (pendant vertex). Tức là, đỉnh chỉ kề với duy nhất
một đỉnh khác của đồ thị.
- Cạnh tới đỉnh treo gọi là cạnh treo (pendant edge). Hay nói cách khác, cạnh treo
là cạnh nối một đỉnh khác của đồ thị với đỉnh treo.
- Đồ thị mà mọi đỉnh đều là đỉnh cô lập gọi là đồ thị rỗng (null graph).
Ví dụ: Cho đồ thị sau

Ta có:

deg  A  4; deg  B   4; deg  C   5; deg  D   3;
deg  E   5; deg  F   5;deg  G   0.
11


 Định lý 1: Trong mọi đơn đồ thị G = (V, E) vô hƣớng, tổng số bậc của các
đỉnh của G bằng 2 lần số cạnh. Nghĩa là ta có:
∑

( )
Chứng minh


Nếu e là khuyên tại đỉnh v thì nó đƣợc đếm 2 lần khi tính deg  v  . Còn nếu e là
cạnh nối hai đỉnh u, v thì nó cũng đƣợc đếm 2 lần, một lần khi tính deg  u  và một lần
khi tính deg  v  .
Hệ quả: Trong mọi đồ thị G  (V , E ) , ta có:
1. Số các đỉnh bậc lẻ của một đồ thị là một số chẵn.
Thật vậy, giả sử V1, V2 tƣơng ứng là tập các đỉnh bậc chẵn và tập các đỉnh bậc lẻ
của đồ thị vô hƣớng G  (V , E ) có m cạnh. Ta có:

2m   deg(v)   deg(v)   deg(v)
vV
vV1
vV2
Vì deg(v) chẵn với mọi v V1 nên  deg(v) là một số chẵn. Mặc khác, deg  v 
vV2
lại là số lẻ khi v V2 nên để  deg(v) là một số chẵn thì số các đỉnh bậc lẻ phải là
vV2
một số chẵn.
2. Tổng bậc của các đỉnh bậc lẻ trong một đồ thị là một số chẵn.
Thật vậy, cho đồ thị G  (V , E ) , gọi A là tổng số bậc của các đỉnh có bậc chẵn, B
là tổng số bậc của các đỉnh có bậc lẻ.Theo định lí 1 thì A+B=2m (chẵn), với m là số
cạnh của đồ thị. Vì A là tổng các số chẵn nên là số chẵn. Vậy, B là số chẵn.
 Định lý 2: Trong mọi đồ thị G  V , E  , có | V | 2 thì tồn tại ít nhất hai đỉnh
cùng bậc.
Chứng minh

12


Giả sử đồ thị G  (V , E ) là đồ thị tùy ý có | V | n  2 . Ta xét hai trƣờng hợp sau:

Trƣờng hợp 1: Đồ thị có đỉnh bậc 0. Khi đó, trong đồ thị không có đỉnh nào kề
với đỉnh có bậc 0, do đó đỉnh có bậc lớn nhất là n-2 (và đỉnh có bậc thấp nhất là bậc 0).
Vậy, bậc của mỗi đỉnh của đồ thị sẽ thuộc tập hợp {0; 1; 2; ...; n-2}. Tập hợp này gồm
n-1 phần tử.
Trƣờng hợp 2: Đồ thị không có đỉnh bậc 0. Khi đó có thể có một đỉnh nào đó
liền kề với tất các cả đỉnh còn lại, nên đỉnh có bậc cao nhất lúc này là n-1 và đỉnh có
bậc nhỏ nhất là 1. Vậy, bậc của mỗi đỉnh thuộc tập hợp {1; 2; 3; ...; n-1}. Tập hợp này
gồm n-1 phần tử.
Vậy, trong cả hai trƣờng hợp bậc của mỗi đỉnh đều thuộc tập hợp số gồm n-1
phần tử. Do đó, số đỉnh của đồ thị bằng n nên theo nguyên lý Dirichlet thì phải có ít
nhất hai đỉnh cùng bậc.
Nguyên lí Dirichlet tổng quát: Nếu xếp nhiều hơn n đối tƣợng vào k cái hộp thì
tồn tại ít nhất một hộp chứ không ít hơn [n/k] + 1 đối tƣợng (ký hiệu [x] là phần
nguyên của x, đó là số nguyên không vƣợt quá x).
 Định lý 3: Trong mọi đồ thị G = (V, E), có |V| >2 có đúng hai đỉnh cùng bậc
thì hai đỉnh này không thể đồng thời có bậc 0 hoặc bậc n-1.
b) Đối với đồ thị có hƣớng
Cho đồ thị có hƣớng G  V , E  và v V là một đỉnh nào đó của đồ thị.
Bậc vào của v kí hiệu là deg   v  là số cạnh đi các đỉnh khác tới v .
Bậc ra của v đƣợc kí hiệu là deg   v  là số cạnh đi từ các đỉnh v tới các đỉnh
khác.
Bậc của v kí hiệu là deg  v   deg   v   deg   v .
 Định lí 4: Giả sử G  V , E  là một đồ thị có hƣớng. Khi đó:



 deg (v)   deg (v) | E |
vV
vV


13


Chứng minh
Với mỗi cạnh của G có một đỉnh đầu và một đỉnh cuối thì tổng các bậc vào bằng
tổng các bậc ra và cùng bằng số cạnh.
1.3 Biễu diễn đồ thị
Một số đồ thị có thể biểu diễn đƣợc bằng hình học, ma trận hay một bảng.
1.3.1 Biễu điễn đồ thị bằng hình học
Ngƣời ta thƣờng biểu diễn hình học của đồ thị nhƣ sau:
- Biểu diễn mỗi đỉnh của đồ thị bằng một điểm (vòng tròn nhỏ, ô vuông nhỏ).
- Cạnh e đƣợc tạo bởi hai đỉnh u và v thì ta gọi là cạnh e tới hay liên thuộc
(incident) với các đỉnh u và v. Khi đó, u và v đƣợc gọi là hai đỉnh kề.
- Một cạnh đƣợc biểu diễn bởi một đƣờng (cong hay thẳng) nối 2 đỉnh liên thuộc
với cạnh đó.
Ví dụ: Cho đơn đồ thị vô hƣớng G có: V = {a, b, c, d, e} và E = {ab, ac, ad, bd,
cd, ce}. Đồ thị đƣợc biểu diễn bằng hình học nhƣ sau:

Hình 1. 11: Biểu diễn hình học của đồ thị vô hƣớng

14


Chú ý: Khi biểu diễn hình học các đồ thị, giao của các cạnh chƣa chắc là đỉnh
của đồ thị.
Ví dụ: Cho đa đồ thị vô hƣớng G có: V = {u, v, m, n} và E = {uv, um, vm, mn,
nm}. Đƣợc biễu diễn nhƣ sau:

1.3.2 Biểu diễn đồ thị bằng ma trận
Ngƣời ta có thể biểu diễn đồ thị bằng ma trận. Có 2 kiểu ma trận thƣờng đƣợc

dùng để biểu diễn đồ thị:
- Ma trận liên kết hay liền kề (adjacency matrix).
- Ma trận liên thuộc (incidence matrix).
 Ma trận liền kề đối với đồ thị vô hƣớng
Cho ma trận G  V , E  có n đỉnh v1, v2 , , vn . Ma trận liền kề của G tƣơng
ứng với thứ tự các đỉnh v1, v2 , , vn là một ma trận A cấp n.
A = (aij)n trong đó: aij là số cạnh nối vi với vj
Lƣu ý: Mỗi khuyên đƣợc tính là hai cạnh.
Nhận xét: 1. Ma trận liền kề của đồ thị vô hƣớng là một ma trận đối xứng.
2. Số khuyên trong đồ thị bằng một nữa tổng các số hạng trên đƣờng
chéo chính của ma trận liền kề.
Ví dụ: Cho đồ thị sau:

15


Đồ thị đã cho có ma trận liền liền kề là:
a
a
b
c

d
e

0
1

1


0
0

b

c

d

e

1 1 0 0
0 1 1 1

1 0 1 1

1 1 0 1
1 1 1 2 

Chú ý: Ma trận liền kề của một đồ thị khác nhau tùy thuộc vào thứ tự liệt kê các
đỉnh. Do đó, có tới n! ma trận liền kề khác nhau của một đồ thị n đỉnh vì có n! cách sắp
xếp n đỉnh.
Ví dụ: Hãy vẽ đồ thị có ma trận liền kề theo thứ tự của các đỉnh là a, b, c, d.
[

]



 Ma trận liền kề đối với đồ thị có hƣớng


16


Cho ma trận G  V , E  có n đỉnh v1, v2 , , vn . Ma trận liền kề của G tƣơng
ứng với thứ tự các đỉnh v1, v2 , , vn là một ma trận A cấp n.
A = (aij)n trong đó: aij là số cạnh đi từ vi với vj.
Ví dụ: Đồ thị sau có ma trận liền kề là:

V1 V2 V3 V4 V5 V6
V1
V2
V3
V4
V5
V6

0
1

1

0
0

0

1 1 0 0 0
0 1 1 0 0


1 0 1 0 0

1 1 0 1 1
0 0 1 0 1

0 0 1 1 0

 Ma trận liên thuộc đối với đồ thị vô hƣớng
Ngƣời ta còn dùng ma trận liên thuộc để biểu diễn đồ thị. Cho G = (V, E) là một
đồ thị vô hƣớng với v1, v2, …, vn là các đỉnh và e1, e2, …, em là các cạnh của G. Khi đó,
ma trận liên thuộc của G theo thứ tự trên của V và E là một ma trận M = (mij)nxm với :
{
Ví dụ: Cho đồ thị sau:

17


Có ma trận liên thuộc nhƣ sau:
e1 e2 e3 e4 e5 e6 e7

A
B
C
D
E

1
1

0


0
0

1 1 1 0 0 0
0 0 0 0 1 0

1 0 0 1 0 1

0 1 0 0 1 0
0 0 1 1 0 1 

Nhận xét:
Trong trƣờng hợp, nếu trong ma trận liên thuộc có hai cột giống nhau thì hai cạnh
tƣơng ứng là cạnh bội. Trong ví dụ trên, ta thấy, cột e5 và e7 giống nhau, nên cạnh e5 và
e7 là cạnh bội.
Cạnh của đồ thị là khuyên khi và chỉ khi cột tƣơng ứng với nó trong ma trận liên
thuộc chỉ chứa duy nhất một số 1. Khi đó số 1 thuộc hàng tƣơng ứng với đỉnh liên
thuộc với khuyên.
 Ma trận liên thuộc đối với đồ thị có hƣớng

18


Cho G  V , E  là một đồ thị có hƣớng với v1, v2 , , vn là các đỉnh và

e1, e2 , , em là các cạnh của G. Khi đó, ma trận liên thuộc của G theo thứ tự trên của
V và E là một ma trận M = (mij)nxm với :

{

Ví dụ: Cho đồ thị có hƣớng sau:

Đồ thị này có ma trận liên thuộc là:
e1
V1  1
V2  1



V3  0
V4  0

V5  0



V6  0

e2

e3

e4

e5

e6

e7


e8

0
0

1 1 0 1 0 0 0 

0 0 1 1 1 1 0 
0 0 0 0 0 1 1 

0 0 0 0 1 0 1 
1
0

0
1

0
1

0
0

0
0

0
0

1.3.3 Biểu diễn đồ thị bằng bảng

Ta có thể biểu diễn đồ thị không có cạnh bội bằng bảng hay còn gọi là danh sách
liền kề. Danh sách này chỉ rõ các đỉnh nối với mỗi đỉnh của đồ thị.
Ví dụ: Dùng danh sách liền kề để biểu diễn đồ thị sau:

19