1
Ths. Nguyễn Khắc Quốc
IT.Deparment – Tra Vinh University
CHƯƠNG 4
ĐỒ THỊ PHẲNG VÀ TÔ MÀU ĐỒ THỊ
ThS. Nguyễn Khắc Quốc 2
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.
ThS. Nguyễn Khắc Quốc 3
- 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?
Chúng ta sẽ nghiên cứu bài toán:
BÀI TOÁN (tt).
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?
ThS. Nguyễn Khắc Quốc 4
4.1.1. Đị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.
4.1. ĐỒ THỊ PHẲNG.
ThS. Nguyễn Khắc Quốc 5
K4là đồ thị phẳng bởi vì có thể vẽ lại như hình dưới
không có đường cắt nhau
4.1. ĐỒ THỊ PHẲNG (tt).
Đồ thị K4
K4 vẽ không cắt nhau
Vẽ lại K4
Thí dụ: