Graf (matematika)

Graf je matematická abstrakce reálného systému libovolné povahy, jehož objekty mají párové vazby. Graf jako matematický objekt je sbírka dvou množin – množiny samotných objektů, nazývané množina vrcholů , a množiny jejich párových spojení, nazývané množina hran. Prvek množiny okrajů je dvojice prvků množiny vrcholů.

Grafy jsou široce používány v moderní vědě a technice. Používají se jak v přírodních vědách (fyzika a chemie), tak ve společenských vědách (například sociologie), ale největšího rozsahu se využití grafů dostalo v informatice a síťových technologiích.

Jako nejjednodušší příklad ze života můžeme uvést letový diagram určité letecké společnosti, který je modelován grafem, kde vrcholy grafu jsou města a okraje jsou lety spojující dvojice měst. Strom adresářů v počítači je také graf: jednotky, složky a soubory jsou vrcholy a okraje zobrazují vnoření souborů a složek do složek a jednotek [1] . Struktura Wikipedie je modelována pomocí orientovaného grafu , ve kterém jsou články vrcholy grafu a hypertextové odkazy jsou oblouky ( tematická mapa ).

Grafy jsou hlavním předmětem studia v teorii grafů .

Definice

Systémy skutečné přírody modelované pomocí grafů jsou velmi rozmanité, proto existují různé typy grafů. Nejjednodušší abstrakcí systémů s prvky, které mají párová spojení, je jednoduchý graf .

Jednoduchý graf

Definice. Jednoduchý graf je sbírka dvou množin – neprázdná množina a množina neuspořádaných dvojic různých prvků množiny . Množina se nazývá množina vrcholů , množina se nazývá množina hran $G(V,E)$ $PROTI$ $E$ $PROTI$ $PROTI$ $E$

G(V,E)=\left\langle V,E\right\rangle ,\quad V\neq \varnothing ,\quad E\subseteq V\times V,\quad \left\{v,v\ vpravo\}\notin E,\quad v\in V

to znamená, že množina se skládá ze 2-prvkových podmnožin množiny . $E$ $PROTI$

Související pojmy

Teorie grafů nemá ustálenou terminologii. Některé publikace proto mohou používat jiné termíny než ty, které jsou uvedeny níže.

Vrchol (uzel, bod) ( angl. vertex, node, point ) grafu je prvkem množiny vrcholů ; $G$ $v\in V(G)$

Hrana (čára) ( anglicky edge, line ) grafu je prvkem množiny hran , nebo , kde ; $G$ $e\in E(G)$ $e=\left\{v_{1},v_{2}\right\}$ $v_{1}\in V(G),\quad v_{2}\in V(G)$

Prvky grafu jsou jeho vrcholy a hrany grafu; $G$ $v\in V(G)$ $e\in E(G)$

Pořadí ( anglicky order ) grafu je základní číslo množiny vrcholů nebo jinými slovy počet vrcholů; $G$ $n=|V(G)|$

Velikost ( anglicky size ) grafu je kardinální číslo množiny hran nebo jinými slovy počet hran; $G$ $m=|E(G)|$

Vrchol je incidentní k hraně if ; _ pak také říkají, že jest hrana u ; $proti$ $E$ $v\in e$ $E$ $proti$

Koncové vrcholy (ends) ( angl. endvertices, ends ) jsou dva vrcholy spadající do hrany. Hrana spojuje ( anglicky joins ) její koncové vrcholy;

Sousední (sousední) vrcholy ( anglicky sousedé, sousedící ) jsou takové vrcholy a ten nebo jinými slovy oba vrcholy jsou koncové pro jednu hranu; $v_{1}$ $v_{2}$ $\left\{v_{1},v_{2}\right\}\in E(G)$

Sousední hrany ( anglicky sousední hrany ) jsou hrany spadající do jednoho vrcholu nebo - sousedící; ${\displaystyle e_{1}=\left\{v,v_{1}\right\))$ $e_{2}=\left\{v,v_{2}\right\}$

