2) Tập con các cạnh W của G được gọi là cặp ghép nếu trong W không có hai
cạnh nào kề nhau.
Hình 5.1. Tập đỉnh tựa và cặp ghép
Tập đỉnh tựa của một đồ thị luôn tồn tại. Tập tất cả các đỉnh là một ví dụ về
tập đỉnh tựa của đồ thị.
Song ta thường quan tâm đến tập đỉnh tựa có ít đỉnh nhất. Dễ thấy, tập con
các đỉnh C là tập đỉnh tựa khi và chỉ khi tập V \ C là ổn định trong.
Cặp ghép của một đồ thị cũng luôn tồn tại. Mỗi cạnh trong cặp ghép sẽ tạo
nên sự ghép giữa một đỉnh với đỉnh kề của nó.
Ta cũng thường quan tâm đến các cặp ghép có nhiều cạnh nhất.
https://traloihay.net
Ví dụ 5.2: Xét đồ thị vô hướng cho ở Hình 5.2 dưới đây.
Đồ thị này có các tập đỉnh tựa là: {1, 2, 6}, {2, 5, 6}, ... và các cặp ghép:
{(1, 2), (3, 6)}, {(1, 5), (2, 4), (3, 6)}, ...
Hình 5.2. Đồ thị vô hướng
Bạn đang xem 2) - LY THUYET DO THI BAI 8
