グラフの色付け
グラフの色付けは、グラフの頂点に色を割り当てるプロセスとして説明できます。この場合、隣接する 2 つの頂点を埋めるために同じ色を使用しないでください。グラフのカラーリングを頂点カラーリングと呼ぶこともできます。グラフの色付けでは、端の頂点が同じ色で色付けされているエッジがグラフに含まれないように注意する必要があります。このタイプのグラフは、適切に色付けされたグラフとして知られています。
グラフの色付け例
このグラフでは、適切に色分けされたグラフが表示されており、次のように説明されています。
上のグラフにはいくつかの点が含まれており、それらについては次のように説明されます。
- 同じ色を使用して、隣接する 2 つの頂点の色を指定することはできません。
- したがって、これを適切に色分けされたグラフと呼ぶことができます。
グラフの色分けの応用
グラフの色付けにはさまざまな用途があります。その重要な用途のいくつかを以下に説明します。
- 割り当て
- 地図のぬりえ
- タスクのスケジュール設定
- 数独
- タイムテーブルを準備する
- 紛争解決
色彩番号
彩色数は、グラフを適切に色付けするために必要な最小色の数として説明できます。言い換えれば、彩色数は、グラフの隣接する 2 つの頂点に同じ色が割り当てられないようにグラフを着色するために必要な色の最小数として説明できます。
彩色番号の例:
彩色数を理解するために、次のように説明されるグラフを考えます。
上のグラフにはいくつかの点が含まれており、それらについては次のように説明されます。
- 隣接する 2 つの頂点の色付けに同じ色は使用されません。
- このグラフの最小色の数は 3 です。これは、頂点を適切に色付けするために必要です。
- したがって、このグラフでは、彩色数 = 3 となります。
- このグラフに適切に色を付けたい場合、この場合、少なくとも 3 色が必要です。
グラフの彩色番号の種類:
グラフの色数にはさまざまな種類があり、次のように説明されます。
文字列整数
サイクルグラフ:
グラフに長さ「n」のサイクルを形成する「n」個のエッジと「n」個の頂点 (n >= 3) が含まれる場合、そのグラフはサイクル グラフと呼ばれます。サイクル グラフ内のすべての頂点の次数は 2 つまたは 3 つだけです。
彩色番号:
- 周期グラフの頂点の数が偶数の場合、そのグラフの彩度数は 2 になります。
- サイクル グラフの頂点の数が奇数の場合、そのグラフの彩色番号は 3 になります。
サイクルグラフの例:
サイクルグラフにはさまざまな例があります。それらのいくつかは次のように説明されています。
例 1: 次のグラフでは、彩色番号を決定する必要があります。
解決： 上記のサイクル グラフでは、3 つの頂点に 3 つの異なる色があり、隣接する頂点はどれも同じ色で着色されていません。このグラフでは、頂点の数が奇数です。それで
彩色番号 = 3
例 2: 次のグラフでは、彩色番号を決定する必要があります。
解決： 上記のサイクル グラフでは、4 つの頂点に 2 つの色があり、隣接する頂点はどれも同じ色で着色されていません。このグラフでは頂点の数は偶数です。それで
彩色番号 = 2
例 3: 次のグラフでは、彩色番号を決定する必要があります。
解決： 上のグラフでは、5 つの頂点に対して 4 つの異なる色があり、隣接する 2 つの頂点は同じ色 (青) で着色されています。したがって、このグラフは周期グラフではなく、彩色番号も含まれていません。
例 4: 次のグラフでは、彩色番号を決定する必要があります。
解決： 上のグラフでは、6 つの頂点に 2 つの異なる色があり、隣接する頂点には同じ色はありません。このグラフでは頂点の数は偶数です。それで
彩色番号 = 2
プランナーグラフ
グラフが平面上に描かれる場合、プランナー グラフと呼ばれます。プランナー グラフのエッジは互いに交差してはなりません。
彩色番号:
- プランナー グラフでは、半値数値は 4 以下である必要があります。
- プランナー グラフは、例 3 を除く上記のすべてのサイクル グラフによっても表示できます。
平面グラフの例:
平面グラフにはさまざまな例があります。それらのいくつかは次のように説明されています。
例 1: 次のグラフでは、彩色番号を決定する必要があります。
解決： 上のグラフでは、3 つの頂点に 3 つの異なる色があり、このグラフのどの辺も互いに交差していません。それで
ポシネニ・ラム
彩色番号 = 3
ここで、彩色数は４未満であるため、このグラフは平面グラフとなる。
例 2: 次のグラフでは、彩色番号を決定する必要があります。
解決： 上のグラフでは、4 つの頂点に 2 つの異なる色があり、このグラフのどの辺も互いに交差していません。それで
彩色番号 = 2
ここで、彩色数は４未満であるため、このグラフは平面グラフとなる。
例 3: 次のグラフでは、彩色番号を決定する必要があります。
解決： 上のグラフでは、5 つの頂点に 5 つの異なる色があり、このグラフのエッジはいずれも交差しません。それで
彩色番号 = 5
ここで、彩色数は 4 より大きいため、このグラフは平面グラフではありません。
例 4: 次のグラフでは、彩色番号を決定する必要があります。
解決： 上のグラフでは、6 つの頂点に 2 つの異なる色があり、このグラフのどの辺も交差していません。それで
彩色番号 = 2
ここで、彩色数は４未満であるため、このグラフは平面グラフとなる。
完全なグラフ
2 つの異なる頂点を結合するために 1 つのエッジのみが使用される場合、グラフは完全なグラフとして認識されます。完全なグラフ内のすべての頂点は、他のすべての頂点と接続されています。このグラフでは、すべての頂点が異なる色で色付けされます。つまり、完全なグラフでは 2 つの頂点に同じ色が含まれていません。
色彩番号
完全なグラフでは、彩色番号はそのグラフの頂点の数に等しくなります。
完全なグラフの例:
完全なグラフのさまざまな例があります。それらのいくつかは次のように説明されています。
例 1: 次のグラフでは、彩色番号を決定する必要があります。
解決： 4 つの異なる頂点には 4 つの異なる色があり、上のグラフでは同じ色はありません。定義によれば、彩色数は頂点の数です。それで、
彩色番号 = 4
例 2: 次のグラフでは、彩色番号を決定する必要があります。
解決： 5 つの異なる頂点には 5 つの異なる色があり、上のグラフでは同じ色はありません。定義によれば、彩色数は頂点の数です。それで、
彩色番号 = 5
例 3: 次のグラフでは、彩色番号を決定する必要があります。
解決： 4 つの異なる頂点に 3 つの異なる色があり、上のグラフでは 2 つの頂点で 1 つの色が繰り返されます。したがって、このグラフは完全なグラフではなく、彩色番号が含まれていません。
二部グラフ
グラフに 2 つの頂点セット A と B が含まれている場合、そのグラフは 2 部グラフとして知られます。A の頂点は B の頂点とのみ結合できます。つまり、エッジは頂点をセットに結合できません。
色彩番号
文字列 ti int
2 部グラフでは、彩色番号は常に 2 に等しくなります。
二部グラフの例:
二部グラフにはさまざまな例があります。それらのいくつかは次のように説明されています。
例 1: 次のグラフでは、彩色番号を決定する必要があります。
解決： 上のグラフには 2 つの異なる頂点セットがあります。したがって、すべての 2 部グラフの色彩数は常に 2 になります。
彩色番号 = 2
木：
接続されたグラフは、そのグラフ内に回路が存在しない場合、ツリーと呼ばれます。ツリーでは、ツリー内の頂点の数に関係なく、彩色番号は 2 に等しくなります。すべての 2 部グラフもツリーです。
色彩番号
どの木でも彩色番号は 2 に等しくなります。
ツリーの例:
樹木にはさまざまな例があります。それらのいくつかは次のように説明されています。
例 1: 次のツリーでは、彩色番号を決定する必要があります。
解決： 4 つの頂点には 2 つの異なる色があります。任意の数の頂点を持つツリーには、上記のツリーの 2 として色彩番号が含まれている必要があります。それで、
彩色番号 = 2
例 2: 次のツリーでは、彩色番号を決定する必要があります。
解決： 5 つの頂点に対して 2 つの異なる色があります。任意の数の頂点を持つツリーには、上記のツリーの 2 として色彩番号が含まれている必要があります。それで、
彩色番号 = 2
色彩数の実例
Marry が Xyz Company のマネージャーであると仮定します。会社は何人かの新入社員を雇用するので、彼女はそれらの新入社員のための研修スケジュールを取得する必要があります。彼女は 3 つの会議をスケジュールする必要があり、少ない時間枠をできるだけ会議に使おうとしています。 2 つの異なる会議に出席する必要がある従業員がいる場合、マネージャーはそれらの会議に異なるタイム スケジュールを使用する必要があります。この会議を視覚的に表現したいとします。
視覚的な表現では、マリーはドットを使用して会議を示します。 2 つの会議があり、両方の会議に参加する必要がある従業員がいる場合、両方の会議はエッジの助けを借りて接続されます。さまざまなタイムスロットは色を使用して表されます。したがって、マネージャーは、エッジを共有する 2 つのドットに同じ色が含まれないように、これらの色でドットを塗りつぶします。 (つまり、2 つの会議に出席する必要がある従業員は、同じ時間枠にあってはなりません)。これを視覚的に表現すると次のようになります。
