多部グラフ

数学の一部であるグラフ理論において、 k部グラフとは、頂点がk 個の異なる独立集合に分割される(または分割できる)グラフのことです。同様に、 k色で色付けできるグラフで、辺の 2 つの端点が同じ色になることはありません。k = 2 の場合、これらは2 部グラフであり、k = 3の場合、これらは3 部グラフと呼ばれます。

二部グラフは多項式時間で認識できるが、 k > 2 の任意のグラフに対して、色付けされていないグラフが与えられた場合、それがk部グラフであるかどうかをテストするのはNP 完全である。^[1] しかし、グラフ理論の応用によっては、k部グラフが計算の入力として与えられ、その色付けが既に決定されていることがある。これは、グラフ内の頂点の集合が異なる種類のオブジェクトを表す場合に発生する可能性がある。たとえば、フォークソノミーは、グラフ内の 3 つの頂点の集合がシステムのユーザー、ユーザーがタグ付けしているリソース、ユーザーがリソースに適用したタグを表す三部グラフによって数学的にモデル化されている。^[2]

完全k部グラフは、異なる独立集合のすべての頂点のペアの間に辺が存在するk部グラフです。これらのグラフは、大文字Kに、分割内の各集合のサイズのシーケンスを下付き文字として付けた表記法で記述されます。たとえば、K _{2,2,2 は}、正八面体の完全な三部グラフであり、それぞれが 2 つの反対の頂点からなる 3 つの独立集合に分割できます。完全多部グラフは、あるkに対して完全なk部グラフであるグラフです。^[3] トゥラングラフは、2 つの独立集合のサイズが最大で 1 つの頂点だけ異なる完全多部グラフの特殊なケースです。完全k部グラフ、完全多部グラフ、およびそれらの補グラフであるクラスターグラフは、コグラフの特殊なケースであり、分割が入力の一部として提供されなくても多項式時間で認識できます。