Chương 3 - CÁC BÀI TOÁN ĐƯỜNG ĐI

CÁC BÀI TOÁN Đ

NG ĐI

ƯỜ

ntsonptnk@gmail.com

N I DUNG

Ộ

Đ ng đi ng n nh t ấ

ườ

ắ

Bài toán

Nguyên lý Bellman

Thu t toán Dijkstra ậ

Thu t toán Floyd ậ

Thu t toán Ford-Bellman ậ Đ th Euler ồ ị Đ th Hamilton ồ ị

Lý thuy t đ th , ch

2 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

Đ

ƯỜ

NG ĐI NG N NH T Ắ

Ấ

Lý thuy t đ th - ch

3 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

BÀI TOÁN

ướ

ỉ

có tr ng ọ G=(X, E) và hai đ nh t, đ nh s đ n đ nh ế ừ ỉ c đ nh ng đi P đ ị ượ

ng Cho đ th có h ồ ị s, t ˛ X, g i P là m t đ ng đi t ộ ườ ọ ng (hay giá) c a đ tr ng l ườ ủ ượ ọ nghĩa là:

L(P) = (cid:229)

(e˛ P)L(e)

ng đi t

s đ n t có tr ng l

ườ

ừ

ế

ọ

ượ

Bài toán: tìm đ nh nh t ấ

ỏ

Lý thuy t đ th - Nguy n Thanh S n

4 ế ồ ị

ơ

ễ

NH N XÉT

Ậ

c phát bi u cho đ th có h ể ướ ượ ồ ị

 Bài toán đ ư ọ ụ ể

ướ

ậ ị ồ ị ề ằ ạ ọ ư ủ

ng n i cùng m t c p đ nh nh ng có chi u ng ỉ ướ ặ ọ ượ ư ề ố ộ

ng có tr ng, nh ng các thu t toán s trình bày đ u có th áp d ng ẽ cho các đ th vô h ng có tr ng b ng cách xem m i ỗ ồ ng nh hai c nh có cùng tr ng c nh c a đ th vô h ạ l c ượ nhau.  Khi tìm đ ườ

ấ i m t c nh có tr ng l ng đi ng n nh t có th b b t đi các c nh ạ ng nh ỏ ể ỏ ớ ọ ắ ừ ạ ộ ạ ượ ỉ

song song và ch ch a l nh t.ấ

ượ

ố ớ ể ỏ ả ủ ọ ả ế

ưở ọ

ng đi ng n nh t không có l i gi  Đ i v i các khuyên có tr ng l th b đi mà không làm nh h ế toán. Đ i v i các khuyên có tr ng l ượ ố ớ đ a đ n bài toán đ ấ ng không âm thì cũng có ng đ n k t qu c a bài ng âm thì có th ể ờ ườ ả . i ư ế ắ

Lý thuy t đ th - Nguy n Thanh S n

5 ế ồ ị

ơ

ễ

ĐI U KI N T N T I L I Gi

I Ệ Ồ Ạ Ờ Ả

Ề

ng đi t

s P có ch a m t

ộ ườ

ừ s đ n ế t, gi

ả ử

ứ

ộ

P là m t đ m ch ạ

ng đi P b ng ế ể ả ế ườ ằ

m . 0 thì có th c i ti n đ ạ

m ) ‡ N u L( cách b đi m ch ỏ m ) < 0 thì không t n t i đ ồ ạ ườ ng đi ng n nh t t ắ

t vì n u quay vòng t ế ỉ

ế ng đ ườ ượ ấ ừ ạ m càng nhi u ề i ng đi P càng nh đi, t c là ỏ ứ

