tailieunhanh - Giáo trình lý thuyết đồ thị - Bài 9

Giả sử G là đồ thị hai phần có n đỉnh. Ký hiệu k là số phần tử của tập đỉnh tựa bé nhất. Khi đó thì: Định lý : 1. Số ổn định trong của đồ thị hai phần G là bằng n-k. 2. Số phần tử của cặp ghép lớn nhất của G là bằng k. Chứng minh: 1. Suy từ nhận xét trên: C là tập đỉnh tựa nhỏ nhất ⇔ V \ C là tập ổn định trong lớn nhất. 2. Giả sử W là cặp ghép lớn nhất và C là tập tựa nhỏ. | BÀI 09 Giả sử G là đồ thị hai phần có n đỉnh. Ký hiệu k là số phần tử của tập đỉnh tựa bé nhất. Khi đó thì Định lý 1. Số ổn định trong của đồ thị hai phần G là bằng n-k. 2. Số phần tử của cặp ghép lớn nhất của G là bằng k. Chứng minh 1. Suy từ nhận xét trên C là tập đỉnh tựa nhỏ nhất V C là tập ổn định trong lớn nhất. 2. Giả sử W là cặp ghép lớn nhất và C là tập tựa nhỏ nhất. Lập ánh xạ t W C như sau Ve G W t e là một đỉnh của e thuộc C. Đỉnh đó tồn tại vì C là tập tựa còn nếu cả hai đỉnh của e đều thuộc C thì ta lấy một trong hai đỉnh đó. Nếu u V G W và u z V thì t u t v vì hai cạnh u và V không có đỉnh chung. Vậy thì W C k. Hình . Cách xây dựng ánh xạ t Để chứng minh chiều ngược lại ta xây dựng tập đỉnh tựa C từ cặp ghép lớn nhất W mà hai tập này có cùng lực lượng. Ký hiệu B là tập các đỉnh của W trong V1. Lập ánh xạ h B V2 như sau Va G B 3 b G V2 a b G W ta đặt h a b. Vậy h B chính là tập các đỉnh của W trong V2. Nếu a c G B và a z c thì h a h c vì các cạnh trong W chứa a và c không kề nhau. Hình . Cách xây dựng tập đỉnh tựa Một đường đi trong đồ thị G được gọi là đường đan nếu nó có dạng Wj Uj w2 u2 . wq uq trong đó w w2 . wq đều thuộc W và UỊ u2 . uq đều không thuộc W. Ký hiệu Bl a G B I 3 đường đan đi từ a đến một đỉnh nào đó nằm ngoài B và B2 B B1. Đặt C B2 u h B1 . Chúng ta sẽ chứng minh rằng tập C là tập đỉnh tựa của đồ thị G. Ta chứng minh điều này bằng phản chứng. Giả sử rằng tập C không phải tập đỉnh tựa của đồ thị hai phần G nghĩa là có cạnh a b nào đó không tựa vào tập C. Vậy thì a t B2 và b h B1 . Nhưng vì tập các cạnh W là cặp ghép lớn nhất nên cạnh a b phải kề với một cạnh nào đó trong W nghĩa là a E B hoặc b E h B . Xét các trường hợp sau đây 1 Trường hợp a E B. Suy ra a E B1. Khi đó có một đường đan X Wj u w2 u2 . wq uq dẫn đỉnh a tới một đỉnh d nào đó nằm ngoài tập B. - Nếu b t h B thì cạnh a b t W. Ta loại các cạnh W1 w2 . wq ra khỏi W và thay các cạnh a b U1 u2 . uq vào W. Khi đó W vẫn là một cặp ghép và số cạnh tăng thêm 1. Vậy trái