Shannon multigraf

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 25. prosince 2019; kontroly vyžadují 3 úpravy .

V teorii grafů jsou Shannonovy multigrafy speciálním druhem trojúhelníkových grafů , které se používají při studiu zbarvení hran . Withing pojmenoval tyto grafy po Claude Shannonovi [1] .

Shannonovy multigrafy jsou multigrafy se třemi vrcholy, které splňují jednu z následujících podmínek:

a) všechny tři vrcholy jsou spojeny stejným počtem hran.
b) stejné jako v a), ale je přidána jedna hrana navíc.

Přesněji řečeno, graf je Shannonův multigraf , pokud jsou tři vrcholy spojeny , respektive hranami. Tento multigraf má maximální stupeň . Jeho násobnost (maximální počet hran, které mají stejné konce) je . $Sh(n)$ $\left\lfloor {\frac {n}{2}}\right\rfloor$ $\left\lfloor {\frac {n}{2}}\right\rfloor$ $\left\lfloor {\frac {n+1}{2}}\right\rfloor$ $n$ $\left\lfloor {\frac {n+1}{2}}\right\rfloor$

Příklady

Shannonovy multigrafy
Sh(2)
Sh(3)
Sh(4)
Sh(5)
Sh(6)
Sh(7)

Barvení okrajů

Podle Shannonova teorému [2] má každý multigraf s maximálním stupněm zbarvení hran pomocí maximálních barev. Pokud je číslo sudé, příklad Shannonova multigrafu s násobností ukazuje, že tato hranice je přesná: stupeň vrcholu je přesně stejný, ale každá z hran je konjugována s jakoukoli jinou hranou, takže pro každou správnou hranu jsou vyžadovány barvy. zbarvení. $\Delta$ ${\frac {3}{2}}\Delta$ $\Delta$ $\Delta /2$ $\Delta ,$ ${\frac {3}{2}}\Delta$ ${\frac {3}{2}}\Delta$

Verze Vizingova teorému [3] uvádí, že jakýkoli multigraf s maximálním stupněm a multiplicitou lze vybarvit maximálně barvami. Opět platí, že tato hranice je přesná pro Shannonovy multigrafy. $\Delta$ $\mu$ $\Delta +\mu$

Poznámky

↑ V. G. Vizáž. O odhadu chromatické třídy p-grafu // Sat. Diskrétní analýza. - 1964. - T. 3. - S. 25-30.
↑ Claude E. Shannon. Věta o vybarvování čar sítě // J. Math. Fyzika. - 1949. - T. 28. - S. 148-151.
↑ V. G. Vizáž. Chromatická třída multigrafu // Kybernetika. - 1965. - Vydání. 3. - S. 29-39.

Literatura

S. Fiorini, RJ Wilson. Barvení okrajů grafů. - London: Pitman, 1977. - V. 16. - S. 34. - (Research Notes in Mathematics). - ISBN 0-273-01129-4 .
Lutz Volkmann. Fundamente der Graphentheorie (neopr.) . - Wien: Springer, 1996. - S. 289. - ISBN 3-211-82774-9 .

Odkazy

Lutz Volkmann: Graphen an allen Ecken und Kanten . Poznámky z přednášek 2006, str. 242 (německy)