Tài liệu Đồ thị phẳng và bài toán tô màu đồ thị

?? TH? PH?NG V￀ B￀I TO￁N Tￔ M￀U ?? TH?

I. ?? th? ph?ng
1. B￠i to￡n m? ??u
2. ?? th? ph?ng
3. C￴ng th?c Euler
4. ??nh l Kuratowski
II. B￠i to￡n t￴ m￠u ?? th?
1. B￠i to￡n m? ??u
2. T￴ m￠u ?? th?
3. M?t s? ??nh l v? t￴ m￠u ?? th?
4. Thu?t to￡n Welch-Powell v? t￴ m￠u ?? th?
5. ?ng d?ng c?a b￠i to￡n t￴ m￠u

I. ?? th? ph?ng TOP


1. B￠i to￡n m? ??u TOP


?? nghi￪n c?u v? ?? th? ph?ng, ta b?t ??u b?ng vi?c x￩t b￠i to￡n Ba nh￠ ba gi?ng nh? sau:
C￳ ba nh￠ ? g?n ba c￡i gi?ng, t? m?i nh￠ c￳ ???ng ?i th?ng ??n t?ng 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 h￲a 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?
Ta x￢y d?ng ?? th? G = (V, E) m￴ t? ??y ?? c￡c th￴ng tin c?a b￠i to￡n:
+ ??nh: L?y c￡c ?i?m tr￪n m?t ph?ng hay trong kh￴ng gian t??ng ?ng v?i c￡c gia ?￬nh v￠ c￡c gi?ng n??c. ??i t??ng c?a b￠i to￡n ? ?￢y ???c chia l￠m hai lo?i l￠ gia ?￬nh v￠ gi?ng n??c. V?y, m?i ??nh bi?u di?n cho m?t gia ?￬nh ho?c m?t gi?ng n??c.
+ C?nh: Trong ?? th? G c￡c ??nh v￠ ???c n?i v?i nhau b?ng m?t c?nh n?u c￳ ???ng n?i th?ng (tr?c ti?p) t? m?t gia ?￬nh ??n m?t gi?ng n??c. V?y, m?i quan h? gi?a 02 ??i t??ng ? ?￢y l￠ m?i quan h????ng ?i. M?i c?nh n?i 2 ??nh (??i di?n cho 01 gia ?￬nh) v￠ (??i di?n cho m?t gi?ng n??c) trong G n?u c￳ ???ng ?i tr?c ti?p t? gia ?￬nh ??n gi?ng n??c . Ta c￳ ?? th? G nh? sau:

Khi gi?i quy?t b￠i to￡n tr￪n ta c?n ??n kh￡i ni?m ?? th? ph?ng nh? sau:
2. ?? th? ph?ng TOP


2.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 ? ?i?m kh￴ng ph?i l￠ ?i?m mt c?a m?i c?nh. H￬nh v? nh? v?y ???c g?i l￠ m?t bi?u di?n ph?ng c?a ?? th?.
2.2. C￡c v￭ d?
V￭ d? 1: K4 l￠ ?? th? ph?ng v￬ c￳ th? v? l?i nh? sau:

V￭ d? 2: Q3 c?ng l￠ ?? th? ph?ng v￬:

V￭ d? 3: Ta s? x￩t xem ?? th? l??ng ph￢n K3,3 c￳ l￠ ?? th? ph?ng kh￴ng?