PB165 – Grafy a sítě Grafy a algoritmy v komunikačních sítích PB165 – Grafy a sítě 1/51 Organizační pokyny Průsvitky pruběžná aktualizace v IS Studijní materiály Odpovědníky v IS příklady na procvičení k jednotlivým přednáškám procvičení i dalších základních grafových témat, které byste měli znát Hodnocení vnitrosemestrální písemná práce body započítány 20% do výsledné známky termín: na páté (15.10.) nebo šesté (22.10.) přednášce, upřesněno nejpozději 1.10. 50 minut, cca 5 příkladů z obsahu proběhlých přednášek závěrečná písemná práce body započítány 80% do výsledné známky podle dosažených procent: A 100, 89), B 89, 79), C 79, 69), D 69, 59), E 59, 55 PB165 – Grafy a sítě 2/51 Obsah předmětu Návaznost na IB000 Matematické základy informatiky zopakujte si studijní materiály IB000 ke grafům vybrané hlavní koncepty stručně zopakujeme 1 Síťové grafy 1-2 přednášky, Rudová 2 Plánování a rozvrhování na síťových grafech 4-5 přednášek, Rudová 3 Modelování sítí Hladká & Matyska PB165 – Grafy a sítě 3/51 Obsah první části předmětu 1 Úvod do technik diskrétní matematiky pro podporu návrhu a řízení komunikačních sítí 2 Grafově teoretický koncept 3 Ukázky aplikací v komunikačních sítích PB165 – Grafy a sítě 4/51 Proč diskrétní matematika a sítě? Teorie grafů je důkladně rozpracována a nabízí mnoho využitelných algoritmů. Graf představuje velmi přímočarou reprezentaci sítě na všech úrovních OSI modelu, např.: Síťové prvky a jejich fyzické propojení na nejnižší vrstvě, síťové aplikace a TCP spojení mezi nimi na transportní vrstvě, procesy distribuovaného výpočtu a jejich komunikace na aplikační vrstvě. Grafy nacházejí využití i v návrhu síťových protokolů a jejich formální verifikaci. PB165 – Grafy a sítě 5/51 Diskrétní matematika Diskrétní struktury grafy hypergrafy kombinatorika Algoritmy procedurální popis „krok za krokem“ problémů, které nelze řešit bezprostředně složitost, NP - těžké problémy Matematická optimalizace vývoj a implementace pro podporu rozhodování problém návrhu sítí, identifikace úzkých míst obchodní aspekty sítí modeluje se grafy Distribuované výpočty síť jako distribuovaný systém příklad směrovací algoritmy, P2P sítě PB165 – Grafy a sítě 6/51 Obsah: Typy grafů používané v počítačových sítích Graf, orientovaný graf, ohodnocený graf opakování Multigraf Strom opakování Kořenový strom n-ární strom, uspořádaný strom Binární strom + Aplikace grafů v počítačových sítích Implementace grafů PB165 – Grafy a sítě 7/51 Grafy a sítě Nejjednodušší diskrétní strukturou pro modelování síťových problémů jsou grafy. Intuitivně se graf skládá z: Vrcholů (uzlů), znázorňovaných schematicky jako „body“, hran spojujících vrcholy. Co lze reprezentovat grafem? Mapu měst a silničního spojení, atomy v molekule a jejich vazby, vodovodní, elektrické sítě a zejména počítačové sítě. Označován také jako jednoduchý graf. PB165 – Grafy a sítě 8/51 Grafy a síťě - příklady PB165 – Grafy a sítě 9/51 Opakování: definice grafu Definice Graf G je uspořádaná dvojice množin (V , E), kde V je množina vrcholů a E je množina hran – dvouprvkových podmnožin množiny V Vrcholy spojené hranou se nazývají sousední. Hrana se označuje jako incidentní k vrcholům, které spojuje. V = {a, b, c, d, e, f } E = { {a, b}, {a, c}, {b, c}, {e, f } } PB165 – Grafy a sítě 10/51 Opakování: Orientovaný graf Hrany v grafu, jak byly definovány, spojují dva rovnocenné vrcholy. Takové grafy se také nazývají neorientované. U hran ovšem můžeme vyznačit směr, kterým vedou – hrany i graf se poté nazývají orientované. Definice Graf, jehož hrany jsou uspořádané dvojice vrcholů, se nazývá orientovaný. O hraně (u, v) říkáme, že vychází z vrcholu u a vstupuje do vrcholu v. Graficky se orientace hrany označí šipkou ve směru, kterým hrana vede. PB165 – Grafy a sítě 11/51 Orientovaný graf - příklady Kde najdeme orientované grafy v sítích? Webové stránky – graf odkazů DNS – hierarchická struktura domén, serverů Směrování – graf cest paketů k cíli V = {a, b, c, d, e} E = { (a, b), (a, c), (b, c), (a, d), (e, d) } PB165 – Grafy a sítě 12/51 Multigraf Definice grafu povoluje nejvýše 1 hranu mezi každou dvojicí vrcholů a požaduje, aby hrana spojovala různé vrcholy. Tato omezení odstraňuje multigraf: Definice Multigraf je graf, jenž nahrazuje množinu hran multimnožinou (smí obsahovat násobné prvky) a umožňuje existenci smyček – hran spojujících vrchol sám ze sebou. Multigraf lépe odpovídá reálným fyzickým sítím, kde se často vyskytují redundantní linky. Smyčky mohou znázornit např. loopback – rozhraní přijímající zprávy, které samo vysílá. PB165 – Grafy a sítě 13/51 Opakování: Ohodnocení grafu Vrcholům a hranám je možné přiřadit např. číslo či barvu. Definice Přiřazení prvků konečné množiny vrcholům či hranám grafu nazýváme jejich ohodnocením. Hranově ohodnocený graf Vrcholově ohodnocený graf PB165 – Grafy a sítě 14/51 Příklady ohodnocení na sítích Ohodnocení síťových zařízení L2 a L3 adresami (viz ARP protokol) Šířka pásma, latence, cena přenosu za jednotku dat jako ohodnocení linek – hran Ohodnocení vrcholů názvem stavu, hran typem zprávy při abstraktním návrhu protokolů (MSC – Message Sequence Charts) MSC datového přenosu pro TCP PB165 – Grafy a sítě 15/51 Stupeň vrcholu Definice Stupněm vrcholu v neorientovaném grafu nazýváme počet hran incidentních k vrcholu. Počet klientů připojených k Wi-Fi AP Počet uzavřených spojení spojovaného protokolu (např. TCP) Stupeň vrcholu u značíme deg(u). deg(a) = 1 deg(b) = 2 deg(c) = 1 deg(d) = 0 deg(a) = 3 deg(b) = 1 deg(c) = 4 deg(d) = 0 PB165 – Grafy a sítě 16/51 Stupeň vrcholu v orientovaném grafu V případě orientovaného grafu rozlišujeme vstupní a výstupní stupeň. Definice Vstupním (výstupním) stupněm vrcholu u neorientovaného grafu nazýváme počet hran vstupujících do, resp. vycházejících z vrcholu u a značíme jej deg+(u), resp. deg−(u). V grafu odkazů mezi webovými stránkami reprezentuje vstupní stupeň počet odkazů na vedoucích stránku. vrchol deg− deg+ a 2 0 b 1 2 c 1 1 d 0 2 e 1 0 PB165 – Grafy a sítě 17/51 Sledy v grafu Definice Sledem v grafu (neorientovaném grafu) nazýváme posloupnost vrcholů a hran v0, e1, v1, . . . , en, vn, kde každá hrana ei spojuje vrcholy vi−1, vi , resp. vede z vi−1 do vi . Sled v grafu je tedy „trasou“, na které se mohou vrcholy i hrany opakovat. Se sledy se lze setkat i v reálných sítích: Cesta paketu sítí (některé směrovací algoritmy nezabraňují zacyklení paketu v průběhu výpočtu). Samostatný vrchol je také sledem. PB165 – Grafy a sítě 18/51 Cesty v grafu Definice Cesta v grafu je sled bez opakování vrcholů. V cestě se v důsledku neopakování vrcholů nemohou opakovat ani hrany. Cesty definující směrování paketů mezi dvojicemi síťových prvků. b, e3, c, e4, d, e2, b je sledem v grafu, ale nikoliv cestou – vrchol b se opakuje. a, e1, b, e2, d, e5, e je sledem i cestou v grafu. PB165 – Grafy a sítě 19/51 Souvislost grafu Definice Neorientovaný graf se nazývá souvislý, pokud mezi jeho každými dvěma vrcholy vede cesta. Definice Nahradíme-li všechny hrany orientovaného grafu G neorientovanými a získáme-li tak souvislý graf, G je slabě souvislý. Orientovaný graf je silně souvislý, pokud mezi každými dvěma jeho vrcholy vedou cesty v obou směrech. Tento graf je souvislý; po odebrání vyznačené hrany by souvislý nebyl, odebrání jedné z nevyznačených hran by jeho souvislost zachovalo. PB165 – Grafy a sítě 20/51 Souvislost grafu – příklady Internet na fyzické vrstvě tvoří souvislý graf. Internet na IP vrstvě tvoří slabě souvislý (ovšem silně nesouvislý) orientovaný graf (adresy za NAT). Orientovaný graf webových stránek není silně ani slabě souvislý. Grafy na obrázcích jsou: 1 Nesouvislý 2 Slabě souvislý 3 Silně souvislý PB165 – Grafy a sítě 21/51 Implementace grafu Jak efektivně uložit graf v paměti počítače či aktivního síťového prvku? Vrcholy označíme čísly 1 . . . n. Pro uložení hran máme dvě základní možnosti: matice sousednosti, seznamy sousedů. Matice sousednosti matice E o rozměrech n × n pro n vrcholů grafu Eij = 1 pokud hrana (i, j) patří do grafu Eij = 0 jinak pro neorientovaný graf je symetrická pro orientovaný graf nemusí být symetrická PB165 – Grafy a sítě 22/51 Matice sousednosti a b c d e a 0 0 1 0 0 b 0 0 1 1 0 c 1 1 0 0 1 d 0 1 0 0 0 e 0 0 1 0 0 V této podobě je matice sousednosti vhodná jen pro reprezentaci jednoduchého grafu. Multigraf lze reprezentovat maticí sousednosti, jejíž prvky udávají počet hran mezi každými dvěma vrcholy: a b c d e a 0 0 1 0 0 b 0 0 2 2 0 c 1 2 0 0 1 d 0 2 0 1 0 e 0 0 1 0 1 Obdobně lze ukládat jednoduchý hranově ohodnocený graf. PB165 – Grafy a sítě 23/51 Matice sousednosti pro orientovaný multigraf a b c d e a 0 0 1 0 0 b 0 0 1 0 0 c 0 1 0 0 1 d 0 2 0 1 0 e 0 0 0 0 1 PB165 – Grafy a sítě 24/51 Seznamy sousedů Pro každý vrchol existuje samostatný seznam sousedů, s nimiž je vrchol spojen hranou (či do nich vede orientovaná hrana). Lze implementovat pomocí 2 jednorozměrných polí: V jednom jsou uloženy všechny seznamy za sebou, seřazené podle čísla vrcholu Druhé uchovává indexy, na kterých začínají v prvním poli sousedé každého vrcholu Násobné hrany v multigrafu jsou zadány násobným uvedením vrcholu v seznamu sousedů Pro „řídké“ grafy (výrazně méně než n2 hran) jsou seznamy sousedů výhodnější z hlediska paměťové náročnosti než matice sousednosti. Takových grafů je mezi sítěmi většina. PB165 – Grafy a sítě 25/51 Seznamy sousedů – příklad Pole indexů do seznamu sousedů: a b c d e 1 2 6 10 13 Seznam sousedů: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 c c c d d a b b e b b d c e PB165 – Grafy a sítě 26/51 Kružnice a cyklus v grafu Definice Kružnice (uzavřená cesta) v grafu je netriviální ∗ neorientovaná cesta, která začíná i končí ve stejném vrcholu. Orientovaná kružnice (také cyklus) je kružnice složená z orientovaných hran respektující orientaci těchto hran. ∗ triviální cesta obsahuje jeden vrchol Příklady V Internetu existuje mnoho redundantních linek – graf jeho fyzického propojení je cyklický. Lokální ethernetové sítě mají acyklickou topologii. Sítě založené na technologii Token Ring mají logickou kruhovou topologii. Sítě SONET podporují zapojení do kruhu. PB165 – Grafy a sítě 27/51 Topologie sítě CESNET PB165 – Grafy a sítě 28/51 Topologie sítě GÉANT PB165 – Grafy a sítě 29/51 Opakování: Strom Definice Les je graf, který neobsahuje kružnice. Strom je graf, který neobsahuje kružnice a je souvislý. Strom je tedy souvislý les. Lokální ethernetová síť je strom, protože je souvislá a acyklická. Jednoduchý příklad stromu PB165 – Grafy a sítě 30/51 Kořenový strom Definice Strom, jehož hrany jsou orientované, se nazývá také orientovaný. Orientovaný strom, jenž má určen význačný vrchol (kořen) r, a v němž existuje orientovaná cesta z r do všech ostatních vrcholů, se nazývá kořenový strom. Při kreslení kořenových grafů se obvykle vynechávají šipky definující orientaci hran, předpokládá se, že směřují „od kořene“. Vzhledem k absenci cyklů je interpretace jednoznačná. PB165 – Grafy a sítě 31/51 Kořenový strom – příklady Kde v sítích najdeme kořenové stromy? DNS – hierarchická struktura serverů obsluhujících domény různých úrovní. Multicast – zdroj je kořenem, cesty k příjemcům tvoří strom. Dvě obvyklá kreslení kořenového stromu. Kořen je vyznačen modře. PB165 – Grafy a sítě 32/51 Vztah orientovaných a kořenových stromů Každý kořenový strom je orientovaný. Jaké jsou podmínky pro to, aby byl orientovaný strom zároveň kořenovým? Věta Orientovaný strom je kořenový právě tehdy, když právě jeden z jeho vrcholů má vstupní stupeň 0 a všechny ostatní vrcholy 1. Důkaz. ⇒ Nechť r je kořen stromu a jeho vstupní stupeň je vyšší než 0. Potom do něj vede hrana z některého z ostatních vrcholů stromu. Do toho ovšem vede cesta z kořene, v grafu je tedy cyklus, čímž docházíme ke sporu. Pokud do některého z ostatních vrcholů (označme jej u) vedou více než 2 hrany (z různých vrcholů v, w), potom do něj vedou 2 cesty z kořene, a to skrze cesty do v, w. Tím opět docházíme ke sporu. PB165 – Grafy a sítě 33/51 Vztah orientovaných a kořenových stromů – pokračování důkazu Orientovaný strom je kořenový právě tehdy, když právě jeden z jeho vrcholů má vstupní stupeň 0 a všechny ostatní vrcholy 1. Důkaz. ⇐ Označme r vrchol, jehož vstupní stupeň je 0. Poté pro každý jiný vrchol w platí následující: Vstupní stupeň w je roven 1. Existuje tedy právě jeden vrchol, u1, z nějž vede do w hrana. Není-li u1 totožný s r, vede do něj opět hrana z právě jednoho vrcholu, u2. Takto tvořená řada vrcholů, z nichž vede cesta do w, je nutně konečná, neboť strom je acyklický, tudíž se v ní žádný z vrcholů nemůže opakovat. Posledním vrcholem v této posloupnosti musí být r. Do každého vrcholu stromu tedy vede orientovaná cesta z vrcholu r a ten je tudíž kořenem stromu. PB165 – Grafy a sítě 34/51 Hloubka vrcholů a výška stromů Definice Vzdálenost (počet hran na cestě) vrcholu od kořene stromu se nazývá hloubka či úroveň vrcholu. Hloubka kořene je rovna 0. Je zvykem kreslit vrcholy jedné úrovně ve stejné výšce. Definice Výškou kořenového stromu označujeme nejvyšší z hloubek všech jeho vrcholů. PB165 – Grafy a sítě 35/51 Rodiče a sourozenci v kořenových stromech Definice Vede-li v kořenovém stromu hrana z vrcholu u do v, nazývá se u rodičem (otcem) v a v synem (potomkem). Vrcholy mající společného rodiče nazýváme sourozenci. Vrchol u je rodičem obou vrcholů v, w, které jsou sourozenci. PB165 – Grafy a sítě 36/51 Listy a vnitřní vrcholy stromu Definice Vrchol u je předkem vrcholu v, pokud leží na cestě z r do v. v se v takovém případě nazývá následníkem vrcholu u. Vrcholy v, w, x jsou následníky vrcholu u. Vrchol w má jediného následníka x. Předky x jsou u, w. Listy jsou vyznačeny zeleně, vnitřní vrcholy stromu hnědě. Definice Vrchol, který nemá žádné potomky, nazýváme list stromu. Ostatní vrcholy se označují jako vnitřní. PB165 – Grafy a sítě 37/51 n-ární, úplné stromy Definice Kořenový strom, jehož každý vrchol má nejvýše n potomků, se nazývá n-ární. n-ární strom, jehož vnitřní vrcholy mají právě n potomků a všechny listy jsou stejné hloubky, se nazývá úplný n-ární. Levý strom je 3-ární (ternární), pravý je úplný ternární. PB165 – Grafy a sítě 38/51 Uspořádané stromy V některých případech může být výhodné potomky každého vrcholu jednoznačně pojmenovat a seřadit: Definice Uspořádaný strom je kořenový strom s daným pořadím potomků každého vrcholu. Při kreslení uspořádaného grafu se dané pořadí vrcholů dodržuje ve směru zleva doprava. Isomorfní ∗ kořenové stromy s různým uspořádáním. ∗ Zopakujte si pojem isomorfismus. PB165 – Grafy a sítě 39/51 Počet vrcholů úrovně stromu Pro každou úroveň n-árního stromu je dán limit počtu vrcholů v této úrovni: Věta V m-té úrovni n-árního stromu se nachází nejvýše nm vrcholů. Důkaz. Indukcí: Pro kořen platí triviálně: n0 = 1. Nechť je v úrovni k právě nk vrcholů. Každý z nich může mít nejvýše n potomků. Úroveň k + 1 tedy obsahuje nejvýše n ∗ nk = nk+1 vrcholů. PB165 – Grafy a sítě 40/51 Kořenové stromy – cvičení 1 Nakreslete, nebo zdůvodněte, proč to není možné: 1 Binární strom výšky 5 s právě 12 vrcholy a právě 5 listy. 2 Binární strom výšky 3 s právě 12 vrcholy. 2 Kolik existuje různých neúplných ternárních stromů výšky 3 takových, že každý vnitřní vrchol má právě 3 potomky? PB165 – Grafy a sítě 41/51 Binární stromy Speciálním (a prakticky nejpoužívanějším) n-árním stromem je strom binární. Definice Uspořádaný 2-ární strom se nazývá binární. Potomci každého vrcholu jsou označováni jako levý a pravý. Každý kořenový strom lze převést na binární. Vnitřní algoritmy směrovacích zařízení mohou být založeny na binárních stromech. PB165 – Grafy a sítě 42/51 Podstromy binárních stromů Definice Indukovaný podgraf∗ binárního stromu G, tvořený jedním potomkem vrcholu v a všemi jeho následníky, se nazývá podstromem vrcholu v a stromu G. Podstrom binárního stromu je také binárním stromem. Každý vrchol má levý a pravý podstrom, přičemž jeho levý, resp. pravý, potomek je kořenem tohoto podstromu. Pravý a levý podstrom binárního stromu o výšce h mají výšku nejvýše h − 1, přičemž nejméně jeden z nich má výšku právě h − 1. ∗ Zopakujte si pojmy podgraf a indukovaný podgraf. PB165 – Grafy a sítě 43/51 Podstromy binárních stromů – příklad Obrázek: Levý a pravý podstrom kořene stromu. PB165 – Grafy a sítě 44/51 Počet vrcholů úplného binárního stromu Věta Úplný binární strom výšky h má právě 2h+1 − 1 vrcholů. Důkaz. Indukcí: Pro binární strom výšky 0 platí zřejmě. Nechť strom výšky k má právě 2k+1 − 1 vrcholů. Jak bylo dokázáno dříve ∗, (k + 1)-ní vrstva obsahuje 2k+1 vrcholů. Strom výšky k + 1 tedy má 2k+1 − 1 + 2k+1 = 2 ∗ 2k+1 − 1 = 2k+2 − 1 vrcholů. ∗ Víme: V m-té úrovni n-árního stromu se nachází nejvýše nm . vrcholů. PB165 – Grafy a sítě 45/51 Reprezentace kořenových stromů Kořenové stromy lze jednoznačně reprezentovat polem rodičů – tedy polem, ve kterém je pro každý vrchol uložen pouze název jeho rodiče. Taková reprezentace je prostorově velmi výhodná (lineární prostorová složitost). Pole rodičů má tvar: - 0 0 0 2 2 3. Cvičení: Nakreslete kořenový strom podle zadaného pole rodičů: - 0 1 1 2 2 3 4 4 PB165 – Grafy a sítě 46/51 Reprezentace úplných ohodnocených stromů Obdobně výhodně lze reprezentovat úplné ohodnocené stromy. Každý vrchol může mít v lineárním poli pevně danou pozici. Na této pozici je v poli uloženo ohodnocení vrcholu. Konkrétně pro binární strom: Kořen je uložen na pozici 0. Potomci vrcholu k jsou uloženi na pozicích 2 ∗ k + 1, 2 ∗ k + 2. Pole reprezentující tento binární graf obsahuje hodnoty g r n e v i q. PB165 – Grafy a sítě 47/51 Průchod binárním stromem V některých případech (např. synchronizace distribuovaných algoritmů a výpočtů) je potřebné projít všemi vrcholy grafu a vykonat nějakou akci. Průchod binárním stromem je možné provést 2 základními způsoby: 1 průchod po úrovních 2 průchod po podstromech PB165 – Grafy a sítě 48/51 Průchod binárním stromem po úrovních Vlož kořen do fronty. Dokud je fronta neprázdná: Odstraň její první vrchol a proveď akci. Vlož do fronty jeho potomky v daném pořadí. Vrcholy stromu jsou navštíveny v pořadí a, b, c, d, e, f , g, h, i, j, k, l. PB165 – Grafy a sítě 49/51 Průchod binárním stromem po podstromech Proveď akci v kořenu stromu. Spusť algoritmus průchodu v levém podstromu. Spusť algoritmus průchodu v pravém podstromu. Tato verze algoritmu je rekurzivní. Průchod je možné implementovat iterativně bez rekurzivních volání za použití zásobníku. Akci lze také provádět po průchodu levým či oběma podstromy. PB165 – Grafy a sítě 50/51 Průchod po podstromech – příklad Vrcholy stromu jsou navštíveny v pořadí a, b, d, h, l, e, i, j, c, f , g, k. Cvičení: V jakém pořadí budou vypsány vrcholy, pokud bude výpis vrcholu proveden 1) po průchodu levým podstromem; 2) po průchodu oběma podstromy? PB165 – Grafy a sítě 51/51