色多項式とは？
いろたこうしき
色多項式とは、グラフ理論において隣り合う頂点が同じ色にならないようにグラフを色分けする方法の数を、色の数を変数とする多項式で表したものです。
色多項式（いろたこうしき、chromatic polynomial）は、グラフ理論の概念で、与えられたグラフGをk色で「適切に彩色」できる方法の数をkの多項式として表したものです。「適切な彩色」とは、辺（edge）でつながっている頂点（vertex）どうしは必ず異なる色で塗るというルールを守った塗り方を指します。
例えば、3つの頂点がすべて互いに辺でつながった三角形（完全グラフK₃）の場合、k色で塗り分ける方法の数はk×(k-1)×(k-2)という多項式で表されます。k=3を代入すると6通りとなり、これは3色ですべての頂点を異なる色で塗る順列の数と一致します。
色多項式の性質として次のことが知られています。
- 多項式の最小次数はグラフの頂点数に等しい。
- k=0のとき、色多項式は必ず0になる（色がなければ塗れない）。
- 彩色数（chromatic number）は、色多項式が正の値を取る最小の正整数kとして読み取れる。
この概念は地図の塗り分け（四色定理）の研究から発展し、組合せ論・代数・計算機科学で広く用いられます。スケジューリングや無線通信の周波数割り当てなど、実用的な問題に応用されることもあります。
使い方・例文
「地図上で隣り合う国を異なる色で塗り分けるとき、何種類の配色が可能かを求める問題に色多項式が活用されます。」グラフ理論や組合せ数学の授業・入試問題で登場します。
この用語をシェア
最終更新: