Luận văn Thạc sĩ Toán học: 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

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————–

NGUYỄN THỊ PHƯƠNG

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Ĩ TOÁN HỌC

THÁI NGUYÊN - 2018

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————–

NGUYỄN THỊ PHƯƠNG

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

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 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

8 1.1. KHÁI NIỆM ĐỒ THỊ . . . . . . . . . . . . . . . . . . . . .

8 1.1.1. Định nghĩa và các ký hiệu . . . . . . . . . . . . . . .

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 (cid:96) 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

Tập các số tự nhiên {1, 2, 3, ...}

Tập các số nguyên (Tập các số nguyên không âm)

Tập các số hữu tỉ (Tập các số hữu tỉ không âm)

Tập các số thực (Tập các số thực không âm)

N Z(Z+) Q(Q+) R(R+) X ⊂ Y X là tập con thực sự của tập Y

X ⊆ Y 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 (cid:52) Y Hiệu đối xứng của hai tập hợp X và Y

G Đồ thị (vô hướng hoặc có hướng)

Đồ thị bù của đồ thị G

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)

G − v Đồ thị con của G cảm sinh bởi V (G) \ {v}

G − e Đồ 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

Tổng của hai đồ thị G và H G + H

Tập các đỉnh kề với đỉnh v của đồ thị N (v)

Tập các đỉnh trong V \ U kề với các đỉnh thuộc U ⊂ V N (U )

E(X, Y ) Tập tất cả các cạnh xy của đồ thị sao cho x ∈ X, y ∈ Y

Bậc của đỉnh v d(v)

Bậc trung bình của đồ thị G d(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 (cid:52)(G)

Đồ thị đầy đủ n đỉnh

Đồ thị hai phần đầy đủ, mỗi phần có m và n đỉnh

Một đoạn của đường đi P từ x tới y

Độ dài đường đi ngắn nhất từ u tới v Kn Km,n P[x,y] dist(u, 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 (cid:96)(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.1. KHÁI NIỆM ĐỒ THỊ

[1], [4] và [5].

1.1.1. Đị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(cid:48) gọi là kề nhau nếu e, e(cid:48) 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(cid:48) 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ố (cid:52)(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(v) = 2m/n (n = |V (G)| , m = |E(G)|). d(G) := 1 |V | (cid:80) v∈V

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.2. ĐƯỜNG ĐI VÀ CHU TRÌNH

1, 43.

Đườ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), ... , (ak−1, ak) với (ai−1, 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 (cid:54)= 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 aiak ∈ 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) := minx∈V (G) (cid:8)maxy∈V (G)dG(x, y)(cid:9) .

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

1.3. TÍNH LIÊN THÔNG CỦA ĐỒ THỊ

quá d(d − 1)k/(d − 2) đỉnh (k, d nhỏ thì số đỉnh sẽ nhỏ).

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ị G−v (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) (cid:54)= ∅ với mọi ∅ (cid:54)= 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ừ Cn−1 bằng cách thêm vào một đỉnh v và nối v với mỗi đỉnh của Cn−1 bởi một cạnh, gọi là một đồ thị bánh xe (wheel) n đỉnh, ký hiệu là Wn.

22

1.4.5. Đồ thị đều (đồ thị chính qui)

Một đồ thị mà mọi đỉnh có bậc bằng nhau gọi là một đồ thị đều hay đồ

thị chính qui (regular graph). Nếu mọi đỉnh có bậc r thì đồ thị được gọi

là đồ thị đều (chính qui) bậc r hoặc r - chính qui. Có tầm quan trọng đặc

biệt là các đồ thị bậc 3 (cubic graph), tức các đồ thị đều (chính qui) bậc

3.

Một ví dụ điển hình về đồ thị bậc 3 là đồ thị Petersen (Petersen graph),

đồ thị này được vẽ ở Hình 1.19. Chú ý rằng đồ thị không Nn là đồ thị chính qui bậc 0, đồ thị vòng Cn là đồ thị chính qui bậc 2 và đồ thị đầy đủ Kn là đồ thị chính qui bậc n - 1.

23

1.4.6. Đồ thị hai phần

Nếu tập đỉnh của đồ thị có thể chia tách thành hai tập rời nhau A và

B sao cho mỗi cạnh của G nối một đỉnh thuộc A với một đỉnh thuộc B,

thì G được gọi là một đồ thị hai phần (bipartite graph) (Hình 1.20). Nói

một cách khác, đồ thị hai phần là đồ thị mà có thể tô các đỉnh của nó

bằng hai màu đen và trắng sao cho mỗi cạnh nối một đỉnh đen (trong A)

và một đỉnh trắng (trong B).

Có thể chứng minh rằng đơn đồ thị G là đồ thị hai phần khi và chỉ khi

mọi chu trình trong G đều có độ dài (số cạnh) chẵn.

Đồ thị hai phần đầy đủ (complete bipartite graph) là một đồ thị hai

phần mà mỗi đỉnh trong A được nối với mỗi đỉnh trong B bằng đúng một

cạnh. Ta ký hiệu đồ thị hai phần đầy đủ có r đỉnh đen và s đỉnh trắng

là Kr,s. Các đồ thị K1,3, K2,3, K3,3 và K4,3 được vẽ ở Hình 1.21. Dễ dàng kiểm tra lại rằng Kr,s có (r + s) đỉnh và r × s cạnh.

1.4.7. Phần bù của đơn đồ thị

Nếu G là một đơn đồ thị với tập đỉnh V (G), thì phần bù (complement)G

của G là một đơn đồ thị, với cùng tập đỉnh V (G) và hai đỉnh kề nhau trong

G khi và chỉ khi chúng không kề nhau trong G. Chẳng hạn, Hình 1.22 vẽ

đồ thị G và phần bù G của nó. Có thể thấy rằng phần bù của một đồ thị

24

đầy đủ là một đồ thị không và phần bù của một đồ thị hai phần đầy đủ

là hợp của 2 đồ thị đầy đủ.

Kết luận chương. Chương này đã đề cập tới các khái niệm cơ bản

về đồ thị: đỉnh, cạnh, bậc của đỉnh, đồ thị vô hướng và đồ thị có hướng,

đường đi và chu trình, đồ thị liên thông và không liên thông. Trình bày

các phép toán thường dùng trên đồ thị (thêm, bớt đỉnh hoặc cạnh). Miêu

tả nhiều dạng đồ thị đặc biệt: rừng và cây, đồ thị hình sao, đồ thị vòng,

đồ thị bánh xe, đồ thị đầy đủ, đồ thị hai phần, đồ thị hai phần đầy đủ, đồ

thị đều, ...

25

Chương 2

LIÊN THÔNG ĐỈNH VÀ LIÊN

THÔNG CẠNH CỦA ĐỒ THỊ

Chương này trình bày khái niệm liên thông cấp k giữa hai đỉnh của một

đồ thị và tính chất (định lý Menger), đồ thị k - liên thông và tính chất

(định lý Whitney), đặc biệt lưu ý tính chất của các đồ thị 2 - liên thông.

Cuối chương xét tính liên thông cạnh cấp (cid:96) giữa hai đỉnh và tính chất. Nội

2.1. LIÊN THÔNG CẤP k GIỮA HAI ĐỈNH

dung của chương được tham khảo chủ yếu từ các tài liệu [2], [4] và [5].

Theo định nghĩa ở Chương 1, hai đỉnh a và b của một đồ thị là liên

thông khi nào có ít nhất một đường đi nối liền hai đỉnh ấ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á mức độ liên thông của một

đồ thị.

Cho a, b là hai đỉnh khác nhau của một đồ thị vô hướng G = (A, U )

với tập đỉnh A và tập cạnh U . Để thuận tiện, ta nhắc lại: một đường đi

từ a tới b là đường đi sơ cấp (elementary path) nếu đường đi đó không đi

qua đỉnh nào hai lần trở lên và một số đường đi nối a với b là tách biệt

26

(separable) nếu từng đôi một chúng không có đỉnh chung nào khác a và b.

Định nghĩa 2.1 Hai đỉnh a và b của đồ thị G gọi là liên thông cấp k trong

G nếu k là số tối đa đường đi sơ cấp và tách biệt nối a với b, nghĩa là nếu:

1) có k đường đi sơ cấp, tách biệt nối a với b;

2) không có k + 1 đường đi như thế.

Định lý 2.1 (Menger, 1927). Muốn cho hai đỉnh a, b không kề nhau

của một đồ thị là liên thông cấp k, điều kiện cần và đủ là

1) có k đỉnh, khác a và b, sao cho khi rút đi tất cả các đỉnh ấy thì a và

