グラフ g の辺の最小サイズの彩色を求める.
FindEdgeColoring[g,{c1,c2,…}]
グラフ g の辺について彩色{c1,c2,…,ck}を求める.
FindEdgeColoring
グラフ g の辺の最小サイズの彩色を求める.
FindEdgeColoring[g,{c1,c2,…}]
グラフ g の辺について彩色{c1,c2,…,ck}を求める.
詳細とオプション
- FindEdgeColoringは彩色と辺のラベル付けとしても知られている.
- FindEdgeColoringは,通常,スケジューリングや割当ての問題に使われる.
- FindEdgeColoring[g]は g の辺について最小サイズの彩色{c1,c2,…,ck}を求める.ただし,ciは整数で g の隣接する指標が i と j の2辺 eiと ejについて ciと cjは等しくはない.
- FindEdgeColoring[g,{c1,c2,…}]は指定された色 ciを使う.
- FindEdgeColoring[g,l]は,事実上,FindEdgeColoring[g,{1,2,…,l}]に等しい.
例題
すべて開く すべて閉じる例 (2)
FindEdgeColoring[PetersenGraph[]]g = PetersenGraph[];FindEdgeColoring[g, ColorData[106, "ColorList"]]Annotate[g, {EdgeStyle -> Thread[EdgeList[g] -> %]}]スコープ (7)
FindEdgeColoringは無向グラフに使うことができる:
FindEdgeColoring[[image]]FindEdgeColoring[[image]]FindEdgeColoring[[image]]FindEdgeColoring[[image]]FindEdgeColoring[{1 -> 2, 1 -> 3, 1 -> 4, 1 -> 5, 2 -> 3, 2 -> 5, 3 -> 4, 4 -> 5}]FindEdgeColoring[[image], ColorData[3, "ColorList"]]FindVertexColoringは大きいグラフに使うことができる:
g = GridGraph[{10, 10, 10}];AbsoluteTiming[FindEdgeColoring[g];]アプリケーション (3)
基本的なアプリケーション (1)
トーナメントの日程 (2)
総当たりのトーナメントの日程を組むために,頂点がトーナメントの競技者に,辺が試合に対応するグラフを作る.
g = [image];競技者の各ペアがいずれかのラウンドでお互いに競技するように,できるだけ少ないラウンドの日程を求める:
res = FindEdgeColoring[g]EdgeList[g][[Flatten@Position[res, 1]]]FindEdgeColoring[g, ColorData[106, "ColorList"]];Annotate[g, {EdgeStyle -> Thread[EdgeList[g] -> Thread[{Thickness[0.02], %}]]}]NFLでは,ある年に対戦するチームのペアは前年のチームの成績によって決定される.頂点がチームに,辺が試合に相当するグラフを作る:
g = [image];FindEdgeColoring[g]Max[%]特性と関係 (4)
g = PetersenGraph[]FindVertexColoring[LineGraph[g]]FindEdgeColoring[g]FindEdgeColoringを使ってEdgeChromaticNumberを計算する:
g = PetersenGraph[];Max[FindEdgeColoring[g]]EdgeChromaticNumber[g]単純グラフの辺彩色に必要な色の数は,グラフの最大次数
または
である:
g = Table[RandomGraph[{5, i}], {i, 10}];Max[FindEdgeColoring[#]]& /@ gMax[VertexDegree[#]]& /@ g二部グラフの辺彩色に必要な色の数はそのグラフの最大次数である:
g = {[image], [image], [image], [image]};BipartiteGraphQ /@ gMax[FindEdgeColoring[#]]& /@ gMax[VertexDegree[#]]& /@ g関連するガイド
テキスト
Wolfram Research (2021), FindEdgeColoring, Wolfram言語関数, https://reference.wolfram.com/language/ref/FindEdgeColoring.html.
CMS
Wolfram Language. 2021. "FindEdgeColoring." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/FindEdgeColoring.html.
APA
Wolfram Language. (2021). FindEdgeColoring. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindEdgeColoring.html
BibTeX
@misc{reference.wolfram_2026_findedgecoloring, author="Wolfram Research", title="{FindEdgeColoring}", year="2021", howpublished="\url{https://reference.wolfram.com/language/ref/FindEdgeColoring.html}", note=[Accessed: 08-November-2026]}
BibLaTeX
@online{reference.wolfram_2026_findedgecoloring, organization={Wolfram Research}, title={FindEdgeColoring}, year={2021}, url={https://reference.wolfram.com/language/ref/FindEdgeColoring.html}, note=[Accessed: 08-November-2026]}