ÿþ <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <title>EDITOR</title> <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=windows-1250"> <link rel="stylesheet" type="text/css" href="../style/style.css"> <script type="text/javascript" src="../js/showhide.js"></script> <script type="text/javascript" src="../js/rollover.js"></script> <style type="text/css"> /*<![CDATA[*/ .answer { display: none; } img { cursor: pointer; } /*]]>*/ </style> </head> <body> <div id="module">Grafy</div> <div id="unit">Grafy a jejich reprezentace</div><div id="print"><a href="javascript:window.print();"><img src="../img/tisk.gif" width="32" height="29" alt=" Vytisknout studijní materiál"></a></div> <p><h1>Grafy a jejich reprezentace</h1></p> <p></p> <p>Stromy vyjadYují njakou hierarchii vztaho. Velice obecným prostYedkem pro modelování vztaho mezi prvky jsou grafy. Prvky jsou vrcholy grafu a vztahy mezi nimi vyjadYujeme jejich spojením - hranami. PYíkladem mo~e být graf po íta ové sít CESNET na obr.<img src="../img/but1.gif" width="12" height="12" >. Msta jsou vrcholy a hrany znázorHují jejich spojení komunika ními linkami. Grafy nemusí znázorHovat jenom prostorové vztahy, ale napYíklad i asové, logické ap.</p> <p></p> <p></p> <p>Formáln je graf dvojice<i> G = (V, H)</i>, kde<i> V</i> je mno~ina vrcholo (uzlo) a<i> H</i> je mno~ina hran, pYi em~ hrana je dvojice<i> (u,v) u,v</i><font face="Symbol"><i>&#206;</i></font><i>V.</i> Po et vrcholo grafu<i> G</i> pak je |<i>V</i>| a po et jeho hran je |<i>H</i>|. Mno~inu vrcholo grafu<i> G</i> budeme zapisovat<i> V(G)</i> a mno~inu jeho hran<i> H(G)</i>.</p> <p></p> <p>Platí-li<i> (u,v) `" (v,u)</i> je hrana orientovaná, tj. má za áte ní a koncový vrchol. Takový graf nazýváme<i> orientovaný</i> a jsou v nich mo~né hrany z vrcholu do tého~ vrcholu. PYíklad orientovaného grafu je na obr.<img src="../img/but2.gif" width="12" height="12" >. Pro tento graf je</p> <p></p> <p><i>V = { 1, 2, 3, 4, 5, 6 }&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|V| = 6</i></p> <p><i>H = { (1,2) (1,6) (2,5) (3,5) (4,4) (5,6) (6,2) }&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|H| = 7</i></p> <p></p> <p></p> <p>StupeH vrcholu orientovaného grafu je dán sou tem po tu hran do nj vstupujících a po tu hran z nj vystupujících. NapYíklad stupeH vrcholu<i> 2</i> na obr.<img src="../img/but2.gif" width="12" height="12" > je<i> 3.</i></p> <p></p> <p>V opa ném pYípad<i> (u,v) = (v,u)</i> a graf se nazývá<i> neorientovaný,</i> pYi em~ budeme po~adovat<i> u `" v.</i> PYíklad neorientovaného grafu je na obr.<img src="../img/but3.gif" width="12" height="12" >. Pro tento graf je</p> <p></p> <p><i>V = { 1, 2, 3, 4, 5, 6 }&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|V| = 6</i></p> <p><i>H = { (1,2), (1,6), (2,3), (2,5), (2,6), (3,5), (5,6) }&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|H| = 7</i></p> <p></p> <p></p> <p>V neorientovaném grafu je stupeH vrcholu dán po tem incidentních hran, tj. hran, kterých je vrchol sou ástí. NapYíklad stupeH vrcholu<i> 2</i> na obr.<img src="../img/but3.gif" width="12" height="12" > je<i> 4.</i></p> <p></p> <p><h2>Reprezentace grafu</h2></p> <p></p> <p>Dva standardní zposoby v informatice pro reprezentaci grafu jsou</p> <p></p> <p> <ul> <li>seznamy sousednosti</li> <li>matice sousednosti.</li> </ul></p> <p></p> <p></p> <p>Oba zposoby jsou pou~itelné pro orientované i neorientované grafy.</p> <p></p> <p></p> <p><h3>Seznamy sousednosti</h3></p> <p></p> <p>Pro ka~dý vrchol grafu<i> G = (V, H)</i> je vytvoYen seznam sousedo. Seznam sousedo pro vrchol<i> u</i><font face="Symbol"><i> &#206;</i></font><i> V</i> obsahuje vaechny vrcholy<i> v</i>, pro které je<i> (u,v)</i><font face="Symbol"><i>&#206;</i></font><i>H</i>.<i></i> Sousedící vrcholy jsou obecn ulo~eny v seznamech v libovolném poYadí.</p> <p></p> <p>PYíklad reprezentace orientovaného grafu z obr.<img src="../img/but2.gif" width="12" height="12" > seznamy sousednosti je na obr.<img src="../img/but4.gif" width="12" height="12" >. Celková délka seznamo sousednosti pro orientovaný graf je zYejm |<i>H</i>|.</p> <p></p> <p></p> <p>PYíklad reprezentace neorientovaného grafu z obr.<img src="../img/but3.gif" width="12" height="12" > seznamy sousednosti je na obr.<img src="../img/but5.gif" width="12" height="12" >. Celková délka seznamo sousednosti pro orientovaný graf je zYejm 2|<i>H</i>|, proto~e je-li hrana<i> (u,v)</i><font face="Symbol"><i>&#206;&#32;</i></font><i> H</i>, potom<i> v</i> je v seznamu sousedo<i> u</i> a<i> u</i> je v seznamu sousedo<i> v</i>. Po~adovaná velikost pamti tedy v obou pYípadech je ˜<i>(|V| + |H|).</i></p> <p></p> <p></p> <p>Implementace reprezentace grafu seznamy sousednosti potom bude tvoYena polem vrcholy, kterého prvky reprezentují vrcholy grafu.</p> <p></p> <p class="programkod"><b>Vrchol[ ] vrcholy = new Vrchol [|V|];</b></p> <p></p> <p>V objektech tYídy<b> Vrchol</b> jsou ulo~ena data vrcholu a ukazatel<b> sousedi</b>. Tento obsahuje odkaz na prvního souseda seznamu sousedo anebo<b> null</b>, kdy~ vrchol nemá sousedy.</p> <p></p> <p class="programkod"><b>class Vrchol {</b></p> <p><b></b><font face="Courier New"><b> ...</b></font></p> <p><b></b><font face="Courier New"><b> Soused sousedi;</b></font></p> <p></p> <p><b></b><font face="Courier New"><b> Vrchol ( ) {</b></font></p> <p><b></b><font face="Courier New"><b> ...</b></font></p> <p><b></b><font face="Courier New"><b> sousedi = null;</b></font></p> <p><b></b><font face="Courier New"><b> }</b></font></p> <p class="programkod"><b>}</b></p> <p></p> <p>Objekty tYídy<b> Soused</b> obsahují íslo vrcholu, tj. jeho index v poli<b> vrcholy</b>, a ukazatel<b> dalsi</b> na dalaího souseda.</p> <p></p> <p class="programkod"><b>class Soused {</b></p> <p><b></b><font face="Courier New"><b> int vrchol;</b></font></p> <p><b></b><font face="Courier New"><b> Soused dalsi;</b></font></p> <p></p> <p class="programkod"><b> Soused (int v) {</b></p> <p><b></b><font face="Courier New"><b>&nbsp;&nbsp;&nbsp;&nbsp;...</b></font></p> <p><b></b><font face="Courier New"><b>&nbsp;&nbsp;&nbsp;&nbsp;vrchol = v;</b></font></p> <p><b></b><font face="Courier New"><b>&nbsp;&nbsp;&nbsp;&nbsp;dalsi = null;</b></font></p> <p><b></b><font face="Courier New"><b> }</b></font></p> <p class="programkod"><b>}</b></p> <p></p> <p>Hrany grafu pak budou vytváYeny metodou<b> hrana( )</b> tak, ~e vytvoYíme objekt tYídy<b> Soused</b> obsahující vrchol, do kterého hrana vede a vlo~íme ho do seznamu sousedo vrcholu, z kterého hrana vychází.</p> <p></p> <p><b></b><font face="Courier New"><b> void hrana(int z, int kam) {</b></font></p> <p><b></b><font face="Courier New"><b>&nbsp;&nbsp;&nbsp;&nbsp;Soused s = new Soused(kam);</b></font></p> <p><b></b><font face="Courier New"><b>&nbsp;&nbsp;&nbsp;&nbsp;s.dalsi = vrcholy[z].sousedi;</b></font></p> <p><b></b><font face="Courier New"><b>&nbsp;&nbsp;&nbsp;&nbsp;vrcholy[z].sousedi = s;</b></font><b></b></p> <p><b></b><font face="Courier New"><b> }</b></font></p> <p></p> <p>Poznamenejme, ~e vzhledem k tomu, ~e jsme Yekli, ~e na poYadí sousedo v jejich seznamu nezále~í, sousedy vkládáme pYímo na za átek jejich seznamu.</p> <p></p> <p>Reprezentace seznamem sousednosti je vhodná i pro ohodnocené grafy. Ohodnocením grafu<i> G</i> se nazývá funkce</p> <p></p> <p><i>w: H(G) -&gt</i><b> R</b></p> <p></p> <p>Je-li<i> (u,v)</i><font face="Symbol">&#206;</font><i>H(G), w(u,v)</i> se ulo~í ve vrcholu<i> v</i> seznamu sousedo vrcholu<i> u.</i> PYíkladem mo~e být ohodnocení hran reprezentujících po íta ovou síe pYenosovými rychlostmi.</p> <p></p> <p>Potenciální nevýhodou reprezentace grafu seznamy sousednosti je zjiaeování existence hrany<i> (u,v),</i> co~<i></i> znamená hledat vrchol<i> v</i> v seznamu sousedo vrcholu<i> u.</i></p> <p></p> <p></p> <p><h3>Matice sousednosti</h3></p> <p></p> <p>Ozna me vrcholy ísly<i> 1, & , |V</i>|. Matice sousednosti je matice<i> S = (s</i><i><sub>ij</sub></i><i> ), i,j = 1, & , |V|</i>, pYi em~</p> <p></p> <p>je-li<i>&nbsp;&nbsp;&nbsp;&nbsp;(i,j)</i><font face="Symbol"><i>&#206;</i></font><i>H, s</i><i><sub>ij</sub></i><i> = 1</i></p> <p>jinak<i>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s</i><i><sub>ij</sub></i><i> = 0</i></p> <p></p> <p>Reprezentace orientovaného grafu z obr.<img src="../img/but2.gif" width="12" height="12" > maticí sousednosti je na obr.<img src="../img/but6.gif" width="12" height="12" > a reprezentace neorientovaného grafu z obr.<img src="../img/but3.gif" width="12" height="12" > maticí sousednosti je na obr.<img src="../img/but7.gif" width="12" height="12" >. Po~adovaná pame je ˜<i>( |V |</i><i><sup>2</sup></i><i>)</i>, bez ohledu na po et hran. Pro neorientovaný graf je<i> S = S</i><i><sup>T</sup></i><i>,</i> kde<i> S</i><i><sup>T</sup></i> je transponovaná matice, co~ umo~Huje sní~it nároky na pame témY na polovinu.</p> <p></p> <p></p> <p></p> <p>Dalaí mo~ností sní~ení nároko na pame pro orientovaný i neorientovaný graf je ulo~ení matice sousednosti v bitech, co~ vaak vy~aduje bitové operace.</p> <p></p> <p>Graf je pYi reprezentaci maticí sousednosti implementován dvourozmrným polem</p> <p></p> <p class="programkod"><b>int[ ][ ] s = new int [|V|] [|V|];</b></p> <p></p> <p>Maticí sousednosti lze implementovat i ohodnocený graf. Pro ohodnocený graf je</p> <p></p> <p><i> s</i><i><sub>uv</sub></i><i> = w(u,v),</i> je-li<i> (u,v)</i><font face="Symbol"><i>&#206;</i></font><i>H(G),</i></p> <p><i> s</i><i><sub>uv</sub></i><i></i>&nbsp;&nbsp;&nbsp;je hodnota mimo hodnot mo~ných ohodnocení, není-li<i> (u,v)</i><font face="Symbol"><i>&#206;</i></font><i>H(G).</i></p> <p></p> <p>Je-li&nbsp;&nbsp;&nbsp;|<i>H</i>| &lt&lt |<i>V</i>|<sup>2</sup>&nbsp;&nbsp;&nbsp;graf se nazývá<i> Yídký</i> a obvykle je vhodnjaí pou~ít seznam sousednosti. Je-li&nbsp;&nbsp;&nbsp;|<i>H</i>| ~ |<i>V</i>|<sup>2</sup>&nbsp;&nbsp;&nbsp;&nbsp;graf se nazývá<i> hustý</i> a obvykle je vhodnjaí pou~ít matici sousednosti. Matici sousednosti je vhodnjaí pou~ít také, je-li nutno rychle zjistit existenci hrany.</p> <p></p> <p></p> <!-- Tato stranka byla vygenerovana pomoci aplikace ProAuthor --> </body> </html></body> </html>