Tài liệu Các bài toán về đường đi

C￁C B￀I TO￁N V? ???NG ?I
I. CHU TRￌNH V￀ ???NG ?I EULER
1. B￠i to￡n m? ??u
2. ??nh ngh?a
3. Chu tr￬nh v￠ ???ng ?i Euler trong ?? th? v￴ h??ng
4. Chu tr￬nh v￠ ???ng ?i Euler trong ?? th? c￳ h??ng
II. CHU TRￌNH V￀ ???NG ?I HAMILTON
1. Chu tr￬nh Hamilton
2. Ph??ng ph￡p t￬m chu tr￬nh Hamilton
3. ???ng ?i Hamilton
III. B￀I TO￁N ???NG ?I NG?N NH?T
1. M? ??u
2. Thu?t to￡n t￬m ???ng ?i ng?n nh?t
IV. THU?T TO￁N HEDETNIEMI
1. Ph￩p c?ng ma tr?n Hedetniemi
2. Thu?t to￡n Hedetniemi


I. Chu tr￬nh v￠ ???ng ?i Euler TOP


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


B￠i to￡n 7 c￢y c?u ? K￶nigsberg: Th￠nh ph? K￶nigsberg thu?c Ph? (b￢y gi? g?i l￠ Kaliningrad thu?c C?ng h￲a Li￪n bang Nga) ???c chia th￠nh b?n vng b?ng c￡c nh￡nh s￴ng Pregel. C￡c vng n￠y g?m 2 vng b￪n b? s￴ng, ??o Kneiphof v￠ m?t mi?n n?m gi?a 2 nh￡nh c?a s￴ng Pregel. V￠o th? k? th? XVIII, ng??i ta ?￣ x￢y 7 c￢y c?u n?i c￡c vng l?i v?i nhau nh? s? ?? sau:

V￠o ch? nh?t, ng??i d￢n ? ?￢y th??ng ?i b? d?c theo c￡c vng trong th￠nh ph?. H? t? h?i C￳ th? xu?t ph￡t t?i m?t ?i?m n￠o ?￳ trong th￠nh ph?, ?i qua t?t c? 7 c￢y c?u, m?i c￢y m?t l?n, r?i tr? v? ?i?m xu?t ph￡t ???c kh￴ng?
Nh￠ to￡n h?c Th?y S? Leonard Euler ?￣ nghi￪n c?u gi?i b￠i to￡n n￠y. L?i gi?i c?a ￴ng ???c c￴ng b? n?m 1736. B￠i to￡n n￠y c￳ th? ???c coi l￠ m?t trong nh?ng ?ng d?ng ??u ti￪n c?a l thuy?t ?? th?.
Ta c￳ th? x￢y d?ng ?? th? G = (V, E) m￴ t? b￠i to￡n nh? sau:
+ ??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 vng ??t trong s? ??. ??i t??ng c?a b￠i to￡n ? ?￢y l￠ m?t vng ??t trong s? ??. V?y, m?i ??nh bi?u di?n cho m?t vng ??t. ?? th? G s? c￳ 4 ??nh A, B, C, D t??ng ?ng v?i 4 vng ??t.
+ C?nh: Trong ?? th? G c￡c ??nh v￠ ???c n?i v?i nhau b?ng m?t c?nh e ??i di?n cho m?t chi?c c?u n?i gi?a hai vng ??t. ?? th? G s? c￳ 7 c?nh t??ng ?ng v?i 7 chi?c c?u n?i gi?a c￡c vng ??t trong s? ??.
Euler ?￣ nghi￪n c?u b￠i to￡n n￠y, m￴ h￬nh n￳ b?ng m?t ?a ?? th?, b?n vng ???c bi?u di?n b?ng 4 ??nh, c￡c c?u l￠ c￡c c?nh nh? ?? th? sau:
B￠i to￡n t￬m ???ng ?i qua t?t c? c￡c c?u m?i c?u kh￴ng qu￡ m?t l?n c￳ th? ???c ph￡t bi?u l?i b?ng m￴ h￬nh n￠y nh? sau: T?n t?i hay kh￴ng m?t chu tr￬nh ??n trong ?a ?? th? G= (V, E) c￳ ch?a t?t c? c￡c c?nh?
2. ??nh ngh?a TOP


2.1. Chu tr￬nh Euler (?? th? Euler)
Cho G = (V,E) l￠ m?t ?a ?? th? li￪n th￴ng. Chu tr￬nh ??n ch?a t?t c? c￡c c?nh c?a ?? th? G ???c g?i l￠ chu tr￬nh Euler. ?? th? c￳ ch?a m?t chu tr￬nh Euler ???c g?i l￠ ?? th? Euler.
2.2. ???ng ?i Euler
Cho G = (V,E) l￠ m?t ?a ?? th? li￪n th￴ng. ???ng ?i Euler trong G l￠ ???ng ?i ??n ch?a t?t c? c￡c c?nh c?a ?? th? G.
V￭ d? 1: ?? th? c￳ chu tr￬nh Euler: a, b, e, d, c, e, a.
V￭ d? 2: ?? th? kh￴ng c￳ chu tr￬nh Euler nh?ng c￳ ???ng ?i Euler: a, c, d, a, b, e, d, b.
V￭ d? 3: ?? th? kh￴ng c￳ chu tr￬nh Euler v￠ ???ng ?i Euler.
3. Chu tr￬nh v￠ ???ng ?i Euler trong ?? th? v￴ h??ng TOP


Khi gi?i b￠i to￡n c?u K￶nigsberg, Euler ?￣ ph￡t hi?n ra c￡c ti￪u chu?n ?? kh?ng ??nh m?t ?a ?? th? c￳ chu tr￬nh v￠ ???ng ?i Euler hay kh￴ng?
3.1. ??nh l v? chu tr￬nh Euler
M?t ?a ?? th? li￪n th￴ng G =(V, E) c￳ chu tr￬nh Euler khi v￠ ch? khi m?i ??nh c?a n￳ ??u c￳ b?c ch?n.
Ch?ng minh
(￞) Ta s? ch?ng minh n?u ?? th? G c￳ chu tr￬nh