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

• Toán học
• Chu trình Hamilton
• thuật toán
• đồ thị
• ứng dụng cây
• hàm trên đồ thị
• Lý thuyết đồ thị
• Đường đi Hamilton
• Đồ thị Hamilton
• Định nghĩa về chu trình Hamilton
• Định nghĩa về đường đi Hamilton
• Đường Hamilton
• bài toán mã đi tuần
• chu trình vô hướng hamilton
• Luận án Tiến sĩ Toán học
• Luận án Tiến sĩ
• Cơ sở toán học cho tin học
• Thuật toán đa thức xác định chu trình Hamilton
• Bài giảng Lý thuyết đồ thị
• Đồ thị Euler
• Kiểm tra đồ thị Hamilton
• Bài toán người du lịch
• Bài toán tối ưu tổ hợp
• Đường Hamilton
• Thuật toán nhánh cận giải TSP
• Bài toán người du lịch và thuật toán nhánh cận
• Bài toán tối ưu liên quan đến đường Hamilton
• Đồ thị tách cực
• Đồ thị tách cực phi Hamilton tối đại
• Bậc cực tiểu
• Chu trình euler
• thuật toán tìm chu trình
• đồ thị liên thông
• Bài toán lý thuyết đồ thị
• Bài toán luông
• toán rời rạc
• bài tập học phần
• Đường đi đồ thị
• Đồ thị phẳng
• Bài toán tô màu đồ thị
• Tài liệu Thực hành
• Đồ thị Chu trình
• Lý thuyết đồ thị chu trình
• Đường đi Euler
• Đồ thị ơ2= N
• Đồ thị đơn
• Bài toán HC
• Thuật toán đa thức
• Xây dựng thuật toán đa thức
• Đồ thị 2 phần
• Đồ thị đầy đủ
• Đồ thị rỗng
• tài liệu toán học
• phép toán hedetniemi
• bài giảng toán học
• các bài toán về đường đi
• Bài giảng Toán rời rạc
• Thuật toán Dijkstra
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• Đường đi trên đồ thị
• Bài toán đường đi tốt nhất
• Bài giảng Cấu trúc rời rạc
• Cấu trúc rời rạc
• Chu trình và đường đi Euler
• Chu trình và đường đi Hamilton