FindVertexColoring

FindVertexColoring[g]

グラフ g の頂点について最小サイズの彩色を求める．

FindVertexColoring[g,{c₁,c₂,…}]

グラフ g の頂点について彩色{c₁,c₂,…,c_k}を求める．

詳細とオプション

FindVertexColoringはグラフ彩色および頂点のラベル付けとしても知られている．
FindVertexColoringは，通常，スケジューリングや割当て問題のモデル化に使われる．

FindVertexColoring[g]は，g の頂点について最小サイズの彩色{c₁,c₂,…,c_k}を与える．ただし，c_iは整数で指標 i と j を持った g の2つの隣接頂点 v_iと v_jについてc_iと c_jは等しくてはならない．
FindVertexColoring[g,{c₁,c₂,…}]は指定された色 c_iを使う．
FindVertexColoring[g,l]は，事実上，FindVertexColoring[g,{1,2,…,l}]に等しい．

例題

すべて開くすべて閉じる

例 (2)

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

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

グラフを可視化する：

スコープ (7)

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

有向グラフ：

重み付きグラフ：

多重グラフ：

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

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

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

アプリケーション (5)

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

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

CompleteGraph[n]の色のシーケンスを求める：

CycleGraph[n]：

日程を組む (1)

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

学生の履修している2つの科目が同じ時間に重ならないような試験日程を求める：

すべての試験の日程を組むために必要な最小のスロット数を求める：

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

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

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

地図彩色 (1)

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

最小数の色で地図に彩色する．隣接する国には異なる色を割り当てなければならない：

特性と関係 (6)

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

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

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

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

個の頂点があるグラフ，その彩色数，独立数は ≤ を満足する：

平面グラフの面彩色はそのグラフの双対の頂点彩色である：

トップへ

その他のラーニングリソース

テクニカルサポート

大人用の教育プログラム

若者のための教育プログラム

イベント

Wolframイニシアチブ

教育リソース

趣味とプロジェクト

Wolframソリューション

教育のためのWolframソリューション

使い始める

Grow Your Skills

Wolframと繋がる

読む