Tính liên thông đỉnh, liên thông cạnh và các tính chất về bậc của đồ thị vô hướng (Luận văn thạc sĩ)Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (780.35 KB, 54 trang ) ĐẠI HỌC THÁI NGUYÊN GS.TS. TRẦN VŨ THIỆU THÁI NGUYÊN, 5/2018 iii Mục lục Danh mục các ký hiệu 1 Danh mục các hình vẽ 3 Mở đầu 5 1 KIẾN THỨC CHUẨN BỊ 8 1.1. KHÁI NIỆM ĐỒ THỊ . . . . . . . . . . . . . . . . . . . . . 8 1.1.1. Định nghĩa và các ký hiệu . . . . . . . . . . . . . . . 8 1.1.2. Phép toán trên đồ thị . . . . . . . . . . . . . . . . . 11 1.1.3. Đồ thị đẳng cấu . . . . . . . . . . . . . . . . . . . . . 12 1.1.4. Bậc của đỉnh trong đồ thị . . . . . . . . . . . . . . . 13 1.2. ĐƯỜNG ĐI VÀ CHU TRÌNH . . . . . . . . . . . . . . . . . 14 1.3. TÍNH LIÊN THÔNG CỦA ĐỒ THỊ . . . . . . . . . . . . . 17 1.4. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT . . . . . . . . . . . . 20 1.4.1. Đồ thị rỗng và đồ thị không . . . . . . . . . . . . . . 20 1.4.2. Rừng và cây . . . . . . . . . . . . . . . . . . . . . . . 20 1.4.3. Đồ thị đầy đủ . . . . . . . . . . . . . . . . . . . . . . 21 1.4.4. Đồ thị vòng, đồ thị đường và đồ thị bánh xe . . . . . 21 1.4.5. Đồ thị đều (đồ thị chính qui) . . . . . . . . . . . . . 22 1.4.6. Đồ thị hai phần . . . . . . . . . . . . . . . . . . . . . 23 1.4.7. Phần bù của đơn đồ thị . . . . . . . . . . . . . . . . 23 iv 2 LIÊN THÔNG ĐỈNH VÀ LIÊN THÔNG CẠNH CỦA ĐỒ THỊ 25 2.1. LIÊN THÔNG CẤP k GIỮA HAI ĐỈNH . . . . . . . . . . . 25 2.2. ĐỒ THỊ k - LIÊN THÔNG . . . . . . . . . . . . . . . . . . 30 2.3. ĐỈNH KHỚP . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.4. LIÊN THÔNG CẠNH CẤP GIỮA HAI ĐỈNH . . . . . . . 34 3 CÁC TÍNH CHẤT VỀ BẬC CỦA ĐỒ THỊ 39 3.1. DI CHUYỂN TRÊN ĐỒ THỊ . . . . . . . . . . . . . . . . . 39 3.2. ĐỒ THỊ ĐỒNG BẬC . . . . . . . . . . . . . . . . . . . . . . 40 3.3. BÁN NHÂN TỬ . . . . . . . . . . . . . . . . . . . . . . . . 42 3.4. TẬP HỢP TƯƠNG THÍCH LỚN NHẤT . . . . . . . . . . . 43 Kết luận 49 Tài liệu tham khảo 50 1 DANH MỤC CÁC KÝ HIỆU N Tập các số tự nhiên {1, 2, 3, ...} Z(Z+ ) Tập các số nguyên (Tập các số nguyên không âm) Q(Q+ ) Tập các số hữu tỉ (Tập các số hữu tỉ không âm) R(R+ ) Tập các số thực (Tập các số thực không âm) XY X là tập con thực sự của tập Y XY X là tập con (có thể bằng) của tập Y X Y Hợp của hai tập hợp X và Y X Y Giao của hai tập hợp X và Y X \Y Hiệu của tập hợp X và tập hợp Y X Hiệu đối xứng của hai tập hợp X và Y Y G Đồ thị (vô hướng hoặc có hướng) G Đồ thị bù của đồ thị G Đồ thị rỗng V (G), E(G) Tập đỉnh và tập cạnh của đồ thị G u = (i, j) Cạnh (hay cung) đi từ đỉnh i tới đỉnh j G[X] Đồ thị con của G cảm sinh bởi X V (G) Gv Đồ thị con của G cảm sinh bởi V (G) \ {v} Ge Đồ thị nhận được từ G do bỏ cạnh e khỏi G G|e Đồ thị nhận được từ G bằng cách co cạnh e thành một đỉnh G+e Đồ thị nhận được từ G do thêm cạnh e vào G 2 G+H Tổng của hai đồ thị G và H N (v) Tập các đỉnh kề với đỉnh v của đồ thị N (U ) Tập các đỉnh trong V \ U kề với các đỉnh thuộc U V E(X, Y ) Tập tất cả các cạnh xy của đồ thị sao cho x X, y Y d(v) Bậc của đỉnh v d(G) Bậc trung bình của đồ thị G δ(G) Bậc nhỏ nhất của đỉnh trong đồ thị G (G) Bậc lớn nhất của đỉnh trong đồ thị G Kn Đồ thị đầy đủ n đỉnh Km,n Đồ thị hai phần đầy đủ, mỗi phần có m và n đỉnh P[x,y] Một đoạn của đường đi P từ x tới y dist(u, v) Độ dài đường đi ngắn nhất từ u tới v µ Dây chuyền hay chu trình trên đồ thị 3 DANH MỤC CÁC HÌNH VẼ Hình 1.1. Sơ đồ khu phố Hình 1.2. Sơ đồ mạch điện Hình 1.3. Đồ thị: đỉnh, cạnh Hình 1.4. Đồ thị với 7 đỉnh và 5 cạnh Hình 1.5. Cạnh kép và đa đồ thị Hình 1.6. Khuyên trong đa đồ thị Hình 1.7. Đồ thị có hướng Hình 1.8. Đa đồ thị không liên thông Hình 1.9. Đồ thị G, cạnh e và các đồ thị G e và G \ e tương ứng Hình 1.10. Các đồ thị đẳng cấu với đồ thị ở Hình 1.3 Hình 1.11. Dây cung xy, vòng nhỏ = 4, vòng lớn = 8 Hình 1.12. Đường đi dài nhất [a0 , a1 , . . . , ak ] và các đỉnh kề ak Hình 1.13. Các đỉnh khớp và cầu e1 , e2 , e3 của đồ thị Hình 1.14. Đồ thị G1 , G2 và hợp G1 G2 Hình 1.15. Đồ thị không liên thông Hình 1.16. Ví dụ về rừng và cây Hình 1.17. Đồ thị đầy đủ K4 và K5 Hình 1.18. Đồ thị vòng C6 , đồ thị đường P6 và đồ thị bánh xe W6 Hình 1.19. Đồ thị Petersen (chính qui bậc 3) Hình 1.20. Đồ thị hai phần Hình 1.21. Đồ thị hai phần đầy đủ: K1,3 , K2,3 , K3,3 , K4,3 Hình 1.22. Phần bù của đơn đồ thị G 4 Hình 2.1. Đường đậm, đường yếu Hình 2.2. Không có đường yếu từ a tới b Hình 2.3. Đặt trạm kiểm soát thuyền bè đi từ vùng núi ra biển Hình 2.4. Tìm đường đi bắt đầu bằng u và tận cùng bằng v Hình 2.5. Tìm chu trình sơ cấp qua u và v Hình 2.6. Số liên thông đỉnh κ(G) và số liên thông cạnh (G) Hình 2.7. Bản đồ giao thông Hình 2.8. Đồ thị tương ứng Hình 3.1. Đường đi xen kẽ và chu trình xen kẽ Hình 3.2. Bán nhân tử và chu trình Haminton Hình 3.3. Ví dụ 3.2. 5 Mở đầu Các sơ đồ giao thông, sơ đồ mạng lưới thông tin hay sơ đồ tổ chức của một cơ quan, trường học đã khá quen thuộc với nhiều người. Đó là những hình ảnh sinh động và cụ thể của một khái niệm toán học trừu tượng khái niệm đồ thị (graph). Tuy nhiên, phải nhấn mạnh ngay là khái niệm đồ thị ở đây rất khác và không có liên quan gì tới khái niệm đồ thị của hàm số đã biết từ bậc phổ thông. Có thể hiểu đơn giản "đồ thị" là một cấu trúc toán học rời rạc, bao gồm hai yếu tố chính là đỉnh và cạnh cùng với mối quan hệ giữa chúng. Đồ thị là mô hình toán học cho nhiều vấn đề lý thuyết và thực tiễn đa dạng. Lý thuyết đồ thị đề cập tới nhiều vấn đề và bài toán có ý nghĩa thực tiễn thiết thực, cùng nhiều phương pháp xử lý và thuật toán giải độc đáo và hiệu quả, giúp ích cho sự phát triển tư duy toán học nói chung và khả năng vận dụng trong cuộc sống thường ngày nói riêng. Trong số đó đáng chú ý là các bài toán về giao thông, liên lạc. Ta xét một bài toán cụ thể như sau: Trong một mạng giao thông, hai địa điểm a và b trong mạng là liên thông khi nào có ít nhất một đường đi nối liền hai địa điểm ấy. Đương nhiên, số đường đi nối a với b càng nhiều thì mức độ liên thông càng cao. Chẳng hạn giữa hai thành phố càng có nhiều đường giao thông với nhau thì sự liên lạc càng thuận tiện. Nhận xét đơn giản này đưa đến một vấn đề quan trọng về lý luận cũng như thực tiễn: "đánh giá tính liên thông của một đồ thị". Để nâng cao khả năng tư duy toán học và tìm hiểu thêm các vấn đề toán học hiện đại, gần với ứng dụng, tôi chọn đề tài 6 "Tính liên thông đỉnh, liên thông cạnh và các tính chất về bậc của đồ thị vô hướng" Luận văn này có mục đích tìm hiểu và trình bày các kiến thức cơ bản về đồ thị và các kết quả lý thuyết, các định lý liên quan đến tính liên thông, các tính chất về bậc của đồ thị vô hướng và một số ví dụ ứng dụng cụ thể. Nội dung luận văn được tham khảo chủ yếu từ các tài liệu [1] - [6] và được trình bày trong ba chương. Cụ thể như sau. Chương 1 "Kiến thức chuẩn bị" nhắc lại một số khái niệm cơ bản về đồ thị: đỉnh và cạnh, đồ thị vô hướng, đồ thị có hướng, đồ thị đẳng cấu, đồ thị con, bậc của đỉnh và tính chất, đường đi và chu trình, đồ thị liên thông và không liên thông, các thành phần liên thông. Một số đồ thị đặc biệt: rừng và cây, đồ thị đầy đủ, đồ thị hai phần, đồ thị hai phần đầy đủ, đồ thị đều, đồ thị bù, . . . Chương 2 "Liên thông đỉnh và liên thông cạnh của đồ thị" trình bày các khái niệm về tính liên thông đỉnh, tính liên thông cạnh của một đồ thị và các định lý về điều kiện để đồ thị là k-liên thông đỉnh hay l-liên thông cạnh. Nêu một số ví dụ ứng dụng. Chương 3 "Các tính chất về bậc của đồ thị" trình bày một số kết quả về bậc của đồ thị và các phép biến đổi bảo toàn bậc của mọi đỉnh, đồ thị đồng bậc và tính chất, bán nhân tử (đồ thị con với mọi đỉnh có bậc hai) và chu trình Hamilton của đồ thị. Các kết quả này tạo cơ sở xây dựng thuật toán tìm tập hợp tương thích lớn nhất, ví dụ và ứng dụng. Do thời gian có hạn nên luận văn này chủ yếu chỉ dừng lại ở việc tìm hiểu, tập hợp tài liệu, sắp xếp và trình bày các kết quả nghiên cứu đã có theo chủ đề đặt ra. Trong quá trình viết luận văn cũng như trong soạn thảo, văn bản chắc chắn không tránh khỏi có những sai sót nhất định. Tác giả luận văn rất mong nhận được sự góp ý của các thầy cô và các bạn đồng nghiệp để luận văn được hoàn thiện hơn. Nhân dịp này, tác giả xin bày tỏ lòng biết ơn sâu sắc tới thầy hướng 7 dẫn GS.TS. Trần Vũ Thiệu đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Tác giả cũng xin chân thành cảm ơn các GS, PGS, TS của Khoa Toán - Tin, Trường Đại học Khoa học Thái Nguyên đã giảng dạy và tạo mọi điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu. Thái Nguyên, ngày 02 tháng 5 năm 2018 Tác giả luận văn Nguyễn Thị Phương 8 Chương 1 KIẾN THỨC CHUẨN BỊ Chương này trình bày một số kiến thức cơ bản thường dùng trong lý thuyết đồ thị: các khái niệm đỉnh, cạnh, đồ thị vô hướng, các phép toán trên đồ thị, bậc của đỉnh và tính chất, đường đi và chu trình, đồ thị liên thông và đồ thị không liên thông. Cuối chương mô tả một số dạng đồ thị thường gặp. Nội dung của chương được tham khảo chủ yếu từ các tài liệu [1], [4] và [5]. 1.1. 1.1.1. KHÁI NIỆM ĐỒ THỊ Định nghĩa và các ký hiệu Trong thực tế ta thường gặp các sơ đồ giao thông (Hình 1.1) hay sơ đồ mạch điện (Hình 1.2). Các sơ đồ này được khái quát thành sơ đồ vẽ ở Hình 1.3. Từ đó ta đi tới định nghĩa sau. 9 Đồ thị (graph) là một tập hợp hữu hạn và khác rỗng các điểm, gọi là các đỉnh (vertex) hay nút (node) và một tập hợp các đoạn (thẳng hay cong) nối liền một số cặp điểm này, gọi là các cạnh (edge) của đồ thị (Số cạnh có thể bằng 0). Mỗi đỉnh của đồ thị thường được ký hiệu bằng một chữ cái ( a, b, c, ... hay A, B, C, ...) hoặc chữ số (1, 2, 3, ...). Cạnh nối liền đỉnh a với đỉnh b được ký hiệu là (a, b) hay đơn giản là ab (a và b có thể là các chữ số). Một cạnh có dạng (a, a), nối đỉnh a với chính nó, gọi là một khuyên (loop). Nếu đồ thị G có tập đỉnh là V và tập cạnh là E V × V (nghĩa là mỗi phần tử của E là một cặp gồm hai phần tử của V ) thì để cho gọn, ta viết G = (V, E). Ta cũng dùng ký hiệu V (G) để chỉ tập đỉnh và E(G) để chỉ tập cạnh của đồ thị G. Ký hiệu n = |V (G)| là số đỉnh và m = |E(G)| là số cạnh của đồ thị G. Đồ thị gọi là hữu hạn (finite), vô hạn hay đếm được là tùy theo số đỉnh của nó là hữu hạn, vô hạn hay đếm được. Luận văn này chỉ xét các đồ thị hữu hạn. Để dễ hình dung, mỗi đồ thị thường được biểu diễn bởi một hình vẽ trên mặt phẳng, bằng cách vẽ các điểm thay cho các đỉnh và nối hai điểm bằng một đoạn thẳng (hay cong), nếu hai đỉnh tương ứng thì sẽ tạo nên một cạnh. Chẳng hạn, Hình 1.3 biểu diễn một đồ thị có 5 đỉnh: P, Q, R, S, T và 8 cạnh (mỗi cạnh là một đoạn thẳng nối hai đỉnh). Chú ý rằng điểm giao nhau của hai cạnh P S và QT trong hình vẽ không phải là một đỉnh của đồ thị. Hình 1.4 biểu diễn một đồ thị có 7 đỉnh (các đỉnh được đánh số từ 1 tới 7) và 5 cạnh (đã liệt kê ở hình vẽ). 10 Đỉnh u gọi là kề đỉnh v nếu có một cạnh của đồ thị nối u với v. Nếu ký hiệu cạnh này là e thì ta viết e = (u, v) và nói cạnh e liên thuộc (incident) u, v hay u, v là hai đỉnh mút (endvertices) hay hai đầu mút (ends) của e và ta nói cạnh e nối (join) hai đầu mút của nó. Cạnh e và e gọi là kề nhau nếu e, e có chung đỉnh. Cạnh (u, v) thường được viết gọn thành uv (hoặc vu). Tập hợp tất cả các cạnh uv E sao cho u X và v Y được ký hiệu là E(X, Y ). Hai cạnh e và e cùng nối một cặp đỉnh gọi là cạnh kép (multiple edge). Đồ thị không có cạnh kép gọi là một đơn đồ thị (simple graph). Trái lại, gọi là một đa đồ thị. Hình 1.5 và 1.6 minh họa cạnh kép và khuyên trong đa đồ thị. Hai đỉnh hay hai cạnh không kề nhau gọi là độc lập (independent). Cũng vậy, một tập hợp đỉnh hay cạnh gọi là độc lập nếu tập đó không chứa hai 11 phần tử nào kề nhau. Các tập đỉnh độc lập còn được gọi là các tập ổn định (stable set). Một cạnh của đồ thị gọi là cạnh có hướng (directed edge) nếu có qui định rõ một đầu mút của cạnh là đỉnh đầu, mút kia là đỉnh cuối. Cạnh có hướng còn được gọi là một cung. Một đồ thị gồm toàn các cạnh gọi là đồ thị vô hướng (undirected graph), đồ thị gồm toàn các cung gọi là đồ thị có hướng (digraph). Một đồ thị vừa có cạnh vừa có cung gọi là đồ thị hỗn hợp (mixed graph). Bằng cách thay một cạnh bởi hai cung có hướng ngược chiều nhau, ta có thể qui mọi đồ thị về đồ thị có hướng. Hình.1.7 mô tả một đồ thị có hướng. 1.1.2. Phép toán trên đồ thị Sau đây ta chủ yếu xét các đồ thị vô hướng và một số phép toán trên đồ thị. Đồ thị con hay đồ thị bộ phận (subgraph) của một đồ thị G là đồ thị nhận được từ G bằng cách bỏ đi một số đỉnh và một số cạnh của nó. Nói chính xác, H = (V (H), E(H)) là một đồ thị con của G nếu V (H) V (G) và E(H) E(G). Ta cũng nói G chứa H. H gọi là đồ thị con cảm sinh (induced subgraph) của G nếu H là một đồ thị con của G và E(H) = {(x, y) E(G) : x, y V (H)} Ở đây H là đồ thị con của G sinh bởi V (H). Vì thế ta còn viết H = G[V (H)]. Đồ thị con H của G gọi là đồ thị con bao trùm (spanning subgraph) nếu V (H) = V (G), tức là tập đỉnh của H và của G trùng nhau. 12 Bỏ đỉnh: Với v V (G), ký hiệu G v là đồ thị con của G cảm sinh bởi V (G) \ {v}, tức là đồ thị nhận được từ G bằng cách bỏ đỉnh v và các cạnh liên thuộc v. Xóa cạnh và co cạnh: Với e E(G), ta định nghĩa G e := (V (G), E(G) \ {e}), tức là đồ thị nhận được từ G bằng cách xóa cạnh e (không xóa hai đầu mút của e). Ta cũng định nghĩa G \ e là đồ thị nhận được bằng cách co cạnh e thành một đỉnh duy nhất. Hình 1.9 minh họa các đồ thị G, G e và G \ e. Tương tự, ký hiệu G + e = (V (G), E(G) {e}) là đồ thị nhận được khi thêm vào G một cạnh mới e. Cho hai đồ thị tuỳ ý G và H, ta ký hiệu G + H là đồ thị với tập đỉnh V (G + H) = V (G) V (H) và tập cạnh E(G + H) là hợp rời nhau của E(G) và E(H) (có thể xuất hiện cạnh kép). 1.1.3. Đồ thị đẳng cấu Hai đồ thị G1 và G2 gọi là đẳng cấu (isomorphic) nếu chúng có số đỉnh và số cạnh như nhau và có phép tương ứng một - một giữa tập đỉnh của G1 và G2 sao cho hai đỉnh được nối với nhau bởi một cạnh trong đồ thị này khi và chỉ khi hai đỉnh tương ứng trong đồ thị kia cũng được nối với nhau bởi một cạnh và ngược lại. Hình 1.10 vẽ các đồ thị đẳng cấu với đồ thị vẽ ở Hình 1.3. Các cạnh của hai đồ thị ở Hình 1.10 chỉ gặp nhau ở đỉnh. Các đồ thị đẳng cấu được xem là tương đương (cùng biểu diễn một đồ thị). 13 1.1.4. Bậc của đỉnh trong đồ thị Cho một đồ thị khác rỗng G = (V, E). Tập các đỉnh kề với đỉnh v trong G được ký hiệu là NG (v) hay đơn giản là N (v). Tổng quát, với tập con U V thì các đỉnh trong V \ U kề với các đỉnh thuộc U được gọi là các đỉnh lân cận (neighbours) của U , ký hiệu là N (U ). Bậc (degree) của đỉnh v trong đồ thị vô hướng G là số cạnh hay số đỉnh kề v (tức d(v) := |N (v)|), ký hiệu là d(v). Đỉnh có bậc 0 gọi là đỉnh cô lập (isolate), đỉnh có bậc 1 gọi là đỉnh treo (end-vertex). Tương tự, trong đồ thị có hướng ta gọi bậc ra (bậc vào) của đỉnh v là số cung đi khỏi v (số cung đi tới v), ký hiệu tương ứng là d+ (v) và d (v). Qui ước: khuyên tại một đỉnh được tính 2 lần. Ví dụ trong đồ thị vẽ ở Hình 1.8 ta có d(P ) = d(S) = d(U ) = d(V ) = 2; d(Q) = d(R) = 3 và d(T ) = 4 (có khuyên ở T ). Nếu mọi đỉnh của đồ thị G đều có bậc k thì G gọi là đồ thị đều bậc k hay đồ thị k - chính quy (k - regular). Đồ thị đều bậc 3 gọi là đồ thị lập phương (cubic) Dễ dàng chứng minh các tính chất sau đây về bậc của đỉnh trong đồ thị: a) Trong một đồ thị vô hướng, tổng số bậc của mọi đỉnh bằng hai lần số cạnh của đồ thị và số đỉnh có bậc lẻ bao giờ cũng là một số chẵn. b) Trong một đồ thị có hướng, tổng các bậc vào của mọi đỉnh bằng tổng các bậc ra của mọi đỉnh và bằng tổng số cung trong đồ thị. Nhiều tính chất của đồ thị có hướng không phụ thuộc vào hướng các cung trong đồ 14 thị. Vì thế, khi bỏ qua hướng trên các cung (đổi cung thành cạnh) ta sẽ nhận được một đồ thị vô hướng, gọi là đồ thị nền của đồ thị có hướng đã cho. Cùng với bậc của đỉnh, ta còn dùng các khái niệm sau: Số δ(G) := min{d(v)|v V } gọi là bậc nhỏ nhất (minimum degree) của G, số (G) := max{d(v)| V } gọi là bậc lớn nhất (maximum degree) của G và bậc trung bình (average degree) của G là số d(G) := 1 |V | d(v) = 2m/n (n = |V (G)| , m = |E(G)|). vV Rõ ràng là δ(G) d(G) (G). Với đồ thị vẽ ở Hình 1.4 thì δ(G) = 0, (G) = 3 và d(G) = 10/7 1, 43. 1.2. ĐƯỜNG ĐI VÀ CHU TRÌNH Đường đi (path) P từ đỉnh u tới đỉnh v là một dãy liên tiếp các cạnh có dạng (a0 , a1 ), (a1 , a2 ), ... , (ak1 , ak ) với (ai1 , ai ) E(G), a0 = u, ak = v và k 1 Để đơn giản, đôi khi ta viết P = [a0 , a1 , ..., ak ] và nói đó là đường đi nối đỉnh u và đỉnh v. Đỉnh u gọi là đỉnh đầu, đỉnh v gọi là đỉnh cuối của P . Một đường đi nối một đỉnh với chính nó (đỉnh đầu trùng với đỉnh cuối) gọi là một chu trình (cycle). Độ dài (length) của đường đi (chu trình) thông thường được định nghĩa là số cạnh của đường đi (chu trình) đó. Ví dụ: đồ thị ở Hình 1.10 có đường nối đỉnh P và đỉnh S là [P, T, Q, R, S] với độ dài 4 và có các chu trình [P, Q, R, S, T, P ], [P, S, T, P ] với độ dài lần lượt là 5 và 3, v.v ... Một đường đi (nói riêng chu trình) được gọi là sơ cấp, nếu nó không đi qua đỉnh nào hai lần trở lên, đơn giản nếu nó không đi qua cạnh nào hai lần trở lên. Các đường đi trong đồ thị nối đỉnh u và đỉnh v = u gọi là tách biệt hay độc lập (independent) nếu từng đôi một chúng không có 15 đỉnh chung nào khác u và v. Độ dài nhỏ nhất của chu trình trong đồ thị G gọi là vòng nhỏ (girth) của G, ký hiệu g(G). Độ dài lớn nhất của chu trình trong G gọi là vòng lớn hay chu vi (circumference) của G. Nếu đồ thị không chứa chu trình thì đặt vòng nhỏ g(G) = và vòng lớn bằng 0. Một cạnh nối hai đỉnh của một chu trình sơ cấp và không thuộc chu trình là một dây cung (chord) của chu trình đó. Mệnh đề sau cho thấy một đồ thị có bậc nhỏ nhất lớn (tức δ(G) lớn) thì nó có đường đi và chu trình dài. Mệnh đề 1.1 Mọi đồ thị G chứa một đường đi (sơ cấp) với độ dài δ(G) và một chu trình (sơ cấp) với độ dài ít nhất δ(G)+1 (với điều kiện δ(G) 2). Chứng minh. Giả sử [a0 , a1 , ..., ak ] là đường đi sơ cấp dài nhất trong G. Khi đó, mọi đỉnh kề đỉnh cuối ak đều nằm trên đường đi này (Hình 1.12). Do đó k d(ak ) δ(G). Nếu i < k là chỉ số nhỏ nhất sao cho cạnh ai ak E(G) thì [ai , ..., ak , ai ] là chu trình với độ dài ít nhất bằng δ(G) + 1. Khoảng cách (distance) giữa hai đỉnh x và y trong G, ký hiệu dG (x, y), được định nghĩa là độ dài đường đi ngắn nhất trong G nối x và y. Nếu không có đường đi như thế thì đặt dG (x, y) = . Khoảng cách lớn nhất 16 giữa hai đỉnh bất kỳ trong G gọi là đường kính (diameter) của G, ký hiệu là diam(G). Đường kính và vòng nhỏ có mối liên hệ như sau. Mệnh đề 1.2 Mọi đồ thị G chứa chu trình thỏa mãn g(G) 2 × diam(G) + 1 Chứng minh. Giả sử C là một chu trình ngắn nhất trong G, tức C có độ dài g(G). Nếu như g(G) 2 × diam(G) + 2 thì C có hai đỉnh với khoảng cách trong C ít nhất bằng diam(G) + 1. Trong G hai đỉnh này có khoảng cách nhỏ hơn (vì theo định nghĩa diam(G) là khoảng cách lớn nhất giữa hai đỉnh bất kỳ trong G); vì thế bất kỳ đường đi ngắn nhất P trong G nối hai đỉnh ấy không thể là một đồ thị bộ phận của C. Do vậy P chứa một đường đi có tính chất: 1) Nối hai đỉnh nào đó x và y thuộc C; 2) Đường đi ấy gồm toàn các cạnh không thuộc C. Kết hợp đường đi này với đường đi ngắn hơn trong C nối x và y, ta nhận được một chu trình mới ngắn hơn so với chu trình C và gặp mâu thuẫn! Một đỉnh là tâm (central) của đồ thị G nếu khoảng cách xa nhất từ một đỉnh bất kỳ khác tới nó là nhỏ nhất. Khoảng cách này là bán kính (radius) của G, ký hiệu là rad(G). Như vậy, rad(G) := minxV (G) maxyV (G) dG (x, y) . Có thể thấy rad(G) diam(G) 2 × rad(G). Nếu không để ý tới số đỉnh của đồ thị thì bán kính và đường kính của đồ thị không có liên hệ gì tới bậc nhỏ nhất, bậc trung bình và bậc lớn nhất của đồ thị. Tuy nhiên, mệnh đề sau đây cho thấy rằng các đồ thị có đường kính lớn và bậc nhỏ nhất lớn sẽ có nhiều đỉnh (số đỉnh lớn) và các đồ thị có đường kính nhỏ và bậc lớn nhất nhỏ sẽ có ít đỉnh (số đỉnh nhỏ). Mệnh đề 1.3 a) Một đồ thị với đường kính k và bậc nhỏ nhất d sẽ có ít nhất khoảng kd/3 đỉnh (k, d lớn thì số đỉnh sẽ lớn). 17 b) Đồ thị G với bán kính k và bậc lớn nhất d (d 3) sẽ có không quá d(d 1)k /(d 2) đỉnh (k, d nhỏ thì số đỉnh sẽ nhỏ). 1.3. TÍNH LIÊN THÔNG CỦA ĐỒ THỊ Một đồ thị (hay đa đồ thị) vô hướng G gọi là liên thông (connected) nếu có đường đi trong G nối hai đỉnh bất kỳ của đồ thị. Trái lại, đồ thị gọi là không liên thông (disconnected). Đồ thị không liên thông sẽ bị tách thành một số đồ thị con liên thông, đôi một không có đỉnh chung. Mỗi đồ thị con liên thông như thế gọi là một thành phần liên thông (connected component). Đôi khi ta đồng nhất thành phần liên thông với tập đỉnh của nó. Tập đỉnh X được gọi là liên thông nếu đồ thị con sinh bởi X là liên thông. Ví dụ: đồ thị vẽ ở Hình 1.6 là liên thông, trong khi đó đồ thị vẽ ở Hình 1.8 là không liên thông (gồm 2 thành phần liên thông). Định nghĩa 1.1 Đỉnh v gọi là đỉnh khớp (cut vertex) nếu đồ thị Gv (bỏ khỏi G đỉnh v và các cạnh liên thuộc v) có nhiều thành phần liên thông hơn G. Định nghĩa 1.2 Cạnh e gọi là một cầu (bridge) nếu đồ thị G e (xóa khỏi G cạnh e, không xóa hai đầu mút) có nhiều thành phần liên thông hơn G. Đỉnh khớp (tô đậm) và cầu e1 , e2 , e3 của đồ thị được minh họa ở Hình 1.13. 18 Trong đồ thị có hướng có các khái niệm liên thông yếu và liên thông mạnh, tuy nhiên ta sẽ không đi sâu tìm hiểu các khái niệm này. Mệnh đề 1.4 Đồ thị vô hướng G là liên thông khi và chỉ khi N (X) = với mọi = X V (G) (N (X) - tập đỉnh trong V (G) \ X kề với các đỉnh thuộc X). Mệnh đề 1.5 Các đỉnh của một đồ thị liên thông G có thể được đánh số, chẳng hạn v1 , ..., vn , sao cho đồ thị con cảm sinh Gi = G[v1 , ..., vi ] là liên thông với mọi i = 1, ... , n. Chứng minh. Chọn trong G một đỉnh bất kỳ v1 và giả thiết rằng v1 , ..., vi với 1 i < n đã được chọn sao cho G1 , ..., Gi là liên thông. Bây giờ ta chọn một đỉnh v / Vi = {v1 , ..., vi }. Do G liên thông nên trong G có đường đi P nối v và v1 . Chọn vi+1 là đỉnh cuối cùng / Vi trên đường đi P theo chiều từ v đến v1 ; khi đó vi+1 là đỉnh kề với một đỉnh nào đó trong Gi và Gi+1 là liên thông. Từ nguyên lý qui nạp suy ra mọi đồ thị con cảm sinh Gi , i = 1, ..., n là liên thông. Ví dụ đồ thị vẽ ở Hình 1.10 có thể đánh số các đỉnh theo thứ tự P, Q, R, S, T và rõ ràng các đồ thị con cảm sinh [P ], [P, Q], [P, Q, R], [P, Q, R, S] và [P, Q, R, S, T ] là liên thông. Có thể hiểu đồ thị liên thông theo nghĩa tương đương như sau. Ghép hai đồ thị để lập nên một đồ thị lớn hơn: Cho G1 = (V (G1 ), E(G1 )), G2 = (V (G2 ), E(G2 )) với V (G1 ) V (G2 ) = . Khi đó, hợp (union) G1 G2 là đồ thị có tập đỉnh là V (G1 ) V (G2 ) và tập cạnh là E(G1 ) E(G2 ) (Hình 1.14). 19 Hầu hết các đồ thị thường gặp là đồ thị ghép. Một đồ thị được gọi là liên thông nếu nó không biểu diễn được dưới dạng hợp của hai hay nhiều đồ thị. Trái lại, đồ thị gọi là không liên thông. Rõ ràng là bất cứ một đồ thị không liên thông G nào cũng biểu diễn được dưới dạng hợp của các đồ thị liên thông, mỗi đồ thị liên thông đó gọi là một thành phần liên thông của G. Chẳng hạn, một đồ thị gồm ba thành phần liên thông được vẽ ở Hình 1.15. Khi cần chứng minh một kết luận nào đó cho các đồ thị nói chung, ta thường chứng minh kết quả tương ứng cho các đồ thị liên thông, sau đó áp dụng kết quả thu được cho từng thành phần liên thông riêng lẻ của đồ thị. Mọi đồ thị liên thông với n > 1 đỉnh đều có độ liên thông k = 1. Đôi khi ta quan tâm tới độ liên thông cao hơn, giả sử k 2 . Một đồ thị vô hướng gồm hơn k đỉnh gọi là k - liên thông (k - connected) hay có độ liên thông bằng k, nếu bỏ ít hơn k đỉnh bất kỳ thì đồ thị vẫn còn liên thông. Đồ thị vô hướng gồm ít nhất hai đỉnh gọi là k - liên thông cạnh (k edge connected) hay có độ liên thông cạnh bằng k, nếu bỏ ít hơn k cạnh bất kỳ mà đồ thị vẫn còn liên thông. Như vậy, một đồ thị liên thông bất kỳ với ít nhất ba đỉnh là 2 - liên thông (2 - liên thông cạnh) khi và chỉ khi đồ thị không có đỉnh khớp (cầu). Vấn đề này sẽ được đề cập kỹ hơn ở chương sau. 20 1.4. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT Mục này trình bày một số dạng đồ thị đặc biệt, đáng chú ý và hay được dùng trong lý thuyết đồ thị và trong các ứng dụng. 1.4.1. Đồ thị rỗng và đồ thị không Đồ thị không có đỉnh và cạnh nào gọi là đồ thị rỗng (empty graph) và được ký hiệu gọn là . Đồ thị rỗng hoặc gồm duy nhất một đỉnh gọi là đồ thị tầm thường (trivial graph), chúng thường được dùng trong chứng minh qui nạp hoặc để xây dựng các phản ví dụ. Một đồ thị có đỉnh, nhưng không có cạnh nào (tập cạnh rỗng) gọi là một đồ thị không (null graph). Đồ thị không n đỉnh được ký hiệu là Nn . Mọi đỉnh của đồ thị không đều là các đỉnh cô lập (đỉnh bậc 0). 1.4.2. Rừng và cây Một đồ thị vô hướng không có chu trình gọi là một rừng (forest). Một rừng liên thông gọi là một cây (tree), tức cây là một đồ thị liên thông và không chứa chu trình. Ví dụ phả hệ của một họ tộc là một cây (cây phả hệ). Rừng có thể gồm nhiều thành phần liên thông khác nhau, mỗi thành phần liên thông là một cây. Như vậy, rừng gồm nhiều cây. Đỉnh có bậc 1 trong cây gọi là một lá (leaf). Đồ thị hình sao là một cây có duy nhất một đỉnh không phải là lá (Hình 1.16c). Một đồ thị con, không chứa chu trình của đồ thị G gọi là một cây của G. Một đồ thị con bao trùm của G mà là một cây được gọi là một cây bao trùm (spanning tree) của G. Một số tính chất đặc trưng của cây: cây n đỉnh có đúng n 1 cạnh, trong một cây, bao giờ cũng có một đường đi duy nhất nối một cặp đỉnh bất kỳ của cây. Các ví dụ về rừng và cây được vẽ ở Hình 1.16. 21 1.4.3. Đồ thị đầy đủ Một đơn đồ thị trong đó mọi cặp đỉnh (khác nhau) đều kề nhau, gọi là một đồ thị đầy đủ (completed graph). Đồ thị đầy đủ n đỉnh ký hiệu là Kn . Số cạnh của Kn bằng n(n 1)/2. Đồ thị K4 và K5 được vẽ ở Hình 1.17. 1.4.4. Đồ thị vòng, đồ thị đường và đồ thị bánh xe Một đồ thị liên thông và mọi đỉnh bậc 2 gọi là một đồ thị vòng (cycle graph). Ký hiệu đồ thị vòng n đỉnh là Cn . Đồ thị nhận được từ Cn bằng cách bỏ đi một cạnh bất kỳ gọi là một đồ thị đường (path graph) n đỉnh, ký hiệu là Pn . Đồ thị nhận được từ Cn1 bằng cách thêm vào một đỉnh v và nối v với mỗi đỉnh của Cn1 bởi một cạnh, gọi là một đồ thị bánh xe (wheel) n đỉnh, ký hiệu là Wn . |