b bị tách rời hoàn toàn (không còn liên thông nữa);

2) không có k − 1 đỉnh như thế.

Nói cách khác, đối với hai đỉnh a, b không kề nhau thì số tối đa đường

đi sơ cấp, tách biệt, nối a với b bằng số tối thiểu đỉnh, khác a và b, mà cần

rút đi để tách rời được a với b.

Chứng minh. Giả sử hai đỉnh không kề nhau a và b là liên thông cấp

k, và µ1, µ2, ..., µk là k đường đi sơ cấp, tách biệt, nối a với b. Nếu ta chỉ rút đi k − 1 đỉnh (khác a và b), thì chúng chỉ có thể phá mất nhiều nhất là

k − 1 đường đi nói trên, và vẫn còn ít nhất một dây chuyền không bị đụng

chạm đến, cho nên a và b vẫn còn liên thông. Do đó, chỉ rút k − 1 đỉnh

thì không đủ tách rời a và b. Ta sẽ chứng minh rằng chọn đúng k đỉnh để

tách rời được hoàn toàn a với b.

Tạm gọi các đường đi µ1, µ2, ..., µk là "đường đậm" và các cạnh hay đỉnh của chúng là cạnh hay đỉnh "đậm". Đi trên mỗi đường đậm, từ a tới b, ta

vẽ trên mỗi cạnh của nó một mũi tên hướng theo chiều đi ấy (Hình 2.1).

Một đường đi v từ một đỉnh e tới một đỉnh f sẽ gọi là một đường "yếu"

khi nào nó có điều kiện sau đây: hễ v đi qua một đỉnh đậm khác e và f

thì nó phải chứa một cạnh đậm liên thuộc đỉnh ấy, và mỗi cạnh đậm trên

v (nếu có) đều hướng theo chiều ngược lại với chiều đi trên v từ e tới f (ví

dụ, trong Hình 2.1, đường đi [e, g1, g2, f ] là yếu).

27

Trước hết, có thể thấy rằng không có một đường yếu nào đi từ a tới b.

Thật vậy, giả sử có một đường yếu v như thế (đường chấm chấm trong

Hình 2.2).

Sau khi bỏ đi những chu trình của v (nếu có), có thể cho rằng v là một

đường đi sơ cấp. Theo giả thiết, không thể có k + 1 đường đi sơ cấp tách

biệt nối a với b, vậy v phải có đỉnh chung với một số đường đậm, và do

đó, theo định nghĩa đường yếu, v phải có chứa những cạnh đậm.

Cho µi1, µi2, ..., µih là tất cả những đường đậm có những cạnh chung với v. Ta hãy bỏ tất cả những cạnh đậm ở trên v, đồng thời vẽ trên những

cạnh còn lại của v một mũi tên hướng theo chiều đi trên v từ a tới b, rồi

xét đồ thị H tạo nên bởi các đường đi µi1, µi2, ..., µih, v (không kể các cạnh đậm trên v). Trong đồ thị H này ở đỉnh a có h + 1 mũi tên đi, ở đỉnh b có

h + 1 mũi tên tới, còn ở mọi đỉnh khác đều có vừa đúng một mũi tên tới

và một mũi tên đi.

Do đó nếu ta rời khỏi a theo một mũi tên tùy ý rồi cứ tới đỉnh nào thì

theo mũi tên ở đó mà đi tiếp, thì ta sẽ tới b và vạch ra được một đường đi

sơ cấp từ a tới b; sau khi bỏ đường đi này (trừ a và b) thì tại a còn lại h

mũi tên đi, tại b còn lại h mũi tên tới, và tại mọi đỉnh khác chưa bỏ của

H vẫn có một mũi tên tới, một mũi tên đi, cho nên ta lại có thể theo cách

trên mà vạch một đường đi sơ cấp thứ hai từ a tới b, v.v . . . Như thế ta sẽ

được h + 1 đường đi sơ cấp tách biệt nối a với b, tức là, nếu kể cả (k − h)

đường đậm không cắt v, thì sẽ có tất cả k + 1 đường đi sơ cấp tách biệt

28

nối a với b : vô lý!

Vậy không thể có đường yếu đi từ a tới b.

Bây giờ ta sẽ nói một đỉnh là "yếu" nếu có một đường yếu từ đỉnh ấy

tới b. Từ định nghĩa này có thể suy ra ngay:

α) Nếu e là một đỉnh yếu thì mọi đỉnh nối liền với e bằng một đường

yếu cũng sẽ yếu;

β) Nếu e là một đỉnh yếu ở trên một đường đậm µi thì mọi đỉnh ở trên

µi[e, b] (phần đường đi trên µi từ e tới b) cũng sẽ yếu.

Ta hãy chọn trên mỗi đường đi µi(i = 1, 2, . . . , k) một đỉnh ei như sau: nếu trên µi có những đỉnh yếu thì lấy ei là đỉnh yếu đầu tiên ta gặp trên µi theo chiều từ a tới b; nếu trên µi không có đỉnh yếu thì lấy ei là đỉnh cuối cùng trên µi, khác a và b (vì a và b không kề nhau, nên mỗi đường đi µi phải có ít nhất một đỉnh khác a và b).

Có thể khẳng định rằng bất cứ đường đi nào từ a tới b cũng phải qua

ít nhất một trong các đỉnh e1, e2, . . . , ek. Thật vậy, giả sử có một đường đi π từ a tới b, không đi qua đỉnh ei nào cả. Đương nhiên π phải có những đỉnh chung với một số đường đậm. Gọi d1, d2, . . . , dp là các đỉnh đậm trên π (không kể a và b), theo thứ tự chiều đi từ a tới b trên π; và gọi µir là đường đậm chứa dir(r = 1, 2, . . . , p; một số µir có thể trùng nhau). Đỉnh dp là một đỉnh yếu, bởi vì hoặc là π[dp, b] nằm trọn trên µip thì lúc đó π[dp, b] phải là một cạnh (nếu không dp sẽ không phải là đỉnh đậm cuối cùng của π!), cho nên eip phải đứng trước dp và phải là đỉnh yếu (theo cách chọn các ei).

