Pseudo Forest – Mapa znalostí

V teorii grafů pseudo les — je neorientovaný graf, ve kterém má jakákoli připojená složka nejvýše jeden cyklus. To znamená, že je to systém vrcholů a hran spojujících dvojice vrcholů, takže žádné dva cykly nemají společné vrcholy a nemohou být spojeny cestou. Pseudostrom je propojený pseudoles.

Názvy jsou brány analogicky se známými stromy a lesy (strom je souvislý graf bez cyklů, les je svazek odpojených stromů). Gabow a Tarjan připisují studium pseudolesů Dantzigově knize o lineárním programování z roku 1963, ve které se pseudolesy objevují při řešení některých problémů s dopravním tokem. Pseudolesy také tvoří teoretické grafové modely funkcí a objevují se v některých algoritmických problémech. Pseudolesy jsou řídké grafy – mají velmi málo hran vzhledem k počtu vrcholů – a jejich matroidní struktura umožňuje některé další rodiny řídkých grafů rozložit na svazky lesů a pseudolesů. Název „pseudoles“ pochází z článku Picarda a Keranna.

Související pojmy

Kostra grafu se skládá z minimální podmnožiny hran grafu tak, že z kteréhokoli vrcholu grafu se lze dostat do jakéhokoli jiného vrcholu pohybem po těchto hranách.

Cesta v grafu je posloupnost vrcholů, ve kterých je každý vrchol spojen s dalším hranou.

