Lý thuyết đồ thị và ứng dụng

Bài viết "Lý thuyết đồ thị và ứng dụng" đề cập đến những khái niệm và kết quả cơ bản nhất, nhằm giúp người đọc có một cái nhìn tổng quan, đồng thời trình bày một số kỹ thuật và ứng dụng tiêu biểu của Lý thuyết đồ thị trong toán học phổ thông. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Lý thuyết đồ thị và ứng dụng Hội thảo khoa học, Hưng Yên 25-26/02/2017 LÝ THUYẾT ĐỒ THỊ VÀ ỨNG DỤNG Hoàng Phương Anh THPT Chuyên Hưng Yên Tóm tắt nội dung Lý thuyết đồ thị là một ngành toán học hiện đại, còn rất trẻ so với lịch sử phát triển hàng nghìn năm của những chuyên ngành khác, nhưng lại có ứng dụng quan trọng trong nhiều ngành khoa học kỹ thuật hiện đại như: tin học, công nghệ thông tin, vật lý, hóa học, sinh học,... Trong khuôn khổ hạn hẹp, không thể trình bày hết được kiến thức của cả một chuyên ngành, nên bài viết này chỉ đề cập đến những khái niệm và kết quả cơ bản nhất, nhằm giúp người đọc có một cái nhìn tổng quan, đồng thời trình bày một số kỹ thuật và ứng dụng tiêu biểu của Lý thuyết đồ thị trong toán học phổ thông. 1 Cơ sở lý thuyết 1.1 Khái niệm Định nghĩa 1. Một đồ thị G = (V, E) được hiểu là một bộ hai tập hợp: tập hợp đỉnh V và tập hợp cạnh E nối các đỉnh này với nhau. Nếu mỗi cạnh của đồ thị là đường nối duy nhất giữa một cặp hai đỉnh phân biệt, ta gọi đó là đồ thị đơn. Một đồ thị được gọi là đồ thị vô hướng nếu tất cả các cạnh của nó đều là cạnh vô hướng. Một đồ thị được gọi là đồ thị có hướng nếu tất cả các cạnh của nó đều là cạnh có hướng. Trong khuôn khổ bài viết này, chúng ta chỉ nghiên cứu các đồ thị đơn vô hướng hữu hạn đỉnh. Một số thuật ngữ khác 1. Hai đỉnh v, w được gọi là kề nhau nếu có một cạnh nối v và w. 2. Bậc của một đỉnh là số cạnh xuất phát từ đỉnh đó. Một đỉnh được gọi là đỉnh cô lập nếu nó có bậc bằng 0. Đỉnh có bậc bằng 1 gọi là đỉnh treo. 3. Một dãy cạnh kế tiếp ei = (vi , vi + 1) với i = 1, 2, ..., m − 1 được gọi là một đường đi nếu các đỉnh v1 , v2 , ...vm đôi một khác nhau. v1 được gọi là đỉnh đầu và vm được gọi là đỉnh cuối của đường đi đó. Số các cạnh của đường đi được gọi là độ dài của đường đi. 79 Hội thảo khoa học, Hưng Yên 25-26/02/2017 4. Một dãy cạnh dạng ei = (vi , vi + 1) với i = 1, 2, ..., m được gọi là một chu trình nếu các đỉnh v1 , v2 , ..., vm đôi một khác nhau và vm+1 ≡ v1 . Độ dài của chu trình là số cạnh của chu trình đó. 5. Một đồ thị được gọi là liên thông nếu giữa hai đỉnh bất kỳ của nó luôn tồn tại một đường đi nối hai đỉnh đó với nhau. 6. Cho G = (V, E) là một đồ thị. Đồ thị bù G của G là một đồ thị với cùng tập đỉnh như G và E( G ) = {e ∈ / E( G )}, nghĩa là G chứa đúng các cạnh không thuộc G. 7. Đồ thị đầy đủ n đỉnh, ký hiệu là Kn , là một đồ thị đơn vô hướng có n đỉnh và giữa hai đỉnh bất kỳ của nó có đúng một cạnh nối. 8. Đồ thị lưỡng phân là đồ thị G = (V, E) mà tập đỉnh V có thể phân hoạch thành 2 tập hợp V1 ∪ V2 sao cho tập cạnh E chỉ gồm các cạnh nối 2 đỉnh không cùng một tập hợp. 9. Một cây là một đồ thị liên thông vô hướng với ít nhất một đỉnh và không có chu trình. 10. Bụi là một đồ thị vô hướng không có chu trình. 11. Những đồ thị có thể biểu diễn được trên mặt phẳng sao cho không có 2 cạnh được biểu diễn nào cắt nhau được gọi là đồ thị phẳng. 12. Cho một đồ thị G = (V, E). Khi đó một đồ thị G 0 = (V 0 , E0 ) được gọi là đồ thị con của G nếu V 0 ⊂ V, E0 ⊂ E. Đồ thị con G 0 = (V 0 , E0 ) được gọi là đồ thị thành phần nếu như mọi cạnh của G nối 2 đỉnh của G 0 cũng là cạnh của G 0 . 13. Đường đi Hamilton là đường đi chứa mọi đỉnh của đồ thị. Chu trình Hamilton là chu trình chứa mọi đỉnh của đồ thị. 14. Đường đi Euler là đường đi đi qua mỗi cạnh đúng một lần. Chu trình Euler là chu trình đi qua mỗi cạnh đúng một lần. Đồ thị Euler là đồ thị có chu trình Euler. 15. Sắc số của đồ thị là số nhỏ nhất các màu có thể dùng để tô các đỉnh của đồ thị sao cho không có hai đỉnh kề nhau nào được tô cùng một màu. 1.2 Tính chất Trước hết, tôi xin trình bày một số định lý cơ bản mà các bạn học sinh được phép sử dụng như kết quả sách giáo khoa trong kỳ thi Học sinh giỏi Quốc gia VMC. Đây đều là các kết quả có được qua các bước chứng minh đơn giản. Định lý 1. Tổng số bậc của tất cả các đỉnh trong đồ thị gấp hai lần số cạnh của đồ thị ấy. Từ đó suy ra, số đỉnh bậc lẻ của một đồ thị luôn là số chẵn. Định lý 2. Trong đồ thị đơn vô hướng n đỉnh (n ∈ Z, n ≥ 2), tồn tại ít nhất 2 đỉnh có cùng bậc. Định lý 3. Nếu đồ thị G đơn vô hướng n đỉnh (n ∈ Z, n ≥ 2) có đúng hai đỉnh cùng bậc thì G phải có đúng một đỉnh bậc 0 hoặc có đúng một đỉnh bậc n − 1. 80 Hội thảo khoa học, Hưng Yên 25-26/02/2017 Định lý 4. Mỗi đồ thị đơn vô hướng hữu hạn không liên thông đều bị phân chia một cách ...