Do đó, theo nhận xét β) ở trên, dp cũng phải yếu; hoặc là π[dp, b] không nằm trên µip thì lúc đó π[dp, b] không chứa cạnh đậm (vì dp là đỉnh đậm cuối cùng của π), cho nên π[dp, b] là một đường yếu, tức là dp yếu. Đã vậy thì đỉnh dp−1 cũng phải yếu: điều đó có thể suy ra từ nhận xét β) nếu dp−1 ở trên µip (lúc đó dp−1 đứng sau đỉnh yếu eip), hoặc từ nhận xét α) nếu dp−1 không ở trên µip (lúc đó đoạn π[dp−1, dp] là một đường yếu, vì không

29

chứa cạnh đậm).

Lần lượt ta thấy rằng tất cả các đỉnh dp, dp−1, . . . , d2, d1 đều yếu. Vì trên µi1 có đỉnh yếu d1, nên ei1 phải đứng trước d1 trên µi1 , do đó đoạn π[a, d1] không thể là một cạnh đậm mà phải là một đường yếu; đường này, cùng

với đường yếu từ d1 tới b, tạo nên một đường yếu từ a tới b, trái với điều đã chứng minh ở trên.

Vậy mọi đường đi từ a tới b phải đi qua ít nhất một trong các đỉnh

e1, e2, . . . , ek. Điều đó có nghĩa là nếu ta rút e1, e2, . . . , ek thì mọi đường đi từ a tới b đều bị phá, và a, b không còn liên thông nữa.

Tóm lại, số tối đa đường đi sơ cấp tách biệt nối a với b là tổng số tối

thiểu đỉnh khác a và b mà cần phải rút để tách rời a với b. Định lý đã được

chứng minh đầy đủ.

Chú ý 2.1 Cách chứng minh trên cho thấy rằng: muốn tách rời được hai

đỉnh a, b khi rút một tập hợp đỉnh, điều kiện tất yếu và đủ là mọi dây

chuyền nối a với b đều phải đi qua ít nhất một phần tử của tập hợp đỉnh

này.

Ứng dụng. Trên một mạng lưới đường giao thông, muốn đặt một số

trạm kiểm soát ở các ngã ba, ngã tư, v.v . . . , để kiểm soát toàn bộ sự đi

lại giữa hai địa điểm a và b, thì cần đặt ít nhất bao nhiêu trạm kiểm soát?

Nếu ta biểu diễn mạng đường bằng một đồ thị (mỗi ngã ba, ngã tư là

một đỉnh) thì chỉ cần tìm cấp liên thông của a với b. Các trạm kiểm soát

cần đặt ở những đỉnh mà rút đi thì a và b hết liên thông.

30

Chẳng hạn, Hình 2.3 là bản đồ một hệ thống sông ngòi chảy từ vùng

núi ra biển. Muốn kiểm soát thuyền bè đi từ vùng núi ra biển chỉ cần đặt

ba trạm kiểm soát ở d, i, j (xem vùng núi và biển là hai đỉnh a, b của đồ

2.2. ĐỒ THỊ k - LIÊN THÔNG

thị).

Định nghĩa 2.2 Cho số tự nhiên k. Ta nói một đồ thị là k - liên thông,

khi mà số đỉnh của nó lớn hơn k và mọi cặp đỉnh của nó đều liên thông

cấp k trở lên.

Định nghĩa 2.3 Nếu một đồ thị G là k - liên thông, nhưng không (k + 1)

- liên thông thì số k ấy gọi là số liên thông (connectivity) của đồ thị G và

được ký hiệu là κ(G).

Theo định nghĩa này κ(G) = 0 khi và chỉ khi G không liên thông hoặc

G chỉ gồm một đỉnh duy nhất và κ(Kn) = n − 1 đối với mọi n (cid:62) 1.

Định nghĩa 2.4 Một tập hợp đỉnh E ⊂ A gọi là một tập hợp khớp của

đồ thị G = (A, U ) nếu đồ thị còn lại sau khi rút đi tập hợp E (cùng các

cạnh liên thuộc E) là không liên thông.

31

Định lý sau nêu mối liên hệ giữa tính liên thông và tập hợp khớp.

Định lý 2.2 (Whitney, 1932). Một đồ thị có số đỉnh lớn hơn max

(2, k), nghĩa là lớn hơn 2 và lớn hơn k, là k - liên thông khi và chỉ khi

mọi tập hợp khớp của nó đều có ít nhất k phần tử.

Chứng minh. Nếu một đồ thị G có một tập hợp khớp E với h < k

phần tử, thì sau khi rút E phải có ít nhất hai đỉnh bị tách rời hoàn toàn,

tức là theo định lý 2.1, hai đỉnh ấy liên thông cấp 1 ≤ h < k. Vậy nếu G

là k - liên thông thì mọi tập hợp khớp của nó có ít nhất k phần tử.

Ngược lại, giả sử mọi tập hợp khớp của G đều có ít nhất k phần tử và

cho a, b là hai đỉnh tùy ý của G. Nếu a, b không kề nhau thì theo định lý 2.1, chúng liên thông cấp k trở lên. Còn nếu a, b kề nhau thì ta gọi G(cid:48) là đồ thị G bỏ đi cạnh (a, b). Trong G(cid:48) muốn tách rời được a với b phải rút

ít nhất k − 1 đỉnh khác a, b.

Thật vậy, giả sử trái lại là có h < k − 1 đỉnh khác a, b, mà sau khi rút đi thì a và b bị tách rời trong G(cid:48). Khi đó trong G hai đỉnh a, b chỉ còn được

nối bởi cạnh (a, b) mà thôi. Vì số đỉnh của G lớn hơn k nên sau khi rút h

đỉnh nói trên thì ngoài a và b ra phải còn ít nhất một đỉnh nữa, do đó chỉ

cần rút thêm a hay b thì phá được sự liên thông của G. Thế là có một tập hợp khớp của G chỉ gồm h + 1 < k đỉnh, trái với giả thiết. Vậy trong G(cid:48)

phải rút ít nhất k − 1 đỉnh mới tách rời được a với b.

Do đó theo Định lý 2.1, trong G(cid:48) phải có ít nhất k − 1 đường đi tách

biệt nối a với b; k − 1 đường đi ấy, cùng với cạnh (a, b) làm thành k đường

đi tách biệt nối a với b trong G. Vậy G là k - liên thông.

Các tính chất đơn giản sau đây cũng đáng được chú ý.

Định lý 2.3 Trong một đồ thị k - liên thông, bậc của mọi đỉnh đều ≥ k.

Chứng minh. Giả sử G là k - liên thông và a là một đỉnh bất kỳ của

nó. Vì số đỉnh của G lớn hơn k, nên phải có ít nhất một đỉnh b (cid:54)= a, và

32

hai đỉnh a, b phải được nối liền bởi ít nhất k đường đi tách biệt. Vậy phải

có ít nhất k cạnh liên thuộc a, nghĩa là bậc của a phải ≥ k

Định lý 2.4 Trong một đồ thị k - liên thông, khi bỏ đi một đỉnh hay một

cạnh thì còn lại một đồ thị (k − 1) - liên thông.

