Graf (diskrétní matematika)

V matematiky , a přesněji teorie grafů , je graf je struktura skládá z objektů, kde některé páry předměty jsou ve vztahu. Objekty odpovídají matematickým abstrakcím a nazývají se vrcholy (nebo uzly nebo body ) a vztahy mezi vrcholy jsou hrany (nebo odkazy nebo čáry ). Rozlišujeme neorientované grafy , kde hrany symetricky spojují dva vrcholy, a směrované grafy , kde hrany, nazývané šipky , spojují dva vrcholy asymetricky.

Graf je často reprezentován diagramem ve formě sady bodů pro vrcholy, spojených dohromady přímými nebo zakřivenými čarami pro hrany, případně opatřenými šipkami pro případ orientovaných grafů. Grafy jsou jedním z předmětů studia v oblasti diskrétní matematiky .

Grafy jsou základním předmětem teorie grafů . Slovo „ graf “ v tomto smyslu poprvé použil James Joseph Sylvester v roce 1878.

Definice

Existuje několik variací v definici grafů v teorii grafů. Nejběžnější definice jsou následující.

Graf

V omezeném, ale velice rozšířené slova smyslu, je graf je dvojice G = ( V , E ), obsahující

V set z vrcholů (také volal uzly nebo body );
E ⊆ {{ x , y } | ( X , y ) ∈ V 2 ∧ x ≠ y} sada z okrajů (také nazývané odkazy , nebo linie ), které jsou dvojice vrcholů (tj. Jedna hrana je spojena se dvěma vrcholy oddělit).

Aby se předešlo pochybnostem, lze tento typ objektu nazvat přesně jednoduchým neorientovaným grafem .

V hraně { x , y } se vrcholy x a y nazývají konce nebo krajní vrcholy hrany. Říkáme, že hrana spojuje x a y a incidentu na x a y . Vrchol může existovat v grafu bez dopadající hrany. Smyčka je okraj, který spojuje vrchol na sebe. Tyto vícenásobné hrany jsou dva nebo více okrajů spojují stejné dva píky.

V obecnějším smyslu termínu umožňujícího více hran je graf triplet G = ( V , E , ϕ ) obsahující

V set z vrcholů (také volal uzly nebo body );
E sada z okrajů (také nazývané odkazy nebo čáry );
ϕ : E → {{ x , y } | ( X , y ) ∈ V 2 ∧ x ≠ y} funkce výskyt sdružovat se s každou hranu na dvojici vrcholů (tj okraj je spojen s dvěma odlišnými vrcholy).

Aby se předešlo pochybnostem, lze tento typ objektu nazvat přesně neorientovaným multigrafem .

Grafy, jak jsou definovány ve dvou předchozích definicích, nemohou mít smyčky, protože smyčka spojující vrchol x je hrana (pro jednoduchý neorientovaný graf) nebo dopadá na (pro neorientovaný multigraf) { x , x } = { x }, což je ne v {{ x , y } | ( x , y ) ∈ V 2 ∧ x ≠ y} . Aby bylo možné povolit smyčky, musí být definice rozšířeny. Pro jednoduché neorientované grafy platí E ⊆ {{ x , y } | ( x , y ) ∈ V 2 ∧ x ≠ y} se musí stát E ⊆ {{ x , y } | ( x , y ) ∈ V 2 } . U neorientovaných multigrafů platí : ϕ : E → {{ x , y } | ( x , y ) ∈ V 2 ∧ x ≠ y} musí být ϕ : E → {{ x , y } | ( x , y ) ∈ V 2 } . Aby se předešlo pochybnostem, lze tyto typy objektů nazvat přesně neorientovaným jednoduchým grafem se smyčkami a neorientovaným multigrafem se smyčkami .

Obecně se předpokládá, že V a E jsou konečné a mnoho výsledků pro nekonečné grafy přestává platit (nebo má jiné výroky), protože některé důkazní argumenty se nepřekládají na nekonečný případ. Navíc se často předpokládá , že V je neprázdné, ale E může být prázdná množina.

Pořadí grafu | V | je jeho počet vrcholů. Velikost grafu je | E |, jeho počet hran. Stupeň nebo valence z vrcholu je počet hran události na tomto vrcholu, kde se smyčka počítá zdvojnásobit.

V jednoduchém neorientovaném grafu řádu n je maximální stupeň vrcholu n - 1 a maximální velikost grafu je n ( n - 1) / 2 .

