Giáo trình Lý thuyết đồ thị - Trường Đại học Hàng Hải
BỘ GIAO THÔNG VẬN TẢI
TRƢỜNG ĐẠI HỌC HÀNG HẢI
BỘ MÔN: KHOA HỌC MÁY TÍNH
KHOA: CÔNG NGHỆ THÔNG TIN
BÀI GIẢNG
LÝ THUYẾT ĐỒ THỊ
TÊN HỌC PHẦN
: LÝ THUYẾT ĐỒ THỊ
MÃ HỌC PHẦN
: 17205
TRÌNH ĐỘ ĐÀO TẠO
: ĐẠI HỌC CHÍNH QUY
DÙNG CHO SV NGÀNH : CÔNG NGHỆ THÔNG TIN
HẢI PHÒNG - 2009
MỤC LỤC
1.1. Tổng quan về đồ thị..............................................................................................1
1.1.1. Định nghĩa đồ thị...........................................................................................1
1.1.2. Các thuật ngữ căn bản ...................................................................................4
1.1.3. Một số dạng đồ thị.........................................................................................6
1.2. Biểu diễn đồ thị ....................................................................................................9
1.2.2. Danh sách cạnh, cung của đồ thị .................................................................11
1.2.3. Danh sách kề................................................................................................12
Bài tập........................................................................................................................16
2.1. Tìm kiếm theo chiều sâu trên đồ thị ...................................................................17
2.2. Tìm kiếm theo chiều rộng trên đồ thị .................................................................20
2.3. Tìm đƣờng đi và kiểm tra tính liên thông...........................................................21
2.4. Tô màu đồ thị......................................................................................................28
2.4.1. Giới thiệu........................................................................................................28
2.4.2. Các khái niệm cơ bản ..................................................................................29
2.4.3. Ví dụ ............................................................................................................30
2.4.5. Thuật toán....................................................................................................33
Bài tập........................................................................................................................33
3.1. Đồ thị Euler ........................................................................................................34
3.1.1. Khái niệm về đƣờng đi và chu trình Euler ..................................................34
3.2. Đồ thị Haminton.................................................................................................37
Bài tập........................................................................................................................40
4.1. Khái niệm và các tính chất của cây khung .........................................................43
4.2. Cây khung của đồ thị..........................................................................................44
4.3. Xây dựng các tập chu trình cơ bản của đồ thị ....................................................47
4.4. Cây khung nhỏ nhất của đồ thị...........................................................................49
4.4.1. Thuật toán Kruskal ......................................................................................50
4.4.2. Thuật toán Prim ...........................................................................................56
Bài tập........................................................................................................................60
5.1. Các khái niệm mở đầu........................................................................................63
5.2. Đƣờng đi ngắn nhất xuất phát từ một đỉnh.........................................................65
5.3. Thuật toán Dijkstra.............................................................................................68
5.4. Thuật toán Floyd-Washall ..................................................................................71
5.5. Thuật toán Bellman-Ford ...................................................................................75
Bài tập........................................................................................................................80
6.4. Một số bài toán luồng tổng quát.........................................................................91
T n ọc p ần: Lý thuyết đồ thị
Bộ môn p ụ trác g ảng d y: Khoa học Máy tính
Mã ọc p ần: 17205
Lo ọc p ần:2
K oa p ụ trác : CNTT
Tổng số TC: 3
TS tiết Lý thuyết
60 45
Thực hành/Xemina
Tự học
Bài tập lớn
Đồ án môn học
15
0
0
0
Đ ều k ện t n quyết:
Sinh viên phải học xong các học phần sau mới đƣợc đăng ký học phần này:
Kỹ thuật lập trình (C), Cấu trúc dữ liệu.
Mục t u của ọc p ần:
Cung cấp các kiến thức về lý thuyết đồ thị và vận dụng các bài toán trong tin học
Nộ dung c ủ yếu
Gồm 2 phần:
- Phần các kiến thức thức về đồ thị, ứng dụng các bài toán tin học trên đồ thị: các
phƣơng pháp biểu diễn đồ thị, các thuật toán tìm kiếm cơ bản trên đồ thị, các chu trình
và thuật toán tìm cây khung nhỏ nhất, các thuật toán tìm đƣờng đi ngắn nhất, bài toán
luồng cực đại.
- Phần thực hành: Sinh viên cài đặt chƣơng trình của các bài tập liên quan đến đồ thị
Nộ dung c t ết của ọc p ần:
PHÂN PHỐI SỐ TIẾT
TÊN CHƢƠNG MỤC
C ƣơng 1. Các k á n ệm cơ bản của lý t uyết đồ t ị
1.1. Tổng quan về đồ thị
TS LT TH/Xemina
BT
0
KT
0
5
5
0
3
1.1.1. Định nghĩa đồ thị
1.1.2. Các thuật ngữ căn bản
1.1.3. Một số dạng đồ thị
1.2. Biểu diễn đồ thị
2
1.2.1. Biểu diễn bằng ma trận kề, ma trận liên thuộc
1.2.2. Danh sách cạnh, cung của đồ thị
C ƣơng 2. Các t uật toán tìm k ếm tr n đồ t ị
2.1. Tìm kiếm theo chiều sâu trên đồ thị
2.2. Tìm kiếm theo chiều rộng trên đồ thị
2.3. Tìm đƣờng đi và kiểm tra tính liên thông
2.4. Tô màu đồ thị
11
10
7
2
2
1
2
6
3
1
1
0
0
1
0
1
C ƣơng 3. Đồ t ị Euler và đồ t ị Ham nton
4
PHÂN PHỐI SỐ TIẾT
TS LT TH/Xemina BT
3 2
TÊN CHƢƠNG MỤC
3.1. Đồ thị Euler
KT
3.1.1. Khái niệm về đƣờng đi và chu trình Euler
3.1.2. Điều kiện tồn tại đƣờng đi hoặc chu trình Euler
3.1.3. Thuật toán tìm đƣờng đi và chu trình Euler
3.1.4. Một số vấn đề khác về đƣờng đi và chu trình
Euler
3.2. Đồ thị Haminton
3
2
3.2.1. Khái niệm về đƣờng đi và chu trình Haminton
3.2.2. Điều kiện tồn tại đƣờng đi hoặc chu trình
Haminton
3.2.3. Thuật toán tìm đƣờng đi và chu trình Haminton
3.2.4. Một số vấn đề khác về đƣờng đi và chu trình
Haminton
C ƣơng 4. Cây k ung của đồ t ị
4.1. Khái niệm và các tính chất của cây khung
4.2. Cây khung của đồ thị
12
8
1
1
2
3
3
0
1
4.3. Xây dựng các tập chu trình cơ bản của đồ thị
4.4. Cây khung nhỏ nhất của đồ thị
4.4.1. Thuật toán Kruskal
1
2
4.4.2. Thuật toán Prim
4.4.3. Ứng dụng của bài toán tìm cây khung nhỏ nhất
C ƣơng 5. Bà toán đƣờng đ ngắn n ất
5.1. Các khái niệm mở đầu
12
8
2
1
2
1
2
8
1
2
2
3
3
0
1
5.2. Đƣờng đi ngắn nhất xuất phát từ một đỉnh
5.3. Thuật toán Dijkstra
1
1
1
2
5.5. Thuật toán Bellman-Ford
C ƣơng 6. Bà toán luồng cực đ trong m ng
6.1. Mạng. Luồng trong mạng. Bài toán luồng cực đại
6.2. Lát cắt, luồng. Định lý Ford Fulkerson
6.3. Thuật toán tìm luồng cực đại
10
0
0
1
1
6.4. Một số bài toán luồng tổng quát
PHÂN PHỐI SỐ TIẾT
TS LT TH/Xemina BT
TÊN CHƢƠNG MỤC
6.4.1. Mạng với nhiều điểm phát và điểm thu
6.4.2. Bài toán với khả năng thông qua của các cung và
các đỉnh
KT
6.4.3. Mạng trong đó khả năng thông qua của mỗi cung
bị chặn 2 phía
6.4.4. Một số ứng dụng khác
N ệm vụ của s n v n :
Tham dự các buổi thuyết trình của giáo viên, tự học, tự làm bài tập do giáo viên giao,
tham dự các bài kiểm tra định kỳ và cuối kỳ.
Tà l ệu ọc tập :
-
-
-
học Quốc Gia TPHCM, 2007.
Doãn Châu Long. Lý thuyết quy hoạch tuyến tính và lý thuyết đồ thị. NXB Giáo dục.
1982.
Kenneth Rosen. Toán học rời rạc và ứng dụng trong tin học. NXB KHKT Hà nội.
1998.
Hìn t ức và t u c uẩn đán g á s n v n:
-
-
Hình thức thi cuối kỳ : Thi viết.
Sinh viên phải đảm bảo các điều kiện theo Quy chế của Nhà trƣờng và của Bộ
T ang đ ểm: T ang đ ểm c ữ A, B, C, D, F
Đ ểm đán g á ọc p ần: Z = 0,3X + 0,7Y.
Bài giảng này là tài liệu c ín t ức và t ống n ất của Bộ môn Khoa học Máy tính,
Khoa Công nghệ Thông tin và đƣợc dùng để giảng dạy cho sinh viên.
Ngày p duyệt:
/
/20
TRƢỞNG BỘ MÔN: THS. NGUY N H U TUÂN KÝ VÀ GHI R HỌ TÊN
CHƢƠNG 1: CÁC KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THỊ
1.1. Tổng quan về đồ thị
Lý thuyết đồ thị là một lĩnh vực đã có từ lâu và có nhiều ứng dụng hiện đại. Những tƣ tƣởng
cơ bản của lý thuyết đồ thị đƣợc đề xuất vào những năm đầu của thế kỷ 18 bởi nhà toán học
lỗi lạc ngƣời Thụy Sỹ Lenhard Eurler. Chính ông là ngƣời đã sử dụng đồ thị để giải bài toán
nổi tiếng về các cái cầu ở thành phố Konigsberg.
Đồ thị đƣợc sử dụng để giải các bài toán trong nhiều lĩnh vực khác nhau. Chẳng hạn, đồ thị có
thể sử dụng để xác định các mạch vòng trong vấn đề giải tích mạch điện. Chúng ta có thể
phân biệt các hợp chất hóa học hữu cơ khác nhau với cùng công thức phân tử nhƣng khác
nhau về cấu trúc phân tử nhờ đồ thị. Chúng ta có thể xác định hai máy tính trong mạng có thể
trao đổi thông tin đƣợc với nhau hay không nhờ mô hình đồ thị của mạng máy tính. Đồ thị có
trọng số trên các cạnh có thể sử dụng để giải các bài toán nhƣ: Tìm đƣờng đi ngắn nhất giữa
hai thành phố trong mạng giao thông. Chúng ta cũng còn sử dụng đồ thị để giải các bài toán
về lập lịch, thời khóa biểu, và phân bố tần số cho các trạm phát thanh và truyền hình…
1.1.1. Địn ng ĩa đồ thị
Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này. Chúng ta phân
biệt các loại đồ thị khác nhau bởi kiểu và số lƣợng cạnh nối hai đỉnh nào đó của đồ thị. Để có
thể hình dung đƣợc tại sao lại cần đến các loại đồ thị khác nhau, chúng ta sẽ nêu ví dụ sử dụng
chúng để mô tả một mạng máy tính. Giả sử ta có một mạng gồm các máy tính và các kênh
điện thoại (gọi tắt là kênh thoại) nối các máy tính này. Chúng ta có thể biểu diễn các vị trí đặt
náy tính bởi các điểm và các kênh thoại nối chúng bởi các đoạn nối, xem hình 1.
Hình 1. Sơ đồ mạng máy tính.
Nhận thấy rằng trong mạng ở hình 1, giữa hai máy bất kỳ chỉ có nhiều nhất là một kênh thoại
nối chúng, kênh thoại naỳ cho phép liên lạc cả hai chiều và không có máy tính nào lại đƣợc
nối với chính nó. Sơ đồ mạng máy cho trong hình 1 đƣợc gọi là đơn đồ thị vô hƣớng. Ta đi
đến định nghĩa sau
1
Định nghĩa 1: Đơn đồ thị vô hƣớng G = (V,E) bao gồm V là tập các đỉnh, và E là tập các cặp
không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh.
Trong trƣờng hợp giữa hai máy tính nào đó thƣờng xuyên phải truyền tải nhiều thông tin
ngƣời ta phải nối hai máy nàu bởi nhiều kênh thoại. Mạng với đa kênh thoại giữa các máy
đƣợc cho trong hình 2.
Trong trƣờng hợp giữa hai máy tính nào đó thƣờng xuyên phải truyền tải nhiều thông tin
ngƣời ta phải nối hai máy nàu bởi nhiều kênh thoại. Mạng với đa kênh thoại giữa các máy
đƣợc cho trong hình 2.
Hình 2. Sơ đồ mạng máy tính với đa kênh thoại.
Định nghĩa 2.
Đa đồ thị vô hƣớng G= (V, E) bao gồm V là tập các đỉnh, và E là tập các cặp không có thứ tự
gồm hai phần tử khác nhau của V gọi là các cạnh. Hai cạnh e1 và e2 đƣợc gọi là cạnh lặp nếu
chúng cùng tƣơng ứng với một cặp đỉnh.
Hình 3. Sơ đồ mạng máy tính với kênh thoại thông báo.
Rõ ràng mỗi đơn đồ thị đều là đa đồ thị, nhƣng không phải đa đồ thị nào cũng là đơn đồ thị, vì
trong đa đồ thị có thể có hai (hoặc nhiều hơn) cạnh nối một cặp đỉnh nào đó.
Trong mạng máy tính có thể có những kênh thoại nối một náy nào đó với chính nó (chẳng hạn
vời mục đính thông báo). Mạng nhƣ vậy đƣợc cho trong hình 3. Khi đó đa đồ thị không thể
mô tả đƣợc mạng nhƣ vậy, bởi vì có những khuyên (cạnh nối một đỉnh với chính nó). Trong
2
trƣờng hợp nàychúng ta cần sử dụng đến khái niệm giả đồ thị vô hƣớng, đƣợc định nghĩa nhƣ
sau:
Định nghĩa 3.
Giả đồ thị vô hƣớng G = (V, E) bao gồm V là tập các đỉnh và E là tập các cặp không có thứ tự
gồm hai phần tử (không nhất thiết phải khác nhau) của V gọi là cạnh. Cạnh e đƣợc gọi là
khuyên nếu nó có dạng e = (u, u).
Hình 4. Mạng máy tính với kênh thoại một chiều
Các kênh thoại trong mạng máy tính có thể chỉ cho phép truyền tin theo một chiều. Chẳng
hạn, trong hình 4 máy chủ ở Hà Nội chỉ có thể nhận tin từ các máy ở địa phƣơng, có một số
máy chỉ có thể gửi tin đi, còn các kênh thoại cho phép truyền tin theo cả hai chiều đƣợc thay
thế bởi hai cạnh có hƣớng ngƣợc chiều nhau.
Ta đi đến định nghĩa sau.
Định nghĩa 4.
Đơn đồ thị có hƣớng G = (V, E) bao gồm V là tập các đỉnh và E là tập các cặp có thứ tự gồm
hai phần tử khác nhau của V gọi là các cung.
Nếu trong mạng có thể có đa kênh thoại một chiều, ta sẽ phải sử dụng đến khái niệm đa đồ thị
có hƣớng:
Định nghĩa 5.
Đa đồ thị có hƣớng G = (V, E) bao gồm V là tập các đỉnh và E là tập các cặp có thứ tự gồm
hai phần tử khác nhau của V gọi là các cung. Hai cung e1, e2 tƣơng ứng với cùng một cặp đỉnh
đƣợc gọi là cung lặp.
Trong các phần tiếp theo chủ yếu chúng ta sẽ làm việc v?i đơn đồ thị vô hƣớng và đơn đồ thị
có hƣớng. Vì vậy, để cho ngắn gọn, ta sẽ bỏ qua tính từ đơn khi nhắc đến chúng.
3
1.1.2. Các thuật ngữ căn bản
Trong mục này chúng ta sẽ trình bày một số thuật ngữ cơ bản của lý thuyết đồ thị. Trƣớc tiên,
ta xét các thuật ngữ mô tả các đỉnh và cạnh của đồ thị vô hƣớng.
Định nghĩa 1.
Hai đỉnh u và v của đồ thị vô hƣớng G đƣợc gọi là kề nhau nếu (u,v) là cạnh của đồ thị G.
Nếu e = (u, v) là cạnh của đồ thị ta nói cạnh này là liên thuộc với hai đỉnh u và v, hoặc cũng
nói là nối đỉnh u và đỉnh v, đồng thời các đỉnh u và v sẽ đƣợc gọi là các đỉnh đầu của cạnh (u,
v).
Để có thể biết có bao nhiêu cạnh liên thuộc với một đỉnh, ta đƣa vào định nghĩa sau
Định nghĩa 2.
Ta gọi bậc của đỉnh v trong đồ thị vô hƣớng là số cạnh liên thuộc với nó và sẽ ký hiệu là
deg(v).
Hình 1. Đồ thị vô hƣớng
Thí dụ 1. Xét đồ thị cho trong hình 1, ta có
deg(a) = 1, deg(b) = 4, deg(c) = 4, deg(f) = 3,
deg(d) = 1, deg(e) = 3, deg(g) = 0
Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 đƣợc gọi là đỉnh treo. Trong ví dụ trên đỉnh g là
đỉnh cô lập, a và d là các đỉnh treo. Bậc của đỉnh có tính chất sau:
Định lý 1. Giả sử G = (V, E) là đồ thị vô hƣớng với m cạnh. Khi đó tông bậc của tất cả các
đỉnh bằng hai lần số cung.
Chứng minh. Rõ ràng mỗi cạnh e = (u, v) đƣợc tính một lần trong deg(u) và một lần trong
deg(v). Từ đó suy ra tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh.
Thí dụ 2. Đồ thị với n đỉnh có bậc là 6 có bao nhiêu cạnh?
Giải: Theo định lý 1 ta có 2m = 6n. Từ đó suy ra tổng các cạnh của đồ thị là 3n.
Hệ quả. Trong đồ thị vô hƣớng, số đỉnh bậc lẻ (nghĩa là có bậc là số lẻ) là một số chẵn.
Chứng minh. Thực vậy, gọi O và U tƣơng ứng là tập đỉnh bậc lẻ và tập đỉnh bậc chẵn của đồ
thị. Ta có
2m = Σ deg(v) + Σ deg(v) v U ; v O
4
Do deg(v) là chẵn với v là đỉnh trong U nên tổng thứ nhất ở trên là số chẵn. Từ đó suy ra tổng
thứ hai (chính là tổng bậc của các đỉnh bậc lẻ) cũng phải là số chẵn, do tất cả các số hạng của
nó là số lẻ, nên tổng này phải gồm một số chẵn các số hạng. Vì vậy, số đỉnh bậc lẻ phải là số
chẵn.
Ta xét các thuật ngữ tƣơng tự cho đồ thị vô hƣớng.
Định nghĩa 3.
Nếu e = (u, v) là cung của đồ thị có hƣớng G thì ta nói hai đỉnh u và v là kề nhau, và nói cung
(u, v) nối đỉnh u với đỉnh v hoặc cũng nói cung này là đi ra khỏi đỉnh u và vào đỉnh v. Đỉnh
u(v) sẽ đƣợc gị là đỉnh đầu (cuối) của cung (u,v).
Tƣơng tự nhƣ khái niệm bậc, đối với đồ thị có hƣớng ta có khái niệm bán bậc ra và bán bậc
vào của một đỉnh.
Định nghĩa 4.
Ta gọi bán bậc ra (bán bậc vào) của đỉnh v trong đồ thị có hƣớng là số cung của đồ thị đi ra
khỏi nó (đi vào nó) và ký hiệu là deg+(v) (deg-(v))
Hình 2. Đồ thị có hƣớng
Thí dụ 3. Xét đồ thị cho trong hình 2. Ta có
deg-(a)=1, deg-(b)=2, deg-(c)=2, deg-(d)=2, deg-(e) = 2.
deg+(a)=3, deg+(b)=1, deg+(c)=1, deg+(d)=2, deg+(e)=2.
Do mỗi cung (u, v) sẽ đƣợc tính một lần trong bán bậc vào của đỉnh v và một lần trong bán
bậc ra của đỉnh u nên ta có:
Định lý 2. Giả sử G = (V, E) là đồ thị có hƣớng. Khi đó
+
-(v)
Rất nhiều tính chất của đồ thị có hƣớng không phụ thuộc vào hƣớng trên các cung của nó. Vì
vậy, trong nhiều trƣờng hợp sẽ thuận tiện hơn nếu ta bỏ qua hƣớng trên các cung của đồ thị.
Đồ thị vô hƣớng thu đƣợc bằng cách bỏ qua hƣớng trên các cung đƣợc gọi là đồ thị vô hƣớng
tƣơng ứng với đồ thị có hƣớng đã cho.
5
1.1.3. Một số d ng đồ thị
Trong mục này ta xét một số đơn đồ thị vô hƣớng dạng đặc biệt xuất hiện trong nhiều vấn đề
ứng dụng thực tế.
1.1.3.1. Đồ t ị đầy đủ.
Đồ thị đầy đủ n đỉnh, ký hiệu bởi Kn, là đơn đồ thị vô hƣớng mà giữa hai đỉnh bất kỳ của nó
luôn có cạnh nối.
Các đồ thị K3, K4, K5 cho trong hình dƣới đây.
Hình 1. Đồ thị đầy đủ
Đồ thị đầy đủ Kn có tất cả n(n-1)/2 cạnh, nó là đơn đồ thị có nhiều cạnh nhất.
1.1.3.2. Đồ t ị vòng.
Đồ thị vòng Cn, n≥3. gồm n đỉnh v1, v2,. . . .vn và các cạnh (v1,v2), (v2,v3) . . . (vn-1,vn), (vn,v1).
Đồ thị vòng C3, C4, C5, C6 cho trong hình 2.
Hình 2. Đồ thị vòng C3, C4, C5, C6
1.1.3.3. Đồ t ị bán xe.
Đồ thị Wn thu đƣợc từ Cn bằng cách bổ sung vào một đỉnh mới nối với tất cả các đỉnh của Cn
(xem hình 3).
Hình 3. Đồ thị bánh xe W3, W4, W5, W6
6
1.1.3.4. Đồ t ị lập p ƣơng.
Đồ thị lập phƣơng n đỉnh Qn là đồ thị với các đỉnh biểu diễn 2n xâu nhị phân độ dài n. Hai
đỉnh của nó gọi là kề nhau nếu nhƣ hai xâu nhị phân tƣơng ứng chỉ khác nhau 1 bit. Hình 4
cho thấy Qn với n=1,2,3.
Hình 4. Đồ thị lập phƣơng Q1, Q2, Q3
1.1.3.5. Đồ t ị ai phía.
Đơn đồ thị G=(V,E) đƣợc gọi là hai phía nếu nhƣ tập đỉnh V của nó có thể phân hoạch thành
hai tập X và Y sao cho mỗi cạnh của đồ thị chỉ nối một đỉnh nào đó trong X với một đỉnh nào
đó trong Y. Khi đó ta sẽ sử dụng ký hiệu G=(X Y, E) để chỉ đồ thị hai phía với tập đỉnh X
Y.
Định lý sau đây cho phép nhận biết một đơn đồ thị có phải là hai phía hay không.
Định lý 1. Đơn đồ thị là đồ thị hai phía khi và chỉ khi nó không chứa chu trình độ dài lẻ.
Để kiểm tra xem một đồ thị liên thông có phải là hai phía hay không có thể áp dụng thủ tục
sau. Cho v là một đỉnh bất kỳ của đồ thị. Đặt X={v}, còn Y là tập các đỉnh kề của v. Khi đó
các đỉnh kề của các đỉnh trong Y phải thuộc vào X. Ký hiệu tập các đỉnh nhƣ vậy là T. Vì thế
Y # thì đồ th
Tiếp tục xét nhƣ vậy đối với T’ là tập các đỉnh kề của T,. . .
Y, E) với |X|= m, |Y| = n đƣợc gọi là đồ thị hai phía đầy đủ và ký
hiệu là K2,3, K3,3, K3,4 đƣợc cho trong hình 5. Khi E…
Hình 5. Đồ thị hai phía
1.1.3.6. Đồ t ị p ẳng.
7
Đồ thị đƣợc gọi là đồ thị phẳng nếu ta có thể vẽ nó trên mặt phẳng sao cho các cạnh của nó
không cắt nhau ngoài ở đỉnh. Cách vẽ nhƣ vậy sẽ đƣợc gọi là biểu diễn phẳng của đồ thị.
Thí dụ đồ thị K4 là phẳng, vì có thể vẽ nó trên mặt phẳng sao cho các cạnh của nó không cắt
nhau ngoài ở đỉnh (xem hình 6).
Hình 6. Đồ thị K4 là đồ thị phẳng
Một điều đáng lƣu ý nếu đồ thị là phẳng thì luôn có thể vẽ nó trên mặt phẳng với các cạnh nối
là các đoạn thẳng không cắt nhau ngoài ở đỉnh (ví dụ xem cách vẽ K4 trong hình 6).
Để nhận biết xem một đồ thị có phải là đồ thị phẳng có thể sử dụng định lý Kuratovski, mà để
phát biểu nó ta cần một số khái niệm sau: Ta gọi một phép chia cạnh (u,v) của đồ thị là việc
loại bỏ cạnh này khỏi đồ thị và thêm vào đồ thị một đỉnh mới w cùng với hai cạnh (u,w), (w,
u) . Hai đồ thị G(V,E) và H=(W,F) đƣợc gọi là đồng cấu nếu chúng có thể thu đƣợc từ cùng
một đồ thị nào đó nhờ phép chia cạnh.
Định lý 2 (Kuratovski). Đồ thị là phẳng khi và chỉ khi nó không chứa đồ thị con đồng cấu với
K3,3 hoặc K5.
Trong trƣờng hợp riêng, đồ thị K3,3 hoặc K5 không phải là đồ thị phẳng. Bài toán về tính
phẳng của đồ thị K3,3 là bài toán đố nổi tiếng về ba căn hộ và ba hệ thống cung cấp năng
lƣợng cho chúng: Cần xây dựng hệ thống đƣờng cung cấp năng lƣợng với mỗi một căn hộ nói
trên sao cho chúng không cắt nhau.
Đồ thị phẳng còn tìm đƣợc những ứng dụng quan trọng trong công nghệ chế tạo mạch in.
Biểu diễn phẳng của đồ thị sẽ chia mặt phẳng ra thành các miền, trong đó có thể có cả miền
không bị chặng. Thí dụ, biểu diễn phẳng của đồ thị cho trong hình 7 chia mặt phẳng ra thành
6 miền R1, R2,. . . .R6.
Hình 7. Các miền tƣơng ứng với biểu diễn phẳng của đồ thị
8
Euler đã chứng minh đƣợc rằng các cách biểu diễn phẳng khác nhau của một đồ thị đều chia
mặt phẳng ra thành cùng một số miền. Để chứng minh điều đó, Euler đã tìm đƣợc mối liên hệ
giữa số miền, số đỉnh của đồ thị và số cạnh của đồ thị phẳng sau đây.
Định lý 3 (Công thức Euler). Giả sử G là đồ thị phẳng liên thông với n đỉnh, m cạnh. Gọi r là
số miền của mặt phẳng bị chia bởi biểu diễn phẳng của G. Khi đó
r = m-n + 2
Có thể chứng minh định lý bằng qui nạp. Xét thí dụ minh hoạ cho áp dụng công thức Euler.
Thí dụ. Cho G là đồ thị phẳng liên thông với 20 đỉnh, mỗi đỉnh đều có bậc là 3. Hỏi mặt
phẳng bị chia làm bao nhiêu phần bởi biểu diễn phẳng của đồ thị G?
Giải. Do mỗi đỉnh của đồ thị đều có bậc là 3, nên tổng bậc của các đỉnh là 3x20=60. Từ đó
suy ra số cạnh của đồ thị m=60/20=30. Vì vậy, theo công thức Euler, số miền cần tìm là
r=30-20+2=12.
1.2. Biểu diễn đồ thị
Để lƣu trữ đồ thị và thực hiện các thuật toán khác nhau với đồ thị trên máy tính cần phải tìm
những cấu trúc dữ liệu thích hợp để mô tả đồ thị. Việc chọn cấu trúc dữ liệu nào để biểu diễn
đồ thị có tác động rất lớn đến hiệu quả của thuật toán. Vì vậy, việc chọn lựa cấu trúc dữ liệu
để biểu diễn đồ thị phụ thuộc vào từng tình huống cụ thể (bài toán và thuật toán cụ thể). Trong
mục này chúng ta sẽ xét một số phƣơng pháp cơ bản đƣợc sử dụng để biểu diễn đồ thị trên
máy tính, đồng thời cũng phân tích một cách ngắn gọn những ƣu điểm cũng nhƣ những nhƣợc
điểm của chúng.
1.2.1. Biểu diễn bằng ma trận kề, ma trận liên thuộc
Xét đơn đồ thị vô hƣớng G=(V,E), với tập đỉnh V={1, 2,. . .,n}, tập cạnh E={e1, e2,. . .,em }.
Ta gọi ma trận kề của đồ thị G là ma trận.
A={ ai,j : i,j=1, 2,. . .,n}
Với các phần tử đƣợc xác định theo qui tắc sau đây:
ai, j = 0, nếu (i,j) E và
ai,j = 1, nếu (i,j) E, i, j=1, 2,. . .,n.
Thí dụ 1. Ma trận trận kề của đồ thị vô hƣớng cho trong hình 1 là:
1
0
1
1
2
1
0
1
3
1
1
0
4
0
0
1
5
1
1
0
6
0
0
0
1
2
3
9
4
5
6
0
1
0
0
1
0
1
0
0
0
1
1
1
0
1
1
1
0
Hình 1. Đồ thị vô hƣớng G và Đồ thị có hƣớng G1
Các tính chất của ma trận kề:
1) Rõ ràng ma trận kề của đồ thị vô hƣớng là ma trận đối xứng, tức là
a[i,j]=a[j,i], i,j=1,2,. . .,n.
ngƣợc lại, mỗi (0,1)-ma trận đối xứng cấp n sẽ tƣơng ứng, chính
xác đến cách đánh số đỉnh (còn nói là: chính xác đến đẳng cấu), với một đơn đồ thị vô hƣớng
n đỉnh.
2) Tổng các phần từ trên dòng i (cột j) của ma trận kề chính bằng bậc của đỉnh i (đỉnh j).
p
3) nếu ký hiệu aịj , i,j=1, 2,. . .,n
là phần tử của ma trận Ap =A.A. . .A p thừa số
p
Khi đó
aịj , i,j=1, 2,. . .,n
cho ta số đƣờng đi khác nhau từ đỉnh i đến đỉnh j qua p-
1 đỉnh trung gian.
Ma trận kề của đồ thị có hƣớng đƣợc định nghĩa một cách hoàn toàn tƣơng tự.
Thí dụ 2. Đồ thị có hƣớng G1 cho trong hình 1 có ma trận kề là ma trận sau:
1 2
0 1
0 0
0 1
0 0
0 0
0 0
3
1
0
0
0
0
0
4 5
0 0
0 0
1 0
0 0
1 0
0 1
6
0
0
0
0
1
0
1
2
3
4
5
6
Lƣu ý rằng ma trận kề của đồ thị có hƣớng không phải là ma trận đối xứng.
10
Chú ý: Trên đây chúng ta chỉ xét đơn đồ thị. Ma trận kề của đa đồ thị có thể xây dựng hoàn
toàn tƣơng tự, chỉ khác là thay vì ghi 1 vào vị trí a[i,j] nếu (i,j) là cạnh của đồ thị, chúng ta sẽ
ghi k là số cạnh nối hai đỉnh i, j.
Trong rất nhiều vấn đề ứng dụng của lý thuyết đồ thị, mỗi cạnh e=(u,v) của đồ thị đƣợc gán
với một con số c(e) (còn viết là c(u,v) gọi là trọng số của cạnh e. Đồ thị trong trƣờng hợp nhƣ
vậy đƣợc gọi là đồ thị có trọng số. Trong trƣờng hợp đồ thị có trọng số, thay vì mà trận kề, để
biểu diễn đồ thị ta sử dụng ma trận trọng số.
C= {c[i,j], i,j=1, 2,..., n}
với
c[i,j]=c(i,j) nếu (i,j) E
và c[i,j]= 0 nếu (i,j) E
đƣợc đặt bằng một trong các giá trị sau: 0,
-
Ƣu điểm lớn nhất của phƣơng pháp biểu diễn đồ thị bằng ma trận kề (hoặc ma trận trọng số)
là để trả lời câu hỏi: Hai đỉnh u,v có kề nhau trên đồ thị hay không, chúng ta chỉ phải thực
hiện một phép so sánh. nhƣợc điểm lớn nhất của phƣơng pháp này là: không phụ thuộc vào số
cạnh của đồ thị, ta luôn phải sử dụng n2 đơn vị bộ nhớ để lƣu trữ ma trận kề của nó.
1.2.2. Danh sách c nh, cung của đồ thị
Trong trƣờng hợp đồ thị thƣa (đồ thị có số cạnh m thoả mãn bất dẳng thức: m < 6n) ngƣời ta
thƣờng dùng cách biểu diễn đồ thị dƣới dạng danh sách cạnh.
Trong cách biểu diễn đồ thị bởi danh sách cạnh (cung) chúng ta sẽ lƣu trữ danh sách tất cả các
cạnh (cung) của đồ thị vô hƣớng (có hƣớng). Một cạnh (cung) e=(x,y) của đồ thị sẽ tƣơng ứng
với hai biến Dau[e], Cuoi[e]. nhƣ vậy, để lƣu trữ đồ thị ta cần sử dụng 2m đơn vị bộ nhớù.
Nhƣợc điểm của cách biểu diễn này là để xác định những đỉnh nào của đồ thị là kề với một
đỉnh cho trƣớc chúng ta phải làm cỡ m phép so sánh (khi duyệt qua danh sách tất cả các cạnh
của đồ thị).
Chú ý: Trong trƣờng hợp đồ thị có trọng số ta cần thêm m đơn vị bộ nhớ để lƣu trữ trọng số
của các cạnh.
Thí dụ 3. Danh sách cạnh (cung) của đồ thị G (G1) cho trong hình 1 là:
Dau Cuoi
Dau
1
Cuoi
2
1
2
11
1
1
2
2
3
4
4
3
5
3
5
4
5
6
6
1
3
3
5
5
6
3
2
4
4
6
5
5
Danh sách cạnh của G
Danh sánh cung của G1
1.2.3. Danh sách kề
Trong rất nhiều vấn đề ứng dụng của lý thuyết đồ thị, cách biểu diễn đồ thị dƣới dạng
danh sách kề là cách biểu diễn thích hợp nhất đƣợc sử dụng.
Trong cách biểu diễn này, với mỗi đỉnh v của đồ thị chúng ta lƣu trữ danh sách các
đỉnh kề với nó, mà ta sẽ ký hiệu là
Ke(v)= { uÎ V: (v,u)Î E}
Khi đó vòng lặp thực hiện với mỗi một phần tử trong danh sách này theo thứ tự các
phần tử đƣợc sắp xếp trong nó sẽ đƣợc viết nhƣ sau:
for uÎ Ke(v) do. . .
Chẳng hạn, trên PASCAL có thể mô tả danh sách này nhƣ sau (Gọi là cấu trúc
Forward Star):
Const
m=1000; { m-so canh}
n= 100; { n-so dinh}
var
Ke:array[1..m] of integer;
Tro:array[1..n+1] of integer;
12
Trong đó Tro[i] ghi nhận vị trí bắt đầu của danh sách kề của đỉnh i, i=1, 2,. . .,n,
Tro[n+1]=2m+1.
Khi đó dòng lệnh qui ƣớc
for uÎ Ke(v) do
begin
. . . .
end.
Có thể thay thế bởi cấu trúc lệnh cụ thể trên PASCAL nhƣ sau
For i:=Tro[v] to Tro[v+1]-1 do
Begin
U:=Ke[i];
. . . .
End;
Trong rất nhiều thuật toán làm việc với đồ thị chúng ta thƣờng xuyên phải thực hiện
các thao tác: Thêm hoặc bớt một số cạnh. Trong trƣờng hợp này cấu trúc dữ liệu dùng
ở trên là không thuận tiện. Khi đó nên chuyển sang sử dụng danh sách kề liên kết
(Linked Adjancency List) nhƣ mô tả trong chƣơng trình nhập danh sách kề của đồ thị
từ bàn phím và đƣa danh sách đó ra màn hình sau đây:
Program AdjList;
Const
maxV=100;
Type
link=^node;
node=record
v:integer;
next:link;
End;
13
Tải về để xem bản đầy đủ
111 trang
04/05/2022
4100
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Lý thuyết đồ thị - Trường Đại học Hàng Hải", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_ly_thuyet_do_thi_truong_dai_hoc_hang_hai.pdf