N u L( ế s đ n đ nh đ nh ỉ vòng thì tr ng l ọ -¥ L(P)ﬁ .

t s

Lý thuy t đ th - Nguy n Thanh S n

6 ế ồ ị

ơ

ễ

Ậ c đ nh nghĩa:

Ma tr n ậ tr ng l

ọ

ượ

D LI U NH P Ữ Ệ ng LNxN đ ượ ị

ượ ng c nh nh nh t n i i đ n j n u có, ấ ố ế ế ạ ỏ

n u không có c nh n i i đ n j. ế ế ố Lij = tr ng l ọ Lij = ¥

ể

ậ

ặ

ộ ố ể

ằ

ợ

ạ Khi cài đ t thu t toán có th dùng 0 thay cho b ng cách đ a thêm m t s ki m tra thích h p.

12

¥ (cid:246) (cid:230) B A (cid:247) (cid:231)

¥ (cid:247) (cid:231)

16

7

5

(cid:247) (cid:231)

15

¥ ¥ ¥

14

(cid:247) (cid:231) (cid:247) (cid:231) ¥ ¥ ł Ł D C

Lý thuy t đ th - Nguy n Thanh S n

7 ế ồ ị

ơ

ễ

P2 P1 t s

’

NGUYÊN LÝ BELLMAN

Lý thuy t đ th - Nguy n Thanh S n

8 ế ồ ị

ơ

ễ

NGUYÊN LÝ BELLMAN

ấ ừ ỉ

G iọ P là đ P. Gi

ủ

đ nh s đ n đ nh 1 là đ ườ ng đi con c a P t ng đi ng n nh t t ắ

t; ế ỉ ng đi con ừ ấ ừ

ng đi ng n nh t t ắ ườ ¯ P2 v i Pớ k ˛ s P=P ả ử 1 2 là đ ừ s đ n k và P c a P t ườ ế ủ k đ n ế t. Khi đó P1 cũng là đ ườ . s đ n kế

P2 P1 t s

’

L(P1’) < L(P1) (cid:222)

L(P1’¯ P2) < L(P1

¯ P2)=L(P)

Lý thuy t đ th - Nguy n Thanh S n

9 ế ồ ị

ơ

ễ

TÌM Đ

NG ĐI NG N NH T TRÊN Đ TH CÓ TR NG S D

ƯỜ

Ố ƯƠ

Ọ

Ồ

Ấ

Ắ

Ị

THU T TOÁN DIJKSTRA

Ậ

Lý thuy t đ th - ch

10 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

THU T TOÁN DIJKSTRA

Ậ

ng, đ nh xu t Input: N, L, s, t – s đ nh, ma tr n tr ng l ố ỉ ậ ọ ượ ấ ỉ

phát, đ nh k t thúc ế ỉ

ng ĐĐNN s k, Labels[k]: ọ

đ nh ngay tr ượ k Output: D, Labels – D[k]: tr ng l c k trong ĐĐNN s ướ ỉ

, " k˛ X\{s}; Labels[k]=-1, " k˛ X.

1. V=X; D[s]=0; D[k]=¥ 2. Trong khi t˛ V:

1. Ch n đ nh v ọ ỉ ˛ V v iớ D[v] nh nh t ấ ; ỏ

2. V := V\{v};

3. V i m i đ nh k ˛ V và có c nh n i t ọ ỉ ớ ố ừ ạ v đ n k, ế

N u D[k] ế > D[v]+Lvk thì

D[k] = D[v]+Lvk và Labels[k]=v

Lý thuy t đ th - ch

11 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

d(u) = 50

d(z) = 75

u

z

s

d(u) = 50

d(z) = 60

u

z

s

 60 C p nh t đ dài ĐĐ t ậ ộ ậ ừ s đ n đ nh z: 75 ỉ ế

Lý thuy t đ th - ch

12 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

ị ỉ ồ

2

ấ ừ ỉ

9

8

Đ th G g m 7 đ nh, 12 ồ c nh nh hình bên. Tìm ạ ng đi ng n nh t t đ nh đ ắ ườ 1 đ n đ nh 5 ế ỉ

4

3

1

3

¥ ¥ ¥ (cid:246) (cid:230)

(cid:247) (cid:231)

4

¥ ¥ ¥ ¥ ¥ (cid:247) (cid:231)

6

8

5

(cid:247) (cid:231) ¥ ¥ ¥ ¥ ¥

2

(cid:247) (cid:231)

8 0 1

5 8

¥ ¥ ¥ (cid:247) (cid:231)

4

5

(cid:247) (cid:231)

7

¥ ¥ ¥ ¥ ¥ (cid:247) (cid:231)

12

17

17 0

(cid:247) (cid:231) ¥ ¥ ¥ ¥ ¥

6

(cid:247) (cid:231)

12 0

¥ ¥ ¥ ¥ ł Ł

Lý thuy t đ th - ch

13 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

ỉ ỏ ố ị

V: đ nh ch a b tô màu; D[k]: s có màu đ ; Labels[k]: s có ố ư màu xanh lá ¥

2

-1

9

8

4

3

1

-1

1

3

0 -1

4

6

5

¥ -1

8

2

4

¥ ¥

7

5

-1 -1

12

17

6

¥ -1

Lý thuy t đ th - ch

14 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

ỉ ỏ ố ị

V: đ nh ch a b tô màu; D[k]: s có màu đ ; Labels[k]: s có ố ư màu xanh lá

2

9 1

9

8

4

3

1

-1

1

3

0 -1

4

6

5

3 1

8

2

4

7

5

-1 6 1

12

17

6

¥ -1

Lý thuy t đ th - ch

15 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

ỉ ố ỏ ị

V: đ nh ch a b tô màu; D[k]: s có màu đ ; Labels[k]: s có ố ư màu xanh lá

2

7 4

9

8

4

3

1

4 4

1

3

0 -1

4

6

5

3 1

8

2

4

7

5

11 4 6 1

12

17

6

¥ -1

Lý thuy t đ th - ch

16 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

ỉ ỏ ố ị

V: đ nh ch a b tô màu; D[k]: s có màu đ ; Labels[k]: s có ố ư màu xanh lá

2

7 4

9

8

4

3

1

4 4

1

3

0 -1

4

6

5

3 1

8

2

4

7

5

9 3 6 1

12

17

6

¥ -1

Lý thuy t đ th - ch

17 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

ỉ ố ỏ ị

V: đ nh ch a b tô màu; D[k]: s có màu đ ; Labels[k]: s có ố ư màu xanh lá

2

7 4

9

8

4

3

1

4 4

1

3

0 -1

4

6

5

3 1

8

2

4

7

5

9 3 6 1

12

17

6

¥ -1

Lý thuy t đ th - ch

18 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

ĐĐNN t 1 đ n 5 có tr ng l ng D[5]=9: 5  3  4  1 ừ ế ượ

2

ọ 7 4

9

8

4

3

1

4 4

1

3

0 -1

4

6

5

3 1

8

2

4

5

7

9 3 6 1

12

17

6

26 5

Lý thuy t đ th - ch

19 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

GIÁ TR CÁC BI N D, Labels

Ế

Ị

D Labels

2 3 4 5 6 7 1 2 3 4 5 6 7

¥ ¥ ¥ ¥ ¥ 1 0 ¥ 0 0 -1 -1 -1 -1 -1 -1 -1

¥ 1 3 ¥ 6 1 1 -1 1 -1 -1 1

¥ 2 9 ¥ 7 4 6 2 4 4 4 -1 1

3 4 3 -1 1

7 3 6

4 4 3 -1 7 4

5 3 -1 5 1 1 9 ¥ 9 ¥ 9 ¥

Lý thuy t đ th - ch

20 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

5 E

¥ ¥

Lý thuy t đ th - ch

21 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

Lý thuy t đ th - ch

22 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

THU T TOÁN DIJKSTRA – CÀI Đ T

Ặ

Ậ

Graph Graph::Dijkstra(int s, int t) {

//Tìm đ ườ ng đi ng n nh t t ắ ấ ừ s đ n t ế

}

Lý thuy t đ th - ch

23 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

THU T TOÁN DIJKSTRA – CÀI Đ T

Ậ

Ặ

Graph Graph::PrintPath(int s, int t) {

s đ n t d a vào Labels ự ấ ừ ườ

int temp[MAX]; int dem = 0; //In đ ng đi ng n nh t t ế ắ while(Labels[t] != -1) {

temp[dem++]=t; t=Labels[t];

} temp[dem++]=s; while (dem > 0)

printf(“%d “, temp[--dem]);

}

