Bài giảng Chương 10: Đồ thị phẳng

CHƯƠNG 10ĐỒ THỊ PHẲNG1NỘI DUNGBài toán ba biệt thự và ba nhà máyĐồ thị phẳngCác điều kiện cho tính phẳng của đồ thịSắc số của đồ thị phẳng210.1. BÀI TOÁN BA BIỆT THỰ VÀ BA NHÀ MÁYBài toán: Trong một thị trấn có ba biệt thự và ba nhà máy cung cấp: điện, nước và khí đốt. 	Mỗi biệt thự đều muốn mắc đường cáp điện ngầm, đường ống cấp nước, đường ống cấp khí đốt riêng từ nhà mình đến ba nhà máy mà không gặp đường ống của các biệt thự khác. 	Hỏi rằng có làm được những đường đi như thế hay không?310.1. BÀI TOÁN BA BIỆT THỰ VÀ BA NHÀ MÁY (tiếp)ABC123ĐiệnNướcGas410.2. ĐỒ THỊ PHẲNGĐịnh nghĩa 10.1	Đa đồ thị vô hướng G được gọi là đồ thị phẳng nếu có thể biểu diễn nó trên mặt phẳng sao cho không có hai cạnh nào cắt nhau, trừ tại đỉnh. 	- Diện hữu hạn của một đồ thị phẳng là một miền kín của mặt phẳng được giới hạn bằng các cạnh của đồ thị sao cho có thể nối hai điểm bất kỳ thuộc diện này bằng một nét liền mà không cắt một cạnh nào. 	- Đồ thị còn có một diện vô hạn, đó là phần bù trên mặt phẳng của hợp các diện hữu hạn. 510.2. ĐỒ THỊ PHẲNG (tiếp)Định lý 10.1: Số diện hữu hạn của một đa đồ thị phẳng G bằng chu số của đồ thị này.Chứng minh: Quy nạp theo số diện hữu hạn h của G.h = 1: chỉ có một chu trình đơn duy nhất, đó chính là biên của diện này. Suy ra chu số bằng 1.- (h-1)  (h) : Giả sử đồ thị phẳng G với n đỉnh, m cạnh và p mảng liên thông có h diện. 610.2. ĐỒ THỊ PHẲNG (tiếp)Chứng minh định lý:	Lập đồ thị G’ từ G bằng cách bớt đi cạnh e nào đó trên biên của một diện để số diện hữu hạn bớt đi 1. Khi đó, G’ có h-1 diện. 	Theo giả thiết quy nạp, c(G’) = h-1 = (m - 1) - n + p (p không đổi vì chỉ bớt đi một cạnh trên chu trình). 	Suy ra, số diện hữu hạn của G là:	 h = m - n +p = c(G).   710.1. ĐỒ THỊ PHẲNG (tiếp)Hệ quả 10.1 	Nếu đa đồ thị phẳng G có n đỉnh, m cạnh, p mảng liên thông và h diện thì: n - m + h = p +1 (công thức Euler tổng quát)Chứng minh:	Số diện của đồ thị phẳng bằng số diện hữu hạn cộng thêm 1 (diện vô hạn), bằng chu số cộng 1. Vậy thì, 	h = m - n + p +1. 	Do đó, n - m + h = p +1. 810.2. ĐỒ THỊ PHẲNG (tiếp)Hệ quả 10.2 	Trong một đơn đồ thị phẳng có ít nhất một đỉnh có bậc không quá 5.Chứng minh: 	Không mất tính tổng quát có thể giả thiết rằng đơn đồ thị là liên thông. 	Trong đơn đồ thị phẳng mỗi diện hữu hạn được giới hạn bởi ít nhất 3 cạnh, mà mỗi cạnh thuộc nhiều nhất là hai diện nên: 3h ≤ 2m  h ≤ 2m/3.910.2. ĐỒ THỊ PHẲNG (tiếp)	Phản chứng: Giả sử mọi đỉnh của đồ thị G đều có bậc ít nhất là 6. 	Khi đó, tổng tất cả các bậc của các đỉnh của trong G = 2m  6n.	Theo công thức Euler thì: n - m + h = 1 + p = 2	Ta có: . Suy ra điều vô lý. 1010.3. CÁC ĐIỀU KIỆN CHO TÍNH PHẲNG CỦA ĐỒ THỊĐịnh lý 10.2 Giả sử G là một đồ thị và G’ là đồ thị con của nó. Đồ thị G phẳng thì G’ cũng phẳng.Đồ thị G’ không phẳng thì G cũng không phẳng.1110.3. CÁC ĐIỀU KIỆN CHO TÍNH PHẲNG CỦA ĐỒ THỊ (tiếp)Ký hiệu:  là độ dài của chu trình ngắn nhất hoặc là số cạnh của đồ thị G nếu không có chu trình. 	Số  được gọi là đai của đồ thị. Định lý 10.3Nếu G là đồ thị phẳng n đỉnh và đai của nó là  ≥ 3thì: m ≤  (n-2)/( -2).Chứng minh: Do h. ≤ 2m nên theo công thức Euler:  (m - n + 2) ≤ 2m. Suy ra điều phải chứng minh. 12VÍ DỤ 10.1Bài toán ba biệt thự và ba nhà máy:Đai của đồ thị trên là  = 4. Vậy thì: m = 9 > 4.(6-2)/(4-2) = 8Theo Định lý 10.5, đồ thị trên không phẳng.1310.3. CÁC ĐIỀU KIỆN CHO TÍNH PHẲNG CỦA ĐỒ THỊ (tiếp)	Đồ thị hai phần đầy đủ Km,n là một đơn đồ thị có m+n đỉnh gồm m đỉnh “bên trái” và n đỉnh “bên phải” sao cho mỗi đỉnh “bên trái” đều kề với mọi đỉnh “bên phải”.	K2,2	 K2,31410.3. CÁC ĐIỀU KIỆN CHO TÍNH PHẲNG CỦA ĐỒ THỊ (tiếp)Hệ quả 10.3 Đồ thị hai phần đầy đủ Km,n là đồ thị phẳng khi vàchỉ khi m  2 hoặc n  2.15VÍ DỤ 10.2	Đồ thị đầy đủ 5 đỉnh:Đồ thị có đai  = 3. Vậy	m = 10 > 3.(5-2)/(3-2) = 9Đồ thị K5 không phẳng. Từ đó suy ra, đồ thị đầy đủ Kn với n  5 là không phẳng. adbce1610.3. CÁC ĐIỀU KIỆN CHO TÍNH PHẲNG CỦA ĐỒ THỊ (tiếp)Định lý 10.3 (Kuratowski) 	Đồ thị là phẳng khi và chỉ khi nó không chứa cấu hình K3,3 hoặc K5. Ta có thể áp dụng định lý Kuratowski để xét tính chất phẳng của đồ thị.17VÍ DỤ 10.3Xét đồ thị sau đây (bên phải) và hình vẽ lại của nó (bên trái):Đồ thị này chứa cấu hình K5. Do vậy, nó không phẳng. 	adbceeeadbcecc1810.4. SẮC SỐ CỦA ĐỒ THỊ PHẲNGĐịnh lý 10.4 (Kemple - Heawood)	Mọi đồ thị phẳng không có đỉnh nút đều có sắc số không lớn hơn 5. Chứng minh: 	Quy nạp theo số đỉnh n của đồ thị.- n = 1, 2, 3, 4, 5 : Hiển nhiên đúng.- (n-1)  (n): theo Hệ quả 10.3, G có ít nhất 1 đỉnh x bậc không quá 5.Bỏ đỉnh x ra khỏi G, ta được G’. 1910.4. SẮC SỐ CỦA ĐỒ THỊ PHẲNG (tiếp)	Theo quy nạp, G’ có sắc số không vượt quá 5.	Lấy một cách tô màu nào đấy của G’. 	- Nếu các đỉnh kề với đỉnh x được tô bằng ít hơn 5 màu thì vẫn còn thừa màu để tô cho x. 	Sắc số của G bằng sắc số của G’.2010.4. SẮC SỐ CỦA ĐỒ THỊ PHẲNG (tiếp)	- Nếu đỉnh x kề với 5 đỉnh và các đỉnh kề với x được đánh số thứ tự theo chiều kim đồng hồ và tô bằng 5 màu thì ta đổi màu của các đỉnh để dành ra màu cho đỉnh x.	5 e 4 d1 a2 b3 cx2110.4. SẮC SỐ CỦA ĐỒ THỊ PHẲNG (tiếp)	Xét tất cả các đường đi trong G bắt đầu từ đỉnh a và chỉ gồm các đỉnh tô bằng màu 1 và màu 3. 	Xét hai trường hợp:	1) Trong các đường này không có đường nào đi qua đỉnh c thì ta có thể tráo đổi màu 1 với màu 3 cho tất cả các đỉnh trên các đường đi ấy. Sau đó, ta tô màu 1 cho đỉnh x. 	2210.4. SẮC SỐ CỦA ĐỒ THỊ PHẲNG (tiếp)	2) Ngược lại, nếu có đường đi từ a đến c gồm toàn các đỉnh được tô bằng màu 1 hoặc 3 thì đường này cùng hai cạnh (c,x) và (x,a) tạo thành chu trình trong G. 	Do tính phẳng nên hai đỉnh b và d không thể cùng nằm bên trong hoặc bên ngoài chu trình này được. Suy ra, không có đường đi nào nối b với d gồm các đỉnh chỉ tô màu 2 hoặc 4. 	Vậy lại có thể tráo đổi màu 2 với màu 4 cho các đỉnh trên các đường đi qua đỉnh b. Khi đó hai đỉnh b và d cùng màu 4. 	Tô màu 2 cho đỉnh x.  23BÀI TOÁN BỐN MÀUBài toán: Vào khoảng năm năm mươi của thế kỷ 19 Gazri, một thương gia người Anh, khi tô màu bản đồ hànhchính nước mình, đã nhận ra rằng luôn có thể tô đượcbằng 4 màu. Năm 1852 ông ta thông báo giả thuyết này cho DeMorgan.Năm 1878 Keli đã đăng bài toán trên trong Tuyểntập các công trình của Hội Toán học Anh, gây nên sựchú ý của nhiều người. 24BÀI TOÁN BỐN MÀU (tiếp)- Năm 1976, ba nhà khoa học người Mỹ là K.Appel, W. Haken và J. Koch chứng minh bằng máy tính điện tử được rằng giả thuyết của Gazri là đúng.Định lý 10.5 (Appel - Haken):	Mọi đồ thị phẳng không có đỉnh nút đều có sắc số không quá 4.	Dễ thấy rằng, đồ thị vô hướng đầy đủ Kn (n  5) có sắc số lớn hơn 4 nên không phẳng.25