Chương 1 Lý thuyết đồ thị 1.1 Các khái niệm cơ bản. Định nghĩa đồ thị và các yếu tố liên quan. + Tập hợp X 6= ∅ các đối tượng tùy ý và bộ E các cặp được sắp thứ tự và không được 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 hoặc bằng G(X, E) hoặc bằng G = (X, E) hoặc bằng G(X). Các phần tử của tập X được gọi là các đỉnh còn các phần tử của tập E được gọi là các cạnh của đồ thị G.
Hình ảnh về đồ thị: Trong (H1) có: Tập đỉnh là X = {2, 3, 5, 6, 7, 10} Tập cạnh là E = {(2, 3), (2, 7), (3, 5), (3, 7), (3, 10), (6, 5), (6, 7), (7, 5), (7, 10)} + Cặp đỉnh không sắp thứ tự a = (x, y) được gọi là cạnh hay cạnh vô hướng, còn x, y được gọi là các đỉnh đầu của cạnh a; cặp đỉnh được sắp thứ tự b = (u, v) được gọi là cạnh có hướng hay cung. Đỉnh u được gọi là đỉnh đầu, còn đỉnh v được gọi là đỉnh cuối của cung b. Người ta còn nói rằng: cung b đi từ đỉnh u đến đỉnh v. 5 TIEU LUAN MOI download : skknchat@gmail.com Trong hình (H2) có: Tập cạnh là (3, 5), (5, 7), (7, 10) Cung là (3,10), trong đó 3 là đỉnh đầu, 10 là đỉnh cuối.
+ Đồ thị chỉ chứa các cạnh được gọi là đồ thị vô hướng. Đồ thị chỉ chứa các cung gọi là đồ thị có hướng. Nếu đồ thị chứa cả cạnh lẫn cung, thì gọ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 cạnh (hay một cung) có thể bắt đầu và kết thúc tại một đỉnh. 6 TIEU LUAN MOI download : skknchat@gmail.com Trong hình (H4) có: Cạnh bội là cạnh (3, 5). Cung bội là cung (3, 10). + 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 cùng một cung.
+ Đối với mỗi đỉnh x dùng D(x) để kí hiệu 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. Trong hình (H4) có: D(3) = {5, 7}; D+ (3) = {10}; D− (3) = ∅ + Hai cạnh (cung) a, b được gọi là kề nhau, nếu: 1.
Chúng khác nhau. Chúng có đỉnh chung (nếu a, b 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 ). Biểu diễn đồ thị bằng hình học. Đồ thị có nhiều cách để biểu diễn nhưng trong phần này chỉ trình bày cách biểu diễn bằng hình học.
Giả sử có đồ thị G = (X, E). Để có dạng biểu diễn hình học của G ta cần biểu diễn đỉnh và cạnh. Biểu diễn đỉnh: Lấy các điểm trên mặt phẳng hay trong không gian tương ứng với các phần tử của tập X và dùng ngay kí hiệu các phần tử này để ghi trên các điểm tương ứng. Biểu diễn cạnh: Nếu cạnh a với hai đỉnh đầu là x, y thì nó được biểu diễn bằng một đoạn thẳng hay một đoạn cong nối giữa hai điểm x, y và không đi qua các điểm tương ứng chung gian khác.
Biểu diễn cung: Cung b có đỉnh đầu là u, đỉnh cuối là v , thì nó được biểu diễn bằng một đoạn thẳng hay một đoạn cong được định hướng từ u sang v và không đi qua các điểm tương ứng chung gian khác. Hình nhận được gọi là dạng biểu diễn hình học của đồ thị G = (X, E). Đôi khi người ta cũng gọi dạng biểu diễn hình học là đồ thị. Giả sử đồ thị G có tập đỉnh X = {x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 } và tập cạnh E gồm các cạnh a1 = (x1 , x2 ), a2 = (x2 , x3 ), a3 = (x4 , x5 ), a4 = (x5 , x6 ), khuyên vô hướng a5 = (x7 , x7 ), khuyên có hướng (x6 , x6 ) và cung b1 = (x1 , x8 ).
Khi đó đồ thị G = (X, E) có dạng biểu diễn hình học sau: 7 TIEU LUAN MOI download : skknchat@gmail. Một số dạng đồ thị đặc biệt. Trong những trường hợp không cần phân biệt 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 gọi là đồ thị.
Hình ảnh về đơn đồ 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ị. Hình ảnh về đa đồ thị. + Đồ 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 ý).
+ Đồ thị (đa đồ thị) G = (X, E) được gọi là hữu hạn, nếu số đỉnh của nó là hữu hạn, tức tập X có lực lượng hữu hạn. + Đồ thị G được gọi là giả đồ thị nếu trong G tồn tại một cạnh nối một đỉnh 8 TIEU LUAN MOI download : skknchat@gmail.com với chính nó. Cạnh này được gọi là khuyên. + Đồ thị (đa đồ thị) G = (X, E) được gọi là đồ thị (đa đồ thị) hai mảng, nếu tập đỉnh X được phân thành hai tập con rời nhau X1 , X2 , (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.
Hình ảnh của đồ thị hai mảng.2 Bậc của đồ thị. Để định lượng số cạnh thuộc mỗi đỉnh đồ thị người ta đưa ra khái niệm bậc của đỉnh. Đối với đồ thị và đa đồ thị có hướng để định lượng số cung đi vào và số cung đi ra tại mỗi đỉnh còn có khái niệm nửa bậc vào và nửa bậc ra. Bậc của đỉnh đồ thị.
Giả sử G = (X, E) là một đồ thị hay đa đồ thị có hướng hoặc là 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). Nếu cạnh là khuyên thì được tính là 2. 9 TIEU LUAN MOI download : skknchat@gmail.com Trong đồ thị hình (H9) có: m(X1 ) = 3; m(X2 ) = 5 m(X3 ) = m(X5 ) = 2 m(X4 ) = 5 m(X6 ) = 1 m(X7 ) = 0 + Đỉnh có bậc 0 được gọi là đỉnh biệt lập.
+ Đỉnh có bậc 1 được gọi là đỉnh treo. Trong đồ thị hình (H9) có: X7 là đỉnh biệt lập. X6 là đỉnh treo. (X4 , X6 ) là cung treo.
Giả sử G = (X, E) là đồ thị hoặc đ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 đi ra khỏi đỉnh x bằng E + (x).
Trong đồ thị hình (H10) có: m0 (X1 ) = 0; m00 (X1 ) = 3 m0 (X2 ) = 1; m00 (X2 ) = 2 10 TIEU LUAN MOI download : skknchat@gmail. Một số tính chất. Trong một đồ thị hay đa đồ thị tùy ý tổng số bậc của tất cả các đỉnh luôn luôn 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 hoặc có hướng đều được tính mỗi đầu đúng một lần, mà mỗi cạnh thuộc hai đỉnh nên ta có điều cần chứng minh.
Trong một đồ thị hay đa đồ thị tùy ý G = (X, U ) số đỉnh bậc lẻ luôn luôn là một số chẵn. Giả sử đồ thị có |X| = n; |U | = m và k đỉnh bậc lẻ là x1 ; x2 ; x3 ;. Vì N là số chẵn nên M chẵn, suy ra k chẵn. Trong một đồ thị với n(n ≥ 2) đỉnh có ít nhất 2 đỉ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ó một cạnh nào nối đỉnh này với tất cả các đỉnh còn lại trong n đỉnh của đồ thị, do đó mỗi đỉnh của đồ thị có bậc là một trong n − 1 số nguyên 0, 1, 2,. 2) Nếu không có đỉnh bậc 0 thì n đỉnh của đồ thị có bậc là một trong n − 1 số 1, 2,. Từ kết quả lý luận trên khẳng định được rằng, đồ thị G(X, E) với n đỉnh, nhưng chỉ có không quá n − 1 loại bậc.
Bởi vậy 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(n > 2) đỉnh có đúng 2 đỉnh cùng bậc, thì hai đỉnh này không thể đồng thời có bậc 0 hoặ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 đồng thời hai đỉnh cùng bậc trong đồ thị G. Như vậy, đồ thị G phải có ít nhất hai cặp đỉnh cùng 11 TIEU LUAN MOI download : skknchat@gmail. 2) Nếu x, y đều có 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 trong đồ thị G phải có ít nhất hai cặp đỉnh cùng bậc. Cả hai trường hợp đều có thể 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 hoặ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(n ≥ 4) đỉnh, mà 4 đỉnh tùy ý có ít nhất một đỉnh kề với 3 đỉnh còn lại, không nhỏ hơn n − 3.