Stupeň (valence) vrcholu ( eng. degree, valency ) je počet hran, které s ním spadají. Stupeň vrcholu je označen jako ; $d(v)$

Izolovaný vrchol ( angl. isolated ) je vrchol se stupněm , to znamená, že to není konec žádné hrany; $d(v)=0$

Visící vrchol (leaf) ( angl. leaf ) je vrchol se stupněm , tedy který je koncem právě jedné hrany. $d(v)=1$

Typicky je graf znázorněn jako diagram : vrcholy - body, hrany - čáry.

Pseudograf

Pseudograf je sbírka dvou množin – neprázdná množina a množina neuspořádaných dvojic prvků množiny . $G(V,E)$ $PROTI$ $E$ $PROTI$

G(V,E)=\left\langle V,E\right\rangle ,\quad V\neq \varnothing ,\quad E\subseteq V\times V

Prvek je povolen v sadě hran pseudografu . $\left\{v,v\right\}\in E(G)$

Smyčka je prvek , který je hranou, jejíž koncové vrcholy se shodují. $e=\left\{v,v\right\}$

Jinými slovy, pokud prvky množiny E mohou být smyčky, pak se graf nazývá pseudograf [2] .

Multigraf

Multigraf je sbírka dvou množin – neprázdná množina a multimnožina neuspořádaných dvojic různých prvků množiny . $G(V,\mathbf {E} )$ $PROTI$ $\mathbf {E}$ $PROTI$

G(V,\mathbf {E} )=\left\langle V,\mathbf {E} \right\rangle ,\quad V\neq \varnothing ,\quad \mathbf {E} \subseteq V\times V\quad \left\{v,v\right\}\notin \mathbf {E} ,\quad v\in V

Vícenásobné hrany jsou identické prvky multimnožiny , tedy hrany, jejichž koncové vrcholy se shodují. $\left\{e,e,\tečky ,e\right\}\in \mathbf {E}$

Jinými slovy, pokud ne množina, ale rodina, tedy pokud obsahuje stejné prvky, pak se takové prvky nazývají vícenásobné hrany a graf se nazývá multigraf [2] . $E$ $\mathbf {E}$

Pseudomultigraf

Pseudomultigraf je sbírka dvou množin – neprázdná množina a vícenásobná množina neuspořádaných dvojic prvků množiny . $G(V,\mathbf {E} )$ $PROTI$ $\mathbf {E}$ $PROTI$

G(V,\mathbf {E} )=\left\langle V,\mathbf {E} \right\rangle ,\quad V\neq \varnothing ,\quad \mathbf {E} \subseteq V\times PROTI

Jinými slovy, pokud rodina obsahuje stejné prvky (více hran) a může obsahovat smyčky, pak se graf nazývá pseudo-multigraf [2] . $\mathbf {E}$ $\mathbf {E}$

Orientovaný graf

Orientovaný graf (digraph) ( angl. directional graph nebo dirgaph ) je množina dvou množin - neprázdná množina a množina oblouků nebo uspořádaných dvojic různých prvků množiny $G(V,E)$ $PROTI$ $E$ $PROTI$

G(V,E)=\left\langle V,E\right\rangle ,\quad V\neq \varnothing ,\quad \left\langle \left\{v_{1},v_{2}\ vpravo\},\prec \pravo\rangle \in E,\quad v\in V

společně se dvěma displeji

init:E\rightarrow V,\quad ter:E\rightarrow V

kde mapování přiřadí každému oblouku jeho počáteční vrchol (začátek oblouku) a mapování přiřadí každému oblouku jeho koncový vrchol (konec oblouku) . Říká se, že oblouk vede od do $init:E\rightarrow V$ $init(e)$ $ter:E\rightarrow V$ $ter(e)$ $E$ $init(e)$ $ter(e)$

Smíšený graf

