TAILIEUCHUNG - CHƯƠNG VII ĐỒ THỊ PHẲNG VÀ TÔ MÀU ĐỒ THỊChứng minh: Không mất tính chất

Chứng minh: Không mất tính chất tổng quát có thể giả sử G liên thông. Cố định đỉnh u của G và tô nó bằng màu 0 trong hai màu 0 và 1. | CHƯƠNG VII ĐÒ THỊ PHẲNG VÀ TÔ MÀU ĐỒ THỊ Chứng minh Không mất tính chất tổng quát có thể giả sử G liên thông. Cố định đỉnh u của G và tô nó bằng màu 0 trong hai màu 0 và 1. Với mỗi đỉnh v của G tồn tại một đường đi từ u đến v nếu đường này có độ dài chẵn thì tô màu 0 cho v nếu đường này có độ dài lẻ thì tô màu 1 cho v. Nếu có hai đường đi mang tính chẵn lẻ khác nhau cùng nối u với v thì dễ thấy rằng G phải chứa ít nhất một chu trình độ dài lẻ. Điều mâu thuẫn này cho biết hai màu 0 và 1 tô đúng đồ thị G. . Mệnh đề Với mỗi số nguyên dương n tồn tại một đồ thị không chứa K3 và có sắc số bằng n. Chứng minh Ta chứng minh mệnh đề bằng quy nạp theo n. Trường hợp n 1 là hiển nhiên. Giả sử ta có đồ thị Gn với kn đỉnh không chứa K3 và có sắc số là n. Ta xây dựng đồ thị Gn 1 gồm n bản sao của Gn và thêm knn đỉnh mới theo cách sau mỗi bộ thứ tự v1 v2 . vn với vi thuộc bản sao Gn thứ i sẽ tương ứng với một đỉnh mới đỉnh mới này được nối bằng n cạnh mới đến các đỉnh v1 v2 . vn. Dễ thấy rằng Gn 1 không chứa K3 và có sắc số là n 1. . Định lý Định lý 5 màu của Kempe-Heawood Mọi đồ thị phẳng đều có thể tô đúng bằng 5 màu. 104 Chứng minh Cho G là một đồ thị phẳng. Không mất tính chất tổng quát có thể xem G là liên thông và có số đỉnh n 5. Ta chứng minh G được tô đúng bởi 5 màu bằng quy nạp theo n. Trường hợp n 5 là hiển nhiên. Giả sử định lý đúng cho tất cả các đồ thị phẳng có số đỉnh nhỏ hơn n. Xét G là đồ thị phẳng liên thông có n đỉnh. Theo Hệ quả trong G tồn tại đỉnh a với deg a 5. Xoá đỉnh a và các cạnh liên thuộc với nó ta nhận được đồ thị phẳng G có n-1 đỉnh. Theo giả thiết quy nạp có thể tô đúng các đỉnh của G bằng 5 màu. Sau khi tô đúng G rồi ta tìm cách tô đỉnh a bằng một màu khác với màu của các đỉnh kề nó nhưng vẫn là một trong 5 màu đã dùng. Điều này luôn thực hiện được khi deg a 5 hoặc khi deg a 5 nhưng 5 đỉnh kề a đã được tô bằng 4 màu trở xuống. Chỉ còn phải xét trường hợp deg a 5 mà 5 đỉnh kề a là b c d e f đã được tô bằng 5 màu rồi. Khi đó trong 5 .