Souvislý graf je graf, který obsahuje právě jednu souvislou složku. To znamená, že mezi libovolným párem vrcholů v tomto grafu existuje alespoň jedna cesta. Jinými slovy, neexistuje žádný izolovaný vrchol (ten, který nemá žádné odpovídající hrany (tzv. „hrany incidentní s vrcholem 1“ (nebo 2)).

V teorii grafů jsou sérioparalelní grafy grafy se dvěma odlišnými vrcholy, nazývanými terminály, vytvořené rekurzivně dvěma jednoduchými operacemi. Tyto grafy lze použít k modelování sériových a paralelních zapojení elektrických obvodů.

Strom je souvislý acyklický graf. Propojenost znamená přítomnost cest mezi libovolným párem vrcholů, acykličnost znamená absenci cyklů a skutečnost, že mezi páry vrcholů je pouze jedna cesta.

Indukovaný podgraf grafu je další graf vytvořený z podmnožiny vrcholů grafu spolu se všemi hranami spojujícími dvojice vrcholů z této podmnožiny.

V teorii grafů je odpovídající nebo nezávislá množina hran v grafu množina párových nesousedících hran.

V teorii grafů je hloubka stromu spojeného neorientovaného grafu G numerickým invariantem G, minimální výška Trémauxova stromu pro supergraf G. Tento invariant a související pojmy se v literatuře objevují pod různými názvy, včetně pořadového čísla vrcholu, uspořádaného chromatického čísla a minimální výšky prořezávání stromu. Tento koncept je také blízký takovým konceptům, jako je cyklická hodnost orientovaných grafů a iterační výška jazyka regulárních jazyků; . Intuitivně, pokud je šířka stromu.

V teorii grafů je vnější rovinný graf graf, který připouští rovinný diagram, ve kterém všechny vrcholy patří vnější ploše.

Degenerace je také známá jako k-core číslo, šířka a vazba a je v podstatě stejná jako číslo zbarvení nebo Szekeres-Wilfovo číslo. k-degenerované grafy se také nazývají k-indukční grafy. Degeneraci grafu lze vypočítat v lineárním čase pomocí algoritmu, který postupně odstraňuje vrcholy s minimálním stupněm. Souvislá složka zbývající po odstranění všech vrcholů se stupněm menším než k se nazývá k-jádro grafu a degenerace grafu je .

Problém hamiltonovské cesty a problém hamiltonovského cyklu jsou problémy určení, zda existuje hamiltonovská cesta (cesta v neorientovaném nebo orientovaném grafu, která prochází všemi vrcholy grafu přesně jednou) nebo hamiltonovský cyklus v daném grafu (směrovaný nebo neorientovaný). Oba problémy jsou NP-úplné.

V teorii grafů je hranový graf L(G) neorientovaného grafu G grafem L(G) reprezentujícím okolí hran G.

V teorii grafů je graf cyklu graf skládající se z jednoho cyklu, nebo jinými slovy z řady vrcholů spojených uzavřenou cestou. Cyklický graf s n vrcholy je označen jako Cn. Počet vrcholů v Cn se rovná počtu hran a každý vrchol má stupeň 2, to znamená, že jakýkoli vrchol je incidentní přesně se dvěma hranami.

V teorii grafů je graf hyperkrychle Qn pravidelný graf s 2n vrcholy, 2n−1n hranami a n hranami sbíhajícími se v jediném vrcholu. Lze jej získat jako jednorozměrnou kostru geometrické hyperkrychle. Například Q3 je graf tvořený 8 vrcholy a 12 hranami trojrozměrné krychle. Dalším způsobem, jak získat graf, je začít z rodiny podmnožin množiny s n prvky použitím všech podmnožin jako vrcholů a spojením dvou vrcholů hranou, pokud jsou odpovídající množiny.

Stromovitost neorientovaného grafu je minimální počet lesů, na které lze rozložit okraje. Ekvivalentně se jedná o minimální počet kostry, které jsou potřeba k pokrytí okrajů grafu.

V teorii grafů je částečná krychle podgrafem hyperkrychle, který zachovává vzdálenosti (v podmínkách grafu) – vzdálenost mezi libovolnými dvěma vrcholy v podgrafu je stejná jako v původním grafu. Částečná krychle je ekvivalentně graf, jehož vrcholy mohou být označeny bitovými řetězci stejné délky, takže vzdálenost mezi dvěma vrcholy v grafu je rovna Hammingově vzdálenosti mezi těmito dvěma popisky. Toto označení se nazývá Hammingovo označení a představuje izometrické vložení částečné krychle do .

Charakterizace zakázaných grafů je metoda popisu rodiny grafů nebo hypergrafů určením podstruktur, které se nesmí objevit v žádném grafu v rodině.

V teorii grafů je vrchol základní jednotkou, která tvoří grafy – neorientovaný graf se skládá ze sady vrcholů a sady hran (neuspořádané dvojice vrcholů), zatímco orientovaný graf se skládá ze sady vrcholů a sady oblouků (uspořádané dvojice vrcholů). Na výkresech znázorňujících graf je vrchol obvykle označen kruhem se štítkem, hranou čárou a obloukem šipkou spojující vrcholy.

Eulerovský cyklus je eulerovská cesta, která je cyklem, tedy uzavřenou cestou, která prochází každým okrajem grafu právě jednou.

Problém nezávislých množin patří do třídy NP-úplných problémů v oblasti teorie grafů. Ekvivalent k problému kliky.

Problém izomorfního podgrafu je výpočetní problém, ve kterém jsou vstupem dva grafy G a H a úkolem je určit, zda G obsahuje podgraf, který je izomorfní k H.

Tato sbírka obsahuje definice pojmů z teorie grafů. Text psaný kurzívou označuje odkazy na výrazy v tomto slovníku (na této stránce).

Faktorově kritický graf (nebo téměř shodný graf) je graf s n vrcholy, ve kterém má každý podgraf s n − 1 vrcholy dokonalou shodu. (Dokonalá shoda v grafu je podmnožina hran s vlastností, že každý vrchol grafu je koncovým vrcholem právě jedné hrany v podmnožině.)

V teorii grafů se neorientovaný graf H nazývá menším grafem G, pokud H lze vytvořit z G odstraněním hran a vrcholů a stažením hran.

V teorii grafů je stromová dekompozice mapování grafu do stromu, které lze použít k určení šířky stromu grafu a urychlení řešení určitých výpočetních problémů na grafech.

V teorii grafů je dominující množina pro graf G = (V, E) podmnožinou D množiny vrcholů V tak, že každý vrchol, který není v D, sousedí alespoň s jedním prvkem v D. Číslo dominance γ(G) je počet vrcholů v minimální dominující množině G.

Apolloniův graf je neorientovaný graf vytvořený rekurzivním procesem dělení trojúhelníku na tři menší trojúhelníky. Apolloniovy grafy lze ekvivalentně definovat jako rovinné 3-stromy, jako maximální rovinné chordální grafy, jako jednoznačně 4-barevné rovinné grafy nebo jako blokové polytopové grafy. Grafy jsou pojmenovány po Apolloniovi z Pergy, který studoval související konstrukce kruhových výplní.

Minimální kostra (nebo minimální kostra) v připojeném váženém neorientovaném grafu je kostra tohoto grafu, která má minimální možnou váhu, kde hmotnost stromu je součtem vah jeho hran.

Klika neorientovaného grafu je podmnožinou jeho vrcholů, z nichž libovolné dva jsou spojeny hranou. Kliky jsou jedním ze základních pojmů teorie grafů a používají se v mnoha dalších matematických problémech a konstrukcích zahrnujících grafy. Kliky jsou také studovány v informatice — problém určení, zda klika dané velikosti v grafu existuje (problém kliky) je NP-úplný. Navzdory této obtížnosti se studuje mnoho algoritmů pro hledání klik.

Bipartitní graf nebo bigraf je matematický termín v teorii grafů, který označuje graf, jehož množinu vrcholů lze rozdělit na dvě části tak, že každá hrana grafu spojuje nějaký vrchol v jedné části s nějakým vrcholem v druhé části, tj. neexistuje žádná hrana spojující dva vrcholy v téže části.

Šířka cesty je také známá jako tloušťka intervalu (o jednu menší než je velikost největší kliky intervalového supergrafu G), hodnota separace vrcholů nebo číslo hledání vrcholu.

Orientace neorientovaného grafu je přiřazením směrů každé hraně, čímž se původní graf změní na orientovaný graf.

V teorii grafů je kruhový graf průsečíkový graf množiny tětiv kruhu. To znamená, že jde o neorientovaný graf, jehož vrcholy lze identifikovat s tětivami kružnice a tyto vrcholy sousedí právě tehdy, když se odpovídající tětivy protínají.

Most je v teorii grafů hrana, jejíž odstranění zvyšuje počet připojených komponent. Taková žebra jsou také známá jako řezná žebra, řezné oblouky nebo řezné šíje. Ekvivalentní definice je, že hrana je most právě tehdy, když není obsažena v žádném cyklu.

Orientovaný graf se nazývá silně souvislý, pokud jsou jakékoli dva jeho vrcholy silně propojeny. Dva vrcholy s a t jakéhokoli grafu jsou silně propojeny, pokud existuje řízená cesta z s do t a řízená cesta z t do s.

V teorii grafů je kontrakce hrany operace, která odstraní hranu z grafu, po které se vrcholy spojené hranou sloučí do jediného vrcholu. Kontrakce hran je základní operací v teorii grafů. Vertexová identifikace je další formou této operace se slabšími omezeními.

V topologické teorii grafů je 1-rovinný graf graf, který lze nakreslit v euklidovské rovině tak, že každá hrana má nanejvýš jeden průsečík s právě jednou další hranou.

V teorii grafů se graf nazývá tětivový, pokud každý z jeho cyklů se čtyřmi nebo více hranami má tětivu (hranu spojující dva vrcholy cyklu, která však není jeho součástí).

Problém pokrytí vrcholů je NP-úplný počítačový problém v teorii grafů. Často se používá v teorii složitosti k prokázání NP-úplnosti složitějších problémů.

V teorii grafů je multigraf (nebo pseudograf) graf, ve kterém je povoleno více hran (také nazývaných „paralelní“), tj. hran, které mají stejné koncové vrcholy. Dva vrcholy tedy mohou být spojeny více než jednou hranou (to odlišuje multigrafy od hypergrafů, ve kterých každá hrana může spojovat libovolný počet vrcholů, ne rovnou dva).

Stupeň grafu by se neměl zaměňovat s násobením grafu se sebou samým, který (na rozdíl od stupně grafu) má obecně mnohem více vrcholů než původní graf.

Periferní cyklus v neorientovaném grafu je intuitivně cyklus, který neodděluje žádnou část grafu od jiné části. Periferní cykly (nebo, jak byly poprvé nazývány, periferní polygony, protože Tat nazýval cykly „polygony“) byly poprvé studovány Tatem a hrají důležitou roli při popisu rovinných grafů a při vytváření prostorů cyklů nerovinných grafů.

V teorii grafů je průsečíkový graf graf, který představuje vzor průsečíku rodiny množin. Jakýkoli graf může být reprezentován jako průsečíkový graf, ale některé důležité speciální třídy lze definovat pomocí typů množin používaných k reprezentaci průniků množin.

Šířka stromu se často používá jako parametr v parametrické analýze složitosti grafových algoritmů. Grafy se šířkou stromu nejvýše k se nazývají částečné k-stromy. Mnoho dalších dobře prostudovaných rodin grafů má také omezenou šířku stromu.

Kompletní bipartitní graf (biclique) je speciální typ bipartitního grafu, ve kterém je libovolný vrchol v první části spojen se všemi vrcholy ve druhé části vrcholů.

Číslo fronty grafu je invariant grafu definovaný analogicky k číslu zásobníku (tloušťka knihy) a pomocí řazení FIFO (první dovnitř, první ven, fronta) místo řazení LIFO (poslední dovnitř, první ven, zásobník).

Orientovaný graf (zkráceně orgraph) je (multi)graf, jehož hranám je přiřazen směr. Nasměrované hrany se také nazývají oblouky a v některých zdrojích jednoduše hrany. Graf, ve kterém není žádné hraně přiřazen směr, se nazývá neorientovaný graf nebo neorientovaný graf.

Kombinatorika mnohostěnů je obor matematiky, který patří do kombinatoriky a kombinatorické geometrie a studuje problematiku počítání a popisu ploch konvexních mnohostěnů.

Chromatický polynom je polynom studovaný v algebraické teorii grafů. Polynom vypočítá počet zabarvení grafu jako funkci počtu barev. Polynom byl původně definován Georgem Davidem Birkhoffem ve snaze zaútočit na problém čtyř barev. Polynom byl zobecněn H. Whitneyem a W. T. Tatou na Tatův polynom a spojil jej s Pottsovým modelem statistické fyziky.

Hamiltonovský graf je matematickým objektem teorie grafů. Je to graf (soubor bodů a čar je spojujících), který obsahuje hamiltonovský cyklus. Hamiltonovský cyklus je v tomto případě cyklus (uzavřená cesta), který prochází každým vrcholem daného grafu právě jednou.