Luận văn Thạc sĩ Khoa học: Lý thuyết đồ thị với các bài toán phổ thông

Chia sẻ: Na Na | Ngày: | Loại File: PDF | Số trang:92

Thêm vào BST

Báo xấu

256
lượt xem 33
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn "Lý thuyết đồ thị với các bài toán phổ thông" đưa đến sự sáng tạo trong cách nhìn nhận bài toán và lập luận cách giải dưới con mắt của lý thuyết đồ thị. Ngoài phần mở đầu và kết luận luận văn gồm 3 chương: Chương 1 Đại cương về đồ thị, Chương 2 Một số bài toán đồ thị cơ bản, Chương 3 Ứng dụng lý thuyết đồ thị vào giải toán phổ thông.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học: Lý thuyết đồ thị với các bài toán phổ thông

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ———– NGUYỄN THỊ MINH THƯƠNG LÝ THUYẾT ĐỒ THỊ VỚI CÁC BÀI TOÁN PHỔ THÔNG LUẬN VĂN THẠC SĨ KHOA HỌC HÀ NỘI - 2015
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ———– NGUYỄN THỊ MINH THƯƠNG LÝ THUYẾT ĐỒ THỊ VỚI CÁC BÀI TOÁN PHỔ THÔNG Chuyên ngành: Phương pháp toán sơ cấp Mã số: 60.46.01.13 LUẬN VĂN THẠC SĨ KHOA HỌC Người hướng dẫn khoa học: GS.TS Đặng Huy Ruận HÀ NỘI - 2015
Mục lục Lời nói đầu 3 1 Đại cương về đồ thị 4 1.1 Định nghĩa đồ thị . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Một số dạng đồ thị đặc biệt . . . . . . . . . . . . . . . . 6 1.3 Bậc của đỉnh đồ thị . . . . . . . . . . . . . . . . . . . . . 8 1.3.1 Bậc của đỉnh . . . . . . . . . . . . . . . . . . . . 8 1.3.2 Nửa bậc . . . . . . . . . . . . . . . . . . . . . . . 8 1.3.3 Một số tính chất . . . . . . . . . . . . . . . . . . 9 1.4 Xích, chu trình, đường, vòng . . . . . . . . . . . . . . . . 13 1.4.1 Xích, chu trình . . . . . . . . . . . . . . . . . . . 13 1.4.2 Đường, vòng . . . . . . . . . . . . . . . . . . . . . 14 1.4.3 Một số tính chất . . . . . . . . . . . . . . . . . . 15 1.5 Đồ thị liên thông . . . . . . . . . . . . . . . . . . . . . . 16 1.5.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . 16 1.5.2 Tính chất . . . . . . . . . . . . . . . . . . . . . . 17 1.6 Số ổn định trong, số ổn định ngoài . . . . . . . . . . . . 18 1.6.1 Số ổn định trong . . . . . . . . . . . . . . . . . . 18 1.6.2 Số ổn định ngoài . . . . . . . . . . . . . . . . . . 19 1.6.3 Các thuật toán tìm số ổn định trong, số ổn định ngoài. . . . . . . . . . . . . . . . . . . . . . . . . 20 1.7 Nhân của đồ thị và ứng dụng vào trò chơi . . . . . . . . 21 1.7.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . 21 1.7.2 Tính chất . . . . . . . . . . . . . . . . . . . . . . 22 1.7.3 Trò chơi Nim . . . . . . . . . . . . . . . . . . . . 23 1.7.4 Trò chơi bốc các vật . . . . . . . . . . . . . . . . 24 1.8 Cây và bụi . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.8.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . 29 1.8.2 Đặc điểm của cây và bụi . . . . . . . . . . . . . . 30 1
2 Một số bài toán đồ thị cơ bản 33 2.1 Bài toán về đường đi . . . . . . . . . . . . . . . . . . . . 33 2.1.1 Đường đi Euler - Chu trình Euler. . . . . . . . . . 33 2.1.2 Đường đi Hamilton - Chu trình Hamilton. . . . . 40 2.2 Bài toán tô màu đồ thị . . . . . . . . . . . . . . . . . . . 43 2.2.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . 43 2.2.2 Một số tính chất . . . . . . . . . . . . . . . . . . 43 2.2.3 Thuật toán tô màu đỉnh. . . . . . . . . . . . . . . 53 3 Ứng dụng lý thuyết đồ thị vào giải toán phổ thông. 54 3.1 Quy trình giải bài toán bằng phương pháp đồ thị. . . . . 54 3.1.1 Xây dựng đồ thị G mô tả các quan hệ. . . . . . . 54 3.1.2 Dựa vào các kết quả của lý thuyết đồ thị hoặc lý luận trực tiếp suy ra đáp án của bài toán D. . . . 54 3.2 Bài toán về đỉnh - cạnh của đồ thị. . . . . . . . . . . . . 55 3.3 Bài toán về xích, chu trình, đường, vòng và tính liên thông của đồ thị. . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.4 Bài toán về tô màu đồ thị. . . . . . . . . . . . . . . . . 63 3.5 Bài toán liên quan đến số ổn định trong, số ổn định ngoài. 74 3.6 Bài toán liên quan đến đường đi. . . . . . . . . . . . . . 76 3.6.1 Bài toán tìm đường đi trong mê cung . . . . . . . 76 3.6.2 Bài toán liên quan đến đường và chu trình Euler . 80 3.6.3 Bài toán liên quan đến đường và chu trình Hamilton 82 3.7 Bài toán liên quan đến cây. . . . . . . . . . . . . . . . . 84 Kết luận 89 Tài liệu tham khảo 90 2
LỜI NÓI ĐẦU Lý thuyết đồ thị là một trong những ngành khoa học ra đời khá sớm. Lý thuyết đồ thị giúp mô tả hình học và giải quyết nhiều bài toán thực tế phức tạp. Khái niệm lý thuyết đồ thị được nhiều nhà khoa học độc lập nghiên cứu và có nhiều đóng góp trong lĩnh vực toán học ứng dụng. Năm 2001, Bộ Giáo Dục và Đào Tạo có quy định các chuyên đề bồi dưỡng học sinh giỏi thống nhất trên toàn quốc, trong đó có chuyên đề lý thuyết đồ thị. Như vậy, việc học chuyên đề Lý Thuyết Đồ Thị đối với học sinh khá và giỏi đang là nhu cầu thực tế trong dạy học toán ở phổ thông. Tuy nhiên, việc dạy học chuyên đề này còn tồn tại một số khó khăn vì những lý do khác nhau. Một trong các lý do đó là sự mới mẻ, độc đáo và khó của chủ đề kiến thức này. Luận văn "Lý thuyết đồ thị với các bài toán phổ thông" đưa đến sự sáng tạo trong cách nhìn nhận bài toán và lập luận cách giải dưới con mắt của lý thuyết đồ thị. Ngoài phần mở đầu và kết luận luận văn gồm 3 chương: Chương 1 Đại cương về đồ thị. Chương 2 Một số bài toán đồ thị cơ bản. Chương 3 Ứng dụng lý thuyết đồ thị vào giải toán phổ thông. Luận văn được hoàn thành dưới sự hướng dẫn, giúp đỡ tận tình của GS.TS Đặng Huy Ruận, tác giả xin bày tỏ sự kính trọng và lòng biết ơn sâu sắc tới thầy. Tác giả cũng xin gửi lời cảm ơn chân thành đến Ban giám hiệu cùng các thầy cô giáo khoa Toán - Cơ - Tin, Trường Đại học Khoa Học Tự Nhiên - Đại Học Quốc Gia Hà Nội đã tạo điều kiện, dạy bảo và dìu dắt tác giả trong những năm học vừa qua. Xin chân thành cảm ơn sự giúp đỡ của bạn bè, người thân trong thời gian học tập và làm luận văn. Do khả năng nhận thức của bản thân tác giả, luận văn còn nhiều hạn chế, thiếu sót. Tác giả kính mong các ý kiến chỉ bảo của quý thầy cô cùng sự đóng góp của các bạn đọc. Tác giả xin chân thành cảm ơn! Hà Nội, tháng 6 năm 2015 3
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)). Hình 1.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). Các cạnh (cung) này được gọi là các cạnh (cung) bội. 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
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). Ví dụ 1.1. 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. Hình 1.2 5
1.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. Hình 1.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 ý). Hình 1.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
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 .Khi đó G = (X, E) còn được ký hiệu bằng G = (X1 , X2 , E). Hình 1.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. Cho Y ⊆ X, Y 6= ∅; H ⊆ E, F = E ∩ (Y × Y ) và V = (X × X)/E. Đồ thị G1 (Y, F ) được gọi là đồ thị con, còn G2 (X, H) là đồ thị bộ phận của đồ thị G(X, E). Đồ thị G0 (X, V ) được gọi là đồ thị bù của đồ thị G(X, E). Đồ 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
1.3 Bậc của đỉnh đồ thị 1.3.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. Cạnh (cung) có ít nhất một đầu là đỉnh treo được gọi là cạnh (cung) treo. Hình 1.6 Ví dụ 1.2. Trong hình 1.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. 1.3.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
Hình 1.7 Ví dụ 1.3. Trong hình 1.7 ta có: m0 (1) = 1, m0 (2) = 2, m0 (3) = 2, m0 (4) = 0, m0 (5) = 1, m0 (6) = 1; m00 (1) = 1, m00 (2) = 1, m00 (3) = 1, m00 (4) = 1, m00 (5) = 1, m00 (6) = 2; E − (4) = {∅}, E + (4) = {g}; E − (6) = {f }, E + (6) = {e, d}. 1.3.3 Một số tính chất Định lí 1.3.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. Chứng minh. 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. Định lí 1.3.2. Trong đồ thị hay đa đồ thị tùy ý, số đỉnh bậc lẻ luôn luôn là số chẵn. Chứng minh. Giả sử đồ thị (đa đồ thị) G = (X, E) có n đỉnh, m cạnh X = {x1 , x2 , ..., xk , xk+1 , ..., xn−1 , xn }, Các đỉnh x1 , x2 , ..., xk bậc lẻ và xk+1 , ..., xn−1 , xn bậc chẵn. 9
Theo định lý 1.1 có đẳng thức: m(x1 ) + m(x2 ) + ... + m(xk ) + m(xk+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. Định lí 1.3.3. Trong một đồ thị với n đỉnh (n ≥ 2) có ít nhất hai đỉnh cùng bậc. Chứng minh. 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, ..., n − 3, n − 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, ..., n − 2, n − 1. 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. Định lí 1.3.4. 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. Chứng minh. 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. Theo định lý 1.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
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. Định lí 1.3.5. 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. Chứng minh. 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. Như vậy, mâu thuẫn với giả thiết, nên hai cặp đỉnh A, B; I, D phải có hai đỉnh trùng nhau, chẳng hạn B ≡ I. Lấy đỉnh C tùy ý khác với A, B, D. Trong bộ bốn A, B, C, D đỉnh C là đỉnh kề với cả ba đỉnh A, B, D. Loại D ra khỏi bộ bốn và thay vào đó là đỉnh E tùy ý khác với A, B, C, D. Trong bộ bốn A, B, C, E hoặc C hoặc E phải kề với ba đỉnh còn lại. Nếu E kề với ba đỉnh còn lại, thì E cũng kề với C. Do đó C kề với tất cả ba đỉnh A, B, E. Do E là đỉnh tùy ý trong n − 4 đỉnh còn lại (khác với A, B, C) nên C có bậc n − 1 C là đỉnh tùy ý trong n − 3 đỉnh bậc n − 1 Khẳng định được chứng minh. Định lí 1.3.6. Với mọi số tự nhiên n (n > 2) luôn luôn tồn tại đồ thị n đỉnh, mà ba đỉnh tùy ý của đồ thị đều không cùng bậc. Chứng minh. 1) Với n = 3 đồ thị G3 gồm một đỉnh bậc 0 và hai đỉnh bậc 1. 11
2) Giả sử khẳng định đúng với đồ thị Gn có n đỉnh. Đồ thị Gn+1 có n + 1 đỉnh được xây dựng như sau: a. Nếu Gn có đỉnh bậc n − 1, thì không có đỉnh bậc 0, nên ta ghép vào Gn đỉnh x bậc 0 và được đồ thị Gn+1 gồm n + 1 đỉnh. Việc ghép thêm đỉnh x vẫn bảo toàn tính chất của Gn (tức là, ba đỉnh bất kỳ đều không cùng bậc). Mặt khác, đồ thị Gn không có đỉnh bậc 0, nên trong Gn+1 ba đỉnh bất kỳ đều không cùng bậc. b. Nếu Gn không có đỉnh bậc n − 1. Khi đó, tất cả các đỉnh của Gn đều có bậc không vượt quá n − 2. Thêm vào Gn đỉnh x (không thuộc Gn ) và nối x với từng đỉnh thuộc Gn bằng một cạnh được đồ thị Gn+1 gồm n + 1 đỉnh. Đỉnh x có bậc n, còn bậc của mỗi đỉnh thuộc Gn trong Gn+1 được tăng lên một đơn vị, nhưng đều không vượt quá n − 1 và trong bậc mới ba đỉnh bất kỳ của Gn vẫn không cùng bậc. Khẳng định được chứng minh. Định lí 1.3.7. Trong đồ thị G = (X, E) với ít nhất kn + 1 đỉnh, mỗi đỉnh có bậc không nhỏ hơn (k − 1)n + 1 luôn tồn tại đồ thị con đầy đủ gồm k + 1 đỉnh. Chứng minh. Ta sẽ chứng minh định lý bằng phương pháp quy nạp theo k. 1) Với k = 1 khẳng định hiển nhiên đúng. 2) Với k = 2 có thể làm chặt chẽ hơn giả thiết. Nếu đồ thị 2n + 1 đỉnh mà mỗi đỉnh có bậc không nhỏ hơn n, thì nó có đồ thị con 3 đỉnh đầy đủ. Thật vậy, xét đỉnh x tùy ý, còn y là một trong các đỉnh kề với x. Tổng số đỉnh kề với x và y không nhỏ hơn 2n, nhưng số đỉnh khác x và y chỉ là 2n − 1. Bởi vậy, phải có ít nhất một đỉnh z được tính hai lần. Khi đó, x, y, z tạo thành một đồ thị con đầy đủ ba đỉnh. 3) Giả sử khẳng định trên đúng với k. Cần suy ra tính đúng đắn của khẳng định đối với k + 1. Theo giả thiết, thông đồ thị G gồm (k + 1)n + 1 đỉnh, số đỉnh kề với đỉnh x tùy ý không nhỏ hơn kn + 1, nên số đỉnh không kề với x sẽ không vượt quá n. Bởi vậy, mỗi đỉnh y kề với x thì nó kề với nhiều nhất n đỉnh không kề với đỉnh x. Do đó, đỉnh y phải kề với ít nhất kn + 1 − n = (k − 1)n + 1 đỉnh kề với đỉnh x. Xét đồ thị con G1 gồm các đỉnh kề với x. Đồ thị con G1 có ít nhất kn + 1 đỉnh và mỗi đỉnh của nó kề với ít nhất (k − 1)n + 1 đỉnh thuộc G1 , nên theo giả thiết quy nạp, 12
trong G1 có đồ thị con đầy đủ G2 gồm k + 1 đỉnh. Vì đỉnh x kề với từng đỉnh thuộc G2 , nên đỉnh x kết hợp với các đỉnh thuộc G2 lập thành một đồ thị con đầy đủ gồm k + 2 đỉnh thong đồ thị G. Khẳng định được chứng minh. 1.4 Xích, chu trình, đường, vòng 1.4.1 Xích, chu trình Giả sử G(X, E) là một đồ thị hay đa đồ thị vô hướng: Dãy α các đỉnh của G(X, E): α = [x1 , x2 , ..., xi , xi+1 , ..., xn−1 , xn ] được gọi là một xích hay một dây chuyền, nếu ∀i(1 ≤ i ≤ n − 1) cặp đỉnh xi , xi+1 kề nhau. Tổng số vị trí của tất cả các cạnh xuất hiện trong xích α được gọi là độ dài của xích α, ký hiệu |α|. Các đỉnh x1 , xn được gọi là hai đỉnh đầu của xích α. Để chỉ rõ đỉnh đầu và đỉnh cuối ta còn ký hiệu α bằng α[x1 , xn ]. Một xích có hai đầu trùng nhau được gọi là một chu trình. Xích (chu trình) α được gọi là xích (chu trình) đơn (sơ cấp hay cơ bản), nếu nó đi qua mỗi cạnh (mỗi đỉnh) không quá một lần. Ví dụ 1.4. Cho đồ thị Hình 1.8 13
α1 = [5, 1, 4, 2, 1] là một dây chuyền không sơ cấp. α2 = [1, 2, 3, 4] là một dây chuyền sơ cấp. α3 = [1, 5, 1] và α4 = [1, 2, 3, 4, 1] là các chu trình đơn và sơ cấp. α5 = [1, 2, 4, 3, 2, 1] là chu trình đơn nhưng không sơ cấp. 1.4.2 Đường, vòng Giả sử G(X, E) là một đồ thị hay đa đồ thị có hướng. Dãy đỉnh β của G(X, E) : β = [x1 , x2 , ..., xi , xi+1 , ..., xm−1 , xm ] được gọi là một đường hay một đường đi nếu ∀i(1 ≤ i ≤ m − 1), đỉnh xi là đỉnh đầu, còn đỉnh xi+1 là đỉnh cuối của một cung nào đó. Tổng số vị trí của tất cả các cung xuất hiện trong β được gọi là đồ dài của đường β, ký hiệu: |β|. Đỉnh x1 được gọi là đỉnh đầu còn xm là đỉnh cuối của đường β. Người ta còn nói rằng, đường β xuất phát từ đỉnh x1 và đi tới xm . Đường β còn được ký hiệu bằng β[x1 , xm ]. Một đường có đỉnh đầu và đỉnh cuối trùng nhau được gọi là một vòng. Đường (vòng) β được gọi là đường (vòng) đơn (sơ cấp hay cơ bản), nếu nó đi qua mỗi cạnh (mỗi đỉnh) không quá một lần. Ví dụ 1.5. Cho đồ thị có hướng (hình 1.9): β1 = [1, 2, 4, 3, 5, 1] là một vòng đơn và sơ cấp. β2 = [1, 4, 3, 5] là một đường đơn và sơ cấp. β3 = [1, 4, 2, 5] không phải là đường. β4 = [1, 2, 4, 3, 2, 5] là một đường đơn nhưng không sơ cấp. β5 = [1, 4, 2, 5, 1, 2, 5] không phải là đường đơn và cũng không phải là đường sơ cấp. β6 = [1, 2, 4, 3, 2, 5, 1] là một vòng đơn nhưng không là vòng sơ cấp. 14
Hình 1.9 1.4.3 Một số tính chất Định lí 1.4.1. Trong một đồ thị vô hướng với n đỉnh (n ≥ 3) và các đỉnh đều có bậc không nhỏ hơn 2 luôn tồn tại chu trình sơ cấp. Chứng minh. Vì đồ thị hữu hạn, mà xích sơ cấp qua từng đỉnh không quá một lần nên số xích sơ cấp trong đồ thị G = (X, E) là một số hữu hạn. Bởi vậy, luôn xác định được xích sơ cấp có độ dài cực đại trong đồ thị G = (X, E). Giả sử α = [x1 , x2 , ..., xk−1 , xk ] là một trong những xích sơ cấp có độ dài cực đại. Do bậc của mỗi đỉnh không nhỏ hơn 2, nên x1 phải kề với một đỉnh y nào đó khác với x2 . Nếu y ∈/ α, tức là y 6= xi , (3 ≤ i ≤ k), thì xích sơ cấp α = [y, x1 , x2 , ..., xk−1 , xk ] có độ dài |α0 | = |α| + 1 > |α|. Ta đã đi 0 tới mâu thuẫn với tính chất độ dài cực đại của α. Bởi vậy, y ∈ α tức y ≡ xi , (3 ≤ i ≤ k), nên trong đồ thị G = (X, E) có chu trình sơ cấp β = [x1 , x2 , ..., xi , x1 ] Khẳng định được chứng minh. Định lí 1.4.2. Trong một đồ thị vô hướng với n đỉnh (n ≥ 4) và các đỉnh đều có bậc không nhỏ hơn 3 luôn tồn tại chu trình sơ cấp độ dài chẵn. 15
Chứng minh. Giả sử α là một trong những xích sơ cấp có độ dài cực đại α = [x1 , x2 , ..., xi−1 , xi , xi+1 , ..., xj−1 , xj , xj+1 , ..., xk−1 , xk ] Vì α có độ dài cực đại, mà bậc của x1 không nhỏ hơn 3, nên x1 phải kề với hai đỉnh khác thuộc α: xi , (3 ≤ i ≤ k), xj , (3 ≤ j ≤ k). Khi đó có hai chu trình sơ cấp: α1 = [x1 , x2 , ..., xi−1 , xi , x1 ] α2 = [x1 , x2 , ..., xi−1 , xi , xi+1 , ..., xj−1 , xj , x1 ] 1) Nếu một trong hai chu trình α1 , α2 có độ dài chẵn thì khẳng định được chứng minh. 2) Nếu ngược lại, cả hai chu trình α1 , α2 đề có độ dài lẻ. Khi đó xích: α3 = [x1 , x2 , ..., xi−1 , xi ] có độ dài chẵn, còn xích α4 = [xi , xi+1 , ..., xj−1 , xj , x1 ] có độ dài lẻ, nên chu trình α5 = [x1 , xi , xi+1 , ..., xj−1 , xj , x1 ] có độ dài chẵn. Khẳng định được chứng minh. 1.5 Đồ thị liên thông 1.5.1 Định nghĩa Hai đỉnh x, y của đồ thị G = (X, E) được gọi là cặp đỉnh liên thông nếu hoặc giữa x và y có ít nhất một xích nối với nhau , hoặc tồn tại ít nhất một đường đi từ x sang y hoặc từ y sang x. Hình 1.10 Trong hình 1.10 cặp đỉnh x,y là liên thông Đồ thị vô hướng G = (X, E) được gọi là đồ thị liên thông, nếu mọi cặp đỉnh của nó đều liên thông. Đồ thị có hướng G = (X, E) được gọi là đồ thị liên thông mạnh, nếu mọi cặp đỉnh của nó đều liên thông. 16
Giả sử a là đỉnh bất kỳ của đồ thị G = (X, E). Dùng Ca để ký hiệu tập con của các đỉnh thuộc G, gồm đỉnh a và tất cả các đỉnh liên thông với a trong đồ thị G. Đồ thị con của G có tập đỉnh Ca được gọi là một thành phần liên thông của đồ thị G Ví dụ 1.6. Cho đồ thị G có bốn thành phần liên thông: Các đồ thị con G1 , G3 , G4 là liên thông Đồ thị con G2 liên thông mạnh Hình 1.11 1.5.2 Tính chất Định lí 1.5.1. Đồ thị vô hướng tùy ý với n đỉnh (n ≥ 2), mà tổng bậc của hai đỉnh tùy ý không nhỏ hơn n là đồ thị liên thông. Chứng minh. Giả sử đồ thị vô hướng G(X, E) có n đỉnh (n ≥ 2). Với mọi cặp đỉnh a, b của đồ thị ta đều có: m(a) + m(b) ≥ n (1) Nhưng a, b không liên thông. Khi đó trong đồ thị G tồn tại hai thành phần liên thông: G1 chứa a và có n1 đỉnh, còn G2 chứa b và có n2 đỉnh. 17
Vì G1 , G2 là các thành phần liên thông của G nên n1 + n2 ≤ n Khi đó m(a) + m(b) ≤ (n1 − 1) + (n2 − 1) = n1 + n2 − 2 ≤ n − 2 < n (2) Như vậy, (1) và (2) mâu thuẫn nhau, nên đồ thị G phải liên thông. Khẳng định được chứng minh. Từ định lý trên suy ra hệ quả sau: Hệ quả 1.5.1. Đồ thị, mà bậc của mỗi đỉnh không nhỏ hơn nửa số đỉnh, là đồ thị liên thông. Định lí 1.5.2. Nếu đồ thị có đúng hai đỉnh bậc lẻ, thì hai đỉnh này phải liên thông. Chứng minh. Giả sử đồ thị G(X, E) có đúng hai đỉnh bậc lẻ và hai đỉnh đó là a và b. Giả sử a, b không liên thông với nhau. Khi đó chúng phải thuộc hai thành phần liên thông khác nhau của đồ thị G. Chẳng hạn G1 chứa đỉnh a, còn G2 chứa đỉnh b. Bậc của đỉnh a trong G1 cũng chính là bậc của a trong G, nên trong G1 đỉnh a vẫn có bậc lẻ. Điều này mâu thuẫn với định lý 1.2. Bởi vậy a, b phải liên thông. Khẳng định được chứng minh. 1.6 Số ổn định trong, số ổn định ngoài 1.6.1 Số ổn định trong 1. Tập ổn định trong Giả sử có đồ thị G(X, E). Tập con A ⊆ X các đỉnh của đồ thị G được gọi là tập ổn định trong, nếu mọi cặp đỉnh thuộc A đều không kề nhau (không có cạnh hoặc cung nối với nhau). Tập con B ⊆ X các đỉnh của đồ thị G được gọi là tập ổn định trong cực đại, nếu B là tập ổn định trong và nếu thêm vào B một đỉnh tùy ý x ∈ X, thì tập con nhận được B ∪ {x} sẽ không ổn định trong. 2. Tính chất Nếu A là tập ổn định trong, thì mọi tập con của A đều phải ổn định trong. 18