Shannonův multigraf - Shannon multigraph - Wikipedia

V matematické disciplíně teorie grafů, Shannonovy multigrafy, pojmenoval podle Claude Shannon podle Vizing (1965), jsou speciální typ trojúhelníku grafy, které se používají v oblasti zbarvení hran zejména.

Shannonův multigraf je multigraf se 3 vrcholy, pro které platí některá z následujících podmínek:

• a) všechny 3 vrcholy jsou spojeny stejným počtem hran.
• b) jako v písmenu a) a přidá se jeden další okraj.

Přesněji řečeno, hovoří se o Shannonově multigrafu Sh (n), pokud jsou tři vrcholy spojeny pomocí ${ displaystyle left lfloor { frac {n} {2}} right rfloor}$, ${ displaystyle left lfloor { frac {n} {2}} right rfloor}$ a ${ displaystyle left lfloor { frac {n + 1} {2}} right rfloor}$ hran. Tento multigraf má maximum stupeň n. Jeho multiplicita (maximální počet hran v sadě hran, které mají všechny stejné koncové body) je ${ displaystyle 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í hran

Tento devítibřitý Shannonův multigraf vyžaduje devět barev v jakémkoli zbarvení hran; jeho vrchol je šest a jeho multiplicita je tři.

Podle věty o Shannon (1949), každý multigraf s maximálním stupněm ${ displaystyle Delta}$ má zbarvení hran, které se používá maximálně ${ displaystyle { frac {3} {2}} Delta}$ barvy. Když ${ displaystyle Delta}$ je dokonce příkladem Shannonova multigrafu s multiplicitou ${ displaystyle Delta / 2}$ ukazuje, že tato vazba je těsná: stupeň vrcholu je přesně ${ displaystyle Delta}$, ale každý z ${ displaystyle { frac {3} {2}} Delta}$ hrany sousedí se všemi ostatními hranami, takže to vyžaduje ${ displaystyle { frac {3} {2}} Delta}$ barvy v každém správném vybarvení hran.

Verze Vizingova věta (Vizingování 1964 ) uvádí, že každý multigraf s maximálním stupněm ${ displaystyle Delta}$ a mnohost ${ displaystyle mu}$ mohou být vybarveny maximálně ${ displaystyle Delta + mu}$ barvy. Tato shoda je opět těsná pro Shannonovy multigrafy.

Reference

• Fiorini, S .; Wilson, Robin James (1977), Barvení hran grafůPoznámky k výzkumu v matematice, 16, Londýn: Pitman, s. 34, ISBN  0-273-01129-4, PAN  0543798
• Shannon, Claude E. (1949), „Věta o vybarvení čar sítě“, J. Math. Fyzika, 28: 148–151, doi:10,1002 / sapm1949281148, hdl:10338.dmlcz / 101098, PAN  0030203.
• Volkmann, Lutz (1996), Fundamente der Graphentheorie (v němčině), Wien: Springer, str. 289, ISBN  3-211-82774-9.
• Vizing, V. G. (1964), „Na základě odhadu chromatické třídy a p-graf", Diskret. Analiz., 3: 25–30, PAN  0180505.
• Vizing, V. G. (1965), „Chromatická třída multigrafu“, Kibernetika, 1965 (3): 29–39, PAN  0189915.

externí odkazy

• Lutz Volkmann: Vykreslete allen Ecken und Kanten. Poznámky k přednášce 2006, s. 242 (německy)