Lý thuy t đ th - ch

24 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

TÌM Đ

NG ĐI NG N NH T GI A CÁC C P Đ NH TRÊN Đ TH

ƯỜ

Ữ

Ồ

Ắ

Ấ

Ặ

Ỉ

Ị

THU T TOÁN FLOYD

Ậ

Lý thuy t đ th - ch

25 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

THU T TOÁN FLOYD

Ậ

ố ỉ ậ ọ ủ

Input: N, L – s đ nh, ma tr n tr ng l ượ Output: L, Nexts – L[u, v]: tr ng l v, ọ ng c a G(X, E) ng ĐĐNN u ượ

Nexts[u, v]: đ nh ngay sau u trong ĐĐNN u v ỉ

1. N u L[u, v]

: Nexts[u, v]=v [u, v]=-1 , "

(u, v)˛ X2.

ế Ng ớ

„ ¥

X có L[u, t]„ X có L[t, v]„

i: Nexts c l ượ ạ ọ ˛ X 2. V i m i t ọ ˛ V i m i u ớ ọ ˛ V i m i v ớ N u L[u, v] > L[u, t] + L[t, v] thì ế

1. L[u, v] = L[u, t] + L[t, v]

2. Nexts[u, v] = Nexts[u, t]

Lý thuy t đ th - ch

