Tài liệu Phân tích tai của đồ thị và đồ thị series parallel

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Nguyễn Thị Thu Hà PHÂN TÍCH TAI CỦA ĐỒ THỊ VÀ ĐỒ THỊ SERIES PARALLEL LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội - 2019 BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- Nguyễn Thị Thu Hà PHÂN TÍCH TAI CỦA ĐỒ THỊ VÀ ĐỒ THỊ SERIES PARALLEL 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: PGS. TSKH Phan Thị Hà Dương Hà Nội - 2019 LỜI CAM ĐOAN Tôi xin cam đoan những gì viết trong luận văn là do sự tìm tòi, học hỏi của bản thân và sự hướng dẫn tận tình của cô Phan Thị Hà Dương. Mọi kết quả nghiên cứu cũng như ý tưởng của tác giả khác, nếu có đều được trích dẫn cụ thể. Đề tài luận văn này cho đến nay chưa được bảo vệ tại bất kì một hội đồng bảo vệ luận văn thạc sĩ nào và cũng chưa hề được công bố trên bất kì một phương tiện nào. Tôi xin chịu trách nhiệm về những lời cam đoan. Hà Nội, tháng 10 năm 2019 Học viên Nguyễn Thị Thu Hà LỜI CẢM ƠN Để hoàn thành luận văn này, trước hết tôi xin được bày tỏ sự biết ơn sâu sắc nhất của mình tới PGS.TSKH Phan Thị Hà Dương đã trực tiếp hướng dẫn, chỉ bảo tận tình cũng như tạo mọi điều kiện thuận lợi nhất trong suốt thời gian tôi thực hiện luận văn. Tôi cũng xin bày tỏ lòng biết ơn các thầy cô, các anh chị và bạn bè trong Viện Toán học đã quan tâm giúp đỡ trong suốt quá trình học tập và nghiên cứu tại Viện. Qua đây, tôi cũng xin trân trọng cảm ơn sự giúp đỡ và tạo điều kiện thuận lợi của cơ sở đào tạo là Học viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam trong quá trình thực hiện luận văn. Cuối cùng tôi xin cảm ơn gia đình, người thân đã luôn quan tâm, giúp đỡ, động viên và khích lệ tôi trong suốt quá trình học tập và nghiên cứu. Hà Nội, tháng 10 năm 2019 Học viên Nguyễn Thị Thu Hà Mục lục Danh sách hình vẽ 3 Danh sách bảng 5 MỞ ĐẦU 6 1 TÌM HIỂU VỀ PHÂN TÍCH TAI VÀ MỐI LIÊN HỆ VỚI TÍNH LIÊN THÔNG CỦA ĐỒ THỊ 8 1.1 Các định nghĩa cơ bản về đồ thị và ví dụ . . . . . . . . . . . . 8 1.2 Tính liên thông của đồ thị . . . . . . . . . . . . . . . . . . . . 12 1.3 Các loại liên thông trên đồ thị . . . . . . . . . . . . . . . . . . 15 1.4 2 1.3.1 Đồ thị k - liên thông . . . . . . . . . . . . . . . . . . . 15 1.3.2 Đồ thị k - cạnh liên thông . . . . . . . . . . . . . . . . 21 Hai loại phân tích tai. Điều kiện để có phân tích tai . . . . . . . 24 1.4.1 Phân tích tai loại 1 . . . . . . . . . . . . . . . . . . . . 24 1.4.2 Phân tích tai loại 2 . . . . . . . . . . . . . . . . . . . . 27 NHẬN DẠNG ĐỒ THỊ SERIES PARALLEL DỰA TRÊN PHÂN TÍCH TAI 32 1 2 2.1 Phân tích tai gắn kết . . . . . . . . . . . . . . . . . . . . . . . 33 2.2 Đồ thị Series - Parallel và phân tích tai . . . . . . . . . . . . . 40 2.3 3 2.2.1 Định nghĩa đồ thị Series - Parallel . . . . . . . . . . . . 40 2.2.2 Điều kiện để một đồ thị là Series - Parallel . . . . . . . 41 Thuật toán nhận dạng đồ thị Series - Parallel . . . . . . . . . . 48 2.3.1 Ý tưởng thuật toán . . . . . . . . . . . . . . . . . . . . 48 2.3.2 Kiểm tra tính gắn kết . . . . . . . . . . . . . . . . . . 49 2.3.3 Độ phức tạp và ví dụ . . . . . . . . . . . . . . . . . . 59 KẾT LUẬN, KIẾN NGHỊ 65 Danh sách hình vẽ 1.1 Một số ví dụ về đồ thị. . . . . . . . . . . . . . . . . . . . . . . 10 1.2 Đồ thị hai phần và đồ thị hai phần đầy đủ K2,3 . . . . . . . . . . 10 1.3 Đồ thị vô hướng G. . . . . . . . . . . . . . . . . . . . . . . . 13 1.4 Trường hợp P chứa e. . . . . . . . . . . . . . . . . . . . . . . 13 1.5 Rừng gồm 4 cây. . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.6 Kết nối của K3 , K2,3 và đồ thị liên thông có một đỉnh cắt. . . . 16 1.7 Trường hợp đường R có điểm trong chung với cả P và Q. . . . 18 1.8 Chu trình u, x, y, v, u đi qua hai cạnh uv và xy . . . . . . . . . . 19 1.9 Sự phân chia cạnh uv thành đường u, w, v . . . . . . . . . . . . 19 1.10 Sửa đổi chu trình qua e, f . . . . . . . . . . . . . . . . . . . . . 20 1.11 Ví dụ tập ngắt kết nối cạnh không phải tập cạnh cắt. . . . . . . 22 1.12 Hình minh họa S, S và T . . . . . . . . . . . . . . . . . . . . . 23 1.13 Kết nối và kết nối cạnh của một số đồ thị. . . . . . . . . . . . . 23 1.14 Ví dụ về phân tích tai và phân tích tai mở loại 1. . . . . . . . . 24 1.15 Phân tích tai mới thu được khi thay P3 = P0 . . . . . . . . . . . 25 1.16 Chuỗi các phép phân chia cạnh uv chuyển đồ thị G + uv thành G ∪ P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3 4 1.17 Phân tích tai và phân tích tai mở loại 2. . . . . . . . . . . . . . 28 1.18 Đồ thị G, cây các khối và cây các đồ thị con 2 - cạnh liên thông cực đại của G. . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.19 Hình minh họa các trường hợp khi thêm tai thứ k . . . . . . . . . 30 2.1 Phân tích tai gắn kết và phân tích tai dạng cây . . . . . . . . . . 34 2.2 Cây của các khoảng gắn trên tai E1 . . . . . . . . . . . . . . . 35 2.3 Phân tích tai dạng cây và cây. . . . . . . . . . . . . . . . . . . 36 2.4 Tai Ej gắn trên Ei nhưng không gắn thực sự. . . . . . . . . . . 38 2.5 Cấu trúc của một đồ thị TTSP bằng các phép tổng hợp chuỗi và song song . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.6 Cây nhị phân thể hiện cấu trúc của đồ thị TTSP trong hình 2.5. 42 2.7 Hình minh họa trường hợp 1 và 2. . . . . . . . . . . . . . . . . 43 2.8 Tai Ei và đường tai Hi . . . . . . . . . . . . . . . . . . . . . . 51 2.9 Cây gắn kết của tai Ei . . . . . . . . . . . . . . . . . . . . . . . 56 2.10 Đường tai Hj của tai Ej . . . . . . . . . . . . . . . . . . . . . . 56 2.11 Cây sp. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.12 Đồ thị G. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.13 Đường cạnh H1 và cây sp. . . . . . . . . . . . . . . . . . . . . 61 2.14 Đường cạnh H2 và cây sp. . . . . . . . . . . . . . . . . . . . . 61 2.15 Đường cạnh H3 và cây sp. . . . . . . . . . . . . . . . . . . . . 62 2.16 Đường cạnh H4 và cây sp. . . . . . . . . . . . . . . . . . . . . 63 2.17 Đường cạnh H5 và cây sp. . . . . . . . . . . . . . . . . . . . . 63 2.18 Cây sp của G. . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Danh sách bảng 2.1 Danh sách các cạnh đi xuôi và đi ngược của các đỉnh trong Hi . . 51 2.2 Bảng liệt kê con đầu và em kế của các cạnh trong Hi . . . . . . . 55 2.3 Lưu trữ các cạnh của Hi vào các ô nhớ. . . . . . . . . . . . . . 55 2.4 Danh sách các cạnh đi xuôi và đi ngược của các đỉnh trong Hj . . 56 2.5 Bảng liệt kê con đầu và em kế của các cạnh trong Hj . . . . . . 57 2.6 Lưu trữ các cạnh của Hj vào các ô nhớ. . . . . . . . . . . . . . 57 2.7 Bảng tính X, Y, Z cho từng cạnh ei . . . . . . . . . . . . . . . . 58 2.8 Bảng liệt kê con đầu và em kế của các cạnh trong H1 . . . . . . 60 2.9 Bảng tính X, Y, Z cho từng cạnh trong H1 . . . . . . . . . . . . 60 2.10 Bảng tính X, Y, Z cho từng cạnh trong H2 . . . . . . . . . . . . 61 2.11 Bảng tính X, Y, Z cho từng cạnh trong H3 . . . . . . . . . . . . 62 2.12 Bảng tính X, Y, Z cho từng cạnh trong H4 . . . . . . . . . . . . 62 2.13 Bảng tính X, Y, Z cho từng cạnh trong H5 . . . . . . . . . . . . 63 5 6 MỞ ĐẦU Ngày nay, lý thuyết đồ thị đã được phát triển mạnh mẽ, trở thành một chủ đề quan trọng của Toán học, và được sử dụng trong nhiều vấn đề ứng dụng toán học. Một trong những lớp đồ thị cơ bản, quan trọng là đồ thị Series Parallel. Chúng hay được ứng dụng trong mô hình mạch điện, trong các vấn đề lập kế hoạch. Việc nhận ra các đồ thị Series Parallel là một trong những vấn đề được nhiều nhà khoa học quan tâm và điều này có thể được thực hiện trong thời gian tuyến tính (Valdes, Tarjan và Lawler, 1979 [2]). Hơn nữa, khi ta biết một phân tích của đồ thị Series Parallel theo hai phép toán Series và Parallel thì ta có thể giải quyết được nhiều vấn đề trong thời gian tuyến tính như tìm ghép cặp lớn nhất, tập độc lập lớn nhất,. . . trong đó có nhiều vấn đề là NP – khó cho các đồ thị tổng quát. Năm 1987, He và Yesha [3] đã đưa ra một thuật toán nhận dạng đồ thị Seriesparallel có hướng trong thời gian O(log 2 n) với O(m + n) bộ xử lí trên EREW PRAM. Năm 1992, Eppstein [4] đã cải thiện kết quả này, thuật toán chạy trong thời gian O(logn) với C(m, n) bộ xử lí trên CRCW PRAM, trong đó C(m, n) là số bộ xử lí cần thiết để đếm số thành phần liên thông của đồ thị trong thời gian logarit. Giá trị bị chặn tốt nhất được biết là C(m, n) = O(mα(m, n)/logn). Trong luận văn này, chúng tôi sẽ trình bày về phân tích tai của đồ thị, mối liên hệ giữa phân tích tai và đồ thị Series Parallel và quan trọng là trình bày thuật toán nhận dạng đồ thị Series Parallel, thuật toán dựa trên khái niệm phân tích tai mở của đồ thị. Luận văn được chia làm hai chương như sau: Chương 1: Tìm hiểu về phân tích tai và mối liên hệ với tính liên thông của đồ thị. Trong phần này, chúng tôi trình bày một số khái niệm cơ bản của đồ thị, các loại liên thông trên đồ thị, định nghĩa phân tích tai và mối liên hệ với tính liên thông. Chương 2: Nhận dạng đồ thị Series Parallel dựa trên phân tích tai. Ở chương 7 này, chúng tôi sẽ giới thiệu về đồ thị Series Parallel, phân tích tai gắn kết, sau đó trình bày điều kiện để một đồ thị là Series Parallel và cuối cùng là kết hợp các kết quả đã có để hình thành thuật toán. Mặc dù bản thân tác giả đã rất cố gắng, xong luận văn này không thể tránh khỏi những thiếu sót. Rất mong nhận được sự góp ý của quý thầy cô và các bạn để luận văn được hoàn thiện hơn. CHƯƠNG 1 TÌM HIỂU VỀ PHÂN TÍCH TAI VÀ MỐI LIÊN HỆ VỚI TÍNH LIÊN THÔNG CỦA ĐỒ THỊ Trước khi đi vào vấn đề chính, chúng tôi sẽ trình bày về những kiến thức cơ bản của đồ thị, tính liên thông, k - liên thông, giới thiệu về phân tích tai của đồ thị và mối liên hệ của nó với tính liên thông. Để làm sáng tỏ hơn vấn đề, chúng tôi đã trình bày chi tiết chứng minh các định lý, phân chia các trường hợp cụ thể và vẽ các hình minh họa. Phần lớn các kiến thức trong chương này được trích dẫn từ [4] [5]. 1.1 Các định nghĩa cơ bản về đồ thị và ví dụ Trong mục này, chúng tôi trình bày những khái niệm cơ bản của đồ thị vô hướng như đồ thị đầy đủ, đồ thị hai phần, đường, chu trình,. . . Đây là những kiến thức cơ sở được sử dụng trong những phần tiếp theo của luận văn. Định nghĩa 1.1.1. (Đồ thị vô hướng) • Một đồ thị vô hướng G là một cặp có thứ tự G := (V, E) trong đó V là tập các đỉnh, E là tập các cặp đỉnh (không có thứ tự), được gọi là cạnh. 8 9 Hai đỉnh thuộc một cạnh được gọi là các đầu mút của cạnh đó. Ta kí hiệu V (G) là tập đỉnh của G, E(G) là tập cạnh của G. • Cạnh e = uv (hay e = vu) nếu u, v là hai đầu mút của e. Khi đó ta nói cạnh e kề với hai đỉnh u và v hay u, v kề nhau hay u, v là hàng xóm của nhau. Định nghĩa 1.1.2. Một khuyên là một cạnh mà hai đỉnh cuối của nó trùng nhau. Các cạnh bội là những cạnh mà chúng có chung đỉnh cuối. Đơn đồ thị là đồ thị không có khuyên hoặc cạnh bội. Trong luận văn này ta xét các đồ thị vô hướng có thể có khuyên và cạnh bội. Định nghĩa 1.1.3. Cho đồ thị G, bậc của đỉnh v ∈ V (G) kí hiệu là dG (v) hay d(v) là số cạnh kề với v , riêng mỗi khuyên tại v (nếu có) được đếm 2 lần. Ta đặt ∆(G) là bậc lớn nhất của đồ thị, δ(G) là bậc nhỏ nhất của đồ thị. Định nghĩa 1.1.4. Đơn đồ thị G = (V, E) được gọi là đồ thị đầy đủ nếu mọi cặp đỉnh phân biệt trong V đều kề nhau. Đồ thị đầy đủ n đỉnh (n > 0) được kí hiệu là Kn . Ví dụ 1.1.1. Trong hình 1.1 • Cạnh e6 là một khuyên của đồ thị G. Cạnh e7 và e1 là các cạnh bội của G, do đó G không phải là một đơn đồ thị. • K2 và K4 là các đồ thị đầy đủ. • Ta có ∆(G) = 4 và δ(G) = 2, ∆(K4 ) = δ(K4 ) = 3. Định nghĩa 1.1.5. (Đồ thị hai phần) • Đơn đồ thị G = (V, E) được gọi là đồ thị hai phần nếu V = U ∪ W sao cho mọi cặp đỉnh phân biệt trong U và W là không kề nhau, tức là với mọi u1 , u2 ∈ U, w1 , w2 ∈ W thì (u1 , u2 ) ∈ / E, (w1 , w2 ) ∈ / E . Khi đó ta có thể viết đồ thị G dưới dạng G = (U ∪ W, E). 10 Hình 1.1: Một số ví dụ về đồ thị. • Đồ thị hai phần G = (U ∪ W, E) là đầy đủ nếu mỗi đỉnh trong U đều kề với mọi đỉnh trong W . Nếu m là số đỉnh của U , n là số đỉnh của W thì đồ thị hai phần đầy đủ G được kí hiệu là Km,n . Hình 1.2: Đồ thị hai phần và đồ thị hai phần đầy đủ K2,3 . Định nghĩa 1.1.6. (Đồ thị con và đồ thị con cảm sinh) • Một đồ thị con của đồ thị G là một đồ thị H sao cho V (H) ⊆ V (G), E(H) ⊆ E(G) và cách gán hai đầu mút cho các cạnh trong H giống như trong G. • Cho T ⊆ V (G), đồ thị con của G sinh bởi T là đồ thị con của G có tập đỉnh là T và tập cạnh là tất cả các cạnh của G có hai đầu mút thuộc T , kí hiệu là G[T ]. 11 Ví dụ 1.1.2. Cho đồ thị G như trong hình 1.1. Ta có đồ thị H với V (H) = {v1 , v2 , v3 , v4 } và E(H) = {e1 , e2 , e3 , e4 } là một đồ thị con của G và do H không có khuyên hay cạnh bội nên H là một đơn đồ thị. H là một đồ thị con của G nhưng không phải là đồ thị con cảm sinh của G do G[V (H)] = G. Định nghĩa 1.1.7. Cho G = (V, E) là một đồ thị vô hướng. Một hành trình là một danh sách vo e1 v1 ...ek vk của các đỉnh và cạnh, sao cho với 0 ≤ i ≤ k cạnh ei có đỉnh cuối là vi−1 và vi . Khi đó k được gọi là độ dài của hành trình, vo được gọi là đỉnh đầu, vk được gọi là đỉnh cuối của hành trình. Để đơn giản, ta thường gọi dãy các đỉnh vo , v1 , ..., vk là một hành trình trong G nếu với mọi i = 0, 1, ..., k − 1, vi vi+1 là một cạnh của G và không có cạnh bội có hai đầu mút là vi , vi+1 . • Một hành trình là khép kín nếu đỉnh đầu và đỉnh cuối của nó trùng nhau. • Một vết là một hành trình mà mỗi cạnh chỉ xuất hiện một lần. • Một đường là một hành trình mà các đỉnh của nó đều khác nhau. Ta gọi hai đỉnh cuối của một đường là hai đầu mút của đường đó. • Một chu trình (hay một xích) là một hành trình khép kín có độ dài ít nhất là 3 và khi xóa đi đỉnh cuối thì trở thành đường. Ví dụ 1.1.3. Cho đồ thị G = (V, E) như trong hình 1.1. Khi đó: • v1 e4 v3 e3 v4 e3 v3 e6 v3 là một hành trình. • v1 e1 v2 e7 v1 e4 v3 là một vết. • v1 e1 v2 e2 v4 e3 v3 là một đường. • v1 e1 v2 e2 v4 e3 v3 e4 v1 là một chu trình. 12 1.2 Tính liên thông của đồ thị Trong mục này, chúng tôi trình bày về tính liên thông và khái niệm cây trong đồ thị. Cây là một trong những lớp đồ thị quan trọng có rất nhiều ứng dụng, đặc biệt trong việc lưu trữ dữ liệu, tìm kiếm,. . . Trong chương 2, chúng tôi sẽ dùng cây để biểu thị cấu trúc của đồ thị Series - Parallel. Định nghĩa 1.2.1. Một đồ thị G là liên thông nếu mọi u, v ∈ G đều có đường nối từ u đến v . Ngược lại, G là không liên thông. Định nghĩa 1.2.2. Một thành phần liên thông của đồ thị G là đồ thị con liên thông cực đại của G. Một thành phần liên thông là tầm thường nếu nó không chứa cạnh nào, ngược lại là không tầm thường. Đỉnh cô lập là đỉnh có bậc 0. Định nghĩa 1.2.3. Cạnh cắt hoặc đỉnh cắt của một đồ thị là một cạnh hoặc một đỉnh mà việc xóa nó làm tăng số thành phần liên thông. Ta viết G − e hoặc G − M là đồ thị con của G thu được bằng việc xóa đi một cạnh e hoặc một tập cạnh M . Ta viết G − v hoặc G − S là đồ thị con của G thu được bằng việc xóa đi một đỉnh v hoặc một tập đỉnh S . Ví dụ 1.2.1. Ta thấy đồ thị trong hình 1.3 là đồ thị không liên thông do không có đường đi nào từ a đến b. G có ba thành phần liên thông với tập đỉnh lần lượt là: {a}, {b, c, d, e}, {f, g, h}. Ta có g là đỉnh cắt của đồ thị, gh và gf là các cạnh cắt của G. Tiếp theo, chúng tôi sẽ trình bày điều kiện để một cạnh là cạnh cắt. Đây là kết quả quan trọng được sử dụng trong một số kết quả về sau. Định lý 1.2.1. [5] Một cạnh là cạnh cắt khi và chỉ khi nó không thuộc một xích nào. Chứng minh. Điều kiện cần: 13 Hình 1.3: Đồ thị vô hướng G. Cho e là một cạnh của đồ thị G (với hai đầu mút là x, y ) và H là một thành phần liên thông của G chứa e. Do việc xóa bỏ e không ảnh hưởng đến các thành phần liên thông khác nên việc chứng minh định lý trên sẽ tương đương với chứng minh H − e liên thông khi và chỉ khi e thuộc một xích. Đầu tiên giả sử H − e liên thông. Khi đó nó chứa một đường nối từ x đến y và không qua e, ghép đường đó với cạnh e ta được một xích chứa e. Ngược lại giả sử e thuộc xích C . Lấy hai đỉnh bất kì u, v ∈ V (H). Do H liên thông nên tồn tại đường P nối u, v . Nếu P không chứa e thì P là đường trong H − e đi nối u, v . Nếu P chứa e, không mất tính tính tổng quát giả sử x nằm giữa y và u trong P . Ta có H − e chứa đường từ u tới x, đường từ y tới v dọc theo P và đường từ x tới y dọc theo C (hình 1.4). Kết hợp ba đường trên ta thu được một đường u, v trong H − e. Do dó H − e là liên thông. Hình 1.4: Trường hợp P chứa e. Định nghĩa 1.2.4. Một đồ thị không có vòng là một đồ thị phi chu trình. Rừng 14 là một đồ thị phi chu trình. Cây là đồ thị liên thông và không có chu trình. Lá là một đỉnh có bậc 1. Đồ thị con bao trùm của G là một đồ thị con với tập đỉnh là V (G). Cây bao trùm là một thị con bao trùm và là một cây. Nhận xét 1.2.1. Ta thấy: • Mỗi cây là một rừng liên thông, mọi thành phần liên thông của rừng là một cây. • Mỗi một đường là một cây, một cây là một đường khi và chỉ khi bậc lớn nhất của nó bằng 2. Ví dụ 1.2.2. Hình 1.5 cho ta ví dụ về một rừng có 4 cây, trong đó có một cây tầm thường (cây chỉ có một đỉnh). Hình 1.5: Rừng gồm 4 cây. Định lý 1.2.2. [5] Cho G là đồ thị n đỉnh với n ≥ 1. Các mệnh đề sau tương đương: 1. G là một cây. 2. G có n − 1 cạnh và không có chu trình. 3. G liên thông và có n − 1 cạnh. 15 4. Với u, v ∈ V (G), có duy nhất một đường nối từ u tới v . Hệ quả 1.2.1. [5] 1. Mọi cạnh của một cây đều là một cạnh cắt. 2. Thêm một cạnh vào cây tạo ra duy nhất một vòng. 3. Mọi đồ thị liên thông đều chứa một cây bao trùm. 1.3 Các loại liên thông trên đồ thị Trong mục này chúng tôi trình bày về những lớp đồ thị có "liên kết" tốt, tức là các đỉnh của đồ thị vẫn được kết nối với nhau kể cả khi xóa bỏ một số đỉnh hoặc cạnh. Điều này rất có ý nghĩa trong việc xây dựng mạng lưới truyền thông, điện lưới,. . . 1.3.1 Đồ thị k - liên thông Phần này giới thiệu về đồ thị k - liên thông, đồ thị mà sau khi xóa đi k − 1 đỉnh thì vẫn còn liên thông. Định nghĩa 1.3.1. Tập phân tách hay tập đỉnh cắt của đồ thị G là tập S ⊆ V (G) sao cho G − S có nhiều hơn một thành phần liên thông. Kết nối của G, viết là κ(G) là kích cỡ nhỏ nhất của một tập đỉnh cắt S sao cho G − S là không liên thông hoặc chỉ có một đỉnh. Một đồ thị G gọi là k -liên thông nếu kết nối của nó lớn hơn hoặc bằng k , tức là khi ta xóa đi k − 1 đỉnh thì đồ thị G vẫn còn liên thông. Ví dụ 1.3.1. • Một clique không có tập phân tách và κ(Kn ) = n − 1. Từ đó ta thu được một đồ thị G không là đồ thị đầy đủ thì κ(G) ≤ n(G) − 2. • κ(Km,n ) = min(m, n) với Km.n là đồ thị hai phần đầy đủ. 16 • Một đồ thị có nhiều hơn hai đỉnh có kết nối 1 khi và chỉ khi nó liên thông và có một đỉnh cắt. • Một đồ thị với nhiều hơn một đỉnh có kết nối 0 khi và chỉ khi nó không liên thông. • κ(K1 ) = 0. • Hình 1.6 cho ta một số ví dụ về kết nối của một số đồ thị. Hình 1.6: Kết nối của K3 , K2,3 và đồ thị liên thông có một đỉnh cắt. Tiếp theo ta sẽ tìm hiểu kĩ hơn về đồ thị 2 - liên thông, lớp đồ thị vẫn giữ được tính 2 - liên thông khi ta thay thế một cạnh của đồ thị bằng một cặp cạnh khác. Đặc biệt nó có thể được phân tích thành hợp của các xích và đường. ĐỒ THỊ 2-LIÊN THÔNG Định nghĩa 1.3.2. Hai đường nối từ u đến v là rời nhau nếu chúng không có đỉnh trong chung.