TAILIEUCHUNG - [Giáo trình Toán rời rạc] - Chương7 - Tô màu Đồ thị

Tài liệu " [Giáo trình Toán rời rạc] - Chương7 - Tô màu Đồ thị " mang tính chất tham khảo, giúp ích cho các bạn tự học, ôn thi, với phương pháp học hay, thú vị, rèn luyện kỹ năng giải đề, nâng cao vốn kiến thức cho các bạn trong các kỳ thi sắp tới. Tác giả hy vọng tài liệu này sẽ giúp ích cho các bạn. | http Tải miễn phí Đề thi eBook Tài liệu học tập CHƯƠNG VII ĐÒ THỊ PHẲNG VÀ TÔ MÀU ĐÒ THỊ Từ xa xưa đã lưu truyền một bài toán cổ Ba nhà ba giếng Có ba nhà ở gần ba cái giếng nhưng không có đường nối thẳng các nhà với nhau cũng như không có đường nối thẳng các giếng với nhau. Có lần bất hoà với nhau họ tìm cách làm các đường khác đến giếng sao cho các đường này đôi một không giao nhau. Họ có thực hiện được ý định đó không Bài toán này có thể được mô hình bằng đồ thị phân đôi đầy đủ K3 3. Câu hỏi ban đầu có thể diễn đạt như sau Có thể vẽ K3 3 trên một mặt phẳng sao cho không có hai cạnh nào cắt nhau Trong chương này chúng ta sẽ nghiên cứu bài toán có thể vẽ một đồ thị trên một mặt phẳng không có các cạnh nào cắt nhau không. Đặc biệt chúng ta sẽ trả lời bài toán ba nhà ba giếng. Thường có nhiều cách biểu diễn đồ thị. Khi nào có thể tìm được ít nhất một cách biểu diễn đồ thị không có cạnh cắt nhau . ĐÒ THỊ PHẲNG. . Định nghĩa Một đồ thị được gọi là phẳng nếu nó có thể vẽ được trên một mặt phẳng mà không có các cạnh nào cắt nhau ở một điểm không phải là điểm mút của các cạnh . Hình vẽ như thế gọi là một biểu diễn phẳng của đồ thị. Một đồ thị có thể là phẳng ngay cả khi nó thường được vẽ với những cạnh cắt nhau vì có thể vẽ nó bằng cách khác không có các cạnh cắt nhau. Thí dụ 1 1 Một cây một chu trình đơn là một đồ thị phẳng. 2 K4 là đồ thị phẳng bởi vì có thể vẽ lại như hình bên không có đường cắt nhau 3 Xét đồ thị G như trong hình a dưới đây. Có thể biểu diễn G một cách khác như trong hình b trong đó bất kỳ hai cạnh nào cũng không cắt nhau. b d b 104 http Tải miễn phí Đề thi eBook Tài liệu học tập 4 Đồ thị đầy đủ K5 là một thí dụ về đồ thị không phẳng xem Định lý . . Định nghĩa Cho G là một đồ thị phẳng. Mỗi phần mặt phẳng giới hạn bởi một chu trình đơn không chứa bên trong nó một chu trình đơn khác gọi là một miền hữu hạn của đồ thị G. Chu trình giới hạn miền là biên của miền. Mỗi đồ thị phẳng liên thông có một miền vô .

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.