シャノンマルチグラフ

数学の分野であるグラフ理論において、シャノン多重グラフは、ヴィイジング（1965）によってクロード・シャノンにちなんで名付けられた特殊なタイプの三角形グラフであり、特に エッジカラーリングの分野で使用されます。

シャノン多重グラフは、次のいずれかの条件が満たされる 3 つの頂点を持つ多重グラフです。

• a) 3 つの頂点はすべて同じ数の辺で接続されています。
• b) a) と同様ですが、さらに 1 つのエッジが追加されます。

より正確には、3 つの頂点がそれぞれ、、および辺で接続されている場合、シャノン多重グラフSh( n )と呼ばれます。この多重グラフの最大次数はnです。その多重度 (すべて同じ端点を持つ辺の集合内の辺の最大数) は です。 ${\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor }$${\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor }$${\displaystyle \left\lfloor {\frac {n+1}{2}}\right\rfloor }$ ${\displaystyle \left\lfloor {\frac {n+1}{2}}\right\rfloor }$

• シャノンマルチグラフ
• 
  し(2)
• 
  し(3)
• 
  し(4)
• 
  し(5)
• 
  し(6)
• 
  し(7)

シャノン (1949) の定理によれば、最大次数を持つすべてのマルチグラフには、最大で色を使用するエッジ彩色があります。が偶数の場合、多重度を持つシャノンのマルチグラフの例は、この境界が厳密であることを示しています。頂点次数はちょうど ですが、各エッジは他のすべてのエッジに隣接しているため、適切なエッジ彩色には 色が必要です。 ${\displaystyle \Delta }$${\displaystyle {\frac {3}{2}}\Delta }$${\displaystyle \Delta }$${\displaystyle \Delta /2}$${\displaystyle \Delta }$${\displaystyle {\frac {3}{2}}\Delta }$${\displaystyle {\frac {3}{2}}\Delta }$

Vizing の定理(Vizing 1964)のバージョンでは、最大次数と多重度を持つすべてのマルチグラフは、最大で色を使用して着色できると述べられています。繰り返しますが、この制限は Shannon マルチグラフに対して厳密です。 ${\displaystyle \Delta }$${\displaystyle \mu}$${\displaystyle \Delta +\mu }$

• フィオリーニ、S.; ウィルソン、ロビン・ジェームズ (1977)、「グラフのエッジカラーリング」、数学研究ノート、第 16 巻、ロンドン: ピットマン、p. 34、ISBN 0-273-01129-4、MR  0543798
• シャノン、クロード E. (1949)、「ネットワークの線の色付けに関する定理」、J. Math. Physics、28 : 148–151、doi :10.1002/sapm1949281148、hdl : 10338.dmlcz/101098、MR  0030203。
• Volkmann、Lutz (1996)、Fundamente der Graphentheorie (ドイツ語)、ウィーン: Springer、p. 289、ISBN 3-211-82774-9。
• Vizing, VG (1964)、「 pグラフの彩度クラスの推定について」、Diskret. Analiz.、3 : 25–30、MR  0180505。
• Vizing, VG (1965)、「マルチグラフの彩色クラス」、Kibernetika、1965 (3): 29–39、MR  0189915。

ウィキメディア・コモンズには、シャノン多重グラフに関連するメディアがあります。

• ルッツ・フォルクマン:グラフェン・アン・アレン・エッケン・アンド・カンテン。講義ノート 2006、p. 242 (ドイツ語)