ĐẠ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
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)
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 4Y
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)
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)
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
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
4(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à e0 gọi là kề nhau
nếu e, e0 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à e0 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ố 4(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 |
P
d(v) = 2m/n (n = |V (G)| , m = |E(G)|).
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, 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 ), ... , (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 6= 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) := minx∈V (G)
maxy∈V (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).
- Xem thêm -