Shannon multigraf

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 25 december 2019; kontroller kräver 3 redigeringar .

Inom grafteorin är Shannon multigrafer en speciell sorts triangulära grafer som används i studien av kantfärgning . Withing döpte dessa grafer efter Claude Shannon [1] .

Shannon multigrafer är multigrafer med tre vertex som uppfyller ett av följande villkor:

a) alla tre hörn är förbundna med samma antal kanter.
b) samma som i a) men ytterligare en kant läggs till.

Mer exakt är en graf en Shannon-multigraf om tre hörn är sammankopplade med respektive kanter . Denna multigraf har en maximal grad av . Dess mångfald (det maximala antalet kanter som har samma ändar) är . $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$

Exempel

Shannon multigrafer
Sh(2)
Sh(3)
Sh(4)
Sh(5)
Sh(6)
Sh(7)

Kantfärgning

Enligt Shannons sats [2] har varje multigraf med maximal grad en kantfärgning med maximala färger. Om talet är jämnt, visar exemplet med Shannon multigraf med multiplicitet att denna gräns är exakt: graden av vertex är exakt lika, men var och en av kanterna är konjugerade med vilken annan kant som helst, så färger krävs för alla korrekta kanter färg. $\Delta$ ${\frac {3}{2}}\Delta$ $\Delta$ $\Delta /2$ $\Delta ,$ ${\frac {3}{2}}\Delta$ ${\frac {3}{2}}\Delta$

En version av Vizings teorem [3] säger att vilken multigraf som helst med maximal grad och mångfald kan färgas med som mest färger. Återigen, denna gräns är exakt för Shannon multigrafer. $\Delta$ $\mu$ $\Delta +\mu$

Anteckningar

↑ V. G. Vizing. På uppskattningen av den kromatiska klassen för en p-graf // lör. Diskret analys. - 1964. - T. 3. - S. 25-30.
↑ Claude E. Shannon. Ett teorem om färgläggning av linjerna i ett nätverk // J. Math. Fysik. - 1949. - T. 28. - S. 148-151.
↑ V. G. Vizing. Kromatisk klass av en multigraf // Cybernetik. - 1965. - Utgåva. 3. - S. 29-39.

Litteratur

S. Fiorini, RJ Wilson. Kantfärgning av grafer. - 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 .

Länkar

Lutz Volkmann: Graphen an allen Ecken und Kanten . Föreläsningsanteckningar 2006, sid. 242 (tyska)