• Toán học
• thuật toán
• khái niệm thuật toán
• toán rời rạc
• giáo trình toán rời rạc
• tài liệu toán rời rạc
• Thuật toán và tư duy thuật toán
• Đặc trưng cơ bản về thuật toán
• Thiết kế thuật toán
• Hiệu quả giảng dạy thuật toán
• Cài đặt thuật toán
• Vấn đề tư duy thuật toán
• Ngôn ngữ lập trình
• Bài giảng thuật toán
• Biểu diễn thuật toán
• Kỹ thuật thiết kế thuật toán
• Phân tích thuật toán
• Đáng giá thuật toán
• Thuật toán máy tính
• Thuật toán tham lam
• Đánh giá thuật toán
• Bài giảng đánh giá thuật toán
• Bài giảng thiết kế thuật toán
• Bài toán sắp xếp
• Sắp xếp chèn
• Tự học lập trình
• Bài giảng Tin học 10
• Bài giảng Tin học 10 Bài 4
• Bài 4 Bài toán và thuật toán
• Bài giảng Bài toán và thuật toán
• Khái niệm bài toán
• Thuật toán tìm Max của một dãy số
• Cẩm nang thuật toán
• Phương pháp giải thuật toán
• Thuật toán thông dụng
• Thuật toán sắp xếp
• Thuật toán tìm kiếm
• Thuật toán xử lý chuỗi
• Thuật toán chuyên dụng
• Một số vấn đề về thuật toán
• Độ phức tạp thuật toán
• Phương pháp trong thuật toán
• Tính đúng đắn của thuật toán
• thuật toán DDA
• thuật toán bresenham
• thuật toán đường tròn
• thuật toán MidPoint
• thuật toán vẽ Ellipse
• Thuật toán tô màu
• Bài giảng Phân tích thuật toán
• Tính chất cơ bản của thuật toán
• Độ phức tạp của thuật toán
• Ước lượng tiệm cận
• Thuật toán Google
• Thuật toán Sand
• Thuật toán chim ruồi
• Thuật toán ngựa vằn Zebra Box
• Thuật toán Chim cánh cụt
• Thuật toán Gấu trúc Panda
• Đề thi cuối kì môn Toán kỹ thuật
• Bài thi môn Toán kỹ thuật
• Ôn thi Toán kỹ thuật
• Luyện thi Toán kỹ thuật
• Tài liệu thi Toán kỹ thuật
• Hướng dẫn thi Toán kỹ thuật
• Lý thuyết thuật toán tìm đường
• Thuật toán tìm đường
• Thuật toán tìm đường đi ngắn nhất
• Thuật toán tìm đường đi
• Xây dựng thuật toán
• Thuật toán xử lý thông tin
• Đặc trưng của thuật toán
• Thuật toán Euclid cải tiến
• Ngôn ngữ thuật toán
• Diễn tả thuật toán
• Phân tích thiết kế thuật toán
• Đề thi Phân tích thiết kế thuật toán
• Câu hỏi Phân tích thiết kế thuật toán
• Ôn tập Phân tích thiết kế thuật toán
• Trình diễn thuật toán
• Thuật toán nâng cao
• Bài giảng Thuật toán nâng cao
• Tính chất của thuật toán
• Đặc tả thuật toán
• Bài giảng Thuật toán Ứng dụng
• Thuật toán Ứng dụng
• Quy hoạch động
• Bài giảng Phân tích thiết kế thuật toán
• Kỹ thuật phân tích thuật toán
• Đánh giá một giải thuật
• Khóa luận tốt nghiệp
• Khóa luận tốt nghiệp Kế toán Kiểm toán
• Kế toán Kiểm toán
• Kế toán thanh toán
• Nguyên tắc kế toán thanh toán với người mua
• Nguyên tắc kế toán thanh toán với người bán
• Thuật toán gần đúng
• Bài toán tối ưu tổ hợp
• Tối ưu tổ hợp
• Toán tối ưu tổ hợp
• Ứng dụng thuật toán gần đúng
• Tìm hiểu thuật toán gần đúng
• Tài liệu thuật toán gần đúng
• Sáng kiến kinh nghiệm
• Bài tập xây dựng thuật toán giải bài toán
• Thuật toán giải bài toán
• Xây dựng thuật toán máy tính
• Kỹ thuật kiểm toán
• tài liệu Kỹ thuật kiểm toán
• bài giảng Kỹ thuật kiểm toán
• kế toán kiểm toán
• nghiệp vụ kế toán
• kế toán tài chính
• kế toán doanh nghiệp