TAILIEUCHUNG - Giáo trình đồ thị - Cặp ghép và đồ thị hai phần

Tham khảo tài liệu 'giáo trình đồ thị - cặp ghép và đồ thị hai phần', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | BÀI 08 Chương 5 Cặp ghép và đồ thị hai phần . Tập đỉnh tựa và cặp ghép Để đưa vào các khái niệm mới này chúng ta xét bài toán phân công nhiệm vụ như sau Một cơ quan có n nhân viên Xị x2 . xn và m nhiệm vụ yi y2 . ym. Do quá trình đào tạo mỗi nhân viên có thể đảm nhiệm một hay nhiều nhiệm vụ và mỗi nhiệm vụ có một số nhân viên có thể đảm nhiệm được. Vậy có thể phân công cho mỗi nhân viên đảm nhiệm một nhiệm vụ thích hợp với trình độ của người đó được không Bài toán này sẽ giải quyết được nhờ khái niệm cặp ghép mà chúng ta sẽ đưa vào dưới đây. Định nghĩa Giả sử G là một đồ thị vô hướng. 1 Tập con các đỉnh C của G được gọi là tập đỉnh tựa của đồ thị G nếu mỗi cạnh của G đều kề với ít nhất một đỉnh nào đó trong C. 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 . 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. Ví dụ Xét đồ thị vô hướng cho ở Hình 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 . _ 2 Hình . Đồ thị vô hướng . Đồ thị hai phần Ta xét một lớp đồ thị đặc biệt sau đây. Định nghĩa Đồ thị G V F được gọi là đồ thị hai phần nếu tập đỉnh V có thể tách thành hai tập ổn định trong không giao nhau. Hay nói một cách khác V V1 u V2 V1 n V2 0 F V1 c V2 F V2 c V1. Khi đó thì mỗi cạnh có một đầu thuộc V1 và đầu kia thuộc V2. Đồng thời V1 và V2 là các tập đỉnh tựa của đồ thị G. Nếu đồ thị có ít nhất một cạnh thì khái niệm đồ thị hai phần trùng với điều kiện sắc số bằng 2. Ta thường ký hiệu đồ thị hai phần là G V1 V2 F . Ví dụ Cho đồ thị vô hướng. Hình .

• Toán học
• đồ thị
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• tài liệu về đồ thị
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• Đồ thị phẳng
• định lý Kemple
• định lý heawood
• đồ thị vô hướng
• đồ thị Euler
• đồ thị hamiton
• bài giảng đồ thị phẳng
• biểu diễn đồ thị
• bậc của đỉnh trong đồ thị
• đại cương đồ thị
• bài giảng về đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị
• Khái niệm đồ thị
• đồ thị riêng
• sự đẳng hình của đồ thị
• cách biểu diễn đồ thị
• định nghĩa đồ thị
• toán rời rạc
• nguyên lý đồ thị
• tự học đồ thị
• cách vẽ đồ thị
• tô màu đồ thị
• Vẽ đồ thị
• bài toán luồng trên mạng
• tài liệu học đại học
• bài giảng toán học
• toán đồ thị
• đơn đồ thị
• đa đồ thị
• giả đồ thị
• đồ thị có hướng