Graf (teorie grafů)

Z Multimediaexpo.cz

Nemáte oprávnění „upravit tuto stránku“. Důvod:

Můžete si prohlédnout a zkopírovat zdrojový kód této stránky:

[[Soubor:Graf-2007.png|thumb|240px|Základní pojmy [[teorie grafů]]]] '''Graf''' je základním objektem [[teorie grafů]]. Jedná se o reprezentaci množiny objektů, u které chceme znázornit, že některé prvky jsou propojeny. Objektům se přiřadí '''vrcholy''' a jejich propojení značí '''hrany''' mezi nimi. Významově se tak překrývá s pojmem [[binární relace]], o grafech se ale mluví hlavně v kontextu relací nad konečnými množinami. Grafy slouží jako abstrakce mnoha různých problémů. Často se jedná o zjednodušený model nějaké skutečné sítě (například dopravní), který zdůrazňuje [[Topologie|topologické]] vlastnosti objektů (vrcholů) a zanedbává geometrické vlastnosti, například přesnou polohu. Může jít ale o v podstatě jakékoliv dobře definované vztahy mezi objekty, například na [[Sociální síť|sociální síti]] můžeme studovat graf uživatelů (vrcholy) a jejich vzájemná propojení (hrany). == Definice == Nejobecněji můžeme '''orientovaný graf''' definovat jako trojici <big>\(G = (V,E,\epsilon)\)</big>, kde <big>\(V\)</big> je množina '''vrcholů''' (někdy také '''uzlů'''), <big>\(E\)</big> je množina '''hran''' a zobrazení <big>\(\epsilon : E \to V^2\)</big> určuje incidenci hran. (tj. <big>\(\epsilon(e) = (u,v)\)</big> znamená, že hrana <big>\(e\)</big> vede z vrcholu <big>\(u\)</big> do vrcholu <big>\(v\)</big>.) Tato definice umožňuje existenci paralelních hran (tj. takových hran <big>\(e_1,e_2\)</big> které mají stejný počáteční i koncový vrchol, tedy <big>\(\epsilon(e_1)=\epsilon(e_2)\)</big>.) Pokud v grafu paralelní hrany nejsou, (tj. zobrazení <big>\(\epsilon\)</big> je [[Prosté zobrazení|prosté]]), o grafu říkáme, že je '''prostý'''. Prosté grafy jsou v aplikacích běžné a tato vlastnost se často implicitně předpokládá a proto se často uvádí rovnou specializovaná definice, kdy graf definujeme jen jako dvojici <big>\(G = (V,E)\)</big>, kde <big>\(E \subseteq V^2\)</big>, tedy hrany identifikujeme přímo s dvojicemi vrcholů. '''Neorientovaný graf''' můžeme definovat analogicky, s tím rozdílem, že zobrazení incidence je <big>\(\epsilon : E \to \{\{u,v\}| u,v \in V\}\)</big>. Tedy u hrany nezáleží na pořadí vrcholů. Pro prosté neorientované grafy můžeme opět definici specializovat na <big>\(G = (V,E)\)</big>, kde <big>\(E \subseteq \{\{u,v\}| u,v \in V\}\)</big>. Množina <big>\(E\)</big> (resp. obor hodnot <big>\(\epsilon\)</big>) je množinou jedno (pokud <big>\(u=v\)</big>) a dvouprvkových množin vrcholů, tzv. '''(neorientovaných) hran'''. Jednoprvková množina v tomto případě značí '''smyčku'''. V aplikacích můžeme chtít uvažovat jen na grafy bez smyček a tedy se omezit pouze na dvouprvkové množiny odpovídající hranám. Ekvivalentně můžeme pro '''neorientovaný graf''' použít definici pro [[orientovaný graf]] a vyžadovat vlastnost, že pro každou dvojici vrcholů <big>\(u,v\)</big> je počet hran z <big>\(u\)</big> do <big>\(v\)</big> stejný jako počet hran z <big>\(v\)</big> do <big>\(u\)</big>, tedy <big>\(\left|\{e | \epsilon(e) = (u,v) \}\right| = \left|\{e | \epsilon(e) = (v,u) \}\right|\)</big> respektive pro prosté grafy jednodušeji: <big>\((u,v) \in E \iff (v,u) \in E\)</big>. Pokud o grafech uvažujeme jako o relacích, neorientované grafy v tomto pojetí odpovídají [[Symetrická relace|symetrickým relacím]]. == Varianty == * Grafu, který obsahuje '''smyčky''', tj. hrany, které začínají i končí ve stejném vrcholu se někdy říká '''pseudograf'''. V aplikacích se běžně smyčky neuvažují. * Pro definici grafu s paralelními hranami můžeme místo použití zobrazení incidence <big>\(\epsilon\)</big> ekvivalentně uvažovat o <big>\(E\)</big> jako o [[multimnožina|multimnožině]]. Graf s více hranami mezi týmiž vrcholy se také říká '''multigraf''' a paralelním (rovnoběžným) hranám se říká '''multihrany''' * Zobecněním grafu takovým, že hrany nemusí obsahovat právě dva vrcholy, je '''[[hypergraf]]'''. == Okolí vrcholu == === Sousedství === Pokud jsou dva vrcholy spojeny hranou, říká se, že spolu '''sousedí'''. Všechny vrcholy, se kterými daný vrchol ''v'' sousedí, jsou jeho '''sousedství''' nebo '''okolí''' ''N(v)''. <big>\(N(v)=\{u:\{v,u\} \in E\}\)</big> === Stupeň === {{Podrobně|Stupeň vrcholu}} '''Stupeň vrcholu''' ''deg(v)'' je velikost jeho sousedství. V případě orientovaných grafů se rozlišuje vstupní stupeň ''deg⁺(v)'', počet hran, které vcházejí do vrcholu ''v'', a výstupní stupeň ''deg⁻(v)'', počet hran, které vychází z vrcholu ''v''. <big>\(deg(v)=|\{u:\{v,u\} \in E\}|\)</big> <big>\(deg^+(v)=|\{u:(u,v) \in E\}|\)</big> <big>\(deg^-(v)=|\{u:(v,u) \in E\}|\)</big> === Regularita === {{Podrobně|Regulární graf}} Graf je ''' ''k''-regulární''', pokud mají všechny jeho vrcholy stupeň právě ''k''. === Skóre === {{Podrobně|Skóre grafu}} '''Skóre grafu''' je multimnožina stupňů všech vrcholů. === Princip sudosti === Platí rovnost <big>\(2|E|=\sum_{v \in V}deg(v)\)</big>, neboť každá hrana přispěje k sumě právě hodnotou 2. === Speciální stupně grafu === Často se používají hodnoty minimálního a maximálního stupně přes všechny vrcholy, minimální stupeň <big>\(\delta(G)\)</big>, maximální stupeň <big>\(\Delta(G)\)</big> a průměrný stupeň <big>\(deg_{avg}(G)=\frac{\sum_{v \in V}deg(v)}{|V|}=\frac{2|E|}{|V|}\)</big>. == Podgrafy a minory == === Odebrání hrany === Pokud ''e'' je hrana grafu ''G'', ''G-e'' označuje graf na stejné množině vrcholů s množinou hran <big>\(E(G)\setminus {e}\)</big>. (graf pak neobsahuje hranu ''e'') === Odebrání vrcholu === Pokud ''v'' je vrchol grafu ''G'', ''G-v'' označuje graf na množině vrcholů <big>\(V(G)\setminus {v}\)</big> a jeho množina hran se liší od původní tím, že neobsahuje hrany vrcholu ''v'', tedy <big>\(E(G-v)=E(G) \cap {V(G)\setminus {v} \choose 2}\)</big>. === Podgraf === {{Podrobně|Podgraf}} Graf ''G'' je '''podgraf''' grafu ''G’'', pokud může vzniknout z ''G’'' odebráním nějakých vrcholů a hran. === Indukovaný podgraf === Graf ''G'' je '''[[Podgraf|indukovaný podgraf]]''' grafu ''G’'', pokud může vzniknout z ''G’'' odebráním nějakých vrcholů. === Kontrakce hrany === Pokud ''e''=''{u,v}'' je hrana grafu ''G'', ''G.e'' označuje graf, který vznikne z G odstraněním ''e'' a identifikací vrcholů ''u'' a ''v''. Pokud má vzniknout obyčejný graf, požaduje se odstranění násobných hran a smyček, které mohly vzniknout. === Minor === {{Podrobně|Minor (teorie grafů)|}} Graf ''G'' je '''minor''' grafu ''G’'', pokud může vzniknout z ''G’'' odebráním nějakých vrcholů a hran a kontrakcí hran. == Sledy, tahy, cesty == === Sled === {{Podrobně|Sled (graf)}} '''Sled''' v grafu je [[posloupnost]] vrcholů taková, že mezi každými dvěma po sobě jdoucími je hrana. === Tah === {{Podrobně|Tah (graf)}} '''Tah''' v grafu je sled, ve kterém se neopakují hrany. === Cesta === {{Podrobně|Cesta (graf)|}} '''Cesta''' je sled, ve kterém se neopakují vrcholy, tedy každý vrchol se v cestě objevuje nejvýše jednou. Existuje-li mezi dvěma vrcholy sled v grafu, existuje mezi nimi i cesta (protože každý úsek mezi dvěma výskyty stejného vrcholu se dá „vystřihnout“). Na všechny tyto pojmy se dá také nahlížet jako na podgraf. == Souvislost == Graf je [[Souvislý graf|'''souvislý''']], pokud mezi každými dvěma vrcholy existuje cesta. V případě orientovaných grafů se mluví o '''silné souvislosti''', pokud mezi každými dvěma vrcholy v obou směrech existuje cesta respektující orientaci. === Komponenta souvislosti === {{Podrobně|Komponenta grafu|}} '''Komponenta souvislosti''' je každý v [[inkluze|inkluzi]] maximální souvislý podgraf. Souvislé grafy jsou právě ty, co mají pouze jednu komponentu souvislosti. U orientovaných grafů se navíc rozlišují '''[[Silně souvislá komponenta|silně souvislé komponenty]]'''. == Důležité typy grafů == * [[Strom (graf)|Strom]] * [[Cesta (graf)|Cesta]] * [[Kružnice (graf)|Kružnice]] * [[Úplný graf]] * [[Bipartitní graf]] == Reprezentace grafu == * ''„obrázkem“'', správně řečeno ''nakreslením'': viz [[rovinný graf]] * ''[[matice sousednosti|maticí sousednosti]]'': je-li |''V''| = n, pak čtvercová [[matice]] sousednosti ''A'' je typu <big>\(\{0, 1\}^{n\times n}\)</big> a platí <big>\(\mathit{A}_{i,j} = 1 \Leftrightarrow \{i, j\}\in\mathit{E}\)</big>. Pokud je graf neorientovaný, stačí na jeho reprezentaci (horní nebo dolní) trojúhelníková matice. * ''maticí vzdálenosti'': jsou-li hrany grafu ohodnocené, lze výše uvedenou matici modifikovat tak, že místo jedničky je na daném pozici uvedeno ohodnocení (délka) příslušné hrany * ''Laplaceovou maticí'': opět [[čtvercová matice]], tentokrát typu <big>\(\mathbb{Z}^{n\times n}\)</big>, pro niž platí :<big>\((\mathit{L}_G)_{i, j} = \begin{cases} deg(i), & i = j \\ -1, &\{i, j\}\in\mathit{E} \\ 0, &i\ne j\;\land\{i, j\}\notin\mathit{E} \end{cases}\)</big> * ''maticí incidence'': je-li |''V''| = n a |''E''| = m, pak matice incidence je typu <big>\(\{-1, 0, +1\}^{n\times m}\)</big> a platí :<big>\((\mathit{I}_G)_{i, e} =\begin{cases} -1, & e = (i, \bullet) \\ +1, & e = (\bullet, i) \\ 0, & \mbox{jinak} \end{cases}\)</big> :Jinými slovy, každá hrana má 1 u vrcholu kde začíná a -1 u vrcholu kde končí. U neorientovaných grafů je vždy +1 když je hrana v incidenci s vrcholem. Pro neorientovaný graf: [[Soubor:Incidence matrix - undirected graph.png|240px|Neorientovaný graf a jeho matice incidence]] Pro orientovaný graf: [[Soubor:Incidence matrix - directed graph.png|240px|Orientovaný graf a jeho matice incidence]] * ''seznamem sousedů'': je-li |''V''| = n, uspořádáme vrcholy grafu do [[pole (informatika)|pole]] velikosti n a v i-tém prvku tohoto pole bude [[ukazatel (informatika)|ukazatel]] na [[spojový seznam]] vrcholů, které s vrcholem ''i'' sousedí. Toto uspořádání je vhodné při množství údajů menším než n^2. Tj. při ostře menším počtu hran než n^2, kde n je počet vrcholů. Jedná se o tzv. řídké grafy, kterých je v prostředí sítí nejvíce. == Izomorfismus grafů == Grafy ''G'' a ''G’'' jsou ''[[izomorfismus|izomorfní]]'' právě tehdy, když existuje taková [[bijekce]] <big>\(f: V(G) \to V(G')\)</big>, že platí <big>\(\{\mathit{i, j}\}\in E(G) \Leftrightarrow \{\mathit{f(i), f(j)}\}\in E(G')\)</big>. Tedy zhruba řečeno, G a G' se liší pouze „očíslováním“ svých vrcholů. == Ohodnocení grafu == Pro některé účely se vrcholy nebo hrany grafu ohodnocují, například reálnými čísly, pomocí ohodnocovací funkce <big>\(w:E\rightarrow \mathbb{R}\)</big> nebo <big>\(V\rightarrow \mathbb{R}\)</big>. Tomuto ohodnocení hran také říkáme vážení. == Literatura == * Doc. Ing. Vítečková Miluše CSc., Bc. Přidal Petr, Ing. Koudela Tomáš: ''Teorie grafů,'' Technická univerzita Ostrava, Listopad 2015, [http://books.fs.vsb.cz/SystAnal/texty/21.htm Dostupné online] * Jiří Matoušek, Jaroslav Nešetřil: ''Kapitoly z diskrétní matematiky'', nakladatelství Karolinum, Praha 2002, ISBN: 80-246-0084-6 * Roman Čada, Tomáš Kaiser, Zdeněk Ryjáček: ''Diskrétní matematika'', Západočeská univerzita v Plzni, Březen 2004, ISBN: 80-7082-939-7 * Zdeněk Ryjáček: ''Pracovní texty přednášek Teorie grafů a diskrétní optimalizace 1'' [https://web.archive.org/web/20060523001515/http://www.cam.zcu.cz/~ryjacek/students/ps/TGD1.pdf Volně ke stažení, PDF verze] * prof. RNDr. Radim Bělohlávek, DSc.: ''Algoritmická matematika 2'' [http://belohlavek.inf.upol.cz/vyuka/algoritmicka-matematika-2-1.pdf Volně ke stažení, PDF verze] * Jiří Demel: ''Grafy a jejich aplikace'', nakladatelství Academia, Praha 2002, ISBN: 80-200-0990-6 == Externí odkazy == {{Commonscat|Graph (discrete mathematics)}}{{Článek z Wikipedie}} [[Kategorie:Teorie grafů]] [[Kategorie:Grafové pojmy]]

Návrat na stránku „Graf (teorie grafů)“.