Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ứ
ụ
ề
ế
ườ
ng THPT Th t N t ố ố
L I M Đ U Ờ Ở Ầ
ớ ướ
ệ ủ Nhi m v đ i m i ph ụ ổ ọ
ị ủ ự
ươ ươ ớ ạ ộ ng tích c c hóa ho t đ ng ự ọ ng mà còn đòi h i c n nghiên c u xác ứ ỏ ầ ng pháp d y h c tích c c. Vi c ệ ọ ạ ư ng pháp d y h c đ c thù nh ọ ạ ặ
ươ ng pháp Graph là m t gi t. ả ộ
ng pháp d y h c theo h ạ ươ h c t p c a h c sinh không ch là đ nh h ướ ỉ ọ ậ đ nh nguyên t c, quy trình v n d ng c a nh ng ph ậ ụ ữ ắ ị ng pháp truy n th ng v i các ph k t h p các ph ế ợ ố ề i pháp t ph ố ươ ộ ạ ọ
ế ồ ị ề ọ
ọ ổ
ng đ ệ ế ồ ị ắ ể ộ ứ
ị ể ậ ủ ự ậ
ượ ứ c ng Lý thuy t đ th (Graph) là m t chuyên ngành toán h c hi n đ i đã đ d ng vào nhi u ngành khoa h c, kĩ thu t khác nhau vì lý thuy t đ th toán h c là ụ ọ ậ ng pháp khoa h c có tính khái quát cao, có tính n đ nh v ng ch c đ mã hóa các ph ữ ươ c nghiên c u. Có th nói Graph là m t phép Toán m i quan h c a các đ i t ố ượ ố ượ ệ ủ th n kì kích thích s ho t đông, óc t ộ duy, suy lu n c a trí não th m chí còn là m t ư ạ ầ câu tr l ố ố
i thông minh, logic cho các câu đ h c búa. ả ờ ạ ệ ụ ậ ằ
ng chuyên Tin) và đ ng THPT (nh t là các tr ọ ọ ấ ườ
ộ ữ ớ ừ ế ậ ừ ổ
ọ ề
ạ ề
ọ ứ ả ộ ố ng này, có nhi u tác gi ạ
c đ u. Năm 1980, tác gi ả ế
ề ầ ươ
ả ứ
ổ ạ ư ủ
ớ i, xây d ng h th ng v l p công th c hoá h c ề ậ ẫ ủ ể ạ
ơ ươ ổ
ng trình t ươ ậ
ử i u đ ố ư ỉ ễ ọ ổ
ứ ụ ế
ề i ph u - Sinh lý ng i (năm 2005). Đ i v i ph ứ ố ớ ườ ươ ả ẫ
ọ ọ
ng pháp graph trong d y h c Toán nh m nâng cao ch t ấ Vi c v n d ng ph ọ ươ l ượ c tr ng d y h c môn h c này ở ườ ượ ạ ệ ố xem nh là m t trong nh ng hành trang m i v a ti p c n v a b sung vào h th ng ư các ph ng pháp d y h c truy n th ng song đó còn làm phong phú thêm kho tàng các ạ ươ ố đã thành công trong ng pháp d y h c Toán . Theo h ph ọ ướ ươ vi c nghiên c u và v n d ng lý thuy t Graph vào d y h c m t s môn h c tr ọ ở ườ ng ậ ụ ệ ế ọ Tr n Tr ng ph thông và đã có nh ng k t qu b ầ ả ướ ữ ổ ng pháp Graph và algorit hoá đ nghiên D ng đã nghiên c u đ tài: “Áp d ng ph ể ụ ứ ươ ng pháp gi c u c u trúc và ph ọ ở ệ ố ự ứ ấ ươ ng ph thông”. Năm 1984, Ph m T v is h ễ ng d n c a giáo s Nguy n tr ư ớ ự ướ ườ Ng c Quang đã nghiên c u đ tài: “Dùng Graph n i dung c a bài lên l p đ d y và ộ ề ứ ọ ng trung h c ph thông”. Năm 1987, Nguy n ng Nit - Phôtpho h c ch ễ l p 11 tr ọ ở ớ ọ ườ ể ng pháp Graph l p ch Chính Trung đã nghiên c u: “Dùng ph ươ ứ d y môn s ”. Trong d y h c sinh h c ng ph thông, Nguy n Phúc Ch nh là tr ạ ọ ở ườ ạ ng i đ u tiên đi sâu nghiên c u v lý thuy t Graph và ng d ng lý thuy t Graph ế ườ ầ ng pháp Graph trong d y h c Gi ạ trong d y h c ttoán cácchuyên gia Hoàng Chúng và Vũ Đình Hoà đã có m t s đ nh ộ ố ị ạ h ướ ư ế ộ
ng nh ng ch a có h c viên cao h c nào nghiên c u m t cách chi ti ọ ệ ậ ư ớ ả ạ ứ ề ượ ố
ộ
ữ ơ ả ả
ữ ng g p trong h c t p hay đ i s ng hàng ngày đ t ể ừ ậ ụ ờ ố ườ ặ
ơ ả
t. ọ ạ m nh d n c ti p c n chuyên sâu v Graph, nhóm tác gi V i mong mu n đ ệ làm bài thu ho ch “Lý thuy t đ th Graph”. N i dung bài vi t là nh ng kinh nghi m ế ế ồ ị ạ đã h c h i đ c, bám sát vào nh ng d ng c b n mà h c sinh mà nhóm tác gi ọ ọ ạ ỏ ượ ế ồ ị đó v n d ng lí thuy t đ th th ọ ậ c hai m c tiêu: và giúp ta đ t đ ụ ạ ượ i đ - Gi c m t l p bài t p ộ ớ ậ ả ượ - H tr cho vi c l p trình ệ ậ ỗ ợ Trong bài thu ho ch, tác gi ạ ữ ộ ố ế ợ ệ ố ự ả ớ
ậ
Trang 1
ư
GVBM: D Quang Anh Huy
ả ư ề ồ ị theo nh ng hình nh minh h a sinh đ ng k t h p v i xây d ng h th ng ph ộ ọ pháp phân tích, trình bày cách gi ả ố ớ đ đ c đ c p. Bên c nh đó chúng tôi còn cung c p đáp án và h ề ượ đ a ra m t s khái ni m c b n v đ th kèm ệ ng ươ ấ i đ i v i các bài t p, ví d c th d a theo các v n ả ơ i s ụ ụ ể ự ướ ng d n gi ẫ ề ậ ấ ạ
Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ứ
ụ
ề
ế
ườ
ng THPT Th t N t ố ố
ậ ể ằ ộ ể có th thông hi u, v n d ng, ki m ậ ụ ể ể
ộ ố ứ ế ệ
l c m t s bài t p tiêu bi u nh m giúp đ c gi ả ượ tra ki n th c và rèn luy n kĩ năng phân tích đ th . ồ ị ế ồ ị ẽ ạ ả ộ
Mong r ng v i bài thu ho ch “Lý thuy t đ th Graph” s giúp đ c gi ộ có cái ọ t khái quát, sâu và r ng h n v d ng Toán vô cùng quan tr ng ề ạ ằ ể ơ
ớ nhìn và t m hi u bi ế ầ này.
Nhân đây, nhóm tác gi c bày t ả ả ơ ỏ
ượ ng THPT Th t N t, TP C n Th ) đã nhi ư t tình ố xin đ ườ lòng c m n sâu s c t ố i th y D ầ ệ
Quang Anh Huy (giáo viên toán tr giúp đ , ch d n chúng tôi trong quá trình biên so n bài thu h ắ ớ ơ ầ ch này. ạ ọạ ỉ ẫ
ế ạ
ế c biên so n khá kĩ và công phu nh ng vi c thi u sót là ư thông c m! Xin chân ộ ạ ơ ấ ấ ệ ả ả ỡ Tuy bài thu ho ch đ ượ ề
Trang 2
ư
GVBM: D Quang Anh Huy
khó tránh kh i. N u có đi u chi s su t r t mong quí đ c gi ỏ thành c m n! ả ơ
Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ứ
ụ
ề
ế
ườ
ng THPT Th t N t ố ố
Đ TH TRONG Đ I S NG
Ờ Ố
Ồ Ị
ả ả ề ể ấ
ờ ố ạ ủ i quy t nhi u v n đ mà ta có th coi m t ộ ế ề ề c coi là đ nh c a c nh. Đ làm rõ đi u ủ ạ ượ ể ỉ
Trong đ i s ng, chúng ta ph i gi ng cong là c nh và đ u mút c a chúng đ đ ầ ườ này, chúng ta có th xem xét nh ng ví d sau đây. ữ ụ ể
ng đi b t nhà đ n tr ng t ườ ộ ừ ế ườ ố ư ấ i u nh t ộ ị
ể ắ
Ví d 1: ụ Hãy xác đ nh m t con đ (hi u theo nghĩa kho ng cách ng n nh t). ả ế ấ ạ ả
ố ả ườ
ả i đ dài c a các con đ ủ ớ ộ ườ ề ắ ấ ộ
ng ng n nh t. Trong v n đ tìm đ ầ ạ ấ
ộ ộ i quy t bài toán này b n ph i quan sát trên b n đ , b qua đ r ng - Khi gi ồ ỏ ng ph và ch còn chú ý t h p c a các đ ng cũng nh các ư ườ ỉ ẹ ủ ườ đ u mút giao thông đ phát hi n m t con đ ng ấ ệ ể ầ đi ng n nh t này chúng ta đã coi các ph là các c nh và các đ u mút giao thông (các ngã t ắ ư ẳ ạ ỉ
ủ ờ ố ủ ả ả ấ
ố ạ ả i quy t khác c a đ i s ng , đôi lúc ta còn ph i ề đ dài c a các c nh c a h th ng c nh, và các đ nh trong mô hình, ch ng h n) là các đ nh c a các c nh. - Trong nhi u v n đ ph i gi ế ạ ủ ệ ố ề ủ ạ ỉ
b qua các y u t ỏ ế ố ộ nh ví d sau ch rõ. ỉ ụ ư
ẽ ơ ồ ạ ủ ộ ộ
ồ ả ố
trên, rõ ràng ta s b qua y u t
ề ế ớ
Ví d 2: ụ Hãy v s đ m ng giao thông công c ng c a m t thành ph . ố - Trong hình trên là b n đ giao thông công c ng thành ph Wien (th đô n ẽ ỏ ở ng đi nh th nào, t đ ế ố ườ ư ế ỉ ạ ề ướ c ủ ng mà đ dài các tuy n đ ế ườ ấ bên nào t i bên nào. Trong v n ng đi qua chúng ho c xu t phát ấ ặ c nh và đ nh ế ố ạ ộ ế ố ộ ừ ế ườ ễ ế ệ ỉ
Áo). Trong v n đ nêu ấ ch còn quan tâm đ n y u t ỉ đ này, các b n là các đ nh còn c nh là các tuy n đ ề ế các b n. Nh ng nhi u khi chúng ta không d phát hi n các y u t t ư ừ i quy t. trong bài toán chúng ta ph i gi ế ả ả
i trong cùng Ví d 3: ụ Hãy phân nhóm h c t p trong l p sao cho nh ng ng ọ ậ ữ ớ ườ
ộ
- Ở ườ ư ể ẵ ậ ấ
ủ đây không còn nh ng đ ơ ồ ầ ậ đ nh trong s đ c n l p là nh ng em h c sinh trong l p. ỉ ớ ng đi cho s n. Nh ng ta có th nh n th y các ọ
ọ ố ố
c). m t nhóm là b n thân c a nhau. ạ ữ ữ ễ ạ ẳ ẫ ươ ạ ộ
ộ ơ ồ ồ ẳ ọ ỉ
ộ ẽ ỉ ủ ớ
ố ụ ớ
ọ ề ữ ố ỉ ỉ
- Trong s đ bi u di n, ta n i nh ng c p hai em h c sinh v n v n là b n ạ ơ ồ ể ặ ữ i b ng m t đo n th ng (ho c b ng m t đo n th ng cũng đ than c a nhau l ủ ặ ằ ạ ằ ạ - B ng cách đó ta s có m t s đ g m các đ nh (các em h c sinh) và các c nh ằ ng n i hai em ch khi hai em này là b n thân c a nhau trong l p). Trong hình ườ ạ ộ ồ ị - Nh ng mô hình quy v các t p đ nh và các c nh n i các đ nh là nh ng đ th . ng xuyên t trong khoa h c chúng ta cũng th ữ ườ ờ ố ạ ọ ặ
Trang 3
ư
GVBM: D Quang Anh Huy
(các đ 7 là m t ví d v i n= 10 em h c sinh. ậ Không ch trong đ i s ng mà đ c bi ệ ỉ g p nh ng đ th . ồ ị ặ ữ
Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ứ
ụ
ề
ế
ườ
ng THPT Th t N t ố ố
thành ph Konigsberg năm 1736. ầ ở ủ ữ ặ
ệ ố ầ
ộ ư ể ế
ể ẽ ồ ị ươ ờ
ằ i dân thành ph Konigsberg đ t ra t ố
c Euler gi ế ồ ị ượ ườ ọ ẹ
Ví d 4: ụ 7 cây c u ố i dân c a thành ph Konigsberg đ t câu h i: - Trong ví d này, nh ng ng ỏ ườ ụ ộ ầ li u có th đi m t vòng qua 7 cây c u sao cho m i cây c u ch đi qua đúng m t l n ỉ ỗ ầ mà thôi? N u nh coi m i cây c u là m t c nh c a đ th , v i đ nh là các hòn đ o và ủ ồ ị ớ ỉ ầ ả ộ ạ ỗ ng ng b ng m t nét bút c đ t ra là có th v đ th t hai b sông, thì bài toán đ ượ ặ ứ ộ nh ng năm c ng hay không? Bài toán này đ ữ ừ ặ ượ 1736, và đ ủ c mang tên c a i quy t tr n v n trong lí thuy t đ th đ ế ả ượ ông.
- Sau đây là l i gi i c a Euler: ờ ả ủ
ế ể ằ ậ
ấ
ạ ừ ỉ ặ
ạ ỏ ấ ả ấ ằ ạ ọ ế ỗ ạ ọ ế ặ ấ ằ ố ọ
ữ ủ - Đ ch ng minh k t qu , Euler đã phát bi u bài toán b ng các thu t ng c a ể ứ ả ầ t c các chi ti lý thuy t đ th . t ngo i tr các vùng đ t và các cây c u, ế ồ ị Ông lo i b t ế sau đó thay th m i vùng đ t b ng m t đi m, g i là đ nh ho c nút, và thay m i cây ỗ ể ộ ượ ượ c c đ c u b ng m t đo n n i, g i là c nh ho c liên k t. C u trúc toán h c thu đ ầ ộ g i là m t đ th . ộ ồ ị ọ
ủ ể
ể ị ữ ư ộ ữ ế ệ ế ẳ
Trang 4
ư
GVBM: D Quang Anh Huy
bên ph i hay bên trái m t nút khác là không quan tr ng. ủ ồ ị b thay đ i, mi n là các liên k t gi a các nút gi ị cong, m t nút ả ồ ị - Hình thù c a đ th có th b bóp méo theo đ ki u nh ng không làm đ th nguyên. Vi c m t liên k t th ng hay ọ ổ ộ ễ ở ộ
Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ứ
ụ
ề
ế
ườ
ng THPT Th t N t ố ố
c gi ằ ậ ủ ể ượ
ố ạ ậ ộ
ộ ằ ố ớ ậ
ộ . M t đ ố ỉ ồ ạ ộ ườ ỉ
ọ ằ ậ ẻ ầ ộ
- Euler nh n ra r ng bài toán có th đ i b ng cách s d ng b c c a các ử ụ ả ằ nút. B c c a m t nút là s c nh n i v i nó; trong đ th các cây c u Konigsberg, ba ậ ủ ồ ị ầ nút có b c b ng 3 và m t nút có b c 5. Euler đã ch ng minh r ng m t chu trình có ậ ứ ng đi d ng nh mong mu n ch t n t i khi và ch khi không có nút b c l ư ạ nh v y đ ố c g i là m t chu trình Euler. Do đ th các cây c u Königsberg có b n ồ ị ư ậ nút b c l ậ ẻ
ng đi qua t ộ ườ ấ ả
ể ử ầ ể ể ổ ể ườ
. (Nh v y đi u này cũng không th đ i v i b y cây c u ầ t c các cây c u ư ậ ượ ọ c g i i khi và ch khi đ th có đúng ầ ở ả ư ậ ể ố ỉ ớ ẻ
ượ , nên nó không th có chu trình Euler. ể - Có th s a đ i bài toán đ yêu c u m t đ ầ nh ng không c n có đi m đ u và đi m cu i trùng nhau. Đ ng đi nh v y đ ố ầ ư ng đi nh v y t n t ng đi Euler. M t đ là m t đ ộ ườ ồ ị ư ậ ồ ạ ộ ườ hai đ nh b c l ề ậ ỉ Konigsberg.)
KHÁI NI M C B N V Đ TH Ề Ồ Ị Ơ Ả
Ệ
Hình 1
- Trong các ví d k trên, các c nh c a đ th đ u là các đ ủ ườ
ặ ữ ạ ồ ị
ộ ề
ng không có ồ ị ề ữ ng. Nh ng đôi khi ta g p nh ng ọ ướ ng ng ta bu c ph i xác đ nh m t h ng đi cho nó. ộ ướ ả là có ế ạ ế ố
ư ị i đi xe đ p thì ph i l u ý đ n y u t ả ư ườ c đánh d u b ng mũi tên nh trên hình 1). ằ ấ ế ộ ẳ ể
c xác đ nh b i hai t p h p, t p h p ượ ậ ợ ị
ạ ỉ ỉ
ệ t th t ng. N u có phân bi ư ợ X ( „ 0 ) ậ ở ủ X. Ta có A, B ợ E g m các c nh n i hai đ nh c a ồ ng h p này đ ợ ườ ặ ế ồ AB và BA s khác nhau thì ta có đ ố là AB ho c BA trong tr ứ ự ẽ
ồ ị ng. ụ ể h ng. Nh ng đ th nh v y g i là đ th vô h ư ậ ồ ị ướ v n đ mà khi xác l p đ th t ồ ị ươ ứ ậ ấ Ch ng h n trong ví d 1 ,n u b n là ng ạ ụ ạ ng m t chi u (đ th có nh ng con đ ượ ề ườ ữ s đ th G đ - Nh v y, gi ả ử ồ ị ư ậ }DCBA { , , , và t p h p g m các đ nh ồ ậ ồ là hai đ nh trong X c nh n i AB, n u kí hi ố ạ ỉ th G là đ th vô h ệ ế ướ th có h ướ
Trang 5
ư
GVBM: D Quang Anh Huy
ị ị A B D C
Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ứ
ụ
ề
ế
ườ
ng THPT Th t N t ố ố
- Khi bi u di n đ th có h ướ ẫ
ố ớ ướ
ư ể ng thì nguyên t c cũng v n gi ng nh bi u ng ta đánh ạ ễ ồ ị ể di n đ th c nh không có h ễ ồ ị ạ d u mũi tên theo chi u c nh đ bi u th h ấ ố ắ Riêng đ i v i nh ng c nh có h ướ ữ ng đi c a nó. ủ ng. ể ể ề ạ ị ướ
- Trong đ th trên có h ồ ị ướ ớ ỉ
ữ ạ ỉ ng v i 4 đ nh. Đi m chung nhau c a t ể ữ ụ ủ ấ ả . Nh ng đ th ch có h u h n đ nh ỉ t c các ví d ữ ạ ỉ ồ ị
mà chúng ta xem xét là chúng có h u h n đ nh nh v y đ c g i là đ th h u h n. ư ậ ượ ọ ồ ị ữ ạ
Hình 3
- Cũng có tình hu ng là m t đ nh đ ộ ỉ ở ạ
ố Trong hình 3 là m t đ th có c nh kép bên trái và khuyên c n i v i chính nó b i môt c nh nào ở ượ ố ớ ộ ồ ị ạ
đó mà ta g i là khuyên. ọ gi a. ữ
- V i đ c đi m này đ th h u h n đ c chia thành 2 lo i c b n là ồ ị ữ ớ ặ ể ạ ượ ạ ơ ả đ thồ ị
không có khuyên và gi a hai đ nh c a nó có không quá ữ ủ ỉ đ nơ và đ thồ ị kép. + Đ th đ n thì ồ ị ơ
m t c nh n i chúng. ộ ạ
i hai đ nh nào đó mà gi a chúng ặ ặ ồ ạ ữ ỉ
ố ồ ị có ít nh t hai c nh n i. ạ ố
ứ ề ỉ
ng). Chính xác v m t toán h c đ th đ c đ nh nghĩa nh +Đ th kép thì ho c có khuyên ho c t n t ấ - Trong chuy n đ này ta ch xét và nghiên c u đ th h u h n ( t c là X và E ư ứ ồ ị ữ ạ ồ ị ượ ệ ướ ề ặ ọ ị
là h u h n và vô h ạ ữ sau :
Đ nh nghĩa ị : M t b G = (X, E) g m hai t p h p X và E đ ồ ộ ộ ậ ợ ượ ộ c g i là m t ọ
đ th h u h n n u ồ ị ữ ạ ế
˛ N X và n ˛ sao ộ ặ
ng) ho c e = {x,y,n} (c nh vô h x, y ng) i m t c p hai ph n t ạ ầ ử ướ E t n t ồ ạ ặ
1) X và E là 2 t p h u h n 2) Cho m i ph n t ỗ cho e = (x,y,n) (c nh có h ạ - S ố n bi u di n c nh ể ố ạ
Trang 6
ư
GVBM: D Quang Anh Huy
cùng m t đ nh.Trong tr ậ ữ ạ ầ ử ˛ e ướ ễ ạ ho c các khuyên xu t phát t ừ ặ ấ e = (x,y,n) ho c ặ e = {x,y,n} dùng đ đánh s c nh kép ạ ng h p đ th không có c nh ể ồ ị ộ ỉ ườ ợ
Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ứ
ụ
ế
ề
ườ
ng THPT Th t N t ố ố
t c nh ế ạ (x,y.n) ho c ặ {x,y.n} ta có th vi ể ế ơ t đ n gi n c nh ả ạ (x,y) ho cặ
kép thì thay vì vi {x,y}
ế ế
ượ ọ ng h p t t c các c nh c a ạ c g i là song song n u chúng cùng liên k t m t c p đ nh. ợ ấ ả ề ạ cượ
g i là ọ
ủ G đ u là c nh vô h ộ ố ồ ị ơ c g i là ủ G thì x,y đ
ng thì đ nh ỉ ề ướ ạ
ạ t c ạ ng . G đ ướ
- Hai c nh đ ỉ ộ ặ ạ ng thì G đ - Trong tr ướ ườ ng 4 đ nh đ thồ ị vô h ngướ (h.4). Trong hình 4 ta có m t s đ th đ n vô h ỉ ướ - N u ế e = {x,y,n} là c nh c a c a ủ c nh e ượ ọ ạ ợ ấ ả các c nh c a đ th G đ u là c nh có h ng h p t - Trong tr ủ ồ ị ườ c g i là đ th có h ồ ị ượ ọ
còn y - N u ế e = (x,y,n) là m t c nh c a ộ ạ ượ c g i là ọ đ nh xu t phát ấ ỉ Hình 4 ủ G thì x đ
đ c g i là ượ ọ ủ . đ nh k t thúc c a e ỉ ế
Hình 5
X v i các đ nh ồ ị G = (X,E) có t p đ nh ậ ớ ỉ ỉ
a,b,c,d và t pậ {a,b}, {b,d,1}, {b,d,2}, {b,c,1}, {b.c.2}, {b,e}, {e,e,1}, {e,e,2}, - Trong hình 5 có đ th ạ ớ
ủ ỉ
ỉ c tính hai l n) và đ c nh e v i các c nh ạ {e,e,3}, {e,e,4} và {e,e,5} * Chú ý ậ ủ (v i qui ướ ớ ộ ỉ ượ s là đ nh A) là t ng s các c nh c a đ nh đó ố ổ ạ ả ử deg(A) c kí hi u là: ệ ầ ượ
0A1, A1A2, ...., An-1An đ
(cid:204) c g i là con c a đ th G n u X’ X và E’ (cid:204) E. : B c c a m t đ nh (gi c m i khuyên đ ỗ 1. Đ th con ồ ị - Cho 2 đ th G (X, E) và G’(X’ ồ ị - Đ th G’ đ ượ ọ ồ ị , E’) ủ ồ ị ế
ượ ọ ế ạ
ộ ườ ế ầ ố ỉ
m t đ ỉ An và ch a các c nh A0A1, A1A2, An-1An
2. Đ ng đi ườ -Trong đ th G xét m t dãy c nh liên ti p: A c g i là ồ ị ộ đ nh A0 (đ nh đ u) đ n đ nh An(đ nh cu i) qua các đ nh A0, A1,…, ỉ ỉ ừ ỉ ạ
Trang 7
ư
GVBM: D Quang Anh Huy
ng đi t ứ
Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ứ
ụ
ề
ế
ườ
ng THPT Th t N t ố ố
i là: A t g n l ế ọ ạ ấ 0A1A2…An hay A0-An (n u mu n nh n ế ố
ỉ ạ ườ ầ
ổ ỉ
ộ ồ ị i, Ai+1), i= 0,…, k- 1 v i Aớ 0= A, Ak= B. S các c nh ( ng đi t ạ A ừ ở ộ
ng đi g i là đ dài c a đ
ng đi đ n n u nó không qua c nh nào l n th ườ ng đi đ c vi - Đ ng đi này đ ượ m nh đ nh đ u và đ nh cu i). ố ỉ Cho A, B là hai đ nh c a m t đ th G. M t đ - T ng quát ta có: ộ ườ ủ đ n B là m t dãy các c nh (A ố ạ ế đây là k) t o nên đ ọ ạ ộ c g i là đ - M t đ ượ ọ ộ ườ ủ ườ ơ ng đi. ế ườ ứ ầ ạ
hai.
- M t đ ng đi đ c g i là đ ộ ườ ượ ọ ườ ầ ng đi s c p n u nó không đi qua đ nh nào l n ơ ấ ế ỉ
th hai. ứ
*Chú ý: n u đ i thì ườ ng đi là s c p đ n đ ơ ấ ế ườ ng đi đ n nh ng đi u ng ư ề ơ c l ượ ạ
ế không ch c đúng. ắ
ộ ườ ng đi khép kín ( đ nh đ u trùng đình ỉ ầ
ộ ố
- Chu trình đ n: là m t chu trình không qua c nh nào l n th hai đ
3. Chu trình: m t chu trình là m t đ ộ cu i) và có đ dài l n h n ho c b ng 3. ớ ơ ơ
ặ ằ ộ ứ ạ ầ ượ c g i là ọ
chu trình đ n.ơ
ừ ỉ ứ ầ ầ ộ ố ỉ ỉ
nhau g i là m t chu trình s c p. - M t chu trình không qua đ nh nào l n th hai tr đ nh đ u và đ nh cu i trùng ọ ơ ấ ộ
Ví d : ụ
ườ ng đi s c p đ dài b ng 3. ộ ơ ấ ằ
ườ ơ ườ ằ ộ
ằ
+ Đ ng đi ABDE là đ + ABCDE là đ ng đi đ n không s c p, đ dài b ng 5. ơ ấ + DBCDB không đ n, có đ dài b ng 4. ộ ơ + CDABC là m t chu trình đ n s c p, đ dài b ng 4. ơ ơ ấ ằ ộ ộ
c g i là hai đ nh liên ủ ộ ồ ị ượ ọ ỉ
thông n u trong đ th có m t đ
c g i là liên thông n u m i c p đ nh c a nó đ u liên thông ế ủ ề
hay v i hai đ nh b t kỳ, ta luôn có m t đ
4. Tính liên thông: hai đ nh A, B c a m t đ th đ ỉ ng đi A-B. ộ ườ ế ồ ị - M t đ th đ ọ ỉ
ọ ặ ỉ ng đi gi a chúng. ữ ộ ườ ớ
- M t đ th không liên thông là h p c a hai hay nhi u đ th con liên thông, ợ ủ ồ ị ề
m i c p các đ th con này không có đ nh chung. ỗ ặ ỉ
c g i là các thành ph n liên ư ậ ờ ượ ọ ầ ộ ồ ị ượ ấ ộ ồ ị ồ ị ồ ị
Trang 8
ư
GVBM: D Quang Anh Huy
- Các đ th con liên thông r i nhau nh v y đ ủ ồ ị thông c a đ th đang xét. ộ ồ ị ậ V y m t đ th liên thông khi và ch khi nó có m t thành ph n liên thông. ỉ ầ ộ
Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ụ
ứ
ề
ế
ườ
ng THPT Th t N t ố ố
ng G đ ượ ệ t ớ ỉ
u đ n v và t ườ liên thông m nhạ n u v i hai đ nh phân bi ế ừ
ng G đ ướ ề ướ ướ
ế v đ n u. ế liên thông y uế n u đ th vô h ế ữ ồ ị ỉ
ng đi: s t n t c g i là ọ ng đi t ừ c g i là ượ ọ ằ i đ ự ồ ạ ượ ả ộ ả ở
t gi a hai đ nh thì b ng cách i v i nhau ta đ ng đi phân bi ề ủ ng n n c a i duy ồ ạ c b o đ m b i tính liên thông, m t khác, n u t n ế ồ ượ c n iố chúng l ỉ ấ ặ ạ ớ ữ ệ ằ
- Đ th có h ồ ị b t kì u và v c a G đ u có đ ủ ấ - Đ th có h ồ ị nó là đ th liên thông. Chú ý r ng trong m t cây, gi a hai đ nh b t kỳ t n t ồ ị nh t m t đ ộ ườ ấ i hai đ t ườ ạ m t chu trình. ộ
Ví d :ụ
Đ th liên thông Đ th không liên thông ồ ị ồ ị
M T S Đ TH Đ C BI T
Ộ Ố Ồ Ị Ặ
Ệ
4 1-đ u K 2
- Đ th đ u là đ th mà m i đ nh đ u cùng b c. - N u k là b c c a đ nh thì ta g i là đ th K-đ u. ồ ị ậ ủ ỉ ồ ị ề ế ề ồ ị ọ ỉ ọ ậ ề
3 3-đ u, Kề
2-đ u, Kề ề
ố
- Đ th đ y đ là đ th mà m i c p đ nh đ u có c nh n i chúng. ọ ặ - Đ th không đ y đ c a p đ nh đ ỉ ề ỉ ạ c kí hi u là Kp. ệ ồ ị ầ ủ ồ ị ượ
- Kp có p đ nh và ỉ c nh.ạ ồ ị ầ ủ ủ -pp ( )1 2
)1
Ví d :ụ K8 có 28 c nh.ạ K7 có 21 c nh.ạ
-pp ( 2
Kp là m t đ th (p-1) -đ u và có ộ ồ ị ề c nh.ạ
Trang 9
ư
GVBM: D Quang Anh Huy
Ví d :ụ K5 => 4-đ u, 10 c nh. ề K6 => 5-đ u, 15 c nh. ề ạ ạ
Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ụ
ứ
ề
ế
ườ
ng THPT Th t N t ố ố
Đ
NG ĐI EULER VÀ Đ TH HAMILTON
ƯỜ
Ồ Ị
1.Đ ng đi Euler - Đ ng đi Euler là m t đ
ng đi s c p A-B qua t t c các c nh c a đ th ộ ườ ơ ấ ấ ả ủ ồ ị ạ
ườ ườ ch m t l n. ỉ ộ ầ
c g i là m t đ th Euler. ng đi Euler đ ộ ườ ộ ồ ị ượ ọ
ị
- Chu trình Euler là m t đ * Đ nh lí Euler : - Cho đ th G[ X, E] ồ ị - G là đ th Euler khi và ch khi G liên thông và deg (x) là s ch n, ồ ị ỉ ố ẵ " x˛ X.
ng đi s c p A-B qua t
2.Đ th Hamilton: - Đ ng đi Hamilton là m t đ
ộ ườ ơ ấ ấ ả t c các đ nh c a đ ỉ ủ ồ
th ch m t l n. ị
ộ
c g i là đ th Hamilton. ồ ị ượ ọ
ư ệ
- N u A trùng B thì ta có m t chu trình Hamilton . - M t đ th có ít nh t m t chu trình Hamilton đ ộ ấ - Không gi ng nh đ th Euler hi n nay ch a có quy t c c n và đ đ ki m ủ ể ể ư ồ ị ỉ c hi n nay ch ệ ả ượ ế
ắ ầ tra xem m t đ th có ph i là Hamilton hay không. Các k t qu có đ ả là đi u ki n đ đ m t đ th là Hamilton. ề
ồ ị ườ ỉ ộ ầ ế ộ ồ ị ố ộ ồ ị ệ ủ ể ộ ồ ị ộ ồ ị ầ ủ
1-n 2
+ M t đ th đ y đ là đ th Hamilton. ồ ị ẻ ‡ 3 thì Kn s có , n + V i n l ớ ẽ ạ chu trình Hamilton đôi m t không có c nh ộ
chung.
x
X
‡ 3. N u deg (x)
n 2
˛ " ‡ + Gi s G là đ th đ n g m n đ nh, n thì G là ả ử ồ ị ơ ồ ỉ ế
m t đ th Hamilton. ộ ồ ị
CÁC M NH Đ M R NG VÀ T LI U THAM KH O
Ề Ở Ộ
Ư Ệ
Ả
Ệ
ấ ơ ả ề
ượ ọ ộ
ng liên thông không có chu trình đ ng không ch a chu trình đ ượ ọ ứ ướ ướ c g i là m t cây. ộ c g i là m t r ng. Trong m t ộ ừ
*T li u tham kh o ả ư ệ 1. Đ nh nghĩa và các tính ch t c b n v cây ị - M t đ th vô h ộ ồ ị - M t đ th vô h ộ ồ ị ỗ
A
r ng, m i thành viên liên thông là m t cây. ừ ộ
D
B
E
C
Trang 10
ư
GVBM: D Quang Anh Huy
Ví d :ụ R ng có 3 cây ừ
Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ứ
ụ
ề
ế
ườ
ng THPT Th t N t ố ố
ạ ỏ ạ ế ằ
s đ ẽ ượ ồ ị ẫ
2. Cây khung - Trong đ th liên thông G, n u ta lo i b c nh n m trên chu trình nào đó thì ta ồ ị c đ th v n liên thông. - Cây khung c a đ th G là cây n i các đ nh c a đ th không còn chu trình ủ ồ ị
ồ ị ủ ố ỉ
nh ng v n liên thông. ư ẫ
A
D
C
B
Ví d :ụ Cho đ th G: ồ ị
D
A
C
B
Ta có cây khung sau:
ế ồ ị ầ ỉ
ụ ủ ầ ỗ
*T ng quát ổ áp d ng th t c v a mô t ủ ụ ừ th đ ị ượ ọ ừ
: n u G là đ th có n đ nh, m c nh và k thành ph n liên thông thì ạ đ i v i m i thành ph n liên thông c a G, ta thu đ ượ ồ c đ ả ố ớ c g i là r ng khung c a G. ủ 3. Cây có g cố - Cây có g c là m t cây có h t g i là g c, t ố ừ ệ ọ ặ ố ộ ỉ
ng đi đ n m i đ nh khác c a cây. ng, trong đó có m t đ nh đ c bi ướ ủ g c có đ ố ườ ế
- Trong cây có g c thì g c R có b c b ng 0, còn t ố ậ ằ ấ ả ậ t c các đ nh khác có b c ỉ ộ ọ ỉ ố
b ng 1. ằ
- M t cây có g c th ng đ trên cùng và cây phát tri n t ố ườ ượ c v v i g c r ẽ ớ ố ở ể ừ
1
ộ trên xu ng.ố
2
4
3
6
7
8
5
9
Trang 11
ư
GVBM: D Quang Anh Huy
Ví d : ụ
Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ứ
ụ
ề
ế
ườ
ng THPT Th t N t ố ố
ượ ọ
phía d c g i là đ nh m c 1. Đ nh d c g i là đ nh m c 0. + G c r đ ứ ố ỉ + Các đ nh k v i r và x p ế ở ề ớ ỉ i đ ướ ượ ứ ọ ỉ ỉ ướ i
ứ m c 1 là đ nh m c 2 ỉ
- Trong m t cây có g c thì v là đ nh m c k khi và ch khi đ ng đi t ứ ố ỉ ỉ ưở ừ r đ n v ế
ứ ộ có đ dài b ng k. ộ
- M c l n nh t c a m t đ nh b t kì trong cây đ ộ ỉ ấ ủ ấ ượ ọ c g i là chi u cao cây. ề ằ ứ ớ
Đ TH PH NG VÀ TÔ MÀU Đ TH Ồ Ị
Ồ Ị
Ẳ
ớ ệ ể ể
ư ố
ấ
ấ ể ặ ệ ấ ạ ộ
ườ ự
ẩ ng đi không giao nhau ngoài các đ nh c c biên hay không? T đó, đ ỉ ị ộ ớ
L 1
L 3
Đ
L 2 1 1 1 1 1 N
R
ở ầ “ba Đ đi sâu vào hai khái ni m m i này ta hãy tìm hi u qua bài toán m đ u làng ba và nhà máy” nh sau: Ta có ba làng L1, L2, L3 mu n đ t đ ng n i v i ba ố ớ ặ ườ c N và nhà máy nhà máy: m t nhà máy cung c p đi n Đ, m t nhà máy cung c p n ộ ướ ộ cung c p th c ph m rau s ch R. V n đ đ t ra là ta có th đ t trên m t m t ph ng ẳ ặ ề ặ ự ấ ồ sao cho các đ ừ ễ “ba làng và ba nhà máy” cho phép đ nh nghĩa m t l p các đ th g i là th bi u di n ồ ị ọ ị ể l p đ th ớ ồ ị không ph ng.ẳ
ộ ọ ẳ ặ
1. Đ th ph ng: ẳ ồ ị - M t đ th đ ộ ồ ị ượ ạ
ể ẽ ượ ả ủ
ẳ ẽ ư ế ượ ọ
ẳ ể ắ ể c g i là m t bi u di n ph ng c a đ th . ủ ồ ị ễ ắ c v v i nh ng c nh c t ữ ẽ ớ ọ ả ạ
- M t đ th đ ể ẽ c g i là ph ng ngay c khi nó đ ượ ắ ạ
- Cho G là m t đ th ph ng. M i ph n m t ph ng gi ẳ c trên m t m t ph ng c g i là ph ng n u nó có th v đ ế 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 đ ể ộ ạ ộ ồ ị ượ ằ ộ ồ ị nhau vì có th v nó b ng cách khác không có các c nh c t nhau. ẳ ầ ẳ ở ỗ
ồ ị ề ạ ộ
ỗ ồ ị ủ ề ề
ữ ề ạ ấ
t c các mi n h u h n). S ấ ả ợ ặ ẳ “đai” c a G. Tr ủ ườ ế
Trang 12
ư
GVBM: D Quang Anh Huy
i h n b i m t chu trình ặ ộ ớ ạ đ n không ch a bên trong m t chu trình khác g i là mi n (h u h n) c a đ th G. ủ ữ ọ ứ ơ i h n mi n g i là biên c a mi n. M i đ th ph ng liên thông có m t Chu trình gi ộ ẳ ọ ớ ạ ố mi n vô h n duy nh t (là ph n m t ph ng bên ngoài t ầ ạ ề ng h p n u G không có chu trình c nh ít nh t t o thành biên g i là ọ ấ ạ ạ thì đai chính là s c nh c a G. ố ạ ủ
Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ứ
ụ
ề
ế
ườ
ng THPT Th t N t ố ố
A
B
Ví d : ụ
D
M1 M4
E
C
F
M2 M3
N u m t đò th ph ng liên thông có n đ nh, p c nh và d mi n thì ta 4 mi nề (M1, M2, M3, M4) và có đai là 8 ỉ ẳ ị ề ạ
Đ th trên có ồ ị Đ nh lí: ế ị có h th c: ộ ệ ứ n – p + d = 2.
c g i là “h th c Euler cho hình đa di n”. M i hình H th c: ệ ứ ệ ỗ
ệ ứ n – p + d = 2 đ ượ ọ đa di n có th coi là m t đ th ph ng. ệ
ể H qu : ệ ả Trong m t đ th ph ng liên thông tùy ý , luôn t n t ẳ ồ ạ ộ i ít nh t m t ấ ộ ồ ị ẳ ộ ồ ị
t quá 5. đ nh có b c không v ậ ỉ ượ
2. Tô màu đ thồ ị Bài toán m đ u
c đ t ra xu t phát t bài toán tô màu b n đ ở ầ : Bài toán đ ượ ặ ấ ừ ả ồ
nh sau: ư
ồ ỗ ả ộ ồ ị ề ẳ
ọ ề ề
ỉ ng đ ộ ả ể ề ề ề ề
c tô màu khác nhau). Và bài toán đ t ra là: xác đ nh s màu t - Ta coi m i b n đ là m t đ th ph ng và hai mi n có chung nhau m t ộ ng biên g i là hai mi n k nhau (hai mi n ch có chung nhau m t đi m biên g i ọ ộ ề c tô màu mà hai mi n k nhau ồ ườ ể i thi u c n đ tô ầ ặ ượ ị ể ố
đ ườ là hai mi n không k nhau). M t b n đ th đ ượ ố m t b n đ sao cho hai mi n k nhau thì có màu khác nhau). ề ề ộ ả ồ
Hình 6
ồ ặ ẳ
ể ễ ế ằ ỉ
B A C E ể ề ộ ồ ị ằ ộ ỉ ố ạ D F ậ ượ ằ G
c bi u di n b ng hai đ nh này là k nhau. Đ th nh n đ ề
Trang 13
ư
GVBM: D Quang Anh Huy
- M i b n đ trên m t m t ph ng có th bi u di n b ng m t đ th , trong đó ễ ộ ỗ ả c bi u di n b ng m t đ nh, các c nh n i hai đ nh n u các m i mi n c a b n đ đ ỗ ồ ượ ề ủ ả mi n đ c b ng cách này ễ ồ ị ằ ề ượ g i là đ th đ i ng u c a b n đ đang xét. ẫ ủ ả ọ ể ồ ị ố ỉ ồ
Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ứ
ụ
ề
ế
ườ
ng THPT Th t N t ố ố
ị ộ ơ ủ ỉ
Đ nh nghĩa: ề ệ ỗ ồ ị ề ể ề ỉ
Tô màu m t đ n đ th là vi c gán màu cho các đ nh c a nó sao ồ ị cho hai đ nh li n k có màu khác nhau. M i đ th có th có nhi u cách tô màu khác nhau.
c (G).
ể i thi u ố ố ủ ắ ố ộ ồ ị
ệ c n thi ầ
c (Kn) = n.
- S c màu hay s c s (Chromatic number) c a m t đ th G là s màu t ắ t đ tô màu G. Kí hi u là: ế ể 3. M t s đ nh lí: ộ ố ị - Đ nh lí 1 : M i đ n đ th đ y đ K ồ ị ầ ủ n đ u có ề
Ví d :ụ
đ u có s c s là ẻ ề
- Đ nh lí 2: - Đ nh lí 3: ị ở ị ị ế ể
ỉ
2 màu khi và ch khi nó ắ ố 3. M i chu trình đ dài l ộ c (G’). N u dùng k màu đ c (G) ‡ N u G’ là con c a đ th G thì ủ ồ ị i nh ng đ nh có b c nh h n k. tô màu G thì không c n quan tâm t ỏ ơ ậ ữ ớ M t đ n đ th G = (X, E) có th tô b ng ằ ể ồ ị ỉ ị
M i đ th ph ng đ u có ọ ồ ị ủ ề ẳ
ọ ơ c (K3) = 3 hình 6 có ọ ế ầ - Đ nh lí 4: ộ ơ không có chu trình đ dài l ẻ ộ - Đ nh lí 5 5 màu c a Kempe – Heawood): (Đ nh lí ị 5 màu. ể
- Đ nh lí 6 (Đ nh lí ị ị
4 màu hay đ nh lí Appel – Haken, 1976): ơ 4. Đ nh lí này là đ nh lí đ u tiên đ ượ M i đ thì ph ng ẳ ớ c ch ng minh v i ọ ồ ứ ầ ị ị
n (cid:0)
2
ị th tô đúng ị đ u có s c s không l n h n ớ ắ ố ề s h tr c a máy tính. ự ỗ ợ ủ
đ nh, có ít nh t hai đ nh có cùng ọ ồ ị ớ ấ ỉ ỉ
*M nh đ ề ệ 1. M nh đ 1. ề Trong m i đ th v i ệ
b c.ậ
: ứ
n= -
B
)
ậ ủ ơ
ượ ể ỉ
deg( ặ
ậ 1 đ ệ ằ ỉ
Ch ng minh Do đ th là đ n nên b c c a các đ nh n m trong t p {0,1,…, n-1. Tuy nhiên ồ ị ằ ỉ A = , deg( ) 0 c. Nói cách khác, b c không th có hai đ nh A, B sao cho ậ ế các đ nh n m trong {0, 1, …, n-2} ho c {1, 2, …n-1}. Nguy n lí Dirichlet giúp ta k t thúc ch ng minh. ứ
1
E
V(cid:0)
- ộ ồ ị ế
ệ
ề . Cho G= (V, E) là m t đ th liên thông. Th thì
ứ
n c a đ th . Tr ủ ồ ị ườ ạ ợ
ọ
ọ ồ ị ỉ ằ ạ
2.M nh đ 2 Ch ng minh: ng h p n= 1, 2 là Ta ch ng minh b ng quy n p theo s đ nh ố ỉ ứ ề s r ng m i đ th liên thông N đ nh đ u t m th ỉ ả ử ằ ườ ầ có ít nh t N- 1 c nh. G i G= (V, E) là m t đ th N+ 1 đ nh. L u ý r ng do G liên ư ộ ồ ị ấ thông nên b c c a m i đ nh ≥ 1
2(cid:0)
ằ ng. G i N là m t s nguyên và gi ộ ố ọ ỗ ỉ
N u b c c a m i đ nh c a G đ u ỗ ỉ ủ ề ế thì theo công th c quen thu c liên k t ứ ộ ậ ủ
=
ậ ủ ế các b c và s c nh, ta có ố ạ ậ (cid:0)
(
)
2
E
deg
A
2
n
A V
E n(cid:0)
(cid:0) (cid:0)
ư ậ
T đó suy ra ừ Gi ả ử c t o thành t s có m t đ nh c a ộ ỉ ằ
ọ G’ là ọ A là m t đ nh nh v y và g i ộ ấ ả G v i m t A và c nh duy nh t c ớ 1E - c nh. Áp ớ N đ nh và ạ ỉ
Trang 14
ư
GVBM: D Quang Anh Huy
G’ ta có đi u c n ch ng minh đ th đ ồ ị ượ ạ đ u mút ầ d ng gi ả ụ ủ G có b c 1. G i ộ ỉ ậ ừ G b ng cách lo i b đ nh ạ ạ ỏ ỉ A. D th y ễ ấ G’ cũng là m t đ th liên thông v i t quy n p cho thi ạ ộ ồ ị ề ầ ứ ế
Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ứ
ụ
ề
ế
ườ
ng THPT Th t N t ố ố
.
ọ ồ ị ể ượ ự ằ
ề M i đ th liên thông đ u có th đ
3. M nh đ 3. ệ ộ ố ạ
ớ ồ ị ộ ề ố ỉ c xây d ng b ng cách ư ộ
thêm vào m t s c nh vào m t cây có cùng s đ nh v i đ th đã cho, và m t cây nh v y đ ậ ượ ọ c g i là cây bao trùm c a đ th . ủ ồ ị
: ứ
Ch ng minh Ta quy n p theo s chu trình c c a đ th . N u c = 0, đ t ị ố
ứ ử ế ủ ồ ị ả ầ
ạ ả ộ ồ ị ừ
ỏ ế ứ ồ ị ả ộ ộ ạ ộ
ủ ề ằ
ủ ấ
ỉ ầ
t, có th xây d ng G’ t ủ A ừ ộ ộ ế ầ ự
Nh n xét. ậ ủ ừ ộ
ố ỉ V ể c G. ượ ố ạ i m t đ th G= (V,E), c n thêm vào ồ h là m t cây và ta ộ ả không có gì ph i ch ng minh. Già s k t qu c n ch ng minh là đúng v i c ≥ 0. Gi ớ s G là m t đ th có c + 1 chu trình. G i G’ là đ th c m sinh t ữ G b ng cách gi ằ ọ ử ạ ạ nguyên các đ nh và b đi đúng m t c nh thu c m t chu trình nào đó, ch ng h n c nh ẳ ỉ ộ (A1, A2) c a chu trình A 1, A2,..., Ak, A1. Chú ý r ng m i chu trình c a G’ đ u là m t ọ ủ chu trình c a G và do ta đã phá đi ít nh t m t chu trình c a G, s chu trình c a G’ vì ố ủ th ế £ c. Ngoài ra, G’ v n còn liên thông (n u c n đi t 1, 2 ch c n đi vòng A ừ 1 đ n Aế ẫ thi Ak,..., A3, A2). Theo gi ỉ ầ m t cây nào đó. Sau đó ch c n ế ả 1, A2 đ thu đ thêm vào G’ c nh Aạ ể t r ng s c nh c a m t cây b ng s đ nh tr đi 1. Nh v y, ư ậ Ta bi ằ ế ằ + - 1E c nh vào m t cây bao ộ ồ ị ầ ạ ạ ộ ự
đ xây d ng l ể trùm G.
Môt đô thi la hai phân khi va chi khi không co chu
4. Mênh đê 4 (Koenig).
̣ ̀ ̣ ̀ ̀ ̀ ̉ ́ ̣ ̀
trinh đô dai le. ̀ ̣ ̀ ̉
Ch ng minh : ứ
- (a) Gia s G ̉ ử ̀ . la ̀ môt đô thi hai phân ̣ ̀ ̣
̃ ̀ ̣ ̀ ̃ ́ ̉ ̉ ̣ ̣ ̉ ̣ ̣ ̣ ́
̀ ́ ̉ ́ ̉ ̣ ̉ ̀ ̣ ́ ̃ ̀ ́ ́
+ Ro rang môt chu trinh se đi qua cac đinh cua môt tâp đinh đôc lâp môt cach luân phiên va do đo chi co thê quay lai đinh đâu tiên sau môt sô chăn lân. Noi cach ̉ G phai co đô dai chăn. khac, moi chu trinh (nêu co) cua ́ ̣ ̀ ́ ́ ̉ ́ ̣ ̀ ̃
̉ ử ́ ̀ ̣ ̀
ự ̃ ̣ ̉ ̣ ̀ ́ ̀ ̀ ̉
ừ ́ ̃ ́ ́ ̉ ̉ ́ ̉ ̀ ́ ̀ ̀
cach. Dê thây co thê gia thiêt phân liên thông rôi ghep cac phân đôi lai.Goi ̀ ̀ ́ ́ ̣ ̀ ̣ ̉ ́ ̀
B cua ̣ d(A,B) la ̀ khoang cach ớ ̃ ̉ ́ ̉ ́ ̉
̉ G ky hiêu c đinh nghia nh la đô dai ngăn nhât trong cac đô dai cac đ gi a hai đinh ng đi t ̉. - (b) Gia s G không co chu trinh đô dai le ̉ G băng cach đ a vao ham khoang + Ta se xây d ng cu thê môt phân đôi cua ư ́ G liên thông, nêu không chi cân tiên hanh cho t ng thanh ̉ G (liên thông). ̣ A la môt đinh bât ky cua ữ ườ + V i môi đinh ư ̀ ừ A đên ̣ ̃ ̣ ̀ ́ ́ ́ ̣ ̀ ́
A va ̀ B, ́ B ̀ ́ G liên thông đam bao cho viêc đinh nghia nay la ́ ́ ̀ ̉ ̉ ̉ ̣ ̣ ̃ ̀
đ ượ (nh ư d(A,A) = 0). Chu y răng gia thiêt tôt.́
ng ng la tâp cac đinh co đô dai t i A la chăn, le. Hiên nhiên + Goi ̣ X, Y t ̀ ớ ̀ ̣ ́ ̉ ́ ̣ ̀ ̃ ̉ ̉
ơ ữ ̣ ̀ ̣ ̣ ̉ ̣ ̉ ̃ ̀ ̣ ̣ ̉
̉ ử B,C ˛ ̣ ̉ ̣ ̀ ̣ ̣ ́ ̀ ̀ ́
̉ G. h n n a môi tâp X sao cho (B,C) la môt canh cua (B,C), đ ng đi đô dai ngăn nhât t ́ ừ ườ ́ ̣ ̀ ́ ́ ̀ ̣ ́ ̣ ̀
A đên B, rôi canh i ớ A (co thê cân bo môt sô canh trung nhau va đinh lăp) ta se thu đ X, Y ̣ ̣ X, Y la môt tâp đinh đôc ̉ G. Thê thi băng cach nôi ́ ng đi co đô dai ngăn ́ ̣ c môt ườ ́ ừ C t ượ ́ ̉ ̀ ̉ ̣ ́ ̣ ̀ ̀ ̉ ̣ ̃
Trang 15
ư
GVBM: D Quang Anh Huy
ươ ứ tao thanh môt phân hoach cua tâp đinh cua lâp. Chăng han, gia s cac đ nhât t chu trinh co đô dai le, mâu thuân v i gia thiêt ban đâu. ớ ̀ ́ ̣ ̀ ̉ ̃ ̉ ́ ̀
Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ứ
ụ
ế
ề
ườ
ng THPT Th t N t ố ố
Nhân xet. ́ Ta se đ a ra môt đăc tr ng khac cua cac đô thi 2 phân thông qua ̃ ư ư ̣ ̣ ̣ ́ ̉ ́ ̀ ̣ ̀
sô săc tô. ́ ́ ́
Hê qua. ̉ Moi cây la môt đô thi hai phân. ̣ ̣ ̀ ̣ ̀ ̣ ̀
BÀI T P THAM KH O
Ậ
Ả
Bài 1. Ch ng minh răng trong môt đô thi G tuy y tông tât ca cac bâc cua cac ́
ứ ̀ ̣ ̀ ̣ ̀ ́ ̉ ́ ̉ ́ ̣ ̉
đinh trong G luôn băng hai lân sô canh cua no. ̉ ̀ ̀ ́ ̣ ̉ ́
Giai : Ta co đô thi G = (V,T) ̉ ́ ̀ ̣
= 2|E| ( Vi môi canh nôi chinh xac hai canh Ta cân ch ng minh : ứ ̀ ̀ ̃ ̣ ́ ́ ́ ̣
cua đô thi) ̉ ̀ ̣
→ đpcm.
ng tuy y luôn tôn tai hai
Bài 2. Ch ng minh răng trong môt đô thi đ n vô h
̣ ơ ứ ướ ̀ ̣ ̀ ̀ ́ ̀ ̣
̉ ́ ̣ ̀
̉ ơ ̀ ̣ ́ ̉ ̣ ̣ ̉ ́ ̉ ̉ ́ ̀
trong hai tr đinh co bâc băng nhau. ̣ ̉ Gia s đô thi G co n đinh vây bâc cua cac đinh chi co thê r i vao môt Giai : ̉ ử ợ ườ
ư ườ ng h p. ợ ́ ̣ ́ ́ ̉ ̉ ́
ng h p: TH1:{0,1,2,…,n-2} TH2:{1,2,3,…,n-1} Ap dung nguyên li Dirichlet co n đinh nh ng chi co n-1 tr → Tôn tai hai đinh co bâc băng nhau. ̀ ̣ ̉ ́ ̣ ̀
ng n nao thi tôn tai đô thi đêu đ n bâc ba
V i nh ng gia tri nguyên d
Bài 3.
ữ ớ ươ ơ ́ ̣ ̀ ̀ ̀ ̣ ̀ ̣ ̀ ̣
co n đinh. ́ ̉
Giai : ̉ Theo đê bai ta co : cac bâc cua đinh trong đô thi đ n đêu la 3 ma co n ̣ ơ ̀ ̀ ́ ́ ̣ ̉ ̉ ̀ ̀ ̀ ̀ ́
đinh ̉
̣ ơ ̉ ̣ ̉ ̀ ̀
→ Tông bâc cua đô thi đ n la 3n. Ma ta co : 3n = 2m (v i n , m nguyên d ng va n la sô canh cua đô thi đ n ớ ươ ̣ ơ ̀ ́ ̀ ̀ ́ ̣ ̉ ̀
(n > 3)).
↔ n = m → n la môt sô chăn. ̀ ̣ ́ ̃
:
Bài 4.
L p s đ quan h giao nhau c a các hình tròn trong hình sau đây ủ
ậ ơ ồ ệ
3
2
4
1
5
6
Trang 16
ư
GVBM: D Quang Anh Huy
Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ứ
ụ
ề
ế
ườ
ng THPT Th t N t ố ố
Gi iả
3
2
4
1
6
5
Bài 5.
ộ ờ
ắ ướ
Trên m t bàn c 3x 3 ô vuông có 2 con mã tr ng đ ng ở ứ ỏ ằ ộ
hai góc bên d ắ ứ ở ị
ả
t r ng ch đ ng ng ế ằ ố
hai góc bên trên và 2 con mã đen đ ng i. H i r ng có th đ i ể ổ ch 2 con mã đen lên v trí 2 con mã tr ng b ng m t cách t ươ ng ằ ỗ ng: con mã đen góc trái lên v trí trên góc trái và con mã đen v trí ị ị ứ bên ph i s lên góc bên trên v trí bên ph i còn 2 con mã tr ng thì ả ẽ ị ắ ỉ ượ ẫ c d n i hay không? Bi d xu ng v trí t ị c quy đ nh c a bàn c mà thôi. các con mã đi theo lu t đi đ ị ươ ứ ở ướ ượ ậ ủ ờ
Gi iả
ế ươ
ễ c n i b i m t c nh n u nh hai ô t ế ể ư ớ ỉ ớ ượ ố ở ứ ươ ứ ng ng v i đ nh là các ô vuông, ớ i ng ng v i chúng có th đi t
ộ ướ
ượ
ễ
ể ấ
ể
ỗ
ộ
ắ
Trang 17
ư
GVBM: D Quang Anh Huy
bên d - N u chúng ta đem bi u di n thành gragh t ể còn hai đ nh đ ộ ạ ỉ c đi c a m t ộ nhau b i m t b ủ ở c ượ c đ con mã. Graph thu đ ễ bi u di n trong hình bên. D th y khi đó không di chuy n các ể ể ổ con mã đ cho chúng có th đ i ch cho nhau sao cho 2 con mã đen lên v trí 2 con mã tr ng b ng ằ ắ ị ng ng: con mã đen m t cách t ứ ươ góc trái lên v trí trên góc trái và ị con mã đen v trí bên ph i s lên góc bên trên v trí bên ph i còn 2 con mã tr ng thì ị ả c nh v y, thì trên graph xu ng v trí t ổ ượ ươ ị c. Vì n u đ i đ ế ả ẽ ở i d ướ ượ ng ng ứ ư ậ ố ị
Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ứ
ụ
ề
ế
ườ
ng THPT Th t N t ố ố
ng ng, các con mã ph i đi qua đ u nhau là đi u không cho phép (m t b ộ ướ
c đi c m t c a con mã trên ủ ứ ầ ớ ộ ủ ướ
t ươ bình th graph t ng c a con mã t ng ng, và đ c bi ng ng v i m t phép d ch đi b ộ t chúng không đ ề ị c ăn nhau). ứ ườ ươ ứ ặ ả ươ ệ ượ
Ậ
Ề
Ị ể ệ ộ
ấ ộ
ch c bao nhiêu tr n đ u? cu c thi là b t kì đ i bóng nào ấ ậ ỏ
Bài 1. Có 20 đ i bóng tham gia thi đ u, th l ộ ầ ỉ ặ G i ý:ợ
ỗ ộ ỉ ặ ộ
đó suy ra t ng s ượ ồ ị ầ ủ ớ ỗ ỉ ừ
BÀI T P Đ NGH ấ ộ cũng ch g p nhau đúng m t l n. H i ph i t ả ổ ứ ộ ỉ c đ th đ y đ v i 20 đ nh. M i đ nh có b c là 19 t ỉ · 19) sau đó tính t ng s c nh cũng chính là s tr n đ u ph i t ấ
)1
ta coi m i đ i bóng là m t đ nh do hai đ i nào cũng ch g p nhau m t ộ ố ổ ch c theo ả ổ ứ l n nên ta đ ầ b c (20 ậ ậ ố ậ ố ạ ố
-pp ( 2
(c nh) v i p là s đ nh. công th c: ứ ố ỉ ạ ớ
ồ ộ ề ườ
ồ ứ ỗ ộ ả
i mà thành viên có quen nhau? ộ ể ế ườ
G i ý:ợ
ể ỗ Bài toán ch a 2 m i quan h là quen và không quen ta coi 5 ng ườ ố
ớ ạ ấ ậ
ỏ ạ ả ử ấ ạ ầ
ẽ ế ỏ
ạ ỏ ế ạ ế ỏ
ả ử ỏ ỏ ỏ
ế ề ỏ
ậ ỏ ỏ
Bài 2. M t nhóm g m 5 thành viên trong đó m i b 3 đ u có 2 ng i quen nhau và 2 không quen nhau. Ch ng minh r ng có th x p c nhóm ng i xung quanh ằ m t bàn tròn đ m i thành viên s ng i gi a hai ng ữ ẽ ồ i là 5 ệ ố ứ ng ng v i c nh n i 2 đ nh i quen nhau t đ nh A, B, C, D, E c a m t đ th : 2 ng ộ ồ ị ỉ ươ ứ ườ ủ ỉ i không quen nhau tô màu đ . Xét đ nh A b t kì, A có b c là 4 tô màu xanh còn 2 ng ườ ỉ suy ra A là đ u mút c a 4 c nh và có ít nh t hai c nh cùng lo i, gi s AB, AC là ủ màu xanh thì BC là màu đ . N u AD màu xanh thì DC s là màu đ còn n u BD màu xanh thì tam giác ABD có 3 c nh màu xanh, n u BD màu đ thì tam giác BCD có 3 c nh màu đ (vô lí) => AD màu đ . Gi s AB, AC là màu xanh thì BC là màu đ và ạ BD màu đ . Khi đó n u DC màu xanh EC, EA, EB, ED đ u nét đ (vô lí). V y BC ậ ỏ màu đ , l i có AD màu đ , BC màu đ suy ra CE, DE màu xanh. V y ta đ c cách ỏ ạ ượ i thành m t vòng tròn. x p 5 ng ộ ườ ế
A
B
E
C
D
ạ ộ ớ
Bài 3. M t l p 10 chuyên Toán có 6 b n h c sinh, trong bu i h p t tr
ị ằ đ u năm ổ ọ ổ ầ ạ quen đúng v i 3 b n ớ
ệ ứ ọ ỗ ạ ế ủ ỏ ỏ
b n t ng đã phát hi n ra đi u thú v r ng m i b n trong t ổ ề ạ ổ ưở khác ngay l p t c Chi đ ng lên bác b . H i ý ki n c a ai đúng? ậ ứ ố ộ ạ ể ẽ ố ớ G i ý:ợ ỏ ệ ổ ẽ ạ ỉ
màu đ . M t b n trong t nh t 3 c nh cùng màu ( có th màu xanh hay màu đ ). T đó rút ra k t lu n…. M i quan h quen nhau ta có th tô màu xanh còn không quen nhau ta tô là 1 đ nh s n i v i 5 c nh . Theo Dirichle, thì s có ít ừ ể ấ
i sao cho ạ Bài 4. Hãy v m t graph bi u di n quan h quen bi ẽ ộ ế ủ ể ễ
Trang 18
ư
GVBM: D Quang Anh Huy
không có 3 ng ậ ế t c a 5 ng ườ i nào đôi m t quen nhau ho c đôi m t không quen nhau? ặ ỏ ệ ộ ườ ộ
Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ứ
ụ
ế
ề
ườ
ng THPT Th t N t ố ố
ề ố ỉ ỉ
ỉ ấ ấ ỉ ề ỏ
G i ý:ợ Graph có 5 đ nh là 5 đ nh c a ngũ giác đ u và c nh n i 2 đ nh b t kì là ủ c nh c a ngũ giác đ u này th a mãn y u c u đ bài. Th t v y, n u ta l y 3 đ nh tùy ế ề ầ ủ ạ ý thì luôn có 2 đ nh k nhau và có 2 trong s chúng không k nhau. ố ạ ậ ậ ề ề ề ỉ
M C L C
Ụ
Ụ
Trang
L i m đ u ờ
Đ TH TRONG Đ I S NG Ờ Ố ……..………..……………………………….…..
ở ầ ……………………………………………………..…………...…...… 01 Ồ Ị 03
Ệ
KHÁI NI M C B N V Đ TH Ơ Ả M T S Đ TH Đ C BI T
ồ ị ườ
NG ĐI EULER VÀ Đ TH HAMILTON Đ Ồ Ị ƯỜ
1. Đ ng đi Euler ………………………………………………………………. 2. Đ th Hamilton ………………………………………………………………
CÁC M NH Đ M R NG VÀ T LI U THAM KH O Ề Ồ Ị ……………………………………………. 05 Ệ ……………………………………………………09 Ộ Ố Ồ Ị Ặ 07 1. Đ th con …………………………………………………………………… 2. Đ ng đi …………………………………………………………………….. 07 3. Chu trình …………………………………………………………………….. 08 ……………………………….. 10 10 10 Ả ………………….. 10 Ư Ệ
* T li u tham kh o ……………………………………………………………. Ề Ở Ộ ả
1. Đ nh nghĩa và các tính ch t c b n v cây ………………………………....... ề ấ ơ ả
ườ ồ ị Ệ ư ệ 10 ị 10
Đ TH PH NG VÀ TÔ MÀU Đ TH Ồ Ị ố Ẳ
ồ ị ẳ
ồ ị
2. Cây khung ………………………………………………………………...…. 11 11 3. Cây có g c ………………………………………………………………..…. Ồ Ị ………………………………………. 12 12 13 13 14 14 14
1. Đ th ph ng ………………………………………………………………… 2. Tô màu đ th ……………………………………………………………….. 3. M t s đ nh lí ………………………………………………………………... * M nh đ …………………………………………………………………….... 1. M nh đ 1 …………………………………………………………………… 2. M nh đ 2 …………………………………………………………………… 3. M nh đ 3 …………………………………………………………………….
BÀI T P THAM KH O BÀI T P Đ NGH Ề Ả ………………………………………………………... 16 Ị ……………………………………………………………... 18
Trang 19
ư
GVBM: D Quang Anh Huy
ộ ố ị ề ệ ề ệ ề ệ ề ệ 15 Ậ Ậ
Nhóm 1: Chuyên đ “Lý thuy t Graph và ng d ng”
Tr
ụ
ứ
ề
ế
ườ
ng THPT Th t N t ố ố
Trang 20
ư
GVBM: D Quang Anh Huy
