ÕÒÖÎ ÆÉ ÐÖÔÒ Ñ ˆ e Ê j ÉÏÏÔÐÏÒuu ËÊ o y * ÎÏ Ó ÏÕ( ) (* É ) An Improvement of Force-directed Hierarchical Graph Layout And Its Application to Web Site Visualization Jun DOI Takayuki ITOH IBM Research, Tokyo Research Laboratory doichan@jp.ibm.com, itot@computer.org ÐÖÔÒ ÑÊuu sê } Ê Ç~ÌÍÍÉÆÍ r ~ ~ d v ÑÑÒÕ Ï Ñ ÓÒÒÊÊ ˆ Ê Æ ÊÒ Ñ ÆÍËÒ Ñ uê ÉÊ Ç ÈÍÉÆÍ ÐÖÔÒ ÑÊu u ÊÆÇÍ Ì ÇÊ ŠÊ ÃÐÖÔÎwwÈÈÊÆ ÊÓ ÒÊ ˆ eî i Ê ÈÍÃÉÆÆ ŠÉÆÍ ÇÊ ŠÎu ÈÍÉÌÊ Ó ÒÊ ÕÒÖ Î ÐÊÓÓÕÒÖÎ ÈÉ ~ ÊÍÉÉjzÊÓ Ò e Î Í Ç ÈÍÉÆÍ w ÉÊ vêíæêã ÕÒÖÎ ÆÉÐÖÔÒ ÑÊ ˆ e ÃÊ j ÆÍË ÐÖÔÒ ÑËÊ Î ÈÍ Ê Ó ÒÎ ÈÉ eèíï ÐÖÕ ÑÖÊÎÖÐÖÑÕÊÍÍ e Î ÈÍÉ ÉÌÊ v Ê Î ÆÍÇÉÊ ÈÉÆÍ ÌÉ w ÉÊ v Î ÆÉÏÏÔÐÏÒÊuu Î ÈÍ ÉÊ ÏÏÔÐÏÒÎ ÈÍÏÏÔÔ ÑÎÓ Ò ÏÏÔÔ Ñ ÊÓÏÓ Ö ÐÎÎ ÐÉÈÉ ÌÉÏÏÔÔ ÑÊÒÏÖÐÒÖ Î ÈÉÏÏÔÔ ÑÎ Ò ÑÊ ÈÍÇÉÊÍÍ ÏÏÔÐÏÒÎ ÐÖÔÒ ÑÉÈÉs ÈÍ ÇÊ ÐÖÔÒ ÑÎ v ÊÍÍ ˆ eè ÂÊÏÏÔÔ ÑÎÐÕÓÏÖ És ÈÍÇÉÊÍÍ ÏÏÔÐÏÒÊ Îs ÈÍ ÊÈÌÊ ÐÖÔÒ ÑÊÐÖÔÏÒÐÑs sê ˆ Ê Æ ÊÒ Ñ ÆÍËÒ Ñ Ê ÉÆ Í }ÉÊ ÏÏÔÐÏÒÊÖ Ð ~Ês r ~ ~ dêêê ÓÒÒÖ ÐÊs ÊÊÊÐ ÔÖ ÐÒ ÑÊ u ÊÉÌÊ Ò ÑÎ ~ É~ ÈÉÐÖÔÊs ÒÐÑÒÒ ÑÌ Ò ÑÊ ÊÉÌÊ Ò ÑÎ ~ É~ ÈÉÐÖÔÊs ÆÊ v ÊÔÖÑÑÊÊÊÍÆÊ ~ ÆÍÕÑÕ ÖÊ É ÈÍÍÑÑÒÕÊ jæîsèéðöôês ÊÊÊ ÉÊ Ç ÈÍÉÆÍ ÌÉ ÐÖ ÔÒ Ñuu ÊÉÌÊ sêéæéê } Ê ÊÉÉ Êuw ÌÐ ÔÏw Ç ÈÍÉÆÍ [1] [2] ÐÖÔÒ ÑÊuu ÊÆÇÍ Ì ÇÊ ŠÊ ÃÐÖÔÎwwÈÈÊÆ ÊÓ Ò ˆ eî i Ê ÈÍÃÉÆÆ ŠÉÆÍ ÇÊ ŠÎu ÈÍÉÌÊ ÆÊ [ 1] } Ó ÒÇÿ Ê{ Î ÉÇÉÊÍ
Í Ó ÒÊÆÈÊ ˆ Ê ÊÍÎÇÍ [ 2] Î ÐÊ ÈÊd ÎÉÇÍÉÇ ÇÈÉ Î ÐÉ~ ÈÍÉÓ ÒÎÆ ÆÊ}Æ eê e ÈÍ [ 3] Î ÐÊÆÈÇ ÈÊÆÍÆÊÈÍ [ 4] Î ÐÇ Ê É ÊÓ ÒÉ Ê ÍÊÆÍÆÊÈÍ ÊÊÊ 1 Î ÉÈÍÆÊ e Î ÈÍ Ç Ç ÈÍÉÆÍ =?Ó Ò Ê ÊÍÎÇÍ =?Î ÐÊ ÈÊd Î ÈÇÈÍ =?Î Ð Ê ÎÇÍ =?Î ÐÉÓ ÒÊ ÊÍÎÇÍ 1 ÐÖÔÒ Ñ ˆ eê Ê vê ŠÊ ÈÉ ÇÊuu ÎÔÖÐ ÑÕ Ç ÌÉÆÍu Ê Ã ÉÊÇÉÌÆÆÇÍ w wî ÇÇÉÊÉÇÍ Ê e Î ~ Ê ÌÍÃÇÉÉÆÍ ÇÊÃ Ê ÃÎ Ã ~Ê ÌÍÃÉÆÆÒÖ ÒÏÔ Ê Ê È É ÓÖ ÑÊÉÍÉ ÉÈÉ ÐÖÔÊÓ ÒÊ ÕÒÖ ÐÖÔÊÎ ÐÊÓÓÕÒÖ Î ÆÉ ~ ÎuÇÇÉÊÍÉÉ ÂÊÓ ÒÊ Ê eî ÈÍ 2 Ç ÍÍ ÉÆÍ ÈÇÈ ÇÊ ÊÈÉÌ 2 ÊÉ ~ÈÍ ÉÆÍ ÆÇÉÇÊwŠÎ ÈÉÆÍ w ÉÊ ÕÒÖÌÓÓÕÒÖÊÊÊ ÕÒÖÎ ÆÉÐÖÔ eê ÈÍ j Î ÈÍ w Ç ÈÍ j Ê ÇÍ ÈËÉÊÓ ÒÎ eèí É ÊÍ È ÉÏ ÐÖÕ ÑÖÊÓ ÒÎ eèí ÇÊÎÖÐ ÖÑÕÊÍÍ Ê ÃÓ ÒÊ e Ç e Ê ÇÇ ÈÍÃÉÆÆ ŠÎ ÈÍÉÉÌÊ ÕÒÖÊv Î ÈÍÇÉÉ ÍÍ Ì ~ÊÓ Ò eî ÈÍ ÆÉ w ÉÊ v Î ÐÖÔÒ Ñ Ê ˆ eê ÈÍÎÖÐÖÑÕÌ ÈÍ ÇÇ É ÐÖÔÒ ÑÉÊ ÐÖÔÎ ÈÍÓ Ò Ê ~ÎvÇÉ É Ó Ò Î~ ÈÍÎ Ð ÎvÇÉÐÖÔÒ ÑÎ È ÈÍÊ w ÉÊ v Î ÆÉÏÏÔÐÏÒ Êuu Î ÈÍ ÉÊ ÏÏÔÐÏÒ Î ÈÍÏÏÔÔ ÑÎÓ Ò ÏÏÔÔ Ñ Ê Ö ÐÎÎ ÐÉÈÉ ÌÉÏÏÔÔ ÑÊÒÏÖÐ ÒÖ Î ÈÉÏÏÔÔ ÑÎ Ò ÑÊ ÈÍÇÉÊÍÍ ÏÏÔÐÏÒÎ ÐÖÔÒ ÑÉÈÉs ÈÍ ÇÊ ÐÖÔÒ ÑÎ v ÊÍÍ ˆ eè ÂÊÏÏÔÔ ÑÎÐÕÓÏ Ö És ÈÍÇÉÊÍÍ ÏÏÔÐÏÒÊ Îs ÈÍ ~ ÕÒÖÊÐÖÔÒ Ñ eëê ÐÖÔÒ ÑÊuu ÐÖÔÒ ÑÊuu Ê 1980 ÇÍ Ç Ç~ÎÉÆÍ ÈÊ É ÊÆÇÉÇ ÊÐ ÔÏ [1][2]Êu ÈÍÉÆÍ 1 ÊÉ ÌÓÓÕÒÖÊÊÊ ÕÒÖÎ ÈÉÐÖÔÒ Ñuu ÊÉÆÉ~ËÉÇ ÇÍÌ[3]Ê sèíííæê 1980 ÇÍ Ç~ÎÉÆÍ ÇÊ Ê 1 ÉÆÇÉ Ê ÆÉ Ê[ 1][ 2]Î ÉÈÉÌÊuu ÉÆÍÉÆÆÍ ÌÉÿj Ê [ 2]Î ÉÈÇÉÇÉÇÍÊ Ê[ 3]Î ÉÈ h Ç Æ ÇÊ ÕÒÖÎ ÆÉuu ÊÊ ÊÍÆÊ Š Ç ÈÍÉÆÍ
v Ê ÇÉÇÍËÊ ~ÉÊÊÆ Ê u ÊÐÖÔÒ ÑÊÆÆÉ ˆ Ê ÇÊv ÎuÈÍ Ó ÒÊ e Ç eê ÇÇ ÈÍ ÊÌÇÇÍÍÈ Ê eî ÌÍ Ç ÊÆ Î ÐÉÓ ÒÊ ÊÍÎ ÈÊv Éu ÈÍ Ê ÇÊÆ ÉÌÍ 1 É ÈÉ[ 4]Î ÉÈÇÉÇ ÈÆ ÇÍÍÊ Š Îu ÈÍÉÌÊ } ÊÊÉÉ ÕÒÖÎ ÆÉÐÖÔÒ Ñuu Ê Ê ÇÊ j Ç ÈÍÉÆÍ ÆÊ [4]ÉÊ 10 ÊÓ ÒÎÌÉ ÊÐÖ ÔÒ ÑËÊ ÇvÌÍÍÉÆÍ ÌÉ [5] ÉÊ Î ÐÊÆÈÊ Î ÍÈÇÉÊ Î ÆÇÊÇÍ Ê ÊÓ ÒÊ eî È ÉÆÍ ÌÉ [6]ÉÊ ÔÖÓÏ Î ÈÊ ÇÍ ÕÒÖÎ ÈÍÇÉÉ Ó ÒÊ e Î ÈÉÆÍ w Ê 3 É ÈÉÆÍÏ ÐÖÕ ÑÖ ÊÓ Ò e ÊŠ ÈÍ ÉÈÉ [7][8]ÊÊÊ ÇÈÉÊ ÈÍÉÆÍ ÈÇÈ ÇÍÍÊ Ê ÈÉÊ Ê eèíéæíðö ÔÒ ÑÊ ÈÉ Ê~ ÎsÆ ÇÉÉ ÐÖÔÒ ÑÊÒÓÐ ÑÕ Î ÈÍÌ ÊÉÆÍ ÐÖÔÒ Ñ Ê ˆ eê ~ Î ÉÈÍÌÊÉÊÊÆ w Ê 4 É ÈÉÆÍ ÐÖÔÒ Ñu u Êÿ ÉÈÉ ÊÆÍÈÉÐÖÔÒ Ñ Î Êuu ÈÍ Ì ÈÊÿÎÑ Õ ÈÍ Ç ÈÍÉÆÍ[9][10] ÈÇÈÇÍÍÊ Ì ÐÖÔÒ Ñ Î 2 ˆÊ ~ eèí w Ê ÉÊ Ç ÊÍ ÏÏÔÐÏÒÊuu ÏÏÔÐÏÒÊuu Ê ÇÊ ÏÏÔÐÏÒ Î ÈÍÏÏÔÔ ÑfÎÿus ÈÍ Ì Ç uíííïïôðïòuu Ê ÏÏÔÔ ÑÎ ÒÏÖÐÒÖ ÌÉÊÒÒÔÔ ÑÇÍÊÖ Ð ~É ÈÉs ÈÍ ÉÆÍ ÏÏÔÐÏÒÊ ~Îs ÈÍÐÏÒÔÒÔÊ Ê ÉÈÉ Inxight Ç ÈÉÆÍÕ Ð Ï ÑÔÏ Ñ [11] ÇÆÍ ÇÊ Ê Hyperbolic Tree [12] ÉÆÆ ~Ò Ñuu Î ÈÉ ÒÒÔÔ ÑÎ ÊÈÉÏÏÔÐÏÒÊ ~Îs ÈÉÆÍ Õ Ð Ê v Ê~ ÈÉ Ñ ÕÊÍÍv s Î ÈÉÆÍ ÌÉ Durand ÍÇ ÈÉ MAPA [13] Ì ÏÏÔÔ ÑÎ ~ÊÈÉÇÉÉd Ê ËÍs Î ÆÉÆÍ Õ Ð Ê v ÊÈÉ ÇÉÉ ÊÇÉ ÊÏÏÔÔ ÑfÎs É ÇÍ ÌÉ ÍÊ Ê Í ~Î ÈÉ Ò Ñuu Î ÆÉ ÏÏÔÐÏÒÊÎ ÐÑÑ vîuu ÈÍ Î ÈÉÆÍ[14] ÿ ÏÏÔÔ ÑfÎÓ Ò ÏÏÔÔ Ñ Ê ÓÏÓ Ö ÐÎÎ Ð Ê ÈÍÇÉÉ ÈÍ ÍÐÖÔÎuu ÈÍ Ì Ç ÈÍÉÆÍ ÿ ÉÈÉ ÕÒÖÎ ÆÉÐÖÔ ~Î 3 Êi eèí Î ÏÏÔÐÏÒÊÖ Ð Êuu Ê ÈÉ Ç ÈÍÉÆÍ [15] ÿ i eéêêç v ÊÍÉÉÐÖÔ ~Î uèèíuu Ì Ç ÍÍÉÆÍ ÍÊ ÆÍÇÈÌ ˆ Ê eèíéó ÒÎ É ÇÍ ÊÍÉÉ ÊÏÏÔÔ ÑÊÖ Ð Î v Êuu ÈÍ Î ÈÉÆÍ [16] ÇÍÍÊ ÊÆÈÍÌ 3 ÊÏÏÔÔ ÑfÎ eè ÉÆÍ 2 ˆ ÊÏÏÔÔ ÑfÎ eèí w Ê ÉÊ ÇÇ ÊÍ ÕÒÖÎ ÆÉÏ ÐÖÕ Ñ ÖÊÓ Ò eê É ÈÍ ÕÒÖ ÉÊ ÐÖÔÊÎ ÐÊÓÓ Ó ÒÊ Î È ~ Î ÆÉÎ ÐÊ ÆÍËÓ Ò Ê { Î ÌÍ Êw ÉÊ yéêí 2 ÊÓ ÒÎ ÉÈÉ Ã É ÈÉÊ Êd ÃÊ ÈÍÃÓ Ò Ê{ (ÌÉÊÎ ÐÊ È)ÃÊ Îd ÉÈÍ ÌÉÈËÉÊ Ê ÈÆ ÎÌÉÌÊÉÈÍ ÉÊ Ê Î ÆÉ Î ÐÉ~ ÈÍ É 2 ÊÓ Ò Ê ÌÉÊ F a Î ÌÍ 3( ) k( d 1.0) F a = k( D 1.0)...( d < D)...( d D)
ÇÇÉ k, D Ê ÉÆÍ D > 1. 0ÉÆÍÉÈÍ ÇÊ ÊÔÒÐÊ ÊÍÍÓÓÕÒÖÊŠ ÈÉÆ ÍÇ ÉÊv Ê Î ÇÉÌÊ Î Ð Ç Æ ( d D) ÉÇÊ Ê ÇÈÇÿ ÉÆÍ ÉÆÆ Î ÆÉÆÍ ÌÉ ÉÊ Ê Î ÆÉ Î ÐÉ~ ÈÍÉÆÊÆ 2 ÊÓ Ò Ê F b Î ÌÍ 3( ) 5 3 19 2 9 k( d d + ) F b = 4 8 8 0...(0.0 d < 1.0)...( d 1.0) ÇÇÉ k Ê ÉÆÍÉÈÍ ÇÊ Ê ÕÒÖÊÿÉÉÆÍÔÎ ÒÖ Ö ÖÑ Î 3 É} ÈÉÌÊ [17] ÉÆÍÇ ÉÊ Ê uêêé d 1. 0 1 ÊÉÇÊ ÎÑÖÉÈÉÆÍ ÉÊ Ó ÒÎ ÈÉ ˆ Ê e È ÈÉÊ eèíéæíó Ò Ê ÆÍË Î ÈÍ ÇÇÉ i ÊÓ ÒÊÇÇÍ Ê vî F i eî x i Ó ÒÊz Î m Ñ Ó Ð Î c ÉÈÍÉ vê~ mx ''+ cx ' = F i D i d i ªªªªª ªªª É ÆÍ Ê Ê ÊÍÉÉ Ó ÒÊ Ê eî Ì ÍÇÉÇÉÇÍ Ï ÐÖÕ ÑÖÊÓ Ò eêíí v Ê ÈÉÊÆÇÉÇÊÓ ÒÇ eèíéæí 4(a)Ê ÍÆÊ ÇÍ ÊÓ Ò N0Î~ ÈÍÇÉÎ fæí ÉÊ ÊÍÆÊ É v Î È v Ê Î ÆÍ ÌÈ N 0 ÉÇÊà ÃÊÔÖÐÎ ÉÍ 4(b) ÆÉ Ó ÒÉÎ ÐÉ~ ÈÍÉÓ Ò 1 d Ó ÒÉÎ ÐÉ~ ÈÍÉÆÊÆÇ }Æ{ ÊÆÍÓ Ò ÊÌÊ ÈÉ Î È ÈÊ Êd Î~ Ê ÈÉ Ó ÒÊ ÈÆ eîv ÈÍ Ç ÇÆÓ ÒÊÉÆÉÊ Ã ÃÊÔÖÐÎ É ÊÆÈ 4(c) à ÃÊÓ ÒÊ ÈÉ Î ÈÍ 4(d) ÆÉ ÇÊ Êd ÊÍ ÉÉ ËÓ ÒÊ ÈÆ eîv È 4(e) Ê Î ÈÍ 4(f) ÇÊ Ê Ê ÍÍ ÉÊ ÕÒÖÊv Î È v Ê Î ÆÍ (a) (c) (e) N 0 fíê téê v Ê Ê ÑÒÒÔÊ É Ó ÒÊ Ê 0.5 Ê Î ÈÍ Ó ÒÊ ÈÉÔÖÐÎ ÉÍ ÈÈÉÔÖÐÊ É ÉÆÍÓ ÒÇ ÇÊÇÊÉÉÉÇÊ ÕÒÖÊ v Ç ÈÉ É ÈÍ ÇÊÃ Ê 0.5 ÃÉÆÆ ÊÊ w ÊÊÇ fi Ê ÍÍu ÇÍ Œ Ê ÌÉÆÍ fíê téê Ê ÊÆÆÉ 5 30 Ê v É 1 ÊÓ Ò~ eê ÈÍ v Î ÈÍ ÈÇ (b) (d) v Ê jêó ÒÊà ÃÊÔÖÐÇÉÉÍÍÉÆÍ v Ê É ÊÍÉÓ Ò ÊÌÊsÍÍ ÈÍ ÊÓ Ò Êv ÊÈËÉ ÈÍÉÆÍ (f)
È ÊÇÍ ÌÍÊÓ ÒÊ~ Ç ÈÉ Î ÇÍ ÌÆÍ ÈÇÉ fíê Œ Ê 1 ÊÓ Ò eê ÈÍ Î 50 ÉÈ ÈÍÌÉ Ê ÈÊÇÉÉ Ê 50 Ê v ÉÊ e Î ÆÍ ÊÆ v Ç ÈÊÆÉÆÆ ŠÊ Ï ÐÖ Õ ÑÖÊÓ Ò eîöðöñõê Ê ŠÉÊ ÊÇ ÕÒÖÎ ÆÉ e ŠÊ ÇÊ ~ÈÍ ŠÉÆÍ ŠÉÈÉ ÊÐÖÔ ÑÔ ÒÏÏÎ[18]Ê ÈÍÉÆÍ ÕÒÖÊÌ v Ç ÈÊÆ yêu ÉÇÍ ÌÉÐÖÔÒ Ñ uu Ê Š ÆÊ uõòñõ ÊÉÌÊ ÕÒÖ[17]ÊÆÆÉÌ v Ç ÈÊÆ y Êu ÈÍÉÆÍ Ó Ò e Êi ÉÊÓ ÒÎ 1 ÈÉÏ ÐÖÕ ÑÖ Ê eèíçéî ÉÈÉÆÍÇ ÈÊ e ÊÕ Ð Ç fèíçéìéçíè ÌÉi ÈÍÇÉÌÉÇÍ Õ Ð Ç fèí u ÊÓ ÒÎ eèíê Õ Ð Ê Ê Æ ÊÔÖÐÖÒÑÔÊÐÖÔÒ ÑÎs È ÍÇÉÇÉÇÍ ~Ê j Ê e Î ÌÈ ÆÍÆÊ e Îi ÉÇÍÊ ÈÍÇ Ì ÈÆ ÌÆÍ 6 5 7 5 ( ) Î Ð Ê ÆÓ ÒÇ Ê eèííæê e ( ) Î Ð Ê ÆÓ ÒÇ }Ê eèííæê e 3 1 2 4 8 9 ÉÊÓ ÒÊ e Îi ÈÍÿ ÉÈÉ Ó ÒÎ Î Ð É Ñ ÒÈ Î Ð Ê ÆÓ ÒÇÍ Ê eèí É ÆÆ e Î ÈÍ ÇÇÉ ÉÊ Ê eèíó ÒÇ Ê ÇÍ eèíó 1 5 2 6 9 8 7 3 4 ÒÇ }Ê eèíííæêó Ò eî ÈÍ ÊÈÊÍ 5 Ê È~Í Î Ð Ê ÆÓ ÒÇ Ê eèí e ÊË ÆÇ Î ÐÊ Ç ÊÆ Ç ÆÉ È ÍÍÇÍÉÆÍ ÇÊ ÊÈÉÇÉÉ É Ê ÈÉÊ k ÊÓ ÒÇ eèíéæíéçê (k+1) ÊÓ ÒÊ e p Î Ê~Í ÈÍ p 0 0 = p + t ( p O ) ÇÇÉ p 0 Ê(k+1) ÊÓ ÒÊÎ ÐÉ~ È ÍÉÓ ÒÊ e OÊÈÉÊ eèíéæíó Ò fê t Ê Ê ÉÆÍ ÇÊ ÊÍÉÉ eî ÈÉÇÍ v Î ÈÍÇÉÊ ÍÍ (k+1) ÊÓ ÒÊ Ó ÒÍÍÌ Ê eèíí ÇÊ ÊÍÍ 5( )ÊÍÆÊ eî ÈÍ ÊÎÖÐÖÑÕÆÍË ÊÍÍÏ ÐÖÕ ÑÖÊÓ Ò e ÊÎÖÐÖÑÕÎ 6 Ê È Ó ÒÎ Ê É (+(1Ê ƒèí (+(1ÇÍÓ ÒÎ È Ã ÃÊÔÖ ÐÎÉÉÍ ÈÍÉÓ ÒÊ eî ÈÍ C FÎ ÊÓ ÒÊà à ÊÔÖÐÇÉÉÉÆÍ Í ÈÍ C Ó ÒÊÉÆÉ Î ÐÉ ÊÍÉ Ó ÒÉÊ Î ÓÓÕÒÖÉ ÈÍ D Ó ÒÊÉÆÉ Î ÐÉ ÊÍÉ ÆÊÆ} Ó ÒÉÊ Î ÕÒÖÉ ÈÍ E Î ÈÉÓ ÒÊ ÈÆ eî Ì Í F Ê ÇÆÓ ÒÊà ÃÊÔÖÐ Î ÉÍ (+(1Ç ÊÊÍÌÉ Î ÈÍ Ï ÐÖÕ ÑÖÊÓ Ò e ÊÎÖÐÖÑÕ ÈËÉÊÓ ÒÎ ÇÍ ˆ eèíˆï ÐÖ Õ ÑÖÊ É ÈÉ ÊÊ ÊÍÆÊ ÇÆÍ ÿé Ê ÉÈÉ ÊˆÏ ÐÖÕ ÑÖ Ê É ÈÉ v Î ÇÇ déçí Ç
ÆÇÍÍÍ ÕÒÖÎ ÆÉ v Êv Ê Ó Ò Î n ÉÈÉÉÇÊ v ÇÌÉÉÇ 2 ÈÍÉÆÊÆ É O( n ) ÉÆÍ v Î ÈÍÊÈÉÇÉÉ O( n) Ê}ÉÇ ÇÊÇÉÇ Í ÕÒÖÊ Êy ÈÉÆÍ Ê v Ê dêy ÉÇÍÇÉÇÍÇÍ 5 Ê È Œ ÇÍÌ v Ê Ê dç véçéæí É Ê ÉÈÉ 1 É ÈÉ[ 1][ 2] Êu ÊÆÆÉ ˆÏ ÐÖÕ ÑÖÊ É ÆÍÆÊÈÍ Êj Ê e Î ÍÇÉÇÉÇ Í ÇÆÇÍÍÍ ÇÊ Ì 5 Ê È Œ ÇÍ véçéæí É Ê ÉÈÉ 3.3 É ÈÉÓ Ò e ÊÍÍ Î ÐÊ Î ÍÈ ÉÌÍ 1 É ÈÉ[ 3]Êu É Î~ ÈÉÆÍ ÉÆÍ ÇÊ Ì 5 Ê È Œ ÇÍ v ÉÇÉÆÍ ÿ É Ê ÇwŠÉÈÉ ÉÉÆÍ Ê 1 É ÈÉ[ 4]Î ÈÍÌÊÉÊÊÆ ÈÉ ÇÉÉ ÉÈÉ Ó ÒÉÎ ÐÊ ÊuÍÍÍ ÇÉÇÆÍ ÇÊ ŠÊ ÈÉ fíê Î ÐÎ d ÈÍ ÊÍÉÉ ˆ ÐÖÔÒ ÑÊuu Ê ÈÉ Î~ ÈÉÆÍ[19]Ç ÇÍÎ Ð ÖÔÒ ÑÊ ÈÍÊÊ ŠÎ ÈÉÆÍ ÍÉÉ 6 É ÈÏÏÔÐÏÒÊuu ÊÊ Î ÐÊ d Ê ÆÉÆÊÆ ÐÖÔÒ Ñuu ÆÍ ËÏÏÔÐÏÒuu ÊÉÌÊÎ Ð d Î 7 ÊÉ ÊwŠÉÈÉ eéçéæí ÐÖÔÒ ÑËÊ ÐÖÔÒ Ñ ÐÖÔÒ ÑÊ Ó Ò Ê Î Î ÐÉ ËÇÉÉs ÈÍÉÒ ÑÉÆÍÇ ÇÍÉÊ Ê È ÊÓ ÒÊ ÎÐÖ ÔÉÈÉ ÉÍÆÍÇÉÉ ÊÐÖÔÒ ÑÎs È ÍÇÉÇ héæí ÈÍÊ ÐÖ Ôi ÎÓ ÒÉÈÉÉÍÆÍÇÉÊÍÍ ÐÖ Ô Ê ÎÎ ÐÉ ËÇÉÉ ÉÊÐÖÔÒ ÑÎ s ÈÍÇÉÇÉÇÍ ÇÊÍÆÊÈÉ Ó Ò Ê ÊÉÊÇÍÉÒÖ ~ÊÍÆÊ Ê dêéêçíî ÉÉÍÆÊÐÖÔÒ ÑÊ ÇÉÎ ÐÖÔÒ ÑÉ Ë 7 Ê ÐÖÔÒ ÑÊ Î È 7(i) Ê ÈÍ Ê~ ÊÐÖÔÒ ÑÉÆÍ Ç ÇÉ a h ÊÐÖ ÔÊÓ ÒÎ Í ÇÍÉ 7(ii)ÊÍÆÊ ÉÊÐÖÔÇ ÈÍÍ È ÍÆÊ 7(iii)ÊÍÆÊÈÍÊ Ê ÊÐÖ ÔÇ ÈÍÍ ÇÊÉÇ 7(iii)ÊÓ Ò A Ê ÈÉ 7(ii)ÊÓ Ò a~c É ÈÍÍÐÖ ÔÊÇÉÎ A Ê ÐÖÔ ~ÊÓ Ò a~c ÇÍu ÉÓ Ò A ÎuÓ Ò Ó Ò ABC É ÈÍ ÍÐÖÔÊÇÉÎuÐÖÔÉ Ë ÇÊ ÉÊ ÐÖÔÊ Ê ÈÊ ÿéæíç 7(i)ÊÓ ÒÊÈÍÊ ÐÖÔÇÆÍÍÆÊ ÈÊ ÊÍÐÖÔÌfÆÍÍÍ (i) ÇÊÍÆÊ ÊÐÖÔÒ ÑÊ ÆÊ Ê~ Ì}~Ì ÊÓÒÒÖ ÐÊ u dê ÌÓÑÓÑÔÖÑÑÊ u Ê ÉÆÍ ÊÐÖÔÒ ÑÎ ÆÍÇÉÊÍÉÉ ÊÍÆÊ Î ÍÇÉÇÉÇÍÉfÆÍÍ Í u ÐÖÔÊ ÌÇÊ u Ê ÊÐÖÔÎs ÈÍÇÉÊÍÉÉ ÐÖÔ Ê uî ÇÍ Ê Ê u Ê ÐÖÔÎ Ês ÈÍÇÉÊ ÍÍ Ê uî ÊÍÈÊ Êv ÊÒ ÑÎ ÍÇÉÇÉÇÍ u Ê (ii) ÐÖÔÒ ÑÊ (iii)
ÊÓ ÒÇÍ ÊÓ ÒÎ eèí ÇÉÉ u Î ~ ÈÍÇÉÇÉÇÍ ÇÊ ÊÉÆÉÊ ~ÈÍ ÐÖÔÒ ÑÊÓ Ò e ÐÖÔÒ ÑÌ Ê ÉÐÖ Ô ÌÓ ÒÎÎ ÐÉ ÊÍÉÐÖÔÒ ÑÉÆ ÍÉfÆÍÍÍ ÈÇÉ Ê ÊÐÖÔÒ ÑÊÐÖ ÔÌÓ ÒÎ eèíêê 3 É~ ËÉ Î ÆÉÓ Ò e Î Æ ÍÇÉÇÉÇÍ ÉÊ u ÐÖÔÒ ÑÊÓ Ò e Ê É Ï ÑÖÐÒÏ ÔÊ u Î ÈÍÉÌÊ ÇÍ Ê ÐÖÔÎ eèéæç Î ÈÉ ÇÊ ÊÎÖÐÖÑÕÎ 8 Ê È v ÊÉ ÆÉ~ËÍ ÐÖÔ ) Î ÈÍÓ ÒÎ eèí ÐÖÔ) Ê ÈÍÓ Ò 0KK PÊÉ ÆÉ ÎsÆ Ó Ò 0K Ç ÐÖÔ )K Î ÉÉÇ ÐÖ Ô )K ÊÉÆÉ Ê Î È ÇÍÊ Î Ê Ë È É ÐÖÔ )K Ê ÊÆÍÈÉ Ó Ò 0K Ê ÇÈÎ ÈÍ Ó Ò 0K ÊÐÏÑ Ê ÆÐÖÔ ) Î Ê eèí Ó Ò 0K Ê ÐÖÔ )K ÎÔÒÓ ÐÈÍ uó ÒÊÐÖÔ ) Ê Î}ÈuÐÖ ÔÊ Ê ÈÍ ÐÖÔÒ ÑÊ ÊÓ Ò e ÊÎÖÐÖÑÕ 8 Ê ÈÉÎÖÐÖÑÕÊ ÐÖÔÊ Ê Ê ÐÖÔÊÓ Ò e Ê ÈÍÇÉÇÉÇ ÇÊ Î Ê Ë È ÇÉÊÍÉÉ ÐÖÔ ÎÓ ÒÊ ÊÍÊÈ Ê eèíçéçéçí 8 ÊÈÍÈÍÊ ÊÉÆÉ 9 Î ÆÉw ÈÍ 1 Ê 9(i)ÊÍÆÊ ÈÉÆÍ Ê ÐÖÔ ABC ÊÓ Ò eîsæ ÆÉ 2 ÊÍÆÊ Ó Ò ABC ÊÉÆÉ 3 6 ÎsÆ 3 ÉÊ 9(ii)ÊÍÆÊ Ó Ò C ÊÉÆ É ÐÖÔÊ eîsæ 9(ii)Ê ÊÍÆÊ uðöôéê Ê ÉÓ Ò e Îs Æ ÇÊ Ê 8 ÊÎÖÐÖÑÕÎ Ê Ë ÈÇÉÉ ÈÍ 4 ÉÊ 9(iii)ÊÍÆÊ Ê eè ÍÉ ÐÖÔÊÓÏ ÒÏ ÐÔÒÐÑÎuÓ Ò C Ê ÇÈÊ ÈÈ uó Ò C Î È Í Ó ÒÊ Ê Æ uó ÒÇ ÊÓ Ò É ÊÉÉÈÌÆÇÉÇÆÍ ÇÊÍÆÊ 5 ÊÆÆÉ ÊÍÇÊÇÊÍÍÆÊ uð ÖÔÊÓ ÒÎ eèí uçæí ÇÊ e Ê Ê ÊÐÖÔÇ eèííéëê ŠdÊ Ë ÈÍÍÉÌ ÍÇ ÈÍÉÌ Ê 3.2 É~ËÉ ÊÓ Ò e Î ÈÍ ÈÍÉuÓ ÒÊÃ ÃÊÔÖÐ Î ÉÉ 4(b) (f)é Ê Ê v Î ÈÍÇÉÊÍÍ ~Ê e Î ÈÍ ÊÆ 4 ÊÍÉÉ ÈÍÉuÓ Ò Ç Ê eèíéæíî ÐÉ ÈÉÈÌÆ h ÇÆÍ ÇÊ ŠÊ 3.4 ÉÌ~ËÍÍ ÉÆÍÍÆÊ ÊÆÆÉÊ ÊÓ ÒÉÎ ÐÊ Î ÈÍÇÉÎu ÈÉÊ ÆÊÆ ÇÊÍÆÊ ÊÉÆÉÌ Î Í ÇÍÆÊ Ê Î vèéæçé Æ 6 ÉÊ 9(iv)ÊÍÆÊ ÈÍÉuÓ ÒÊ eê Ê É eèíé ÐÖÔÎ ÔÒÓ ÐÈÍÇÉÉ Ê eèíéæíó ÒÉ ÊÍÊÈÊ ÐÖÔÊÓ ÒÎ eèí ÇÉÇÉÇÍ ÇÊÍÆÊ ÊÍÍ Ê ÊÐÖÔÎ Ê u ÈÍÇÉÇ héêí Õ Ð ÊÐÖÔÊ ÎÉÇÌÉÉ ÈÉÆ Êv ÊÐÖÔÎuÍÉÆÉÉ Ç hêê Í ÌÉ ÐÖÔÒ ÑÊ e Î Æ ÍÇÉÉ}Æ zêó ÒÎ}Æ eê eè ÍÇÉÇÉÇ ÐÖÔÊ uî ÇÍ ÌÆÍ ÐÖÔÒ ÑÊ u Ê ÎÒÑÑÖ Ò ÑÉÈÉ ÈÉ 8 Ê ÈÉ Ê~ Ê Ê uðöôê e ÇÍ uó ÒÎ ÈÉÆÇÇÉÊÍÍ ÐÖÔÇ eèíéæ Ç Ç ÇÍÍÆÊÊÉÉÆÍ
(i) (ii) (iii) (iv) ÐÖÔÒ ÑÊÓ Ò eê 9(iv)ÊÆÆÉ uó ÒÊ ÈÍÉ ÐÖ ÔÊÓ ÒÇÍ ÊÊÓ Ò A ÆÍË B Ê ÈÍ ÐÖÔÊÓ ÒË Î ÐÇ ÈÍÉÆ ÍÇÉÊÊÍÇ ÇÇÉÊ uó Ò C ÉuÓ Ò AÆÍË BÉÎ ËÎ ÐÉ sèés ÈÍ ÇÉÊÈÉÆÍ ÉÊ ÊÓ Ò Ê dçíîs ÈÍÇÉÍÍÌ ~É ÈÊ Ê ÎuÌÈÇÈÍÇÉÊ ÎÆÆÉ u ÎsÆ ÉfÆ uó Ò ÊÎ ÐÊÍ Í É Ó Ò Êt Ê Î sè És ÈÍÇÉÉs Çt ÊÊÍÊÎ ÆÉ ÆÍ ÊÆ Ó Ò ÊÎ ÐÊ Ê È ÍÉÆÍÊÉ ÊÓ ÒÎ ÈÉ ÊÎ ÐÎ ÈÍÇÉÌ héæíç ÇÇÉÊ ÈÊÎ ÐÇ ÊÓ ÒÌÎ ÐÉ ÈÍ ŠÊÉÆÉÊu ÈÉÆÊÆ Î ÐÎ ÈÉ Ê e Î Ó ÒÊ ÈÉ s ÈÍÇÉÉ Î Í ÇÇÉÊ héæíç ÇÍÊÍÉÉÐÖ Ô ÈÍÉÓ ÒÇ~ÇÊ eèííéæéé ŠÌ Ê ÎmÉÈ ŠÇÆÍ ÌÉ u ÊÐÖÔÒ ÑÊÆÆÉÊ ÊÈËÉÊÓ ÒÊ e ÎsÆÆÉÈÍÉ i Êv Ç uéêí ÊÍÍ v ÊÍÍÓ Ò eêv Ê n ÊÓ Ò Ê eîsæ v Ê ÊÊ Ê v ÈÍÍÇ 1 ÊÓ ÒÊ ÈÉ É n-1 C C F F E E D D 2 Êv ÎsÆÉÌ O( n ) ÉÆÍ ÈÇÈ ÐÖÔÒ ÑÎ ÆÍÇÉÉ ÐÖÔÉÊ ÊÆÓ Ò É e Îs ÆÇÉÇÉÇ ÐÖÔÊ e Ì Ê É ÌÊÉÐÖÔ Ê e Êv Î ÇÈÍÇÉÇÉÇÍÉfÆÍÍ Í Ê n ÊÓ ÒÊÐÖÔÊÉÆÉ k ÈÉÊÓ ÒÎ m ÊÐÖ ÔÊÍÇuÐÖÔ Î Í ÈÍÊ k ÈÉÊuÓ ÒÎÐÖ ÔÊ ÌÉÌÉ ÉÆÆ Î ÈÉ ÐÖ ÔÎ ÉÉÉÈÍ ÇÊÉÇÊ Ê ÈÊ log méêí ÐÖÔÊd Ê m log mé u ÌÍÇÉÇÉÇÍ ÇÊÉÇ 8 Ê ÈÉ ÊÓ Ò e Ê Ê m( log m) 2 É u ÌÍÇÉÇÉÇÍ ÌÉ ÐÖÔÒ ÑÊÓ Ò e ÉÊ v Êv Ì ÇÊÍÇ ÈÊv Ê v Êv É ÈÉ uéçíçíæ ÈÆ ÍÉÉ ÐÖÔÒ ÑÊ e ÊÆÇÍ v Ê 2 2 2 v Ê m( log m) O( k ) ÉÊÍ O( n ) ÍÍÌ ÊÆv ÉÊÍ ÊÓ Ò e Ê Î ÈÉÌÍÉ 16 ÊÍÆÊÊÍ ÐÖÔÒ Ñ e Ê s ÉÊ 3 ÆÍË 4 É ÈÉÐÖÔÒ Ñ e Î tèé sèé Î È fíê Î Microsoft Visual C++É tè IBM IntelliStation M Pro (Intel Pentium III 3.06 GHz RAM 1.0GB)ÆÍË Microsoft Windows XP ÊÉ sèé 10 Ê 3 É ÈÉ ÊÍÍÏ ÐÖÕ ÑÖÊÓ Ò e ÊÑÒÒÔÑÕÒÒÎ ÈÉÌÊÉÆÍ ÊÆÇÊÐÖÔÒ ÑÊ s 1 Ê ÈÍÉÆÍ 11ÊÐÖÔÒ ÑÉ ÿêð ÖÔÒ ÑÉÆÍ 11 ÆÍË 12 Ê 3 É ÈÉ ÊÍ ÍÏ ÐÖÕ ÑÖÊÓ Ò e É ÇÍÈËÉÊÓ ÒÎ eèíˆï ÐÖÕ ÑÖÊ ÊÍÍÓ Ò e Î ÈÉ Visual C++ÆÍË WindowsXP Ê Microsoft Ê ƒ IntelliStationÊ IBM Ê ƒ
ÌÊÉÆÍ ÇÇÉˆÏ ÐÖÕ ÑÖ ÉÊ ÈËÉÊÓ ÒÎ ˆ Ê } Ê Î ÉÈÉ ÈÈÍÇÉÉ eèé Ì ÉˆÏ ÐÖÕ ÑÖ É ÉÉÊ v Ê Ì ÊÊÎ ÿêèéæí Ê Î ÐÊ Î ÈÍÇÉÉ e Î v ÈÉÌÊÉÆÍ ÇÇÉÎ ÐÊ ÈÊ ÕÒÖ Ê Î 1 ÉÈÉ És ÈÉÆÍ ÈÊ Ç 1 Ê}ÆËÊj Ê eéæíéææí ÌÉÎ ÐÊ Ê ÊÆËÊj Ê eéæíé ÆÆÍ (1) (2) (3) (4) (5) (6) 10 ÊÍÍÏ ÐÖÕ ÑÖÊÓ Ò e ÊÑÒÒÔÑÕÒÒ s 1 11,12 Ê yéêíðöôò Ñ 11 12 Ó Ò 70 100 Î Ð 81 180 s 2 Ê (1) ( ÕÖ ) 11 12 ˆÏ ÐÖÕ ÑÖ 9542.5 19477.1 2483.7 4052.3 Ó Ò e Ê ÊˆÏ ÐÖÕ ÑÖ Ê 12 Ó Ò e Ê (2) ÊˆÏ ÐÖÕ ÑÖ Ê s 1 Ê 11 ÆÍË 12 Ê yéêíðöô Ò ÑÊÓ Ò ÆÍËÎ Ð Î ÈÉÌÊ ÉÆÍ s 2 Ê 11 ÆÍË 12 Ê Ê ÈÍ Î ÈÉÌÊÉÆÍ s 2 ÆÍËs 3 Ê 11 ÆÍË 12 Ê Ê ÈÉ Î ÐÊ È s 3 e Ê v (Î ÐÊ ÈÊ ) 11 12 ˆÏ ÐÖÕ ÑÖ 1.14 1.24 0.94 0.99 s 4 e Ê v (Î ÐÊ ) 11 12 ˆÏ ÐÖÕ ÑÖ 8 31 0 0 11 ÊÉÆÉÊ s 3 ÍÍÎ ÐÊ ÈÊÉ ÆÉÊ ÉÌ ÌÈÆ ÉÊÉÉÆÍ Ì És 4 ÍÍÎ ÐÊ ÊÉÆÉÌ ÉÌ ÊÇÊÉÉÆÍ ÈÇÈs 2 ÇÍÍÇÍÍÆÊ ÊËÆÇv Ê Ê ÈÆ 12 ÊÉÆÉÊ s 4 ÇÍÍÇÍÍÆÊ ˆ Ï ÐÖÕ ÑÖ ÉÊÎ ÐÊ Çˆ Ê ÆÇÉÇÍ ÊËÆÇ ÍÇÊj Ê e Î ÈÉÆÍ ÌÉs 2 ÇÍÍÇ ÍÍÆÊ ÊËÆÇv Ê Ê ÈÆ
13 Ê ÊÍÍ ÐÖÔÒ ÑÊ Ó Ò e ÊÑÒÒÔÑÕÒÒÎ ÈÉÌ ÊÉÆÍ 13(1) (4)Ê É ÈÉÓ ÒÎ ÈÈÊ ÐÖÔÎ ÈÍÇÉÉÓ Ò eîsæ Î ÈÉ 13(6)Ç ÊÓ Ò e ÉÆÍ 14 ÆÍË 15 Ê ÈÍÈÍ ÿêðöôê ÈÉ ÈÉÌÊÉ ÈÊÌÌÊ ÊÌ ÊÉÉ Ó Ò e ÎÈÉ Î ÈÉÌÊ ÆÍ ÇÊ ÇÍ ÐÖÔÒ ÑÊÓ Ò e ÉÊ Ó ÒÊÐÖ ÔÇ Ês ÈÍ ÐÖÔÊ Ê ~Î ÈÌÈÆÌÊ ÉÊÉÉÆÍ ÊÆ 14 15 16 É ÈÉÐÖÔÒ ÑÊ n 14 ÉÊ n=50 15 ÉÊ n=100 ÊÓ ÒÎÖ ÑÕÊÎ ÐÉ Ë ÐÖ ÔÊ ÈÐÖÔÊ ÈÉ Î ÐÉ ÈÍ 5 10 ÊÓ ÒÇ ÍÍÆÊÐÖ ÔÎ ÉÉ ÆÇ ÐÖ ÔÇÍÉÇÍÐÖÔÎ Ê ÈÉ ÍÍÉÌÊÉÆÍ s 5 Ê 14 15 ÈÍÈÍÊ e Ê Î ÈÉÌÊÉÆÍ ÌÉ 16 Ê ÐÖÔɈ ÐÖÔÊÓ Ò e Ê Î ÐÖÔÊÓ Ò É ÈÉ ÉÆÍ Ê ÈÌ ÐÖ ÔÊ ÈÍÓ Ò Ê~ÆÉ Ç ÈÍÇ ÊÐ ÖÔÒ ÑÊÓ Ò e ÊÍÉÉ ÍÇ ÐÖÔÊ e ÇsÍÍÉÆÍÇÉÇÍÇÍ s 5 Ê (2) ( ÕÖ ) 14 15 ~ ÊÐÖÔ 510.2 1993.1 ÐÖÔ 66.9 156.6 (1) (2) (3) (4) (5) (6) 13 ÊÍÍ ÐÖÔÒ ÑÊÓ Ò e ÊÑÒÒÔÑÕÒÒ 14 Ó Ò e Ê (3) ÿðöô Ê ÈÉ Ê ÈÓ Ò eîséé 15 Ó Ò e Ê (4) ÿðöô Ê ÈÉ Ê ÈÓ Ò eîséé
ªªª ~ ªªª ªªª 16 É~ ÊÐÖÔÒ ÑÊÓ Ò e Ê ÏÏÔÐÏÒuu ËÊ ÐÖÔÒ ÑÊ u ÉÈÉ ÇÇÉ ÊÏÏÔÐÏÒ u Î ÊÆÇÍ ÏÏÔÐÏ ÒÊ HTML uwév~èíéïïôô ÑÇÍ ÈÍ ÈÊÏÏÔÔ ÑÊ http://é ÌÍ ÔÑÒ É ÈÊÆÉÊ ÇÒÏÖÐÒÖ ÉÔ ÎÏÖ Éx ÈÍÍ ÌÉ ÏÏÔÔ ÑÊ HTMLÊÓÏÓ Ö ÐÊÍÉÉ ÊÏÏÔÔ ÑË ÈÍÍ ÇÇÉÊÏÏÔÐÏÒÊ ~Î ÏÏÔÔ ÑÎÓ Ò ÓÏÓ Ö ÐÎÎ Ð ÉÈ ÔÑÒ ÉÒÏÖÐÒÖ ÉÐÖ Ô ÈÉ ÐÖÔÒ ÑÉÈÉ u ÎsÆ ÒÒÔÔ Ñ / u /profile t /products Ï ÖÏ ÑÕÒÔ /shop ÑÔÒÏÏÎ /products/software } /products/hardware 17 ÏÏÔÐÏÒÊÒÏÖÐÒÖ É Ê ÿj ÊÏÏÔÐÏÒÊ ÉÈÉ 17 ÊÍÆÊ ~ÈÍ ÊÔ ÑÎ ÿòïöð ÒÖÊÌÉÌÉ ÈÍ ÇÍÇ ÍÍÍ Ò ÏÖÐÒÖ Î ÆÉ ÈÍÉÐÖÔÒ ÑÎ u ÈÍÇÉÊÍÍ ~Ê ÊÔ ÑÎÌÉÌÉs ÉÇ ÏÏÔÐÏÒÊ Î uèìèçêí ÊÐÖÔ ~Î ÆÍÇÉÉ ~ Îs ÈÍÉÉÌÊ ~Î ÆÉÏÏÔÐÏ Ò u [11][13][14]ÉÊs ÈÇÍÊÆÏ ÏÔÔ Ñ ÊÖ Ð ÎÌs ÉÇÍ ÇÆÍ ÌÉ ÊÏÏÔÔ ÑÎ e ÈÍÏÏÔÐÏÒ u [15][16]ÉÊ ÊÍ u Ê Î uéèèêÿ ˆÊÏÏ ÔÐÏÒÊ Î u ÉÇÍ ÇÆÍ Ì É ~Î ÆÊÆ ÐÖÔÒ ÑÊÍÍ u Ê ÏÏÔÔ Ñ ÊÖ ÐÊ Ç Ç ÉÉÌ Ê u ÊÊÉÉÈÌÆÇÉÇ ÆÍÇ ÈÐÖ Ô ÈÍÇÉÊÍÉÉ ÐÖ Ô ÊÖ ÐÉ Ô Ñ ÊÖ ÐÎ s ÈÍ Î ÆÍÇÉÉ Ö ÐÊ Îw ÈÍÇÉÇÉÇÍ ÇÆÍ Ê ÒÏÖÐ Ò ~Î ÆÉ ÈÍÉÏÏÔÐÏÒÉÆÍ Ê ÊÒÏÖÐÒÖËÊÖ ÐÍÍÌ ÿòï ÖÐÒÖ ÉÊÖ Ð ~Ê Ç uéæíç ÉÇ Ç ÐÖÔÒ ÑÊ u ÊÍÉÉ ÿòïöðòö ÊÔ ÑÊÖ Ð ~Îu ÌÈÇ ÈÍÇÉÇÉÇÍ ÏÏÔÐÏÒÊ ÐÖÔÎ ÈÍÊÊ ÒÒÔÔ ÑÇÍÖ ÐÎÉÊÍÇÉÊÍÉÉ Ó ÒÎ ÈÉÆÇ ÇÊÉÇ ÏÏÔÐÏÒ ÊÔ Ñ ÔÑÒ Ê~ÆÔ ÑÌÒÒÔÔ ÑÊ ÈÍÒÏÖÐÒÖ Ê Ê ÈÊÆ ÌÊ Ê ÈÐÖ ÔÊÌÉÌÉÆÇ ÈÍ ÊÖ ÐÊÉÊÍÊÆ ÌÉ Ê ËÊÖ ÐÌ ÊÉÊÉÉÔ ÑËÊÖ ÐÊ ÈÍ ÎÉÊÍÊÆ ÇÇÉÊ ÐÖÔÎ Æ ÍÉÌ ÊÔ ÑË ÍÍÆÊÖ ÐÊf È ÊÆ ÏÏÔÐÏÒ ÊÔ ÑÊÒÏÖÐÒÖ ÇÉÊÐÖ Ô È ÐÖÔÎ ÈÍ 18 ÊÏÏÔÐÏÒÎ ÐÖÔ ÈÓ
Ò eîsæ Ó Ò ÊÈÊÔ ÑÊÐÕÓ ÏÖÎs ÈÉ u ÉÆÍ ÇÊÍÆÊ u Ê Ê Î ÆÉ Ô ÑÊdÇÍÎ u ÈÊÇÍÏÏÔÐÏÒ ÎÒÓÐ ÒÈÍÇÉ Ç héæí 19 20 ÊÏÏÔÐÏÒÊ Î u È É ÉÆÍ 19 ÉÊÏÏÔÔ ÑÊ ÎÓ ÒÊjÉ ÈÉ zç } ÈÍÉÔ ÑÉ ˆÇ Ê ÈÍÉÇÍÊ Ê Ç ~ÈÉÔ ÑÉÆÍÇÉÎ ÈÉÆÍ ÌÉ 20 Ê 19 Ê ÆÉ Ô ÑÊÿ ÊÎÐÑÑ Î Ó ÒÊ ÇÈÉ ÈÉ ÉÆÍ ÇÊÍÆÊ ÎÐÑÑ Ì Š Ê Î ÈÇÉÉ Ï ÏÔÐÏÒÊ f ÇÊ Î ÏÏÔÐÏÒ Ê ~ÌÖ Ð ~É Ê u ÈÍÇÉ ÇÉÇÍ ÇÊÍÆÊ u Î ÆÍÇÉÉ ÆÊ ÊÆÍÔ ÑÉÈÊ ~ÈÍÔ Ñ ÎuÉÇÉÍ ÇŠdÊsÍÍÉÆÍÊÌ ÍÈÎÐÑÑÇ ÊÆÔ ÑÎuÉÇ ÈÊ ÊÈÊÔ ÑÊÉÊÍ ÇÌÉÊ Ê ÈÇ ŠÉÆÍÉÆÉÉÇÉÎ uèíéìê ÈÉÍ ÉÆÉÉ ÇfÆÍÍÍ ÊÆ 18 19 20 Ê ÈÏÏÔÐÏÒ Ê u ÉÊ 4.2 É~ËÉÍÆÊ ÈËÉ ÊÔ Ñ ÊÖ ÐÎ Ês ÈÍÇÉÊ Ç Ê ÊÔ Ñ ÊÖ ÐÊ uó Ò ÊÖ ÐÉ sèéô Ñ Ê Î sèíæêèíçéé Ö Ðs ÊÍÍ Ê ÆÎw ÈÍÍÆÊÈÉÆÍ ÈÇÈÊÇÍ ÇÊ ÉÊÆÍÔ ÑÇ ÊÊÔ ÑÇÍ ÈÍÉÆÍÉÆÆ Ê Î ÍÇÉÇÉÇ ÊÆ ÆÊ ÆÍÔ ÑÎ ÈÉ ÈÊÔ ÑÊdÇÍÖ ÐÊÌÎ Ês ÈÍÉÆÉ É u Ê Î Í ÍÉÆÇËÇÉÆÍÉ fæéæí ÌÉ f ÇÊ u Ê Ê ÇÉ ŠdÊ ÈÍÉÆÍÊÌÇÇÍÍÈ ÎÐÑÑ Ê ÊÆÔ ÑÎ uèí ÆÊ ÒÒÔÔ ÑÇÍÈÊÔ ÑËiÍÖ ÐÊÍ Í {ÊÌÎs ÈÍÉÆÉÉ u Ì ÉÆÍÉfÆÍÍÍ Ê ÇÊÍÆÊ Ê u ÎsÆ ÊÉÆÉÌ vèéæ ÇÉÆ ÏÏÔÔ ÑÊ u Ê ÉÈÉ ÒÑÑÖÒ ÑÎ ÈÉ 1 É Ê ÊÏÏÔÔ Ñ Ê u ÉÆÍ ÐÕÓÏÖÎÐÖÒÐÈÍ É ÊÔ ÑËsÇÇÉÇÉÇÍ 2 É Ê 19 20Ê ÈÍ Ê u ÉÆÍ 18 ÏÏÔÐÏÒÊ u Ê 19 ÏÏÔÔ ÑÊ Ê u
ÌÉ ÊÐÖÔ ~Î u ÈÍ É Õ Ð Ê ÊÍÉÉÆÇÊ Ê u ÎsÆÇÉ ÆÆ ÊÉÆÉ ÆÊ ÊÎ ÐÊs Ì Õ Ð Ê Ê Ês ÊÉÆ ÉÌ vèéæçéæ 20 ÏÏÔÐÏÒÊ Ê u ÌÈË w ÉÊ ÕÒÖÎ ÆÉÐÖÔÒ Ñuu Ê ÈÉ Ó ÒÎÏ ÐÖÕ ÑÖÊ 1 È É ˆ eèí ÉÆÆfÆ ÊÍÍ e ÆÍË Î ÈÍ Î ÈÉ ÌÉ ÇÊ Î ÐÖÔÒ ÑÊuu Ê ÈÍ Î ÈÉ ÌÉ ÇÍÍÊ Ê Ê ËÍ Î Œ É ÈÉÉÌÊ ÏÏÔÐÏÒÊuu Ê ÈÉ Î ÈÉ ÊwŠÉÈÉ ÏÏÔÐÏÒ Ê Ò ÑÊ ÈÉ Î È Êuu Î v ÈÍÇÉÇÆÇÍÍÍ ÌÉ fíê ÐÖÔÒ Ñuu Ê ÈÍ ~ ÉÈÉ Î ÐÊ d ÊÍÍ Î ÐÉÓ ÒÊ ÊÍ ÎÇÍ [19] ÐÖÔÒ ÑÎ Ê~u ÈÍ [20] Ì ÈÉÆÍÇ ÇÍÍÊ Ê w ÉÊÏÏÔ ÐÏÒÊuu Ê ÈÉÆÊÆ ÇÍÍÊ ÇÊ ÊÍÆÊ Ê ÉÇÍÇ ÊÉÆÉÌ vè ÉÆ f [1] Battista G. D., Eades P., Tamassia R., Tollis I. G., Graph Drawing Algorithms for the Visualization of Graphs, Prentice Hall, ISBN0-13-301615-3, 1999. [2] Herman I., Melancon G., Marshall M. S., Graph Visualization and Navigation in Information Visualization: A Survey, IEEE Transactions on Visualization and Computer Graphics, Vol. 6, No. 1, pp. 24-43, 2000. [3] Eades P., A Heuristic for Graph Drawing, Congressus Numerantium, Vol. 42, pp. 149-160, 1984. [4] Quigley A., Eades P., FADE: Graph Drawing, Clustering and Visual Abstraction, Symp. Graph Drawing 2000, 2000. [5] Bertault F., A Force-Directed Algorithm that Preserves Edge Crossing Properties, Graph Drawing 99, pp. 351-358, 1999. [6] Gansner E., et al., Improved Force-Directed Layouts, Graph Drawing '98, LNCS 1547, pp. 364-373, 1998. [7] Huang M. L., Eades P., Wang J., On-line Animated Visualization of Huge Graphs Using a Modified Spring Algorithm, Journal of Visual Languages and Computing, Vol. 9, pp. 623-645, 1998. [8] North S., Incremental Layout in DynaDAG, Graph Drawing 95, pp. 409-418, 1995. [9] P. Eades, et al., Multilevel Visualization of Clustered Graphs, Graph Drawing 96, pp. 101-112, 1996. [10] D. Schaffer, et al., Navigating Hierarchically Clustered Networks through Fisheye and Full-Zoom Methods, ACM Trans. Computer-Human Interaction, Vol. 3, No. 2, pp. 162-188, 1996. [11] Inxight Star Tree (TM) SDKs, http://www.inxight.com/products/sp/ht/sdk/index.html [12] Lamping J., Rao R., The Hyperbolic Browser: A Focus+context Technique for Visualizing Large Hierarchies, Journal of Visual Languages and Computing, Vol. 7, No. 1,
pp. 33-55, 1996. [13] Durand D., et al., MAPA: A System for Inducing and Visualizing Hierarchy in Web sites, 9th ACM Conference on Hypertext and Hypermedia, pp. 66-76, 1998. [14], o,,, Ò Ñuu ÃÒ Ñ ÃÉÏÏÔÐÏÒÊuu, w v Visul Computing, Vol. 32, No. 4, pp. 407-417, 2003. [15] Hendley R. J., Drew N. S., Wood A., Beale R., Narcissus: Visualizing Information, IEEE Information Visualization '95, pp. 90-96, 1995. [16], u,, Ã xóõ ÃÊ v Ê uu ÊÆÇÍ e Ç, w v, Vol. 38, No. 11, pp. 2331-2342, 1997. [17], ÕÒÖÊÍÍi ÕÒÑÕ, ÑÕ ÕÖ ÑÕ, 12, 1, 11-20, 1993. [18] LEDA, http://www.algorithmic-solutions.com/enleda.htm [19] o,,,,, ÕÒÖ Î ÆÉÐÖÔÒ ÑÊuu Ê j, ÐÖÔÏÐÑ &CAD, 2001-CG-103, pp. 7-12, 2001. [20] o ÐÖÔÒ ÑÊÉÌÊ u ÐÖÔÏÐÑÉ CAD Ñ ÔÑÏÕ 2001 pp.47-50,2001.