Chứng minh. Cho n là số đỉnh của đồ thị. Vì n > k nên khi bỏ một

đỉnh thì số đỉnh còn lại là n − 1 > k − 1; mặt khác, muốn phá sự liên

thông của đẳng thức mới cần rút đi ít nhất k − 1 đỉnh. Vậy đồ thị mới

là (k − 1)-liên thông. Nếu ta không bỏ một đỉnh, mà bỏ một cạnh thì lập

2.3. ĐỈNH KHỚP

luận cũng tương tự.

Định nghĩa 2.5 Một tập hợp khớp chỉ gồm một đỉnh duy nhất thì gọi là

một đỉnh khớp (cutvertex). Như vậy một đỉnh khớp của một đồ thị liên

thông G là một đỉnh mà sau khi rút bỏ nó đi thì đồ thị hết liên thông.

Đương nhiên một đỉnh e của đồ thị G là đỉnh khớp khi và chỉ khi có hai

đỉnh a, b của G hoàn toàn bị tách rời sau khi rút đi e. Do đó, theo Chú ý

2.1 ở cuối mục trước, ta có

Định lý 2.5 Trong một đồ thị liên thông, một đỉnh e là đỉnh khớp khi và

chỉ khi có hai đỉnh a, b sao cho mọi đường đi nối a với b đều đi qua e.

Sau đây là một tính chất cơ bản của những đồ thị không có đỉnh khớp.

Định lý 2.6 Đối với một đồ thị G có ba đỉnh trở lên, không có khuyên và

không có đỉnh cô lập; ba điều kiện sau đây là tương đương:

1) đồ thị không có đỉnh khớp;

2) qua hai đỉnh bất kỳ bao giờ cũng có một chu trình sơ cấp;

3) qua hai cạnh bất kỳ bao giờ cũng có một chu trình sơ cấp.

33

Chứng minh. Trước hết, theo định lý Whitney (Định lý 2.2), đồ thị

G không có điểm khớp khi và chỉ khi nó 2 - liên thông, tức là bất cứ hai

đỉnh nào của nó cũng được nối bằng ít nhất hai đường đi sơ cấp tách biệt;

hai đường đi này tạo thành một chu trình sơ cấp. Do đó 1)⇔ 2).

Mặt khác, ta thấy dễ dàng 3)⇒ 2). Thật vậy, giả sử có 3) và cho a, b là

hai đỉnh bất kỳ. Vì đồ thị không có đỉnh cô lập, nên phải có một cạnh u

liên thuộc a, và một cạnh v liên thuộc b; chu trình sơ cấp đi qua hai cạnh

đó cũng chính là chu trình sơ cấp đi qua a và b.

Tóm lại, ta chỉ còn phải chứng minh rằng 2)⇒ 3). Muốn thế, ta chú ý

rằng nếu có 2) thì với hai cạnh u, v cho trước bao giờ cũng có một đường đi

µ bắt đầu bằng u và tận cùng bằng v. Thật vậy, giả sử u = (a, b), v = (e, f ).

Do 2) nên có hai đường đi sơ cấp tách biệt nối b với e; trong hai đường đi

đó phải có ít nhất một cái không đi qua a; nếu cái này cũng không đi qua

f (Hình 2.4a) thì nó tạo nên với hai cạnh u, v đường đi nói trên; còn nếu

nó đi qua f (Hình 2.4b) thì chỉ cần thêm cạnh u là được đường đi ấy.

Bây giờ, ta xét đỉnh gốc a của đường đi và đỉnh cuối của nó; để cho xác

định, ta giả thiết rằng đỉnh cuối ấy là f (nếu đỉnh cuối là e thì lập luận

cũng tương tự). Theo giả thiết, có một chu trình sơ cấp qua a và f , tức là có hai đường đi sơ cấp tách biệt : µ, và µ,, nối a với f . Ta hãy gọi c là đỉnh đầu tiên (sau a) mà µ gặp µ, ∪ µ,, và d là đỉnh cuối cùng (trước f ) mà µ gặp µ, ∪ µ,,. Có mấy trường hợp khác nhau như sau:

Trường hợp 1: c = a, d = f (Hình 2.5a) : lúc đó µ với µ, (hoặc µ với µ,,)

34

tạo nên một chu trình sơ cấp qua u và v.

Trường hợp 2: c (cid:54)= a, d (cid:54)= f , c và d cùng ở trên µ, (Hình 2.5b) : lúc đó

µ[a, c], µ,[c, d], µ[d, f ] và µ,, tạo thành chu trình nói trên.

Trường hợp 3: c (cid:54)= a, d (cid:54)= f , c và d cùng ở trên µ,, : tương tự như trường

hợp 2.

Trường hợp 4: c (cid:54)= a, d (cid:54)= f , c ở trên µ,, d ở trên µ,, (Hình 2.5c) : lúc đó

µ[a, c], µ,[c, f ], µ[f, d] và µ,,[d, a] tạo thành chu trình nói trên.

Trường hợp 5: c (cid:54)= a, d (cid:54)= f , c ở trên µ,,, d ở trên µ, : tương tự như

trường hợp 4.

2.4. LIÊN THÔNG CẠNH CẤP (cid:96) GIỮA HAI ĐỈNH

Vậy 2)⇒ 3) và định lý đã được chứng minh đầy đủ.

Trong định nghĩa trên về liên thông cấp k giữa hai đỉnh a, b của một đồ

thị G, nếu ta không buộc các đường đi nối a với b phải tách biệt, nghĩa là

từng đôi một không có đỉnh chung ngoài a và b, mà chỉ buộc các đường đi

ấy từng đôi một không có cạnh chung, thì ta có một khái niệm liên thông

nhẹ hơn khái niệm trước. Để phân biệt, ta gọi khái niệm liên thông trước

là "liên thông đỉnh", còn khái niệm mới là "liên thông cạnh". Nói chính

xác hơn, ta có

Định nghĩa 2.6 Hai đỉnh a, b của một đồ thị gọi là liên thông cạnh cấp (cid:96)

((cid:96) - edge-connected) nếu:

35

1) có ít nhất (cid:96) đường đi sơ cấp, từng đôi một không có cạnh chung, nối

a với b;

2) không có (cid:96) + 1 đường đi như thế.

Bằng lập luận tương tự như đối với định lý Menger, ta có thể chứng

minh mệnh đề sau đây.

Định lý 2.7 Muốn cho hai đỉnh a, b của một đồ thị G là liên thông cạnh

cấp (cid:96), điều kiện cần và đủ là:

1) có (cid:96) cạnh sao cho khi rút đi tất cả các cạnh ấy thì a và b bị tách rời

hoàn toàn;

2) không có (cid:96) − 1 cạnh như thế.

Định nghĩa 2.7 Ta nói một đồ thị là (cid:96) - liên thông cạnh, nếu nó có ít

nhất (cid:96) cạnh, và mọi cặp đỉnh của nó đều liên thông cạnh cấp (cid:96) trở lên.

Khi đồ thị G là (cid:96)- liên thông cạnh, nhưng không ((cid:96) + 1) - liên thông cạnh

thì số (cid:96) ấy gọi là số liên thông cạnh (edge-connectivity) của G và được ký

hiệu là (cid:96)(G). Nói riêng, ta có (cid:96)(G) = 0 khi G không liên thông.