Smíšený graf je soubor tří množin – neprázdná množina vrcholů a množina oblouků nebo uspořádaných dvojic různých prvků množiny a množina hran neuspořádaných dvojic různých prvků množiny. $G(V,E,U)$ $PROTI$ $E$ $PROTI$ $U$ $PROTI$

G(V,E,U)=\left\langle V,E,U\right\rangle ,\quad V\neq \varnothing ,\quad \left\langle \left\{v_{1},v_ {2}\vpravo\},\před \vpravo\rozsah \v E,\čtverec \levý\{v_{3},v_{4}\vpravo\}\v U,\čtverec v\ve V

společně se dvěma displeji

init:E\rightarrow V,\quad ter:E\rightarrow V

Orientované a neorientované grafy jsou speciální případy smíšených grafů.

Izomorfní grafy

Graf se nazývá izomorfní vůči grafu , pokud existuje bijekce z množiny vrcholů grafu do množiny vrcholů grafu , která má následující vlastnost: pokud má graf hranu od vrcholu k vrcholu , pak graf musí mít hranu od vertexu k vertexu a naopak - pokud má graf hranu od vertexu k vertexu , tak graf musí mít hranu od vertexu k vertexu . V případě orientovaného grafu musí tato bijekce také zachovat orientaci hrany. V případě váženého grafu musí bijekce zachovat i váhu hrany. $G$ $H$ $F$ $G$ $H$ $G$ $A$ $B$ $H$ $f(A)$ $f(B)$ $H$ $A$ $B$ $G$ $f^{-1}(A)$ $f^{-1}(B)$

Další související definice

Trasa v grafu je konečná posloupnost vrcholů, ve které je každý vrchol (kromě posledního) spojen s dalším vrcholem v posloupnosti hranou. Řetěz je cesta bez opakujících se hran. Jednoduchá cesta je cesta bez opakujících se vrcholů (což znamená, že v jednoduché cestě nejsou žádné opakující se hrany).

Orientovaná trasa (nebo cesta ) v digrafu je konečná posloupnost vrcholů a oblouků, ve kterých každý prvek souvisí s předchozím a následujícím.

Cyklus je řetězec, ve kterém se první a poslední vrcholy shodují. V tomto případě je délka cesty (nebo cyklu) počtem jejích základních hran . Všimněte si, že pokud jsou vrcholy a konce nějaké hrany, pak podle této definice je posloupnost cyklus. Aby se předešlo takovým "degenerovaným" případům, jsou zavedeny následující pojmy. $u$ $proti$ $(u,v,u)$

Cesta (nebo cyklus) se nazývá jednoduchá , pokud se hrany v ní neopakují; elementární , pokud je jednoduchý a vrcholy v něm se neopakují (s výjimkou počátečního a koncového v případě cyklu).

Nejjednodušší vlastnosti cest a cyklů:

každá cesta spojující dva vrcholy obsahuje elementární cestu spojující stejné dva vrcholy;
každá jednoduchá neelementární cesta obsahuje elementární cyklus ;
každý jednoduchý cyklus procházející nějakým vrcholem (nebo hranou) obsahuje elementární (pod)cyklus procházející stejným vrcholem (nebo hranou);
smyčka je elementární cyklus.

Binární relace na vrcholové množině grafu, daná jako "existuje cesta od do ", je relací ekvivalence , a proto rozděluje tuto množinu do tříd ekvivalence, nazývaných spojené komponenty grafu. Pokud má graf právě jednu spojenou složku, pak je graf souvislý. Na připojené komponentě můžeme zavést pojem vzdálenosti mezi vrcholy jako minimální délku cesty spojující tyto vrcholy. $u$ $proti$

Jakýkoli maximální souvislý podgraf grafu se nazývá souvislá složka (nebo jednoduše složka) grafu . Slovo „maximum“ znamená maximum s ohledem na zahrnutí, to znamená, že není obsaženo v připojeném podgrafu s velkým počtem prvků. $G$ $G$

