導入
グラフ理論では、4 つ以上の頂点からなるサイクルのそれぞれに弦、つまりサイクルの隣接しない 2 つの頂点を接続するエッジがある場合、そのグラフは弦状であると言われます。同等の定義は、文字列のないサイクルには最大 3 つの頂点が含まれるということです。 Chordal グラフは、三角グラフとも呼ばれ、完全グラフのサブセットです。
完璧な除去と効率的な認識
グラフの完全消去順序とは、任意の頂点vについて、 vによって形成される集合とその近傍がクリークを形成した後に見つかるようなグラフの頂点の順序です。グラフが完全な消去順序を持っている場合に限り、グラフは健全です。 (フルカーソンとグロス、1965)。
Rose et al (1976; Habib et al 2000 も参照) は、幅優先辞書検索と呼ばれるアルゴリズムを使用して、弦グラフの完全な消去順序を効率的に見つけることができることを示しています。このアルゴリズムは、グラフ頂点の分割を一連のセットとして維持します。最初、このシーケンスはすべての頂点を含む 1 つのセットです。次にアルゴリズムは、まだ選択されていない頂点を含むシーケンス内の最も若いセットから頂点vを繰り返し選択し、シーケンスの各セットS を2 つのサブセットに分離します。1 つはS内のvの近傍を含み、もう 1 つは非選択の頂点を含みます。隣接する頂点。この分離がすべての頂点に対して行われると、シーケンスは頂点を 1 つだけ含むセットで構成されます。これらの頂点は、完全消去順序の逆の順序で見つかります。
幅優先辞書編集検索と順序付けが完全消去順序かどうかのテストは線形時間で実行できるため、グラフが線形時間でコーダルであるかどうかを知ることができます。
弦グラフのすべての完全消去順序のセットは、アンチマトロイドの基本単語としてモデル化できます。チャンドランら。 (2003) は、与えられた弦グラフのすべての完全消去順序を効率的にリストするアルゴリズムでアントリマトロイドとのこの関係を使用しました。
サブツリー交差グラフ
Gavril (1974) によって作成されたコーダル グラフの別の特徴付けでは、ツリーとそのサブツリーが使用されています。
ツリーAのサブツリーの集合から、サブツリーごとに 1 つの頂点を持つ交差グラフであるサブツリー グラフを定義できます。エッジは、ツリーA内に少なくとも 1 つの共通ノードを持つサブツリーを接続します。 Gavril が示したように、サブツリー グラフはまさにコード グラフです。この表現はグラフのツリー分解を形成します。グラフの高さは、グラフ内の最大クリークのサイズから 1 を引いたものになります。このようにして、任意のグラフGのツリー分解は、弦グラフのサブグラフとしてのGの表現として見ることができます。
最大クリークとグラフの色分け
完全消去スケジューリングの応用例は、多項式時間における弦グラフの最大クリークの検索です。同様の問題は、どのグラフでも NP 完全です。一般に、コーダル グラフの最大クリークの数は直線的に増加しますが、非コーダル グラフではこの増加は指数関数的になる可能性があります。弦グラフのすべての最大クリークをリストするには、単に完全消去順序を見つけ、完全消去順序でvの後に来るvの近傍を持つ各頂点vに対してクリークを作成し、このようにして形成された各クリークについてテストします。最大。
最大の最大クリークは最大クリークであり、弦グラフは完全なグラフであるため、クリークのサイズは弦グラフの色彩数になります。コーダル グラフは完全にスケジュール可能なグラフであるため、最適なカラーリングは、完全な消去順序の逆の順序で頂点に貪欲なカラーリングアルゴリズムを適用することによって取得できます。 ()。