Tài liệu Luận văn đồ thị euler và đồ thị hamilton cùng một số ứng dụng

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 ——————————o0o—————————— LƯU THỊ THÊM ĐỒ THỊ EULER VÀ ĐỒ THỊ HAMILTON CÙNG MỘT SỐ ỨNG DỤNG Chuyên ngành: Toán ứng dụng Mã số: 8 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học TS. Trần Minh Tước HÀ NỘI, 2018 Lời cảm ơn Sau một thời gian cố gắng, nỗ lực học tập và nghiên cứu, đến nay tôi đã hoàn thành luận văn tốt nghiệp thạc sĩ của mình. Để có được kết quả này, tôi xin bày tỏ lòng biết ơn sâu sắc và lời cảm ơn chân thành nhất đến thầy giáo, TS. Trần Minh Tước, người đã định hướng nghiên cứu cho tôi trong suốt thời gian thực hiện luận văn của mình. Tôi xin chân thành cảm ơn sự giúp đỡ quý báu của các thầy cô giáo trong bộ môn Toán ứng dụng nói riêng và khoa Toán, trường Đại học Sư phạm Hà Nội 2 nói chung. Xin cảm ơn những người thân trong gia đình và tất cả những người bạn thân yêu đã hết sức thông cảm, chia sẻ và tạo điều kiện tốt nhất cho tôi để tôi có thể học tập, nghiên cứu và thực hiện luận văn của mình. Tôi rất mong nhận được sự đóng góp ý kiến của các thầy cô và các bạn để luận văn được hoàn thiện hơn. Tôi xin chân thành cảm ơn! Hà Nội, tháng 11 năm 2018 Tác giả Lưu Thị Thêm 1 Lời cam đoan Tôi xin cam đoan luận văn này là công trình nghiên cứu của riêng tôi, được thực hiện dưới sự hướng dẫn của thầy giáo TS. Trần Minh Tước. Trong quá trình nghiên cứu, tôi đã kế thừa thành quả khoa học của các nhà khoa học với sự trân trọng và biết ơn. Các kết quả trích dẫn trong luận văn này đã được chỉ rõ nguồn gốc. Hà Nội, tháng 11 năm 2018 Tác giả Lưu Thị Thêm 2 Mục lục Mở đầu 5 Chương 1 Kiến thức cơ sở 1.1 Đồ thị và phân loại đồ thị . . . . . . . . 1.1.1 Đồ thị có hướng . . . . . . . . . . 1.1.2 Đồ thị vô hướng . . . . . . . . . . 1.1.3 Đa đồ thị có hướng và đa đồ thị vô 1.1.4 Đồ thị có trọng số . . . . . . . . . 1.2 Đồ thị con và một số vấn đề liên quan . . 1.3 Bậc của đỉnh . . . . . . . . . . . . . . . 1.4 Chu trình, mạch . . . . . . . . . . . . . 1.5 Tính liên thông của đồ thị . . . . . . . . 1.6 Cây khung của đồ thị . . . . . . . . . . . 1.7 Phương pháp duyệt đồ thị . . . . . . . . 1.8 Luồng trong mạng . . . . . . . . . . . . 1.9 Ghép cặp đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . hướng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chương 2 Vết Euler, mạch Euler và đồ thị Euler 2.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Định lí về điều kiện cần và đủ để một đồ thị là đồ thị Euler 2.3 Thuật toán tìm các mạch Euler . . . . . . . . . . . . . . . 2.3.1 Đối với đồ thị vô hướng . . . . . . . . . . . . . . . . 2.3.2 Đối với đồ thị có hướng . . . . . . . . . . . . . . . . 2.4 Ứng dụng đồ thị Euler giải bài toán người đưa thư . . . . . 2.4.1 Thuật toán tìm lời giải cho bài toán người đưa thư trong đồ thị vô hướng có trọng số không là đồ thị Euler[[2]] . . . . . . . . . . . . . . . . . . . . . . . . 3 . . . . . . . . . . . . . 7 7 7 8 9 10 11 12 12 13 13 14 14 15 . . . . . . 16 16 18 20 20 21 25 . 25 Luận văn thạc sĩ 2.4.2 Thuật toán tìm lời giải cho bài toán người đưa thư trong đồ thị có hướng có trọng số không là đồ thị Euler[[2]] . . . . . . . . . . . . . . . . . . . . . . . . . 28 Chương 3 3.1 3.2 3.3 3.4 Đường đi Hamilton, chu trình Hamilton và đồ thị Hamilton Định nghĩa đồ thị Hamilton . . . . . . . . . . . . . . . . . . Một số định lí cơ bản . . . . . . . . . . . . . . . . . . . . . . Tìm các chu trình Hamilton bằng phương pháp nhân ma trận Ứng dụng: Thuật toán xấp xỉ cho bài toán tìm chu trình của người bán hàng có trọng số tối thiểu trong đồ thị có trọng số 3.4.1 Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 Xây dựng thuật toán xấp xỉ tìm chu trình Hamilton có trọng số tối thiểu của đồ thị có trọng số. . . . . . . . . 3.4.3 Thuật toán cải tiến . . . . . . . . . . . . . . . . . . . 33 33 35 40 45 45 48 50 Kết luận 53 Tài liệu tham khảo 54 Lưu Thị Thêm 4 K20-Toán ứng dụng Mở đầu 1. Lí do chọn đề tài Năm 1736 có thể coi là năm khai sinh của lý thuyết đồ thị với việc công bố lời giải bài toán “Bảy cây cầu ở Königsberg” của nhà toán học lỗi lạc người Thụy Sĩ Leonhard Euler (1707 - 1783). Từ đó có khái niệm và những nghiên cứu về một loại đồ thị được gọi là đồ thị Euler. Năm 1858, nhà toán học Hamilton (1805 - 1865) đã đưa ra trò chơi “Đi vòng quanh thế giới”, mở ra một loạt các nghiên cứu cho một loại đồ thị là đồ thị Hamilton. Ra đời muộn hơn một số lĩnh vực toán khác nhưng lý thuyết đồ thị đang có rất nhiều các ứng dụng trong thực tế. Khi nghiên cứu về lý thuyết đồ thị thì hai lớp đồ thị trên luôn luôn được nhắc đến và tạo những hứng thú cho việc tìm hiểu, phát triển những ứng dụng. Những phép chứng minh, những thuật toán của lý thuyết đồ thị đã tạo cảm hứng cho không chỉ những người nghiên cứu toán học mà còn cho cả những lập trình viên công nghệ thông tin. Đã có rất nhiều những nghiên cứu về hai loại đồ thị này và cũng có rất nhiều định lý, các mối liên hệ và những ứng dụng đã được tìm thấy. Được sự gợi ý của giảng viên hướng dẫn là T.S Trần Minh Tước và với mong muốn có một sự hiểu biết đầy đủ hơn về mối liên hệ giữa đồ thị Euler, đồ thị Hamilton với một số các khái niệm khác của lý thuyết đồ thị và một số ứng dụng của nó, tôi đã chọn đề tài: “Đồ thị Euler và đồ thị Hamilton cùng một số ứng dụng”. 2. Mục đích và nghiên cứu Nghiên cứu về đồ thị Euler, đồ thị Hamilton và mối liên hệ của chúng với một số khái niệm khác của lý thuyết đồ thị cùng một số ứng dụng của hai lớp đồ thị này. 5 Luận văn thạc sĩ 3. Nhiệm vụ nghiên cứu • Tìm hiểu các tính chất của mạch Euler, chu trình Hamilton trong đồ thị. • Tìm hiểu mối liên hệ của đồ thị Euler, đồ thị Hamilton với các khái niệm khác để nghiên cứu các thuật toán liên quan tới hai loại đồ thị này. • Tìm hiểu về một số ứng dụng của hai loại đồ thị trên. 4. Đối tượng và phạm vi nghiên cứu • Đồ thị có hướng và đồ thị vô hướng. • Mạch Euler, đồ thị Euler. • Chu trình Hamilton, đồ thị Hamilton. 5. Phương pháp nghiên cứu Chúng tôi sử dụng chủ yếu việc nghiên cứu lý thuyết, vận dụng các luật logic trong toán học, cùng với một số công cụ của tổ hợp và tối ưu rời rạc. Lưu Thị Thêm 6 K20-Toán ứng dụng Chương 1 Kiến thức cơ sở Trong chương này, các khái niệm và kết quả tôi tham khảo từ tài liệu "Lý thuyết Tổ hợp và Đồ thị", Nxb ĐHQG Hà Nội, 2005 của GS. TS. Ngô Đắc Tân. 1.1 Đồ thị và phân loại đồ thị Khái niệm đồ thị xuất hiện từ nhiều lĩnh vực khác nhau trong cuộc sống. Trong mỗi lĩnh vực riêng của mình, người ta cần tới một kiểu đồ thị nào đó. Vì vậy mà cũng xuất hiện nhiều loại đồ thị khác nhau. Song tựu chung lại ta có thể phân loại chúng theo bốn dạng chính sau đây: đồ thị có hướng, đồ thị vô hướng, đa đồ thị có hướng, đa đồ thị vô hướng. Ngoài ra, tùy theo từng mục đích mà ta có thể gắn trọng số cho các đỉnh hoặc các cạnh của đồ thị. 1.1.1 Đồ thị có hướng Một đồ thị có hướng G là một cặp có thứ tự G = (V, E), ở đây V là một tập, còn E là một tập con của tích đề các V × V , tức E là một quan hệ hai ngôi trên V . Các phần tử của V được gọi là các đỉnh, còn các phần tử của E được gọi là các cung của đồ thị có hướng G. Cụ thể hơn, nếu (a, b) ∈ E thì (a, b) được gọi là cung của G với đỉnh đầu là a, đỉnh cuối là b và có hướng đi từ a tới b. Ví dụ 1.1.1. Cho G = (V, E) với V = {a, b, c, d, e, f } và E = {(a, a), (a, b), (b, d), (d, b), (c, e), (e, a)} . Khi đó G là đồ thị có hướng được biểu diễn bằng hình (1.1). 7 Luận văn thạc sĩ Hình 1.1: Ví dụ một đồ thị có hướng Giả sử G = (V, E) là một đồ thị có hướng. Nếu (a, b) ∈ E thì các đỉnh a và b được gọi là liên thuộc với cung (a, b). Khi đó a và b cũng được gọi là kề nhau. Hai cung bất kì của G được gọi là kề nhau nếu chúng có đỉnh chung. Cung dạng (a, a) với a ∈ V được gọi là khuyên. Đỉnh không liên thuộc với một cung nào được gọi là đỉnh cô lập. Số các đỉnh của G, tức là | V |, được gọi là cấp của G. Số các cung của G, tức là | E |, được gọi là cỡ của G. 1.1.2 Đồ thị vô hướng Một đồ thị vô hướng G là một cặp có thứ tự G = (V, E), ở đây V là một tập, còn E là tập với các phần tử là các đa tập lực lượng 2 trên V , trong đó đa tập là khái niệm mở rộng của khái niệm tập hợp. Trong một đa tập, mỗi phần tử có thể xuất hiện nhiều hơn một lần. Tổng số tất cả các lần xuất hiện của các phần tử được gọi là lực lượng của đa tập. Các phần tử của V cũng được gọi là các đỉnh, còn các phần tử của E được gọi là các cạnh của đồ thị vô hướng G. Nếu e = {a, b} là một cạnh của G thì a và b được gọi là các đỉnh đầu mút của cạnh e hay các đỉnh liên thuộc với e. Ta cũng thường kí hiệu cạnh e = {a, b} ngắn gọn là ab. Ví dụ 1.1.2. Cho G = (V, E) với V = {a, b, c, d} và E = {{a, a} , {a, b} , {b, d} , {b, c} , {c, d}}. Khi đó G là đồ thị vô hướng và được biểu diễn bằng hình (1.2). Lưu Thị Thêm 8 K20-Toán ứng dụng Luận văn thạc sĩ Hình 1.2: Ví dụ một đồ thị vô hướng 1.1.3 Đa đồ thị có hướng và đa đồ thị vô hướng. Một đa đồ thị có hướng G là một cặp có thứ tự G = (V, E) ở đây V là một tập, còn E là một đa tập với các phần tử đều thuộc tích Đề các V × V . Đa đồ thị có hướng cũng được biểu diễn trên mặt phẳng tương tự như đồ thị có hướng, trong có các cung có cùng đỉnh đầu và đỉnh cuối phải được biểu diễn bằng các đường cong khác nhau. Tương tự, một đa đồ thị vô hướng G là một cặp có thứ tự G = (V, E), ở đây V là một tập, còn E là một đa tập với các phần tử đều là đa tập lực lượng 2 trên V . Trong biểu diễn trên mặt phẳng của đa đồ thị vô hướng, các cạnh khác nhau nhưng có các đỉnh đầu mút như nhau phải được biểu diễn bằng các đường cong khác nhau. Ví dụ 1.1.3. Đồ thị G1 = (V, E1 ) với V = {a, b, c, d} và E1 = {(a, d), (a, d), (d, a), (a, c), (c, a), (b, a), (c, b), (b, c), (d, c)} là một đa đồ thị có hướng: Lưu Thị Thêm 9 K20-Toán ứng dụng Luận văn thạc sĩ Ví dụ 1.1.4. Đồ thị G2 = (V, E2 ) với V = {a, b, c, d} và E2 = {{a, d} , {a, d} , {d, a} , {c, d} , {a, c} , {c, a} , {b, a} , {c, b} , {c, b}} là một đa đồ thị vô hướng: 1.1.4 Đồ thị có trọng số Đồ thị G = (V, E) được gọi là đồ thị có trọng số nếu ít nhất một trong hai hàm f : V → WV và g : E → WE được xác định, ở đây WV và WE là các tập nào đấy. Các phần tử của WV và WE có thể chỉ đơn thuần là các dữ liệu nhưng thường thì có một ý nghĩa định lượng. Giá trị f(v) cho v ∈ V được gọi là trọng số của đỉnh v , còn giá trị g(e) cho e ∈ E được gọi là trọng số của cung e hoặc trọng số của cạnh e. Người ta cũng thường kí hiệu đồ thị có trọng số là G = (V, E, f ) hay G = (V, E, g) hay G = (V, E, f, g) tùy thuộc vào việc chỉ một hàm f , chỉ một hàm g hay cả hai hàm f và g được xác định. Ví dụ 1.1.5. Cho G = (V, E, g) với V = {a, b, c, d, e} và E = {(a, b), (a, c), (b, e), (e, d), (b, d), (c, e)} và g : E → N được xác định như sau: g(a, b) = g(b, e) = g(c, e) = 5 g(a, c) = 4 g(e, d) = g(b, d) = 7 Khi đó G là một trọng đồ thị có hướng được biểu diễn bởi hình (1.3). Lưu Thị Thêm 10 K20-Toán ứng dụng Luận văn thạc sĩ Hình 1.3: Ví dụ một đồ thị có trọng số có hướng 1.2 Đồ thị con và một số vấn đề liên quan Đồ thị G0 = (V 0 , E 0 ) được gọi là đồ thị con của đồ thị G = (V, E) nếu V 0 ⊆ V và E 0 ⊆ E . Đồ thị con G0 = (V 0 , E 0 ) của đồ thị G = (V, E) được gọi là đồ thị con bao trùm của G nếu V 0 = V . Nếu E 0 chứa tất cả các cung hay cạnh của G, mà hai đỉnh liên thuộc với nó đều thuộc V 0 , thì G0 = (V 0 , E 0 ) được gọi là đồ thị con của G = (V, E) cảm sinh bởi tập đỉnh V 0 hay cũng được gọi là đồ thị con cảm sinh bởi G = (V, E) trên tập đỉnh V 0 . Khi đó G0 cũng được kí hiệu là G0 = G[V 0 ]. Ta thường phải xây dựng các đồ thị mới từ các đồ thị đã cho bằng cách xóa hay thêm một số đỉnh hoặc cạnh. Nếu W ⊆ V , thì G−W = G[V \W ], tức là đồ thị con của G nhận được từ G bằng cách xóa đi các đỉnh thuộc W và mọi cung (hay cạnh) liên thuộc với các đỉnh trong W . Tương tự, nếu E 0 ⊆ E , thì G − E 0 = (V, E\E 0 ). Nếu W = {w} và E 0 = {(x, y)} (hay E 0 = {xy}) thì kí hiệu ở trên được đơn giản viết thành G−w và G−(x, y) (hay G − xy ). Tương tự, nếu x và y không kề nhau trong G thì G + (x, y) (hay G + xy ) là đồ thị nhận được từ G bằng cách nối x với y bằng cung (x, y) (tương ứng bằng cạnh xy ). Nếu G1 = (V1 , E1 ) và G2 = (V2 , E2 ) là hai đồ thị đã cho thì hợp của hai đồ thị này, kí hiệu G1 ∪ G2 , là đồ thị với tập đỉnh là V1 ∪ V2 và tập cung (hay cạnh) là E1 ∪ E2 . Nếu cả hai đồ thị G1 và G2 là đồ thị vô hướng thì kết nối của hai đồ thị G1 và G2 , kí hiệu là G1 + G2 , là đồ thị nhận được từ G1 ∪ G2 bằng cách thêm vào tất cả các cạnh dạng xy với x 6= y và x ∈ V1 , y ∈ V2 . Lưu Thị Thêm 11 K20-Toán ứng dụng Luận văn thạc sĩ 1.3 Bậc của đỉnh a) Đối với đồ thị vô hướng Bậc của đỉnh v , kí hiệu là deg(v), là số cạnh liên thuộc với v . Nhận xét 1.3.1 Nếu đồ thị vô hướng G = (V, E) có n cạnh thì tổng số bậc của các đỉnh trong G bằng 2n và số đỉnh bậc lẻ luôn là số chẵn. b) Đối với đồ thị có hướng Cho đồ thị có hướng G = (V, E) với m cung. – Bán bậc ra của đỉnh v , kí hiệu là deg + (v), là số cung đi ra khỏi v. – Bán bậc vào của đỉnh v , kí hiệu là deg − (v), là số cung đi vào đỉnh v . Nhận xét 1.3.2 Tổng tất cả các bán bậc ra bằng tổng tất cả các bán bậc vào của các đỉnh và bằng m. X X + deg (v) = deg − (v) = m. v∈V 1.4 v∈V Chu trình, mạch Cho G = (V, E) là đồ thị có hướng hoặc vô hướng. • Hành trình trong đồ thị có hướng G là dãy v0 , v1 , ..., vn với vi ∈ V và vi−1 vi ∈ E, ∀i = 1, n. • Hành trình trong đồ thị vô hướng G là dãy v0 , v1 , ..., vn với vi ∈ V và vi−1 vi ∈ E hoặc vi vi−1 ∈ E, ∀i = 1, n. • Hành trình trong đồ thị có các đỉnh phân biệt được gọi là đường đi. • Hành trình trong đồ thị có các cạnh phân biệt được gọi là vết. • Hành trình được gọi là khép kín nếu đỉnh đầu và đỉnh cuối trùng nhau. • Hành trình khép kín mà khi xóa đỉnh cuối thì trở thành một đường đi được gọi là chu trình. • Vết có điểm đầu và điểm cuối trùng nhau được gọi là mạch. Lưu Thị Thêm 12 K20-Toán ứng dụng Luận văn thạc sĩ 1.5 Tính liên thông của đồ thị a Đối với đồ thị vô hướng G = (V, E) – Đồ thị G được gọi là liên thông nếu luôn tồn tại đường đi giữa mọi cặp đỉnh phân biệt của G. – Đồ thị con liên thông cực đại của G được gọi là thành phần liên thông của G. – Nếu bỏ đi một cạnh mà làm tăng số thành phần liên thông của đồ G thị thì cạnh đó được gọi là cạnh cắt hoặc cạnh cầu của G. b Đối với đồ thị có hướng G = (V, E) – 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. – G = (V, E) được gọi là liên thông một chiều nếu với hai đỉnh khác nhau bất kì vi và vj , tồn tại một hành trình có hướng với đỉnh đầu là vi và đỉnh cuối là vj hoặc một hành trình có hướng với đỉnh đầu là vj và đỉnh cuối là vi (hoặc cả hai hành trình đó). – G = (V, E) được gọi là liên thông mạnh nếu với hai đỉnh bất kì khác nhau vi và vj , luôn tồn tại cả hành trình có hướng với đỉnh đầu là vi và đỉnh cuối là vj và hành trình có hướng với đỉnh đầu là vj và đỉnh cuối là vi . 1.6 Cây khung của đồ thị • Cây bao trùm (tiếng anh: spanning tree), còn được gọi là cây khung, của đồ thị G là cây con của đồ thị G, chứa tất cả các đỉnh của G. Nói cách khác, cây bao trùm của một đồ thị G là một đồ thị con của G, chứa tất cả các đỉnh của G, liên thông và không có chu trình. • Mọi đồ thị liên thông đều có ít nhất một cây khung. • Cây khung ngoài của đồ thị có hướng là cây khung có đúng một đỉnh có bán bậc vào bằng 0. • Cây khung trong của đồ thị có hướng là cây khung có đúng một đỉnh có bán bậc ra bằng 0. Lưu Thị Thêm 13 K20-Toán ứng dụng Luận văn thạc sĩ 1.7 Phương pháp duyệt đồ thị a) Duyệt đồ thị ưu tiên chiều sâu (DFS). Bước 1: Bắt đầu từ một đỉnh v0 vào thăm và lấy thông tin. Bước 2: Chọn một trong số các đỉnh kề với v0 mà chưa được thăm (gọi là u). Bước 3: Khởi động quá trình duyệt bắt đầu từ u (giống như từ v0 ). b) Duyệt đồ thị ưu tiên chiều rộng (BFS). Bước 1: Bắt đầu từ v0 , thăm tất cả các đỉnh kề với v0 . Bước 2: Lần lượt khởi động quá trình duyệt từ mỗi đỉnh vừa được thăm. 1.8 Luồng trong mạng • Ta gọi mạng là một đồ thị có hướng G = (V, E), trong đó có duy nhất một đỉnh s không có cung đi vào (gọi là điểm phát) và có duy nhất một đỉnh t không có cung đi ra (gọi là đỉnh thu). Mỗi cung e = (u, v) ∈ E được gán với một số không âm w(e) = w(u, v) gọi là khả năng thông qua của cung đó. Ta quy ước rằng nếu không có cung w(x, y) thì khả năng thông qua w(u, v) của nó được gán bằng 0. • Cho G = (V, E), ta gọi luồng f trong mạng G là một phép gán cho mỗi cung e = (u, v) ∈ E một số thực không âm f (e) = f (u, v), gọi là luồng trên cung e, thỏa mãn các điều kiện sau: 1) Với mọi cung (x, y) ∈ E ta luôn có 0 ≤ f (x, y) ≤ w(x, y); với w(x, y) là khả năng thông qua của cung (x, y) X X f (s, x) − f (y, s) = c ≥ 0; 2) y∈N − (s) x∈N + (s) 3) X x∈N + (t) f (t, x) − X f (y, t) = −c; y∈N − (t) 4) Với t, Xmọi đỉnh z 6= s,X f (z, x) − f (y, z) = 0. x∈N + (z) y∈N − (z) • Giá trị của luồng được tính bằng tổng giá trị trên các cung đi ra từ đỉnh nguồn s hoặc tổng giá trị trên các cung đi vào từ đỉnh thu t. Luồng trong mạng có giá trị luồng lớn nhất được gọi là luồng cực đại trên mạng đó. Lưu Thị Thêm 14 K20-Toán ứng dụng Luận văn thạc sĩ 1.9 Ghép cặp đồ thị Định nghĩa 1 Cho đồ thị G = (V, E). • Một ghép cặp của G là một tập con M nào đó của tập cạnh E sao cho trong M không có hai cạnh nào là kề nhau (có đỉnh chung). • Một ghép cặp cực đại là ghép cặp mà không thể mở rộng thành một ghép cặp có số cạnh lớn hơn. • Một ghép cặp lớn nhất là ghép cặp có số cạnh lớn nhất của đồ thị G. • Một ghép cặp đầy đủ/ hoàn chỉnh/ hoàn hảo của G là ghép cặp mà tất cả các đỉnh của G đều là những đầu mút của các cạnh thuộc ghép cặp đó. Ví dụ 1.9.1. Xét đồ thị G trong hình vẽ dưới đây: Hình 1.4: M1 = {b, d, h}, M2 = {a, e, k} là những ghép cặp lớn nhất. M3 = {c, h}, M4 = {c, l} là những ghép cặp cực đại. Ví dụ 1.9.2. Xét đồ thị G trong hình vẽ dưới đây: Hình 1.5: Ghép cặp đầy đủ trong đồ thị M = {v1 v2 , v3 v7 , v4 v6 , v5 v8 } là một ghép cặp đầy đủ của G. Lưu Thị Thêm 15 K20-Toán ứng dụng Chương 2 Vết Euler, mạch Euler và đồ thị Euler 2.1 Định nghĩa Định nghĩa 2.1.1 ([2]) Cho đồ thị G = (V, E) liên thông, có hướng hoặc vô hướng. • Nếu tồn tại một mạch C chứa tất cả các cạnh của G thì C được gọi là mạch Euler trong G. Khi đó G được gọi là đồ thị Euler. • Nếu tồn tại một vết T chứa tất cả các cạnh của G thì T được gọi là vết Euler trong G. Khi đó G được gọi là đồ thị nửa Euler. Nhận xét 2.1.1 Nếu G là đồ thị Euler thì G là đồ thị nửa Euler. Ví dụ 2.1.1. Cho đồ thị G dưới đây: Hình 2.1: Đồ thị G trên hình (2.1) là đồ thị Euler với mạch Euler: v1 , v2 , v3 , v4 , v8 , v6 , v7 , v8 , v3 , v1 , v5 , v2 , v4 , v7 , v5 , v6 , v1 . 16 Luận văn thạc sĩ Ví dụ 2.1.2. Cho đồ thị G dưới đây: Hình 2.2: Đồ thị G trên hình(2.2) là đồ thị Euler với mạch Euler: v1 , v8 , v2 , v3 , v4 , v6 , v7 , v8 , v6 , v5 , v4 , v2 , v1 . Ví dụ 2.1.3. Cho đồ thị G dưới đây: Hình 2.3: Đồ thị G trên hình (2.3) là đồ thị nửa Euler với vết Euler: v3 , v2 , v1 , v5 , v2 , v4 , v5 , v3 , v4 . Ví dụ 2.1.4. Cho đồ thị G dưới đây: Lưu Thị Thêm 17 K20-Toán ứng dụng Luận văn thạc sĩ Hình 2.4: Đồ thị G trên hình (2.4) là đồ thị nửa Euler với vết Euler: v3 , v2 , v1 , v5 , v4 , v1 , v5 , v4 . 2.2 Định lí về điều kiện cần và đủ để một đồ thị là đồ thị Euler Không phải mọi đồ thị liên thông đều là đồ thị Euler. Nhà toán học Euler đã đưa ra câu trả lời cho bài toán "Bảy cây cầu Königsberg" với kết luận không thể đi một lần qua tất cả bảy cây cầu mà mỗi cây cầu chỉ đi qua đúng một lần. Dưới đây là định lí về điều kiện cần và đủ để một đồ thị vô hướng là đồ thị Euler. Định lý 2.2.1 ([2]) Ta có: a) Đồ thị vô hướng G là đồ thị Euler khi và chỉ khi G liên thông và bậc của mọi đỉnh đều là số chẵn. b) Đồ thị vô hướng G là đồ thị nửa Euler khi và chỉ khi G liên thông và có đúng 2 đỉnh bậc lẻ. Chứng minh. Định lí 2.3.1a a) Điều kiện cần. Giả sử G = (V, E) là một mạch Euler. Khi đó, mỗi lần mạch đi qua một đỉnh nào đó thì bậc của đỉnh đó tăng lên 2. Mặt khác mỗi cạnh chỉ được lặp lại đúng một lần nên bậc của mỗi đỉnh luôn là bậc chẵn. b) Điều kiện đủ. Giả sử G = (V, E) có bậc của mọi đỉnh đều là số chẵn. Suy ra Lưu Thị Thêm 18 K20-Toán ứng dụng