Okraje E z undirected grafu G vyvolat symetrické binární relace na ~ V nazývá sousednosti vztah s G . Konkrétně pro každou hranu { x , y } se říká , že její extrémní vrcholy x a y sousedí navzájem, což je označeno x ~ y .

Orientovaný graf

Orientovaný graf je graf, ve kterém jsou okraje mají orientaci.

V omezeném, ale velmi rozšířeném smyslu tohoto pojmu je směrovaný graf dvojice G = ( V , A ) (někdy G = ( V , E ) ) obsahující

V set z vrcholů (také volal uzly nebo body );
A ⊆ {( x , y ) | ( X , y ) ∈ V 2 ∧ x ≠ y } sada z šipek (nazývané také orientované hrany - někdy jednoduše hrany s odpovídajícím souborem s názvem E místo A -, orientované vazby nebo orientované čáry ), které jsou páry odlišné vrcholy( tj. šipka je spojena se dvěma odlišnými vrcholy).

Aby se předešlo pochybnostem, lze tento typ objektu nazvat přesně jednoduchým řízeným grafem .

V šipky ( x , y ), orientované od x do y , x se nazývá ocas šipky a y hlavy šipky. Šipka ( y , x ) se nazývá inverzní šipku z ( x , y ) .

V obecnějším smyslu termínu umožňujícího více šipek je směrovaný graf triplet G = ( V , A , ϕ ) (někdy G = ( V , E , ϕ ) ) včetně

V set z vrcholů (také volal uzly nebo body );
Má se soubor z šipek (také nazývaných orientovaných hran - někdy jen hrany s odpovídajícím souborem s názvem E místo A -, orientované vazby nebo orientované čáry );
ϕ : A → {( x , y ) | ( X , y ) ∈ V 2 ∧ x ≠ y} funkce výskyt sdružovat se s každou šipka na dvojici oddělených vrcholů (tj šipka je spojena se dvěma různými vrcholy).

Aby se předešlo pochybnostem, lze tento typ objektu nazývat přesně orientovaným multigrafem .

Směrované grafy, jak jsou definovány v předchozích dvou definicích, nemohou mít smyčky, protože smyčka spojující vrchol x je šipka (pro jednoduchý směrovaný graf) nebo dopadá na (pro směrovaný multigraf) ( x , x ), který není v { ( x , y ) | ( x , y ) ∈ V 2 ∧ x ≠ y} . Aby bylo možné povolit smyčky, musí být definice rozšířeny. Pro jednoduché orientované grafy A ⊆ {( x , y ) | ( x , y ) ∈ V 2 ∧ x ≠ y} se musí stát A ⊆ V 2 . Pro orientované multigrafy platí : ϕ : A → {( x , y ) | ( x , y ) ∈ V 2 ∧ x ≠ y} se musí stát ϕ : A → V 2 . Aby se předešlo pochybnostem, lze tyto typy objektů nazvat přesně jednoduchým řízeným grafem se smyčkami a cíleným multigrafem se smyčkami (nebo toulcem ).

Jednoduchý směrovaný graf se smyčkami je homogenní vztah ( binární vztah mezi množinou a sebou samým). Jednoduchý orientovaný graf s smyčky G = ( V , ) se nazývá symetrický , jestliže pro každou šipkou A , odpovídající inverzní šipka i A .

Smíšený graf

Smíšené graf je graf složený z neorientovaných hran a směřujících hran. Jedná se o triplet G = ( V , E , A ) pro jednoduchý smíšený graf a G = ( V , E , A , ϕ E , ϕ A ) pro smíšený multigraf s V , E , A , ϕ E a ϕ A jak je definováno výše. Orientované a neorientované grafy jsou speciální případy.

Vážený graf

Vážený graf nebo síť je graf, kde každý okraj nese číslo (jeho hmotnosti). Tyto váhy mohou představovat například náklady, délky nebo kapacity v závislosti na řešeném problému. Tyto grafy jsou běžné v různých kontextech, jako je problém s nejkratší cestou nebo problém s cestujícím prodejcem .

Druhy grafů

Asymetrický graf

Asymetrický graf (v angličtině „ orientovaný graf “ ) je orientovaný graf, kde alespoň jedno z dvojice ( x , y ) a ( y , x ) je šipka grafu. Takový graf je loopless. Vidíme to jako výsledek volby orientace pro každou hranu neorientovaného grafu bez smyčky.

Pravidelný graf

Pravidelný graf je (neorientovaný) graf, kde jsou všechny vrcholy mají stejný stupeň. Pokud je tento stupeň k , mluvíme také o k- regulárním grafu .

