Bài toán tìm đường đi ngắn nhất và ứng dụng

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (2.09 MB, 102 trang )

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

kinh nghiệm tay nghề quý báu để làm hành trang cho em trên con đƣờng giảng dạy và nâng caotrình độ của mình sau này. Em xin gửi lời cảm ơn thâm thúy đến cô Phạm Thị Vui, là giáo viên hƣớng dẫn luậnvăn cho em. Nhờ sự hƣớng dẫn và trợ giúp tận tình của cô đã giúp em hoàn thành xong tốtluận văn này. Em xin gửi lời cảm ơn đến bè bạn, mái ấm gia đình và mọi ngƣời xung quanh đãđộng viên, ủng hộ và trợ giúp em trong suốt quy trình học tập và triển khai xong luận vănnày. Trong quy trình triển khai xong luận văn, tuy em đã cố gắng nỗ lực nổ lực nhƣng do thờigian có hạn nên chắc như đinh vẫn còn nhiều thiếu sót. Rất mong nhận đƣợc quan điểm góp ýquý báu của những Thầy Cô và bạn đọc. Cần Thơ, ngày tháng năm năm nay sinh viên thực hiệnLƣu Thị Hồng TrangMục LụcPHẦN MỞ ĐẦU ……………………………………………………………………………………………….. 11.1 Lý do chọn đề tài ………………………………………………………………………………………. 11.2 Mục đích nghiên cứu và điều tra …………………………………………………………………………………. 11.3 Phƣơng pháp nghiên cứu và điều tra ……………………………………………………………………………. 21.4 Phạm vi điều tra và nghiên cứu …………………………………………………………………………………… 21.5 Nội dung của luận văn ……………………………………………………………………………….. 2PH ẦN NỘI DUNG ……………………………………………………………………………………………. 3C hƣơng 1 ………………………………………………………………………………………………………….. 3KI ẾN THỨC CHUẨN BỊ …………………………………………………………………………………… 31.1 Đồ thị ………………………………………………………………………………………………………. 31.1.1 Sơ lƣợc về đồ thị ……………………………………………………………………………………. 31.1.2 Một số khái niệm ……………………………………………………………………………………. 31.1.3 Một số ví dụ về đồ thị …………………………………………………………………………….. 41.2 Một số khái niệm tương quan đến đồ thị …………………………………………………………. 71.2.1 Cạnh bội và khuyên ………………………………………………………………………………… 71.2.2 Đơn đồ thị ……………………………………………………………………………………………… 71.2.3 Đa đồ thị ……………………………………………………………………………………………….. 81.2.4 Giả đồ thị …………………………………………………………………………………………….. 101.2.5 Đồ thị có trọng số …………………………………………………………………………………. 101.2.6 Bậc của đỉnh trong đồ thị ………………………………………………………………………. 111.3 Biễu diễn đồ thị ………………………………………………………………………………………. 141.3.1 Biễu điễn đồ thị bằng hình học ………………………………………………………………. 141.3.2 Biểu diễn đồ thị bằng ma trận ………………………………………………………………… 151.3.3 Biểu diễn đồ thị bằng bảng …………………………………………………………………….. 191.4 Đƣờng đi – quy trình – tính liên thông trong đồ thị ……………………………………… 201.4.1 Đƣờng đi ……………………………………………………………………………………………… 201.4.3 Tính liên thông trong đồ thị …………………………………………………………………… 21C hƣơng 2 ………………………………………………………………………………………………………… 25B ÀI TOÁN TÌM ĐƢỜNG ĐI NGẮN NHẤT ……………………………………………………… 252.1 Bài Toán Tìm Đƣờng Đi Ngắn Nhất ………………………………………………………….. 252.1.1 Giới thiệu bài toán ………………………………………………………………………………… 252.1.2 Phát biểu bài toán tìm đƣờng đi ngắn nhất trên đồ thị ……………………………….. 252.1.3 Một số khái niệm ………………………………………………………………………………….. 262.2 Thuật toán Dijkstra ………………………………………………………………………………….. 272.2.1 Giới thiệu thuật toán Dijkstra …………………………………………………………………. 272.2.2 Thuật toán Dijkstra ……………………………………………………………………………….. 292.2.3 Ví dụ …………………………………………………………………………………………………… 332.2.4 Định lí 1 ………………………………………………………………………………………………. 392.2.5 Định lí 2 ………………………………………………………………………………………………. 392.2.6 Định lí 3 ………………………………………………………………………………………………. 412.2.7 Lƣu đồ thuật toán Dijkstra …………………………………………………………………….. 422.3 Thuật toán Ford-Bellman …………………………………………………………………………. 432.3.1 Giới thiệu thuật toán Ford-Bellman ………………………………………………………… 432.3.2 Tƣ tƣởng của thuật toán Ford-Bellman ……………………………………………………. 442.3.3 Ví dụ …………………………………………………………………………………………………… 452.3.4 Lƣu đồ thuật toán Ford-Bellman …………………………………………………………….. 522.4 Thuật toán Hedetniemi …………………………………………………………………………….. 532.4.1 Giới thiệu thuật toán Hedetniemi ……………………………………………………………. 532.4.2 Phép cộng hai ma trận Hedetniemi …………………………………………………………. 532.4.3 Thuật toán Hedetniemi ………………………………………………………………………….. 542.4.5 Lƣu đồ thuật toán Hidetniemi ………………………………………………………………… 572.5 Một số bài toán tìm đƣờng đi ngắn nhất lan rộng ra ………………………………………… 582.5.1 Bài toán 1 ……………………………………………………………………………………………. 582.5.2 Bài toán 2 ……………………………………………………………………………………………. 64C hƣơng 3 ………………………………………………………………………………………………………… 76 ỨNG DỤNG …………………………………………………………………………………………………… 763.1 Tổng quan về ứng dụng của những bài toán tìm đƣờng đi ngắn nhất phối hợp với bảnđồ số …………………………………………………………………………………………………………… 763.2 Bài toán xe buýt ……………………………………………………………………………………… 773.2.1 Hiện trạng mạng lưới hệ thống xe buýt …………………………………………………………………… 773.2.2 Cách thức đón xe buýt …………………………………………………………………………… 783.2.3 Chức năng chính và những nhu yếu cần có của ứng dụng WebGIS …………….. 793.2.4 Tìm đƣờng đi ngắn nhất ………………………………………………………………………… 793.2.5 Tìm trạm dừng / nhà chờ gần nhất ……………………………………………………………. 813.3 Bài toán xe taxi ……………………………………………………………………………………….. 823.4 Công tác phòng cháy chữa cháy ………………………………………………………………… 853.5 Mở rộng của bài toán xe buýt ……………………………………………………………………. 88K ết Luận …………………………………………………………………………………………………………. 94D anh Mục HìnhHình 1. 1 : Đồ thị “ lấn tổ ” ……………………………………………………………………………………. 4H ình 1. 2 : Đồ thị ảnh hƣởng ……………………………………………………………………………….. 5H ình 1. 3 : Đồ thị màn biểu diễn tác dụng của những cuộc tranh tài …………………………………………. 6H ình 1. 4 : Đồ thị có ƣu tiên trƣớc sau …………………………………………………………………… 7H ình 1. 5 : Đơn đồ thị vô hƣớng …………………………………………………………………………… 8H ình 1. 6 : Đơn đồ thị có hƣớng …………………………………………………………………………… 8H ình 1. 7 : Đa đồ thị vô hƣớng …………………………………………………………………………….. 9H ình 1. 8 : Đa đồ thị có hƣớng ……………………………………………………………………………… 9H ình 1. 9 : Giả đồ thị …………………………………………………………………………………………. 10H ình 1. 10 : Đồ thị màn biểu diễn khoảng cách đƣờng dây điện thoại cảm ứng giữa những thành phố .. 10H ình 1. 11 : Biểu diễn hình học của đồ thị vô hƣớng …………………………………………….. 14H ình 1. 12 : G là đồ thị liên thông, H không là đồ thị liên thông …………………………….. 22H ình 1. 13 : Đồ thị liên thông mạnh ……………………………………………………………………. 24H ình 1. 14 : Đồ thị liên thông yếu ……………………………………………………………………….. 24H ình 3. 1 : Sơ đồ tƣơng tác giữa ngƣời dùng và hệ thông điều phối xe taxi ……………… 83H ình 3. 2 : Sơ đồ tƣơng tác giữa người mua truyền thống lịch sử và mạng lưới hệ thống điều phối xe taxi ………………………………………………………………………………………………………………………. 84H ình 3. 3 : Quá trình xử lí của mạng lưới hệ thống ứng dụng công nghệ tiên tiến GIS tìm đƣờng đi ngắnnhất tới điểm cháy ……………………………………………………………………………………………. 87H ình 3. 4 : Quá trình xử lí của mạng lưới hệ thống ứng dụng công nghệ tiên tiến GIS tìm vị trí trụ nƣớc gầnđịa điểm cháy nhất …………………………………………………………………………………………… 88PH ẦN MỞ ĐẦU1. 1 Lý do chọn đề tàiLý thuyết đồ thị là một trong những công cụ quan trọng có nhiều ứng dụng củaToán rời rạc. Lý thuyết đồ thị sử dụng đồ thị để nghiên cứu và điều tra, làm đơn giản hóa và giảicá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 triết lý đồ thị đƣợc hình thành từ lâu, tuy nhiên nó vẫn còn ý nghĩa rất lớn đốivới hiện tại và ngày càng đƣợc nâng cấp cải tiến và lan rộng ra. 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 tiên phong cho sự sinh ra của nó từ thếkỉ 18. Ông đã dùng đồ thị để xử lý 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ệ tiên tiến, nhiều bài toán về quy mô mạng giaothông, mạng hàng không tương quan mật thiết tới kim chỉ nan đồ thị và thuật toán tìm kiếmtrên đồ thị. Cùng với sự tăng trưởng của xã hội, việc chuyển dời cả về con ngƣời, sản phẩm & hàng hóa vàthông tin, … ngày càng ngày càng tăng. Cùng với sự ngày càng tăng đó thì nhu yếu cực tiểu vềchi phí, khoảng cách, thời hạn, … cũng trở nên quan trọng hơn. Theo kim chỉ nan đồ thị đólà bài toán tìm đƣờng đi ngắn nhất giữa những đỉnh của một đồ thị. Chẳng hạn, bài toántìm đƣờng bay ngắn nhất giữa những thành phố, bài toán tìm tuyến xe buýt từ địa điểmnày đến khu vực kia sao cho tiết kiệm chi phí ngân sách nhất, … v.v… Bài toán tìm đƣờng đi ngắnnhất càng trở nên cấp thiết và quan trọng so 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ảiquyết nhiều bài toán trong thực tiễn. Trong đó những 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ậttoán Hedetniemi. 1.2 Mục đích nghiên cứuNội dung của luận văn là trình diễn một số ít kỹ năng và kiến thức cơ bản về triết lý đồ thịliên quan đến bài toán tìm đƣờng đi ngắn nhất, ra mắt bài toán tìm đƣờng đi ngắnnhất và một số ít thuật toán để giải. Phần ở đầu cuối là 1 số ít ứng dụng thực tiễn áp dụngthuật toán tìm đƣờng đi ngắn nhất. 1.3 Phƣơng pháp nghiên cứuTìm hiểu sách tìm hiểu thêm, giáo trình, những bài báo cáo giải trình và một số ít website. 1.4 Phạm vi nghiên cứuLuận văn tập trung trình diễn 1 số ít thuật toán để xử lý một số ít bài toán tìmđƣờng đi ngắn nhất, làm sáng tỏ 1 số ít định lí có tương quan và ý tƣởng của ba thuậttoán Dijkstra, Ford-Bellman và Hedetniemi để xử lý bài toán tìm đƣờng đi ngắnnhất. Đồng thời, khám phá và trình diễn một số ít ứng dụng của thuật toán tìm đƣờng đingắn nhất trong thực tiễn. 1.5 Nội dung của luận vănLuận văn ngoài phần khởi đầu, phần Kết luận, tài liệu tìm hiểu thêm thì còn có phầnnội dung gồm ba chƣơng : Chương 1 : Kiến thức sẵn sàng chuẩn bị : Trình bày một số ít kỹ năng và kiến thức cơ bản của đồ thị liênquan đế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 đingắn nhất. Trình bày ba thuật toán đó là Dijkstra, Ford-Bellman và Hedetniemi để giảibài toán tìm đƣờng đi ngắn nhất. Chương 3 : Ứng dụng. Trình bày một số ít ứng dụng của thuật toán tìm đƣờng đingắn nhất trong những bài toán thực tiễn lúc bấy giờ. Tuy đã cố gắng nỗ lực khám phá và soạn thảo, tuy nhiên do hạn chế về thời hạn nên luận văntránh không khỏi thiếu sót. Rất mong nhận đƣợc sự góp phần của quý thầy cô để luậnvăn hoàn toàn có thể triển khai xong hơn. PHẦN NỘI DUNGChƣơng 1KI Ế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 những đỉnh và những cạnh ( vô hƣớng hoặc có hƣớng ) nối những đỉnh đó. Có nhiều yếu tố thuộc những nghành rất khác nhau trong đời sống hoàn toàn có thể đƣợc môhình hóa bằng đồ thị. Chẳng hạn, ngƣời ta hoàn toàn có thể dùng đồ thị để màn biểu diễn sự cạnh tranhgiữa những loài trong một môi trƣờng sinh thái xanh, dùng đồ thị để trình diễn ai có ảnh hƣởnglên ai trong một tổ chức triển khai nào đó, và cũng hoàn toàn có thể dùng đồ thị để màn biểu diễn những kết cụccủa cuộc tranh tài thể thao … Nhiều nghành nghề dịch vụ trong xã hội luôn sống sót rất nhiều yếu tố và để xử lý nhữngvấn đề này tất cả chúng ta cần phải vận dụng đến những công cụ của toán học. Chẳng hạn, bàitoán tính số những tổng hợp khác nhau của những chuyến bay giữa những thành phố trong mộtmạng hàng không, để giải bài toán tìm đƣờng đi thăm quan toàn bộ những đƣờng phố củamột thành phố sao cho mỗi đƣờng phố đi qua đúng một lần, bài toán tìm số những màucần thiết để tô những vùng khác nhau của một map sao cho những vùng có chung ranh giớikhông bị trùng màu với nhau, và nhất là bài toán tìm đƣờng đi từ khu vực này đến địađiểm khác trong một thành phố sao cho thỏa mãn nhu cầu một trong những tiêu chuẩn tiết kiệm chi phí nhấtvề thời hạn, nguyên vật 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 tất cả chúng ta vận dụng triết lý đồ thị trong khi việc vận dụng cáccông cụ khác của toán học sẽ khó khăn vất vả hơn. 1.1.2 Một số khái niệmKhá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 thành phần của V là những đỉnh ( vertices ), những thành phần của E là cáccạnh ( edges ), mỗi cạnh tƣơng ứng với 2 đỉnh. Khái niệm 2 : Đồ thị có hƣớng là đồ thị có những cạnh đƣợc tạo bởi những cặp đỉnh cóthứ tự thuộc E. Giả sử cạnh e đƣợc mở màn 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 xanh họcĐồ thị “ lấn tổ ” là đồ thị đƣợc dùng để màn biểu diễn sự tƣơng tác qua lại giữa những loàivật trong một hệ sinh thái. Chẳng hạn, sự cạnh tranh đối đầu của những loài trong một hệ sinh tháicó thể quy mô hóa bằng đồ thị này. Mỗi loài đƣợc trình diễn bằng một đỉnh. Một cạnhvô hƣớng nối hai đỉnh nếu hai loài tƣơng ứng đƣợc màn biểu diễn bằng những đỉnh này là cạnhtranh với nhau ( cạnh tranh đối đầu ở đây hoàn toàn có thể là chúng có cùng chung nguồn thức ăn ). Ví dụ : Đồ thị lấn tổ giữa những loàiHình 1. 1 : Đồ thị “ lấn tổ ” Từ đồ thị này, ta hoàn toàn có thể thấy Sóc và chim gõ kiến là cạnh tranh đối đầu thức ăn với nhau, còn Quạ và Thú có túi thì không cạnh tranh đối đầu thức ăn với nhau. b ) Đồ thị ảnh hƣởngKhi điều tra và nghiên cứu về việc làm của 1 số ít bộ phận trong một công ty, công việccủa bộ phận này hoàn toàn có thể ảnh hƣởng đến quyền hạn hoặc việc làm 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ạnhoặc việc làm của bộ phận này ảnh hƣởng lên quyền hạn hoặc việc làm của bộ phậnkia 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 triển khai quản lí của công ty Bia CP Hà Nội-Hải PhòngHình 1. 2 : Đồ thị ảnh hƣởngTừ đồ thị này, ta thấy cạnh Đại hội đồng cổ đông và Hội đồng quản trị, mở màn 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à trách nhiệm trải qua định hƣớng tăng trưởng, quyết định hành động những phƣơng án, trách nhiệm sản xuất kinh doanh thương mại ; quyết định hành động sửa đổi, bổ trợ vốn điều lệ của Công ty ; bầu, không bổ 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 quản lý quyết định hành động những yếu tố tương quan đến hoạtđộng sản xuất kinh doanh thương mại của Công ty, chịu nghĩa vụ và trách nhiệm trƣớc Hội đồng quản trị vềviệc triển khai những quyền và nghĩa vụ và trách nhiệm đƣợc giao. Phòng tổng hợp đảm nhiệm và chịutrách nhiệm trong công tác làm việc tham mƣu thiết kế xây dựng cơ cấu tổ chức tổ chức triển khai quản trị sản xuất kinhdoanh, quy hoạch cán bộ, lập kế hoạch giảng dạy và tuyển dụng lao động, kiến thiết xây dựng địnhmứ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ựngquy chế trả lƣơng, thƣởng. c ) Đồ thị màn biểu diễn hiệu quả của những cuộc thi đấuMột cuộc tranh tài thể thao trong đó mỗi đội đấu với những đội khác. Kết quả củacuộc tranh tài hoàn toàn có thể đƣợc quy mô 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 thay mặt cho đội này đến đỉnh đại diện thay mặt cho đội kia. Đồ thị nhƣ vậy gọi là đồ thịbiểu diễn hiệu quả của những cuộc tranh tài. Ví dụ : Kết quả của cuộc tranh tài bảng A, giải vô địch bóng đá Châu Âu năm năm nay : Độ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 gồm có hailƣợt đấu. Hình 1. 3 : Đồ thị trình diễn tác dụng của những cuộc thi đấuTừ đồ thị này, ta thấy đội tƣơng ứng Cộng Hòa Séc thắng Latvia. Tƣơng tự, độiIceland thắng Kazakhtan. d ) Đồ thị có ƣu tiên trƣớc sauTrong khi triển khai một việc làm nào đó gồm có một chuỗi những hoạt động giải trí khácnhau. Các hoạt động giải trí này đƣợc sắp xếp theo một quá trình nhất định. Nghĩa là, để thựchiện hoạt động giải trí 2 ta phải thực thi hoạt động giải trí 1 trƣớc. Hay, để thực thi đƣợc hoạt độngnày ta cần phải thực thi một hoặc nhiều hoạt động giải trí khác trƣớc đó. Mỗi một hoạt độngta 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íaHình 1. 4 : Đồ thị có ƣu tiên trƣớc sauTừ đồ thị này ta thấy, để làm vỏ bánh thì tất cả chúng ta phải làm bột trƣớc. Tƣơng tự, để phân phối mẫu sản phẩm ra thị trƣờng thì phải đƣa bánh vào hộp, đóng gói và kiểm trachất lƣợng trƣớc. 1.2 Một số khái niệm tương quan đến đồ thị1. 2.1 Cạnh bội và khuyênHai 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 songsong ( 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ớinhau 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Đơn đồ thị vô hướng G  ( V, E ) là đơn đồ thị có những cạnh đƣợc tạo bởi những cặpđỉnh không có thứ tự thuộc E. Ví dụ : Đơn đồ thị vô hƣớngHình 1. 5 : Đơn đồ thị vô hƣớngb ) Đơn đồ thị có hƣớngĐơn đồ thị có hướng G = ( V, E ) là đơn đồ thị có những cạnh đƣợc tạo bởi những 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 vuvà đồ thị không có khuyên ( loop ). Ví dụ : Đơn đồ thị có hƣớngHình 1. 6 : Đơn đồ thị có hƣớng1. 2.3 Đa đồ thịĐa đồ thị G  ( V, E ) là đồ thị có khuyên hoặc có tối thiểu một cặp đỉnh đƣợc nốivớ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ó những cạnh đƣợc tạo bởi những cặp đỉnhkhông có thứ tự thuộc E. Ví dụ : Đa đồ thị vô hƣớngHình 1. 7 : Đa đồ thị vô hƣớngb ) Đa đồ thị có hƣớngĐa đồ thị có hướng G  ( V, E ) là đa đồ thị có những cạnh đƣợc tạo bởi những cặp đỉnhcó 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ênhoặc tối thiểu 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ƣớngHình 1. 8 : Đa đồ thị có hƣớng1. 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ộivà 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ố ít thực w ( u, v ) và gọi là trọng số của e. Trọng số hoàn toàn có thể làđộ dài khoảng cách, thời hạn, ngân sách, doanh thu, … Đồ thị có những 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ị màn biểu diễn khoảng cách đƣờng dây điện thoại thông minh giữa những thành phố. Hình 1. 10 : Đồ thị màn biểu diễn khoảng cách đƣờng dây điện thoạigiữa những thành phố101. 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útcủ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ấtmộ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 treolà 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ị sauTa 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 minhNế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ầnkhi tính deg  v .   Hệ quả : Trong mọi đồ thị G  ( V, E ), ta có : 1. Số những đỉ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 những đỉnh bậc chẵn và tập những đỉnh bậc lẻcủa đồ thị vô hƣớng G  ( V, E ) có m cạnh. Ta có : 2 m   deg ( v )   deg ( v )   deg ( v ) v  Vv  V1v  V2Vì 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  V2lại là số lẻ khi v  V2 nên để  deg ( v ) là một số chẵn thì số những đỉnh bậc lẻ phải làv  V2một số chẵn.  2. Tổng bậc của những đỉ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 những đỉnh có bậc chẵn, Blà tổng số bậc của những đỉnh có bậc lẻ. Theo định lí 1 thì A + B = 2 m ( chẵn ), với m là sốcạnh của đồ thị. Vì A là tổng những 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ì sống sót tối thiểu hai đỉnhcùng bậc. Chứng minh12Giả 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ồmn-1 thành phần. Trƣờng hợp 2 : Đồ thị không có đỉnh bậc 0. Khi đó hoàn toàn có thể có một đỉnh nào đóliền kề với tất những 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àygồm n-1 thành phần. 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-1phần tử. Do đó, số đỉnh của đồ thị bằng n nên theo nguyên lý Dirichlet thì phải có ítnhấ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ối thiểu một hộp chứ không ít hơn [ n / k ] + 1 đối tƣợng ( ký hiệu [ x ] là phầnnguyê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ậcthì hai đỉnh này không hề đồng thời có bậc 0 hoặc bậc n-1. b ) Đối với đồ thị có hƣớngCho đồ 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 những đỉ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ừ những đỉnh v tới những đỉnhkhá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  Vv  V13Chứng minhVới mỗi cạnh của G có một đỉnh đầu và một đỉnh cuối thì tổng những bậc vào bằngtổng những bậc ra và cùng bằng số cạnh. 1.3 Biễu diễn đồ thịMột số đồ thị hoàn toàn có thể màn 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ọcNgƣời ta thƣờng màn 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 những đỉnh u và v. Khi đó, u và v đƣợc gọi là hai đỉnh kề. – Một cạnh đƣợc màn biểu diễn bởi một đƣờng ( cong hay thẳng ) nối 2 đỉnh liên thuộcvớ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 trình 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ƣớng14Chú ý : Khi trình diễn hình học những đồ thị, giao của những cạnh chƣa chắc là đỉnhcủ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ậnNgƣời ta hoàn toàn có thể trình diễn đồ thị bằng ma trận. Có 2 kiểu ma trận thƣờng đƣợcdùng để màn biểu diễn đồ thị : – Ma trận link hay liền kề ( adjacency matrix ). – Ma trận liên thuộc ( incidence matrix ).  Ma trận liền kề so với đồ thị vô hƣớngCho 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ự những đỉ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 vjLƣ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 những số hạng trên đƣờngché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à :  0  1  1  0   01 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ắpxếp n đỉnh. Ví dụ : Hãy vẽ đồ thị có ma trận liền kề theo thứ tự của những đỉnh là a, b, c, d.  Ma trận liền kề so với đồ thị có hƣớng16Cho 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ự những đỉ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 V6V1V2V3V4V5V6  0  1  1  0  0  01 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 so với đồ thị vô hƣớngNgƣời ta còn dùng ma trận liên thuộc để màn biểu diễn đồ thị. Cho G = ( V, E ) là mộtđồ thị vô hƣớng với v1, v2, …, vn là những đỉnh và e1, e2, …, em là những 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 : 17C ó ma trận liên thuộc nhƣ sau : e1 e2 e3 e4 e5 e6 e7  1  1  0  0   01 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ạnhtƣơ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ênthuộc chỉ chứa duy nhất 1 số ít 1. Khi đó số 1 thuộc hàng tƣơng ứng với đỉnh liênthuộc với khuyên.  Ma trận liên thuộc so với đồ thị có hƣớng18Cho G   V, E  là một đồ thị có hƣớng với v1, v2, , vn là những đỉnh vàe1, e2, , em là những cạnh của G. Khi đó, ma trận liên thuộc của G theo thứ tự trên củaV 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à : e1V1  1V2   1V3  0V4  0V5  0V6  0 e2e3e4e5e6e7e80  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.3.3 Biểu diễn đồ thị bằng bảngTa hoàn toàn có thể trình diễn đồ thị không có cạnh bội bằng bảng hay còn gọi là danh sáchliền kề. Danh sách này chỉ rõ những đỉnh nối với mỗi đỉnh của đồ thị. Ví dụ : Dùng list liền kề để trình diễn đồ thị sau : 19

Source: https://bem2.vn
Category: Ứng dụng hay