Để minh họa cho khái niệm số liên thông đỉnh κ(G) và số liên thông

cạnh (cid:96)(G) của đồ thị, ta xét hai đồ thị G và H vẽ ở Hình 2.6.

Dựa theo định nghĩa, có thể thấy dễ dàng rằng số liên thông cạnh bao

giờ cũng lớn hơn hoặc bằng số liên thông đỉnh.

Đối với mọi đồ thị G khác rỗng và có số đỉnh n ≥ 2, có thể thấy rằng

36

κ(G) ≤ (cid:96)(G) ≤ δ(G)

vì thế, số liên thông (đỉnh) của đồ thị càng cao đòi hỏi bậc nhỏ nhất của

đỉnh càng phải lớn. Ngược lại, bậc nhỏ nhất lớn không đảm bảo số liên

thông (đỉnh) phải cao, kể cả khi số liên thông cạnh có thể cao. Tuy nhiên

điều này kéo theo sự tồn tai của một đồ thị con có số liên thông (đỉnh)

cao.

Định lý 2.8 (Mader, 1972). Mọi đồ thị mà bậc trung bình ≥ 4k sẽ có đồ

thị con k - liên thông.

Chứng minh. Với k ∈ {0, 1}, kết luận là hiển nhiên. Với k ≥ 2 xét đồ

thị G = (V, E) với số đỉnh n = |V | và số cạnh m = |E|. Bằng suy luận

quy nạp dễ dàng chứng minh kết quả mạnh hơn rằng G có đồ thị con k -

liên thông nếu

(i) n ≥ 2k − 1 và

(ii) m ≥ (2k − 3)(n − k + 1) + 1.

(Kết luận này thực sự mạnh hơn, cụ thể là (i) và (ii) suy ra từ giả thiết

d(G) ≥ 4k: (i) đúng vì n > (cid:52)(G) ≥ d(G) ≥ 4k và (ii) đúng là do

m = d(G)n ≥ 2kn.) 1 2 Ta chứng minh quy nạp theo n.

Nếu n = 2k−1 thì k = (n+1) và do đó m ≥ n(n−1) theo (ii). Như vậy 1 2

G = Kn ⊇ Kk+1 và kết luận là đúng. Bây giờ giả sử n ≥ 2k. Nếu v là một đỉnh mà d(v) ≤ 2k − 3, ta áp dụng giả thiết quy nạp đối với đồ thị G − v

và kết luận được chứng minh. Vì thế ta giả thiết δ(G) ≥ 2k − 2. Nếu G là

k - liên thông thì không còn gì phải chứng minh. Vì thế ta giả thiết rằng

G không liên thông, tức là có dạng G = G1 ∪ G2 với |V (G1) ∩ V (G2)| < k và |V (G1)|, |V (G2)| < n.

Do mỗi cạnh của G nằm trong G1 hoặc G2 nên G không có cạnh nào thuộc G1 − G2 và G2 − G1. Do mỗi đỉnh trong các đồ thị con này có ít nhất δ(G) ≥ 2k −2 đỉnh láng giềng (đỉnh kề) nên ta có |V (G1)|, |V (G2)| ≥

2k − 1. Nhưng khi đó ta sẽ chỉ ra ít nhất một trong các đồ thị G1, G2 phải

37

thỏa mãn giả thiết quy nạp (và lúc đó kết thúc chứng minh): nếu không

cái nào thỏa mãn thì

|E(Gi)| ≤ (2k − 3)(|V (Gi)| − k + 1)

với i = 1, 2 và do đó

m ≤ |E(G1)| + |E(G2)|

≤ (2k − 3)(|V (G1)| + |V (G2)| − 2k + 2)

≤ (2k − 3)(n − k + 1)(do|V (G1) ∩ V (G2)| ≤ k − 1)

trái với (ii).

Ta cũng có thể chứng minh định lý sau đây, tương tự như định lý

Whitney.

Định lý 2.9 Một đồ thị với số cạnh ≥ (cid:96) là (cid:96) - liên thông cạnh khi và chỉ

khi phải rút tối thiểu (cid:96) cạnh thì mới đủ phá vỡ sự liên thông của nó.

Chú ý rằng những khái niệm và kết quả trên đây đều áp dụng được cho

đa đồ thị. Tuy nhiên, sự mở rộng khái niệm liên thông đỉnh cho đa đồ thị

không đưa tới điểm gì mới, vì trong sự khảo sát tính liên thông đỉnh đối

với một đa đồ thị có thể gộp nhiều cạnh nối cùng một cặp đỉnh thành một

cạnh duy nhất: rõ ràng số liên thông đỉnh vẫn không thay đổi (trái lại, số

liên thông cạnh có thể giảm).

Ứng dụng. Trong chiến tranh, có khi người ta cần phá hủy một số

đường giao thông để cô lập một hay nhiều vùng trong một khu vực nào

đó. Vấn đề đặt ra là cần phá hủy ít nhất bao nhiêu đường giao thường để

đạt được mục đích? Nếu ta vẽ đa đồ thị G mà mỗi đỉnh là một vùng nói

trên và các cạnh là những đường giao thông (cầu, hầm, đường xe lửa, v.v

. . . ) nối liền các vùng ấy với nhau, thì vấn đề qui lại là tìm số liên thông

cạnh của đa đồ thị G. Chẳng hạn, trên bản đồ giao thông như vẽ ở Hình

2.7, chỉ cần phá hủy các cầu c − e, d − g, a − g là cả khu vực tách thành

hai vùng không liên lạc được với nhau. (Hình 2.8).

38

Kết luận chương. Chương này đã trình bày khái niệm liên thông đỉ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 (cid:96) -liên thông cạnh. Nêu một số ví dụ và ứng dụng.

39

Chương 3

CÁC TÍNH CHẤT VỀ BẬC CỦA

ĐỒ THỊ

Chương này trình bày một số tính chất về bậc của các đỉnh trong đồ

thị dựa trên phép di chuyển bảo toàn bậc của các đỉnh, các khái niệm bán

nhân tử, tập hợp tương thích lớn nhất và một số ứng dụng. Nội dung của

3.1. DI CHUYỂN TRÊN ĐỒ THỊ

chương được tham khảo chủ yếu từ các tài liệu [2], [4] và [5].

Mục này đề cập tới một số tính chất về bậc của các đỉnh trong đồ thị

và sẽ dùng một cách tiếp cận mới, dựa trên những phương pháp biến đổi

bảo toàn bậc của các đỉnh, gọi là những phép di chuyển trên đồ thị.

Cho một đồ thị vô hướng bất kỳ G = (A, U ), trong đó A là tập đỉnh và

U là tập cạnh của đồ thị. Ta gọi đồ thị bù của G là đồ thị G = (A, U ) với

U = A × A − U nói cụ thể hơn (a, b) ∈ U khi và chỉ khi (a, b) /∈ U . Sau

đây các cạnh của G sẽ gọi là "cạnh đậm", các cạnh của G là "cạnh nhạt".

Một đường đi µ = [u1, u2, .., uk] gọi là một đường đi xen kẽ đối với G (hay đối với U ) nếu trong hai cạnh liên tiếp của µ bao giờ cũng có một cạnh

đậm và một cạnh nhạt (Hình 3.1). Một đường đi xen kẽ, khép kín và chẵn

