PB165 – Grafy a sítě Grafy a algoritmy v komunikačních sítích 21. září 2010 PB165 – Grafy a sítě Obsah předmětu 1 Síťové grafy 2 Plánování a rozvrhování na síťových grafech 3 Modelování sítí PB165 – Grafy a sítě 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ě 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ě 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ě Matematické modelování matematické struktury pro komunikační sítě a jejich rozhodovací problémy koncept neorientovaných grafů v sítích kombinatorická optimalizace PB165 – Grafy a sítě Matematické modelování – množiny a parametry základem modelování jsou definice množin a parametrů množina S je neuspořádaný soubor prvků stejného typu, typ může být velmi obecný kardinalitou S rozumíme počet prvků, prázdná množina má kardinalitu 0 parametrem rozumíme neměnnou hodnotu reprezentující numerický vstup do řešeného problému např. Šířka pásma vyjádřená v Mb/s PB165 – Grafy a sítě 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ňovaý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ě Grafy a síťě - příklady PB165 – Grafy a sítě Formální 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 V Vrcholy spojené hranou se nazývají sousední. Hrana se označuje jako incidentní k vrcholům, které spojuje. G = {a, b, c, d, e, f } V = { {a, b}, {a, c}, {b, c}, {e, f } } PB165 – Grafy a sítě 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ýva orientovaný. O hraně (u, v) říkáme, že vychází z vrcholu u a vstupuje do v. Graficky se orientace hrany označí šipkou ve směru, kterým hrana vede. PB165 – Grafy a sítě 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 G = {a, b, c, d, e} V = { (a, b), (a, c), (b, c), (a, d), (e, d) } PB165 – Grafy a sítě 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íh 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ě 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. 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ů (MSC1 ) 1 Message Sequence Charts PB165 – Grafy a sítě Ohodnocení – příklady Hranově ohodnocený graf Vrcholově ohodnocený graf PB165 – Grafy a sítě 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ě 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í vrchol počet odkazů na stránku vedoucích. vrchol deg− deg+ a 2 0 b 1 2 c 1 1 d 0 2 e 1 0 PB165 – Grafy a sítě 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). Transakce v SIP protokolu (viz SIP ellipse). Samostatný vrchol je také sledem. PB165 – Grafy a sítě 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ě Souvislost grafu Definice Neorientovaný graf se nazývá souvislý, pokud mezi každými dvěma jeho 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ě 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ě Isomorfismus grafů Grafy, lišící se např. nakreslením, označením vrcholů a hran, ohodnocením, se nemusejí lišit svojí strukturou – mohou být isomorfní. Definice Isomorfismus mezi grafy G, H je bijektivní zobrazení vrcholů, které zachovává hrany – tj. pokud vede v grafu G hrana mezi vrcholy u, v, pak v grafu H vede hrana mezi vrcholy f (u), f (v). Pokud mezi grafy G, H existuje isomorfismus, nazývají se isomorfní. Isomorfismus (jelikož je relací ekvivalence) tak definuje třídy grafů, které lze považovat za totožné. PB165 – Grafy a sítě Isomorfismus grafů Co musejí isomorfní grafy splňovat? Mít stejný počet vrcholů. Mít stejný počet hran. Jejich vrcholy musejí mít stejné stupně. V mnoha případech je snadné dokázat, že grafy isomorfní nejsou pomocí těchto (a některých dalších) invariantů. Jsou-li tyto invarianty shodné, je nutno vyloučit všechny možné isomorfismy. Důkaz isomorfie dvou grafů vyžaduje přímo nalezení konkrétního isomorfismu mezi těmito grafy. PB165 – Grafy a sítě Podgrafy Definice Graf H je podgrafem grafu G, pokud platí následující podmínky: 1 Vrcholy grafu H tvoří podmnožinou vrcholů grafu G. 2 Hrany grafu H tvoří podmnožinou hran grafu G. 3 Hrany grafu H mají oba vrcholy v H. Graf G je poté nadgrafem grafu H. Vyznačené vrcholy a hrany tvoří podgraf. Vyznačené vrcholy a hrany netvoří podgraf. PB165 – Grafy a sítě Indukované podgrafy Definice Podgraf H se nazývá indukovaný, pokud obsahuje všechny hrany, které mezi jeho vrcholy vedou v nadřazeném grafu G. Lokální síť je indukovaným podgrafem Internetu na fyzické vrstvě. Samostatné vrcholy libovolného grafu tvoří jeho podgraf. Vyznačené vrcholy a hrany tvoří indukovaný podgraf. Vyznačené vrcholy a hrany netvoří indukovaný podgraf. PB165 – Grafy a sítě 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ý nemusí PB165 – Grafy a sítě 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ě 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ě Seznamy sousedů Pro každý vrchol existuje samostatný seznam sousedů, s nimiž je tento 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ě 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ě Cvičení 1 Nakreslete všechny neisomorfní grafy na: 1 3 vrcholech 2 4 vrcholech 3 5 vrcholech 2 Dokažte, že platí y∈V (G) deg(y) = 2|E(G)| pro neorientovaný graf. 3 Mohou dva grafy, orientovaný a neorientovaný, mít stejné matice sousednosti a zároveň stejné počty hran? Jak takové grafy vypadají? 4 Uvažme orientovaný graf, který reprezentuje relace na množině vrcholů tak, že hrana spojuje právě ty prvky, které jsou spolu v relaci. Jakou strukturu bude mít graf reprezentující: 1 tranzitivní relaci 2 relaci ekvivalence PB165 – Grafy a sítě