Kompletní graf

Úplný graf je jednoduchý graf , jehož vrcholy jsou vedle sebe, to znamená tak, že jakýkoli pár odlišných vrcholů je připojen hranou. Pokud je graf orientovaný , říkáme, že je úplný, pokud je každá dvojice vrcholů spojena přesně dvěma šipkami (jednou v každém směru).

Konečný graf

Konečný graf je graf, jehož sada vrcholů je konečný (a tedy i množina hran). Jinak je to nekonečný graf . Nejčastěji se uvažované grafy mlčky považují za konečné; pokud jsou nekonečné, je to výslovně uvedeno.

Související graf

Spojitý graf je neorientovaný graf, kde jakýkoli pár vrcholů jsou spojeny řetězci. Směrovaný graf je připojen, pokud je připojen neorientovaný graf získaný zapomenutím na orientaci hran. Je silně propojen, pokud je jakýkoli pár vrcholů spojen cestou, takže pokud pro jakýkoli pár ( x , y ) vrcholů existuje cesta od x do y a cesta od y do x . K-vrchol-připojený graf je graf, který má alespoň k +1 vrcholů a která zůstává stále po odstranění připojen k, 1; podobně je k-edge-spojený graf je graf, který zůstane propojený, když z něj odstraníme k - 1 hran.

Bipartitní graf

Bipartitní graf je graf, jehož sada uzlů může být rozdělen do dvou souborů X a Y tak, že neexistuje žádná hrana mezi dvěma vrcholy X , nebo mezi dvěma vrcholy Y . Ekvivalentně je bipartitní graf graf, jehož chromatické číslo je 2.

Úplný bipartitní graf je dvojdílný graf, kde jsou všechny vrcholy X jsou napojeny na všechny vrcholy Y a naopak.

Řetěz

Graf je řetězec řádu n ≥ 2, pokud se skládá z vrcholů n, které lze očíslovat, takže hrany jsou { v i , v i +1 } pro i = 1, 2,…, n - 1. Řetězec je ekvivalentním způsobem spojený graf, jehož vrcholy jsou stupně 2, kromě dvou, které jsou stupně 1. Řetězec v grafu je částečným podgrafem tohoto grafu.

Rovinný graf

Rovinný graf je graf, který lze vyvodit v rovině (nebo na kouli), aniž by obě hrany křížení.

Cyklický graf

Pořadí cyklus nebo n-cyklus graf je graf, jehož vrcholy mohou být očíslovány tak, že okraje jsou páry pro plus okraj . Cyklický graf lze charakterizovat jako spojený graf, jehož všechny vrcholy mají stupeň 2. $n \ ge3$ $v_ {1}, \ ldots, v_ {n}$ ${\ displaystyle [v_ {i}, v_ {i + 1}]}$ $i = 1, \ ldots, n-1$ ${\ displaystyle [v_ {n}, v_ {1}]}$

Strom

Strom je acyklický spojitý graf.

Les je acyklický graf, to znamená, že nesouvislý svazek jednoho nebo více stromů.

Ostatní třídy

Mezi další třídy grafů patří:

Petersenův graf a jeho zobecnění;
Perfektní grafy ;
Cographs ;
Cordal grafy ;
další grafy klasifikované podle jejich skupiny automorfismu : vrcholný graf , symetrický graf a přechodový graf vzdálenosti ;
Silně pravidelný graf a jejich zobecnění; vzdálenost-pravidelný graf .

Vlastnosti grafu

Dvě hrany grafu sousedí, pokud mají společný vrchol. Pokud je konec prvního oblouku začátkem druhého, jsou dva oblouky směrovaného grafu po sobě . Podobně dva vrcholy sousedí, pokud jsou končetinami stejné hrany (stejného oblouku). O hraně a přilehlém vrcholu se říká, že jsou vzájemně dopadající .

Graf tvořený jediným vrcholem a bez hran se často nazývá triviální ; graf bez vrcholu a hrany se také někdy nazývá nulový graf .

Pokud má každý vrchol štítek, je na vrcholech označen graf . Graf má na okrajích štítek, pokud má každý okraj štítek. V případě výčtu nebo bijekčních problémů můžeme uvažovat o označených nebo neoznačených grafech. Graf, jehož vrcholy (nebo hrany) jsou označeny barvami, je barevný graf.

Centrální vlastnosti grafu

V grafové analýze měří centralita důležitost a důležitost vrcholu. Rozlišujeme:

centrálnost stupeň , což je počet břitů události na vrcholu;
blízkost centrálnost což je převrácená hodnota součtu vzdáleností do všech ostatních vrcholů;
centrálnost zprostředkování , což je celkový počet nejkratší cesty procházející vrcholem.

Další opatření jsou výstřednost vrcholu, což je maximální vzdálenost od jakéhokoli jiného vrcholu, průměr grafu nebo poloměr .

Grafické operace

Různé operace, které vytvářejí nové grafy z daných grafů, lze seskupit do:

unární operace , které vytvářejí nový graf ze starého, například:
- Kontrakce hran ,
- Čárový graf ,
- Duální graf ,
- Doplňkový graf ,
- Přepisování grafů .
binární operace , které vytvářejí nový graf ze dvou starých, například:
- disjunktní spojení grafů,
- Kartézský součin ,
- tenzorový produkt,
- silný produkt,
- lexikografický produkt,
- sériově paralelní graf.

Aplikace

V teorii kategorií může být kategorie reprezentována orientovaným multigrafem, jehož vrcholy představují objekty a hrany morfismy . Functor mezi kategoriemi indukuje morphism grafů .
V informatice se směrované grafy používají k reprezentaci pojmů jako koncepční grafy , konečné automaty a mnoho dalších samostatných struktur.
Binární relace R na množině X definuje orientovaný graf (a naopak). V grafu je šipka od x do y právě tehdy, pokud xRy .
Graf může modelovat informace na sociálních sítích , například pojem „následovník“ na Twitteru .
Příkladem pravidelných směrovaných grafů jsou Cayleyovy grafy konečně generovaných skupin nebo graf kosetů Schreier (en) .
V chemii a zejména ve zjednodušeném znázornění vazeb mezi atomy tvořícími molekulu jsou široce používány grafy obecně neorientované, ale s více hranami.

Rozšíření

Grafy se zobecňují několika směry:

V hypergrafu může hrana spojit více než dva vrcholy.
Neusměrněný graf lze chápat jako zjednodušený komplex, jehož 1- simplexy jsou hrany a 0-simplexy vrcholy. V tomto aspektu jsou zjednodušené komplexy zobecněním grafů do vyšších dimenzí.
Libovolný graf také dává matroid .
V teorii modelu je graf jen logickou strukturou . V této souvislosti neexistuje žádné omezení počtu hran, které mohou být libovolným světovým číslem .
V bioinformatiky se síla analýzy graf (v) zavedla zvláštní grafy (dále jen „ výkonové grafy “ ), jako alternativa pro zastoupení neorientované grafy.
V geografických informačních systémech jsou geometrické sítě modely blízké grafům a z teorie grafů si vypůjčují mnoho konceptů pro prostorovou analýzu na silničních sítích nebo měřítka pro použití.

Poznámky a odkazy

Trudeau 1993 , str. 19: „ Graf je objekt se skládá ze dvou sad nazývaných jeho vrchol sady a její okraj sada “ .
In: JJ Sylvester, „ Chemistry and algebra “, Nature , sv. 17,7. února 1878, str. 284: „Každý invariant a kovariant se tak stane vyjádřitelným grafem přesně identickým s Kekuléanovým diagramem nebo chemikografem.“ ( DOI 10.1038 / 017284a0 , číst online ). a JJ Sylvester, „ K aplikaci nové atomové teorie na grafické znázornění invarianty a kovarianty binární kvantiky - se třemi dodatky “, American Journal of Mathematics, Pure and Applied ' , sv. 1, n o 1,1878, str. 64–90 ( DOI 10.2307 / 2369436 , číst online ).
Gross a Yellen 2004 , s. 35 .
(in) Edward A. Bender a S. Gill Williamson , Seznamy, rozhodnutí a grafy: Úvod do pravděpodobnosti ,2010, 251 s. ( číst online ) , s. 148
Například ( Iyanaga a Kawada 1977 , s. 234) nebo ( Biggs 1993 , s. 4).
(in) Edward A. Bender a S. Gill Williamson , Seznamy, rozhodnutí a grafy: Úvod do pravděpodobnosti ,2010, 251 s. ( číst online ) , s. 149
Například ( Graham et. Al. 1995 , s. 5).
(in) Edward A. Bender a S. Gill Williamson , Seznamy, rozhodnutí a grafy: Úvod do pravděpodobnosti ,2010, 251 s. ( číst online ) , s. 161
Strang 2005 .
Fletcher, Hoyle a Patty 1991 , s. 463: Vážený graf je graf, ve kterém je každé hraně e přiřazeno číslo w (e) , nazývané jeho váha .
Xingqin Qi , Eddie Fuller , Qin Wu a Yezhou Wu , „ Laplaciánská ústřednost: nové měřítko ústřednosti pro vážené sítě “, Information Sciences , sv. 194,Červenec 2012, str. 240–253 ( ISSN 0020-0255 , DOI 10.1016 / j.ins.2011.12.027 ).
Martin Grandjean , „ Analýza sociální sítě Twitteru: Mapování digitální humanitní komunity “, Cogent Arts & Humanities , sv. 3, n o 1,2016, str. 1171458 ( DOI 10.1080 / 23311983.2016.1171458 , číst online )
Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang a Reza Bosagh Zadeh WTF: Systém Who -to-Follow na Twitteru , Proceedings of the 22.nd International Conference on World Wide Web . DOI : 10.1145 / 2488388.2488433 .