(nghĩa là có một số chẵn cạnh) gọi là một chu trình xen kẽ (Hình 3.1).

40

Giả sử µ là một đường đi xen kẽ đối với G. Khi đó, nếu ta đổi các cạnh

đậm trên µ thành nhạt và ngược lại (tức là loại ra khỏi U các cạnh đậm

trên µ và thêm vào U các cạnh nhạt trên µ) thì ta được một đồ thị mới

G1 = (A, U1), trong đó bậc của mỗi đỉnh vẫn như cũ, chỉ trừ bậc của mỗi đầu mút của µ có thể tăng hay giảm 1. Phép biến đổi ấy sẽ gọi là di chuyển

đồ thị G (hay tập hợp U ) trên µ.

Khi µ là một chu trình xen kẽ thì rõ ràng phép di chuyển trên µ sẽ bảo

toàn bậc của mọi đỉnh, nghĩa là không làm thay đổi số cạnh liên thuộc

mỗi đỉnh. Chính nhờ sự bảo toàn đó mà các phép di chuyển đó rất tiện lợi

3.2. ĐỒ THỊ ĐỒNG BẬC

cho mục đích nghiên cứu của ta trong chương này.

Hai đồ thị G = (A, U ) và G(cid:48) = (A, U (cid:48)) cùng chung một tập hợp đỉnh

gọi là đồng bậc nếu bậc của mỗi đỉnh trong G đều bằng bậc của nó trong G(cid:48). Theo trên mỗi phép di chuyển trên một chu trình xen kẽ bao giờ cũng

biến G thành một đồ thị G1 đồng bậc của nó. Ngược lại, cho trước hai đồ thị đồng bậc G và G(cid:48), có thể biến G thành G(cid:48) qua một số hữu hạn di

chuyển không? Sau đây ta sẽ giải đáp vấn đề đó.

Cho hai đồ thị bất kỳ G = (A, U ) và G(cid:48) = (A, U (cid:48)) cùng chung một tập

hợp đỉnh. Ta nói đường đi µ = [u1, u2, . . . , uk] là một đường đi phân biệt cho G và G(cid:48) (hay cho U và U (cid:48)) nếu trên đường đi đó các cạnh của G nhưng

41

không thuộc G(cid:48) xen kẽ với các cạnh của G(cid:48) nhưng không thuộc G, bằng nhau: u1 ∈ U − U (cid:48), u2 ∈ U (cid:48) − U, u3 ∈ U − U (cid:48), v.v . . . Một đường đi phân biệt, khép kín và chẵn, gọi là một chu trình phân biệt. Đương nhiên một đường đi (chu trình) phân biệt cho G và G(cid:48) cũng là xen kẽ đối với G (và đối với G(cid:48)).

Bổ đề 3.1 Hai đồ thị đồng bậc G (cid:54)= G(cid:48) phải có ít nhất một chu trình đơn

giản, phân biệt.

Chứng minh. Vì G (cid:54)= G(cid:48) nên phải có một cạnh u1 = (ai1, ai2) ∈ U −U (cid:48). Nhưng theo giả thiết số cạnh trong G liên thuộc ai2 bằng số cạnh trong G(cid:48) liên thuộc cùng đỉnh ấy, cho nên nếu đã có một cạnh u1 ∈ U − U (cid:48) thì phải có một cạnh u2 = (ai2, ai3) ∈ U (cid:48) − U , rồi cũng theo lập luận đó phải có một cạnh u3 = (ai3, ai4) ∈ U − U (cid:48), v.v . . . Vì số cạnh của hai đồ thị là hữu hạn, nên cứ tiếp tục quá trình trên, sẽ có lúc ta gặp một cạnh uis+1 trùng với một cạnh uik đã đi qua. Lúc đó µ = [aik, aik+1, . . . , ais] cho ta một chu trình đơn giản, phân biệt cho G và G(cid:48).

Định lý 3.1 Nếu hai đồ thị G = (A, U ) và G(cid:48) = (A, U (cid:48)) là đồng bậc thì G(cid:48) có thể suy ra từ G bằng một số hữu hạn di chuyển trên những chu trình

đơn giản từng đôi một không có cạnh chung.

Chứng minh. Gọi q là số cạnh của G không thuộc G(cid:48). Dĩ nhiên ta chỉ

cần xét q > 0. Theo bổ đề trên, có một chu trình phân biệt µ cho G và G(cid:48): thực hiện di chuyển trên µ cho G ta được một đồ thị G1, trong đó số cạnh không thuộc G(cid:48) là q1 ≤ q − 1.

Nếu q1 vẫn > 0 thì ta lại tìm một chu trình phân biệt µ2 cho G1 và G(cid:48), rõ ràng µ2 cũng là một chu trình phân biệt giữa G và G(cid:48), và µ2 không có cạnh chung với µ1. Khi thực hiện di chuyển trên µ2 cho G1 ta được một đồ thị G2, trong đó số cạnh không thuộc G(cid:48) là q2 ≤ q1 − 1, v.v . . . Vì số cạnh là hữu hạn nên đến một lúc nào đó ta được một đồ thị Gh với qh = 0. Dĩ nhiên Gh trùng hoàn toàn với G(cid:48).

42

Hệ quả 3.1 Nếu hai đồ thị G = (A, U ) và G(cid:48) = (A, U (cid:48)) là đồng bậc, và u ∈ U − U (cid:48), thì có tồn tại một chu trình đơn giản, phân biệt µ duy nhất

đi qua cạnh u.

Chứng minh. Giả sử µ1, µ2 . . . , µk là các chu trình đơn giản, phân biệt mà các phép di chuyển tương ứng sẽ biến G thành G(cid:48). Dĩ nhiên đó là tất

cả các chu trình đơn giản phân biệt, và trong số đó phải có một chu trình

3.3. BÁN NHÂN TỬ

(và một mà thôi) đi qua u, vì nếu không thì các phép di chuyển nói trên không thể làm cho G trùng với G(cid:48).

Một đồ thị bộ phận F = (A, V ) của một đồ thị cho trước G = (A, U ),

trong đó V ⊂ U gọi là một bán nhân tử của G, nếu mọi đỉnh a ∈ A đều

có bậc 2 trong F . Một bán nhân tử có thể gồm một hay nhiều chu trình

sơ cấp rời nhau (Hình 3.2 a). Nếu nó chỉ gồm một chu trình sơ cấp duy

nhất thì ta gọi nó là một chu trình Haminton (Hamilton). Nói cách khác,

một chu trình Haminton của đồ thị G là một chu trình của G, đi qua mỗi

đỉnh của G vừa đúng một lần (Hình 3.2 b).

Ví dụ 3.1 Một nhân viên bưu điện hàng ngày phải đến mở từng hòm thư

ở các địa điểm b, c, d, . . . (Hình 3.2 b), để lấy thư đưa về sở bưu điện a.

Hãy tìm hành trình ngắn nhất mà anh ta nên đi theo?

43

Đương nhiên, cần phải tìm một hành trình ngắn nhất có thể được, xuất

phát từ a và đi qua mỗi đỉnh b, c, d, . . . vừa đúng một lần để cuối cùng

trở về a. Như vậy vấn đề chung qui là tìm một chu trình Haminton ngắn

nhất của đồ thị G.