26 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

ng đi ng n nh t gi a các c p đ nh

ắ

ữ

ặ

ỉ

Xác đ nh đ ị ấ ườ trên đ th g m 4 đ nh 6 c nh ồ ị ồ

ạ

ỉ

2

8

4

9

1

4

3

5

1 Lý thuy t đ th - ch

27 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

2

4 2 ¥ ¥ 9

-1 -1 8 3 -1 2

4

1 3

¥ ¥ 34 -1 -1 ¥

1

3

-1 5 1

Lý thuy t đ th - ch

28 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

t = 1 u = 3 v = 2

2

4 2 ¥ ¥ 9

-1 -1 8 3 14 1 -1 2

4

1 3

¥ ¥ 34 -1 -1 ¥

1

3

-1 5 1

Lý thuy t đ th - ch

29 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

t = 1 u = 3 v = 4

2

4 2 ¥ 9

-1 -1 8 3 14 1 2

4

¥ ¥ 34 -1 1 3 8 1 -1 ¥

1

3

-1 5 1

Lý thuy t đ th - ch

30 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

t = 2 u = 1 v = 3

2

4 2 ¥ 9

-1 -1 8 3 14 1 2

4

34 -1 1 3 8 1 ¥

1

3

-1 17 2 5 1

Lý thuy t đ th - ch

31 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

t = 2 u = 3 v = x

2

4 2 ¥ 9

-1 -1 8 3 14 1 2

4

34 -1 1 3 8 1

17 2

1

3

5 1

Lý thuy t đ th - ch

32 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

t = 2 u = 4 v = 3

2

4 2 ¥ 9

-1 -1 8 3 14 1 2

4

34 -1 1 3 8 1

17 2

1

3

5 1

Lý thuy t đ th - ch

33 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

t = 3 u = 1 v = 2

2

4 2 ¥ 9

-1 -1 8 3 14 1 2

4

34 -1 1 3 8 1

17 2

1

3

5 1

Lý thuy t đ th - ch

34 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

t = 3 u = 1 v = 4

2

4 2 ¥ 9

-1 -1 8 3 14 1 2

4

34 -1 1 3 8 1

17 2

1

3

5 1

Lý thuy t đ th - ch

35 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

t = 3 u = 2 v = 1, 4

2

4 2 13 9 16 3

3 8 3 14 1 2

4

34 -1 1 3 8 1

17 2

1

3

5 1

Lý thuy t đ th - ch

36 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

t = 3 u = 4 v = 1, 2

2

4 2 13 9 16 3

3 8 3 14 1 2

4

34 63 1 3 8 1

17 2

1

3

5 1

Lý thuy t đ th - ch

37 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

t = 4 u = 1 v = 2, 3

2

4 2 13 7 16 3

3 8 3 14 1 4

4

34 63 1 3 8 1

4 4

1

3

5 1

Lý thuy t đ th - ch

38 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

t = 4 u = 2 v = 1, 3

2

4 2 13 7 16 3

3 8 3 14 1 4

4

34 63 1 3 8 1

4 4

1

3

5 1

Lý thuy t đ th - ch

39 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

t = 4 u = 3 v = 1, 2

2

