WOLFRAM

Wolfram言語 ＆ システムドキュメントセンター

EdgeChromaticNumber[g]

グラフ g の辺の彩色数を与える．

詳細とオプション
Details and Options Details and Options
例題  
例  
スコープ  
アプリケーション  
トーナメントの日程  
特性と関係  
関連項目
関連するガイド
履歴
引用書式

EdgeChromaticNumber

EdgeChromaticNumber[g]

グラフ g の辺の彩色数を与える．

詳細とオプション

  • EdgeChromaticNumberは彩色数としても知られている．
  • EdgeChromaticNumberは，隣接する2辺が同じ色にならないようにグラフ g の辺に割り当てられる色の最小数を与える．

例題

すべて開く すべて閉じる

例  (2)

ピーターセン(Petersen)グラフの辺彩色数を求める：

Wolfram Language code: EdgeChromaticNumber[PetersenGraph[]]

閉路グラフの辺彩色数：

Wolfram Language code: Table[EdgeChromaticNumber[CycleGraph[n]], {n, 2, 9}]

その式：

Wolfram Language code: FindSequenceFunction[%, n - 1]

スコープ  (6)

EdgeChromaticNumberは無向グラフに使うことができる：

Wolfram Language code: EdgeChromaticNumber[[image]]

有向グラフ：

Wolfram Language code: EdgeChromaticNumber[[image]]

重み付きグラフ：

Wolfram Language code: EdgeChromaticNumber[[image]]

多重グラフ：

Wolfram Language code: EdgeChromaticNumber[[image]]

規則を使ってグラフを指定する：

Wolfram Language code: EdgeChromaticNumber[{1 -> 2, 1 -> 3, 1 -> 4, 1 -> 5, 2 -> 3, 2 -> 5, 3 -> 4, 4 -> 5}]

EdgeChromaticNumberは大きいグラフに使うことができる：

Wolfram Language code: g = GridGraph[{10, 10, 10}];
Wolfram Language code: AbsoluteTiming[EdgeChromaticNumber[g];]

アプリケーション  (2)

トーナメントの日程  (2)

総当たりのトーナメントの日程を組むために，頂点がトーナメントの競技者に，辺が試合に対応するグラフを作る．

Wolfram Language code: g = [image];

競技者の各ペアがいずれかのラウンドでお互いに競技するように，できるだけ少ないラウンドの日程を求める：

Wolfram Language code: EdgeChromaticNumber[g]

日程を求める：

Wolfram Language code: FindEdgeColoring[g, ColorData[3, "ColorList"]]

試合に彩色する：

Wolfram Language code: Annotate[g, {EdgeStyle -> Thread[EdgeList[g] -> Thread[{Thickness[0.02], %}]]}]

NFLでは，ある年に対戦するチームのペアは前年のチームの成績によって決定される．頂点がチームに，辺が試合に相当するグラフを作る：

Wolfram Language code: g = [image];

必要な週末の最小数を求める：

Wolfram Language code: EdgeChromaticNumber[g]

試合を行われる週末に割り当てる：

Wolfram Language code: FindEdgeColoring[g]

特性と関係  (5)

閉路グラフの彩色数は，頂点数が偶数のときは2でそれ以外のときは3である：

Wolfram Language code: Table[EdgeChromaticNumber[CycleGraph[n]], {n, 4, 7}]

車輪グラフの彩色数は頂点数マイナス1である：

Wolfram Language code: Table[EdgeChromaticNumber[WheelGraph[n]], {n, 4, 7}]

FindEdgeColoringを使ってEdgeChromaticNumberを計算する：

Wolfram Language code: g = PetersenGraph[];
Wolfram Language code: Max[FindEdgeColoring[g]]
Wolfram Language code: EdgeChromaticNumber[g]

単純グラフの彩色数はそのグラフの最大次数またはである：

Wolfram Language code: g = Table[RandomGraph[{5, i}], {i, 10}];
Wolfram Language code: EdgeChromaticNumber /@ g
Wolfram Language code: Max[VertexDegree[#]]& /@ g

二部グラフの彩色数はそのグラフの最大次数である：

Wolfram Language code: g = {[image], [image], [image], [image]};
Wolfram Language code: BipartiteGraphQ /@ g
Wolfram Language code: EdgeChromaticNumber /@ g
Wolfram Language code: Max[VertexDegree[#]]& /@ g
Wolfram Research (2021), EdgeChromaticNumber, Wolfram言語関数， https://reference.wolfram.com/language/ref/EdgeChromaticNumber.html.

テキスト

Wolfram Research (2021), EdgeChromaticNumber, Wolfram言語関数， https://reference.wolfram.com/language/ref/EdgeChromaticNumber.html.

CMS

Wolfram Language. 2021. "EdgeChromaticNumber." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/EdgeChromaticNumber.html.

APA

Wolfram Language. (2021). EdgeChromaticNumber. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/EdgeChromaticNumber.html

BibTeX

@misc{reference.wolfram_2026_edgechromaticnumber, author="Wolfram Research", title="{EdgeChromaticNumber}", year="2021", howpublished="\url{https://reference.wolfram.com/language/ref/EdgeChromaticNumber.html}", note=[Accessed: 16-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_edgechromaticnumber, organization={Wolfram Research}, title={EdgeChromaticNumber}, year={2021}, url={https://reference.wolfram.com/language/ref/EdgeChromaticNumber.html}, note=[Accessed: 16-June-2026]}