Giáo trình Lý thuyết đồ thị | Đại học Công nghệ Sài Gòn
Giáo trình Lý thuyết đồ thị | Đại học Công nghệ Sài Gòn. Tài liệu được sưu tầm giúp bạn tham khảo, ôn tập và đạt kết quả cao. Mời bạn đọc đón xem.
Môn: Toán tin học 3 tài liệu
Trường: Đại học Công nghệ Sài Gòn 154 tài liệu
Tác giả:
Preview text:
ỦY BAN NHÂN DÂN THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC SÀI GÒN GIÁO TRÌNH
LÝ THUYẾT ĐỒ THỊ Mã số: GT2020-7
Chủ biên: PGS.TS. Nguyễn Hòa
Thành viên tham gia biên soạn: TS. Huỳnh Minh Trí
ThS. Nguyễn Nhựt Đông
Thành phố Hồ Chí Minh, tháng 7 năm 2022 ỦY BAN NHÂN DÂN THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC SÀI GÒN GIÁO TRÌNH
LÝ THUYẾT ĐỒ THỊ Mã số: GT2020-7
Xác nhận của chủ tịch Chủ biên
hội đồng thẩm định (ký, họ tên) (ký, họ tên)
PGS.TS. Nguyễn Tuấn Đăng PGS.TS. Nguyễn Hòa
Thành phố Hồ Chí Minh, tháng 7 năm 2022
GIỚI THIỆU MỞ ĐẦU
Lý thuyết đồ thị là cơ sở toán học để mô hình hóa, biểu diễn thông tin, phát triển
các thuật toán ứng dụng giải quyết nhiều bài toán thực tế, đặc biệt là các bài toán tối
ưu như bài toán tìm các đường đi ngắn nhất, tìm luồng cực đại trong mạng, tô màu
bản đồ với ít màu nhất v.v. Khái niệm đồ thị, lý thuyết đồ thị như là một bộ phận của
lĩnh vực Toán rời rạc xuất hiện từ khá sớm, khoảng cuối thế kỳ 17 đầu thế kỳ 18, do
các nhà toán học Euler và Hamilton khởi xướng khi giải quyết một số bài toán trong
cuộc sống hàng ngày. Tuy nhiên, lý thuyết đồ thị chỉ phát triển mạnh mẽ và tách khỏi
lĩnh vực Toán rời rạc như một lý thuyết toán học riêng, có tính đặc thù với khả năng
mô hình hóa, biểu diễn và xử thông tin hiệu quả, kể từ khi Khoa học máy tính và Công
nghệ thông tin xuất hiện vào khoảng 1950. Có thể nói, lý thuyết đồ thị là một trong
những cơ sở toán học cho sự phát triển Công nghệ thông tin và Khoa học máy tính
nhưng chính sự phát triển nhanh chóng vượt bậc của Công nghệ thông tin và Khoa
học máy tính cũng thúc đẩy mạnh mẽ việc nghiên cứu, khám phá các kết quả mới
trong Lý thuyết đồ thị và làm lý thuyết này phát triển nhanh hơn nhằm đáp ứng ngày
càng cao các công cụ biểu diễn, tính toán và xử lý mới của Công nghệ thông tin và Khoa học máy tính.
Với đặc thù như một hệ thống toán học có tính công cụ thiết yếu cho Công nghệ
thông tin và Khoa học máy tính, Lý thuyết đồ thị được giảng dạy, và được xem như
một môn học cơ sở ngành bắt buộc của các sinh viên, trong các khoa công nghệ
thông tin, khoa học máy tính của hầu hết các trường đại học trên thế giới.
Giáo trình Lý thuyết đồ thị này được biên soạn cho sinh viên chuyên ngành Công
nghệ thông tin, Khoa học máy tính, kỹ thuật máy tính, công nghệ phần mềm và có thể
được học tập và giảng dạy vào kỳ cuối của năm học thứ hai của bậc đại học. Sinh
viên các ngành điện tử viễn thông, toán tin học, toán ứng dụng cũng có thể xem giáo
trình này như một tài liệu tham khảo bổ ích. Giáo trình tập trung trình bày các vấn đề
cốt lõi có phạm vi ứng dụng chung, rộng rãi nhất vào Khoa học máy tính và Công
nghệ thông tin của Lý thuyết đồ thị như hệ thống khái niệm, thuật ngữ, các kiểu đồ
thị, các hình thức biểu diễn đồ thị, các thuật toán tìm kiếm trên đồ thị, đồ thị Euler,
Hamilton, cây và cây bao trùm nhỏ nhất của đồ thị, các thuật toán tìm đường đi ngắn i
nhất và tìm luồng cực đại trên mạng. Các nội dung kiến thức này cũng chính là các
nội dung được yêu cầu giảng dạy trong đề cương chi tiết của môn Lý thuyết đồ thị
trong chương trình đào tạo kỹ sư của Khoa công nghệ thông tin Đại học Sài gòn.
Để trình bày các nội dung Lý thuyết đồ thị, bao gồm cả những khái niệm trừu
tượng cũng như các tính chất phức tạp của các đối tượng toán học một cách khoa
học, có hệ thống sao cho dễ đọc và dễ hiểu, các tác giả đã kết hợp các dẫn nhập, diễn
giải trực giác, không hình thức với các định nghĩa hình thức, chính xác, các chứng
minh chặt chẽ và các ví dụ minh họa có tính điển hình từ đơn giản đến phức tạp. Các
thuật toán trên đồ thị được trình bày một cách ngắn gọn, rõ ràng được chứng minh
tính đúng đắn dựa trên các cơ sở toán học và được tính toán độ phức tạp về thời gian
đầy đủ để đảm bảo có thể ứng dụng trong thực tế.
Một hệ thống các bài tập phong phú có chọn lọc được giới thiệu sau mỗi chương
giúp sinh viên củng cố kiến thức cơ bản, rèn luyện và nâng cao khả năng giải quyết
vấn đề cũng như mở rộng hơn nữa các vấn đề chưa được đề cập trong lý thuyết.
Mặc dù đã có nhiều cố gắng nhưng chắc chắn giáo trình Lý thuyết đồ thị này
không thể tránh khỏi những thiếu sót. Các tác giả mong nhận được những nhận xét,
đóng góp quí giá của các sinh viên, giảng viên nói riêng và các độc giả nói chung.
Thành phố Hồ Chí Minh, tháng 7 năm 2022 Nguyễn Hòa Huỳnh Minh Trí Nguyễn Nhựt Đông ii MỤC LỤC
Chương 1 Các khái niệm cơ bản của lý thuyết đồ thị ....................................... …1 1.1
Định nghĩa đồ thị ........................................................................................ 1
1.2 Các thuật ngữ .............................................................................................. 5 1.3
Đường đi, chu trình, đồ thị liên thông .......................................................... 8 1.4
Một số dạng đồ thị đặc biệt ....................................................................... 14
1.5 Đồ thị phẳng ……..……………………………………...............................19
Bài tập..………………………………………...…………..……….............25
Chương 2 Biểu diễn đồ thị và sự đẳng cấu đồ thị ................................................ 31 2.1
Ma trận kề................................................................................................. 31 2.2
Ma trận trọng số ........................................................................................ 33 2.3
Ma trận liên thuộc. .................................................................................... 34 2.4
Danh sách kề............................................................................................. 36 2.5
Danh sách cạnh ......................................................................................... 38 2.6
Hiệu quả các phương pháp biểu diễn đồ thị……………………………......40 2.7
Đẳng cấu đồ thị ......................................................................................... 43
Bài tập. ..................................................................................................... 47
Chương 3 Các thuật toán tìm kiếm trên đồ thị và ứng dụng .………..................54 3.1
Tìm kiếm theo chiều rộng …………………………………………………54 3.2
Tìm kiếm theo chiều sâu ………………………………………………......62 3.3
Tìm đường đi giữa hai đỉnh ……………………………………………….71 3.4
Tìm các thành phần liên thông của đồ thị………………………………….72
Bài tập……………………………………………………………………...78
Chương 4 Đồ thị Euler và đồ thị Hamilton ……………........................................82 4.1
Đồ thị Euler ………………………………………………………………..82 4.2
Đồ thị Hamilton ........................................................................................ 90
Bài tập ...................................................................................................... 99
Chương 5 Cây và cây bao trùm của đồ thị ........................................................ 103 5.1
Cây và các tính chất cơ bản của cây ........................................................ 103 iii 5.2
Cây bao trùm của đồ thị .......................................................................... 106 5.3
Cây bao trùm bé nhất của đồ thị .............................................................. 108
Bài tập .................................................................................................... 117
Chương 6 Đường đi ngắn nhất .......................................................................... 120 6.1
Các khái niệm mở đầu............................................................................. 120 6.2
Đường đi ngắn nhất xuất phát từ một đỉnh .............................................. 123 6.3
Thuật toán Bellman-Ford ........................................................................ 131 6.4
Thuật toán Dijkstra ................................................................................. 135 6.5
Đường đi ngắn nhất giữa các cặp đỉnh ..................................................... 139
Bài tập .................................................................................................... 146
Chương 7 Luồng cực đại trong mạng ............................................................... 150 6.1
Mạng, luồng mạng và bài toán tìm luồng cực đại .................................... 150 6.2
Lát cắt, đường tăng luồng, định lý Ford-Fulkerson .................................. 152 6.3
Thuật toán tìm luồng cực đại trong mạng ................................................ 161
Bài tập .................................................................................................... 164
TÀI LIỆU THAM KHẢO ................................................................................... 168 iv Chương 1
CÁC KHÁI NIỆM CƠ BẢN
CỦA LÝ THUYẾT ĐỒ THỊ
ác khái niệm cơ bản của lý thuyết đồ thị là những khái niệm có tính nền tảng làm
C cơ sở để xây dựng, phát triển lý thuyết đồ thị. Phần 1.1, 1.2 và 1.3 của chương
này lần lượt trình bày các khái niệm và thuật ngữ về đồ thị, cạnh bội, cạnh khuyên, đỉnh
kề, bậc, bán bậc của đỉnh, đường đi, chu trình, đồ thị con và tính liên thông của đồ thị.
Phần 1.4 trình bày một số đồ thị đặc biệt có nhiều ứng dụng trong thiết kế các hệ thống
mạng trong lĩnh vực Công nghệ Thông tin và Khoa học Máy tính. Phần 1.5 trình bày
về đồ thị phẳng, một lớp đồ thị đặc biệt, có thể biểu diễn hình học trên mặt phẳng mà
không có sự giao cắt của các cạnh, là cơ sở cho nhiều ứng dụng trong thiết kế mạch
điện tử và mô hình hóa các hệ thống kết nối các đối tượng có tính đặc thù trong thực tế.
1.1 Định nghĩa đồ thị
Đồ thị là một mô hình toán học biểu diễn các cấu trúc rời rạc bao gồm một tập các
phần tử kết hợp với một tập các quan hệ giữa các cặp phần tử của chúng. Khi tính thứ
tự trong mối quan hệ giữa các phần tử không được xem xét chúng ta có một đồ thị vô
hướng, ngược lại chúng ta có đồ thị có hướng. Đồ thị vô hướng được định nghĩa một cách hình thức như sau.
Đinh nghĩa 1.1.1 Một đồ thị vô hướng (undirected graph) là một bộ đôi G = (V, E), trong đó
1. V là một tập hợp hữu hạn khác rỗng các phần tử được gọi là các đỉnh (vertex) của G. 1
2. E là một tập hợp hữu hạn các phần tử được gọi là các cạnh (edge) của G sao cho
mỗi cạnh trong E ứng với một cặp không có thứ tự của các đỉnh trong V.
Chúng ta có thể ký hiệu G(V, E) để biểu diễn đồ thị G = (V, E). Các đỉnh của G cũng
còn được gọi là các nút (node) của G. Nếu cạnh e trong E ứng với cặp đỉnh u và v trong
V ta viết e = (u, v) hay e = (v, u) và nói cạnh e nối các đỉnh u và v, các đỉnh u và v là hai
đầu mút của cạnh e. Đồ thị G được định nghĩa như trên gọi là đồ thị hữu hạn (finite
graph). Trong trường hợp V và E là các tập hợp vô hạn (infinite set) thì đồ thị G = (V,
E) được gọi là đồ thị vô hạn (infinite graph).
Ví dụ 1.1.1 Một đồ thị vô hướng G = (V, E) với tập đỉnh và tập cạnh như sau:
1. V = {v1, v2, v3, v4, v5}.
2. E = {e1 = (v2, v2), e2 = (v2, v4), e3 = (v1, v2), e4= (v1, v3), e5 = (v1, v3), e6 = (v3, v4),
e7 = (v4, v5)}.
Một đồ thị vô hướng G = (V, E) có thể được biểu diễn hình học trong một mặt phẳng
bởi một tập các điểm tương ứng với các đỉnh trong V và một tập các đoạn (thẳng hoặc
cong) nối các điểm đó tương ứng với các cạnh trong E.
Ví dụ 1.1.2 Biểu diễn hình học của đồ thị trong Ví dụ 1.1.1 như Hình 1.1.1.
Hình 1.1.1. Biểu diễn hình học của đồ thị
Một cạnh e = (u, u) của đồ thị vô hướng G nối một đỉnh u với chính nó được gọi là
một cạnh khuyên (loop edge) của G, chẳng hạn cạnh e1 = (v2, v2) của đồ thị G trong Ví
dụ 1.1.1 là một cạnh khuyên. Hai cạnh ei và ej cùng ứng với một cặp đỉnh trong G được
gọi là những cạnh song song hay cạnh bội (multiple edge) của G, chẳng hạn hai cạnh
e4 = (v1, v3), e5 = (v1, v3) của đồ thị G trong Ví dụ 1.1.1 là hai cạnh song song. 2
Đinh nghĩa 1.1.2 Một đồ thị G không có cạnh khuyên hoặc cạnh bội được gọi là một
đơn đồ thị (simple graph).
Ví dụ 1.1.3 Các đồ thị được cho như trong Hình 1.1.2 là các đơn đồ thị.
Hình 1.1.2. Đơn đồ thị vô hướng
Lưu ý rằng, nếu chúng ta không quan tâm đến các đỉnh và các cạnh cụ thể của các
đồ thị, chúng ta có thể bỏ qua ký hiệu các tên đỉnh và cạnh như biểu diễn phẳng của đồ
thị thứ ba trong Hình 1.1.2.
Khi tính thứ tự của các cặp đỉnh ứng với một cạnh trong đồ thị được xem xét, đồ thị
được gọi là có hướng. Đồ thị có hướng được định nghĩa một cách hình thức như sau.
Đinh nghĩa 1.1.3 Một đồ thị có hướng (directed graph) là một bộ đôi G = (V, E), trong đó
1. V là một tập hợp hữu hạn khác rỗng các phần tử được gọi là các đỉnh của G.
2. E là một tập hợp hữu hạn các phần tử được gọi là các cạnh có hướng hay cung
(arc) của G sao cho mỗi cung trong E ứng với một cặp có thứ tự của các đỉnh trong V.
Như đối với đồ thị vô hướng, chúng ta có thể ký hiệu G(V, E) để biểu diễn đồ thị
có hướng G = (V, E). Các đỉnh của G cũng còn được gọi là các nút của G. Nếu cung e
trong E ứng với cặp đỉnh có thứ tự (u, v) trong V ta viết e = (u, v) và nói cung e là một
cung (cạnh) có hướng từ u đến v trong G nối đỉnh u với đỉnh v (hay e bắt đầu tại đỉnh
u, kết thúc tại đỉnh v), đỉnh u được gọi là đỉnh đầu và đỉnh v được gọi là đỉnh cuối của
cung e (u và v cũng được gọi là gốc và ngọn của cung e). Đồ thị có hướng G được định
nghĩa như trên gọi là đồ thị có hướng hữu hạn (finite directed graph). Trong trường hợp 3
V và E là các tập hợp vô hạn thì đồ thị G = (V, E) được gọi là đồ thị có hướng vô hạn (infinite directed graph).
Ví dụ 1.1.4 Một đồ thị có hướng G = (V, E) với tập đỉnh và tập cung như sau:
1. V = {v1, v2, v3, v4, v5}.
2. E = {e1 = (v1, v3), e2 = (v1, v4), e3 = (v4, v1), e4= (v1, v2), e5 = (v2, v2), e6 = (v3, v4),
e7 = (v5, v4), e8= (v5, v3), e9 = (v5, v3), e7 = (v5, v3)}.
Một đồ thị có hướng G = (V, E) có thể được biểu diễn hình học trong một mặt phẳng
bởi một tập các điểm tương ứng với các đỉnh trong V và một tập các đoạn (thẳng hoặc
cong) có hướng nối các điểm đó tương ứng với các cung trong E.
Ví dụ 1.1.5 Biểu diễn hình học của đồ thị có hướng trong Ví dụ 1.1.4 như Hình 1.1.3.
Hình 1.1.3. Biểu diễn hình học của đồ thị có hướng
Một cung e = (u, u) của đồ thị có hướng G nối một đỉnh u với chính nó được gọi là
một cung khuyên (loop arc) của G, chẳng hạn cạnh e5 = (v2, v2) của đồ thị G trong Ví
dụ 1.1.4 là một cung khuyên. Hai cung ei và ej cùng nối một cặp đỉnh trong G được gọi
là những cung song song hay cung bội (multiple arc) của G, chẳng hạn ba cung e8 = (v5,
v3), e9 = (v5, v3), e10 = (v5, v3) của đồ thị G trong Ví dụ 1.1.4 là ba cung song song.
Đinh nghĩa 1.1.4 Một đồ thị có hướng G không có cung khuyên hoặc cung bội được
gọi là một đơn đồ thị có hướng (simple directed graph).
Ví dụ 1.1.6 Đồ thị được cho như trong Hình 1.1.4 là một đơn đồ thị có hướng. 4
Hình 1.1.4. Một đơn đồ thị có hướng 1.2 Các thuật ngữ
Phần này giới thiệu một số thuật ngữ cơ bản, thông dụng mô tả mối quan hệ của các
đỉnh, các cạnh của một đồ thị như các định nghĩa dưới đây.
Đinh nghĩa 1.2.1 Hai đỉnh u và v trong một đồ thị vô hướng G được gọi là liền kề hay
kề nhau (adjacent) nếu (u, v) là một cạnh của G và nếu cạnh e = (u, v) thì e được gọi là
cạnh liên thuộc (incident) với các đỉnh u và v.
Số cạnh liên thuộc với một đỉnh trong một đồ thị vô hướng được gọi là bậc của đỉnh
đó. Bậc của một đỉnh trong đồ thị vô hướng được định nghĩa như sau.
Đinh nghĩa 1.2.2 Bậc của một đỉnh v trong đồ thị vô hướng G, ký hiệu degG(v) hoặc
deg(v), là số cạnh liên thuộc với đỉnh v trong G.
Chúng ta lưu ý rằng, trong định nghĩa trên, một cạnh khuyên (v, v) được xem như
hai cạnh liên thuộc với đỉnh v nên được tính hai lần cho bậc của v. Đỉnh bậc 0 được gọi
là đỉnh cô lập đỉnh bậc 1 được gọi là đỉnh treo.
Ví dụ 1.2.1 Xem đồ thị vô hướng như hình 1.2.1 dưới đây. Ta dễ dàng thấy deg(v1) =
3, deg(v2) = 4, deg(v3) = 3, deg(v4) = 3, deg(v5) = 1. 5
Hình 1.2.1. Bậc các đỉnh của đồ thị vô hướng
Từ định nghĩa 1.2.2 chúng ta thấy rằng mỗi cạnh e = (u, v) trong đồ thị vô hướng
G được tính hai lần trong tổng bậc của đỉnh u và đỉnh v (một lần cho bậc của u và một
lần cho bậc của v vì cạnh e kề cả u và v). Từ đó, ta có kết quả về mối quan hệ giữa số
cạnh và tổng các bậc của các đỉnh trong một đồ thị vô hướng như sau.
Định lý 1.2.1 Với mỗi đồ thị vô hướng G = (V, E), thì
2|E| = vV deg(v).
Chứng minh: Theo định nghĩa bậc của một đỉnh của đồ thị vô hướng, deg(x) là số đỉnh
kề với x và deg(y) là số đỉnh kề với y. Từ đó, mỗi cạnh e = (x, y) E tương ứng với
một cặp đỉnh x và y kề nhau và được tính hai lần trong vV deg(v), một lần trong deg(x)
và một lần trong deg(y). Vì vậy 2|E| = vV deg(v).
Ví dụ 1.2.3 Cho đồ thị vô hướng G có 10 đỉnh, trong đó có 4 đỉnh bậc 3, các đỉnh còn
lại đều có bậc 2. Đồ thị G có bao nhiêu cạnh ?
Giải: Đồ thị có 10 đỉnh, trong đó có 4 đỉnh bậc 3 nên còn lại 6 đỉnh bậc 2. Gọi m là số
cạnh của G thì 2m = 4.3+6.2 =2m, suy ra m = 12.
Từ định lý trên chúng ta có hệ quả dưới đây.
Hệ quả 1.2.1 Số đỉnh bậc lẻ trong một đồ thị vô hướng G = (V, E) là một số chẵn.
Chứng minh: Gọi m là số cạnh, O và U là tập các đỉnh bậc lẻ và bậc chẵn của G, thì theo định lý 1.2.1 ta có
2m = vVdeg(v) = vO deg(v) + vU deg(v).
Do deg(v) chẵn với mọi vU nên vU deg(v) = 2k với k là một số nguyên không âm, nên 6
2m = vO deg(v) + 2k. Từ đó
vO deg(v) = 2m - 2k.
Vì tổng vO deg(v) = 2m - 2k là một số chẵn và mỗi số hạng deg(v) trong tổng này
là một số lẻ nên số các số hạng trong vO deg(v) là một số chẵn. Nghĩa là |O| là một số
chẵn. Nói cách khác số đỉnh bậc lẻ của G là một số chẵn.
Đinh nghĩa 1.2.3 Đỉnh v được gọi là liền kề với đỉnh u trong một đồ thị có hướng G
nếu (u, v) là một cạnh của G. Cạnh e = (u, v) được gọi là cạnh liên thuộc với các đỉnh u
và v, đi ra từ đỉnh u và đi vào đỉnh v.
Trong một đồ thị có hướng, mỗi đỉnh có một số cạnh (cung) liên thuộc đi ra và vào
đỉnh này, số cạnh đi ra và vào của một đỉnh được gọi là bán bậc ra và vào của đỉnh và
được định nghĩa như sau.
Đinh nghĩa 1.2.4 Gọi v là một đỉnh trong đồ thị có hướng G, bán bậc ra của v, ký hiệu
deg+(v), là số cạnh đi ra khỏi nó, bán bậc vào của v, ký hiệu deg(v), là số cạnh đi vào
nó, bậc của v, ký hiệu deg(v), là tổng bán bậc ra và bán bậc vào của nó.
Lưu ý rằng, một cạnh khuyên (v, v) trong đồ thị có hướng được xem như hai cạnh
liên thuộc với đỉnh v, một cạnh đi vào v và một cạnh đi ra khỏi v nên bán bậc ra và bán
bậc vào của v bằng 1. Đỉnh có bán bậc ra và bán bậc vào bằng 0 được gọi là đỉnh cô
lập. Đỉnh có tổng bán bậc ra và bán bậc vào bằng 1 được gọi là đỉnh treo.
Ví dụ 1.2.4 Cho đồ thị có hướng như hình dưới đây.
Hình 1.2.2. Bậc của các đỉnh trong đồ thị có hướng 7
Ta dễ dàng thấy deg(v1) = 3, deg(v1) = 1, deg(v1) = 4, deg(v2) = 1, deg (v2) = 2,
deg(v2) = 3, deg(v3) = 1, deg(v3) = 4, deg(v3) = 5, deg(v4) = 1, deg(v4) = 3, deg(v4) =
4, deg(v5) = 4, deg(v5) = 0, deg(v5) = 4.
Định lý 1.2.2 Giả sử G = (V, E) là một đồ thị có hướng. Khi đó ta có
|E| = vV deg(v) = vV deg(v).
Chứng minh: Theo định nghĩa bán bậc ra và bán bậc vào của một đỉnh, mỗi cạnh (u,
v) được tính một lần trong bán bậc ra của u và một lần trong bán bậc vào của v. Từ đó
suy ra hệ thức cần chứng minh.
1.3 Đường đi, chu trình, đồ thị liên thông
Đường đi, chu trình và tính liên thông là các khái niệm cơ bản của đồ thị. Các khái
niệm này là cơ sơ để xem xét các tính chất, loại đồ thị cũng như khả năng áp dụng của
chúng trong khoa học, kỹ thuật và thực tế.
Định nghĩa 1.3.1 Đường đi độ dài n từ đỉnh u đến đỉnh v, với n là số nguyên dương,
trên đồ thị vô hướng G = (V, E) là một dãy các đỉnh x0, x1,…xn-1, xn sao cho u = x0, v =
xn và (xi, xi+1) E, i = 0, 1,…, n-1. Đỉnh u và đỉnh v tương ứng gọi là đỉnh đầu và đỉnh
cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối được gọi là chu trình.
Đường đi hay chu trình được gọi là đơn (simple) nếu không có cạnh nào lặp lại.
Ví dụ 1.3.1 Cho đồ thị vô hướng G như hình 1.3.1.
Hình 1.3.1. Đường đi và chu trình của đồ thị vô hướng
Thì dãy các đỉnh v1, v3, v4, v5 là một đường đi và cũng là đường đi đơn trên G, trong
khi dãy v1, v3, v4, v5, v4, v2 là một đường đi không đơn trên G, do cạnh e7 = (v4, v5) được 8
lặp lại một lần trên đường đi này. Dãy v1, v3, v4, v2, v1 là một chu trình đơn, trong khi
v1, v3, v4, v2, v1, v3, v1 không phải chu trình đơn vì cạnh e4 = (v1, v3) hoặc e5 = (v1, v3)
được lặp lại một lần.
Trên đồ thị có hướng, khái niệm đường đi, chu trình được định nghĩa tương tự như
trên đồ thị vô hướng như sau.
Định nghĩa 1.3.2 Đường đi độ dài n từ đỉnh u đến đỉnh v, với n là số nguyên dương,
trên đồ thị có hướng G = (V, E) là một dãy các đỉnh x0, x1,…xn-1, xn sao cho u = x0, v =
xn và (xi, xi+1) E, i = 0, 1,…, n-1. Đỉnh u và đỉnh v tương ứng gọi là đỉnh đầu và đỉnh
cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối được gọi là chu trình.
Đường đi hay chu trình được gọi là đơn nếu không có cạnh nào lặp lại.
Ví dụ 1.3.2 Cho đồ thị có hướng G như hình 1.3.2.
Hình 1.3.2. Đường đi và chu trình của đồ thị có hướng
Thì dãy các đỉnh v1, v3, v4, v1, v2 là một đường đi và cũng là đường đi đơn trên G,
trong khi dãy v1, v3, v4, v1, v3 là một đường đi không đơn trên G, do cạnh e1 = (v1, v3)
được lặp lại một lần trên đường đi này. Dãy v1, v3, v4, v1 là một chu trình đơn, trong khi
v1, v3, v4, v1, v4, v1 không phải chu trình đơn vì cạnh e3 = (v4, v1) được lặp lại một lần.
Sự liên thông của đồ thị biểu diễn khả năng tồn tại đường đi giữa các cặp đỉnh của
đồ thị, đây là một tính chất được ứng dụng nhiều trong các hệ thống được mô hình hóa
bởi các đồ thị. Chẳng hạn, một mạng máy tính được biểu diễn bởi một đồ thị, khi đó
nếu đồ thị liên thông thì các máy tính trong mạng có thể gửi tín hiệu cho nhau, ngược
lại sẽ có một số máy không thể gửi tín hiệu cho các máy khác. Khái niệm đồ thị vô
hướng liên thông được định nghĩa như sau. 9
Định nghĩa 1.3.3 Một đồ thị vô hướng được gọi là liên thông nếu có đường đi giữa mọi
cặp đỉnh phân biệt của đồ thị.
Ví dụ 1.3.3 Trong Hình 1.3.3, đồ thị G1 là liên thông, đồ thị G2 là không liên thông, vì
không có đường đi giữa hai đỉnh c và d.
Hình 1.3.3. Đồ thị vô hướng liên thông và không liên thông
Trong đồ thị vô hướng liên thông, không chỉ luôn tồn tại đường đi giữa các cặp đỉnh
mà còn tồn tại đường đi đơn giữa chúng như định lý sau.
Định lý 1.3.1 Giữa mọi cặp đỉnh phân biệt của một đồ thị vô hướng liên thông luôn có đường đi đơn.
Chứng minh : Giả sử u và v là hai đỉnh phân biệt của đồ thị vô hướng liên thông G =
(V, E). Vì G liên thông nên có ít nhất một đường đi giữa u và v. Giả sử x0, x1, . . . , xn,
trong đó x0 = u và xn = v, là đường đi có độ dài ngắn nhất từ u đến v. Rõ ràng, đường đi
này chính là đường đi đơn từ u đến v. Thật vậy, nếu đường đi ngắn nhất này không phải
là đường đi đơn thì tồn tại hai đỉnh xi và xj sao cho xi = xj với 0 i j. Khi đó có đường
đi ngắn hơn từ u đến v qua các đỉnh x0, x1, . . . , xi−1, xj , . . . , xn bằng cách xóa đi các cạnh
tương ứng với dãy đỉnh xi, . . . , xj−1.
Đối với đồ thị có hướng, có hai khái niệm liên thông là liên thông mạnh và liên
thông yếu phụ thuộc vào việc ta có xem xét đến hướng trên các cạnh hay không.
Định nghĩa 1.3.4 Một đồ thị có hướng được gọi là liên thông mạnh nếu có đường đi
giữa mọi cặp đỉnh phân biệt của nó. Một đồ thị có hướng được gọi là liên thông yếu nếu
đồ thị vô hướng tương ứng của nó là đồ thị liên thông. 10
Chúng ta lưu ý rằng, đường đi giữa một cặp đỉnh x và y trong đồ thị liên thông mạnh
là đường đi từ x đến y hoặc từ y đến x. Vì vậy, để đồ thị G là liên thông mạnh thì với
mọi cặp đỉnh x và y phải luôn có đường đi từ x đến y và từ y đến x.
Ví dụ 1.3.4 Trong Hình 1.3.4, đồ thị G1 không liên thông mạnh, đồ thị G2 liên thông mạnh.
Hình 1.3.4. Đồ thị có hướng liên thông mạnh và không liên thông mạnh
Chúng ta có thể thấy rằng bất kỳ một đồ thị vô hướng liên thông nào cũng có thể
định hướng các cạnh để tạo thành một đồ thị có hướng liên thông yếu. Tuy nhiên, điều
này không đúng đối với đồ thị có hướng liên thông mạnh. Một đồ thị vô hướng mà có
thể định hướng được các cạnh của nó để tạo ra một đồ thị có hướng liên thông mạnh thì
gọi là đồ thị vô hướng liên thông định hướng được. Điều kiện để có thể định hướng các
cạnh của một đồ thị vô hướng liên thông để nó trở thành một đồ thị có hướng liên thông
mạnh được chỉ ra như định lý sau.
Định lý 1.3.2 Một đồ thị vô hướng liên thông là định hướng được khi và chỉ khi mỗi
cạnh của nó thuộc ít nhất một chu trình.
Chứng minh : Giả sử một đồ thị vô hướng định hướng được thành đồ thị có hướng liên
thông mạnh. Gọi (u, v) là một cạnh của đồ thị có hướng liên thông mạnh. Từ sự tồn tại
đường đi có hướng từ u đến v và từ v đến u nên (u, v) phải nằm trên ít nhất một chu
trình của đồ thị này và do đó cạnh (u, v) phải thuộc ít nhất một chu trình của đồ thị vô
hướng liên thông. Điều kiện cần được chứng minh. 11
Để chứng minh điều kiện đủ ta chỉ ra một thủ tục định hướng các cạnh của một đồ
thị vô hướng liên thông G mà mỗi cạnh của nó thuộc ít nhất một chu trình. Giả sử C là
một chu trình của G. Định hướng các cạnh của C theo một hướng đi vòng theo nó. Nếu
tất cả các cạnh của G đã được định hướng thì kết thúc thủ tục. Ngược lại, chọn e là một
cạnh chưa được định hướng có chung một đỉnh với ít nhất một trong số các cạnh đã
được định hướng. Theo giả thiết có chu trình C’ chứa e. Định hướng các cạnh chưa
được định hướng của C’ theo một hướng dọc theo chu trình này (không định hướng lại
các cạnh đã được định hướng). Thủ tục sẽ được lặp lại cho đến khi tất cả các cạnh của
G được định hướng. Rõ ràng với hai đỉnh bất kỳ thuộc các cạnh đã được định hướng
luôn có đường đi có hướng giữ chúng. Vì số cạnh của G là hữu hạn nên thủ tục sẽ dừng
do mỗi lần định hướng các cạnh trên một chu trình mới C’ ta định hướng thêm được ít
nhất một cạnh. Khi thủ tục dừng ta thu được đồ thị G* là đồ thị có hướng liên thông mạnh.
Trong một số ứng dụng, chúng ta cần xem xét một bộ phận các cạnh và đỉnh của
một đồ thị. Một bộ phận như vậy gọi là một đồ thị con của đồ thị. Đồ thị con của đồ thị
được định nghĩa một cách hình thức như sau.
Định nghĩa 1.3.5 Một đồ thị H = (W, F) được gọi là đồ thị con của đồ thị G = (V, E)
nếu W V và F E.
Ví dụ 1.3.5 Trong Hình 1.3.5, đồ thị H là đồ thị con của đồ thị G. G H
Hình 1.3.5. Đồ thị con của đồ thị
Khi một đồ thị không liên thông (mạnh) thì nó bao gồm một số đồ thị con mà mỗi
đồ thị con là một đồ thị liên thông (mạnh). Ta gọi mỗi đồ thị con này là một thành phần
liên thông (mạnh) của đồ thị.
Ví dụ 1.3.6 Đồ thị H như hình 1.3.6 gồm ba thành phần liên thông H1, H2, H3. 12
Hình 1.3.6. Các thành phần liên thông của đồ thị vô hướng
Ví dụ 1.3.7 Cho các đồ thị có hướng G và H như hình 1.3.7, thì đồ thị G là liên thông
mạnh. Đồ thị H là liên thông yếu, không liên thông mạnh, nó có ba thành phần liên
thông mạnh là đỉnh a, đỉnh e và đồ thị con gồm các đỉnh b, c và d và các cạnh (b, c), (c,
d) và (d, b).
Hình 1.3.7. Các thành phần liên thông của đồ thị có hướng
Trong một đồ thị có thể tồn tại một đỉnh và một số cạnh đặc biệt mà nếu loại bỏ nó
khỏi đồ thị thì có thể làm mất tính liên thông hoặc tăng số thành phần liên thông của đồ
thị. Những đỉnh và cạnh như vậy gọi là đỉnh rẽ nhánh và cạnh cầu của đồ thị.
Định nghĩa 1.3.6 Đỉnh v được gọi là đỉnh rẽ nhánh của đồ thị nếu loại bỏ v cùng với
các cạnh liên thuộc với nó khỏi đồ thị thì làm tăng số thành phần liên thông của đồ thị.
Cạnh e được gọi là cạnh cầu nếu loại bỏ nó khỏi đồ thị thì làm tăng số thành phần liên thông của đồ thị.
Ví dụ 1.3.8 Cho đồ thị như Hình 1.3.8 thì đỉnh c là đỉnh rẽ nhánh, các cạnh (d, e) và (f,
g) là các cạnh cầu. 13
Hình 1.3.8. Đỉnh rẽ nhánh và cạnh cầu của đồ thị
1.4 Một số dạng đồ thị đặc biệt
Phần này giới thiệu một số đồ thị vô hướng đặc biệt có nhiều ứng dụng trong thực
tế như đồ thị đầy đủ, đồ thị vòng, bánh xe, lập phương và đồ thị hai phía. Một trong các
ứng dụng của đồ thị đầy đủ, đồ thị vòng, bánh xe và lập phương là mô hình hóa sơ đồ
kết nối mạng máy tính. Đồ thị hai phía có thể được ứng dụng để giải bài toán tối ưu
ghép cặp, đối sánh và phân công làm việc.
Định nghĩa 1.4.1 Một đồ thị đầy đủ n đỉnh, n 1, ký hiệu Kn, là một đơn đồ thị vô
hướng có n đỉnh và mọi cặp đỉnh phân biệt của nó đều tương ứng với một cạnh.
Ví dụ 1.4.1 Hình 1.4.1 cho các đồ thị đầy đủ K3, K4, K5 và K6.
Hình 1.4.1. Đồ thị Kn đầy đủ
Định nghĩa 1.4.2 Một đồ thị vòng n đỉnh, n 3, ký hiệu Cn, là một đơn đồ thị vô hướng
có n đỉnh v1, v2, …, vn và các cạnh của nó tạo thành một chu trình duy nhất (v1, v2), (v2,
v3), …, (vn-1, vn), (vn, v1).
Ví dụ 1.4.2 Hình 1.4.2 cho các đồ thị vòng C3, C4, C5 và C6. 14
