|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ラフ ： [らふ] 1. (adj,n) rough 2. (adj,n) rough ・ 彩色 ： [さいしょく] 1. (n,vs) colouring 2. coloring 3. colouration 4. coloration 5. painting ・ 色 ： [しきさい, いろ] 【名詞】 1. (1) colour 2. color 3. (2) sensuality 4. lust
グラフ彩色（英: Graph coloring）とは、グラフの何らかの要素に、ある制約条件を満たすように色を割り当てることである。最も単純なものは、隣接する頂点同士が同じ色にならないように全頂点に彩色する問題である。これを頂点彩色という。同様に辺彩色は、隣接する辺同士が同じ色にならないように全辺を彩色する問題、面彩色は、平面グラフの辺で囲まれた各領域（面）を隣接する面同士が同じ色にならないように彩色する問題である。 == 概要 == 頂点彩色が出発点であり、他の彩色問題は頂点彩色に変換可能である。例えば、辺彩色問題は、そのグラフをライングラフに変換したときの頂点彩色と同じであり、面彩色は平面グラフの双対グラフの頂点彩色と同じである。しかし、頂点彩色以外の問題もそのままの形で研究されている。これは、見通しの良さのためでもあり、頂点彩色以外の形式で研究が進んでいるためでもある。 彩色という表現を使うようになったのは、地図を国ごとに彩色する問題が起源である。地図の彩色問題は、平面グラフの面彩色問題に他ならない。また平面グラフの双対性により、頂点彩色問題とも等価であり、あらゆるグラフの問題として一般化できる。数学やコンピュータでは、非負または正の小さい整数を「色」を表現する値として使うことが多い。一般に、任意の有限集合を「色集合」として使うことができる。彩色問題の性質は色数には依存するが、個々の色をどう表すかは関係しない。 グラフ彩色はグラフのラベル付けとは異なる。ラベル付けは数で表される「ラベル」を頂点や辺に割り当てるものである。グラフ彩色問題では、色（を表す数）は任意のマーカーであり、隣接性や結合性に関わる状態を表す。グラフのラベル付け問題では、ラベル（を表す数）は計算可能な値であり、ラベル付けの際の定義で示される何らかの数値的条件を満たす必要がある。 グラフ彩色問題は理論的にも意味があるが、実用的な応用も多い。古典的問題以外にも、色の割り当て方や色自体に異なる制約を加えた問題もある。広く知られているパズルである数独もグラフ彩色問題の変形である。グラフ彩色は研究が盛んな分野のひとつである。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「グラフ彩色」の詳細全文を読む スポンサード リンク
|