FindEdgeColoring

FindEdgeColoring[g]

グラフ 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)

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

グラフの隣接辺に異なる色を割り当てる：

グラフを可視化する：

スコープ  (7)

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

有向グラフ：

重み付きグラフ：

多重グラフ：

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

グラフの隣接辺に異なる色を割り当てる：

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

アプリケーション  (3)

基本的なアプリケーション  (1)

パラメータ化されたグラフの辺彩色を可視化する：

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

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

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

最初のラウンドで競技する競技者のペアを求める：

試合に彩色する：

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

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

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

特性と関係  (4)

グラフの辺彩色はそのグラフの線グラフの頂点彩色である：

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

単純グラフの辺彩色に必要な色の数は，グラフの最大次数またはである：

二部グラフの辺彩色に必要な色の数はそのグラフの最大次数である：

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

テキスト

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_2024_findedgecoloring, author="Wolfram Research", title="{FindEdgeColoring}", year="2021", howpublished="\url{https://reference.wolfram.com/language/ref/FindEdgeColoring.html}", note=[Accessed: 18-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_findedgecoloring, organization={Wolfram Research}, title={FindEdgeColoring}, year={2021}, url={https://reference.wolfram.com/language/ref/FindEdgeColoring.html}, note=[Accessed: 18-November-2024 ]}