4 2 13 7 16 3

3 8 3 12 1 4

4

34 63 1 3 8 1

4 4

1

3

5 1

Lý thuy t đ th - ch

40 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

t s

TÌM Đ

NG ĐI NG N NH T TRÊN Đ TH CÓ C NH ÂM

ƯỜ

Ồ

Ắ

Ấ

Ạ

Ị

THU T TOÁN BELLMAN

Ậ

Lý thuy t đ th - ch

41 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

THU T TOÁN BELLMAN

ng c a G(X, E),

Ậ Input: N, L, u – s đ nh, ma tr n tr ng l ố ỉ

ượ ậ ọ ủ

v sau k ọ

b v ỉ Output: p ướ ặ đ nh xu t phát ấ , Labels – p (k, v): tr ng l c l p, Labels[v]: đ nh ngay tr ỉ ượ ướ

ng ĐĐNN u c v trong ĐĐNN u " v˛ X\{u}; Labels[v] = -1 " v˛ X;

1 . p (0, u)=0; p (0, v)=¥ 2. L p v i k = 1, 2, N-1 ớ

ế ấ ạ ỏ

ặ 1 ." j„

i˛ X, ch n jọ ˛ X sao cho p (k-1, j)+Lji đ t nh nh t; n u i: 1 .p (k, i)= p (k-1, j)+Lji 2.Labels[i] = j

2.N u ế p (k) = p (k-1): p (k, v) là đ

v n còn thay đ i sau b ổ ườ ướ ặ ng đi ng n nh t u ắ c l p N-1: t ừ ấ  v u đã đi đ n ế

ẫ m ch âm 3. N u ế p ạ

Lý thuy t đ th - ch

42 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

1

ườ

1

2 -2

8

2

ng Tìm đ đi ng n nh t ấ ắ đ nh 3 t ỉ ừ các đ n ế i đ nh còn l ạ ỉ

5

3

4

1 -1

2

6

5 Lý thuy t đ th - ch

43 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

k = 0

1

¥ ¥

-1

1

2

-1

-2

8

2

5

3

0 -1 -1

4

1 -1

¥ ¥

2

6

-1

5

-1

Lý thuy t đ th - ch

44 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

k = 1

1

¥ ¥

-1

1

2

-1

-2

8

2

5

3

0 -1 5 3 -1

4

1 -1

¥ ¥

2

6

4 3 -1

5

-1 3 -1

Lý thuy t đ th - ch

45 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

k = 2

1

¥ ¥

-1

1

2

-1

-2

8

2

5

3

0 -1

4

5 3

4

1 -1

2

6

4 1 5 3

5

-1 3

Lý thuy t đ th - ch

46 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

k = 3

1

¥ ¥

-1

1

2

-1

-2

8

2

5

3

0 -1

4

5 2 3 6

4

1 -1

2

6

1 5

5

-1 3

Lý thuy t đ th - ch

47 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

k = 4

1

¥ ¥

-1

1

2

-1

D NGỪ

-2

8

2

5

3

0 -1

4

2 6

4

1 -1

2

6

1 5

5

-1 3

Lý thuy t đ th - ch

48 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

, Labels

Ế p GIÁ TR CÁC BI N

Ị

p Labels

k/v 1 2 k/v 1 2 3 3 4 5 6 4 5 6

¥ ¥ ¥ ¥ ¥ 0 -1 -1 -1 -1 -1 -1 0 0

¥ ¥ 0 5 -1 4 1 -1 -1 -1 3 3 3 1

¥ ¥ 0 5 -1 1 2 -1 -1 -1 3 3 5 2

¥ ¥ 0 2 -1 1 3 -1 -1 -1 6 3 5 3

¥ ¥ 0 2 -1 1 4 -1 -1 -1 6 3 5 4

Lý thuy t đ th - ch

49 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

1

ườ

1

2 -2

8

2

ng Tìm đ đi ng n nh t ấ ắ đ nh 1 t ỉ ừ các đ n ế i đ nh còn l ạ ỉ

5

3

4

1 -1

2

6

5 Lý thuy t đ th - ch

50 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

k = 0

1

-1

1

2

0 -1

-2

8

2

¥ ¥

5

3

-1 -1

