Lý thuyết Graph và ứng dụng

Chia sẻ: Thai Van Phuoc | Ngày: | Loại File: DOC | Số trang:20

Thêm vào BST

Báo xấu

350
lượt xem 30
download

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

Nhiệm vụ đổi mới phương pháp dạy học theo hướng tích cực hóa hoạt động học tập của học sinh không chỉ là định hướng mà còn đòi hỏi cần nghiên cứu xác định nguyên tắc, quy trình vận dụng của những phương pháp dạy học tích cực. Việc kết hợp các phương pháp truyền thống với các phương pháp dạy học đặc thù như phương pháp Graph là một giải pháp tốt. Lý thuyết đồ thị (Graph) là một chuyên ngành toán học hiện đại đã được ứng dụng vào nhiều ngành khoa học, kĩ thuật khác nhau vì lý...

Chủ đề:

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

Lưu

Nội dung Text: Lý thuyết Graph và ứng dụng

Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt LỜI MỞ ĐẦU Nhiệm vụ đổi mới phương pháp dạy học theo hướng tích cực hóa hoạt đ ộng học tập của học sinh không chỉ là định hướng mà còn đòi hỏi cần nghiên cứu xác định nguyên tắc, quy trình vận dụng của những phương pháp dạy học tích cực. Việc kết hợp các phương pháp truyền thống với các phương pháp dạy học đ ặc thù như phương pháp Graph là một giải pháp tốt. Lý thuyết đồ thị (Graph) là một chuyên ngành toán học hiện đại đã đ ược ứng dụng vào nhiều ngành khoa học, kĩ thuật khác nhau vì lý thuyết đ ồ thị toán học là phương pháp khoa học có tính khái quát cao, có tính ổn định vững chắc để mã hóa các mối quan hệ của các đối tượng được nghiên cứu. Có thể nói Graph là một phép Toán thần kì kích thích sự hoạt đông, óc tư duy, suy luận của trí não thậm chí còn là một câu trả lời thông minh, logic cho các câu đố hốc búa. Việc vận dụng phương pháp graph trong dạy học Toán nhằm nâng cao chất lượng dạy học môn học này ở trường THPT (nhất là các trường chuyên Tin) và được xem như là một trong những hành trang mới vừa tiếp cận vừa bổ sung vào hệ thống các phương pháp dạy học truyền thống song đó còn làm phong phú thêm kho tàng các phương pháp dạy học Toán . Theo hướng này, có nhiều tác giả đã thành công trong việc nghiên cứu và vận dụng lý thuyết Graph vào dạy học một số môn học ở trường phổ thông và đã có những kết quả bước đầu. Năm 1980, tác giả Trần Tr ọng Dương đã nghiên cứu đề tài: “Áp dụng phương pháp Graph và algorit hoá để nghiên cứu cấu trúc và phương pháp giải, xây dựng hệ thống về lập công thức hoá học ở trường phổ thông”. Năm 1984, Phạm Tư vớisự hướng dẫn của giáo sư Nguyễn Ngọc Quang đã nghiên cứu đề tài: “Dùng Graph nội dung của bài lên l ớp đ ể dạy và học chương Nitơ- Phôtpho ở lớp 11 trường trung học phổ thông”. Năm 1987, Nguyễn Chính Trung đã nghiên cứu: “Dùng phương pháp Graph lập chương trình tối ưu đ ể dạy môn sử”. Trong dạy học sinh học ở trường phổ thông, Nguyễn Phúc Chỉnh là người đầu tiên đi sâu nghiên cứu về lý thuyết Graph và ứng dụng lý thuyết Graph trong dạy học Giải phẫu - Sinh lý người (năm 2005). Đối với phương pháp Graph trong dạy học ttoán cácchuyên gia Hoàng Chúng và Vũ Đình Hoà đã có một số định hướng nhưng chưa có học viên cao học nào nghiên cứu một cách chi tiết. Với mong muốn được tiệp cận chuyên sâu về Graph, nhóm tác giả mạnh dạn làm bài thu hoạch “Lý thuyết đồ thị Graph”. Nội dung bài viết là những kinh nghiệm mà nhóm tác giả đã học hỏi được, bám sát vào những dạng cơ bản mà học sinh thường gặp trong học tập hay đời sống hàng ngày để từ đó vận dụng lí thuyết đồ thị và giúp ta đạt được hai mục tiêu: - Giải được một lớp bài tập - Hỗ trợ cho việc lập trình Trong bài thu hoạch, tác giả đưa ra một số khái niệm cơ bản về đồ thị kèm theo những hình ảnh minh họa sinh động kết hợp với xây dựng hệ thống phương pháp phân tích, trình bày cách giải đối với các bài tập, ví dụ cụ thể dựa theo các vấn đề được đề cập. Bên cạnh đó chúng tôi còn cung cấp đáp án và hướng dẫn giải sơ GVBM: Dư Quang Anh Huy Trang 1
Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt lược một số bài tập tiêu biểu nhằm giúp độc giả có thể thông hiểu, vận dụng, kiểm tra kiến thức và rèn luyện kĩ năng phân tích đồ thị. Mong rằng với bài thu hoạch “Lý thuyết đồ thị Graph” sẽ giúp độc giả có cái nhìn và tầm hiểu biết khái quát, sâu và rộng hơn về dạng Toán vô cùng quan trọng này. Nhân đây, nhóm tác giả xin được bày tỏ lòng cảm ơn sâu sắc tới thầy Dư Quang Anh Huy (giáo viên toán trường THPT Thốt Nốt, TP Cần Thơ) đã nhiệt tình giúp đỡ, chỉ dẫn chúng tôi trong quá trình biên soạn bài thu họạch này. Tuy bài thu hoạch được biên soạn khá kĩ và công phu nhưng việc thiếu sót là khó tránh khỏi. Nếu có điều chi sơ suất rất mong quí độc giả thông cảm! Xin chân thành cảm ơn! GVBM: Dư Quang Anh Huy Trang 2
Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt ĐỒ THỊ TRONG ĐỜI SỐNG Trong đời sống, chúng ta phải giải quyết nhiều vấn đề mà ta có thể coi một đường cong là cạnh và đầu mút của chúng được coi là đỉnh của cạnh. Để làm rõ điều này, chúng ta có thể xem xét những ví dụ sau đây.  Ví dụ 1: Hãy xác định một con đường đi bộ từ nhà đến trường tối ưu nhất (hiểu theo nghĩa khoảng cách ngắn nhất). - Khi giải quyết bài toán này bạn phải quan sát trên bản đồ, bỏ qua độ rộng hẹp của các đường phố và chỉ còn chú ý tới độ dài của các con đ ường cũng như các đầu mút giao thông để phát hiện một con đường ngắn nhất. Trong vấn đề tìm đường đi ngắn nhất này chúng ta đã coi các phố là các cạnh và các đầu mút giao thông (các ngã tư chẳng hạn) là các đỉnh của các cạnh. - Trong nhiều vấn đề phải giải quyết khác của đời sống , đôi lúc ta còn phải bỏ qua các yếu tố độ dài của các cạnh của hệ thống cạnh, và các đỉnh trong mô hình, như ví dụ sau chỉ rõ.  Ví dụ 2: Hãy vẽ sơ đồ mạng giao thông công cộng của một thành phố. - Trong hình trên là bản đồ giao thông công cộng thành phố Wien (thủ đô nước Áo). Trong vấn đề nêu ở trên, rõ ràng ta sẽ bỏ qua yếu tố độ dài các tuyến đường mà chỉ còn quan tâm đến yếu tố đường đi như thế nào, từ bên nào tới bên nào. Trong vấn đề này, các bến là các đỉnh còn cạnh là các tuyến đường đi qua chúng hoặc xuất phát từ các bến. Nhưng nhiều khi chúng ta không dễ phát hiện các yếu tố cạnh và đ ỉnh trong bài toán chúng ta phải giải quyết.  Ví dụ 3: Hãy phân nhóm học tập trong lớp sao cho những người trong cùng một nhóm là bạn thân của nhau. - Ở đây không còn những đường đi cho sẵn. Nhưng ta có thể nhận thấy các đỉnh trong sơ đồ cần lập là những em học sinh trong lớp. - Trong sơ đồ biểu diễn, ta nối những cặp hai em học sinh vốn vẫn là bạn than của nhau lại bằng một đoạn thẳng (hoặc bằng một đoạn thẳng cũng đươc). - Bằng cách đó ta sẽ có một sơ đồ gồm các đỉnh (các em học sinh) và các cạnh (các đường nối hai em chỉ khi hai em này là bạn thân của nhau trong lớp). Trong hình 7 là một ví dụ với n= 10 em học sinh. - Những mô hình quy về các tập đỉnh và các cạnh nối các đỉnh là những đồ thị. Không chỉ trong đời sống mà đặc biệt trong khoa học chúng ta cũng thường xuyên gặp những đồ thị. GVBM: Dư Quang Anh Huy Trang 3
Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt  Ví dụ 4: 7 cây cầu ở thành phố Konigsberg năm 1736. - Trong ví dụ này, những người dân của thành phố Konigsberg đ ặt câu hỏi: liệu có thể đi một vòng qua 7 cây cầu sao cho mỗi cây cầu chỉ đi qua đúng một l ần mà thôi? Nếu như coi mỗi cây cầu là một cạnh của đồ thị, với đỉnh là các hòn đảo và hai bờ sông, thì bài toán được đặt ra là có thể vẽ đồ thị tương ứng bằng một nét bút hay không? Bài toán này được người dân thành phố Konigsberg đặt ra từ những năm 1736, và được Euler giải quyết trọn vẹn trong lí thuyết đồ thị được mang tên của ông. - Sau đây là lời giải của Euler: - Để chứng minh kết quả, Euler đã phát biểu bài toán bằng các thuật ngữ của lý thuyết đồ thị. Ông loại bỏ tất cả các chi tiết ngoại trừ các vùng đất và các cây cầu, sau đó thay thế mỗi vùng đất bằng một điểm, gọi là đỉnh hoặc nút, và thay mỗi cây cầu bằng một đoạn nối, gọi là cạnh hoặc liên kết. Cấu trúc toán học thu được được gọi là một đồ thị. - Hình thù của đồ thị có thể bị bóp méo theo đủ kiểu nhưng không làm đồ thị bị thay đổi, miễn là các liên kết giữa các nút giữ nguyên. Việc một liên kết thẳng hay cong, một nút ở bên phải hay bên trái một nút khác là không quan trọng. GVBM: Dư Quang Anh Huy Trang 4
Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt - Euler nhận ra rằng bài toán có thể được giải bằng cách sử dụng bậc của các nút. Bậc của một nút là số cạnh nối với nó; trong đồ thị các cây cầu Konigsberg, ba nút có bậc bằng 3 và một nút có bậc 5. Euler đã chứng minh rằng một chu trình có dạng như mong muốn chỉ tồn tại khi và chỉ khi không có nút bậc lẻ. Một đường đi như vậy được gọi là một chu trình Euler. Do đồ thị các cây cầu Königsberg có bốn nút bậc lẻ, nên nó không thể có chu trình Euler. - Có thể sửa đổi bài toán để yêu cầu một đường đi qua tất cả các cây cầu nhưng không cần có điểm đầu và điểm cuối trùng nhau. Đường đi như vậy được gọi là một đường đi Euler. Một đường đi như vậy tồn tại khi và chỉ khi đồ thị có đúng hai đỉnh bậc lẻ. (Như vậy điều này cũng không thể đối với bảy cây cầu ở Konigsberg.) KHÁI NIỆM CƠ BẢN VỀ ĐỒ THỊ Hình 1 - Trong các ví dụ kể trên, các cạnh của đồ thị đều là các đ ường không có hướng. Những đồ thị như vậy gọi là đồ thị vô hướng. Nhưng đôi khi ta gặp những vấn đề mà khi xác lập đồ thị tương ứng ta buộc phải xác định một hướng đi cho nó. Chẳng hạn trong ví dụ 1 ,nếu bạn là người đi xe đạp thì phải lưu ý đến yếu tố là có thể có những con đường một chiều (được đánh dấu bằng mũi tên như trên hình 1). - Như vậy, giả sử đồ thị G được xác định bởi hai tập hợp, tập hợp X ( ≠ 0 ) gồm các đỉnh { A , B ,C , D } và tập hợp E gồm các cạnh nối hai đỉnh của X. Ta có A, B là hai đỉnh trong X cạnh nối AB, nếu kí hiệ là AB hoặc BA trong trường hợp này đồ thị G là đồ thị vô hướng. Nếu có phân biệt thứ tự AB và BA sẽ khác nhau thì ta có đồ thị có hướng. A B D C GVBM: Dư Quang Anh Huy Trang 5
Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt - Khi biểu diễn đồ thị có hướng thì nguyên tắc cũng vẫn giống như biểu diễn đồ thị cạnh không có hướng. Riêng đối với những cạnh có hướng ta đánh dấu mũi tên theo chiều cạnh để biểu thị hướng đi của nó. - Trong đồ thị trên có hướng với 4 đỉnh. Điểm chung nhau của tất cả các ví dụ mà chúng ta xem xét là chúng có hữu hạn đỉnh . Những đồ thị chỉ có hữu hạn đỉnh như vậy được gọi là đồ thị hữu hạn. Hình 3 - Cũng có tình huống là một đỉnh được nối với chính nó bởi môt cạnh nào đó mà ta gọi là khuyên. Trong hình 3 là một đồ thị có cạnh kép bên trái và khuyên ở giữa. - Với đặc điểm này đồ thị hữu hạn được chia thành 2 loại cơ bản là đồ thị đơn và đồ thị kép. + Đồ thị đơn thì không có khuyên và giữa hai đỉnh của nó có không quá một cạnh nối chúng. +Đồ thị kép thì hoặc có khuyên hoặc tồn tại hai đỉnh nào đó mà giữa chúng có ít nhất hai cạnh nối. - Trong chuyện đề này ta chỉ xét và nghiên cứu đồ thị hữu hạn ( tức là X và E là hữu hạn và vô hướng). Chính xác về mặt toán học đồ thị được định nghĩa như sau : Định nghĩa: Một bộ G = (X, E) gồm hai tập hợp X và E được gọi là một đồ thị hữu hạn nếu 1) X và E là 2 tập hữu hạn 2) Cho mỗi phần tử e ∈ E tồn tại một cặp hai phần tử x, y ∈ X và n ∈ Ν sao cho e = (x,y,n) (cạnh có hướng) hoặc e = {x,y,n} (cạnh vô hướng) - Số n biểu diễn cạnh e = (x,y,n) hoặc e = {x,y,n} dùng để đánh số cạnh kép hoặc các khuyên xuất phát từ cùng một đỉnh.Trong trường hợp đồ thị không có cạnh GVBM: Dư Quang Anh Huy Trang 6
Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt kép thì thay vì viết cạnh (x,y.n) hoặc {x,y.n} ta có thể viết đơn giản cạnh (x,y) hoặc {x,y} - Hai cạnh được gọi là song song nếu chúng cùng liên kết một cặp đỉnh. - Trong trường hợp tất cả các cạnh của G đều là cạnh vô hướng thì G được gọi là đồ thị vô hướng (h.4). Trong hình 4 ta có một số đồ thị đơn vô hướng 4 đỉnh - Nếu e = {x,y,n} là cạnh của G thì x,y được gọi là đỉnh của cạnh e - Trong trường hợp tất cả các cạnh của đồ thị G đều là cạnh có hướng thì G được gọi là đồ thị có hướng . Hình 4 - Nếu e = (x,y,n) là một cạnh của G thì x được gọi là đỉnh xuất phát còn y được gọi là đỉnh kết thúc của e . Hình 5 - Trong hình 5 có đồ thị G = (X,E) có tập đỉnh X với các đỉnh a,b,c,d và tập cạnh e với các cạnh {a,b}, {b,d,1}, {b,d,2}, {b,c,1}, {b.c.2}, {b,e}, {e,e,1}, {e,e,2}, {e,e,3}, {e,e,4} và {e,e,5} * Chú ý : Bậc của một đỉnh (giả sử là đỉnh A) là tổng số các cạnh của đỉnh đó (với qui ước mỗi khuyên được tính hai lần) và được kí hiệu là: deg(A) 1. Đồ thị con - Cho 2 đồ thị G (X, E) và G’(X’, E’) - Đồ thị G’ được gọi là con của đồ thị G nếu X’ ⊂ X và E’ ⊂ E. 2. Đường đi -Trong đồ thị G xét một dãy cạnh liên tiếp: A0A1, A1A2, ...., An-1An được gọi là một đường đi từ đỉnh A0 (đỉnh đầu) đến đỉnh An(đỉnh cuối) qua các đỉnh A0, A1,…, An và chứa các cạnh A0A1, A1A2, An-1An GVBM: Dư Quang Anh Huy Trang 7
Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt - Đường đi này được viết gọn lại là: A0A1A2…An hay A0-An (nếu muốn nhấn mạnh đỉnh đầu và đỉnh cuối). - Tổng quát ta có: Cho A, B là hai đỉnh của một đồ thị G. Một đường đi từ A đến B là một dãy các cạnh (Ai, Ai+1), i= 0,…, k- 1 với A0= A, Ak= B. Số các cạnh (ở đây là k) tạo nên đường đi gọi là độ dài của đường đi. - Một đường đi được gọi là đường đi đơn nếu nó không qua cạnh nào lần thứ hai. - Một đường đi được gọi là đường đi sơ cấp nếu nó không đi qua đỉnh nào lần thứ hai. *Chú ý: nếu đường đi là sơ cấp đến đường đi đơn nhưng điều ngược l ại thì không chắc đúng. 3. Chu trình: một chu trình là một đường đi khép kín ( đỉnh đầu trùng đình cuối) và có độ dài lớn hơn hoặc bằng 3. - Chu trình đơn: là một chu trình không qua cạnh nào lần thứ hai được gọi là chu trình đơn. - Một chu trình không qua đỉnh nào lần thứ hai trừ đỉnh đầu và đỉnh cuối trùng nhau gọi là một chu trình sơ cấp. Ví dụ: + Đường đi ABDE là đường đi sơ cấp độ dài bằng 3. + ABCDE là đường đi đơn không sơ cấp, độ dài bằng 5. + DBCDB không đơn, có độ dài bằng 4. + CDABC là một chu trình đơn sơ cấp, độ dài bằng 4. 4. Tính liên thông: hai đỉnh A, B của một đồ thị được gọi là hai đỉnh liên thông nếu trong đồ thị có một đường đi A-B. - Một đồ thị được gọi là liên thông nếu mọi cặp đỉnh của nó đều liên thông hay với hai đỉnh bất kỳ, ta luôn có một đường đi giữa chúng. - Một đồ thị không liên thông là hợp của hai hay nhiều đồ thị con liên thông, mỗi cặp các đồ thị con này không có đỉnh chung. - Các đồ thị con liên thông rời nhau như vậy được gọi là các thành phần liên thông của đồ thị đang xét. Vậy một đồ thị liên thông khi và chỉ khi nó có một thành phần liên thông. GVBM: Dư Quang Anh Huy Trang 8
Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt - Đồ thị có hướng G được gọi là liên thông mạnh nếu với hai đỉnh phân biệt bất kì u và v của G đều có đường đi từ u đến v và từ v đến u. - Đồ thị có hướng 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. Chú ý rằng trong một cây, giữa hai đ ỉnh bất kỳ t ồn t ại duy nhất một đường đi: sự tồn tại được bảo đảm bởi tính liên thông, mặt khác, nếu tồn tại hai đường đi phân biệt giữa hai đỉnh thì bằng cách nối chúng lại với nhau ta được một chu trình. Ví dụ: Đồ thị liên thông Đồ thị không liên thông MỘT SỐ ĐỒ THỊ ĐẶC BIỆT - Đồ thị đều là đồ thị mà mọi đỉnh đều cùng bậc. - Nếu k là bậc của đỉnh thì ta gọi là đồ thị K-đều. 2-đều, K3 3-đều, K4 1-đều K2 - Đồ thị đầy đủ là đồ thị mà mọi cặp đỉnh đều có cạnh nối chúng. - Đồ thị không đầy đủ của p đỉnh được kí hiệu là Kp. p ( p − 1) - Kp có p đỉnh và cạnh. 2 Ví dụ: K8 có 28 cạnh. K7 có 21 cạnh. p ( p − 1) Kp là một đồ thị (p-1) -đều và có cạnh. 2 Ví dụ: K5 => 4-đều, 10 cạnh. K6 => 5-đều, 15 cạnh. GVBM: Dư Quang Anh Huy Trang 9
Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt ĐƯỜNG ĐI EULER VÀ ĐỒ THỊ HAMILTON 1.Đường đi Euler - Đường đi Euler là một đường đi sơ cấp A-B qua tất cả các cạnh của đ ồ thị chỉ một lần. - Chu trình Euler là một đường đi Euler được gọi là một đồ thị Euler. * Định lí Euler: - Cho đồ thị G[ X, E] - G là đồ thị Euler khi và chỉ khi G liên thông và deg (x) là số chẵn, ∀ x∈ X. 2.Đồ thị Hamilton: - Đường đi Hamilton là một đường đi sơ cấp A-B qua tất cả các đỉnh của đồ thị chỉ một lần. - Nếu A trùng B thì ta có một chu trình Hamilton . - Một đồ thị có ít nhất một chu trình Hamilton được gọi là đồ thị Hamilton. - Không giống như đồ thị Euler hiện nay chưa có quy tắc cần và đủ để kiểm tra xem một đồ thị có phải là Hamilton hay không. Các kết quả có được hiện nay chỉ là điều kiện đủ để một đồ thị là Hamilton. + Một đồ thị đầy đủ là đồ thị Hamilton. n −1 + Với n lẻ, n ≥ 3 thì Kn sẽ có chu trình Hamilton đôi một không có cạnh 2 chung. n + Giả sử G là đồ thị đơn gồm n đỉnh, n ≥ 3. Nếu deg (x) ≥ ∀x ∈ X thì G là 2 một đồ thị Hamilton. CÁC MỆNH ĐỀ MỞ RỘNG VÀ TƯ LIỆU THAM KHẢO *Tư liệu tham khảo 1. Định nghĩa và các tính chất cơ bản về cây - Một đồ thị vô hướng liên thông không có chu trình được gọi là một cây. - Một đồ thị vô hướng không chứa chu trình được gọi là một rừng. Trong một rừng, mỗi thành viên liên thông là một cây. Ví dụ: Rừng có 3 cây A D E B C GVBM: Dư Quang Anh Huy Trang 10
Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt 2. Cây khung - Trong đồ thị liên thông G, nếu ta loại bỏ cạnh nằm trên chu trình nào đó thì ta sẽ được đồ thị vẫn liên thông. - Cây khung của đồ thị G là cây nối các đỉnh của đồ thị không còn chu trình nhưng vẫn liên thông. Ví dụ: Cho đồ thị G: A D C B Ta có cây khung sau: A D C B *Tổng quát: nếu G là đồ thị có n đỉnh, m cạnh và k thành phần liên thông thì áp dụng thủ tục vừa mô tả đối với mỗi thành phần liên thông của G, ta thu được đồ thị được gọi là rừng khung của G. 3. Cây có gốc - Cây có gốc là một cây có hướng, trong đó có một đỉnh đặc biệt gọi là gốc, từ gốc có đường đi đến mọi đỉnh khác của cây. - Trong cây có gốc thì gốc R có bậc bằng 0, còn tất cả các đỉnh khác có bậc bằng 1. - Một cây có gốc thường được vẽ với gốc r ở trên cùng và cây phát triển từ trên xuống. 1 Ví dụ: 2 3 4 5 6 7 8 9 GVBM: Dư Quang Anh Huy Trang 11
Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt + Gốc r được gọi là đỉnh mức 0. + Các đỉnh kề với r và xếp ở phía dưới được gọi là đỉnh mức 1. Đ ỉnh d ưới mức 1 là đỉnh mức 2 - Trong một cây có gốc thì v là đỉnh mức k khi và chỉ khi đ ưởng đi t ừ r đ ến v có độ dài bằng k. - Mức lớn nhất của một đỉnh bất kì trong cây được gọi là chiều cao cây. ĐỒ THỊ PHẲNG VÀ TÔ MÀU ĐỒ THỊ Để đi sâu vào hai khái niệm mới này ta hãy tìm hiểu qua bài toán mở đầu “ba làng ba và nhà máy” như sau: Ta có ba làng L1, L2, L3 muốn đặt đường nối với ba nhà máy: một nhà máy cung cấp điện Đ, một nhà máy cung cấp nước N và nhà máy cung cấp thực phẩm rau sạch R. Vấn đề đặt ra là ta có thể đặt trên một mặt ph ẳng sao cho các đường đi không giao nhau ngoài các đỉnh cực biên hay không? Từ đó, đ ồ thị biểu diễn “ba làng và ba nhà máy” cho phép định nghĩa một lớp các đồ thị gọi là lớp đồ thị không phẳng. L L L 1 2 3 1 1 1 1 1 Đ N R 1. Đồ thị phẳng: - Một đồ thị được gọi là phẳng nếu nó có thể vẽ được trên một mặt phẳng mà không có các cạnh nào cắt nhau (ở một điểm không phải là điểm mút của các cạnh). Hình vẽ như thế được gọi là một biểu diễn phẳng của đồ thị. - Một đồ thị được gọi là phẳng ngay cả khi nó được vẽ với những cạnh cắt nhau vì có thể vẽ nó bằng cách khác không có các cạnh cắt nhau. - Cho G là một đồ thị phẳng. Mỗi phần mặt phẳng giới hạn bởi một chu trình đơn không chứa bên trong một chu trình khác gọi là miền (hữu hạn) của đ ồ thị G. Chu trình giới hạn miền gọi là biên của miền. Mỗi đồ thị phẳng liên thông có một miền vô hạn duy nhất (là phần mặt phẳng bên ngoài tất cả các miền hữu hạn). Số cạnh ít nhất tạo thành biên gọi là “đai” của G. Trường hợp nếu G không có chu trình thì đai chính là số cạnh của G. GVBM: Dư Quang Anh Huy Trang 12
Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt Ví dụ: A B M1 M4 M2 D M3 E C F Đồ thị trên có 4 miền (M1, M2, M3, M4) và có đai là 8 Định lí: Nếu một đò thị phẳng liên thông có n đỉnh, p cạnh và d miền thì ta có hệ thức: n – p + d = 2. Hệ thức: n – p + d = 2 được gọi là “hệ thức Euler cho hình đa diện”. Mỗi hình đa diện có thể coi là một đồ thị phẳng.  Hệ quả: Trong một đồ thị phẳng liên thông tùy ý , luôn tồn tại ít nhất một đỉnh có bậc không vượt quá 5. 2. Tô màu đồ thị Bài toán mở đầu: Bài toán được đặt ra xuất phát từ bài toán tô màu bản đồ như sau: - Ta coi mỗi bản đồ là một đồ thị phẳng và hai miền có chung nhau một đường biên gọi là hai miền kề nhau (hai miền chỉ có chung nhau một điểm biên gọi là hai miền không kề nhau). Một bản đồ thường được tô màu mà hai miền kề nhau được tô màu khác nhau). Và bài toán đặt ra là: xác định số màu tối thiểu cần đ ể tô một bản đồ sao cho hai miền kề nhau thì có màu khác nhau). B Hình 6 A C - Mỗi bản đồ trên một mặt phẳng có thể biều diễn Eằng một đồ thị, trong đó b mỗi miền của bản đồ được biểu diễn bằng một đỉnh, các cạnh nối hai đỉnh nếu các D F miền được biểu diễn bằng hai đỉnh này là kề nhau. Đồ thị nhận được bằng cách này G gọi là đồ thị đối ngẫu của bản đồ đang xét. GVBM: Dư Quang Anh Huy Trang 13
Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt  Định nghĩa: Tô màu một đơn đồ thị là việc gán màu cho các đỉnh của nó sao cho hai đỉnh liền kề có màu khác nhau. Mỗi đồ thị có thể có nhiều cách tô màu khác nhau. - Sắc màu hay sắc số (Chromatic number) của một đồ thị G là số màu tối thiểu cần thiết để tô màu G. Kí hiệu là: χ (G). 3. Một số định lí: - Định lí 1: Mọi đơn đồ thị đầy đủ Kn đều có χ (Kn) = n. Ví dụ: ở hình 6 có χ (K3) = 3 - Định lí 2: Mọi chu trình độ dài lẻ đều có sắc số là 3. - Định lí 3: Nếu G’ là con của đồ thị G thì χ (G) ≥ χ (G’). Nếu dùng k màu để tô màu G thì không cần quan tâm tới những đỉnh có bậc nhỏ hơn k. - Định lí 4: Một đơn đồ thị G = (X, E) có thể tô bằng 2 màu khi và chỉ khi nó không có chu trình độ dài lẻ - Định lí 5 (Định lí 5 màu của Kempe – Heawood): Mọi đồ thị phẳng đều có thể tô đúng 5 màu. - Định lí 6 (Định lí 4 màu hay định lí Appel – Haken, 1976): Mọi đồ thì phẳng đều có sắc số không lớn hơn 4. Định lí này là định lí đầu tiên được chứng minh với sự hỗ trợ của máy tính. *Mệnh đề 1. Mệnh đề 1. Trong mọi đồ thị với n 2 đỉnh, có ít nhất hai đỉnh có cùng bậc. Chứng minh: Do đồ thị là đơn nên bậc của các đỉnh nằm trong tập {0,1,…, n-1. Tuy nhiên không thể có hai đỉnh A, B sao cho deg( A) = 0 , deg( B) = n − 1 được. Nói cách khác, bậc các đỉnh nằm trong {0, 1, …, n-2} hoặc {1, 2, …n-1}. Nguyện lí Dirichlet giúp ta kết thúc chứng minh. 2.Mệnh đề 2. Cho G= (V, E) là một đồ thị liên thông. Thế thì E V −1 Chứng minh: Ta chứng minh bằng quy nạp theo số đỉnh n của đồ thị. Trường hợp n= 1, 2 là tầm thường. Gọi N là một số nguyên và giả sử rằng mọi đồ thị liên thông N đỉnh đều có ít nhất N- 1 cạnh. Gọi G= (V, E) là một đồ thị N+ 1 đỉnh. Lưu ý rằng do G liên thông nên bậc của mỗi đỉnh ≥ 1 Nếu bậc của mỗi đỉnh của G đều 2 thì theo công thức quen thuộc liên kết các bậc và số cạnh, ta có 2E = deg ( A ) 2n A V Từ đó suy ra E n Giả sử có một đỉnh của G có bậc 1. Gọi A là một đỉnh như vậy và gọi G’ là đồ thị được tạo thành từ G bằng cách loại bỏ đỉnh A và cạnh duy nhất cả G với một đầu mút A. Dễ thấy G’ cũng là một đồ thị liên thông với N đỉnh và E − 1 cạnh. Áp dụng giả thiết quy nạp cho G’ ta có điều cần chứng minh GVBM: Dư Quang Anh Huy Trang 14
Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt . 3. Mệnh đề 3. Mọi đồ thị liên thông đều có thể được xây dựng bằng cách thêm vào một số cạnh vào một cây có cùng số đỉnh với đồ thị đã cho, và một cây như vậy được gọi là cây bao trùm của đồ thị. Chứng minh : Ta quy nạp theo số chu trình c của đồ thị. Nếu c = 0, đồ t hị là một cây và ta không có gì phải chứng minh. Già sử kết quả cần chứng minh là đúng với c ≥ 0. Giả sử G là một đồ thị có c + 1 chu trình. Gọi G’ là đồ thị cảm sinh từ G b ằng cách gi ữ nguyên các đỉnh và bỏ đi đúng một cạnh thuộc một chu trình nào đó, chẳng hạn cạnh (A1, A2) của chu trình A1, A2,..., Ak, A1. Chú ý rằng mọi chu trình của G’ đều là một chu trình của G và do ta đã phá đi ít nhất một chu trình của G, số chu trình c ủa G’ vì thế ≤ c. Ngoài ra, G’ vẫn còn liên thông (nếu cần đi từ A 1 đến A2 chỉ cần đi vòng A1, Ak,..., A3, A2). Theo giả thiết, có thể xây dựng G’ từ một cây nào đó. Sau đó chỉ c ần thêm vào G’ cạnh A1, A2 để thu được G. Nhận xét. Ta biết rằng số cạnh của một cây bằng số đỉnh trừ đi 1. Như vậy, để xây dựng lại một đồ thị G= (V,E), cần thêm vào E + 1 − V cạnh vào một cây bao trùm G. 4. Mênh đề 4 (Koenig). Môt đồ thị là hai phân khi và chỉ khi không có chu ̣ ̣ ̀ trinh độ dai le. ̀ ̀ ̉ Chứng minh : - (a) Giả sử G là môt đồ thị hai phân. ̣ ̀ + Rõ rang môt chu trinh sẽ đi qua cac đinh cua môt tâp đinh đôc lâp môt cach ̀ ̣ ̀ ́ ̉ ̉ ̣ ̣ ̉ ̣ ̣ ̣ ́ luân phiên và do đó chỉ có thể quay lai đinh đâu tiên sau môt số chăn lân. Noi cach ̣ ̉ ̀ ̣ ̃ ̀ ́ ́ khac, moi chu trinh (nêu co) cua G phai có độ dai chăn. ́ ̣ ̀ ́ ́ ̉ ̉ ̀ ̃ - (b) Giả sử G không có chu trinh độ dai lẻ. ̀ ̀ + Ta sẽ xây dựng cụ thể môt phân đôi cua G băng cach đưa vao ham khoang ̣ ̉ ̀ ́ ̀ ̀ ̉ cach. Dễ thây có thể giả thiêt G liên thông, nêu không chỉ cân tiên hanh cho từng thanh ́ ́ ́ ́ ̀ ́ ̀ ̀ phân liên thông rôi ghep cac phân đôi lai.Goi A là môt đinh bât kỳ cua G (liên thông). ̀ ̀ ́ ́ ̣ ̣ ̣ ̉ ́ ̉ + Với môi đinh B cua G ký hiêu d(A,B) là khoang cach giữa hai đinh A và B, ̃ ̉ ̉ ̣ ̉ ́ ̉ được đinh nghia như là độ dai ngăn nhât trong cac độ dai cac đường đi từ A đên B ̣ ̃ ̀ ́ ́ ́ ̀ ́ ́ (như d(A,A) = 0). Chú ý răng giả thiêt G liên thông đam bao cho viêc đinh nghia nay là ̀ ́ ̉ ̉ ̣ ̣ ̃ ̀ ́ tôt. + Goi X, Y tương ứng là tâp cac đinh có độ dai tới A là chăn, le. Hiên nhiên X, Y ̣ ̣ ́ ̉ ̀ ̃ ̉ ̉ tao thanh môt phân hoach cua tâp đinh cua G. hơn nữa môi tâp X, Y là môt tâp đinh đôc ̣ ̀ ̣ ̣ ̉ ̣ ̉ ̉ ̃ ̣ ̣ ̣ ̉ ̣ lâp. Chăng han, giả sử B,C ̣ ̉ ̣ ∈ X sao cho (B,C) là môt canh cua G. Thế thì băng cach nôi ̣ ̣ ̉ ̀ ́ ́ cac đường đi độ dai ngăn nhât từ A đên B, rôi canh (B,C), đường đi có độ dai ngăn ́ ̀ ́ ́ ́ ̀ ̣ ̀ ́ nhât từ C tới A (có thể cân bỏ môt số canh trung nhau và đinh lăp) ta sẽ thu được môt ́ ̀ ̣ ̣ ̀ ̉ ̣ ̣ chu trinh có độ dai le, mâu thuân với giả thiêt ban đâu. ̀ ̀ ̉ ̃ ́ ̀ GVBM: Dư Quang Anh Huy Trang 15
Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt Nhân xet. Ta sẽ đưa ra môt đăc trưng khac cua cac đồ thị 2 phân thông qua ̣ ́ ̣ ̣ ́ ̉ ́ ̀ số săc tô. ́ ́ Hệ qua. Moi cây là môt đồ thị hai phân. ̉ ̣ ̣ ̀ BÀI TẬP THAM KHẢO Bài 1. Chứng minh răng trong môt đồ thị G tuy ý tông tât cả cac bâc cua cac ̀ ̣ ̀ ̉ ́ ́ ̣ ̉ ́ đinh trong G luôn băng hai lân số canh cua no. ̉ ̀ ̀ ̣ ̉ ́ Giai : Ta có đồ thị G = (V,T) ̉ Ta cân chứng minh : ̀ = 2|E| ( Vì môi canh nôi chinh xac hai canh ̃ ̣ ́ ́ ́ ̣ cua đồ thi) ̉ ̣ → đpcm. Bài 2. Chứng minh răng trong môt đồ thị đơn vô hướng tuy ý luôn tôn tai hai ̀ ̣ ̀ ̀ ̣ đinh có bâc băng nhau. ̉ ̣ ̀ Giai : Giả sử đồ thị G có n đinh vây bâc cua cac đinh chỉ có thể rơi vao môt ̉ ̉ ̣ ̣ ̉ ́ ̉ ̀ ̣ trong hai trường hợp: TH1:{0,1,2,…,n-2} TH2:{1,2,3,…,n-1} Ap dung nguyên lí Dirichlet có n đinh nhưng chỉ có n-1 trường hợp. ́ ̣ ̉ → Tôn tai hai đinh có bâc băng nhau. ̀ ̣ ̉ ̣ ̀ Bài 3. Với những giá trị nguyên dương n nao thì tôn tai đồ thị đêu đơn bâc ba ̀ ̀ ̣ ̀ ̣ có n đinh. ̉ Giai : Theo đề bai ta có : cac bâc cua đinh trong đồ thị đơn đêu là 3 mà có n ̉ ̀ ́ ̣ ̉ ̉ ̀ ̉ đinh → Tông bâc cua đồ thị đơn là 3n. ̉ ̣ ̉ Mà ta có : 3n = 2m (với n , m nguyên dương và n là số canh cua đồ thị đơn ̣ ̉ (n > 3)). ↔ n=m → n là môt số chăn. ̣ ̃ Bài 4. Lập sơ đồ quan hệ giao nhau của các hình tròn trong hình sau đây : 2 3 4 1 5 6 GVBM: Dư Quang Anh Huy Trang 16
Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt Giải 2 3 1 4 6 5 Bài 5. Trên một bàn cờ 3x 3 ô vuông có 2 con mã trắng đứng ở hai góc bên trên và 2 con mã đen đứng ở hai góc bên dưới. Hỏi rằng có thể đổi chỗ 2 con mã đen lên vị trí 2 con mã trắng bằng một cách tương ứng: con mã đen góc trái lên vị trí trên góc trái và con mã đen vị trí bên phải sẽ lên góc bên trên vị trí bên phải còn 2 con mã trắng thì xuống vị trí tương ứng ở dưới hay không? Biết rằng chỉ được dẫn các con mã đi theo luật đi được quy định của bàn cờ mà thôi. Giải - Nếu chúng ta đem biểu diễn thành gragh tương ứng với đỉnh là các ô vuông, còn hai đỉnh được nối bởi một cạnh nếu như hai ô tương ứng với chúng có thể đi tới nhau bởi một bước đi của một con mã. Graph thu được được biểu diễn trong hình bên. Dễ thấy khi đó không di chuyển các con mã để cho chúng có thể đổi chỗ cho nhau sao cho 2 con mã đen lên vị trí 2 con mã trắng bằng một cách tương ứng: con mã đen góc trái lên vị trí trên góc trái và con mã đen vị trí bên phải sẽ lên góc bên trên vị trí bên phải còn 2 con mã trắng thì xuống vị trí tương ứng ở bên dưới dược. Vì nếu đổi được như vậy, thì trên graph GVBM: Dư Quang Anh Huy Trang 17
Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt tương ứng, các con mã phải đi qua đầu nhau là điều không cho phép (một b ước đi bình thường của con mã tương ứng với một phép dịch đi bước một của con mã trên graph tương ứng, và đặc biệt chúng không được ăn nhau). BÀI TẬP ĐỀ NGHỊ Bài 1. Có 20 đội bóng tham gia thi đấu, thể lệ cuộc thi là bất kì đội bóng nào cũng chỉ gặp nhau đúng một lần. Hỏi phải tổ chức bao nhiêu trận đấu? Gợi ý: ta coi mỗi đội bóng là một đỉnh do hai đội nào cũng chỉ gặp nhau một lần nên ta được đồ thị đầy đủ với 20 đỉnh. Mỗi đỉnh có bậc là 19 từ đó suy ra tổng số bậc (20 ×19) sau đó tính tống số cạnh cũng chính là số trận đấu phải tổ chức theo p ( p − 1) công thức: (cạnh) với p là số đỉnh. 2 Bài 2. Một nhóm gồm 5 thành viên trong đó mỗi bộ 3 đều có 2 người quen nhau và 2 không quen nhau. Chứng minh rằng có thể xếp cả nhóm ngồi xung quanh một bàn tròn để mỗi thành viên sẽ ngồi giữa hai người mà thành viên có quen nhau? Gợi ý: Bài toán chứa 2 mối quan hệ là quen và không quen ta coi 5 người là 5 đỉnh A, B, C, D, E của một đồ thị: 2 người quen nhau tương ứng với cạnh nối 2 đỉnh tô màu xanh còn 2 người không quen nhau tô màu đỏ. Xét đỉnh A bất kì, A có bậc là 4 suy ra A là đầu mút của 4 cạnh và có ít nhất hai cạnh cùng loại, giả sử AB, AC là màu xanh thì BC là màu đỏ. Nếu AD màu xanh thì DC sẽ là màu đỏ còn nếu BD màu xanh thì tam giác ABD có 3 cạnh màu xanh, nếu BD màu đỏ thì tam giác BCD có 3 cạnh màu đỏ (vô lí) => AD màu đỏ. Giả sử AB, AC là màu xanh thì BC là màu đỏ và BD màu đỏ. Khi đó nếu DC màu xanh EC, EA, EB, ED đều nét đỏ (vô lí). Vậy BC màu đỏ, lại có AD màu đỏ, BC màu đỏ suy ra CE, DE màu xanh. Vậy ta được cách xếp 5 người thành một vòng tròn. A B E C D Bài 3. Một lớp 10 chuyên Toán có 6 bạn học sinh, trong buổi họp tổ đầu năm bạn tổ trưởng đã phát hiện ra điều thú vị rằng mỗi bạn trong tổ quen đúng với 3 bạn khác ngay lập tức Chi đứng lên bác bỏ. Hỏi ý kiến của ai đúng? Gợi ý: Mối quan hệ quen nhau ta có thể tô màu xanh còn không quen nhau ta tô màu đỏ. Một bạn trong tổ là 1 đỉnh sẽ nối với 5 cạnh . Theo Dirichle, thì s ẽ có ít nhất 3 cạnh cùng màu ( có thể màu xanh hay màu đỏ). Từ đó rút ra kết luận…. Bài 4. Hãy vẽ một graph biểu diễn quan hệ quen biết của 5 người sao cho không có 3 người nào đôi một quen nhau hoặc đôi một không quen nhau? GVBM: Dư Quang Anh Huy Trang 18
Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt Gợi ý:Graph có 5 đỉnh là 5 đỉnh của ngũ giác đều và cạnh nối 2 đ ỉnh bất kì là cạnh của ngũ giác đều này thỏa mãn yều cầu đề bài. Thật vậy, nếu ta lấy 3 đỉnh tùy ý thì luôn có 2 đỉnh kề nhau và có 2 trong số chúng không kề nhau. MỤC LỤC Trang Lời mở đầu ……………………………………………………..…………...…...… 01 ĐỒ THỊ TRONG ĐỜI SỐNG ……..………..……………………………….….. 03 KHÁI NIỆM CƠ BẢN VỀ ĐỒ THỊ ……………………………………………. 05 MỘT SỐ ĐỒ THỊ ĐẶC BIỆT ……………………………………………………09 1. Đồ thị con …………………………………………………………………… 07 2. Đường đi …………………………………………………………………….. 07 3. Chu trình …………………………………………………………………….. 08 ĐƯỜNG ĐI EULER VÀ ĐỒ THỊ HAMILTON……………………………….. 10 1. Đường đi Euler ………………………………………………………………. 10 2. Đồ thị Hamilton ……………………………………………………………… 10 CÁC MỆNH ĐỀ MỞ RỘNG VÀ TƯ LIỆU THAM KHẢO ………………….. 10 * Tư liệu tham khảo ……………………………………………………………. 10 1. Định nghĩa và các tính chất cơ bản về cây ………………………………....... 10 2. Cây khung ………………………………………………………………...…. 11 3. Cây có gốc ………………………………………………………………..…. 11 ĐỒ THỊ PHẲNG VÀ TÔ MÀU ĐỒ THỊ ………………………………………. 12 1. Đồ thị phẳng ………………………………………………………………… 12 2. Tô màu đồ thị ……………………………………………………………….. 13 3. Một số định lí ………………………………………………………………... 13 * Mệnh đề …………………………………………………………………….... 14 1. Mệnh đề 1 …………………………………………………………………… 14 2. Mệnh đề 2 …………………………………………………………………… 14 3. Mệnh đề 3 ……………………………………………………………………. 15 BÀI TẬP THAM KHẢO ………………………………………………………... 16 BÀI TẬP ĐỀ NGHỊ ……………………………………………………………... 18 GVBM: Dư Quang Anh Huy Trang 19
Nhóm 1: Chuyên đề “Lý thuyết Graph và ứng dụng” Trường THPT Thốt Nốt GVBM: Dư Quang Anh Huy Trang 20