Dodatky

Bibliografie

Obecné práce

Všechny učebnice diskrétní matematiky obsahují grafy:

Peter Fletcher , Hughes Hoyle a C. Wayne Patty , Foundations of Discrete Mathematics , Boston, PWS-KENT Pub. Co.,1991, 781 str. ( ISBN 0-534-92373-9 )
Ronald L. Graham, Martin Grötschel a Lovász Lovász (dirigent), Příručka kombinatoriky , MIT Press,1995( ISBN 0-262-07169-X )
Shôkichi Iyanaga a Yukiyosi Kawada, Encyklopedický slovník matematiky , MIT Press,1977( ISBN 0-262-09016-3 )
Gilbert Strang , lineární algebra a její aplikace , Brooks Cole,2005, 4 th ed. , 487 s. ( ISBN 0-03-010567-6 , číst online ).
(en) Daniel Zwillinger , Standardní matematické tabulky a vzorce CRC , Boca Raton / Londýn / New York atd., Chapman & Hall / CRC,27. listopadu 2002, 31 th ed. , 910 s. ( ISBN 1-58488-291-3 )

Konkrétní práce

Mnoho knih se zaměřuje na teorii grafů:

R. Balakrishnan a K. Ranganathan, Učebnice teorie grafů , New York, Springer-Verlag, kol. "Universitext",2012, xiii + 292 str. ( ISBN 978-1-4614-4528-9 , DOI 10.1007 / 978-1-4614-4529-6 , číst online )
Claude Berge, Teorie grafů a její aplikace , Paříž, Sbírka univerzitní matematiky,1963, 2 nd ed. , viii + 267 s. ( SUDOC 007608756 )
(en) Norman Biggs , Algebraic Graph Theory , Cambridge, Cambridge University Press,1993, 2 nd ed. , 205 s. ( ISBN 0-521-45897-8 )
(en) Béla Bollobás , teorie moderního grafu , New York / Berlín / Paříž, Springer,12. srpna 2002, 1 st ed. , 394 s. ( ISBN 0-387-98488-7 )
Jørgen Bang-Jensen a Gregory Z. Gutin, Digraphs: Theory, Algorithms and Applications , Springer-Verlag,2000( číst online )
Reinhard Diestel, teorie grafů , Springer, kol. "Graduate texty matematiky" ( n o 173)srpna 2016( Repr. 2010, 2005, 2000, 1997), 5 th ed. , 447 s. ( ISBN 978-3-662-53621-6 a 978-3-96134-005-7 , online prezentace , číst online )
(en) Jonathan L. Gross a Jay Yellen, Teorie grafů a její aplikace , Boca Raton (Fla.) / Londýn / New York atd., CRC Press,30. prosince 1998, 585 s. ( ISBN 0-8493-3982-0 , číst online )
Jonathan L. Gross a Jay Yellen (redaktoři), Příručka teorie grafů , CRC Press ,2004, 1192 s. ( ISBN 978-1-58488-090-5 , číst online ).
Frank Harary , teorie grafů , Addison Wesley Publishing Company,Leden 1995( ISBN 0-201-41033-8 )
Richard J. Trudeau , Úvod do teorie grafů , New York, Dover Publications ,1993, 209 s. ( ISBN 978-0-486-67870-2 , online prezentace )

Související články

externí odkazy

(en) Eric W. Weisstein , „ Graph “ , na MathWorld
Poznámka ve slovníku nebo obecné encyklopedii : Brockhaus Enzyklopädie