Hrana v grafu se nazývá můstek , pokud její odstranění zvyšuje počet komponent.

Další charakteristiky grafů

Graf se jmenuje:

připojena pokud pro nějaké vrcholyexistujecesta oddo. $u$ $proti$ $u$ $proti$
silně propojený nebo směrově spojený , pokud je orientovaný a existuje orientovaná cesta z libovolného vrcholu do kteréhokoli jiného.
strom , pokud je propojený a neobsahuje netriviální cykly.
kompletní , pokud je některý z jeho dvou (různých, pokud nejsou povoleny smyčky) vrcholů spojeny hranou.
bipartitní , pokud lze jeho vrcholy rozdělit na dvě neprotínající se podmnožinyatak, že jakákoli hrana spojuje vrchol zs vrcholem z. $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$
k-částečné , pokud lze jeho vrcholy rozdělit na neprotínající se podmnožiny , , …, takže neexistují žádné hrany spojující vrcholy téže podmnožiny. $k$ $V_{1}$ $V_{2}$ $V_{k}$
úplná bipartita , pokud je každý vrchol jedné podmnožiny spojen hranou s každým vrcholem jiné podmnožiny.
rovinný , pokud lze graf znázornit diagramem na rovině bez křížení hran.
vážený , pokud je každé hraně grafu přiřazeno určité číslo, nazývané váha hrany.
chordální , pokud graf neobsahuje indukované cykly s délkou větší než tři.

Stává se také:

Zobecnění pojmu graf

Jednoduchý graf je jednorozměrný jednoduchý komplex .

Abstraktněji lze graf definovat jako triple , kde a jsou nějaké množiny ( vrcholů a hran , v tomto pořadí) a je incidenční funkcí (nebo incidentorem ), která přiřazuje každé hraně (uspořádané nebo neuspořádané) dvojici vrcholů a od (jeho konce ). Konkrétní případy tohoto konceptu jsou: $(V,E,\varphi )$ $PROTI$ $E$ $\varphi$ $e\in E$ $u$ $proti$ $PROTI$

Eulerovy grafy - graf, ve kterém je cyklická Eulerova cesta ( Eulerův cyklus );

Způsoby znázornění grafu v informatice

Matice sousedství

Tabulka, kde sloupce i řádky odpovídají vrcholům grafu. V každé buňce této matice je zapsáno číslo, které určuje přítomnost spojení z horního řádku do horního sloupce (nebo naopak).

Toto je nejpohodlnější způsob znázornění hustých grafů.

Nevýhodou jsou paměťové nároky, které jsou přímo úměrné druhé mocnině počtu vrcholů.

Dvourozměrné pole;
Matice s mezerami;
Implicitní nastavení (pomocí funkce).

Incidenční matice

Tabulka, kde řádky odpovídají vrcholům grafu a sloupce odpovídají spojnicím (hranám) grafu. V buňce matice na průsečíku řádku se sloupcem se zapíše následující: $i$ $j$

jeden v případě, že spojení „opustí“ horní část ,

j

i

-1, pokud spojení „vstoupí“ do vrcholu, 0 ve všech ostatních případech (tj. pokud je spojení smyčkou nebo spojení není incidentní ve vrcholu)

Tato metoda je poměrně prostorná (velikost je úměrná ) pro ukládání, takže se používá velmi zřídka, ve speciálních případech (například pro rychlé nalezení cyklů v grafu). $|V||E|$

Seznam sousedství

Seznam, kde každý vrchol grafu odpovídá řetězci, který ukládá seznam sousedních vrcholů. Taková datová struktura není tabulkou v obvyklém smyslu, ale je „seznamem seznamů“.

Velikost paměti: . $O(|V|+|E|)$