Bài toán nêu trong ví dụ trên thường gọi là bài toán người du lịch, và

cho đến nay vẫn chưa có một cách giải hiệu quả, mặc dù đã được rất nhiều

nhà toán học chú ý nghiên cứu. Đó cũng là một bài toán nổi tiếng khó

nhất của toán ứng dụng.

Dựa vào Định lý 3.1 và hệ quả của nó ta có thể tìm được dễ dàng một

bán nhân tử (nếu có) của một đồ thị G cho trước theo cách sau đây: xuất

phát từ một đỉnh (mỗi đỉnh chỉ qua một lần), nếu tới một đỉnh e nào đó

mà không có cạnh nào dẫn tới một đỉnh mới (nghĩa là một đỉnh chưa từng

đi qua) ta thêm vào đồ thị một cạnh "giả" để có thể tiếp tục đi nữa. Như

thế cuối cùng ta vẽ được một chu trình H đi qua mỗi đỉnh vừa đúng một

lần nhưng trong đó có thể có cả một số cạnh "giả" mới thêm vào. Gọi u

là một cạnh giả ấy. Nếu G có một bán nhân tử thì bán nhân tử đó và H

có cùng bậc 2 ở mỗi đỉnh nên theo Hệ quả 3.1, ta tìm được một chu trình

đi qua cạnh giả u, và trên đó các cạnh "thật" (cạnh thuộc G) xen kẽ với

những cạnh "giả". Thực hiện di chuyển trên chu trình này, ta được bán

nhân tử H1, trong đó số cạnh giả đã giảm bớt so với H.

Lặp lại phép toán trên nhiều lần, ta bỏ dần được các cạnh giả và cuối

cùng thu được một bán nhân tử không có cạnh giả, tức là một bán nhân

tử của G. Nếu trong quá trình đó, lúc nào ta gặp một cạnh giả mà không

có chu trình xen kẽ (gồm cạnh thật và cạnh giả xen kẽ nhau) đi qua nó,

3.4. TẬP HỢP TƯƠNG THÍCH LỚN NHẤT

tức là G không có bán nhân tử và ta không cần tiếp tục nữa.

Cho một đồ thị G = (A, U ) và ứng với mỗi đỉnh a ∈ A cho một số

tự nhiên γ(a), bé hơn hay bằng bậc của a trong G. Ta nói một tập hợp

44

W ⊂ U , hay đồ thị bộ phận (A, W ) là tương thích với hàm γ(a) nếu bậc

của mỗi đỉnh a ∈ A trong đồ thị (A, W ) là tw(a) ≤ γ(a).

Ta ký hiệu |W | là số phần tử của tập hợp W . Nếu không có tập hợp tương thích W (cid:48) nào với |W (cid:48)| > |W | thì W được gọi là tập hợp tương thích

lớn nhất và đồ thị (A, W ) được gọi là đồ thị bộ phận tương thích lớn nhất. Giả sử ta có hai tập hợp tương thích W và W (cid:48). Một đường đi phân biệt µ = [u1, u2, . . . , uk] cho hai tập hợp W và W (cid:48), theo định nghĩa ở trên là một đường đi trong đó các cạnh thuộc W − W (cid:48) xen kẽ với các cạnh thuộc W (cid:48) − W . Đường đi phân biệt đó được gọi là đầy đủ nếu nó là đơn giản

(không đi qua cạnh nào hai lần trở lên) và không chứa trong một đường

đi đơn giản phân biệt nào khác nó. Một đường đi µ xen kẽ đối với W được

gọi là sửa được cho W nếu phép di chuyển tập hợp W trên µ cho ta một

tập hợp W1 cũng tương thích.

Bổ đề 3.2 Một đường đi phân biệt, đầy đủ µ = [u1, u2, . . . , uk] cho hai tập hợp tương thích W và W (cid:48) thì bao giờ cũng là sửa được cho W (và cho W (cid:48)).

Chứng minh. Nếu µ có chứa những chu trình phân biệt thì rõ ràng sự

di chuyển trên các chu trình đó không ảnh hưởng gì đến tính tương thích,

cho nên thực hiện trước sự di chuyển trên các chu trình đó (nếu có), ta có

thể coi như µ không chứa những chu trình phân biệt.

a − µa vì nếu có một cạnh u ∈ Wa − (W (cid:48)

a) là tập hợp các phần tử của W (W (cid:48)) liên thuộc a, µa là tập hợp các phần tử của µ liên thuộc a(µa ⊂ W (cid:48) và có 1 hoặc 2 phần tử tùy theo a (cid:54)= b hoặc a = b). Ta thấy rằng Wa ⊂ W (cid:48) a − µa) thì thêm u vào µ ta sẽ được một đường đi phân biệt chứa µ, trái với giả thiết

