Teorie grafů je disciplína matematika a počítač , který studiích grafy , které jsou abstraktní vzory výkresů sítí spojující předměty. Tyto modely se skládají z dat vrcholů (také nazývaných uzly nebo body , s odkazem na mnohostěn ) a hran (také nazývaných odkazy nebo čáry ) mezi těmito vrcholy; tyto hrany jsou někdy nesymetrické (grafy jsou pak označeny jako orientované ) a nazývají se šipky nebo oblouky .
Tyto algoritmy vyvinuté k řešení problémů týkajících se objekty této teorie mají četné aplikace ve všech oblastech souvisejících s pojmem sítě ( sociální sítě , počítačové sítě , telekomunikace , apod) a v mnoha dalších oblastech (např genetická ) jako pojem grafu , zhruba ekvivalentní binárnímu vztahu (nezaměňovat s grafem funkce ), je obecný. Velké a obtížné věty, jako je věta o čtyřech barvách, věta o dokonalém grafu nebo věta o Robertson-Seymourovi , pomohly založit tento předmět u matematiků a otázky, které ponechává otevřené, jako je Hadwigerova domněnka , ho činí živá větev diskrétní matematiky .
Existuje několik variací v definici grafů v teorii grafů. Nejběžnější definice jsou následující.
V omezeném, ale velice rozšířené slova smyslu, je graf je dvojice G = ( V , E ), obsahující
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. Tyto vícenásobné hrany jsou dvě nebo více hran, které spojují stejné dva vrcholy; nemohou existovat v jednoduchém neorientovaném grafu.
V obecnějším smyslu termínu umožňujícího více hran je graf triplet G = ( V , E , ϕ ) obsahující
Aby se předešlo pochybnostem, lze tento typ objektu nazývat přesně neorientovaným multigrafem .
Smyčka je okraj, který spojuje vrchol na sebe. 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} musí bý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 mají 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 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í
Aby se předešlo pochybnostem, lze tento typ objektu nazývat přesně orientovaným jednoduchý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ě
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 směrovaný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 .
Celkem existují tři hlavní skupiny grafů a pět kategorií:
Článek švýcarského matematika Leonharda Eulera , představený na Akademii v Petrohradě v roce 1735 a poté publikovaný v roce 1741, se zabýval problémem sedmi Königsbergových mostů , jak je schematicky znázorněno níže. Problémem bylo najít promenádu z daného bodu, která se do tohoto bodu vrací, procházející jednou a jen jednou každým ze sedmi mostů ve městě Königsberg. Cesta, která právě jednou prošla jakýmkoli hřebenem, se nazývala Eulerianova cesta nebo Eulerianský okruh, pokud končí tam, kde začala. Rozšířením se graf, který připouští Eulerianův obvod, nazývá Eulerianův graf , který tedy představuje první případ vlastnosti grafu. Euler formuloval, že graf je Eulerian pouze v případě, že každý vrchol má sudý počet hran. Zvyk je označovat jako Eulerovu větu , ačkoli důkaz poskytl až o 130 let později německý matematik Carl Hierholzer . Podobným problémem je projít každý vrchol přesně jednou a byl nejprve vyřešen zvláštním případem, kdy rytíř musel navštívit každý čtverec šachovnice arabským šachovým teoretikem Al-Adlim ve své práci Kitab ash -shatranj publikované kolem roku 840 a od té doby ztracen. Tour Rytířský byl studován podrobněji v XVIII tého století francouzský matematik Alexandre-Théophile Vandermonde , Pierre Remond de Montmort a Abraham de Moivre ; Britský matematik Thomas Kirkman studoval obecnější problém trasy, kde lze vrchol projít pouze jednou, ale taková trasa nakonec převzala jméno Hamiltonova cesta podle irského matematika Williama Rowana Hamiltona , a přestože tento studoval pouze jeden konkrétní případ. Proto přiznáváme Eulerovi počátek teorie grafů, protože jako první navrhl matematické zpracování otázky, za nímž následoval Vandermonde.
V polovině XIX th století, britský matematik Arthur Cayley se zajímal o stromech , které jsou speciální druh graf bez cyklu, tedy v níž je nemožné se vrátit do výchozího bodu, aniž by opačný cestu. Zejména studoval počet stromů s n vrcholy a ukázal, že tam jsou některé . To představovalo „jeden z nejkrásnějších vzorců enumerativní kombinatoriky “, pole spočívající v počítání počtu prvků v konečné sadě, a také otevřelo cestu k výčtu grafů, které mají určité vlastnosti. Tuto oblast výzkumu skutečně zahájil maďarský matematik George Pólya , který v roce 1937 publikoval teorém o počítání, který nese jeho jméno , a nizozemský matematik Nicolaas Govert de Bruijn . Cayleyova práce, stejně jako práce Polya, měla aplikace na chemii a anglický matematik James Joseph Sylvester , spoluautor Cayley, představil v roce 1878 termín „graf“ založený na chemii:
"Nemusí to být zcela bez zájmu čtenářů přírody, aby si byli vědomi analogie, která na mě nedávno velmi zapůsobila mezi větvemi lidského poznání, zjevně tak odlišnými jako chemie a moderní algebra." […] Každý invariant a kovariant se proto stane vyjádřitelným grafem přesně identickým s Kékuléanovým diagramem nebo chemikografem. "
Jeden z nejznámějších problémů v teorii grafů pochází z barvení grafů , kde cílem je určit, kolik různých barev stačí k úplnému vybarvení grafu tak, aby žádný vrchol neměl stejnou barvu jako jeho sousedé. V roce 1852 jihoafrický matematik Francis Guthrie představil čtyřbarevný problém v diskusi se svým bratrem, který se zeptal svého učitele Auguste De Morgana, zda by nějaká mapa mohla být vybarvena čtyřmi barvami, aby sousední země měly různé barvy. De Morgan nejprve poslal dopis irskému matematikovi Williamovi Rowanovi Hamiltonovi , který se nezajímal, a poté anglický matematik Alfred Kempe zveřejnil chybné důkazy v časopise American Journal of Mathematics , který právě založil Sylvester. Studium tohoto problému vedlo k mnoha vývojům v teorii grafů, a to Peter Guthrie Tait , Percy John Heawood , Frank Ramsey a Hugo Hadwiger .
Problémy faktorizace grafů se tak objevily na konci XIX . Století tím, že se zajímaly o překlenující podgrafy, tedy o grafy obsahující všechny vrcholy, ale pouze část okrajů. Překlenovací podgraf se nazývá k -faktor, pokud má každý jeho vrchol vrcholy k a první věty dal Julius Petersen ; například ukázal, že graf lze rozdělit na 2 faktory právě tehdy, když všechny vrcholy mají sudý počet hran (ale Bäblerovi trvalo 50 let, než se vypořádal s lichým případem). Ramseyova práce na zbarvení, a zejména výsledky maďarského matematika Pal Turana , umožnily rozvoj teorie extrémních grafů zaměřených na grafy dosahující maxima určité veličiny (například počtu hran) s danými omezeními, jako je například absence určitých podgrafů.
Ve druhé polovině XX th století, francouzský matematik Claude Berge přispívá k rozvoji teorie grafů podle svých příspěvků na dokonalé grafů a zavedení funkčního hypergraph (v návaznosti na připomínky z Jean-Marie Pla majícího používán v seminář) s monografií na toto téma. Jeho úvodní kniha o teorii grafů také nabídla originální alternativu, spočívající spíše v osobní procházce než v úplném popisu. Bude také známkou francouzského výzkumu v této oblasti společným vytvořením týdenního semináře s Marcel-Paul Schützenbergerem v Institutu Henriho Poincaré, setkání v pondělí v Maison des Sciences de l'Homme a vedením kombinatorického týmu z Paříž.
Němci Franz Ernst Neumann a Jacobi , fyzik a matematik, založili v roce 1834 sérii seminářů. Německý fyzik Gustav Kirchhoff byl jedním ze studentů účastnících se semináře v letech 1843 až 1846 a v roce 1845 rozšířil práci Georga Ohma, aby ustanovil Kirchhoffovy zákony vyjadřující zachování energie a náboje v elektrickém obvodu . Jeho zákon uzlů zejména uvádí, že součet intenzit proudů vstupujících do uzlu se rovná té, která jej opouští. Elektrický obvod lze chápat jako graf, ve kterém vrcholy jsou uzly obvodu a hrany odpovídají fyzickým spojením mezi těmito uzly. Pro modelování proudů protékajících obvodem se má za to, že každou hranu lze protnout proudem . To nabízí mnoho analogií, například tok kapaliny, jako je voda, sítí kanálů nebo cirkulace v silniční síti. Jak je stanoveno zákonem uzlů, tok ve vrcholu je zachován nebo identický na vstupu i na výstupu; například voda vstupující do kanálu nezmizí a kanál neprodukuje žádnou vodu, takže z ní odchází tolik vody, kolik vstupuje. Okraj má navíc kapacitní limit, stejně jako kanál může nést určité maximální množství vody. Přidáme-li, že tok začíná v určitém vrcholu ( zdroj ) a že končí v jiném ( propad ), získáme základní principy studia toků v grafu.
Pokud vezmeme v úvahu, že zdrojem je ropné pole a že vrt je rafinerie, kde je vypouštěn, pak chceme upravit ventily tak, aby měl nejlepší možný tok ze zdroje do vrtu. Jinými slovy, usilujeme o co nejefektivnější využití kapacity každé z hran, což je problém s maximálním průtokem . Předpokládejme, že graf „rozdělíme“ na dvě části, takže zdroj je v jedné a dřez v druhé. Každý stream musí procházet mezi dvěma částmi, a je proto omezen maximální kapacitou, kterou může jedna část odeslat druhé. Nalezení řezu s nejmenší kapacitou tedy naznačuje místo, kde je síť nejvíce omezená, což odpovídá stanovení maximálního toku, který ji může protínat. Tato věta se nazývá flow-max / cut-min a byla založena v roce 1956.
Studium síťových toků je zobecněno několika způsoby. Hledání maxima, zde v případě toku, je optimalizační problém , kterým je odvětví matematiky spočívající v optimalizaci ( tj. Nalezení minima nebo maxima) funkce za určitých omezení. Tok sítě podléhá třem omezením: omezení kapacity na každém okraji, vytvoření nenulového toku mezi zdrojem a jímkou ( tj. Zdroj vytváří tok) a rovnost vstupního / výstupního toku pro jakýkoli jiný vrchol než zdroj a jímky ( tj. ani nespotřebovávají, ani negenerují část toku). Jelikož jsou tato omezení lineární , je problém toku sítě součástí lineární optimalizace . K problému je také možné přidat další proměnné, aby se zohlednilo více situací: můžeme tedy mít několik zdrojů a propadů (in) , minimální kapacitu (in) na každé hraně, náklady při použití hrany nebo zesílení toku (pro) procházejícího hranou.
Až do poloviny XX th století, stavební algoritmus grafu nebyl náhodný: tak dlouho, dokud parametry poskytované algoritmu nezměnil, pak graf je postaven byl stejný. Poté byla zavedena určitá dávka náhodnosti a algoritmy se tak staly pravděpodobnostními . Matematik ruského původu Anatol Rapoport měl tuto myšlenku poprvé v roce 1957, ale o dva roky později ji formálně navrhli nezávisle maďarští matematici Paul Erdős a Alfréd Rényi . Přemýšleli, jak vypadá „typický“ graf s n vrcholy a hranami m . Chtěli vědět, které vlastnosti lze najít s n vrcholy a hranami m vytvořenými náhodně. Protože pevné množství m není praktické na tuto otázku odpovědět, bylo rozhodnuto, že každá hrana bude existovat s pravděpodobností p . To byl počátek teorie náhodných grafů , kde uvažujeme počet vrcholů n dostatečně velká, a máme zájem o pravděpodobnosti p dostatečné pro graf mít určitou vlastnost.
Erdős a Rényi zjistili, že graf se nevyvíjel lineárně, ale místo toho existovala kritická pravděpodobnost p, po které se radikálně změnil. Toto chování je ve fyzice dobře známé: bez ohledu na to, zda je do mrazničky vložena sklenice vody, při poklesu pod 0 ° C se postupně nemění na led . Voda měla dvě fáze (kapalná a ledu) a přechází z jednoho do druhého o jev nazývaný fázového přechodu, přechod je rychlý kolem kritického bodu , který je v tomto případě, že teplota 0 ° C . U mnoha pozorovaných vlastností fungují náhodné grafy stejným způsobem: existuje kritická pravděpodobnost, pod kterou jsou v subkritické fázi a nad kterou procházejí v superkritické fázi. V případě náhodného grafu je pravděpodobnost, že sledujeme vlastnost, která nás zajímá, v subkritické fázi nízká, ale v nadkritické fázi se stává velmi vysokou ( tj. Kvazistotou); děj pravděpodobnosti, že vlastnost bude mít funkci p, má tedy velmi zvláštní vzhled, zjednodušený v diagramu vpravo.
Kromě běžného slovníku fází se ve statistické fyzice nachází teorie náhodných grafů ve formě teorie perkolace . Ten původně zamýšlel studovat tok tekutiny porézním materiálem . Pokud například ponoříme pemzu do kbelíku naplněného vodou, zajímá nás, jak bude voda protékat kamenem. Při modelování tohoto problému se zaměřujeme na důležité parametry: na věku nebo barvě kamene nezáleží, zatímco otvory nebo „kanály“, ve kterých může voda cirkulovat, jsou zásadní. Nejjednodušší abstrakcí je vidět kámen jako mřížku, kde každý kanál existuje s pravděpodobností p . Najdeme tedy model náhodného grafu, ale s prostorovým omezením : hrana může existovat pouze mezi dvěma vrcholy, pokud jsou sousedy v mřížce. Toto omezení však lze odstranit, aby se vytvořila rovnocennost mezi teorií grafů a teorií perkolace. Nejprve může být graf n vrcholů reprezentován mřížkou s n rozměry; protože nás zajímá případ, kdy n je dostatečně velké, to znamená, že se tím vytvoří ekvivalence s perkolací v nekonečné dimenzi. Kromě toho existuje kritická dimenze , takže výsledek již nezávisí na dimenzi, jakmile je dosaženo ; tato kritická dimenze je považována za 6, ale mohla být prokázána pouze u 19.
Od počátku roku 2000 bylo navrženo mnoho modelů k nalezení jevů pozorovaných v grafech, jako je ten, který představuje spojení mezi hollywoodskými herci (získanými IMDb ) nebo částmi webu . V roce 1999 Albert-László Barabási a Réka Albert vysvětlili, že jeden z těchto jevů „je důsledkem dvou mechanismů: síť neustále roste s přidáváním nových vrcholů a nové vrcholy se s určitými preferencemi připoutávají k ostatním, kteří jsou již v pořádku na místě ". Kolem jejich modelu se usadila určitá zmatek: pokud to skutečně umožňuje získat požadovaný jev, není to jediný model, který dospěl k tomuto výsledku, a proto nemůžeme uzavřít pohled na fenomén, který je výsledkem preferenčního procesu připoutání. Fenoménů malého světa a svobody měřítka , pro které bylo navrženo mnoho modelů, lze dosáhnout jednoduše náhodnými grafy: technika Michaela Molloye a Bruce Reeda umožňuje dosáhnout účinku bez měřítka, zatímco Li , Leonard a Loguinov vedou do malého světa.
Formálně je označen graf : každý vrchol nebo hrana patří do množiny, proto nese označení . Grafy jsou obvykle označeny celými čísly, ale štítek může ve skutečnosti patřit do jakékoli sady: sada barev, sada slov, sada reálných čísel. Následující příklady ukazují grafy označené celými čísly a písmeny. Označení grafu může být navrženo tak, aby poskytlo užitečné informace o problémech, jako je směrování : počínaje od vrcholu chceme dosáhnout vrcholu , tj. Chceme směrovat informace z do . V závislosti na tom, jak jsou vrcholy označeny, štítky, které nesou a umožňují nám snadno najít způsob. Například v grafu Kautz (v), kde je maximální vzdálenost mezi dvěma vrcholy , si představte, že se nacházíme na označeném vrcholu a na který chceme jít : stačí posunout štítek zadáním cíle, který udává cestu
Tato cesta zní následovně: pokud jste v horní části se štítkem , přejdete k sousedovi se štítkem atd.
Tváří nás však problém: podíváme-li se nad ilustraci seznamu stromů se 2, 3 a 4 vrcholy, mnoho z nich má přesně stejnou strukturu, ale jiné označení (zde dané barvami). Abychom mohli studovat pouze strukturu, potřebujeme tedy nástroj umožňující ignorovat označení, tj. Poskytnout strukturální ekvivalenci. Za tímto účelem zavedeme pojem morfismu. Graf morfismus , nebo graf homomorphism , je aplikace mezi dvěma grafy, které respektuje strukturu grafů. Jinými slovy, obraz grafu ve musí respektovat přítomnost sousednosti vztahy v . Přesněji řečeno, v případě, a jsou dva grafy, aplikace je morfismus grafů v případě, kde se transformuje vrcholy G do těch z H, a hrany G na ty z H, při respektování následující omezení: v případě, že je hrana mezi dvěma vrcholy pak musí být hrana mezi dvěma odpovídajícími vrcholy . O homomorfismu říkáme , že je to injekce (respektive surjekce ), pokud má dvě funkce a je injektivní (respektive surjektivní); pokud jsou injektivní i surjektivní, tj. bijektivní , pak jde o izomorfismus grafu . Pokud jsou dva grafy izomorfní, pak mají stejnou strukturu: bez ohledu na to, jak jsou nakresleny nebo označeny, je možné přesunout vrcholy nebo změnit štítky tak, aby jeden byl kopií druhého, jak je znázorněno níže. Pak označíme neznačeným grafu na třídu ekvivalence z grafu pro vztah izomorfizmu. Dva izomorfní grafy pak budou považovány za rovnocenné, pokud je budeme považovat za neznačené grafy.
Graf G | Graf H | Izomorfismus mezi G a H |
---|---|---|
![]() |
![]() |
|
Slovo graf může v závislosti na kontextu označit označený nebo neznačený graf. Když mluvíme o webovém grafu, štítky jsou adresy URL a mají význam. Slovo se používá k označení označeného grafu. Naproti tomu je Petersenův graf vždy považován za izomorfismus, tedy neznačený, zajímavé jsou pouze jeho strukturní vlastnosti.
Hypercube označeny na abecedě
Graf označený celými čísly
Graf s písmeny
Libovolný graf může být reprezentován maticí . Vztahy mezi hranami a vrcholy, nazývané vztahy dopadu, jsou všechny reprezentovány maticí dopadu grafu. Vztahy sousedství (jsou-li dva vrcholy spojeny hranou, sousedí) jsou reprezentovány jeho maticí sousedství . Je definován
Graf | Reprezentace pomocí matice sousedství | Reprezentace laplaciánskou maticí (není normalizováno) |
---|---|---|
![]() |
Mnoho informací v grafu může být reprezentováno maticí. Například matice stupňů je diagonální matice, kde prvky odpovídají počtu spojů vrcholu , to znamená jeho stupni . Pomocí této a předchozí matice můžeme také definovat lapovou matici ; získáme její normalizovaný tvar o , kde označuje matici identity , nebo můžeme jej získat přímo od každého z prvků:
Tyto reprezentace závisí na tom, jak jsou označeny vrcholy grafu. Představme si, že zachováme stejnou strukturu jako v předchozím příkladu a obrátíme popisky 1 a 6 : potom obrátíme sloupce 1 a 6 matice sousedství. Existují však veličiny, které nezávisí na tom, jak označíme vrcholy, například minimální / maximální / průměrný stupeň grafu. Tyto veličiny jsou invarianty grafu: nemění se podle číslování. Zatímco adjacence nebo laplaciánská matice se liší, její spektrum , to znamená sada jejích vlastních čísel , je neměnné. Studium vztahu mezi spektry a vlastnostmi grafu je předmětem teorie spektrálních grafů ; mezi zajímavými poměry spektrum poskytuje informace o chromatickém čísle , počtu připojených komponent a cyklech grafu.
Protože grafy mohou představovat mnoho situací, existuje mnoho algoritmů ( tj. Programů), které je používají. Složitost algoritmu sestává v podstatě vědět, pro daný problém, jak je nutno ji řešit mnoho času a jaký je prostor stroj, který se bude používat. Některá grafická znázornění poskytují lepší výkon, to znamená, že problém je vyřešen rychleji nebo zabírá méně místa. V některých případech lze NP-úplný problém (nejobtížnější třída) na reprezentaci grafu vyřešit v polynomiálním čase (jednoduchá třída) s jinou reprezentací; Myšlenka není taková, že by stačilo dívat se na graf jinak, abychom problém vyřešili rychleji, ale že ten „zaplatí“ za to, aby jej transformoval, a ten pak „uloží“, aby problém vyřešil. Jednou z takových transformací je stromový rozklad navržený matematiky Robertsonem a Seymourem v jejich sérii Graph Minors . Rozklad stromu intuitivně představuje původní graf stromem, kde každý vrchol odpovídá podmnožině vrcholů G s určitými omezeními. Formálně je pro daný graf jeho stromový rozklad tam, kde je strom a funkce spojující s každým vrcholem sadu vrcholů . Musí být splněna tři omezení:
Šířka strom z rozkladu grafu je , že znamená, že velikost největšího sadu reprezentován vrchol minus 1; můžeme to vidět jako maximální abstrakci: pro vrchol stromu, kolik vrcholů grafu představujeme? Vytvoření rozkladu stromu libovolného grafu s nejmenší šířkou stromu je NP-těžký problém. To však lze u některých grafů provést rychle nebo u jiných, například u rovinných grafů, aproximovat ( tj. Lze je nakreslit bez překročení dvou hran).
Robertson a Seymour také vyvinuli koncept větvení . Abyste tomu porozuměli, musíte do stromu vložit více slovníku. V grafech je strom nakreslen „vzhůru nohama“: začínáme od kořene nahoře a sestupujeme, dokud nedosáhneme listů dole; jakýkoli vrchol, který není listem, se nazývá „vnitřní uzel“. Výsledkem rozkladu na větve je strom, ve kterém má každý vnitřní uzel přesně tři sousedy (jako v opačném příkladu) a kde každý list představuje hranu původního grafu. Je zaznamenána minimální hloubka rozkladu grafu a máme vztah . Pokud jde o rozklad stromů, je NP těžké postavit větvový rozklad s minimem pro jakýkoli graf; v tomto případě je tato konstrukce proveditelná pro rovinný graf .
Tyto reprezentace se používají na NP-úplné problémy technikami dynamického programování , které obvykle trvají exponenciální čas v nebo . Takovým problémem je například dominantní množina : chceme vědět, jestli existuje podmnožina vrcholů velikosti nanejvýš taková, že vrchol, který není v y, je spojen hranou. Pokud je graf rovinný, umožňuje tato technika vyřešit problém včas .
Způsob, jakým je graf znázorněn jako matematický objekt, byl popsán v předchozí části. V algoritmickém aspektu teorie grafů se snažíme navrhnout efektivní proces řešení problému zahrnujícího graf. Hlavními kritérii pro účinnost procesu jsou čas potřebný k získání odpovědi a prostor, který proces zabírá při své práci. Způsob, jakým graf reprezentujeme, ovlivňuje výkon v čase a prostoru: například pokud chceme znát existenci hrany mezi dvěma vrcholy, matice sousedství umožní okamžitě získat výsledek, který nazýváme v . Na druhou stranu je základní operace, jako je nalezení souseda vrcholu, na matici sousedství: v nejhorším případě bude nutné naskenovat celý sloupec a zjistit, že neexistuje žádný soused. Další datovou strukturou je seznam sousedů , který se skládá z pole, jehož vstup dává seznam sousedů vrcholu : na takové struktuře se hledání souseda provádí, když je existence hrany . Z hlediska času tedy volba struktury závisí na základních operacích, které si přejete optimalizovat.
Reprezentace seznamu sousedů grafu naproti: | ||
0 | přilehlý k | 0,1,2,3 |
1 | přilehlý k | 0 |
2 | přilehlý k | 0.3.4 |
3 | přilehlý k | 0.2 |
4 | přilehlý k | 2 |
Podobně prostor, který struktura spotřebovává, závisí na typu uvažovaného grafu: hrubá zkratka spočívá v tom, že seznam adjacencies zabírá méně místa než matice, protože matice bude řídká , ale to například vyžaduje více místa pro uložení náhodný graf se seznamy než s maticí; v obecném případě matice používá prostor, a proto seznamy používají, pokud je graf hustý, pak mohou být dostatečně velké, aby matice spotřebovala méně místa, a pokud je graf řídký, pak seznamy spotřebují méně prostoru. Jednoduché úpravy datové struktury mohou umožnit značný zisk: například v částečně doplněné reprezentaci seznamu speciální bit označuje, zda je seznam seznam sousedních přítomných nebo chybějících; tato technika umožňuje mít lineární algoritmy na doplňku grafu.
I když jsou tyto struktury lokální, existují také distribuované datové struktury . Princip těchto struktur spočívá v návrhu schématu označování tak, aby pro dva vrcholy a jeden mohl odpovědět na otázku typu „jaká je vzdálenost mezi a “ pouze pomocí štítků těchto uzlů; takové použití štítků bylo vidět v části „ Značení a morfizmy “ s Kautzovým grafem, kde můžeme odvodit cestu mezi dvěma vrcholy pouze díky jejich označení a délka této cesty nám dává vzdálenost. Označování je účinné, pokud umožňuje odpovědět na danou otázku pouze pomocí dvou značek, přičemž se minimalizuje maximální počet bitů pro značku. Kromě vzdálenosti může být typickou otázkou otestování sousednosti, to znamená vědět, zda jsou dva vrcholy blízko; Všimněte si, že se to scvrkává také na speciální případ vzdálenosti 1. První příklad efektivního značení pro testování sousednosti byl navržen v případě stromů a každý štítek se skládá ze dvou částí bitů: první část identifikuje vrchol a číslo až vyžaduje kódování bitů , zatímco druhá část identifikuje rodiče tohoto vrcholu; k otestování sousedství použijeme skutečnost, že dva vrcholy jsou sousedy ve stromu právě tehdy, je-li jeden z rodičů druhého.
Účinnost schématu označování souvisí s velikostí oddělovačů v grafu.
Definice - separátor je podmnožina vrcholů, že „rozděluje“ vrcholy grafu do dvou složek, a tak, že i zde k dispozici žádné hrany mezi vrcholy a .
Pokud má graf oddělovače velikostí , můžeme například navrhnout bitové štítky pro vzdálenost; to umožňuje přímo odvodit označení pro grafy, jejichž velikost oddělovačů je známa, například planární graf, kde má oddělovač velikost . A konečně, musíme nejen vzít v úvahu velikost označování, ale také čas potřebný vzhledem k tomu, dva štítky, provést dekódování odpovědi na otázku ( tedy to, co je vzdálenost? Jsou to sousedi?).
Mnoho problémů s grafy je NP-úplné, to znamená, že je těžké je vyřešit. Tato tvrdost je však nerovnoměrná: některé části problému mohou být obzvláště drsné, a tvoří tak jeho jádro, zatímco s jinými se dá celkem snadno vypořádat. Než tedy spustíte algoritmus na problém, který může být obtížný, je nejlepší věnovat nějaký čas jeho redukci, takže musíte vzít v úvahu pouze své jádro.