Graf (teorie grafů)

Z Multimediaexpo.cz

(Rozdíly mezi verzemi)

Aktuální verze z 30. 5. 2025, 10:11

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 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íti můžeme studovat graf uživatelů (vrcholy) a jejich vzájemná propojení (hrany).

Definice

Nejobecněji můžeme orientovaný graf definovat jako trojici $G = (V, E, ϵ)$ , kde $V$ je množina vrcholů (někdy také uzlů), $E$ je množina hran a zobrazení $ϵ : E \to V^{2}$ určuje incidenci hran. (tj. $ϵ (e) = (u, v)$ znamená, že hrana $e$ vede z vrcholu $u$ do vrcholu $v$ .) Tato definice umožňuje existenci paralelních hran (tj. takových hran $e_{1}, e_{2}$ které mají stejný počáteční i koncový vrchol, tedy $ϵ (e_{1}) = ϵ (e_{2})$ .) Pokud v grafu paralelní hrany nejsou, (tj. zobrazení $ϵ$ je 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 $G = (V, E)$ , kde $E \subseteq V^{2}$ , tedy hrany identifikujeme přímo s dvojicemi vrcholů.

Neorientovaný graf můžeme definovat analogicky, s tím rozdílem, že zobrazení incidence je $ϵ : E \to {{u, v} | u, v \in V}$ . Tedy u hrany nezáleží na pořadí vrcholů. Pro prosté neorientované grafy můžeme opět definici specializovat na $G = (V, E)$ , kde $E \subseteq {{u, v} | u, v \in V}$ . Množina $E$ (resp. obor hodnot $ϵ$ ) je množinou jedno (pokud $u = v$ ) 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ů $u, v$ je počet hran z $u$ do $v$ stejný jako počet hran z $v$ do $u$ , tedy $| {e | ϵ (e) = (u, v)} | = | {e | ϵ (e) = (v, u)} |$ respektive pro prosté grafy jednodušeji: $(u, v) \in E ⟺ (v, u) \in E$ . Pokud o grafech uvažujeme jako o relacích, neorientované grafy v tomto pojetí odpovídají 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 $ϵ$ ekvivalentně uvažovat o $E$ jako o 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). $N (v) = {u : {v, u} \in E}$

Stupeň

Podrobnější informace naleznete na stránce: 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.

$d e g (v) = | {u : {v, u} \in E} |$

$d e g^{+} (v) = | {u : (u, v) \in E} |$

$d e g^{-} (v) = | {u : (v, u) \in E} |$

Regularita

Podrobnější informace naleznete na stránce: Regulární graf

Graf je k-regulární, pokud mají všechny jeho vrcholy stupeň právě k.

Skóre

Podrobnější informace naleznete na stránce: Skóre grafu

Skóre grafu je multimnožina stupňů všech vrcholů.

Princip sudosti

Platí rovnost $2 | E | = \sum_{v \in V} d e g (v)$ , 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ň $δ (G)$ , maximální stupeň $Δ (G)$ a průměrný stupeň $d e g_{a v g} (G) = \frac{\sum_{v \in V} d e g (v)}{| V |} = \frac{2 | E |}{| V |}$ .

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 $E (G) ∖ e$ . (graf pak neobsahuje hranu e)

Odebrání vrcholu

Pokud v je vrchol grafu G, G-v označuje graf na množině vrcholů $V (G) ∖ v$ a jeho množina hran se liší od původní tím, že neobsahuje hrany vrcholu v, tedy $E (G - v) = E (G) \cap (\binom{V (G) ∖ v}{2})$ .

Podgraf

Podrobnější informace naleznete na stránce: 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 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ější informace naleznete na stránce: 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ější informace naleznete na stránce: Sled (graf)

Sled v grafu je posloupnost vrcholů taková, že mezi každými dvěma po sobě jdoucími je hrana.

Tah

Podrobnější informace naleznete na stránce: Tah (graf)

Tah v grafu je sled, ve kterém se neopakují hrany.

Cesta

Podrobnější informace naleznete na stránce: 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ý, 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ější informace naleznete na stránce: Komponenta grafu

Komponenta souvislosti je každý v 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é komponenty.

