Přeplněný hrabě

Přeplněný graf [ 1] je jednoduchý graf (bez více hran a smyček), jehož velikost je větší než součin maximálního stupně jeho vrcholů a poloviny jeho řádu zaokrouhleného dolů . $G$ $|E|$ $\displaystyle \Delta (G)$ $|V|$

|E|>\Delta (G)\lpodlaží |V|/2\rpodlaží

Pokud má graf přeplněný podgraf a = pak - se nazývá graf přeplněný podgrafem [2] [ 3] . $G$ $S$ $\displaystyle \Delta (S)$ $\displaystyle \Delta (G)$ $G$

Koncept přetečeného grafu byl zaveden při zvažování problémů barvení okrajů grafu, konkrétně při rozhodování, zda graf patří do třídy 1 nebo třídy 2. Jak vyplývá z Vizingova teorému, chromatický index grafu může být buď a potom graf patří do třídy 1 nebo a potom graf patří do třídy 2. $\chi ^{\prime }(G)=\Delta (G)$ $\chi ^{\prime }(G)=\Delta (G)+1$

Vlastnosti

Některé vlastnosti přetečení grafů:

Z věty [1] , která říká, že pokud má graf velikost takovou, že , kde je číslo hrany nezávislosti a je maximální stupeň jeho vrcholů , pak graf patří do třídy 2 a platí podmínky, že pokud je graf řádu , pak jeho číslo hrany nezávislosti , vlastnost následuje: $G$ $|E|$ $|E|>\beta _{1}(G)\Delta (G)$ $\beta _{1}(G)$ $\Delta (G)$ $G$ $|V|$ $\beta _{1}(G)=\lpatro |V|/2\rpatro$

Přeplněný graf je grafem třídy 2

Je to dokázáno jako věta [2] :

Pokud má graf podgraf přetečení, pak je přetečený i samotný graf.

Je dokázáno jako věta [1] .

Pořadí přeplněného grafu je liché číslo

Přetečení domněnka

Chetwind a Hilton [4] navrhli v roce 1986 to, co je nyní známé jako Overfull Graph Conjecture

Pokud maximální stupeň vrcholů grafu splňuje podmínku , kde je řád grafu, pak graf patří do třídy 2 právě tehdy, když se jedná o graf s přetečeným podgrafem.

3\Delta (G)\geqslant |V|

|V|

G

Tato domněnka, je-li pravdivá, by měla četné aplikace v teorii grafů, včetně 1-faktorizační domněnky [5] .

Algoritmy

V [6] je uveden algoritmus, který umožňuje najít pro graf, pro který všechny generované přetečení podgrafy v čase , kde a . $G$ $|V(S)|>|V(G)|-\Delta (G)$ $S$ $O(n\log(n)+m)$ $n=|V(G)|$ $m=|E(G)|$

Varianta tohoto algoritmu umožňuje pro graf najít všechny vygenerované podgrafy přetečení v lineárním čase . $G$ $2\Delta (G)\geq |V(G)|$ $O(n+m)$

Článek také představuje druhý algoritmus, který pracuje s prvním algoritmem, který vám umožňuje najít všechny vygenerované přetečení podgrafy grafu , což je v obecném případě v polynomiálním čase a pro běžný graf v čase . $G$ $3\Delta (G)\geq |V(G)|$ $O(n^{5/3} m)$ $G$ $O(n^{3})$

Poznámky

↑ 1 2 3 Chartran, 2009 , str. 258.
↑ 12 Chartran , 2009 , str. 260.
↑ Hilton, 1989 .
↑ Chetwynd, Hilton, 1986 , s. 303–317.
↑ Chetwynd, Hilton, 1989 , s. 103–112.
↑ Niessen, 2001 .

Literatura

Chartran G., Zhang P. Teorie chromatických grafů (anglicky) / Editor seriálu Kenneth H. Rosen. - Baca Ration, Londýn, New York: Chapman & Hall/CRC, 2009. - S. 483. - (Diskrétní matematika a její aplikace). - ISBN 978-1-58488-800-0 .

Chetwynd AG, Hilton AJW Star multigrafy se třemi vrcholy maximálního stupně // Mathematical Proceedings of the Cambridge Philosophical Society. - 1986. - Sv. 100 , iss. 2 . — S. 303–317 . - doi : 10.1017/S030500410006610X .
Chetwynd AG, Hilton AJW 1-faktorizace pravidelných grafů vysokého stupně – vylepšená hranice // Matematika . - 1989. - Sv. 75 , iss. 1–3 . — S. 103–112 . - doi : 10.1016/0012-365X(89)90082-4 .
Hilton AJW Dvě domněnky o barvení hran // Diskrétní matematika. - 1989. - Sv. 74 . — S. 61-64 .
Niessen T. Jak najít přeplněné podgrafy v grafech s velkým maximálním stupněm. II (anglicky) // Electronic Journal of Combinatorics. - 2001. - Sv. 8 , iss. 1 . (Research Paper 7)