Luận văn Một số vấn đề ứng dụng đồ thị trong Tin học

Ch­¬ng 1 mét sè vÊn ®Ò c¬ b¶n cña ®å thÞ I. C¸c ®Þnh nghÜa ®å thÞ 1. §Þnh nghÜa ®å thÞ §å thÞ lµ mét cÊu tróc rêi r¹c bao gåm c¸c ®Ønh vµ c¸c c¹nh nèi c¸c ®Ønh nµy, c¸c lo¹i ®å thÞ kh¸c nhau ®­îc ph©n biÖt bëi kiÓu vµ sè l­îng c¹nh nèi hai ®Ønh nµo ®ã cña ®å thÞ. Gi¶ sö X lµ tËp h÷u h¹n, kh«ng rçng c¸c phÇn tö nµo ®ã vµ U Í X´X. Bé G = ®­îc gäi lµ ®å thÞ h÷u h¹n. Mçi phÇn tö xÎX gäi lµ mét ®Ønh vµ mçi phÇn tö u = (x,y) Î U gäi lµ mét c¹nh cña ®å thÞ G = . XÐt mét c¹nh u Î U khi ®ã tån t¹i 2 ®Ønh x, y Î X sao cho u = (x, y), ta nãi r»ng x nèi víi y hoÆc x vµ y thuéc u. x y u - NÕu c¹nh u = (x, y) mµ x vµ y lµ hai ®Ønh ph©n biÖt th× ta nãi x, y lµ hai ®Ønh kÒ nhau. - NÕu u = (x, x) th× u lµ c¹nh cã hai ®Ønh trïng nhau ta gäi ®ã lµ mét khuyªn. - NÕu u = (x, y) mµ x,y lµ cÆp ®Ønh cã ph©n biÖt thø tù hay cã h­íng tõ x ®Õn y th× u lµ mét cung, khi ®ã x lµ gèc cßn y lµ ngän hoÆc x lµ ®Ønh ra, y lµ ®Ønh vµo. - Khi gi÷a cÆp ®Ønh (x, y) cã nhiÒu h¬n mét c¹nh th× ta nãi nh÷ng c¹nh cïng cÆp ®Ønh lµ nh÷ng c¹nh song song hay lµ c¹nh béi y x y x y a) b) c) a. T¹i ®Ønh y cã mét khuyªn b. Mét cung cã h­íng tõ x sang y c. CÆp ®Ønh (x, y) cã 2 c¹nh song song H×nh 1.1 Trong thùc tÕ ta cã thÓ gÆp nhiÒu vÊn ®Ò mµ cã thÓ dïng m« h×nh ®å thÞ ®Ó biÓu diÔn, nh­ s¬ ®å mét m¹ng m¸y tÝnh, s¬ ®å m¹ng l­íi giao th«ng, s¬ ®å thi c«ng mét c«ng tr×nh. VÝ dô: XÐt mét m¹ng m¸y tÝnh, cã thÓ biÓu diÔn m¹ng nµy b»ng mét m« h×nh ®å thÞ, trong ®ã mçi m¸y lµ mét ®Ønh, gi÷a c¸c m¸y ®­îc nèi víi nhau b»ng c¸c d©y truyÒn, chóng t­¬ng øng lµ c¸c c¹nh cña ®å thÞ. Mét m« h×nh m¹ng m¸y tÝnh nh­ h×nh 1.2 trong ®ã cã c¸c m¸y tÝnh A, B, C, D t­¬ng øng lµ c¸c ®Ønh, gi÷a 2 m¸y ®­îc nèi trùc tiÕp víi nhau th× t­¬ng øng víi 1 cÆp ®Ønh kÒ nhau. A B C D H×nh 1.2 VÝ dô vÒ mét ®å thÞ 2. §å thÞ ®¬n §å thÞ G = ®­îc gäi lµ ®å thÞ ®¬n nÕu gi÷a hai ®Ønh bÊt kú ®­îc nèi víi nhau bëi kh«ng qu¸ mét c¹nh (cung), tøc lµ ®å thÞ kh«ng cã c¹nh béi, kh«ng cã khuyªn. H×nh 1.2 lµ mét vÝ dô vÒ ®å thÞ ®¬n 3. §a ®å thÞ §å thÞ G = ®­îc gäi lµ ®a ®å thÞ nÕu nã cã Ýt nhÊt mét cÆp ®Ønh ®­îc nèi víi nhau bëi hai c¹nh (hai cung) trë lªn. 4. Gi¶ ®å thÞ Lµ ®å thÞ cã Ýt nhÊt mét khuyªn, cã thÓ chøa c¹nh béi, c¹nh ®¬n. Tãm l¹i ®©y lµ lo¹i ®å thÞ tæng qu¸t nhÊt. A B C D A B C D a) b) H×nh 1.3 a. §a ®å thÞ b. Gi¶ ®å thÞ II. C¸c lo¹i ®å thÞ 1. §å thÞ v« h­íng §å thÞ G= ®­îc gäi lµ ®å thÞ v« h­íng nÕu tÊt c¶ c¸c c¹nh e Î U mµ cÆp ®Ønh thuéc nã e = (x,y) Î X kh«ng ph©n biÖt thø tù. §å thÞ v« h­íng lµ ®å thÞ kh«ng cã bÊt kú mét cung nµo. VÝ dô: nh­ h×nh 1.3.a lµ biÓu diÔn cña mét ®å thÞ v« h­íng. 2. §å thÞ cã h­íng §å thÞ G = ®­îc gäi lµ ®å thÞ cã h­íng nÕu tÊt c¶ c¸c c¹nh e Î U mµ cÆp ®Ønh thuéc nã e = (x, y) Î X cã ph©n biÖt thø tù. §å thÞ cã h­íng lµ ®å thÞ mµ mäi e = (x, y) Î X ®Òu lµ cung. A B C H×nh 2.1 §å thÞ cã h­íng 3. §å thÞ hçn hîp §å thÞ G= võa cã c¹nh v« h­íng, võa cã c¹nh cã h­íng th× nã ®­îc gäi lµ ®å thÞ hçn hîp, lo¹i ®å thÞ nµy rÊt Ýt khi ®­îc dïng tíi. Chó ý r»ng vÊn ®Ò ph©n chia ®å thÞ vµ c¸c thuËt ng÷ vÒ ®å thÞ chØ mang tÝnh t­¬ng ®èi, hiÖn nay vÉn cßn ch­a mang tÝnh thèng nhÊt chuÈn trªn nhiÒu tµi liÖu. III. Mét sè kh¸i niÖm vµ tÝnh chÊt c¬ b¶n cña ®å thÞ 1. BËc ®å thÞ 1.1 BËc ®å thÞ v« h­íng Cho ®å thÞ v« h­íng G = . XÐt 1 ®Ønh x Î X ®Æt m(x) lµ sè c¹nh thuéc ®Ønh x khi ®ã m(x) ®­îc gäi lµ bËc cña ®Ønh x. NÕu x cã mét khuyªn th× m(x) ®­îc céng thªm 2. x x m(x) = 3 m(x) = 2 - NÕu m(x) = 0 th× ®Ønh x ®­îc gäi lµ ®Ønh c« lËp - NÕu m(x) = 1 th× ®Ønh x ®­îc gäi lµ ®Ønh treo Ta ®Æt th× m(G) ®­îc gäi lµ bËc cña ®å thÞ v« h­íng G = 1.2 BËc ®å thÞ cã h­íng Cho ®å thÞ cã h­íng G= xÐt 1 ®Ønh x Î X, ta ký hiÖu m+(x) lµ sè c¸c cung vµo cña ®Ønh x, cßn m-(x) lµ sè c¸c cung ra khái x. Khi ®ã ta gäi m+(x) lµ bËc vµo cña ®Ønh x cßn m-(x) lµ bËc ra cña ®Ønh x. - NÕu m+(x) + m-(x) = 0 th× ®Ønh x ®­îc gäi ®Ønh lµ c« lËp - NÕu m+(x) + m-(x) = 1 th× ®Ønh x ®­îc gäi lµ ®Ønh treo Ta ®Æt Khi ®ã m(G) ®­îc gäi lµ bËc cña ®å thÞ cã h­íng G = . Trong ®å thÞ cã h­íng th× m+(x) = m-(x) = çU ç VÝ dô: - XÐt ®å thÞ v« h­íng nh­ trong h×nh 1.3.a ta cã: m(G) = m(A) + m(B) + m(C) + m(D) = 2 + 5 + 2 + 1 = 10 - XÐt ®å thÞ cã h­íng trong h×nh 2.1 ta cã: m(G) = [m+(A) + m+(B) + m+(C) ] + [m-(A) + m-(B) + m-(C)] = [1 + 2 + 1] + [2 + 1 +1] = 8 §Þnh lý: Cho ®å thÞ h÷u h¹n G = khi ®ã bËc cña ®å thÞ G b»ng 2 lÇn sè c¹nh cña ®å thÞ, tøc lµ m(G) = 2çU ç. Chøng minh: Ta thÊy mét c¹nh thuéc 2 ®Ønh, nÕu xo¸ mét c¹nh th× bËc cña G gi¶m ®i 2, nÕu xo¸ mét khuyªn u = (x, x) th× bËc cña G còng gi¶m ®i 2, cßn nÕu xo¸ hÕt c¹nh, hÕt khuyªn th× bËc cña ®å thÞ b»ng 0. Tõ ®ã suy ra ®Þnh lý. HÖ qu¶: Sè ®Ønh bËc lÎ cña ®å thÞ G = lµ mét sè ch½n Chøng minh: Gäi A vµ B t­¬ng øng lµ tËp ®Ønh bËc lÎ vµ tËp ®Ønh bËc ch½n cña ®å thÞ. Ta cã: Do vÕ tr¸i ch½n nªn tæng vÕ ph¶i còng lµ sè ch½n. Mµ tæng bËc cña c¸c ®Ønh bËc ch½n (xÎA) lµ sè ch½n nªn tæng bËc cña c¸c ®Ønh bËc lÎ (xÎB) ph¶i lµ sè ch½n, do tÊt c¶ c¸c sè h¹ng cña nã lµ sè lÎ, nªn tæng nµy ph¶i gåm mét sè ch½n c¸c sè h¹ng. V× vËy sè ®Ønh bËc lÎ ph¶i lµ sè ch½n. 2. ®­êng ®i vµ chu tr×nh 2.1 §­êng ®i XÐt ®å thÞ G = víi - TËp ®Ønh X = {x1,x2,...,xn} - TËp c¹nh U = {u1,u2,...,um} TËp hîp c¸c ®Ønh kÒ nhau tõ xi ®Õn xj ®­îc gäi lµ 1 ®­êng ®i, kÝ hiÖu xixi1xi2 ... xj º xiuixi1ui1xi2ui2 ... ujxj Trong ®ã c¸c c¹nh, c¸c ®Ønh trong ®­êng ®i cã thÓ lÆp l¹i §é dµi cña ®­êng ®i b»ng sè c¸c c¹nh (hoÆc cung) trong ®­êng ®i ®ã. *Chó ý r»ng trong ®å thÞ cã h­íng, trªn mét cung uv ch¼ng h¹n th× ®­êng ®i chØ cã thÓ ®i tõ gèc (u) ®Õn ngän (v) kh«ng thÓ ®i ng­îc l¹i. 2.2 Chu tr×nh XÐt mét ®­êng ®i tõ xi - xj. NÕu xi º xj 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 A B C D E H×nh 3.1 VÝ dô nh­ ë h×nh 3.1 ADBE lµ mét ®­êng ®i s¬ cÊp tõ A ®Õn E ®é dµi 3; ABCDBE lµ ®­êng ®i kh«ng s¬ cÊp ( qua B 2 lÇn) tõ A ®Õn E ®é dµi 5; ABDAB lµ mét ®­êng ®i kh«ng ®¬n (chøa c¹nh AB 2 lÇn) tõ A ®Õn B ®é dµi 4; ABDA Lµ 1 chu tr×nh ®¬n vµ s¬ cÊp ®é dµi 3; CC lµ ®­êng ®i ®é dµi 0. XÐt ®å thÞ cã h­íng nh­ h×nh 2.1 th× ABCB lµ mét ®­êng ®i ®é dµi 3; CBA kh«ng lµ mét ®­êng ®i v× kh«ng cã cung ®i tõ B ®Õn A. §Þnh lý: NÕu trong ®å thÞ G = c¸c ®Ønh ®Òu cã bËc kh«ng nhá h¬n 2 ( "x Î X | m(x) ³ 2 ) th× trong G tån t¹i Ýt nhÊt mét chu tr×nh. Chøng minh: XÐt tÊt c¶ c¸c ®­êng ®i ®¬n. V× ®å thÞ lµ h÷u h¹n cho nªn sè c¸c ®­êng ®i ®¬n lµ h÷u h¹n. Chän mét ®­êng ®i lµ dµi nhÊt nµo ®ã vÝ dô tõ xi1 ®Õn xij +1 (xem h×nh vÏ d­íi ®©y). Theo gi¶ thiÕt m(x) ³ 2 nªn tån t¹i Ýt nhÊt mét ®Ønh xi0 vµ mét c¹nh nèi ®Ønh xi1 vµ xi0. §Ønh xi0 thuéc mét trong c¸c ®Ønh trªn ®­êng ®i ®· chän ch¼ng h¹n xij v× ®­êng ®i lµ dµi nhÊt, nªn chøng tá tån t¹i mét chu tr×nh trong ®­êng ®i. xi0 xi1 xi2 xi3 xij xij+1 3. §å thÞ liªn th«ng Cho ®å thÞ G = . Hai ®Ønh ph©n biÖt x,y Î X ®­îc gäi lµ liªn th«ng nÕu tån t¹i mét ®­êng ®i nèi c¸c ®Ønh x, y 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 3.1 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 3.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 ®ã: X1 Ç X2 = Æ vµ U1 Ç U2 = Æ Khi ®ã: X = X1 È X2 U = U1 È U2 Th× G = lµ ®å thÞ cã 2 thµnh phÇn liªn th«ng G1, G2. A B F C E D H×nh 3.3 VÝ dô nh­ ®å thÞ trong h×nh 3.3 cã ba thµnh phÇn liªn th«ng sau: G1 = víi X1= {A,B,C} vµ U1 = {AB, AC, CB} G2 = víi X2= {D, E} vµ U2 = {DE} G3 = víi X3= {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 x,y kh¸c nhau bÊt kú cña G lu«n cã ®­êng ®i x - y hoÆc ®­êng ®i y - x. - G lµ liªn th«ng m¹nh (liªn th«ng 2 chiÒu) nÕu hai ®Ønh x,y kh¸c nhau bÊt kú cña G ®Òu cã ®­êng ®i x - y vµ ®­êng ®i y - x. A B C D A B C D A B C D H1 H2 H3 H×nh 3.4 ë h×nh 3.4 ®å 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. 4. §å thÞ con vµ ®å thÞ bé phËn Cho ®å thÞ G = - NÕu trong ®å thÞ ®ã ta bá ®i mét sè ®Ønh nµo ®ã vµ c¸c c¹nh xuÊt ph¸t tõ ®Ønh ®ã th× phÇn cßn l¹i cña ®å thÞ ®­îc gäi lµ ®å thÞ con cña ®å thÞ G ®· cho, hoÆc lµ nÕu D = lµ ®å thÞ con cña G = th× X' Í X vµ U' Í U - NÕu trong ®å thÞ G ta bá ®i mét sè c¹nh nh­ng gi÷ nguyªn c¸c ®Ønh th× phÇn cßn l¹i cña ®å thÞ ®­îc gäi lµ ®å thÞ bé phËn cña ®å thÞ G. IV. C¸c d¹ng biÓu diÔn cña ®å thÞ 1. BiÓu diÔn h×nh häc cña ®å thÞ §Ó cã c¸i nh×n trùc quan ta th­êng biÓu diÔn ®å thÞ b»ng h×nh häc, mét ®å thÞ cã thÓ biÓu diÔn trªn mét mÆt ph¼ng hoÆc trong kh«ng gian. Ph­¬ng ph¸p biÓu diÔn nh­ sau: BiÓu diÔn c¸c ®Ønh cña ®å thÞ b»ng c¸c ®iÓm (hay vßng trßn nhá, « vu«ng nhá) vµ nèi hai ®iÓm b»ng mét ®­êng (cong, th¼ng, mòi tªn) khi cÆp ®iÓm ®ã øng víi mét c¹nh (cung) cña ®å thÞ. VÝ dô 1: Cho ®å thÞ G = trong ®ã X = {A, B, C, D, E} vµ U = {AB, AC, AD, AE, BD, CD, CE} C D E B A A B D E C a) b) H×nh 4.1 H×nh 4.1.a vµ h×nh 4.1.b ®Òu lµ biÓu diÔn h×nh häc cña ®å thÞ G ®· cho ë trªn 2. Sù ®¼ng cÊu Víi mçi ®å thÞ th× cã thÓ cã nhiÒu d¹ng biÓu diÔn h×nh häc, cã nhiÒu ®å thÞ t­ëng chõng kh¸c nhau nh­ng ®ã lµ c¸ch biÓu diÔn h×nh häc kh¸c nhau cña cïng mét ®å thÞ, sù ®¼ng cÊu cho phÐp chóng ta kÕt luËn ®­îc ®iÒu ®ã. §Þnh nghÜa: XÐt 2 ®å thÞ G1 = (X1, U1) vµ G2 = Hai ®å thÞ nµy ®­îc gäi lµ ®¼ng cÊu víi nhau nÕu tån t¹i 1 song ¸nh tõ X1 vµo X2 vµ tõ U1 vµo U2 sao cho nÕu cã c¹nh e = (u, v) Î U1 t­¬ng øng víi c¹nh e' = (u', v') Î U2 th× cÆp ®Ønh u, v Î X1 còng lµ t­¬ng øng cÆp ®Ønh u', v' Î X2 VÝ dô xÐt 2 ®å thÞ G1 vµ G2 nh­ h×nh 4.2 a b c d m n p q G1 G2 H×nh 4.2 Ta cã f : G1 ® G2 f(a) = m f(c) = n f(d) = q f(b) = p NÕu a, b Î X1 kÒ nhau th× f(a), f(b) Î X2 kÒ nhau. VËy ®©y lµ 2 ®å thÞ ®¼ng cÊu víi nhau, ta cã thÓ xem G1 vµ G2 thùc chÊt chØ lµ 1 chØ cã ®iÒu biÓu diÔn ë d¹ng h×nh häc kh¸c nhau, c¸c tªn ®Ønh kh¸c nhau. §Ó xÐt 2 ®å thÞ cã ®¼ng cÊu kh«ng lµ viÖc khã, tuy nhiªn ®Ó xÐt 2 ®å thÞ kh«ng ®¼ng cÊu víi nhau th× ®¬n gi¶n h¬n. §èi víi 2 ®å thÞ ®¼ng cÊu th× c¸c ®å thÞ ®ã cã nh÷ng tÝnh chÊt bÊt biÕn nh­ sau: - Sè ®Ønh b»ng nhau - Sè c¹nh b»ng nhau - BËc c¸c ®Ønh t­¬ng øng cïng nh­ nhau - 2 Ma trËn kÒ còng nh­ nhau - C¸c chu tr×nh còng nh­ nhau 3. Mét sè ®å thÞ ®Æc biÖt Do tÝnh chÊt, d¹ng biÓu diÔn cã nh÷ng nÐt ®Æc thï riªng biÖt nªn ta ph©n lo¹i mét sè ®å thÞ thµnh c¸c d¹ng ®Æc biÖt sau: 3.1 §å thÞ ®Òu Lµ mét ®å thÞ mµ mäi ®Ønh cã cïng bËc, nÕu bËc nµy b»ng k th× ®ã lµ ®å thÞ k - ®Òu a) b) c) d) H×nh 4.3 a: G- 1 ®Òu; b: G - 2 ®Òu; c: G - 2 ®Òu; d: G - 3 ®Òu. Tr­êng hîp riªng nh­ ®å thÞ h×nh 4.3.b vµ h×nh 4.3.c lµ nh÷ng ®å thÞ vßng ký hiÖu Cn (n lµ sè ®Ønh) 3.2 §å thÞ ®Çy ®ñ §å thÞ ®Çy ®ñ n ®inh, ký hiÖu Kn lµ ®¬n ®å thÞ v« h­íng mµ mäi cÆp ®Ønh ph©n biÖt lu«n kÒ nhau. Xem vÝ dô nh­ h×nh 4.4 d­íi ®©y hoÆc 1 tr­êng hîp riªng cña ®å thÞ ®Òu G - 3 lµ nh÷ng ®å thÞ ®Çy ®ñ a) b) H×nh 4.4 a - ®å thÞ ®Çy ®ñ K2 ; b - ®å thÞ ®Çy ®ñ K4 3.3 §å thÞ b¸nh xe: Ký hiÖu Wn, thu ®­îc tõ ®å thÞ vßng cã n ®Ønh b»ng c¸ch bæ sung mét ®Ønh míi nèi tÊt c¶ c¸c ®Ønh ®· cã. W4 W5 W6 H×nh 4.5 C¸c d¹ng ®å thÞ b¸nh xe 3.4 Mét vµi øng dông cña ®å thÞ ®Æc biÖt ë c¸c m¹ng côc bé (LAN), c¸c m¸y tÝnh th­êng ®­îc kÕt nèi theo mét c¸ch thøc nµo ®ã gäi lµ h×nh tr¹ng (topolopy). Dùa theo ®Æc ®iÓm cña c¸c totolopy nµy mµ ta cã thÓ m« h×nh b»ng 1 sè d¹ng ®å thÞ ®Æc biÖt. VÝ dô víi m¹ng LAN c¸c m¸y tÝnh ®­îc kÕt nèi theo topolopy h×nh sao (Star) sau ®©y: H×nh 4.6 ë d¹ng nµy, tÊt c¶ c¸c m¸y ®­îc nèi vµo mét thiÕt bÞ trung t©m cã nhiÖm vô nhËn tÝn hiÖu tõ c¸c m¸y vµ chuyÓn ®Õn m¸y ®Ých cña tÝn hiÖu. Tõ ®Æc ®iÓm nµy cã thÓ m« h×nh b»ng mét ®å thÞ bé phËn cña ®å thÞ b¸nh xe W6 nh­ h×nh 4.7.a a) b) c) d) a) D¹ng sao b) d¹ng vßng c) d¹ng hçn hîp d) d¹ng ®Çy ®ñ (Complete) H×nh 4.7 Mét sè topolopy cña LAN ë m¹ng LAN ta còng th­êng cã c¸c d¹ng topolopy kh¸c nh­ d¹ng chu tr×nh (loop) hoÆc gäi lµ vßng. ë d¹ng nµy mçi m¸y nèi ®óng víi 2 m¸y kh¸c. M¹ng côc bé víi cÊu tróc vßng trßn ®­îc m« h×nh b»ng c¸c ®å thÞ ®Æc biÖt d¹ng vßng Cn nh­ h×nh 4.7.b, th«ng b¸o göi tõ m¸y nµy sang m¸y kh¸c theo chu tr×nh vßng trßn cho tíi khi tíi ®­îc m¸y ®Ých. HoÆc 1 d¹ng n÷a lµ d¹ng hçn hîp, ®ã lµ sù kÕt hîp cña d¹ng h×nh sao vµ h×nh vßng. Topolopy kiÓu nµy lµ mét ®å thÞ b¸nh xe Wn (h×nh 4.7.c). M¹ng côc bé d¹ng b¸nh xe c¸c m¸y cã thÓ truyÒn vßng quanh theo vßng trßn hoÆc cã thÓ qua bé phËn trung t©m. Ngoµi ra ng­êi ta còng th­êng hay bè trÝ m¹ng sao cho c¸c m¸y ®Òu kÕt nèi trùc tiÕp víi nhau, víi kiÓu nµy cã thÓ m« h×nh b»ng ®å thÞ ®Çy ®ñ Kn (h×nh 4.7.d) 4. BiÓu diÔn ®å thÞ trªn m¸y tÝnh LÜnh vùc ®å thÞ cã nhiÒu øng dông trong thùc tÕ, cã thÓ m« h×nh nhiÒu øng dông b»ng ®å thÞ vµ sö dông m¸y tÝnh ®Ó gi¶i quyÕt c¸c bµi to¸n vÒ øng dông ®ã. Nªn viÖc biÓu diÔn vµ l­u tr÷ ®å thÞ trªn m¸y tÝnh lµ mét vÊn ®Ò kh¸ träng t©m, ph­¬ng thøc biÓu diÔn tõng lo¹i ®å thÞ trªn m¸y tÝnh ¶nh h­ëng ®Õn c¸c gi¶i thuËt, ph­¬ng ph¸p gi¶i quyÕt c¸c øng dông trªn m¸y tÝnh. 4.1 BiÓu diÔn b»ng ma trËn kÒ Ph­¬ng ph¸p nµy dùa trªn mèi quan hÖ gi÷a c¸c cÆp ®Ønh, mçi ®å thÞ ®­îc ®Æt t­¬ng øng víi mét ma trËn vu«ng cÊp n (n lµ sè ®Ønh cña ®å thÞ). Gäi ma trËn kÒ lµ A = (aij ) i,j = 1...n. + Tr­êng hîp G = lµ ®å thÞ v« h­íng víi X = {x1, x2,...,xn} khi ®ã mçi phÇn tö aij cña ma trËn A ®­îc x¸c ®Þnh nh­ sau: aij = aji = d, nÕu cÆp ®Ønh (xi, xj) cã d c¹nh nèi víi nhau. Khi cÆp ®Ønh (xi, xj) kh«ng cã c¹nh nµo nèi víi nhau thÞ aij = 0. Ta thÊy ma trËn kÒ cña ®å thÞ v« h­íng lµ ma trËn ®èi xøng. + Tr­êng hîp G = lµ ®å thÞ cã h­íng víi X = {x1, x2,...,xn} th× mçi phÇn tö aij cña A ®­îc x¸c ®Þnh nh­ sau: ®èi víi mçi cÆp ®Ønh (xi, xj) tõ xi ®Õn xj nÕu cã d cung th× aij = d. Chó ý aji = 0 nÕu kh«ng cã cung nµo h­íng tõ xj ®Õn xi. Ma trËn kÒ trong tr­êng hîp nµy lµ kh«ng ®èi xøng. Trong 2 tr­êng hîp trªn ta chó ý nÕu ®Ønh xi cã mét khuyªn th× phÇn tö t­¬ng øng cña ma trËn kÒ lµ aii = 1 A C B D A B C D G1 G2 H×nh 4.8 Ta cã thÓ dïng ma trËn kÒ biÓu diÔn ®å thÞ G1 vµ G2 trong h×nh 4.8 nh­ sau: §èi víi ®å thÞ cã träng sè mçi c¹nh e = (xi, xj) ®­îc g¸n mét träng sè l(e) (cßn viÕt lµ l(xi, xj) ) th× ma trËn kÒ cña nã ®­îc thay b»ng ma trËn cã träng sè, khi ®ã mçi phÇn tö cña ma trËn b»ng träng sè cña c¹nh t­¬ng øng: aij = l(xi, xj) ¦u ®iÓm cña ph­¬ng ph¸p nµy lµ dÔ dµng x¸c ®Þnh ®­îc c¸c cÆp ®Ønh cã kÒ nhau hay kh«ng hoÆc rÊt thuËn tiÖn khi t×m sè bËc cña mçi ®Ønh. ViÖc truy cËp phÇn tö cña ma trËn kÒ qua chØ sè kh«ng phô thuéc vµo sè ®Ønh cña ®å thÞ. 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ã. §Þnh lý: s lÇn NÕu G = lµ ®a ®å thÞ víi A = (aij) lµ ma trËn kÒ t­¬ng øng, th× sè ®­êng ®i kh¸c nhau tõ ®Ønh xi ®Õn ®Ønh xj cã ®é dµi s b»ng phÇn tö Pij cña ma trËn tÝch A´A´...´A = As = (Pij) XÐt vÝ dô øng dông: Trong mét sè hÖ thèng th«ng tin khi ®­îc m« h×nh b»ng ®å thÞ cã thÓ thùc hiÖn tèt mét sè c«ng t¸c kiÓm kü thuËt. VÝ dô khi biÓu diÔn mét m¹ng m¸y tÝnh b»ng ®å thÞ, gi¶ sö cã 2 m¸y nµo ®ã mµ th«ng tin truyÒn gi÷a chóng lµ quan träng, cÇn tiÕn hµnh kiÓm tra xem ®· cã ®­êng truyÒn dù phßng gi÷a chóng kh«ng. XÐt ë gãc ®é ®å thÞ th× cÇn kiÓm tra xem sè ®­êng ®i gi÷a cÆp ®Ønh t­¬ng øng víi 2 m¸y ®ã, nÕu sè ®­êng ®i lín h¬n 1 lµ ®· cã ®­êng truyÒn dù phßng. * Ch­¬ng tr×nh viÕt b»ng PASCAL sau tÝnh sè ®­êng ®i ®é dµi l nhËp tõ bµn phÝm Type MaTran = Array[1..20,1..20] Of Integer; Var a, b, aa: MaTran; n,l,x1,x2: Integer; Procedure InputMt(Var Mt: Matran); Var i, j: Integer; Begin For i:=1 to n do For j:=1 to n do Begin Write('a',i,j,'= '); Readln(Mt[i,j]); End; End; Procedure Gan(Mt1: MaTran; Var Mt2: MaTran); {Mt2 <-- Mt1} Var i,j:Integer; Begin For i:=1 to n do For j:=1 to n do Mt2[i,j]:=Mt1[i,j]; End; Procedure TichMt(mt1,mt2: Matran; Var MtKq: MaTran); { MtKq = Mt1*Mt2 } Var i,j,k: Integer; Begin For i:=1 to n do For j:=1 to n do Begin MtKq[i,j]:=0; For k:=1 to n do MtKq[i,j]:=MtKq[i,j]+Mt1[i,k]*Mt2[k,j]; End; End; Procedure LthuaMt(m: Integer); {aa = a ^m (m: do dai duong di, m>=2) } Var i: Integer; Begin Gan(a,b); For i:=1 to m-1 do Begin TichMt(b,a,aa); Gan(aa,b); End; End; Procedure FindWay(i,j: Integer); { Tim so duong di tu dinh i-->j } Begin If aa[i,j]0 then Writeln('So duong di do dai ',l,' tu x',x1,' --> ','x2 ','la: ',aa[i,j]) Else Writeln('Khong co duong di tu dinh ',i,' toi dinh ',j,' voi do dai ',l); End; BEGIN Writeln('Nhap ma tran ke cho do thi:'); Write('So dinh do thi: '); Readln(n); InputMt(a); Write('Dinh xuat phat: '); Readln(x1); Write('Dinh ket thuc: '); Readln(x2); Write('Do dai duong di: '); Readln(l); LthuaMt(l); FindWay(x1,x2); END. 4.2 Danh s¸ch c¹nh (cung) Cho ®å thÞ G = víi sè c¹nh m, sè ®Ønh n. NÕu m < 6n th× G th­êng ®­îc biÓu diÔn d­íi d¹ng danh s¸ch c¹nh (cung). Theo c¸ch nµy danh s¸ch tÊt c¶ c¸c c¹nh (cung) cña ®å thÞ v« h­íng (cã h­íng). Mçi c¹nh (cung) e = (x, y) cña ®å thÞ t­¬ng øng víi hai biÕn Dau[e], Cuoi[e]. 1 2 3 4 1 2 4 3 G1 G2 H×nh 4.9 Dau Cuoi 1 2 1 3 2 3 2 4 3 4 Danh s¸ch c¹nh G1 Dau Cuoi 1 2 2 3 3 1 4 1 4 2 Danh s¸ch cung G2 VÝ dô: H×nh 4.9 ®å thÞ G1 vµ G2 ®­îc biÓu diÔn b»ng danh s¸ch c¹nh (cung) nh­ sau: Nh­ vËy ®Ó l­u tr÷ ®å thÞ cÇn sö dông 2m ®¬n vÞ bé nhí. Nh­îc ®iÓm cña ph­¬ng ph¸p nµy lµ ®Ó x¸c ®Þnh nh÷ng ®Ønh nµo cña ®å thÞ lµ kÒ víi mét ®Ønh cho tr­íc chóng ta ph¶i lµm cì m phÐp so s¸nh. 4.3 Danh s¸ch kÒ Ph­¬ng ph¸p biÓu diÔn b»ng danh s¸ch kÒ còng ®­îc sö dông kh¸ phæ biÕn vµ th­êng hay dïng cho ®å thÞ cã h­íng. Danh s¸ch kÒ cho ®Ønh xi lµ danh s¸ch gåm tÊt c¶ c¸c ®Ønh kÒ cña xi theo thø tù c¸c ®Ønh trong tËp ®Ønh X. Ta cã thÓ biÓu diÔn ®å thÞ nh­ mét m¶ng FIRST, víi phÇn tö FIRST[i] lµ con trá trá tíi danh s¸ch kÒ cho ®Ønh xi. VÝ dô: ë h×nh 4.9 ®å thÞ G1 vµ G2 ®­îc biÓu diÔn b»ng danh s¸ch kÒ nh­ sau: FIRST 2 1 1 2 3 Nil 3 2 3 Nil 4 Nil 4 Nil 1 2 3 4 a) Danh s¸ch kÒ cña ®å thÞ G1 FIRST 3 Nil 2 1 Nil 3 Nil 2 Nil 1 2 3 4 b) Danh s¸ch kÒ ®å thÞ G2 Bé nhí sö dông cho ph­¬ng ph¸p biÓu diÔn danh s¸ch kÒ lµ tû lÖ thuËn víi tæng sè ®Ønh vµ c¸c c¹nh cña ®å thÞ. Nh­îc ®iÓm cña c¸ch biÓu diÔn nµy lµ thêi gian cÇn thiÕt ®Ó x¸c ®Þnh cã mét c¹nh ®i tõ ®Ønh xi tíi ®Ønh xj cã hay kh«ng mÊt O(n). C¸ch biÓu diÔn nµy thÝch hîp cho c¸c thuËt to¸n mµ cÊu tróc ®å thÞ hay thay ®æi nh­ thªm hoÆc bít c¸c c¹nh.