1 Pojem grafu Grafy jsou jedním z nejdůležitějších pojmů diskrétní matematiky. Neformálně, graf se skládá z • vrcholů neboli také uzlů ("puntíků") • a hran ("spojnic") mezi dvojicemi vrcholů. (Pozor, nepleťme si graf s grafem funkce!) Petr Hliněný, Fl MU Brn MA010 "Grafy": Pojem grafu 1 Pojem grafu Grafy jsou jedním z nejdůležitějších pojmů diskrétní matematiky. Neformálně, graf se skládá z • vrcholů neboli také uzlů ("puntíků") • a hran ("spojnic") mezi dvojicemi vrcholů. (Pozor, nepleťme si graf s grafem funkce!) Takový graf může vyjadřovat souvislosti mezi objekty, návaznosti, spojení nebo toky, atd. Své důležité místo v informatice si grafy získaly dobře vyváženou kombinací svých vlastností -snadným názorným nakreslením a zároveň jednoduchou zpracovatelností na počítačích. Stručný přehled lekce • zavedení a pochopení grafů, jejich základní pojmy, • příklady běžných tříd grafů, • stupně vrcholů v grafech, • podgrafy isomorfismus grafů a jeho poznání. Petr Hliněný, Fl MU Brn MA010 "Grafy": Pojem grafu 1.1 Definice grafu Definice 1.1. Graf (rozšířeně obyčejný či jednoduchý neorientovaný graf) je uspořádaná dvojice G = (V, E), kde V je množina vrcholů a E je množina hran ■ množina vybraných dvouprvkových podmnožin množiny vrcholů. Značení: Hranu mezi vrcholy u a v píšeme jako {u,v}, nebo zkráceně uv. Vrcholy spojené hranou jsou sousední. Na množinu vrcholů grafu G odkazujeme jako na V(G), na množinu hran E(G). Petr Hliněný, Fl MU Brn MA010 "Grafy": Pojem grafu 1.1 Definice grafu Definice 1.1. Graf (rozšířeně obyčejný či jednoduchý neorientovaný graf) je uspořádaná dvojice G = (V, E), kde V je množina vrcholů a E je množina hran - množina vybraných dvouprvkových podmnožin množiny vrcholů. Značení: Hranu mezi vrcholy u a v píšeme jako {u,v}, nebo zkráceně uv. Vrcholy spojené hranou jsou sousední. Na množinu vrcholů grafu G odkazujeme jako na V(G), na množinu hran E(G). Fakt: Na graf se lze dívat také jako na symetrickou ireflexivní relaci, kde hrany tvoří právě dvojice prvků z této relace. Petr Hliněný, Fl MU Brno MA010 "Grafy": Pojem grafu 1.1 Definice grafu Definice 1.1. Graf (rozšířeně obyčejný či jednoduchý neorientovaný graf) je uspořádaná dvojice G = (V, E), kde V je množina vrcholů a E je množina hran - množina vybraných dvouprvkových podmnožin množiny vrcholů. Značení: Hranu mezi vrcholy u a v píšeme jako {u,v}, nebo zkráceně uv. Vrcholy spojené hranou jsou sousední. Na množinu vrcholů grafu G odkazujeme jako na V(G), na množinu hran E(G). Fakt: Na graf se lze dívat také jako na symetrickou ireflexivní relaci, kde hrany tvoří právě dvojice prvků z této relace. Poznámka: Grafy se často zadávají přímo názorným obrázkem, jinak je lze také zadat výčtem vrcholů a výčtem hran. Například: V {1,2,3,4}, E= | {1,2},{1,3},{1,4},{3,4} | Petr Hliněný, Fl MU Brn MA010 "Grafy": Pojem grafu Běžné typy grafů Pro snadnější vyjadřování je zvykem některé běžné typy grafů nazývat popisnými jmény. Kružnice délky n má n > 3 vrcholů spojených do jednoho cyklu n hranami: (sn Petr Hliněný, Fl MU Brn MA010 "Grafy": Pojem grafu Běžné typy grafů Pro snadnější vyjadřování je zvykem některé běžné typy grafů nazývat popisnými jmény. Kružnice délky n má n > 3 vrcholů spojených do jednoho cyklu n hranami: (sn Cesta délky n má n+ 1 vrcholů spojených za sebou n hranami: P •-------•-------•-------•— -•-------• 12 3 4 n n+ í Petr Hliněný, Fl MU Brn MA010 "Grafy": Pojem grafu Úplný graf na n > 1 vrcholech má n vrcholu, všechny navzájem pospojované (tj. celkem (™) hran): K„ Petr Hliněný, Fl MU Brn MA010 "Grafy": Pojem grafu Úplný graf na n > 1 vrcholech má n vrcholů, všechny navzájem pospojované (tj. celkem (™) hran): K„ Úplný bipartitní graf nam>lan>l vrcholech má m + n vrcholů ve dvou skupinách (partitách), přičemž hranami jsou pospojované všechny m • n dvojice z různých skupin: K„ Petr Hliněný, Fl MU Brn MA010 "Grafy": Pojem grafu 1.2 Stupně vrcholů v grafu Definice 1.2. Stupněm vrcholu v v grafu G rozumíme počet hran vycházejících z v. Stupeň značíme da(v). (Slovo "vycházející" zde nenaznačuje žádný směr; je totiž obecnou konvencí říkat, že hrana vychází z obou svých konců zároveň.) Obrázek 1.1: Tento graf má stupně vrcholů 1, 2, 3, 4, 4, 4, 6. Petr Hliněný, Fl MU Brn MA010 "Grafy": Pojem grafu 1.2 Stupně vrcholů v grafu Definice 1.2. Stupněm vrcholu v v grafu G rozumíme počet hran vycházejících z v. Stupeň značíme da(v). (Slovo "vycházející" zde nenaznačuje žádný směr; je totiž obecnou konvencí říkat, že hrana vychází z obou svých konců zároveň.) Obrázek 1.1: Tento graf má stupně vrcholů 1, 2, 3, 4, 4, 4, 6. Věta 1.3. Součet stupňů v grafu je vždy sudý, roven dvojnásobku počtu hran. Petr Hliněný, Fl MU Brn MA010 "Grafy": Pojem grafu 1.2 Stupně vrcholů v grafu Definice 1.2. Stupněm vrcholu v v grafu G rozumíme počet hran vycházejících z v. Stupeň značíme da(v). (Slovo "vycházející" zde nenaznačuje žádný směr; je totiž obecnou konvencí říkat, že hrana vychází z obou svých konců zároveň.) Obrázek 1.1: Tento graf má stupně vrcholů 1, 2, 3, 4, 4, 4, 6. Věta 1.3. Součet stupňů v grafu je vždy sudý, roven dvojnásobku počtu hran. Důkaz. Při sčítání stupňů vrcholů v grafu započítáme každou hranu dvakrát -jednou za každý její konec. Proto výsledek vyjde sudý. D Petr Hliněný, Fl MU Brn MA010 "Grafy": Pojem grafu Vlastnosti stupňů Jelikož v obyčejném grafu zvlášť nerozlišujeme mezi jednotlivými vrcholy, nemáme dáno žádné pořadí, ve kterém bychom stupně vrcholů měli psát. Proto si stupně obvykle seřazujeme podle velikosti. jjc Zajímavou otázkou je, které posloupnosti stupňů odpovídají vrcholům skutečných grafů? (Například posloupnost stupňů 1,2,3,4,5,6,7 nemůže nastat nikdy.) Petr Hliněný, Fl MU Brno MA010 "Grafy": Pojem grafu Vlastnosti stupňů Jelikož v obyčejném grafu zvlášť nerozlišujeme mezi jednotlivými vrcholy, nemáme dáno žádné pořadí, ve kterém bychom stupně vrcholů měli psát. Proto si stupně obvykle seřazujeme podle velikosti. jjc Zajímavou otázkou je, které posloupnosti stupňů odpovídají vrcholům skutečných grafů? (Například posloupnost stupňů 1,2,3,4,5,6,7 nemůže nastat nikdy.) Věta 1.4. Nechť d\ < d2 < ... < dn je posloupnost přirozených čísel. Pak existuje graf s n vrcholy stupňů "1; d-2, .. ., dn právě tehdy, když existuje graf s n — 1 vrcholy stupňů d\, «2 , dn—dn — l7 ^n — dn 1, ■tn-2 1, Clr, 1. K použití Věty 1.4: Mírně nepřehledný formální zápis věty znamená, že ze seřazené posloupnosti odebereme poslední (největší) stupeň d„ a od tolika d„ bezprostředně předchozích stupňů odečteme jedničky. Zbylé stupně na začátku posloupnosti se nezmění. (Nezapomeňme, že posloupnost je třeba znovu seřadit dle velikosti.) Petr Hliněný, Fl MU Brn MA010 "Grafy": Pojem grafu Příklad 1.5. Existuje graf se stupni vrcholů: (1,1,1,2,3,4) ? Dle Věty 1.4 upravíme na (1,0, 0,1, 2), uspořádáme ji (0, 0,1,1, 2), pak znovu (0,0,0,0) a takový graf už jasně existuje. Na druhou stranu, jak takový graf sestrojíme? Petr Hliněný, Fl MU Brno MA010 "Grafy": Pojem grafu Příklad 1.5. Existuje graf se stupni vrcholů: (1,1,1,2,3,4) ? Dle Věty 1.4 upravíme na (1,0, 0,1, 2), uspořádáme ji (0, 0,1,1, 2), pak znovu (0,0,0,0) a takový graf už jasně existuje. Na druhou stranu, jak takový graf sestrojíme? (Obvykle není jediný, ale nás zajímá aspoň jeden z nich.) Prostě obrátíme předchozí postup, začneme z grafu se 4 vrcholy bez hran, přidáme vrchol stupně 2 spojený se dvěma z nich a další vrchol stupně 4 takto: —^^ Petr Hliněný, Fl MU Bn /IA010 "Grafy": Pojem grafu Příklad 1.5. Existuje graf se stupni vrcholů: (1,1,1,2,3,4) ? Dle Věty 1.4 upravíme na (1,0, 0,1, 2), uspořádáme ji (0, 0,1,1, 2), pak znovu (0,0,0,0) a takový graf už jasně existuje. Na druhou stranu, jak takový graf sestrojíme? (Obvykle není jediný, ale nás zajímá aspoň jeden z nich.) Prostě obrátíme předchozí postup, začneme z grafu se 4 vrcholy bez hran, přidáme vrchol stupně 2 spojený se dvěma z nich a další vrchol stupně 4 takto: —^^ (1,1,1,1,2,3,4,6,7) Petr Hliněný, Fl MU Brno MA010 "Grafy": Pojem grafu Příklad 1.5. Existuje graf se stupni vrcholů: (1,1,1,2,3,4) ? Dle Věty 1.4 upravíme na (1,0, 0,1, 2), uspořádáme ji (0, 0,1,1, 2), pak znovu (0,0,0,0) a takový graf už jasně existuje. Na druhou stranu, jak takový graf sestrojíme? (Obvykle není jediný, ale nás zajímá aspoň jeden z nich.) Prostě obrátíme předchozí postup, začneme z grafu se 4 vrcholy bez hran, přidáme vrchol stupně 2 spojený se dvěma z nich a další vrchol stupně 4 takto: —^^ (1,1,1,1,2,3,4,6,7) ? Podobně upravíme na (1,0,0, 0,1, 2, 3, 5) a uspořádáme ji (0,0, 0,1,1, 2, 3, 5), pak znovu (0,0, —1,0,0,1, 2), ale to už přece nelze - stupně nejsou záporné. Proto takový graf neexistuje. D Petr Hliněný, Fl MU Brn MA010 "Grafy": Pojem grafu 1.3 Podgrafy a Isomorfizmus Definice: Podgrafem grafu G rozumíme libovolný graf H na podmnožině vrcholů V(H) C V (G), který má za hrany libovolnou podmnožinu hran grafu G majících oba vrcholy ve V(H). Píšeme H C G. Obrázek 1.2: Co je (vlevo) a co není (vpravo) podgraf. Definice: Indukovaným podgrafem je podgraf H C G takový který obsahuje všechny hrany grafu G mezi dvojicemi vrcholů z V(H). Petr Hliněný, Fl MU Brn MA010 "Grafy": Pojem grafu Definice 1.6. Isomorfizmus grafů G a H je bijektivní (vzájemně jednoznačné) zobrazení / : V(G) —> V(H), pro které platí, že každá dvojice vrcholů u,v G V (G) je spojená hranou v G právě tehdy, když je dvojice f(u),f(v) spojená hranou v H. Grafy G a H jsou isomorfní pokud mezi nimi existuje isomorfismus. Píšeme G ~ iř. Petr Hliněný, Fl MU Brno MA010 "Grafy": Pojem grafu Definice 1.6. Isomorfizmus grafů G a H je bijektivní (vzájemně jednoznačné) zobrazení / : V(G) —> V(H), pro které platí, že každá dvojice vrcholů u,v G V (G) je spojená hranou v G právě tehdy, když je dvojice f(u),f(v) spojená hranou v H. Grafy G a H jsou isomorfní pokud mezi nimi existuje isomorfismus. Píšeme G ~ iř. Fakt: Isomorfní grafy mají stejný počet vrcholů (i hran). Z nakreslených tří grafů jsou první dva isomorfní - jsou to jen různá nakreslení "téhož" grafu, kružnice délky 5. (Určitě snadno najdete isomorfismus mezi nimi. Pro jednoduchost isomorfismus zakreslete do obrázku tak, že vrcholy prvního očíslujete čísly 1 až 5 a vrcholy druhého stejnými čísly v pořadí odpovídajícím jeho bijekci.) Třetí graf jim isomorfní není, neboť, například, má vrcholy jiných stupňů. Petr Hliněný, Fl MU Brn MA010 "Grafy": Pojem grafu Definice 1.6. Isomorfizmus grafů G a H je bijektivní (vzájemně jednoznačné) zobrazení / : V(G) —> V(H), pro které platí, že každá dvojice vrcholů u,v G V (G) je spojená hranou v G právě tehdy, když je dvojice f(u),f(v) spojená hranou v H. Grafy G a H jsou isomorfní pokud mezi nimi existuje isomorfismus. Píšeme G ~ iř. Fakt: Isomorfní grafy mají stejný počet vrcholů (i hran). Z nakreslených tří grafů jsou první dva isomorfní - jsou to jen různá nakreslení "téhož" grafu, kružnice délky 5. (Určitě snadno najdete isomorfismus mezi nimi. Pro jednoduchost isomorfismus zakreslete do obrázku tak, že vrcholy prvního očíslujete čísly 1 až 5 a vrcholy druhého stejnými čísly v pořadí odpovídajícím jeho bijekci.) Třetí graf jim isomorfní není, neboť, například, má vrcholy jiných stupňů. Fakt: Pokud je bijekce / isomorfismem, musí zobrazovat na sebe vrcholy stejných stupňů, tj. d o (v) = du (f (v)). Naopak to však nestačí! Petr Hliněný, Fl MU Brno MA010 "Grafy": Pojem grafu Příklad 1.7. Jsou následující dva grafy isomorfní? Pokud mezi nakreslenými dvěma grafy hledáme isomorfismus, nejprve se podíváme, zda mají stejný počet vrcholů a hran. Petr Hliněný, Fl Ml MA010 "Grafy": Pojem grafu Příklad 1.7. Jsou následující dva grafy isomorfní? Pokud mezi nakreslenými dvěma grafy hledáme isomorfismus, nejprve se podíváme, zda mají stejný počet vrcholů a hran. Mají. Pak se podíváme na stupně vrcholů a zjistíme, že oba mají stejnou posloupnost stupňů 2, 2, 2, 2, 3, 3. Petr Hliněný, Fl Ml MA010 "Grafy": Pojem grafu Příklad 1.7. Jsou následující dva grafy isomorfní? Pokud mezi nakreslenými dvěma grafy hledáme isomorfismus, nejprve se podíváme, zda mají stejný počet vrcholů a hran. Mají. Pak se podíváme na stupně vrcholů a zjistíme, že oba mají stejnou posloupnost stupňů 2,2,2,2,3,3. Takže ani takto jsme mezi nimi nerozlíšili a mohou (nemusejí!) být isomorfní. Dále tedy nezbývá, než zkoušet všechny přípustné možnosti zobrazení isomorfismu z levého grafu do pravého. Petr Hliněný, Fl Ml MA010 "Grafy": Pojem grafu Příklad 1.7. Jsou následující dva grafy isomorfní? Pokud mezi nakreslenými dvěma grafy hledáme isomorfismus, nejprve se podíváme, zda mají stejný počet vrcholů a hran. Mají. Pak se podíváme na stupně vrcholů a zjistíme, že oba mají stejnou posloupnost stupňů 2,2,2,2,3,3. Takže ani takto jsme mezi nimi nerozlíšili a mohou (nemusejí!) být isomorfní. Dále tedy nezbývá, než zkoušet všechny přípustné možnosti zobrazení isomorfismu z levého grafu do pravého. Na levém grafu si pro ulehčení všimněme, že oba vrcholy stupně tři jsou si symetrické, proto si bez újmy na obecnosti můžeme vybrat, že vrchol označený 1 se zobrazí na ľ. Druhý vrchol stupně tři, označený 4, se musí zobrazit na analogický vrchol druhého grafu 4'. A zbytek již plyne snadno: 6 •-----. 5 5' «-^» 6' D Petr Hliněný, Fl Ml MA010 "Grafy": Pojem grafu Věta 1.8. Relace "být isomorfní" ~ na třídě všech grafů je ekvivalencí. Petr Hliněný, Fl MU Brno 11 MA010 "Grafy": Pojem grafu Věta 1.8. Relace "být isomorfní" ~ na třídě všech grafů je ekvivalencí. Důkaz. Relace ~ je reflexivní, protože graf je isomorfní sám sobě identickým zobrazením. Relace je také symetrická, neboť bijektivní zobrazení lze jednoznačně "obrátit". Tranzitivnost ~ se snadno dokáže skládáním zobrazení-isomorfismů. D Důsledkem je, že všechny grafy se rozpadnou na třídy isomorfismu. V praxi pak, pokud mluvíme o grafu, myslíme tím obvykle jeho celou třídu isomorfismu, tj. nezáleží nám na konkrétní prezentaci grafu. Petr Hliněný, Fl MU Brno 11 MA010 "Grafy": Pojem grafu Další grafové pojmy Značení: Mějme libovolný graf G. • Podgrafu H C G, který je isomorfní nějaké kružnici, říkáme kružnice vG. • Speciálně říkáme trojúhelník kružnici délky 3. Petr Hliněný, Fl MU Brno 12 MA010 "Grafy": Pojem grafu Další grafové pojmy Značení: Mějme libovolný graf G. • Podgrafu H C G, který je isomorfní nějaké kružnici, říkáme kružnice vG. • Speciálně říkáme trojúhelník kružnici délky 3. • Podgrafu H C G, který je isomorfní nějaké cestě, říkáme cesta vG. Petr Hliněný, Fl MU Brno 12 MA010 "Grafy": Pojem grafu Další grafové pojmy Značení: Mějme libovolný graf G. • Podgrafu H C G, který je isomorfní nějaké kružnici, říkáme kružnice vG. • Speciálně říkáme trojúhelník kružnici délky 3. • Podgrafu H C G, který je isomorfní nějaké cestě, říkáme cesta vG. • Podgrafu H C G, který je isomorfní nějakému úplnému grafu, říkáme klika vG. • Podmnožině vrcholů X C V (G), mezi kterými nevedou v G vůbec žádné hrany, říkáme nezávislá množina X v G. Petr Hliněný, Fl MU Brno 12 MA010 "Grafy": Pojem grafu Další grafové pojmy Značení: Mějme libovolný graf G. • Podgrafu H C G, který je isomorfní nějaké kružnici, říkáme kružnice vG. • Speciálně říkáme trojúhelník kružnici délky 3. • Podgrafu H C G, který je isomorfní nějaké cestě, říkáme cesta vG. • Podgrafu H C G, který je isomorfní nějakému úplnému grafu, říkáme klika vG. • Podmnožině vrcholů X C V (G), mezi kterými nevedou v G vůbec žádné hrany, říkáme nezávislá množina X v G. • Indukovanému podgrafu H C G, který je isomorfní nějaké kružnici, říkáme indukovaná kružnice v G. Petr Hliněný, Fl MU Brno 12 MA010 "Grafy": Pojem grafu První z ukázaných grafů například neobsahuje žádný trojúhelník, ale obsahuje kružnici délky 4, dokonce indukovanou. Druhý graf trojúhelník obsahuje a kružnici délky 4 taktéž. První graf obsahuje cestu délky 4 na vrcholech 1,2,3,4,5, ale ta není indukovaná. Indukovaná cesta délky 4 v něm je třeba 2,3,4,5,6. Druhý graf tyto cesty také obsahuje, ale naopak žádná z nich není indukovaná. První graf má největší kliku velikosti 2 - jedinou hranu, kdežto druhý graf má větší kliku na vrcholech 3,4,5. Největší nezávislá množina u obou grafů má 3 vrcholy 2, 4, 6. Petr Hliněný, Fl Ml kIAOlO "Grafy": Pojem grafu Příklad 1.9. Jsou následující dva grafy isomorfní? Petr Hliněný, Fl Ml MA010 "Grafy": Pojem grafu Příklad 1.9. Jsou následující dva grafy isomorfní? Postupovat budeme jako v Příkladě 1.7, nejprve ověříme, že oba grafy mají stejně mnoho vrcholů i stejnou posloupnost stupňů 2, 2, 2, 2, 3, 3. Pokud se však budeme snažit najít mezi nimi isomorfismus, něco stále nebude sedět, že? Co nám tedy v nalezení isomorfismu brání? Podívejme se, že v druhém grafu oba vrcholy stupně tři mají svého společného souseda, tvoří s ním trojúhelník. V prvním grafu tomu tak není, první graf dokonce nemá žádný trojúhelník. Proto zadané dva grafy nejsou isomorfní. Petr Hliněný, Fl Ml MA010 "Grafy": Pojem grafu Příklad 1.9. Jsou následující dva grafy isomorfní? Postupovat budeme jako v Příkladě 1.7, nejprve ověříme, že oba grafy mají stejně mnoho vrcholů i stejnou posloupnost stupňů 2, 2, 2, 2, 3, 3. Pokud se však budeme snažit najít mezi nimi isomorfismus, něco stále nebude sedět, že? Co nám tedy v nalezení isomorfismu brání? Podívejme se, že v druhém grafu oba vrcholy stupně tři mají svého společného souseda, tvoří s ním trojúhelník. V prvním grafu tomu tak není, první graf dokonce nemá žádný trojúhelník. Proto zadané dva grafy nejsou isomorfní. D Poznámka: Výše uvedené příklady nám ukazují některé cesty, jak poznat (tj. najít nebo vyloučit) isomorfismus dvou grafů. Ty však ne vždy musí fungovat. Čtenář se může ptát, kde tedy najde nějaký univerzální postup pro nalezení isomorfismu? Petr Hliněný, Fl Ml MA010 "Grafy": Pojem grafu Příklad 1.9. Jsou následující dva grafy isomorfní? Postupovat budeme jako v Příkladě 1.7, nejprve ověříme, že oba grafy mají stejně mnoho vrcholů i stejnou posloupnost stupňů 2, 2, 2, 2, 3, 3. Pokud se však budeme snažit najít mezi nimi isomorfismus, něco stále nebude sedět, že? Co nám tedy v nalezení isomorfismu brání? Podívejme se, že v druhém grafu oba vrcholy stupně tři mají svého společného souseda, tvoří s ním trojúhelník. V prvním grafu tomu tak není, první graf dokonce nemá žádný trojúhelník. Proto zadané dva grafy nejsou isomorfní. D Poznámka: Výše uvedené příklady nám ukazují některé cesty, jak poznat (tj. najít nebo vyloučit) isomorfismus dvou grafů. Ty však ne vždy musí fungovat. Čtenář se může ptát, kde tedy najde nějaký univerzální postup pro nalezení isomorfismu? Bohužel vás musíme zklamat, žádný rozumný univerzální postup není znám a má se za to, že jediná vždy fungující cesta pro nalezení či nenalezení isomorfismu mezi dvěma grafy je ve stylu vyzkoušejte všechny možnosti bijekcí mezi vrcholy těchto grafů. (Těch je, jak známo, n!) Petr Hliněný, Fl Ml MA010 "Grafy": Pojem grafu 1.4 Orientované grafy a multigrafy V některých případech (například u toků v sítích) potřebujeme u každé hrany vyjádřit její směr. To vede na definici orientovaného grafu, ve kterém hrany jsou uspořádané dvojice vrcholů. (V obrázcích kreslíme orientované hrany se šipkami.) Fakt: Orientované grafy odpovídají relacím, které nemusí být symetrické. Značení: Hrana (u,v) v orientovaném grafu D začíná ve vrcholu u a končí ve (míří do) vrcholu v. Opačná hrana (v,u) je různá od (u,v) ! Petr Hliněný, Fl Ml MA010 "Grafy": Pojem grafu 1.4 Orientované grafy a multigrafy V některých případech (například u toků v sítích) potřebujeme u každé hrany vyjádřit její směr. To vede na definici orientovaného grafu, ve kterém hrany jsou uspořádané dvojice vrcholů. (V obrázcích kreslíme orientované hrany se šipkami.) Fakt: Orientované grafy odpovídají relacím, které nemusí být symetrické. Značení: Hrana (u,v) v orientovaném grafu D začíná ve vrcholu u a končí ve (míří do) vrcholu v. Opačná hrana (v,u) je různá od (u,v) ! Poznámka: Navíc někdy můžeme mluvit o tzv. multigrafech, ve kterých padají téměř všechna omezení na hrany. . . V multigrafu může mezi dvojicí vrcholů vést libovolný počet hran - tzv. násobné hrany, a některé z nich mohou být i orientované. Také jsou povoleny hrany, které mají oba konce totožné - tzv. smyčky. Petr Hliněný, Fl MU Brn- MA010 "Grafy": Pojem grafu 1.5 Implementace grafů Mějme jednoduchý graf G na n vrcholech a značme vrcholy jednoduše čísly V(G) = {0,1,... ,n— 1}. Pro počítačovou implementaci grafu G se nabízejí dva základní způsoby: • Maticí soused nosti, tj. dvourozměrným polem g[] [], ve kterém g [i] [j]=l znamená hranu mezi vrcholy i a j. • Výčtem sousedů, tj. použitím opět dvourozměrné pole h[] [] a navíc pole d[] stupňů vrcholů. Zde prvky h[i] [0] ,h[i] [1] , . . . ,h[i] [d[i]-l] udávají seznam sousedů vrcholu i. Poznámka: Dávejte si pozor na symetrii hran v implementaci! Implementace maticí sousednosti je hezká svou jednoduchostí. Druhá možnost se však mnohem lépe hodí pro grafy s malým počtem hran, což nastává ve většině praktických aplikací. (Navíc je implementace výčtem sousedů vhodná i pro multigrafy.) Ke grafům lze do zvláštních polí přidat také ohodnocení vrcholů a hran libovolnými čísly či značkami. . . Petr Hliněný, Fl Ml MA010 "Grafy": Pojem grafu