Vlastnost grafu - Graph property

v teorie grafů, a vlastnost grafu nebo graf neměnný je majetkem grafy to záleží pouze na abstraktní struktuře, ne na grafových reprezentacích, jako jsou konkrétní etikety nebo kresby grafu.[1]
Definice
Zatímco kreslení grafů a reprezentace grafů jsou platnými tématy v teorii grafů, aby se zaměřily pouze na abstraktní strukturu grafů, a vlastnost grafu je definována jako vlastnost zachovaná pod všemi možnými izomorfismy grafu. Jinými slovy se jedná o vlastnost samotného grafu, nikoli o konkrétní výkres nebo reprezentaci grafu. Termín „invariant grafu“ se používá pro vlastnosti vyjádřené kvantitativně, zatímco „vlastnost“ obvykle odkazuje na popisné charakterizace grafů . Například tvrzení „graf nemá vrcholy stupně 1“ je „vlastnost“, zatímco „počet vrcholů stupně 1 v grafu“ je „invariant“.
Více formálně je vlastnost grafu třídou grafů s vlastností, kterou mají libovolné dva izomorfní grafy buď patří do třídy, nebo do ní oba nepatří.[1] Ekvivalentně lze vlastnost grafu formalizovat pomocí funkce indikátoru třídy, funkce od grafů po booleovské hodnoty, která platí pro grafy ve třídě a jinak false; opět platí, že jakékoli dva izomorfní grafy musí mít stejnou funkční hodnotu jako každý jiný. Invariant grafu nebo parametr grafu lze podobně formalizovat jako funkci od grafů po širší třídu hodnot, jako jsou celá čísla, reálná čísla, posloupnosti čísel nebo polynomy, který má opět stejnou hodnotu pro libovolné dva izomorfní grafy.[2]
Vlastnosti vlastností
Mnoho vlastností grafů se chová dobře s ohledem na určité přirozené dílčí objednávky nebo předobjednávky definováno v grafech:
- Vlastnost grafu P je dědičný pokud každý indukovaný podgraf grafu s vlastností P má také majetek P. Například být a perfektní graf nebo být chordální graf jsou dědičné vlastnosti.[1]
- Vlastnost grafu je monotónní pokud každý podgraf grafu s vlastností P má také majetek P. Například být a bipartitní graf nebo být graf bez trojúhelníků je monotónní. Každá monotónní vlastnost je dědičná, ale nemusí to být nutně naopak; například podgrafy chordal grafů nemusí být nutně chordal, takže být chordal graph není monotónní.[1]
- Vlastnost grafu je menší zavřeno pokud každý graf minor grafu s vlastností P má také majetek P. Například být a rovinný graf je zavřený. Každá méně uzavřená vlastnost je monotónní, ale ne nutně naopak; například nezletilí grafy bez trojúhelníků nemusí být nutně samy o sobě bez trojúhelníků.[1]
Tyto definice lze rozšířit z vlastností na číselné invarianty grafů: invariant grafu je dědičný, monotónní nebo méně uzavřený, pokud funkce formalizující invariant vytváří monotónní funkce od odpovídajícího dílčího pořadí v grafech po reálná čísla.
Kromě toho byly studovány invarianty grafů s ohledem na jejich chování s ohledem na disjunktní odbory grafů:
- Invariant grafu je přísada pokud pro všechny dva grafy G a H, hodnota invariantu na disjunktním spojení G a H je součet hodnot na G a dál H. Například počet vrcholů je aditivní.[1]
- Invariant grafu je multiplikativní pokud pro všechny dva grafy G a H, hodnota invariantu na disjunktním spojení G a H je součinem hodnot na G a dál H. Například Hosoyův index (počet shody) je multiplikativní.[1]
- Invariant grafu je max pokud pro všechny dva grafy G a H, hodnota invariantu na disjunktním spojení G a H je maximum z hodnot na G a dál H. Například chromatické číslo je maxing.[1]
Kromě toho lze vlastnosti grafu klasifikovat podle typu grafu, který popisují: zda je graf neorientovaný nebo režie, zda se nemovitost vztahuje na multigrafy, atd.[1]
Hodnoty invarianty
The sada cílů funkce, která definuje invariant grafu, může být jedna z:
- Pravda-hodnota, pravda nebo nepravda, pro funkci indikátoru vlastnosti grafu.
- Celé číslo, například počet vrcholů nebo chromatické číslo grafu.
- A reálné číslo, tak jako zlomkové chromatické číslo grafu.
- Posloupnost celých čísel, například sekvence stupňů grafu.
- A polynomiální, tak jako Tutteův polynom grafu.
Grafové invarianty a izomorfismus grafů
Snadno vypočítatelné invarianty grafů slouží k rychlému rozpoznání izomorfismus grafu, nebo spíše neizomorfismus, protože pro jakýkoli invariant vůbec dva grafy s různými hodnotami nemohou (podle definice) být izomorfní. Dva grafy se stejnými invarianty však mohou nebo nemusí být izomorfní.
Graf neměnný Já(G) je nazýván kompletní pokud je totožnost invarianty Já(G) a Já(H) implikuje izomorfismus grafů G a H. Nalezení efektivně vypočítatelného takového invariantu (problém kanonizace grafů ) by znamenalo snadné řešení náročných problém grafového izomorfismu. Avšak i invariantní hodnoty s polynomem, jako je chromatický polynom obvykle nejsou úplné. The drápový graf a graf cesty například na 4 vrcholech mají oba stejný chromatický polynom.
Příklady
Vlastnosti
- Propojené grafy
- Bipartitní grafy
- Rovinné grafy
- Grafy bez trojúhelníků
- Perfektní grafy
- Euleriánské grafy
- Hamiltonovské grafy
Celočíselné invarianty
- Objednat, počet vrcholů
- Velikost, počet hran
- Počet připojené komponenty
- Pořadí obvodu, lineární kombinace počtu hran, vrcholů a komponent
- průměr, nejdelší z nejkratších cesta délky mezi dvojicemi vrcholů
- obvod, délka nejkratšího cyklu
- Konektivita vrcholů, nejmenší počet vrcholů, jejichž odstranění odpojí graf
- Připojení na hraně, nejmenší počet hran, jejichž odstranění odpojí graf
- Chromatické číslo, nejmenší počet barev pro vrcholy ve správném vybarvení
- Chromatický index, nejmenší počet barev pro hrany ve správném vybarvení hran
- Možnost volby (nebo seznam chromatické číslo), nejmenší číslo k takové, že G je k-volitelný
- Číslo nezávislosti, největší velikost nezávislé sady vrcholů
- Klika číslo, největší řád úplného podgrafu
- Arboricita
- Rod rodu
- Číslo stránky
- Hosoyův index
- Wienerův index
- Colin de Verdière graf invariantní
- Boxicity
Skutečné číslo invarianty
- Koeficient shlukování
- Centrálnost mezi
- Frakční chromatické číslo
- Algebraická konektivita
- Izoperimetrické číslo
- Estrada index
- Síla
Sekvence a polynomy
- Sekvence titulů
- Grafové spektrum
- Charakteristický polynom z matice sousedství
- Chromatický polynom, počet -barvy zobrazené jako funkce
- Tutteův polynom, bivariační funkce, která kóduje velkou část konektivity grafu
Viz také
- Logika grafů, jeden z několika formální jazyky slouží k určení vlastností grafu
- Topologický index, úzce související koncept v teorie chemických grafů
Reference
- ^ A b C d E F G h i Lovász, László (2012), "4.1 Parametry grafu a vlastnosti grafu", Velké sítě a limity grafů, Publikace kolokvia, 60, American Mathematical Society, str. 41–42.
- ^ Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "3.10 Parametry grafu", Sparsity: Graphs, Structures, and AlgorithmsAlgoritmy a kombinatorika, 28, Springer, str. 54–56, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, PAN 2920058.