Cho a là điểm gốc của µ, và giả sử u1 ∈ W (cid:48) − W . Gọi Wa(W (cid:48)

về tính đầy đủ của µ.

Vậy trong trường hợp này, sau khi di chuyển, bậc của a trong W , dù có tăng, vẫn ≤ bậc của a trong W (cid:48) ≤ γ(a). Còn nếu u1 ∈ W − W (cid:48) thì sau khi di chuyển bậc của a trong W giảm đi 1 (nếu a (cid:54)= b) hoặc 2 nếu

(a = b). Đằng nào sự di chuyển cũng không hại đến tính tương thích tại

45

a. Tại điểm cuối b của µ tình hình cũng tương tự, còn tại các đỉnh khác

thì bậc không thay đổi. Vậy µ là sửa được cho W .

Định lý 3.2 Nếu W và W (cid:48) là hai tập hợp tương thích khác nhau thì W (cid:48)

có thể suy ra từ W bằng một số hữu hạn di chuyển trên những đường đi

phân biệt.

Chứng minh. Gọi E là tập hợp tất cả các đường đi đơn giản, phân biệt cho W và W (cid:48). Rõ ràng E khác rỗng, vì theo giả thiết W (cid:54)= W (cid:48), tức là phải có ít nhất một cạnh u ∈ (W − W (cid:48)) ∪ (W (cid:48) − W ). Cạnh này tự nó đã là một đường đi phân biệt cho W và W (cid:48). Vả lại E dĩ nhiên là hữu hạn, do đó phải có một đường đi µ ∈ E, không chứa trong bất cứ đường đi µ(cid:48) ∈ E

nào khác, nghĩa là phải có một đường đi µ đầy đủ.

Theo bổ đề trên, µ là sửa được cho W , tức là khi di chuyển W trên µ ta sẽ được một tập hợp tương thích W1. Nếu W1 vẫn (cid:54)= W (cid:48) thì ta lặp lại cách trên cho W1 để cho một tập hợp tương thích W2, v.v . . . Gọi qi(i = 0, 1, 2, . . .) là số cạnh thuộc (Wi − W (cid:48)) ∪ (W (cid:48) − Wi) (với qui ước W0 = W ) thì rõ ràng qi+1 < qi. Do đó sau một số hữu hạn h phép di chuyển ta sẽ được một tập hợp Wh với qh = 0, tức là Wh = W (cid:48).

Hệ quả 3.2 Nếu W và W (cid:48) là hai tập hợp tương thích lớn nhất thì W (cid:48) có

thể suy ra từ W bằng một số hữu hạn di chuyển trên những đường đi phân

biệt chẵn.

Chứng minh. Cho µ = [u1, u2, . . . , uk] là một đường đi phân biệt đầy đủ cho W và W (cid:48). Nếu µ gồm một số lẻ cạnh thì hoặc là số cạnh thuộc W trên µ < số cạnh thuộc W (cid:48) trên µ, hoặc là ngược lại; cả hai trường

hợp này đều không thể xảy ra, vì nếu chẳng hạn xảy ra trường hợp thứ

nhất thì sự di chuyển W trên µ sẽ cho ta một tập hợp tương thích W1 với |W1| = |W | + 1, trái với tính lớn nhất của W . Vậy µ phải gồm một số chẵn cạnh.

Sau khi di chuyển W trên µ ta sẽ được một tập hợp W1 với |W1| = |W |,

46

nghĩa là W1 cũng sẽ là một tập hợp tương thích lớn nhất, do đó lý luận trên có thể lặp lại cho W1 và W (cid:48), v.v . . . Thành thử các đường đi nói trong Định lý 3.2 đều có thể xem là chẵn.

Định lý 3.3 (Berge-Norman-Rabin). Một tập hợp tương thích W là lớn

nhất khi và chỉ khi không có đường đi xen kẽ sửa được, với hai cạnh mút

nhạt.

Chứng minh. Phần "chỉ khi" rõ ràng, vì nếu có một đường đi µ như

thế thì khi di chuyển W trên µ ta sẽ được một tập hợp tương thích lớn

hơn W .

Để chứng minh phần ngược lại, ta xét một tập hợp tương thích W với điều kiện đã nêu trên, và cho W (cid:48) là tập hợp tương thích lớn nhất. Theo Định lý 3.2, W (cid:48) có thể suy ra được từ W bằng di chuyển trên những đường đi phân biệt cho W và W (cid:48), tức là những đường đi xen kẽ đối với W . Nhưng

mỗi đường đi xen kẽ đó, nếu có số lẻ cạnh thì theo giả thiết, hai cạnh mút

phải là cạnh đậm, cho nên những di chuyển trên các đường đi đó không

thể làm tăng số cạnh đậm.

Do đó nếu Wh là tập hợp thu được ở di chuyển cuối cùng (Wh = W (cid:48)) thì |Wh| ≤ |W |, chứng tỏ rằng |W | = |W (cid:48)|, nghĩa là W là một tập hợp tương thích lớn nhất.

Do Định lý 3.3 ta suy ra thuật toán sau đây: xuất phát từ một tập hợp

tương thích bất kỳ W , ta kiểm tra xem có đường đi xen kẽ, sửa được với

hai cạnh mút nhạt hay không? Nếu có thì di chuyển W trên đường đi đó.

Khi không còn đường đi nào như thế nữa thì sẽ có tập hợp tương thích lớn

nhất.

Để phát hiện một đường đi như trên, có thể làm như sau: bắt đầu từ

một cạnh nhạt liên thuộc một đỉnh "chưa no" (nghĩa là một đỉnh mà

tw(a) < γ(a)), đi theo một đường đi xen kẽ (đi theo cạnh nào thì đánh dấu cạnh ấy bằng mũi tên); cho đến lúc nào không tiếp tục đi được nữa

thì dừng lại xem đường đi đã thu được có đủ điều kiện cần thiết không.

47

Nếu đường đi đó chưa có điều kiện cần thiết thì quay lại điểm rẽ đầu tiên

(quay lại đến đâu thì xóa các mũi tên đến đó), rồi đi theo một hướng khác,

v.v . . . Đến khi đã dùng hết mọi đường đi phát xuất từ một đỉnh chưa no

thì chuyển qua một đỉnh chưa no khác và lặp lại quá trình trên, v.v . . .

Ứng dụng. Cho một đồ thị G = (A, U ). Một tập hợp V ⊂ U được gọi

là một phủ của G nếu mỗi đỉnh a ∈ A đều là đầu mút cho ít nhất một

cạnh trong V . Rõ ràng V là một phủ khi và chỉ khi W = U − V là một

tập hợp tương thích với hàm γ(a) = ρ(a) − 1, trong đó ρ(a) là bậc của a

trong G.

Một phủ nhỏ nhất là một phủ có ít phần tử nhất. Dĩ nhiên V là phủ

nhỏ nhất khi và chỉ khi W = U − V là tập hợp tương thích lớn nhất với

hàm γ(a).

Ví dụ 3.2 Trong một tòa nhà cần mắc một số đèn để soi sáng các chỗ

đông người ra vào: a, b, c, d, e, f, g (Hình 3.3). Một ngọn đèn mắc ở hành

lang (a, f ) thì có thể soi sáng được hai nơi a, f , v.v . . . Cần mắc ít nhất

bao nhiêu đèn để soi sáng được mọi nơi đông người ra vào?

Vấn đề qui lại là tìm một phủ nhỏ nhất của đồ thị ở hình 3.2. Ta thấy

rằng cần mắc ít nhất 4 đèn ở các hành lang vẽ bằng nét đậm.

Kết luận chương. Chương này đã trình bày một số tính chất về bậc

48

của các đỉnh trong đồ thị, dựa trên phép di chuyển bảo toàn bậc của các

đỉnh và các khái niệm bán nhân tử, tập hợp tương thích lớn nhất và một

số ứng dụng.

49

Kết luận

Luận văn tìm hiểu và giới thiệu 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 đỉnh và cạnh,

các tính chất về bậc của đồ thị vô hướng và một số ví dụ ứng dụng.

Luận văn đã trình bày các nội dung cụ thể sau.

1. Khái niêm cơ bản về đồ thị: đỉnh và cạnh, đồ thị vô hướng, đồ thị có

hướng, bậc của đỉnh và tính chất, đường đi và chu trình, đồ thị liên thông,

không liên thông và một số đồ thị đặc biệt thường gặp.

2. Liên thông đỉnh, liên thông cạnh của đồ thị và các định lý về điều

kiện để đồ thị là k-liên thông đỉnh hay (cid:96) -liên thông cạnh. Một số ví dụ và

ứng dụng.

3. Phép biến đổi bảo toàn bậc của mọi đỉnh trong đồ thị. Đồ thị đồng

bậc và tính chất, bán nhân tử (đồ thị con mọi đỉnh có bậc hai) và chu

trình Hamilton. Thuật toán tìm tập hợp tương thích lớn nhất, ví dụ và

ứng dụng.

50

Tài liệu tham khảo

Tiếng Việt

[1] Trần Vũ Thiệu và Bùi Thế Tâm (1998), Các phương pháp tối ưu hoá,

Nhà xuất bản Giao thông vận tải.

[2] Hoàng Tuỵ (1964), Đồ thị hữu hạn và ứng dụng trong vận trù học,

Nhà xuất bản Khoa học Kỹ thuật.

Tiếng Anh

[3] J. M. Aldous, R. J. Wilson (2004), Graphs and Applications - An

Introductory Approach, Springer.

[4] J. A. Bondy, U. S. R. Murty (2008), Graph Theory, Springer.

[5] R. Diestel (2016), Graph Theory, Electronic Edition, Springer-Verlag,

New York.

[6] R. J. Wilson (1998), Introduction to Graph Theory, Fourth Edition,

Addison Wesley Longman Limited.