4

1 -1

¥ ¥

2

6

-1

5

-1

Lý thuy t đ th - ch

51 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

k = 1

1

1 1

1

2

0 -1

-2

8

2

5

3

2 1 -1

4

1 -1

¥ ¥

2

6

-1

5

-1

Lý thuy t đ th - ch

52 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

k = 2

1

1 1

1

2

-1 2

-2

8

2

5

3

2 1 7 3

4

1 -1

2

6

6 3

5

1 3

Lý thuy t đ th - ch

53 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

k = 3

1

0 1

1

2

-1 2

-2

8

2

5

3

1 1 7 3

4

1 -1

2

6

3 5

5

1 3

Lý thuy t đ th - ch

54 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

k = 4

1

0 1

1

2

-2 2

-2

8

2

5

3

1 1 6 3

4

1 -1

2

6

3 5

5

0 3

Lý thuy t đ th - ch

55 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

k = 5

1 Ừ

-1 1

1

2

-2 2

-2

8

2 D NG – CÓ M CH Ạ ÂM

5

3

0 1 4 6

4

1 -1

2

6

2 5

5

0 3

Lý thuy t đ th - ch

56 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

Konigsberg, Hmmm

Leonhard Euler (1707 – 1783)

Đ TH EULER

Ồ Ị

Lý thuy t đ th - ch

57 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

BÀI TOÁN 7 CHI C C U

Ầ

Ế

ị

ế

ầ

ớ

ữ

m t vùng đi d o qua m i ỗ

ở ề ơ

ạ ấ

ế

ầ

ứ

ị

Thành phố Konigsberg (Đ c)ứ b chia thành 4 vùng 7 chi c c u n i do 2 nhánh c a 1 dòng sông. Có ố ủ nh ng vùng n y v i nhau. ầ Bài toán: xu t phát t ộ ừ ấ chi c c u đúng m t l n và tr v n i xu t phát. ộ ầ Năm 1736, nhà toán h c Euler đã mô hình bài toán ọ ng v i m i đ nh ng n y b ng m t đ th vô h ỗ ỉ ướ ộ ầ v i m t vùng, m i c nh ng v i m t chi c c u ầ ế ớ ớ

ồ ỗ ạ

ớ ộ

ằ ộ

ứ

Lý thuy t đ th - ch

58 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

BÀI TOÁN 7 CHI C C U

Ế

Ầ A

C D

Lý thuy t đ th - ch

59 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

Đ NH NGHĨA

Ị

t c các dây chuy n đi qua t ề ả ấ

 DÂY CHUY N EULER: ỗ ạ c nh trong đ th ạ ộ ầ

Ề ồ ị, m i c nh đúng m t l n.  CHU TRÌNH EULER: dây chuy n Euler có đ nh đ u ề ầ ỉ

trùng v i đ nh cu i. ố ớ ỉ

 Đ NG ĐI EULER: đ ng đi qua t t c các c nh c a ƯỜ ườ ấ ả ủ ạ

đ thồ ị, m i c nh đúng m t l n. ỗ ạ ộ ầ

đ ng đi Euler có đ nh đ u trùng v i ớ ỉ ầ ườ

NG: đ th vô h ng có ch a  M CH EULER: đ nh cu i. ố Ị ƯỚ ồ ị ướ ứ

 Đ TH EULER VÔ H m t chu trình Euler.  Đ TH EULER CÓ H NG: đ th có h ng có ch a ƯỚ ồ ị ướ ứ

Ị m t m ch Euler. ạ Ạ ỉ Ồ ộ Ồ ộ

Lý thuy t đ th - ch

60 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

Đ NH LÝ EULER

Ị

ng

ồ ị

ướ G=(X, E)

(cid:219)

Đ th vô h 1. G là đ th Euler ồ

ị

G liên thông và d(x) ch n ẵ

" x˛ X.

ứ

2. G có ch a dây chuy n Euler và không ch a chu G liên thông có ch a ứ

ề trình chu trình Euler (cid:219) . đúng hai đ nh b c l ậ ẻ ỉ

ng

ướ G=(X, E)

ồ ị

G liên thông và d+(x)=d-(x)

ồ ị

(cid:219)

