クラスターグラフ

数学の一分野であるグラフ理論において、クラスターグラフは完全グラフの互いに素な和集合から形成されるグラフである。同様に、グラフがクラスターグラフである場合、それは3頂点誘導パスを持たない場合に限る。このため、クラスターグラフは $P$ $3$ フリーグラフとも呼ばれる。これらは、完全多部グラフ^[1]と2葉冪^[2]の補グラフである。クラスターグラフは推移的に閉じており、推移的に閉じた無向グラフはすべてクラスターグラフである。^[3]

クラスターグラフは、隣接性が同値関係であるグラフであり、その接続されたコンポーネントはこの関係の同値クラスです。

計算上の問題

グラフのサブカラーリングとは、グラフの頂点を誘導クラスターグラフに分割することです。したがって、クラスターグラフはサブカラー数1のグラフとまったく同じです。^[6]

グラフをクラスターグラフに変換するために、グラフに追加または削除するエッジの小さなセットを見つける計算問題は、クラスター編集と呼ばれます。これはNP完全^[7]ですが、固定パラメータで処理可能です。^[8]

エッジコスト（正と負）を持つ完全グラフが与えられた場合、クリーク分割問題は、クラスターグラフのエッジのコストの合計が最小となるクラスターグラフであるサブグラフを求めます。^{[9]この問題は}相関クラスタリング問題と密接に関連しています。

参考文献

^ ab クラスターグラフ、グラフクラスとその包含に関する情報システム、2016 年 6 月 26 日にアクセス。
^ 西村, N.; Ragde, P.; Thilikos, DM (2002)、「葉ラベル付き木のグラフべき乗について」、Journal of Algorithms、42 : 69–108、doi :10.1006/jagm.2001.1195。
^ McColl, WF; Noshita, K. (1986)、「グラフの推移閉包における辺の数について」、離散応用数学、15 (1): 67–73、doi : 10.1016/0166-218X(86)90020-X、MR 0856101
^ ガーディナー、A. (1976)、「同種グラフ」、組合せ理論ジャーナル、シリーズB、20 (1): 94–102、doi : 10.1016/0095-8956(76)90072-1、MR 0419293。
^ Lachlan, AH; Woodrow, Robert E. (1980)、「Countable ultrahomogeneous undirected graphs」、アメリカ数学会誌、262 (1): 51–94、doi : 10.2307/1999974、MR 0583847。
^ Albertson, MO; Jamison, RE; Hedetniemi, ST; Locke, SC (1989)、「グラフのサブクロマティック数」、Discrete Mathematics、74 (1–2): 33–49、doi : 10.1016/0012-365X(89)90196-9。
^ シャミール、ロン; シャラン、ロデッド; ツル、デケル (2004)、「クラスターグラフ修正問題」、離散応用数学、144 (1–2): 173–182、doi : 10.1016/j.dam.2004.01.007、MR 2095392。
^ Böcker, Sebastian; Baumbach, Jan (2013)、「クラスター編集」、計算の性質、Lecture Notes in Comput. Sci.、vol. 7921、Springer、Heidelberg、pp. 33–44、doi :10.1007/978-3-642-39053-1_5、MR 3102002。
^ Grötschel, Martin; Wakabayashi, Yoshiko (1989)、「クラスタリング問題のための切断面アルゴリズム」、Mathematical Programming、vol. 45、Springer、pp. 59–96、doi :10.1007/BF01589097。

[gc-1] クラスターグラフ、グラフクラスとその包含に関する情報システム、2016 年 6 月 26 日にアクセス。

[2] 西村, N.; Ragde, P.; Thilikos, DM (2002)、「葉ラベル付き木のグラフべき乗について」、Journal of Algorithms、42 : 69–108、doi :10.1006/jagm.2001.1195。

[3] McColl, WF; Noshita, K. (1986)、「グラフの推移閉包における辺の数について」、離散応用数学、15 (1): 67–73、doi : 10.1016/0166-218X(86)90020-X、MR 0856101

[4] ガーディナー、A. (1976)、「同種グラフ」、組合せ理論ジャーナル、シリーズB、20 (1): 94–102、doi : 10.1016/0095-8956(76)90072-1、MR 0419293。

[5] Lachlan, AH; Woodrow, Robert E. (1980)、「Countable ultrahomogeneous undirected graphs」、アメリカ数学会誌、262 (1): 51–94、doi : 10.2307/1999974、MR 0583847。

[6] Albertson, MO; Jamison, RE; Hedetniemi, ST; Locke, SC (1989)、「グラフのサブクロマティック数」、Discrete Mathematics、74 (1–2): 33–49、doi : 10.1016/0012-365X(89)90196-9。

[7] シャミール、ロン; シャラン、ロデッド; ツル、デケル (2004)、「クラスターグラフ修正問題」、離散応用数学、144 (1–2): 173–182、doi : 10.1016/j.dam.2004.01.007、MR 2095392。

[8] Böcker, Sebastian; Baumbach, Jan (2013)、「クラスター編集」、計算の性質、Lecture Notes in Comput. Sci.、vol. 7921、Springer、Heidelberg、pp. 33–44、doi :10.1007/978-3-642-39053-1_5、MR 3102002。

[9] Grötschel, Martin; Wakabayashi, Yoshiko (1989)、「クラスタリング問題のための切断面アルゴリズム」、Mathematical Programming、vol. 45、Springer、pp. 59–96、doi :10.1007/BF01589097。

関連するグラフクラス

計算上の問題

参考文献