Chương 1 Đại cương về đồ thị 1.1 Định nghĩa đồ thị Tập hợp X 6= ∅ các đối tượng và bộ E các cặp sắp thứ tự và không sắp thứ tự các phần tử của X được gọi là một đồ thị, đồng thời được ký hiệu bằng G(X, E) (hoặc G = (X, E) hoặc G(X)).1: Ví dụ về mô hình đồ thị Các phần tử của X được gọi là các đỉnh. Cặp đỉnh không sắp thứ tự được gọi là cạnh, cặp đỉnh sắp thứ tự được gọi là cạnh có hướng hay cung. Đồ thị chỉ chứa các cạnh được gọi là đồ thị vô hướng, còn đồ thị chỉ chứa các cung được gọi là đồ thị có hướng. Nếu đồ thị chứa cả cạnh lẫn cung thì nó được họi là đồ thị hỗn hợp hay đồ thị hỗn tạp.
Một cặp đỉnh có thể được nối với nhau bằng hai hoặc nhiều hơn hai cạnh (hai hoặc nhiều hơn hai cung cùng một hướng). Một cung (hay một cạnh) có thể bắt đầu và kết thúc tại cùng một đỉnh. Cung (cạnh) loại này được gọi là khuyên hay nút. Cặp đỉnh x,y được nối với nhau bằng cạnh (cung) a và a được gọi là cạnh (cung) thuộc đỉnh x, đỉnh y.
4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Nếu cung b xuất phát từ đỉnh u và đi vào đỉnh v thì u được gọi là đỉnh đầu, v được gọi là đỉnh cuối của cung b. Cặp đỉnh x, y được gọi là hai đỉnh kề nhau nếu x 6= y và là hai đầu của cùng một cạnh hay một cung. Đối với mọi đỉnh x dùng D(x) để chỉ tập đỉnh, mà mỗi đỉnh này được nối với x bằng ít nhất một cạnh; D+ (x) để chỉ tập đỉnh mà mỗi đỉnh này từ x có cung đi tới; D− (x) để chỉ tập đỉnh mà mỗi đỉnh này có cung đi tới x. Hai cạnh (cung) a,b được gọi là kề nhau, nếu: i) Chúng khác nhau.
ii) Chúng có đỉnh chung (nếu a, b là cung, thì không phụ thuộc vào đỉnh chung đó là đỉnh đầu hay đỉnh cuối của cung a, đỉnh đầu hay đỉnh cuối của cung b). Cho đồ thị hỗn hợp có khuyên G(X, E) với tập đỉnh X = {x1 , x2 , x3 , x4 , x5 , x6 , x7 }, tập cạnh và cung E = {x1 , x2 ; x2 , x3 ; x4 , x6 ; x5 , x6 ; x3 , x3 ; x1 , x6 ; x5 , x5 } = {a1 a2 a3 a4 a5 b1 b2 }, trong đó a1 , a2 , a3 , a4 , a5 là các cạnh; b1 , b2 là các cung.2 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Một số dạng đồ thị đặc biệt Trong những trường hợp không cần phân biệt giữa cạnh và cung ta quy ước dùng cạnh thay cho cả cung. Đồ thị G = (X, E) 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, được gọi là đồ thị đơn hay đơn đồ thị và thông thường được gọi là đồ thị. Đồ thị G = (X, E) không có khuyên và có ít nhất một cặp đỉnh được nối với nhau bằng từ hai cạnh trở lên được gọi là đa đồ thị.
Đồ thị G = (X, E) được gọi là vô hướng nếu các cạnh trong E là không định hướng. Đồ thị G = (X, E) được gọi là có hướng nếu các cạnh trong E là có định hướng.3 Đồ thị vô hướng (có hướng) G = (X, E) được gọi là đồ thị đầy đủ nếu mỗi cặp đỉnh được nối với nhau bằng đúng một cạnh (một cung với chiều tùy ý).4: Đồ thị đầy đủ Đa đồ thị vô hướng (có hướng) G = (X, E) được gọi là đồ thị k-đầy đủ nếu mỗi cặp đỉnh được nối với nhau bằng đúng k cạnh (k cung với 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com chiều tùy ý). Đồ thị (đa đồ thị) G = (X, E) được gọi là đồ thị (đa đồ thị) hai mảng tập đỉnh X của nóTđược phân thành hai tập con rời nhau X1 , X2 nếu S (X1 X2 = X và X1 X2 = ∅) và mỗi cạnh đều có một đầu thuộc X1 còn đầu kia thuộc X2 .5: Đồ thị hai mảng Đồ thị (đa đồ thị) G = (X, E) được gọi là đồ thị (đa đồ thị) phẳng, nếu nó có ít nhất một dạng biểu diễn hình học trải trên một mặt phẳng nào đó, mà các cạnh của đồ thị chỉ cắt nhau ở đỉnh. Đồ thị (đa đồ thị) G = (X, E) được gọi là hữu hạn, nếu số đỉnh của nó hữu hạn, tức tập X có lực lượng hữu hạn.
Đồ thị (đa đồ thị) G = (X, E) được gọi là vô hạn, nếu số đỉnh của nó là vô hạn. Đồ thị (đa đồ thị) với số cạnh thuộc mỗi đỉnh đều hữu hạn được gọi là đồ thị (đa đồ thị) hữu hạn địa phương. Một đồ thị hay đa đồ thị hữu hạn thì nó cũng hữu hạn địa phương. Đồ thị có hướng G(X, E) được gọi là đồ thị đối xứng nếu ∀x, y ∈ X, (x, y) ∈ E ⇒ (y, x) ∈ E Trong đồ thị đối xứng tùy ý, hai đỉnh kề nhau luôn luôn được nối bằng hai cung ngược chiều nhau.
Để đơn giản, trong trường hợp này người ta quy ước thay hai cung nói trên bằng một cạnh nối giữa x và y. Đồ thị có hướng G(X, E) được gọi là đồ thị phản đối xứng nếu ∀x, y ∈ X, (x, y) ∈ E ⇒ (y, x) ∈ /E 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.3 Bậc của đỉnh đồ thị 1.1 Bậc của đỉnh Giả sử G = (X, E) là một đồ thị hay đa đồ thị có hướng hoặc không có hướng. Số cạnh và cung thuộc đỉnh x được gọi là bậc của đỉnh x và ký hiệu bằng m(x). Đỉnh có bậc bằng 0 được gọi là đỉnh biệt lập.
Đỉnh có bậc bằng 1 được gọi là đỉnh treo.6 ta có: m(1) = 2, m(2) = 2, m(3) = 3, m(4) = 3, m(5) = 3, m(6) = 1, m(7) = 0 Đỉnh 6 là đỉnh treo, đỉnh 7 là đỉnh cô lập, g là cạnh treo.2 Nửa bậc Giả sử G = (X, E) là một đồ thị hay đa đồ thị có hướng. Số cung đi vào đỉnh x được gọi là nửa bậc vào của đỉnh x và ký hiệu bằng m0 (x) hoặc m− (x). Số cung đi ra khỏi đỉnh x được gọi là nửa bậc ra của đỉnh x và ký hiệu bằng m00 (x) hoặc m+ (x). Ký hiệu tập cung đi vào đỉnh x bằng E − (x), còn tập cung ra khỏi đỉnh x bằng E + (x).
8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.3 Một số tính chất Định lí 1. Trong đồ thị hay đa đồ thị tùy ý, tổng số bậc của tất cả các đỉnh bao giờ cũng gấp đôi số cạnh. Thật vậy, khi tính bậc của các đỉnh mỗi cạnh vô hướng hặc có hướng đều được tính mỗi đầu đúng một lần, do đó tổng số bậc của tất cả các đỉnh bao giờ cũng gấp đôi số cạnh. Trong đồ thị hay đa đồ thị tùy ý, số đỉnh bậc lẻ luôn luôn là số chẵn.
Giả sử đồ thị (đa đồ thị) G = (X, E) có n đỉnh, m cạnh X = {x1 , x2 , ., xn−1 , xn }, Các đỉnh x1 , x2 , ., xk bậc lẻ và xk+1 , ., xn−1 , xn bậc chẵn. 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Theo định lý 1. + m(xn−1 ) + m(xn ) = 2m | {z } | {z } A B Vì B là tổng của các số chẵn nên B là số chẵn. Do đó, A = 2m − B phải là số chẵn.
Số chẵn A là tổng của k số lẻ, nên k phải chẵn. Bởi vậy, số đỉnh bậc lẻ trong đồ thị (đa đồ thị) bất kỳ phải là một số chẵn. Trong một đồ thị với n đỉnh (n ≥ 2) có ít nhất hai đỉnh cùng bậc. Giả sử G = (X, E) là đồ thị tùy ý với |X| = n ≥ 2.
Xét hai khả năng sau: 1) Nếu đồ thị có đỉnh bậc 0 thì trong đồ thị không có đỉnh nào kề với đỉnh này, nên mỗi đỉnh của đồ thị có bậc là một trong n − 1 số nguyên: 0, 1, 2,. 2) Nếu đồ thị có đỉnh bậc n − 1 thì đồ thị không có đỉnh bậc 0. Bởi vậy, bậc của mỗi đỉnh thuộc đồ thị là một trong n − 1 số nguyên: 1, 2,. Từ kết quả trên ta nhận thấy, đồ thị G = (X, E) với n đỉnh (n ≥ 2), nhưng chỉ có không quá n − 1 loại bậc.
Do đó, phải có ít nhất hai đỉnh cùng bậc. Khẳng định được chứng minh. Nếu đồ thị với n đỉnh (n ≥ 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. Giả sử x,y là hai đỉnh cùng bậc của đồ thị G = (X, E) và đều có bậc 0 hoặc bậc n − 1.
Loại x, y và tất cả các cạnh thuộc chúng khỏi đồ thị G, ta được đồ thị con G1 có n − 2 đỉnh.3 trong G1 có hai đỉnh cùng bậc, chẳng hạn u,v. 1) Nếu x, y cùng bậc 0, thì u,v trong G không kề với x,y nên u,v trong G đồng thời là hai đỉnh cùng bậc. Như vậy, đồ thị G phải có ít nhất hai cặp đỉnh cùng bậc. 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 2) Nếu x, y đều bậc n − 1.
Khi đó, mỗi đỉnh u, v đều kề đồng thời với x, y nên trong đồ thị G các đỉnh u, v cũng cùng bậc. Như vậy, đồ thị G phải có ít nhất hai cặp đỉnh cùng bậc. Cả hai trường hợp có thể đều dẫn tới mâu thuẫn với tính chất: Đồ thị G có duy nhất một cặp đỉnh cùng bậc, nên x, y không thể cùng bậc 0 hặc cùng bậc n − 1. Khẳng định được chứng minh.
Số đỉnh bậc n − 1 trong đồ thị G với n đỉnh (n ≥ 4), mà bốn đỉnh tùy ý có ít nhất một đỉnh kề với ba đỉnh còn lại, không nhỏ hơn n − 3. 1) Nếu G là đồ thị đầy đủ, thì khẳng định là hiển nhiên. 2) Nếu G có cặp đỉnh duy nhất không kề nhau. Khi đó, trong G có n − 2 đỉnh bậc n − 1 3) Nếu G có hai cặp đỉnh không kề nhau, thì chúng phải có đỉnh chung.
Thật vậy, giải sử A, B; I, D là hai cặp đỉnh không kề nhau. Nếu hai cặp đỉnh này không có đỉnh chung, thì trong 4 đỉnh A, B, I, D không có đỉnh nào kề với ba đỉnh còn lại.