Sysop: + Aktualizace

2025-05-30T10:11:13Z

+ Aktualizace

← Starší verze		Verze z 30. 5. 2025, 10:11
Řádka 1:		Řádka 1:
-	~~{{Wikipedia~~-cs\|Graf (teorie grafů)\|~~700}}~~	+	[[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<sup>+</sup>(v)'', počet hran, které vcházejí do vrcholu ''v'', a výstupní stupeň ''deg<sup>−</sup>(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:Teorie grafů]]
	[[Kategorie:Grafové pojmy]]		[[Kategorie:Grafové pojmy]]

Sysop: 1 revizi

2014-04-19T07:36:20Z

1 revizi

← Starší verze

Verze z 19. 4. 2014, 07:36

Sysop: + Výrazné vylepšení

2012-10-22T00:40:00Z

+ Výrazné vylepšení

Nová stránka

{{Wikipedia-cs|Graf (teorie grafů)|700}}

[[Kategorie:Teorie grafů]]
[[Kategorie:Grafové pojmy]]

Graf (teorie grafů) - Historie editací

Sysop: + Aktualizace

Sysop: 1 revizi

Sysop: + Výrazné vylepšení