Důležité typy grafů

Reprezentace grafu

„obrázkem“, správně řečeno nakreslením: viz rovinný graf
maticí sousednosti: je-li |V| = n, pak čtvercová matice sousednosti A je typu ${0, 1}^{n \times n}$ a platí $A_{i, j} = 1 \Leftrightarrow {i, j} \in E$ . 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 $Z^{n \times n}$ , pro niž platí

(L_{G})_{i, j} = {\begin{cases} d e g (i), & i = j \\ - 1, & {i, j} \in E \\ 0, & i \neq j \land {i, j} \notin E \end{cases}

maticí incidence: je-li |V| = n a |E| = m, pak matice incidence je typu ${- 1, 0, + 1}^{n \times m}$ a platí

(I_{G})_{i, e} = {\begin{cases} - 1, & e = (i, ∙) \\ + 1, & e = (∙, i) \\ 0, & jinak \end{cases}

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: Pro orientovaný graf:

seznamem sousedů: je-li |V| = n, uspořádáme vrcholy grafu do pole velikosti n a v i-tém prvku tohoto pole bude 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 izomorfní právě tehdy, když existuje taková bijekce $f : V (G) \to V (G^{'})$ , že platí ${i, j} \in E (G) \Leftrightarrow {f (i), f (j)} \in E (G^{'})$ . 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 $w : E \to R$ nebo $V \to R$ . 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, 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 Volně ke stažení, PDF verze
prof. RNDr. Radim Bělohlávek, DSc.: Algoritmická matematika 2 Volně ke stažení, PDF verze
Jiří Demel: Grafy a jejich aplikace, nakladatelství Academia, Praha 2002, ISBN: 80-200-0990-6

Externí odkazy

Commons nabízí fotografie, obrázky a videa k tématu
Graf (teorie grafů)

[zobrazit] Náklady na energie a provoz naší encyklopedie prudce vzrostly. Potřebujeme vaši podporu... Kolik ?? To je na Vás. Náš FIO účet — 2500575897 / 2010
Informace o článku. Článek je převzat z Wikipedie, otevřené encyklopedie, do které přispívají dobrovolníci z celého světa. Tento text je dostupný za podmínek Creative Commons 3.0 Unported – creativecommons.org. Originální článek na české Wikipedii

@@ Řá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, ϵ)$ </big>, kde <big> $V$ </big> je množina '''vrcholů''' (někdy také '''uzlů'''), <big> $E$ </big> je množina '''hran''' a zobrazení <big> $ϵ : E \to V^{2}$ </big> určuje incidenci hran. (tj. <big> $ϵ (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> $ϵ (e_{1}) = ϵ (e_{2})$ </big>.) Pokud v grafu paralelní hrany nejsou, (tj. zobrazení <big> $ϵ$ </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> $ϵ : 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> $ϵ$ </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> $| {e | ϵ (e) = (u, v)} | = | {e | ϵ (e) = (v, u)} |$ </big> respektive pro prosté grafy jednodušeji: <big> $(u, v) \in E ⟺ (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> $ϵ$ </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> $d e g (v) = | {u : {v, u} \in E} |$ </big>
+<big> $d e g^{+} (v) = | {u : (u, v) \in E} |$ </big>
+<big> $d e g^{-} (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} d e g (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> $δ (G)$ </big>, maximální stupeň <big> $Δ (G)$ </big> a průměrný
+stupeň <big> $d e g_{a v g} (G) = \frac{\sum_{v \in V} d e g (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) ∖ 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) ∖ 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 (\binom{V (G) ∖ v}{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> $A_{i, j} = 1 \Leftrightarrow {i, j} \in 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> $Z^{n \times n}$ </big>, pro niž platí
+:<big> $(L_{G})_{i, j} = {\begin{cases} d e g (i), & i = j \\ - 1, & {i, j} \in E \\ 0, & i \neq j \land {i, j} \notin 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> $(I_{G})_{i, e} = {\begin{cases} - 1, & e = (i, ∙) \\ + 1, & e = (∙, i) \\ 0, & 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> ${i, j} \in E (G) \Leftrightarrow {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 \to R$ </big> nebo <big> $V \to 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]]