Đồ thị phẳng

Chia sẻ: Lê Văn Tình | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

259
lượt xem 58
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Thêm vào 1 đỉnh nằm trên 1 cạnh hay gộm 2 cạnh có chung đỉnh bậc 2 thành 1 cạnh.
-Đồ thị đồng phôi: -Hai đồ thị được gọi là đồng phôi nếu mỗi đồ thị có được từ đồ thị kia bằng các thực hiện một dãy các phép biến đổi đồng phôi.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đồ thị phẳng

ÑOÀ THÒ PHAÚNG NG Ñònh nghóa Ñoà thò phaú phaúngng Moä Moät ñoà thò voâ hö höôùng ng G ñöô ñöôïc goï goïi laø laø phaú phaúng ng neá neáu toà toàn taï taïi moä moät caù caùch ch veõ G trong maë maët phaú phaúng ng sao cho khoâng coù coù hai caï caïnh nh naø naøo cuû cuûa G caé caét nhau. Khi G laø laø moä moät ñoà thò phaú phaúng ng thì thì moãi caù caùch ch veõ G trong maëmaët phaú phaúng ng (sao cho khoâng coù coù hai caï caïnh nh naø naøo cuû cuûa G caé caét nhau) ñöô ñöôïc goï goïi laø laø moä moät bieå bieåu dieãn phaú phaúng ng cuû cuûa G. Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 2 1
Ñònh nghóa Ghi chuù chuù: hai caï caïnh nh coù coù chung moä moät ñænh ñænh ñöô ñöôïc qui öôùc laø laø khoâng caé caét nhau Caét nhau Khoâng caét nhau Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 3 Ñònh nghóa Ví duï duï Ñoà thò (G1) laø laø ñoà thò phaú phaúng ng vaø vaø caù caùc ñoà thò (G2), (G3) laø laø caù caùc bieå bieåu dieãn phaú phaúng ng cuû cuûa (G1). (G2) (G1) (G3) Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 4 2
Ñònh nghóa (b) Pheù Pheùp bieá bieán ñoåi ñoàng ng phoâi Theâm vaø vaøo 1 ñænh ñænh naè naèm treân 1 caï caïnh, nh, hay goägoäp 2 caï caïnh nh coù coù chung ñænh nh ñæ ba baää c 2 thaøønh 1 caï tha nh ca nh. ï nh. (c) Ñoà thò ñoàngng phoâi Hai ñoà thò ñöôñöôïc goïgoïi laø laø ñoàng ng phoâi neáneáu moãi ñoà thò coù coù ñöô ñöôïc töø ñoà thò kia baè baèng ng caù caùch ch thöï thöïc hieä hieän moä moät daõy caù caùc pheù pheùp bieá bieán ñoåi ñoàng ng phoâi. Ñònh lyùlyù: Neá Neáu G laø laø moä moät ñoà thò phaú phaúng ng thì thì ta coù coù theå theå tìm moä moät ñoà thò G1ñoàng ng phoâi vôù vôùi G sao cho coù coù theå theå veõ G1 baèbaèng ng caù caùch ch chæ chæ duø duøng ng caù caùc ñoaï oaïn thaú thaúng. ng. Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 5 Ñònh nghóa Caù Caùc ñoà thò sau ñaây ñoàng ng phoâi: Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 6 3
Caùc pheùp ruùt goïn cô baûn treân ñoà thò Tính phaú phaúng ng cuû cuûa moä moät ñoà thò khoâng thay ñoåi neá neáu thöï thöïc hieä hieän moä moät hay nhieà nhieàu laà laàn caù caùc pheù pheùp ruù ruùt goï goïn sau ñaây: Boû Boû ñi caù caùc khuyeân Boû Boû bôù bôùt caù caùc caï caïnh nh song song (chæ (chæ giö giöõ laï laïi moä moät caï caïnh nh noá noái hai ñænh). ñænh). Goä Goäp hai caï caïnh nh coù coù chung ñænh ñænh baä baäc 2 thaø thaønh nh moä moät caï caïnh. nh. Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 7 Caùc pheùp ruùt goïn cô baûn treân ñoà thò Boû ñænh baäc 2 Boû caïnh ssong Boû ñænh baäc 2 Boû caïnh ssong Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 8 4
Ñònh lyù Kuratowski Ñònh lyù lyù 1: Ñoà thò ñuû K5 khoâng phaú phaúng. ng. K5 Ñònh lyù lyù 2: Ñoà thò lö löôõng phaân ñuû K3,3 khoâng phaú phaúng. ng. K3, 3 Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 9 Ñònh lyù Kuratowski Nhaä Nhaän xeù xeùt: t: Hai ñoà thò K5 vaø vaø K3,3 laø laø caù caùc ñoà thò khoâng phaú phaúngng ñôn giaû giaûn nhaá nhaát vôù vôùi caù caùc tí tính chaá chaát sau Neá Neáu xoù xoùa ñi 1 ñænh ñænh hay 1 caï caïnh nh cuû cuûa 2 ñoà thò treân thìthì chuù chuùng ng ta seõ coù coù ñöô ñöôïc ñoà thò phaú phaúng. ng. Ñoà thò K5 laø laø ñoà thò khoâng phaú phaúng ng coù coù ít ñænh ñænh nhaá nhaát.t. Ñoà thò K3,3 laø laø ñoà thò khoâng phaú phaúng ng coù coù ít caï caïnh nh nhaá nhaát.t. Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 10 5
Ñònh lyù Kuratowski Ñònh lyù lyù 3: Ñieà ieàu kieä kieän caà caàn vaø vaø ñuû ñeå moä moät ñoà thò lieân thoâng G coù coù tính phaú ú ng pha ng la laø ø G khoâ n g chöù öù a baá ch ba ky át kyø ø ñ o à thò con naø naøo ñoàng ng phoâi vôùvôùi K5 hay K3,3. Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 11 Ñònh lyù Kuratowski 1 2 2 6 6 Ñoàng Ñoà thò phoâi 3 con 1 4 4 2 6 5 7 5 7 3 1 4 7 Veõ laïi 4 5 6 5 7 2 Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 12 6
Coâng thöùc Euler Ñònh lyù lyù: Cho G laø laø ñoà thò phaú phaúng, ng, lieân thoâng goà goàm n ñænh, ñænh, e caï caïnh. nh. Giaû Giaû söû G chia maë maët phaú phaúng ng ra laø laøm f vuø vuøng, ng, ta coù coù coâng thöù thöùc sau (coâng thöù thöùc Euler): f=e-n+2 Heä Heä quaû quaû: Neá Neáu G laø laø ñoà thò ñôn, phaú phaúng, ng, lieân thoâng, goà goàm n ñænh ñænh vaø vaø e caï caïnh nh (vôù (vôùi e > 2). Giaû Giaû söû G chia maë maët phaú phaúng ng ra thaø thaønh nh f vuø vuøng. ng. Ta coù coù: e ≥ (3/2)f e ≤ 3n - 6 Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 13 Coâng thöùc Euler Ví duï duï, aù aùp duï duïng ng heä heä quaû quaû naà naày ñeå chöù chöùng ng minh títính khoâng phaú phaúng ng cuû cuûa K5. K5 laø laø ñoà thò ñôn vaøvaø lieân thoâng coù coù v=5 vaø vaø e=10, ta coù coù e=10 > 9=3v- 9=3v-6 do ñoù K5 khoâng phaú phaúng ng (chuù (chuù yù raè raèng ng ñaûo laï laïi neá neáu moä moät ñoà thò thoû thoûa maõn e ≤ 3v – 6 thìthì chö chöa chaé chaéc laø laø ñoà thò phaú phaúng, ng, K3,3 laø laø moä moät ví ví duï duï). ). Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 14 7
Toâ maøu ñoà thò Saé Saéc soá soá cuû cuûa ñoà thò Moä Moät pheù pheùp toâ maømaøu ñoà thò laø laø moä moät caù caùchch ñaùnh nh nhaõn cho moãi ñænhnh ñæ cu cuûû a ñ o à thò baèè ng moä ba ng mo ma ät maøø u sao cho 2 ñænh ñænh keà keà nhau phaû phaûi ñöô ñöôïc ñaùnh nh nhaõn khaùkhaùc nhau. Saé Saéc soá soá cuû cuûa moämoät ñoà thò G, kyù kyù hieä hieäu γ(G), laø laø moä moät soá soá nguyeân dö döông k nhoû nhoû nhaá nhaát sao cho toà toàn taï taïi moä moät pheù pheùp toâ maø maøu G chæ chæ söû duï duïng ng k maø maøu.u. Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 15 Toâ maøu ñoà thò γ(G)=4 Ñ γ(Kn)=n,∀ )=n,∀n∈|N (G) γ(Km, n)=2, ∀m, n∈ n∈|N X V T X Ñ Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 16 8
Toâ maøu ñoà thò Moä Moät vaø vaøi tí tính chaá chaát veà veà saé saéc soá soá Neá Neáu ñoà thò G coù coù chöù chöùa ít nhaá nhaát moä moät caï caïnh nh khoâng phaû phaûi laø laø khuyeân thì ì th (G) γ (G)≥≥ 2. Ñoà thò ñuû n ñænh ñænh Kn coùcoù saé saéc soá soá laø laø n. Neá Neáu ñoà thò G chöù chöùa moä moät ñoà thò con ñaúng caáu Kr thì ng caá thì γ(G)≥ (G)≥ r. Neá Neáu ñoà thò G laø laø moä moät chu trì trình sô caácaáp n ñænh ñænh thì thì: γ(G)= 2 neá neáu n chaú chaún, n, γ(G)= 3 neáneáu n leû leû; γ(G)= (n mod 2) + 2. Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 17 Toâ maøu ñoà thò Ñònh lyù lyù 1. Neá Neáu T laø laø moä moät caây n ñænh ñænh vôù vôùi n≥ n≥2 thì thì γ(T)= 2. Ñònh lyù lyù 2. Cho G laø laø ñoà thò lieân thoâng coù coù ít nhaá nhaát 1 caï caïnh. nh. Khi ñoù γ(G)=2 khi vaø vaø chæ chæ khi G khoâng chöù chöùa chu trì trình sô caá caáp coù coù soá soá caï caïnh nh leû leû. Ñònh lyù lyù 3. Cho ñoà thò G=(X, E). Goï Goïi d(G)=max{d(x)/x∈ d(G)=max{d(x)/x∈X}. Ta coù coù: γ(G)≤ (G)≤ d(G)+1. Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 18 9
Baøi toaùn saéc soá cuûa ñoà thò phaúng ng Lòch söû söû veà veà giaû giaû thuyeá thuyeát 4 maø maøu Khoaû Khoaûng ng 10/1852, giaù giaùo sösö De Morgan ôû ôû trö tröôøng ng Ñaïi hoï hoïc Luaân Ñoân vieá á vie tht thöö cho ñ o à ng nghieä ä ng nghie cu mp cuûû a mìình laø la ø oâng Sir William Hamilton ñeå baø baøn veà veà baø baøi toaù toaùn:n: “MoïMoïi baû baûn ñoà ñeàu coù coù theå theå toâ baè baèng ng 4 maø maøu sao cho hai nö nöôùc naè naèm keàkeà nhau phaû phaûi ñöôñöôïc toâ baèbaèng ng hai maømaøu khaùkhaùc nhau” nhau”. Sau ñoù coù coù nhieà nhieàu coá coá gaé gaéng ng cuû cuûa moä moät soá soá nhaø nhaø toaù toaùn hoïhoïc ñeå giaû giaûi baø baøi toaù toaùn naànaày nhö nhöng ñeàu khoâng ñi ñeán keá keát quaû quaû cuoá cuoái cuø cuøng. ng. Ñaëc bieä bieät coùcoù moä moät lôølôøi giaû giaûi bò sai (phaû (phaûi sau 10 naêm môù môùi phaùphaùt hieähieän ñöô ñöôïc choã khoâng ñuùng ng trong lôø lôøi giaû giaûi), i), nhö nhöng lyù lyù luaä luaän cuû cuûa lôø lôøi giaû giaûi naà naày ñuùng ng cho “baø baøi toaù toaùn 5 maø ma ø u ” . Vaø Va ø o naê m 1976, ... Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 19 Baøi toaùn saéc soá cuûa ñoà thò phaúng ng Ñònh lyù lyù 5 maø maøu: u: moï moïi ñoà thò phaú phaúng ng coù coù theå theå toâ baè baèng ng 5 maø maøu Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 20 10
Baøi toaùn saéc soá cuûa ñoà thò phaúng ng Lieân quan giö giöõa giaû giaû thuyeá thuyeát 4 maø maøu vaø vaø saé saéc soá soá ñoà thò phaú phaúng ng Lyù Thuyeát Ñoà Thò - Ñoà Thò Phaúng - Khoa CNTT - Ñaïi Hoïc KHTN 21 11