Výkres označeného grafu na 6 vrcholech a 7 hranách.
V matematice je graf abstraktní reprezentace množiny objektů, kde jsou některé dvojice objektů propojeny odkazy. Propojené objekty jsou reprezentovány matematickými abstrakcemi nazývanými vrcholy a odkazy, které spojují některé dvojice vrcholů, se nazývají hrany. Obvykle je graf zobrazen v diagrammatické podobě jako množina teček pro vrcholy, spojených čarami nebo křivkami pro hrany. Grafy jsou jedním z objektů studia v diskrétní matematice.
Hrany mohou být směrové (asymetrické) nebo neřízené (symetrické). Pokud například vrcholy reprezentují lidi na večírku a mezi dvěma lidmi je hrana, pokud si potřesou rukou, pak se jedná o neřízený graf, protože pokud si osoba A potřásla rukou s osobou B, pak si osoba B potřásla rukou také s osobou A. Na druhou stranu, pokud vrcholy reprezentují lidi na večírku a existuje hrana od osoby A k osobě B, když osoba A ví o osobě B, pak je tento graf směrovaný, protože znalost někoho nemusí být nutně symetrický vztah (to znamená, že jedna osoba zná jinou osobu nemusí nutně znamenat opak; například mnoho fanoušků může vědět o celebritě, ale celebrita pravděpodobně nebude vědět o všech svých fanoušcích). Tento druhý typ grafu se nazývá směrovaný graf a hrany se nazývají směrované hrany nebo oblouky.
Vrcholy jsou také nazývány uzly nebo body a hrany jsou také nazývány čáry nebo oblouky. Grafy jsou základním předmětem studia teorie grafů. Slovo „graf“ bylo poprvé použito v tomto smyslu J.J. Sylvesterem v roce 1878.
Definice v teorii grafů se liší. Níže jsou uvedeny některé ze základních způsobů definování grafů a souvisejících matematických struktur.
Obecný příklad grafu (vlastně pseudografu) se třemi vrcholy a šesti hranami.
V nejběžnějším smyslu tohoto pojmu je graf uspořádaná dvojice G = (V, E) zahrnující množinu V vrcholů nebo uzlů společně se množinou E hran nebo čar, což jsou 2-prvkové podmnožiny V (tj. hrana souvisí se dvěma vrcholy a vztah je vzhledem ke konkrétní hraně reprezentován jako neuspořádaná dvojice vrcholů). Aby se předešlo nejednoznačnosti, lze tento typ grafu popsat přesně jako neřízený a jednoduchý.
Jiné smysly grafu vycházejí z různých pojetí množiny hran. V jednom zobecněném pojmu je E množina spolu se vztahem výskytu, která spojuje s každou hranou dva vrcholy. V jiném zobecněném pojmu je E množina neuspořádaných dvojic (ne nutně odlišných) vrcholů. Mnoho autorů nazývá tento typ objektu multigrafem nebo pseudografem.
Všechny tyto varianty a další jsou podrobněji popsány níže.
Vrcholy patřící k hraně se nazývají konce, koncové body nebo koncové vrcholy hrany. Vrchol může existovat v grafu a nepatří k hraně.
V a E jsou obvykle považovány za konečné, a mnoho z dobře známých výsledků nejsou pravdivé (nebo jsou spíše odlišné) pro nekonečné grafy, protože mnoho z argumentů selhat v nekonečném případě. Pořadí grafu je (počet vrcholů). Velikost grafu je , Počet hran. Stupeň vrcholu je počet hran, které se k němu připojují, kde hrana, která se připojuje k vrcholu na obou koncích (smyčka) se počítá dvakrát.
Pro okraj {u, v}, teoretici grafů obvykle používají poněkud kratší zápis uv.
Hrany E neřízeného grafu G indukují symetrický binární vztah ~ na V, který se nazývá přilehlý vztah G. Konkrétně pro každou hranu {u, v} se říká, že vrcholy u a v jsou přilehlé k sobě, což se označuje u ~ v.
Rozlišení podle hlavní definice
Jak je uvedeno výše, v různých kontextech může být užitečné definovat pojem graf s různými stupni obecnosti. Kdykoli je nutné striktně rozlišovat, používají se následující pojmy. Nejčastěji v moderních textech v teorii grafů, pokud není uvedeno jinak, graf znamená „neřízený jednoduchý konečný graf“ (viz definice níže).
Jednoduchý neřízený graf se třemi vrcholy a třemi hranami. Každý vrchol má stupeň dva, takže toto je také pravidelný graf.
Neorientovaný graf je takový, ve kterém hrany nemají žádnou orientaci. Hrana (a, b) je shodná s hranou (b, a), tj. nejde o seřazené dvojice, ale o množiny {u, v} (nebo 2-multisety) vrcholů.
Směrovaný graf nebo digraph je uspořádaná dvojice D = (V, A) s
Oblouk a = (x, y) je považován za směrovaný z x do y; y se nazývá hlava a x je nazýván ocas oblouku; y je považován za přímého nástupce x a x je považován za přímého předchůdce y. Pokud cesta vede z x do y, pak y je považován za nástupce x a dosažitelný z x a x je považován za předchůdce y. Oblouk (y, x) je nazýván oblouk (x, y) obrácený.
Variantou této definice je orientovaný graf, ve kterém nesmí být více než jedna z (x, y) a (y, x) oblouků.
Smíšený graf G je graf, ve kterém některé hrany mohou být směrovány a některé mohou být neřízené.
Je psán jako uspořádaný trojitý G = (V, E, A) s V, E a A definovanými výše.
Směrované a neřízené grafy jsou zvláštní případy.
Smyčka je hrana (směrovaná nebo neřízená), která začíná a končí na stejném vrcholu; ty mohou být podle aplikace povoleny nebo nepovoleny. V této souvislosti se hrana se dvěma různými konci nazývá spojnice.
Termínem „multigraf“ se obecně rozumí, že je povoleno použití více hran (a někdy i smyček). Tam, kde jsou grafy definovány tak, že umožňují použití smyček a více hran, je multigraf často definován tak, že znamená graf bez smyček, nicméně tam, kde jsou grafy definovány tak, že neumožňují použití smyček a více hran, je termín často definován tak, že znamená „graf“, který může mít jak více hran, tak smyček, i když mnozí pro tento význam používají termín „pseudograf“.
Na rozdíl od multigrafu, jednoduchý graf je neřízený graf, který nemá žádné smyčky a ne více než jednu hranu mezi dvěma různými vrcholy. V jednoduchém grafu hrany grafu tvoří množinu (spíše než multimnožinu) a každá hrana je odlišná dvojice vrcholů. V jednoduchém grafu s n vrcholy má každý vrchol stupeň, který je menší než n (konverzace však není pravda – existují ne-jednoduché grafy s n vrcholy, ve kterých má každý vrchol stupeň menší než n).
Graf je vážený graf, pokud je ke každé hraně přiřazeno číslo (váha). Takové váhy mohou představovat například náklady, délky nebo kapacity atd. v závislosti na daném problému. Někteří autoři takový graf nazývají sítí.
Ve výjimečných situacích je dokonce nutné mít hrany pouze s jedním koncem, tzv. poloviční hrany, nebo bez konců (volné hrany); viz např. podepsané grafy a zkreslené grafy.
Regulární graf je graf, kde každý vrchol má stejný počet sousedů, tj. každý vrchol má stejný stupeň nebo valenci. Regulární graf s vrcholy stupně k se nazývá k-regulární graf nebo regulární graf stupně k.
Kompletní graf s 5 vrcholy. Každý vrchol má hranu ke každému jinému vrcholu.
Kompletní grafy mají tu vlastnost, že každá dvojice vrcholů má hranu, která je spojuje.
Konečné a nekonečné grafy
Konečný graf je graf G = (V, E) takový, že V a E jsou konečné množiny. Nekonečný graf je graf s nekonečnou množinou vrcholů nebo hran nebo obojího.
Nejčastěji se v teorii grafů předpokládá, že grafy, o kterých se diskutuje, jsou konečné. Pokud jsou grafy nekonečné, je to obvykle výslovně uvedeno.
Grafické třídy z hlediska konektivity
V neřízeném grafu G se dva vrcholy u a v nazývají spojené, jestliže G obsahuje cestu z u do v. Jinak se nazývají odpojené. Graf se nazývá spojený, jestliže je spojena každá dvojice odlišných vrcholů v grafu; jinak se nazývá odpojený.
Graf se nazývá k-vertex-connected nebo k-edge-connected, pokud neexistuje žádná množina k-1 vrcholů (respektive hran), která by po odstranění graf odpojila. K-vertex-connected graf se často nazývá jednoduše k-connected.
Směrovaný graf se nazývá slabě propojený, pokud nahrazením všech jeho směrovaných hran neřízenými hranami vznikne propojený (neřízený) graf. Je silně propojený nebo silný, pokud obsahuje směrovanou cestu z u do v a směrovanou cestu z v do u pro každou dvojici vrcholů u, v.
Dvě hrany grafu se nazývají přilehlé (někdy shodné), pokud sdílejí společný vrchol. Dvě šipky směrovaného grafu se nazývají po sobě jdoucí, pokud je hlava té první na nožku (vrubovém konci) druhé. Podobně se dva vrcholy nazývají po sobě jdoucí, pokud sdílejí společnou hranu (po sobě jdoucí, pokud jsou na vrubu a na hlavě šipky), v takovém případě se říká, že společná hrana spojuje oba vrcholy. Hrana a vrchol na této hraně se nazývají incident.
Graf pouze s jedním vrcholem a bez hran se nazývá triviální graf. Graf pouze s vrcholy a bez hran je znám jako bezhranový graf. Graf bez vrcholů a bez hran se někdy nazývá null graf nebo prázdný graf, ale terminologie není konzistentní a ne všichni matematici povolují tento objekt.
Ve váženém grafu nebo digrafu je každá hrana spojena s nějakou hodnotou, různě nazývanou její cena, hmotnost, délka nebo jiný termín v závislosti na aplikaci; takové grafy vznikají v mnoha kontextech, například při optimálních problémech směrování, jako je problém obchodního cestujícího.
Normálně jsou vrcholy grafu, svou povahou jako prvky množiny, odlišitelné. Tento druh grafu může být nazýván vrcholově označený. Pro mnoho otázek je však lepší považovat vrcholy za nerozlišitelné; pak může být graf nazýván neoznačený. (Samozřejmě, vrcholy mohou být stále odlišitelné vlastnostmi samotného grafu, např. počty dopadajících hran). Stejné poznámky platí pro hrany, takže grafy s označenými hranami se nazývají hranově označené grafy. Grafy s popisky připevněnými k hranám nebo vrcholům jsou obecněji označovány jako označené. Následně se grafy, v nichž jsou vrcholy nerozlišitelné a hrany jsou nerozlišitelné, nazývají neoznačené. (Všimněte si, že v literatuře může označení platit i pro jiné druhy označení, kromě toho, které slouží pouze k rozlišení různých vrcholů nebo hran.)
Pokročilejší druhy grafů jsou:
V hypergrafu může hrana spojovat více než dva vrcholy.
Na neřízený graf lze pohlížet jako na zjednodušující komplex skládající se z 1-zjednodušení (hrany) a 0-zjednodušení (vrcholy). Komplexy jako takové jsou zobecněním grafů, protože umožňují větší-dimenzionální zjednodušení.
Každý graf dává vzniknout matroidu.
Analýza výkonových grafů ve výpočetní biologii zavádí výkonové grafy jako alternativní reprezentaci neřízených grafů.
V geografických informačních systémech jsou geometrické sítě úzce modelovány podle grafů a vypůjčují si mnoho konceptů z teorie grafů pro provádění prostorové analýzy na silničních sítích nebo rozvodných sítích.