Báo cáo Thực tập: lý thuyết đồ thị trong toán học

Lời Mở Đầu Lý thuyết đồ thị là một lĩnh vực đã có từ lâu và có nhiều ứng dụng hiện đại. Những tư tưởng cơ bản của lý thuyết đồ thị được đề xuất vào những năm đầu của thế kỷ 18 bởi nhà toán học lỗi lạc người Thụy Sỹ Lenhard Euler. Đồ thị được sử dụng để giải các bài toán trong nhiều lĩnh lực khác nhau . Chẳng hạn , đồ thị có thể sử để xác định mạch vòng trong vấn đề giải tích mạch điện. Đồ thị có trọng số trên các cạnh có thể sử dụng để giải các bài toán như: Tìm đường đi ngắn nhất giữa hai thành phố trong mạnh giao thông. Chúng ta cũng còn sử dụng đồ thị để giải các bài toán về lập lịch , thời khoa biểu… §Æc biÖt trong kho¶ng vµi m­¬i n¨m trë l¹i ®©y, cïng víi sù ra ®êi cña m¸y tÝnh ®iÖn tö vµ sù ph¸t triÓn nhanh chãng cña tin häc, lÝ thuyÕn ®å thÞ cµng ®­îc quan t©m ®Õn nhiÒu h¬n. C¸c thuËt to¸n trªn ®å thÞ ®· cã nhiÒu øng dông trong nhiÒu lÜnh vùc kh¸c nhau nh­: M¹ng m¸y tÝnh, LÝ thuyÕt m·, Tèi ­u ho¸…. Trong ph¹m vi đề tài nµy do thời gian có hạn chúng em chØ nghiªn cøu vÒ mét sè bµi to¸n về đường đi trong lÝ thuyÕt ®å thÞ nh­: Bµi to¸n t×m chu tr×nh Euler, Bµi to¸n t×m ®­êng ®i ng¾n nhÊt , ThuËt to¸n Dijkstral. Chúng em rất mong được sự đóng góp ý kiến của thầy cô và các bạn. Chóng em ®Æc biÖt bµy tá lßng biÕt ¬n ch©n thµnh tíi thÇy gi¸o, Tiến sĩ: Nguyễn Trung Hòa, ng­êi thÇy ®· t¹o mäi ®iÒu kiÖn vµ lu«n gióp ®ì, h­íng dÉn chóng em tËn t×nh ®Ó chóng em hoµn thµnh tèt ®Ò tµi nµy. Nhóm sinh viên thực hiện: Lê Thị Thu Hiền Nguyễn Thị Thảo Trịnh Thị Thủy Nguyễn Trọng Tài Phần I: Các khái niệm cơ bản về lý thuyết đồ thị Định nghĩa: Là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Được mô tả hình thức: G = (V, E) V gọi là tập các đỉnh (Vertices) và E gọi là tập các cạnh (Edges). Có thể coi E là tập các cặp (u, v), với u và v là hai đỉnh của V. Có thể phân loại đồ thị theo đặc tính và số lượng của tập các cạnh E: Cho đồ thị G = (V, E). Định nghĩa một cách hình thức 1. G được gọi là đơn đồ thị nếu giữa hai đỉnh u, v của V có nhiều nhất là 1 cạnh trong E nối từ u tới v. 2. G được gọi là đa đồ thị nếu giữa hai đỉnh u, v của V có thể có nhiều hơn 1 cạnh trong E nối từ u tới v (Hiển nhiên đơn đồ thị cũng là đa đồ thị). 3. G được gọi là đồ thị vô hướng nếu các cạnh trong E là không định hướng, tức là cạnh nối hai đỉnh u, v bất kỳ cũng là cạnh nối hai đỉnh v, u. Hay nói cách khác, tập E gồm các cặp (u, v) không tính thứ tự. (u, v)≡(v, u) 4. G được gọi là đồ thị có hướng nếu các cạnh trong E là có định hướng, có thể có cạnh nối từ đỉnh u tới đỉnh v nhưng chưa chắc đã có cạnh nối từ đỉnh v tới đỉnh u. Hay nói cách khác, tập E gồm các cặp (u, v) có tính thứ tự: (u, v) ≠ (v, u). Trong đồ thị có hướng, các cạnh được gọi là các cung. Đồ thị vô hướng cũng có thể coi là đồ thị có hướng nếu như ta coi cạnh nối hai đỉnh u, v bất kỳ tương đương với hai cung (u, v) và (v, u). B A E D C Hình 1.2: Đồ thị có hướng Hình 1.1: Đồ thị vô hướng a — e — c — d — g — f — b — Ví dụ : Rất nhiều bài toán có thể mô hình hoá bằng đồ thị và giải quyết bằng các thuật toán trên đồ thị. Ví dụ: Xếp lịch thi đấu là một đồ thị vô hướng với mỗi đội là đỉnh, hai đội thi đấu với nhau là cạnh. Mạng giao thông là một đa đồ thị có hướng với nút giao thông là đỉnh, đường đi giữa hai nút là cung. Tương tự việc thiết kế mạng máy tính, mạng viễn thông có thể đưa về bài toán đồ thị Các khái niệm 1 . Các khái niệm cơ bản Khuyên: cạnh (cung) e gọi là khuyên nếu e có dạng (v,v). Cạnh (cung) lặp: là hai cạnh (cung) cùng tương ứng với một cặp đỉnh. Đỉnh kề: nếu (u,v) là cạnh (hoặc cung) của đồ thị thì v gọi là kề của u. Trong đồ thị vô hướng nếu v kề u thì u cũng kề v, nhưng trong đồ thị có hướng thì không chắc. Cạnh liên thuộc: Trong đồ thị vô hướng, cạnh e=(u,v) gọi là cạnh liên thuộc với đỉnh u và liên thuộc với đỉnh v. Bậc của đỉnh: Trong đồ thị vô hướng, số cạnh liên thuộc với v gọi là bậc của đỉnh v, kí hiệu là deg(v). Ví dụ: Xét đồ thị hình 1,deg(a)=1, deg(b)=deg(c)=4, deg(d)=1, deg(e)=deg(f)=3, deg(g)=0 Đỉnh cô lập, đỉnh treo: Trong đồ thị vô hướng, đỉnh bậc 0 gọi là đỉnh cô lập , đỉnh bậc 1 gọi là đỉnh treo. Ví dụ: Xét đồ thị hình 1.1. Ta có a là đỉnh treo, g là đỉnh cô lập Cung vào, ra: Trong đồ thị có hướng, cung e=(u,v) gọi là cung ra khỏi u và là cung vào v. Bán bậc của đỉnh: Trong đồ thị có hướng, số cung vào v gọi là bán bậc vào của đỉnh v, kí hiệu là: deg-(v), số cung ra khỏi v gọi là bán bậc ra của đỉnh v, kí hiệu là: deg+(v) Ví dụ: Xét đồ thị hình 1.1, deg-(A)=2, deg-(B)=3, deg-(C)=1, deg-(D)=2, deg-(E)=2 deg+(A)=3, deg+(B)=2, deg+(C)=2, deg+(D)=2, deg+(E)=1 Định lý 1: Trong đồ thị vô hướng thì tổng bậc của tất cả các đỉnh bằng 2 lần số cạnh. = 2m (m là số cạnh) Chứng minh: Mỗi cạnh e=(u,v) được tính một lần trong deg(u) và một lần trong deg(v) nên trong tổng bậc của các đỉnh, mỗi cạnh được tính hai lần, mà có m cạnh nên suy ra tổng bậc bằng 2m. Hệ quả: Trong đồ thị vô hướng, số đỉnh có bậc là số lẻ là một số chẵn Chứng minh: Gọi O là tập các đỉnh có bậc là số lẻ, và U là tập các đỉnh có bậc là số chẵn. Ta có: = + = 2m Do vU, deg(v) chẵn nên chẵn Do vO, deg(v) lẻ mà tổng chẵn, nên tổng này phải gồm một số chẵn các số hạng số đỉnh có bậc là số lẻ là một số chẵn (đpcm). Định lý 2: Trong đồ thị có hướng, tổng bán bậc ra của tất cả các đỉnh bằng tổng bán bậc vào của tất cả các đỉnh và bằng số cạnh của đồ thị = = m (m là số cạnh) Chứng minh: Hiển nhiên vì mỗi cung đều ra ở một đỉnh và vào ở một đỉnh khác. 2. Cách biểu diễn đồ thị trong máy tính Ma trận kề, ma trận trọng số Xét đơn đồ thị G=(V,E) với V là tập các đỉnh , E là tập các cạnh. Ma trận kề: Ma trận A={ai,j : i,j=1, 2,. . . ,n} với ai, j = 0, nếu (i,j) E và ai,j = 1 , nếu (i,j) E, i, j=1, 2,. . .,n. gọi là ma trận kề của đồ thị G. Ví dụ: Hình 2.1. Đồ thị vô hướng G và Đồ thị có hướng G1 1 2 3 4 5 6 1 0 1 1 0 1 0 2 1 0 1 0 1 0 3 1 1 0 1 0 0 4 0 0 1 0 1 1 5 1 1 0 1 0 1 6 0 0 0 1 1 0 1 2 3 4 5 6 1 0 1 1 0 0 0 2 0 0 0 0 0 0 3 0 1 0 1 0 0 4 0 0 0 0 0 0 5 0 0 0 1 0 1 6 0 0 0 0 1 0 Ma trận kề G Ma trận kề G1 * Tính chất của ma trận kề của đồ thị vô hướng: Tính đối xứng: a[i,j]=a[j,i], i,j=1,2,. . .,n. Tổng các phần từ trên dòng i (cột j) bằng bậc của đỉnh i (đỉnh j). Gọi aịjp , i,j=1, 2,. . . ,n là phần tử của ma trận Ap =A.A. . .A (p thừa số) Khi đó: aịjp , i,j=1, 2,. . . ,n là số đường đi khác nhau từ đỉnh i đến đỉnh j qua p-1 đỉnh trung gian. * Tính chất của ma trận kề của đồ thị có hướng: Không có tính đối xứng Tổng các phần từ trên dòng i bằng bán bậc ra của đỉnh i và tổng các phần từ trên cột j bằng bán bậc vào của đỉnh j. Giống tính chất 3 của vô hướng * Ma trận kề của đa đồ thị: a[i,j]=số cạnh (cung) nối hai đỉnh i, j. Ma trận trọng số: Đồ thị có trọng số là đồ thị mà mỗi cạnh (i,j) có một giá trị c(i,j) gọi là trọng số của cạnh. Để biểu diễn đồ thị ta sử dụng ma trận trọng số C= {c[i,j], i,j=1, 2,. . .,n} với      c[i,j]=c(i,j) nếu (i,j) E và  c[i,j]= nếu (i,j) E trong đó số có thể được đặt bằng một trong các giá trị sau: 0, + , - . Ưu điểm lớn nhất của phương pháp biểu diễn đồ thị bằng ma trận kề (hoặc ma trận trọng số) là để trả lời câu hỏi: Hai đỉnh u,v có kề nhau trên đồ thị hay không, chúng ta chỉ phải thực hiện một phép so sánh. nhược điểm lớn nhất của phương pháp này là: không phụ thuộc vào số cạnh của đồ thị, ta luôn phải sử dụng n2 đơn vị bộ nhớ để lưu trữ ma trận kề của nó. Ma trận liên thuộc đỉnh-cạnh Xét G=(V, E) là đơn đồ thị có hướng. Ma trận liên thuộc đỉnh-cạnh có dạng: 1, nếu i là đỉnh đầu của cung ej -1, nếu i là đỉnh cuối của cung ej 0, nếu i không là đầu mút của cung ej aij = 1 2 4 6 5 3 Ví dụ: Hinh 2.2 (1,2) (1,3) (2,3) (2,4) (3,5) (4,5) (4,6) (5,2) (5,6) 1 1 1 0 0 0 0 0 0 0 2 -1 0 1 1 0 0 0 -1 0 3 0 -1 -1 0 1 0 0 0 0 A= 4 0 0 0 -1 0 1 1 0 0 5 0 0 0 0 -1 0 0 1 1 6 0 0 0 0 0 0 -1 0 -1 Danh sách cạnh (cung) Trong trường hợp đồ thị thưa (đồ thị có số cạnh m thoả mãn bất dẳng thức: m<6n) người ta thường dùng cách biểu diễn đồ thị dưới dạng danh sách cạnh. Chúng ta sẽ lưu trữ danh sách tất cả các cạnh (cung) của đồ thị. Một cạnh (cung) e=(x,y) của đồ thị sẽ tương ứng với hai biến Dau[e], Cuoi[e]. Như vậy, để lưu trữ đồ thị ta cần sử dụng 2m đơn vị bộ nhớ. Nhược điểm của cách biểu diễn này tìm các đỉnh kề với một đỉnh cho trước chúng ta phải làm cỡ m phép so sánh (khi duyệt qua danh sách tất cả các cạnh của đồ thị). Trong trường hợp đồ thị có trọng số ta cần thêm m đơn vị bộ nhớ để lưu trữ trọng số của các cạnh. Ví dụ: D/s cạnh (cung) của G (G1) ( hình 1) Đầu Cuối Đầu Cuối 1 2 1 2 1 3 1 3 1 5 3 2 2 3 3 4 2 5 5 4 3 4 5 6 4 5 6 5 4 6 5 6 D/s cạnh của G          D/s cung của G1 Danh sách kề Với mỗi đỉnh v, ta lưu trữ danh sách các đỉnh kề với v: Ke(v)={u V: (v,u)E} Ví dụ: - Danh sách kề của G Đỉnh đầu - Danh sách kề của hình G1 Đỉnh đầu Trong cách biểu diễn này chúng ta cần phải sử dụng cỡ m+n đơn vị bộ nhớ. III. Đường đi trong đồ thị 1 Đường đi XÐt ®å thÞ G = víi - TËp ®Ønh V = {v1,v2,...,vn} - TËp c¹nh E = {e1,e2,...,em} TËp hîp c¸c ®Ønh kÒ nhau tõ vi ®Õn vj ®­îc gäi lµ 1 ®­êng ®i, kÝ hiÖu vivi1vi2 ... vj º vieivi1ei1vi2ei2 ... ejvj Trong ®ã c¸c c¹nh, c¸c ®Ønh trong ®­êng ®i cã thÓ lÆp l¹i 2 Chu tr×nh XÐt mét ®­êng ®i tõ vi - vj. NÕu vi º vj th× ®­êng ®i nµy ®­îc gäi lµ mét chu tr×nh. Nh­ vËy chu tr×nh lµ mét ®­êng ®i cã ®Ønh xuÊt ph¸t vµ ®Ønh kÕt thóc trïng nhau. Chó ý r»ng ®­êng ®i trong ®å thÞ cã h­íng kh«ng ®­îc ®i ng­îc chiÒu mòi tªn - §­êng ®i (chu tr×nh) ®­îc gäi lµ ®¬n nÕu nã ®i qua mçi c¹nh kh«ng qu¸ mét lÇn. - §­êng ®i (chu tr×nh) ®­îc gäi lµ s¬ cÊp nÕu nã ®i qua mçi ®Ønh ®óng mét lÇn 3 §­êng ®i vµ chu tr×nh cña ®å thÞ v« h­íng: §­êng ®i ®é dµi n tõ ®Ønh u ®Õn ®Ønh v, trong ®ã n lµ sè nguyªn d­¬ng, trªn ®å thÞ v« h­íng G=(V,E) lµ d·y: x, x, …, xn-1, xn. Trong ®ã: u=x0, v=xn, (xi,xi+1) thuéc E. i=0,1,2,…, n-1. §­êng ®i trªn cßn ®­îc biÓu diÔn d­íi d¹ng c¹nh: (x0,x1), (x1,x2), …,(xn-1,xn). §Ønh u ®­îc gäi lµ ®Ønh ®Çu, cßn ®Ønh v ®­îc gäi lµ ®Ønh cuèi cña ®­êng ®i. §­êng ®i cã ®Ønh ®Çu trïng víi ®Ønh cuèi (tøc lµ u trïng víi v) ®­îc gäi lµ chu tr×nh. §­êng ®i hay chu tr×nh ®­îc gäi lµ ®¬n nÕu kh«ng cã c¹nh nµo bÞ lÆp l¹i. A B C D E Hình2.3 Kh¸i niÖm ®­êng ®i vµ chu tr×nh trªn ®å thÞ cã h­íng ®­îc ®Þnh nghÜa hoµn toµn t­¬ng tù nh­ tr­êng hîp ®å thÞ v« h­íng, chØ kh¸c lµ ta cã chó ý ®Õn h­íng trªn c¸c cung. 4. §­êng ®i vµ chu tr×nh cña ®å thÞ cã h­íng: §­êng ®i cã ®é dµi n tõ ®Ønh u ®Õn ®Ønh v, trong ®ã n lµ sè nguyªn d­¬ng, trªn ®å thÞ cã h­íng lµ d·y: x, x, …, xn-1, xn. Trong ®ã: u=x0, v=xn, (xi,xi+1) thuéc E. i=0,1,2,…, n-1. §­êng ®i trªn cßn ®­îc biÓu diÔn d­íi d¹ng c¸c cung: (x0,x1), (x1,x2), …,(xn-1,xn). §Ønh u ®­îc gäi lµ ®Ønh ®Çu, cßn ®Ønh v ®­îc gäi lµ ®Ønh cuèi cña ®­êng ®i. §­êng ®i cã ®Ønh ®Çu trïng víi ®Ønh cuèi (tøc lµ u trïng víi v) ®­îc gäi lµ chu tr×nh. §­êng ®i hay chu tr×nh ®­îc gäi lµ ®¬n nÕu kh«ng cã c¹nh nµo bÞ lÆp l¹i. 5. §å thÞ liªn th«ng Cho ®å thÞ G = . Hai ®Ønh ph©n biÖt u,v Î V ®­îc gäi lµ liªn th«ng nÕu tån t¹i mét ®­êng ®i nèi c¸c ®Ønh u,v víi nhau. §å thÞ G ®­îc gäi lµ liªn th«ng nÕu víi hai ®Ønh ph©n biÖt bÊt kú trong ®å thÞ ®Òu lµ liªn th«ng. VÝ dô nh­ h×nh 2.3 lµ mét ®å thÞ liªn th«ng v× lu«n cã ®­êng ®i nèi hai ®Ønh bÊt kú cña ®å thÞ, cßn ®å thÞ nh­ h×nh 2 lµ kh«ng liªn th«ng v× kh«ng cã ®­êng ®i tõ A tíi D hoÆc tõ D tíi F v.v.. XÐt 2 ®å thÞ liªn th«ng G1 = vµ G2 = Trong ®ã: V1 Ç V2 = Æ vµ E1 Ç E2 = Æ Khi ®ã: V = V1 È V2 E = E1 È E2 Th× G = lµ ®å thÞ cã 2 thµnh phÇn liªn th«ng G1, G2. A B F C E D H×nh 2.4 VÝ dô nh­ ®å thÞ trong h×nh 2.4 cã ba thµnh phÇn liªn th«ng sau: G1 = víi V1= {A,B,C} vµ E1 = {AB, AC, CB} G2 = víi V2= {D, E} vµ E2 = {DE} G3 = víi V3= {F} vµ U3 = Æ Cho ®å thÞ cã h­íng G = - G ®­îc gäi lµ ®å thÞ liªn th«ng yÕu nÕu ®å thÞ v« h­íng t­¬ng øng víi nã lµ liªn th«ng - G lµ liªn th«ng mét chiÒu nÕu víi hai ®Ønh u,v kh¸c nhau bÊt kú cña G lu«n cã ®­êng ®i u - v hoÆc ®­êng ®i v - u. A B C D A B C D A B C D - G lµ liªn th«ng m¹nh (liªn th«ng 2 chiÒu) nÕu hai ®Ønh u,v kh¸c nhau bÊt kú cña G ®Òu cã ®­êng ®i u - v vµ ®­êng ®i v - u. H1 H2 H3 H×nh 2.5 Trên h×nh 2.5 ®å thÞ H1 lµ liªn th«ng m¹nh, gi¶ sö cÆp ®Ønh (A,C) ta cã chiÒu ®i tõ C tíi A, vµ ®ång thêi còng cã chiÒu ®i tõ A tíi C, vµ bÊt kú c¸c cÆp ®Ønh kh¸c còng t­¬ng tù nh­ vËy. H2 lµ liªn th«ng mét chiÒu v× xÐt cÆp ®Ønh (A,D) cã chiÒu ®i tõ D tíi A nh­ng kh«ng cã chiÒu ®i tõ A tíi D. H3 lµ liªn th«ng yÕu v× tån t¹i cÆp ®Ønh (B,C) kh«ng cã chiÒu ®i B - C còng kh«ng cã chiÒu ®i C - B, nh­ng ®å thÞ v« h­íng t­¬ng øng lµ liªn th«ng 6. Đường đi Euler và chu trinh Euler Đường đi Euler: Một đường đi trong đồ thị được gọi là đường đi euler nếu nó đi qua tất cả các cạnh hoặc cung của đồ thị với mỗi cạnh hoặc cung đi qua đúng một lần. Chu trình Euler: Một chu trình được gọi là chu trình Euler nếu nó là một đường đi Euler Đường đi Euler là một đường đi đơn chứa tất cả các cạnh hoặc cung của đồ thị. Còn chu trình Euler là một chu trinh đơn chứa tất cả các cạnh hoặc cung của đồ thị. Một đồ thị có đường đi Euler thì được gọi là đồ thị nửa Euler.Còn đồ thị có chu trình Euler thì gọi là đồ thị Euler. B C B A C D E A E D F Hình 2.6 Hinh 2.7 Chọn đỉnh khởi đầu là A ,trên hình 2.6 có chu trình Euler là: A->B ->C->A->F->C->D->E->A - Chọn đỉnh đầu là A , hình 2.7 có chu trình nửa Euler là: A->E->D->A->B->D->C->B Định lý 1: a, Điều kiện cần và đủ để một đồ thị vô hướng liên thông có chu trình Euler là mọi đỉnh của nó đều có bậc chẵn. b, Điều kiện cần và đủ để đồ thị có hướng liên thông mạnh có chu trình Euler là tại mọi đỉnh của nó thì bậc vào bằng bậc ra có nghĩa là: Deg -(v)=Deg +(v) vV; Định lý 2 Cần và đủ để 1 đồ thị có đường đi Euler nhưng không có chu trình Euler là đồ thị đó có đúng 2 đỉnh bậc lẻ. 7. Bài toán đường đi ngắn nhất Trong lý thuyết đồ thị, bài toán đường đi ngắn nhất nguồn đơn là bài toán tìm một đường đi giữa hai đỉnh sao cho tổng các trọng số của các cạnh tạo nên đường đi đó là nhỏ nhất. Định nghĩa một cách hình thức, cho trước một đồ thị có trọng số (nghĩa là một tập đỉnh V, một tập cạnh E, và một hàm trong số có giá trị thực f : E → R), cho trước một đỉnh v thuộc V, tìm một đường đi P từ v tới mỗi đỉnh v' thuộc V sao cho: là nhỏ nhất trong tất cả các đường nối từ v tới v' . Bài toán đường đi ngắn nhất giữa mọi cặp đỉnh là một bài toán tương tự, trong đó ta phải tìm các đường đi ngắn nhất cho mọi cặp đỉnh v và v' . Thuật toán Dijkstra, mang tên của nhà khoa học máy tính người Hà Lan Edsger Dijkstra, là một thuật toán giải quyết bài toán đường đi ngắn nhất nguồn đơn trong một đồ thị có hướng không có cạnh mang trọng số âm. Bài toán: Cho một đồ thị có hướng G=(V,E), một hàm trọng số w: E → [0, ∞) và một đỉnh nguồn s. Cần tính toán được đường đi ngắn nhất từ đỉnh nguồn s đến mỗi đỉnh của đồ thị. Ví dụ: Chúng ta dùng các đỉnh của đồ thị để mô hình các thành phố và các cạnh để mô hình các đường nối giữa chúng. Khi đó trọng số các cạnh có thể xem như độ dài của các con đường (và do đó là không âm). Chúng ta cần vận chuyển từ thành phố s đến thành phố t. Thuật toán Dijkstra sẽ giúp chỉ ra đường đi ngắn nhất chúng ta có thể đi. Trọng số không âm của các cạnh của đồ thị mang tính tổng quát hơn khoảng cách hình học giữa hai đỉnh đầu mút của chúng. Ví dụ: Với 3 đỉnh A, B, C đường đi A-B-C có thể ngắn hơn so với đường đi trực tiếp A-C. Thuật toán Dijkstra có thể mô tả như sau: - Ta quản lý một tập hợp động S. Ban đầu S={s}. - Với mỗi đỉnh v, chúng ta quản lý một nhãn d[v] là độ dài bé nhất trong các đường đi từ nguồn s đến một đỉnh u nào đó thuộc S, rồi đi theo cạnh nối u-v. - Trong các đỉnh ngoài S, chúng ta chọn đỉnh u có nhãn d[u] bé nhất, bổ sung vào tập S. Tập S được mở rộng thêm một đỉnh, khi đó chúng ta cần cập nhật lại các nhãn d cho phù hợp với định nghĩa. - Thuật toán kết thúc khi toàn bộ các đỉnh đã nằm trong tập S, hoặc nếu chỉ cần tìm đường đi ngắn nhất đến một đỉnh đích t, thì chúng ta dừng lại khi đỉnh t được bổ sung vào tập S. Tính chất không âm của trọng số các cạnh liên quan chặt chẽ đến tính đúng đắn của thuật toán. Khi chứng minh tính đúng đắn của thuật toán, chúng ta phải dùng đến tính chất này. Phần 2: Cài Đặt Thuật Toán I. KiÓm tra tÝnh liªn th«ng: Mét ®å thÞ ®­îc gäi lµ liªn th«ng nÕu mäi cÆp ®Ønh cña nã ®Òu ®­îc nèi víi nhau bëi mét ®­êng. Mét ®å thÞ con liªn th«ng cña ®å thÞ mµ nã kh«ng ®­îc chøa trong mét ®å thÞ con liªn th«ng kh¸c, gäi lµ thµnh phÇn liªn th«ng. Bµi to¸n: Bµi to¸n ®Æt ra lµ cho mét ®å thÞ v« h­íng G=(V,E), h·y cho biÕt G cã bao nhiªu thµnh phÇn liªn th«ng, vµ mçi thµnh phÇn liªn th«ng cña nã gåm nh÷ng ®Ønh nµo. ThuËt to¸n kiÓm tra tÝnh liªn th«ng: XÐt ®å thÞ G(V,E): B­íc 1: LÊy ®Ønh bÊt kú I cña G, ®Æt T={ I } vµ gäi I lµ ®Ønh gèc. B­íc 2: §­a vµo T tÊt c¶ nh÷ng ®Ønh j sao cho c¹nh ij thuéc E ( tøc c¹nh ij lµ mét c¹nh cña G). B­íc 3: NÕu T chøa mäi ®Ønh cña G( nghÜa lµ ®iÒu kiÖn dõng l¹i ë b­íc 2 tho¶ m·n), th× ®å thÞ G liªn th«ng. B­íc 4: NÕu T kh«ng chøa mäi ®Ønh cña G th× ®å thÞ G kh«ng liªn th«ng. Khi ®ã, T lµ mét thµnh phÇn cña liªn th«ng. B­íc 5: LÊy ®Ønh v thuéc G nh­ng kh«ng thuéc T, trë vÒ b­íc 2. II. T×m chu tr×nh Euler: §Þnh nghÜa chu tr×nh Euler : Gi¶ sö G lµ ®å thÞ v« h­íng. Mét chu tr×nh w trong ®å thÞ G ®­îc gäi lµ chu tr×nh Euler nÕu nã ®i qua tÊt c¶ c¸c c¹nh cña G vµ ®i qua mçi c¹nh ®óng mét lÇn. 1. Nªu bµi to¸n : Cho ®å thÞ G=. H·y t×m chu tr×nh Euler cña ®å thÞ G nÕu cã. 2. Nªu thuËt to¸n : Cho ®¬n ®å thÞ G víi ma trËn kÒ a[i,j]. B­íc 1: KiÓm tra xem bËc cña mçi ®Ønh cã lµ sè ch½n hay kh«ng, tøc lµ kiÓm tra xem tæng c¸c phÇn tö trªn mçi dßng ( hoÆc mçi cét) cã lµ sè ch½n hay kh«ng? B­íc 2: NÕu tån t¹i mét ®Ønh cã bËc lÎ (hoÆc mét dßng hay mét cét cña ma tr©n cã tæng c¸c phÇn tö cña nã lµ lÎ), ta kÕt luËn r»ng ®å thÞ kh«ng cã chu tr×nh Euler. B­íc 3: NÕu mäi ®Ønh cña ®å thÞ ®Òu cã bËc ch½n th× ®å thÞ cã chu tr×nh Euler. B­íc 4: Khi ®ã, xuÊt ph¸t tõ mét ®Ønh bÊt kú, ta ®i mét c¸ch ngÉu nhiªn theo c¸c c¹nh cña ®å thÞ theo quy t¾c mçi cạnh của ®å thÞ chØ ®i cã mét lÇn. Khi dõng l¹i ta ®­îc mét chu tr×nh. B­íc 5: KiÓm tra xem cã cßn ®Ønh nµo cã c¹nh liªn thuéc víi nã mµ ch­a ®­îc ®i qua hay kh«ng? NÕu cã, ta lÊy ®Ønh ®ã lµm xuÊt ph¸t (đỉnh dính), ®i theo chu tr×nh cò, hoµn tÊt chu tr×nh t¹i ®Ønh nµy råi ®i theo c¹nh ch­a ®­îc ®i qua. Trë vÒ b­íc4. B­íc 6: NÕu kh«ng cã ®Ønh nµo cßn cã c¹nh liªn thuéc víi nã mµ ch­a ®­îc ®i qua, thì ta ghép chu trình với chu trình con tại đỉnh dính và coi chu trình mới thu được bằng chu trình. Ta kết luận chu trình tim được là chu trình Euler. 3.Ví dụ minh họa Hinh 3:Chu tr×nh Euler 6 1 2 4 3 5 Ma trËn kÒ t­¬ng øng: 4. Cài đặt thuật toán uses crt; Type imatr=array[1..20,1..20] of byte; bvtor=array[-1..20] of byte; var a,c, w1,w:imatr; l:byte; ct,ctc:bvtor; queue,chuaxet,truoc:array[1..20] of byte; i,j,n,solt,k,s,t:integer; ch:char; {********************************************************} procedure nhapsolieu; begin write('Cho so dinh cua do thi:');readln(n); writeln('Nhap so lieu ma tran ke:'); for i:=1 to n do begin for j:=i+1 to n do begin write('a[',i,',',j,']='); readln(a[i,j]); a[j,i]:=a[i,j]; end; a[i,i]:=0; writeln; end; end; {*********************************************************} procedure doctep; var f:text; fn:string; begin write('Cho ten file du lieu:');readln(fn); assign(F,fn); reset(F); readln(f,n); writeln('Nhap so lieu ma tran ke:'); for i:=1 to n do for j:=1 to n do read(f,a[i,j]); close(f); end; {*******************************************************} procedure Insolieu; begin writeln('Ma tran ke:'); for i:=1 to n do begin for j:=1 to n do write(a[i,j]:3); writeln; end; end; {******************** chu trinh eu