Đ th có h 1. G là đ th Euler X.

" x ˛

Lý thuy t đ th - ch

61 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ a

e e

a c a d d b

b c b

ỉ

ậ

ề

ng đi

ườ

có đ Euler: bacbd

d (G2) (G1) c (G3)

Liên thông và có 2 ậ ẻ  có đ nh b c l dây chuy n Euler: ề bacdaedbc

Liên thông và các đ nh đ u có b c ch n ẵ  có chu trình Euler: bacdaedbcb

Lý thuy t đ th - ch

62 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

GI

I THU T FLEURY

Ả

Ậ

e c a đ th G đ

C nh ạ

ồ ị

C UẦ n u xóa ế

ủ ỏ ồ ị

ầ

c g i là e ọ ượ kh i đ th thì làm tăng s thành ph n liên thông ố c a ủ G. ả

ầ

ọ

i thu t ở ạ

ậ G i chu trình c n tìm là Gi 1. Kh i t o: Ch n m t đ nh b t kỳ cho vào ộ ỉ ọ 2. L p trong khi G v n còn c nh ẫ

ấ ạ

ặ

ạ 1. Ch n c nh ọ ọ

ộ ỉ ế ố ỉ ắ ớ ầ ọ

e n i đ nh v a ch n v i m t đ nh k v i ừ ề ớ nó theo nguyên t c: ch ch n c u n u không còn ỉ c nh nào khác đ ch n. ạ ể ọ

. 2. B sung ổ e và đ nh cu i c a nó vào C ố ủ ỉ

3. Xóa e kh i ỏ G.

Lý thuy t đ th - ch

63 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

1 2 3 4 5 3 1

Lý thuy t đ th - ch

64 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

Gi

I THU T XÁC Đ NH CÁC CHU TRÌNH

Ả

Ậ

Ị THÀNH PH NẦ

ồ ị

ọ

ỉ

Input: đ th Euler G(X, E) Output: chu trình Euler C c a Gủ 1. Ch n đ nh v X; C = {v} 2. L p trong khi G còn c nh

ạ

ặ

˛ 1. Ch n đ nh v C còn c nh trong G ọ ỉ ạ

2. Tìm chu trình C’ xu t phát t v. ấ ừ

3. Ghép C’ vào C

4. Lo i b các c nh c a C’ kh i G ạ ạ ỏ ủ ỏ

Lý thuy t đ th - ch

65 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

VÍ DỤ

1 3 2 4 3 5 3

Lý thuy t đ th - ch

66 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

Sir William Rowan Hamilton (1805-1865)

Đ TH HAMILTON

Ồ Ị

Lý thuy t đ th - ch

67 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

BÀI TOÁN KH I ĐI M

Ở Ể

ấ

ừ ộ ỉ

ị ệ

ủ

ậ

ề

ủ

ạ

“Xu t phát t m t đ nh c a kh i th p nh di n ố đ u, hãy đi d c theo các c nh c a kh i đó sao ọ t c các đ nh khác, m i đ nh qua cho đi qua t ỉ ấ ả đúng m t l n, sau đó tr v đ nh xu t phát”. ộ ầ

ố ỗ ỉ ấ

ở ề ỉ

c nhà toán h c Hamilton đ a

ầ

ượ

ọ

Bài toán n y đ ra vào năm 1859

Lý thuy t đ th - ch

68 ế ồ ị

ươ

ng 3 - Nguy n Thanh S n ễ

ơ

Đ NH NGHĨA

Ị

ồ ị

ướ

ng G(X, E) Đ th vô h DÂY CHUY N HAMILTON: Ề

dây chuy n đi qua t ề

ấ

ỉ

ủ

ộ ầ

ồ ị ố ỉ

ề ầ

ủ

c các đ nh c a đ th m i đ nh đúng m t l n. ồ ị ỗ ỉ ả CHU TRÌNH HAMILTON: dây chuy n Hamilton và m t c nh trong đ th n i đ nh đ u c a dây chuy n v i đ nh cu i c a nó.

ố ủ

ớ ỉ

Đ TH HAMILTON:

đ th có ch a m t chu trình

ồ ị

ứ

ộ

ộ ạ ề Ồ Ị Hamilton.