Toto je nejpohodlnější způsob, jak reprezentovat řídké grafy, stejně jako při implementaci základních algoritmů procházení grafů do šířky nebo hloubky, kdy potřebujete rychle získat „sousedy“ aktuálně zobrazeného vrcholu.

Seznam hran

Seznam, kde každá hrana grafu odpovídá řetězci, který obsahuje dva vrcholy spadající do hrany.

Velikost paměti: . $O(|E|)$

Jedná se o nejkompaktnější způsob znázornění grafů, takže se často používá pro externí úložiště nebo výměnu dat.

Popis jazyků a grafických programů

Jazyky popisu

K popisu grafů, které jsou vhodné pro strojové zpracování a zároveň vhodné pro lidské vnímání, se používá několik standardizovaných jazyků, včetně:

TEČKA
GraphML
Triviální formát grafu
GML
GXL
XGMML
DGML

Stavební programy

Byla vyvinuta řada komerčních programů pro vytváření grafů, například vytváření grafů je základem softwarových balíků aplikací ILOG (od roku 2009 ve vlastnictví IBM Corporation ), mimo jiné - GoView, Lassalle AddFlow, LEDA (existuje bezplatná edice ).

K dispozici je také bezplatný grafický program igraph a bezplatná knihovna s názvem Boost .

Vizualizační programy

K vizualizaci grafů se používají následující softwarové nástroje :

Graphviz ( Eclipse Public License )
Vizualizér grafů LION.
Grafový analyzátor je ruskojazyčný program s jednoduchým uživatelským rozhraním ( GNU LGPL ; pouze Windows).
Gephi je grafický rámec pro reprezentaci a studium grafů ( GNU GPL , CDDL ).
Knihovna GraphX je bezplatná knihovna .NET pro výpočty a kreslení grafů pomocí WPF 4.0 .
Knihovna MSAGL je bezplatná knihovna pro .NET [3] .

Viz také

Poznámky

↑ Burkatovskaya, 2014 , s. 3.
↑ 1 2 3 Burkatovskaya, 2014 , s. 6.
↑ Microsoft Automatic Graph Layout - Microsoft Research . research.microsoft.com. Získáno 15. listopadu 2015. Archivováno z originálu 14. května 2012. (neurčitý)

Literatura

Burkatovskaya Yu. B. Teorie grafů. - Tomsk: Nakladatelství Tomské polytechnické univerzity, 2014. - T. 1. - 200 s.
Distel R. Teorie grafů. - Novosibirsk: Vydavatelství Ústavu matematiky. S. L. Sobolev SO RAN, 2002. - 336 s. - ISBN 5-86134-101-X.
Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Přednášky o teorii grafů. M.: Nauka, 1990. 384 s. (Vyd. 2, rev. M.: URSS, 2009. 392 s.)
Kasjanov V.N., Evstigneev V.A. Grafy v programování: zpracování, vizualizace a aplikace. - Petrohrad. : BHV-Petersburg, 2003. - S. 1104. - ISBN 5-94157-184-4 .
Kirsanov M.N. Grafy v Maple. — M. : Fizmatlit, 2007. — 168 s. - ISBN 978-5-9221-0745-7 .
Kormen T. M. a kol., Část VI. Algoritmy pro práci s grafy // Algoritmy: konstrukce a analýza = Introduction to Algorithms. - 2. vyd. - M. : Williams, 2006. - S. 1296. - ISBN 0-07-013151-1 .
Ruda O. Teorie grafů. — M .: Nauka, 1968. — 336 s.
Grafy // Encyklopedický slovník mladého matematika / Komp. A. P. Savin. - M . : Pedagogika , 1985. - S. 86 -88. — 352 s.
Salii VN, Bogomolov AM Algebraické základy teorie diskrétních systémů. - M .: Fyzikální a matematická literatura, 1997. - ISBN 5-02-015033-9 .
Wilson R. Úvod do teorie grafů. — M .: Mir, 1977. — 208 s.
Harari F. Teorie grafů. — M .: Mir, 1973.