グラフ彩色計算機 — 隣接ノードが一致しないようにグラフを彩色
このグラフ彩色計算機は、貪欲なウェルシュ・パウエルアルゴリズム（次数の降順にノードを並べる）を使用して、直接接続された2つの頂点が同じ色を共有しないように、グラフのすべての頂点に色を割り当てます。グラフはシンプルなテキストの辺リスト（例：A-B, A-C, B-C）として入力します。
クイック回答
グラフを辺リストとして入力すると、貪欲なウェルシュ・パウエルアルゴリズムを使用して、接続された2つのノードが色を共有しないように各頂点が即座に彩色されます。
辺をNodeA-NodeBの形式で入力してください（例：A-B, A-C, B-C）。
グラフ彩色計算機 — オンラインでウェルシュ・パウエルアルゴリズムの使い方
- 1
グラフをカンマ区切りの辺リストとして入力します（例：A-B, A-C, B-C）。
- 2
「計算」をクリックして、ウェルシュ・パウエルアルゴリズムを使用してすべての頂点を彩色します。
- 3
各ノードに割り当てられた色と使用された色の総数を確認します。
なぜグラフ彩色計算機 — オンラインでウェルシュ・パウエルアルゴリズムを使うのか？
グラフ彩色は、辺が同じ色の2つの頂点を結ばないように頂点にラベル（「色」）を割り当てます — これは、スケジューリング問題（互いに矛盾する2つの試験が同じ時間枠を共有しない）や地図の彩色（隣接する2つの領域が色を共有しない）の背後にある古典的な抽象化です。真の最小色数（彩色数）を見つけることは一般にNP困難ですが、ウェルシュ・パウエルヒューリスティック — 次数の降順に頂点を彩色し、常に利用可能な最小の色を選択する — は、多くの実用的なグラフに対して最適値の小さな範囲内であることが証明されている、良好で高速な彩色を生成します。これはまさにこの計算機が計算するものです。
よくある質問
関連ツール
最小全域木計算機 — クラスカルのアルゴリズムをオンラインで
クラスカルのアルゴリズムを使用して、重み付きグラフの最小全域木を求めます。シンプルな辺リスト入力とUnion-Findによるサイクル検出を備えた無料計算機。
グラフ次数列検証機 — オンラインでエルデシュ・ガライの定理
エルデシュ・ガライの定理を使用して、数値のシーケンスが有効な（グラフ的な）次数列であるかどうかを確認します。段階的な検証を備えた無料計算機。
隣接行列計算機 — オンラインでグラフ行列を構築
シンプルな辺リスト入力からグラフの隣接行列を構築して表示し、その次数列も示します。重み付きまたは重みなしに対応した無料計算機。
安定結婚問題ソルバー — Gale-Shapleyアルゴリズムをオンラインで
Gale-Shapleyアルゴリズムを使用して、選好リストから同サイズの2つのグループ間の安定マッチングを求めます。無料電卓、安定した結果を保証します。