BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
——————————o0o——————————
LƯU THỊ THÊM
ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON
CÙNG MỘT SỐ ỨNG DỤNG
Chuyên ngành: Toán ứng dụng
Mã số: 8 46 01 12
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học
TS. Trần Minh Tước
HÀ NỘI, 2018
Lời cảm ơn
Sau một thời gian cố gắng, nỗ lực học tập và nghiên cứu, đến nay tôi
đã hoàn thành luận văn tốt nghiệp thạc sĩ của mình. Để có được kết quả
này, tôi xin bày tỏ lòng biết ơn sâu sắc và lời cảm ơn chân thành nhất đến
thầy giáo, TS. Trần Minh Tước, người đã định hướng nghiên cứu cho tôi
trong suốt thời gian thực hiện luận văn của mình.
Tôi xin chân thành cảm ơn sự giúp đỡ quý báu của các thầy cô giáo
trong bộ môn Toán ứng dụng nói riêng và khoa Toán, trường Đại học Sư
phạm Hà Nội 2 nói chung.
Xin cảm ơn những người thân trong gia đình và tất cả những người bạn
thân yêu đã hết sức thông cảm, chia sẻ và tạo điều kiện tốt nhất cho tôi
để tôi có thể học tập, nghiên cứu và thực hiện luận văn của mình.
Tôi rất mong nhận được sự đóng góp ý kiến của các thầy cô và các bạn
để luận văn được hoàn thiện hơn.
Tôi xin chân thành cảm ơn!
Hà Nội, tháng 11 năm 2018
Tác giả
Lưu Thị Thêm
1
Lời cam đoan
Tôi xin cam đoan luận văn này là công trình nghiên cứu của riêng tôi,
được thực hiện dưới sự hướng dẫn của thầy giáo TS. Trần Minh Tước.
Trong quá trình nghiên cứu, tôi đã kế thừa thành quả khoa học của các
nhà khoa học với sự trân trọng và biết ơn. Các kết quả trích dẫn trong
luận văn này đã được chỉ rõ nguồn gốc.
Hà Nội, tháng 11 năm 2018
Tác giả
Lưu Thị Thêm
2
Mục lục
Mở đầu
5
Chương 1 Kiến thức cơ sở
1.1 Đồ thị và phân loại đồ thị . . . . . . . .
1.1.1 Đồ thị có hướng . . . . . . . . . .
1.1.2 Đồ thị vô hướng . . . . . . . . . .
1.1.3 Đa đồ thị có hướng và đa đồ thị vô
1.1.4 Đồ thị có trọng số . . . . . . . . .
1.2 Đồ thị con và một số vấn đề liên quan . .
1.3 Bậc của đỉnh . . . . . . . . . . . . . . .
1.4 Chu trình, mạch . . . . . . . . . . . . .
1.5 Tính liên thông của đồ thị . . . . . . . .
1.6 Cây khung của đồ thị . . . . . . . . . . .
1.7 Phương pháp duyệt đồ thị . . . . . . . .
1.8 Luồng trong mạng . . . . . . . . . . . .
1.9 Ghép cặp đồ thị . . . . . . . . . . . . . .
. . . .
. . . .
. . . .
hướng.
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Chương 2 Vết Euler, mạch Euler và đồ thị Euler
2.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Định lí về điều kiện cần và đủ để một đồ thị là đồ thị Euler
2.3 Thuật toán tìm các mạch Euler . . . . . . . . . . . . . . .
2.3.1 Đối với đồ thị vô hướng . . . . . . . . . . . . . . . .
2.3.2 Đối với đồ thị có hướng . . . . . . . . . . . . . . . .
2.4 Ứng dụng đồ thị Euler giải bài toán người đưa thư . . . . .
2.4.1 Thuật toán tìm lời giải cho bài toán người đưa thư
trong đồ thị vô hướng có trọng số không là đồ thị
Euler[[2]] . . . . . . . . . . . . . . . . . . . . . . . .
3
.
.
.
.
.
.
.
.
.
.
.
.
.
7
7
7
8
9
10
11
12
12
13
13
14
14
15
.
.
.
.
.
.
16
16
18
20
20
21
25
. 25
Luận văn thạc sĩ
2.4.2 Thuật toán tìm lời giải cho bài toán người đưa thư
trong đồ thị có hướng có trọng số không là đồ thị
Euler[[2]] . . . . . . . . . . . . . . . . . . . . . . . . . 28
Chương 3
3.1
3.2
3.3
3.4
Đường đi Hamilton, chu trình Hamilton và đồ
thị Hamilton
Định nghĩa đồ thị Hamilton . . . . . . . . . . . . . . . . . .
Một số định lí cơ bản . . . . . . . . . . . . . . . . . . . . . .
Tìm các chu trình Hamilton bằng phương pháp nhân ma trận
Ứng dụng: Thuật toán xấp xỉ cho bài toán tìm chu trình của
người bán hàng có trọng số tối thiểu trong đồ thị có trọng số
3.4.1 Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . .
3.4.2 Xây dựng thuật toán xấp xỉ tìm chu trình Hamilton có
trọng số tối thiểu của đồ thị có trọng số. . . . . . . . .
3.4.3 Thuật toán cải tiến . . . . . . . . . . . . . . . . . . .
33
33
35
40
45
45
48
50
Kết luận
53
Tài liệu tham khảo
54
Lưu Thị Thêm
4
K20-Toán ứng dụng
Mở đầu
1. Lí do chọn đề tài
Năm 1736 có thể coi là năm khai sinh của lý thuyết đồ thị với việc
công bố lời giải bài toán “Bảy cây cầu ở Königsberg” của nhà toán học
lỗi lạc người Thụy Sĩ Leonhard Euler (1707 - 1783). Từ đó có khái niệm
và những nghiên cứu về một loại đồ thị được gọi là đồ thị Euler. Năm
1858, nhà toán học Hamilton (1805 - 1865) đã đưa ra trò chơi “Đi vòng
quanh thế giới”, mở ra một loạt các nghiên cứu cho một loại đồ thị là
đồ thị Hamilton. Ra đời muộn hơn một số lĩnh vực toán khác nhưng lý
thuyết đồ thị đang có rất nhiều các ứng dụng trong thực tế. Khi nghiên
cứu về lý thuyết đồ thị thì hai lớp đồ thị trên luôn luôn được nhắc đến và
tạo những hứng thú cho việc tìm hiểu, phát triển những ứng dụng. Những
phép chứng minh, những thuật toán của lý thuyết đồ thị đã tạo cảm hứng
cho không chỉ những người nghiên cứu toán học mà còn cho cả những lập
trình viên công nghệ thông tin. Đã có rất nhiều những nghiên cứu về hai
loại đồ thị này và cũng có rất nhiều định lý, các mối liên hệ và những ứng
dụng đã được tìm thấy. Được sự gợi ý của giảng viên hướng dẫn là T.S
Trần Minh Tước và với mong muốn có một sự hiểu biết đầy đủ hơn về mối
liên hệ giữa đồ thị Euler, đồ thị Hamilton với một số các khái niệm khác
của lý thuyết đồ thị và một số ứng dụng của nó, tôi đã chọn đề tài: “Đồ
thị Euler và đồ thị Hamilton cùng một số ứng dụng”.
2. Mục đích và nghiên cứu
Nghiên cứu về đồ thị Euler, đồ thị Hamilton và mối liên hệ của chúng
với một số khái niệm khác của lý thuyết đồ thị cùng một số ứng dụng của
hai lớp đồ thị này.
5
Luận văn thạc sĩ
3. Nhiệm vụ nghiên cứu
• Tìm hiểu các tính chất của mạch Euler, chu trình Hamilton trong đồ
thị.
• Tìm hiểu mối liên hệ của đồ thị Euler, đồ thị Hamilton với các khái
niệm khác để nghiên cứu các thuật toán liên quan tới hai loại đồ thị
này.
• Tìm hiểu về một số ứng dụng của hai loại đồ thị trên.
4. Đối tượng và phạm vi nghiên cứu
• Đồ thị có hướng và đồ thị vô hướng.
• Mạch Euler, đồ thị Euler.
• Chu trình Hamilton, đồ thị Hamilton.
5. Phương pháp nghiên cứu
Chúng tôi sử dụng chủ yếu việc nghiên cứu lý thuyết, vận dụng các
luật logic trong toán học, cùng với một số công cụ của tổ hợp và tối ưu
rời rạc.
Lưu Thị Thêm
6
K20-Toán ứng dụng
Chương 1
Kiến thức cơ sở
Trong chương này, các khái niệm và kết quả tôi tham khảo từ tài liệu
"Lý thuyết Tổ hợp và Đồ thị", Nxb ĐHQG Hà Nội, 2005 của GS. TS. Ngô
Đắc Tân.
1.1
Đồ thị và phân loại đồ thị
Khái niệm đồ thị xuất hiện từ nhiều lĩnh vực khác nhau trong cuộc
sống. Trong mỗi lĩnh vực riêng của mình, người ta cần tới một kiểu đồ thị
nào đó. Vì vậy mà cũng xuất hiện nhiều loại đồ thị khác nhau. Song tựu
chung lại ta có thể phân loại chúng theo bốn dạng chính sau đây: đồ thị
có hướng, đồ thị vô hướng, đa đồ thị có hướng, đa đồ thị vô hướng. Ngoài
ra, tùy theo từng mục đích mà ta có thể gắn trọng số cho các đỉnh hoặc
các cạnh của đồ thị.
1.1.1
Đồ thị có hướng
Một đồ thị có hướng G là một cặp có thứ tự G = (V, E), ở đây V là
một tập, còn E là một tập con của tích đề các V × V , tức E là một quan
hệ hai ngôi trên V .
Các phần tử của V được gọi là các đỉnh, còn các phần tử của E được
gọi là các cung của đồ thị có hướng G. Cụ thể hơn, nếu (a, b) ∈ E thì
(a, b) được gọi là cung của G với đỉnh đầu là a, đỉnh cuối là b và có hướng
đi từ a tới b.
Ví dụ 1.1.1. Cho G = (V, E) với V = {a, b, c, d, e, f } và
E = {(a, a), (a, b), (b, d), (d, b), (c, e), (e, a)} . Khi đó G là đồ thị có hướng
được biểu diễn bằng hình (1.1).
7
Luận văn thạc sĩ
Hình 1.1: Ví dụ một đồ thị có hướng
Giả sử G = (V, E) là một đồ thị có hướng. Nếu (a, b) ∈ E thì các
đỉnh a và b được gọi là liên thuộc với cung (a, b). Khi đó a và b cũng được
gọi là kề nhau. Hai cung bất kì của G được gọi là kề nhau nếu chúng có
đỉnh chung. Cung dạng (a, a) với a ∈ V được gọi là khuyên. Đỉnh không
liên thuộc với một cung nào được gọi là đỉnh cô lập. Số các đỉnh của G,
tức là | V |, được gọi là cấp của G. Số các cung của G, tức là | E |, được
gọi là cỡ của G.
1.1.2
Đồ thị vô hướng
Một đồ thị vô hướng G là một cặp có thứ tự G = (V, E), ở đây V là
một tập, còn E là tập với các phần tử là các đa tập lực lượng 2 trên V ,
trong đó đa tập là khái niệm mở rộng của khái niệm tập hợp. Trong một
đa tập, mỗi phần tử có thể xuất hiện nhiều hơn một lần. Tổng số tất cả
các lần xuất hiện của các phần tử được gọi là lực lượng của đa tập. Các
phần tử của V cũng được gọi là các đỉnh, còn các phần tử của E được gọi
là các cạnh của đồ thị vô hướng G. Nếu e = {a, b} là một cạnh của G thì
a và b được gọi là các đỉnh đầu mút của cạnh e hay các đỉnh liên thuộc
với e. Ta cũng thường kí hiệu cạnh e = {a, b} ngắn gọn là ab.
Ví dụ 1.1.2. Cho G = (V, E) với V = {a, b, c, d} và
E = {{a, a} , {a, b} , {b, d} , {b, c} , {c, d}}. Khi đó G là đồ thị vô hướng
và được biểu diễn bằng hình (1.2).
Lưu Thị Thêm
8
K20-Toán ứng dụng
Luận văn thạc sĩ
Hình 1.2: Ví dụ một đồ thị vô hướng
1.1.3
Đa đồ thị có hướng và đa đồ thị vô hướng.
Một đa đồ thị có hướng G là một cặp có thứ tự G = (V, E) ở đây V
là một tập, còn E là một đa tập với các phần tử đều thuộc tích Đề các
V × V . Đa đồ thị có hướng cũng được biểu diễn trên mặt phẳng tương
tự như đồ thị có hướng, trong có các cung có cùng đỉnh đầu và đỉnh cuối
phải được biểu diễn bằng các đường cong khác nhau. Tương tự, một đa
đồ thị vô hướng G là một cặp có thứ tự G = (V, E), ở đây V là một tập,
còn E là một đa tập với các phần tử đều là đa tập lực lượng 2 trên V .
Trong biểu diễn trên mặt phẳng của đa đồ thị vô hướng, các cạnh khác
nhau nhưng có các đỉnh đầu mút như nhau phải được biểu diễn bằng các
đường cong khác nhau.
Ví dụ 1.1.3. Đồ thị G1 = (V, E1 ) với V = {a, b, c, d} và
E1 = {(a, d), (a, d), (d, a), (a, c), (c, a), (b, a), (c, b), (b, c), (d, c)} là một đa
đồ thị có hướng:
Lưu Thị Thêm
9
K20-Toán ứng dụng
Luận văn thạc sĩ
Ví dụ 1.1.4. Đồ thị G2 = (V, E2 ) với V = {a, b, c, d} và
E2 = {{a, d} , {a, d} , {d, a} , {c, d} , {a, c} , {c, a} , {b, a} , {c, b} , {c, b}} là
một đa đồ thị vô hướng:
1.1.4
Đồ thị có trọng số
Đồ thị G = (V, E) được gọi là đồ thị có trọng số nếu ít nhất một
trong hai hàm f : V → WV và g : E → WE được xác định, ở đây WV và
WE là các tập nào đấy. Các phần tử của WV và WE có thể chỉ đơn thuần
là các dữ liệu nhưng thường thì có một ý nghĩa định lượng. Giá trị f(v)
cho v ∈ V được gọi là trọng số của đỉnh v , còn giá trị g(e) cho e ∈ E
được gọi là trọng số của cung e hoặc trọng số của cạnh e. Người ta cũng
thường kí hiệu đồ thị có trọng số là G = (V, E, f ) hay G = (V, E, g) hay
G = (V, E, f, g) tùy thuộc vào việc chỉ một hàm f , chỉ một hàm g hay cả
hai hàm f và g được xác định.
Ví dụ 1.1.5. Cho G = (V, E, g) với V = {a, b, c, d, e} và
E = {(a, b), (a, c), (b, e), (e, d), (b, d), (c, e)} và g : E → N được xác định
như sau:
g(a, b) = g(b, e) = g(c, e) = 5
g(a, c) = 4
g(e, d) = g(b, d) = 7
Khi đó G là một trọng đồ thị có hướng được biểu diễn bởi hình (1.3).
Lưu Thị Thêm
10
K20-Toán ứng dụng
Luận văn thạc sĩ
Hình 1.3: Ví dụ một đồ thị có trọng số có hướng
1.2
Đồ thị con và một số vấn đề liên quan
Đồ thị G0 = (V 0 , E 0 ) được gọi là đồ thị con của đồ thị G = (V, E)
nếu V 0 ⊆ V và E 0 ⊆ E . Đồ thị con G0 = (V 0 , E 0 ) của đồ thị G = (V, E)
được gọi là đồ thị con bao trùm của G nếu V 0 = V . Nếu E 0 chứa tất cả
các cung hay cạnh của G, mà hai đỉnh liên thuộc với nó đều thuộc V 0 , thì
G0 = (V 0 , E 0 ) được gọi là đồ thị con của G = (V, E) cảm sinh bởi tập đỉnh
V 0 hay cũng được gọi là đồ thị con cảm sinh bởi G = (V, E) trên tập đỉnh
V 0 . Khi đó G0 cũng được kí hiệu là G0 = G[V 0 ].
Ta thường phải xây dựng các đồ thị mới từ các đồ thị đã cho bằng cách
xóa hay thêm một số đỉnh hoặc cạnh. Nếu W ⊆ V , thì G−W = G[V \W ],
tức là đồ thị con của G nhận được từ G bằng cách xóa đi các đỉnh thuộc
W và mọi cung (hay cạnh) liên thuộc với các đỉnh trong W . Tương tự, nếu
E 0 ⊆ E , thì G − E 0 = (V, E\E 0 ). Nếu W = {w} và E 0 = {(x, y)} (hay
E 0 = {xy}) thì kí hiệu ở trên được đơn giản viết thành G−w và G−(x, y)
(hay G − xy ). Tương tự, nếu x và y không kề nhau trong G thì G + (x, y)
(hay G + xy ) là đồ thị nhận được từ G bằng cách nối x với y bằng cung
(x, y) (tương ứng bằng cạnh xy ). Nếu G1 = (V1 , E1 ) và G2 = (V2 , E2 ) là
hai đồ thị đã cho thì hợp của hai đồ thị này, kí hiệu G1 ∪ G2 , là đồ thị với
tập đỉnh là V1 ∪ V2 và tập cung (hay cạnh) là E1 ∪ E2 . Nếu cả hai đồ thị
G1 và G2 là đồ thị vô hướng thì kết nối của hai đồ thị G1 và G2 , kí hiệu
là G1 + G2 , là đồ thị nhận được từ G1 ∪ G2 bằng cách thêm vào tất cả các
cạnh dạng xy với x 6= y và x ∈ V1 , y ∈ V2 .
Lưu Thị Thêm
11
K20-Toán ứng dụng
Luận văn thạc sĩ
1.3
Bậc của đỉnh
a) Đối với đồ thị vô hướng
Bậc của đỉnh v , kí hiệu là deg(v), là số cạnh liên thuộc với v .
Nhận xét 1.3.1 Nếu đồ thị vô hướng G = (V, E) có n cạnh thì tổng
số bậc của các đỉnh trong G bằng 2n và số đỉnh bậc lẻ luôn là số chẵn.
b) Đối với đồ thị có hướng
Cho đồ thị có hướng G = (V, E) với m cung.
– Bán bậc ra của đỉnh v , kí hiệu là deg + (v), là số cung đi ra khỏi
v.
– Bán bậc vào của đỉnh v , kí hiệu là deg − (v), là số cung đi vào
đỉnh v .
Nhận xét 1.3.2 Tổng tất cả các bán bậc ra bằng tổng tất cả các
bán bậc vào của các đỉnh và bằng m.
X
X
+
deg (v) =
deg − (v) = m.
v∈V
1.4
v∈V
Chu trình, mạch
Cho G = (V, E) là đồ thị có hướng hoặc vô hướng.
• Hành trình trong đồ thị có hướng G là dãy v0 , v1 , ..., vn với vi ∈ V và
vi−1 vi ∈ E, ∀i = 1, n.
• Hành trình trong đồ thị vô hướng G là dãy v0 , v1 , ..., vn với vi ∈ V và
vi−1 vi ∈ E hoặc vi vi−1 ∈ E, ∀i = 1, n.
• Hành trình trong đồ thị có các đỉnh phân biệt được gọi là đường đi.
• Hành trình trong đồ thị có các cạnh phân biệt được gọi là vết.
• Hành trình được gọi là khép kín nếu đỉnh đầu và đỉnh cuối trùng
nhau.
• Hành trình khép kín mà khi xóa đỉnh cuối thì trở thành một đường
đi được gọi là chu trình.
• Vết có điểm đầu và điểm cuối trùng nhau được gọi là mạch.
Lưu Thị Thêm
12
K20-Toán ứng dụng
Luận văn thạc sĩ
1.5
Tính liên thông của đồ thị
a Đối với đồ thị vô hướng G = (V, E)
– Đồ thị G được gọi là liên thông nếu luôn tồn tại đường đi giữa
mọi cặp đỉnh phân biệt của G.
– Đồ thị con liên thông cực đại của G được gọi là thành phần liên
thông của G.
– Nếu bỏ đi một cạnh mà làm tăng số thành phần liên thông của
đồ G thị thì cạnh đó được gọi là cạnh cắt hoặc cạnh cầu của G.
b Đối với đồ thị có hướng G = (V, E)
– G được gọi là liên thông yếu nếu đồ thị vô hướng nền của nó là
đồ thị liên thông.
– G = (V, E) được gọi là liên thông một chiều nếu với hai đỉnh
khác nhau bất kì vi và vj , tồn tại một hành trình có hướng với
đỉnh đầu là vi và đỉnh cuối là vj hoặc một hành trình có hướng
với đỉnh đầu là vj và đỉnh cuối là vi (hoặc cả hai hành trình đó).
– G = (V, E) được gọi là liên thông mạnh nếu với hai đỉnh bất kì
khác nhau vi và vj , luôn tồn tại cả hành trình có hướng với đỉnh
đầu là vi và đỉnh cuối là vj và hành trình có hướng với đỉnh đầu
là vj và đỉnh cuối là vi .
1.6
Cây khung của đồ thị
• Cây bao trùm (tiếng anh: spanning tree), còn được gọi là cây khung,
của đồ thị G là cây con của đồ thị G, chứa tất cả các đỉnh của G.
Nói cách khác, cây bao trùm của một đồ thị G là một đồ thị con của
G, chứa tất cả các đỉnh của G, liên thông và không có chu trình.
• Mọi đồ thị liên thông đều có ít nhất một cây khung.
• Cây khung ngoài của đồ thị có hướng là cây khung có đúng một đỉnh
có bán bậc vào bằng 0.
• Cây khung trong của đồ thị có hướng là cây khung có đúng một đỉnh
có bán bậc ra bằng 0.
Lưu Thị Thêm
13
K20-Toán ứng dụng
Luận văn thạc sĩ
1.7
Phương pháp duyệt đồ thị
a) Duyệt đồ thị ưu tiên chiều sâu (DFS).
Bước 1: Bắt đầu từ một đỉnh v0 vào thăm và lấy thông tin.
Bước 2: Chọn một trong số các đỉnh kề với v0 mà chưa được thăm
(gọi là u).
Bước 3: Khởi động quá trình duyệt bắt đầu từ u (giống như từ v0 ).
b) Duyệt đồ thị ưu tiên chiều rộng (BFS).
Bước 1: Bắt đầu từ v0 , thăm tất cả các đỉnh kề với v0 .
Bước 2: Lần lượt khởi động quá trình duyệt từ mỗi đỉnh vừa được
thăm.
1.8
Luồng trong mạng
• Ta gọi mạng là một đồ thị có hướng G = (V, E), trong đó có duy
nhất một đỉnh s không có cung đi vào (gọi là điểm phát) và có duy
nhất một đỉnh t không có cung đi ra (gọi là đỉnh thu). Mỗi cung
e = (u, v) ∈ E được gán với một số không âm w(e) = w(u, v) gọi là
khả năng thông qua của cung đó. Ta quy ước rằng nếu không có cung
w(x, y) thì khả năng thông qua w(u, v) của nó được gán bằng 0.
• Cho G = (V, E), ta gọi luồng f trong mạng G là một phép gán cho
mỗi cung e = (u, v) ∈ E một số thực không âm f (e) = f (u, v), gọi
là luồng trên cung e, thỏa mãn các điều kiện sau:
1) Với mọi cung (x, y) ∈ E ta luôn có 0 ≤ f (x, y) ≤ w(x, y); với
w(x, y) là khả năng thông qua của cung (x, y)
X
X
f (s, x) −
f (y, s) = c ≥ 0;
2)
y∈N − (s)
x∈N + (s)
3)
X
x∈N + (t)
f (t, x) −
X
f (y, t) = −c;
y∈N − (t)
4) Với
t,
Xmọi đỉnh z 6= s,X
f (z, x) −
f (y, z) = 0.
x∈N + (z)
y∈N − (z)
• Giá trị của luồng được tính bằng tổng giá trị trên các cung đi ra từ
đỉnh nguồn s hoặc tổng giá trị trên các cung đi vào từ đỉnh thu t.
Luồng trong mạng có giá trị luồng lớn nhất được gọi là luồng cực đại
trên mạng đó.
Lưu Thị Thêm
14
K20-Toán ứng dụng
Luận văn thạc sĩ
1.9
Ghép cặp đồ thị
Định nghĩa 1 Cho đồ thị G = (V, E).
• Một ghép cặp của G là một tập con M nào đó của tập cạnh E sao
cho trong M không có hai cạnh nào là kề nhau (có đỉnh chung).
• Một ghép cặp cực đại là ghép cặp mà không thể mở rộng thành một
ghép cặp có số cạnh lớn hơn.
• Một ghép cặp lớn nhất là ghép cặp có số cạnh lớn nhất của đồ thị G.
• Một ghép cặp đầy đủ/ hoàn chỉnh/ hoàn hảo của G là ghép cặp mà
tất cả các đỉnh của G đều là những đầu mút của các cạnh thuộc ghép
cặp đó.
Ví dụ 1.9.1. Xét đồ thị G trong hình vẽ dưới đây:
Hình 1.4:
M1 = {b, d, h}, M2 = {a, e, k} là những ghép cặp lớn nhất.
M3 = {c, h}, M4 = {c, l} là những ghép cặp cực đại.
Ví dụ 1.9.2. Xét đồ thị G trong hình vẽ dưới đây:
Hình 1.5: Ghép cặp đầy đủ trong đồ thị
M = {v1 v2 , v3 v7 , v4 v6 , v5 v8 } là một ghép cặp đầy đủ của G.
Lưu Thị Thêm
15
K20-Toán ứng dụng
Chương 2
Vết Euler, mạch Euler và đồ thị
Euler
2.1
Định nghĩa
Định nghĩa 2.1.1 ([2]) Cho đồ thị G = (V, E) liên thông, có hướng hoặc
vô hướng.
• Nếu tồn tại một mạch C chứa tất cả các cạnh của G thì C được gọi
là mạch Euler trong G. Khi đó G được gọi là đồ thị Euler.
• Nếu tồn tại một vết T chứa tất cả các cạnh của G thì T được gọi là
vết Euler trong G. Khi đó G được gọi là đồ thị nửa Euler.
Nhận xét 2.1.1 Nếu G là đồ thị Euler thì G là đồ thị nửa Euler.
Ví dụ 2.1.1. Cho đồ thị G dưới đây:
Hình 2.1:
Đồ thị G trên hình (2.1) là đồ thị Euler với mạch Euler:
v1 , v2 , v3 , v4 , v8 , v6 , v7 , v8 , v3 , v1 , v5 , v2 , v4 , v7 , v5 , v6 , v1 .
16
Luận văn thạc sĩ
Ví dụ 2.1.2. Cho đồ thị G dưới đây:
Hình 2.2:
Đồ thị G trên hình(2.2) là đồ thị Euler với mạch Euler:
v1 , v8 , v2 , v3 , v4 , v6 , v7 , v8 , v6 , v5 , v4 , v2 , v1 .
Ví dụ 2.1.3. Cho đồ thị G dưới đây:
Hình 2.3:
Đồ thị G trên hình (2.3) là đồ thị nửa Euler với vết Euler:
v3 , v2 , v1 , v5 , v2 , v4 , v5 , v3 , v4 .
Ví dụ 2.1.4. Cho đồ thị G dưới đây:
Lưu Thị Thêm
17
K20-Toán ứng dụng
Luận văn thạc sĩ
Hình 2.4:
Đồ thị G trên hình (2.4) là đồ thị nửa Euler với vết Euler:
v3 , v2 , v1 , v5 , v4 , v1 , v5 , v4 .
2.2
Định lí về điều kiện cần và đủ để một đồ thị là
đồ thị Euler
Không phải mọi đồ thị liên thông đều là đồ thị Euler. Nhà toán học
Euler đã đưa ra câu trả lời cho bài toán "Bảy cây cầu Königsberg" với kết
luận không thể đi một lần qua tất cả bảy cây cầu mà mỗi cây cầu chỉ đi
qua đúng một lần. Dưới đây là định lí về điều kiện cần và đủ để một đồ
thị vô hướng là đồ thị Euler.
Định lý 2.2.1 ([2]) Ta có:
a) Đồ thị vô hướng G là đồ thị Euler khi và chỉ khi G liên thông và bậc
của mọi đỉnh đều là số chẵn.
b) Đồ thị vô hướng G là đồ thị nửa Euler khi và chỉ khi G liên thông và
có đúng 2 đỉnh bậc lẻ.
Chứng minh. Định lí 2.3.1a
a) Điều kiện cần.
Giả sử G = (V, E) là một mạch Euler. Khi đó, mỗi lần mạch đi
qua một đỉnh nào đó thì bậc của đỉnh đó tăng lên 2. Mặt khác mỗi
cạnh chỉ được lặp lại đúng một lần nên bậc của mỗi đỉnh luôn là bậc
chẵn.
b) Điều kiện đủ.
Giả sử G = (V, E) có bậc của mọi đỉnh đều là số chẵn. Suy ra
Lưu Thị Thêm
18
K20-Toán ứng dụng
- Xem thêm -