VertexChromaticNumber

VertexChromaticNumber[g]

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

詳細とオプション

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

例題

すべて開くすべて閉じる

例  (2)

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

完全グラフの彩色数：

その式：

スコープ  (6)

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

有向グラフ：

重み付きグラフ：

多重グラフ：

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

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

アプリケーション  (3)

日程を組む  (1)

大学には数多くの科目がある．各学生はそれらの科目のいくつかに登録する．各頂点が科目で2頂点間の辺は両方を履修している学生がいることを表すグラフを作る：

一人の学生が履修している2つの科目を同時間にしないような最小の時間スロットを求める：

モバイル無線周波数の割当て  (1)

周波数が塔に割り当てられる場合，同じ場所にある塔に割り当てられる周波数は異なっている必要がある．各頂点が塔を，2つの塔の間の辺がお互いに範囲内にあることを表すグラフを作る：

必要な周波数の最小数を求める：

地図彩色  (1)

各頂点がアフリカの国であり，2国が接している場合は2頂点間に辺があるグラフを作る：

隣接する国には異なる色を割り当てて地図に彩色する：

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

特性と関係  (8)

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

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

二部グラフは2色で彩色可能なグラフである：

1色で彩色可能なグラフは空グラフである：

頂点で 辺のグラフの彩色数 は1から までの数になる：

：

グラフにサイズ のクリークがあるなら，そのグラフの彩色数は少なくとも である：

頂点，彩色数 ，独立数 のグラフは を満足する：

FindVertexColoringを使ってVertexChromaticNumberを計算する：

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

テキスト

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

CMS

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

APA

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

BibTeX

@misc{reference.wolfram_2024_vertexchromaticnumber, author="Wolfram Research", title="{VertexChromaticNumber}", year="2021", howpublished="\url{https://reference.wolfram.com/language/ref/VertexChromaticNumber.html}", note=[Accessed: 18-November-2024 ]}

BibLaTeX

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