続: 最大クリーク問題

なんかいろいろやってこんな形に落ち着いた。


簡単にいうとまず適当にソートして、有向グラフに変換してDPする。
dp[j][c]はj以下の頂点を使用したjを含むサイズcのクリークの文字列表現の配列。
後続の頂点iからはこのクリークの頂点にすべて辺があれば、サイズc+1のクリークなのでdp[i][c+1]に追加する。
このクリークの頂点にすべて辺があればの部分は、rubyなので配列を&した、他の言語だとbitsetみたいなライブラリで行うほうがよいと思う。

belongs_max_cliqueは前回のソースを引き継いでいるので現在は適当ではないかもしれないけど、ある頂点vに隣接する誘導グラフから、最大クリークサイズをだす場合はbelongs_max_clique(G[v]) + 1とすればよいようになっている。

#!/usr/bin/env ruby

V, m = gets.split.map(&:to_i) # read Graph Infomation
G = {} 

# Initialize Graph
V.times {|v| G[v] = []}
m.times do 
  from, to = gets.split.map(&:to_i).sort
  G[from] << to
  G[to] << from
end


def belongs_max_clique(node = V.times.to_a, limit =  V)
  subgraph = {}
  node.sort!
  node.each_index{|i| subgraph[i] = [] }
  node.each_with_index do |u, i|
    i.times do |j|
      w = node[j]
      subgraph[i] << j if G[u].include?(w)
    end
  end
  
  dp = Array.new(node.size + 1){ Array.new(limit + 1){ [] } }
  node.each_index{|i| dp[i][1] << i.to_s }
  max_clique_size = (1 ... limit).find do |c|
    found_clique = false
    node.each_index do |i|
      subgraph[i].each do |j|
        dp[j][c].each do |clq|
          clique = clq.split.map(&:to_i)
          shared = clique & subgraph[i]
          if shared == clique
            clique << i
            dp[i][c + 1] << clique.join(' ')
            dp[node.size][c + 1] << clique.join(' ')
            found_clique = true
          end
        end
      end
    end
    !found_clique
  end
  max_clique_size || limit
end

puts belongs_max_clique


前回指摘をもらったグラフだとDPした結果は以下のようになる

[[], ["0"], [], [], [], [], [], [], []], 
[[], ["1"], ["0 1"], [], [], [], [], [], []], 
[[], ["2"], ["0 2", "1 2"], ["0 1 2"], [], [], [], [], []], 
[[], ["3"], ["0 3", "1 3", "2 3"], ["0 1 3", "0 2 3", "1 2 3"], ["0 1 2 3"], [], [], [], []], 
[[], ["4"], ["0 4"], [], [], [], [], [], []], 
[[], ["5"], ["0 5", "4 5"], ["0 4 5"], [], [], [], [], []], 
[[], ["6"], ["0 6", "5 6"], ["0 5 6"], [], [], [], [], []], 
[[], ["7"], ["0 7", "4 7", "6 7"], ["0 4 7", "0 6 7"], [], [], [], [], []], 


入力はこんな感じ

8 14
0 1
0 2
0 3
1 2
1 3
2 3
0 4
0 5
0 6
0 7
4 7
4 5
5 6
6 7

dp[node.size][c]は別になくてもよいけど、サイズcのクリーク( c >= 2)の全列挙用につくっている。

こんな感じになる。

[],
["0 1", "0 2", "1 2", "0 3", "1 3", "2 3", "0 4", "0 5", "4 5", "0 6", "5 6", "0 7", "4 7", "6 7"],
["0 1 2", "0 1 3", "0 2 3", "1 2 3", "0 4 5", "0 5 6", "0 4 7", "0 6 7"], 
["0 1 2 3"]


追記: コメントに計算量のことを書いて質問をいただきました。現在のコードがc^2 * v * eかと言われれば、ご指摘の通りたぶん違うんじゃないかとおもってきました。ただ自分的にはc^2 * v * eにまでおそらく落とせると思っているのでそこまで計算量を落としたアルゴリズムを作りたいと思っています。

メモ: cのループをnodeのループの中に入れて、サイズcのクリークの全列挙をやめると計算量は落ちるな。でもやはりサイズcのクリーク数に依存しそうだから、サイズcのクリークの個数に対して、cかc^2になりそうかな。計算量は落ち着かないけど、これならできそう。

最大クリーク問題

まだうまく証明できていないかもしれないけど、これで解けてると思う解けていないです。

別の実装を考えたのでコードを消しました。

kousuke.hatenablog.com


belongs_max_cliqueではある頂点を含む極大クリークのサイズを返していて、それを全点に対して行いその最大のものを出力している。

belongs_max_cliqueは任意の1頂点(v)とそれに隣接する頂点集合をUとすると、誘導部分グラフG[U]に対し、その次数をまず計算する。 Uの次数の少ないものから、順に切断していくと最終的に他の全ての点と同じ次数になるので、その時残っているグラフがvを含む最大クリークとなる。 クリークのサイズは次数 + 1すればよい。

(証明)

  • 最大クリークはそのグラフの頂点のどれかを含んでいる(自明)
  • ある頂点を選んでその頂点を含む極大クリークがわかれば、それを全点でおこなうことで最大クリークがわかる。(問題ないとおもう)
  • G[U]はvとvに隣接する頂点集合からなる誘導部分グラフであるので、vを含むクリークはすべて含まれる。(多分、自明)
  • G[U]はvとvに隣接する頂点集合からなる誘導部分グラフであるので、vの次数は必ず他の頂点の次数以上である。(Uの頂点数がnならG[U]の頂点の次数はn-1より大きくなることはなく、vの次数はn-1)
  • G[U]が完全グラフ(Kn)のとき、その全ての頂点の次数はn-1となり、頂点数はnとなり、停止条件となる。(n-正則グラフの場合があり、判定できてない)
  • G[U]からvの次数未満の最小の次数をもつ頂点を1点切断した頂点集合をU'とするとG[U']も必ずvを含む極大クリークが含まれる。(問題あり)
  • U'をUとして5に戻っても矛盾はない。(問題ないとおもう)

以上より、このアルゴリズム停止条件をもち、有限時間内に停止する。 またその時、このグラフに含まれる極大クリークのうち、最大のサイズを示す。

計算量はちょっと自信がないけど、頂点数をv , 次数の平均をdとすると O(v * d^2) じゃないかとおもう。 次数の平均はE / VなのでO(E^2 / V)かな。

以下、コーナーケースとして指摘されそうな例

  • G[U]が2つの完全グラフ(Kn,Km)を含み、その節点がvのとき、vは次数n+m - 2をもち、vを除くKn,Kmに含まれる点はそれぞれn-1,m-1の次数をもつ。
    • n < mのとき、Knの点から順に切断され、最終的にKmだけ残りすべての頂点がm-1の次数をもつ。
    • n = mのときはvをのぞく全ての点がn-1の次数を持ち、そのうち1点を切断することで、n < mと同じ状況になる。
  • G[U]が2つの完全グラフ(Kn,Km)を含み、vを除くKn,Km上の点を結ぶ接続がある場合も、上記のケースでの切断する順序に変化があるだけで、同様に最大クリークを返す。
  • G[U]が2つの完全グラフ(Kn,Km)を含み、vを除くKn,Km上の点にすべて接続がある場合、それは完全グラフKn+m-1であり、同様に最大クリークを返す。

TODO: 課題

  • 全ての次数が同じだけど、片側に完全Kn,もう片側にn-1正則グラフがある場合

この状況を把握するのはおそらく無理、右側と左側にリンクがある場合もあるので、フローとかで優先順位を確定できない限り難しい。もしかすると現在の実装でも、それなりに正しいものを出すかもしれないけど、コーナーケースのデータは否定できない。

- 案1. V.each前にsortするかbelongs_max_clique内のsortでabsを使用しているが、これを変えて、全体の順序のなかで順序付けして、整合性が取れるようにする。もしくは現在の状況で整合性がとれていることを示す必要がある。

- 案2. 完全グラフかどうかはキーの数 = 次数 + 1かどうかで判定できるので、そうでない場合はスキップする。この場合も全体のなかで整合性が取れている必要がある。もしくは優先順位を変えて再度実施する。

とりあえず完全グラフかどうか頂点数と次数で判定して、正則グラフの場合は-1を返すようにしてみた。ただ全体の整合性がとれるのかというと違う。もちろん右側と左側の別の頂点でbelong_max_cliqueは呼ばれるけど、全ての頂点がn-正則グラフと隣接しているというような状況はある。

グラフ理論について、今のところわかったこと

任意のグラフをGとし、その彩色数を \chi(G) = kとあらわす。 1点uを加えG'とするとき、その接続数がk未満の場合には必ず \chi(G') = kが成立する。

証明
 \chi(G) = kであるGからk未満の点を選択するとき、uはかならずk色の中から彩色の色を選択できる。 よって上記が成りたつ。
(証明終わり)

任意のグラフをGとし、その彩色数を \chi(G) = kとあらわす。 1点uを加えG'とするとき、その頂点が全点に接続する場合には必ず \chi(G') = k+1が成立する。

証明
 \chi(G) = kであるGに頂点uを加え、全点に接続するならば、uは必ず全色に接続し、k+1色目が必要になる。
もし \chi(G') \le kであるなら、彩色数が彩色できる最小の色数という前提に反する。
また \chi(G') = k+1で十分であり、 \chi(G') \gt k+1にはならない。

(証明終わり)


上記より

  • 頂点数v, 彩色数kをあたえられたとき、接続数をk未満とする頂点を追加する操作を繰り返すことで、頂点数vで彩色数k以下を満たすグラフを作ることができる。
    • vがkに対し、十分大きい時、頂点数v,彩色数kのグラフを作成できる。
  • 無向グラフの頂点を適当に順序付けして、その任意の2頂点i,j (i < j)に辺があるとき、jからiに対し向きをつける。全ての頂点に対し、この出力辺をk本以内にできるとき、k+1彩色可能。ただし彩色数(Chromatic number)と一致するとは限らない。
  • 上記からn正則グラフはn+1彩色可能、ただし彩色数(Chromatic number)と一致するとは限らない。
    • ピーターセングラフがわかりやすい例

多分これは正則グラフではBrooksの定理と一致して、一般のグラフでは上限をよく押さえつけるものになるかな。
Brooks' theorem - Wikipedia

kousuke.hatenablog.com


完全2部グラフKi,jを彩色した色クラスをそれぞれ閉路にしたとき(i,j >= 2)

  • その彩色数は4(i,jが共に偶数),5(i,jが偶数、奇数),6(i,j共に奇数)になる。

偶閉路が2彩色、奇閉路が3彩色できることによる。



完全2部グラフKi,jを彩色した色クラスを完全グラフにしたとき

  • その彩色数はi+jになる。

Ki+jと同一なことによる。


奇閉路に一点加えて彩色数を4とするためには全点に接続しないといけない。



俺の中でP=NPの機運が高まっている。

彩色数判定へのアプローチ

最初は彩色数kのグラフは2部グラフマッチングか最大流にできるとおもっていたのですが、制限付きナップサック問題かなにかに帰着できそうな気がしています。
たしかに組み合わせ問題なのでナップサック問題になってもおかしくなさそうです。


現在、v,e,kのみの数値でのプロトタイプを作成しています、ピーターセングラフはちゃんと3とでますが、2部グラフKn,mが2で出ません。

ただしある程度法則性があってn = mのときnででますし、m = n+1のときmででます。m = n + 2のとき、(m + n) / 2ででていて、完全2部グラフは完全グラフ内に含まれる。というのが仮説としてでてきました。

3彩色問題はヒューリスティックな感じの判定プログラムはつくれそうな気がします。
ただ理論的裏付けがなく、それが判定式となるのかはまだまだ研究中です。

完全グラフのマイナー

完全グラフばかり考えていたのですが、マイナーを考えないと本質にたどりつけなさそうなので考えています。

Kn を彩色数を変えずにKmだけ分離していく(強連結を置換していく)には、完全2部グラフが必要になる。

(片方はmだけど、もう片方が、m+1かn-1か、それともm + n / 2みないなものなのかが不明)


みたいな感じです。

四色定理の証明

変更しました。

四色定理から求められる平面グラフの性質

交差のない平面グラフにおいて、任意の1面に対し、その面を構成する閉路の頂点を3彩色し、 且つ、グラフ全体を4彩色する塗り方がある
交差のない平面グラフGにより構成される面Fの内、任意の面fを構成する閉路をCfとする。 このCfを3彩色し、Gを4彩色する方法が必ず存在する。 Gに点uを加えて、G'を作るとき、uは必ずある面f内に配置される(グラフの外も面と考える)。 この時fを構成する閉路Cfが必ず4色必要とされる場合、uからCf上の4色の点に 辺を作成したG'は必ず5色必要となり、四色定理に反する。

四色定理の別証明


四色定理はすでに証明済みであるが、上記の性質を仮定し、帰納法をもちい証明する。
四色定理が成立するためには、下記を証明すればよい。

交差のない平面グラフは必ず4色で彩色可能 <=> 任意の閉路を3色以内で彩色し、全体では4色となる彩色組み合わせが存在する。

頂点数nで交差のない任意の平面グラフGについて、 任意の閉路を3色とし、全体では4色となる彩色組み合わせが存在する。と仮定する。
G = K3の場合、1点加えたG'は必ず各閉路は3色以内で彩色可能で、 全体としては4色で彩色できる。(4色を必ず必要とするのはK4)
またG = K4に1点加える場合も同様である。

頂点数nの任意の交差のない平面グラフGに頂点uを加えG'とする場合に、 uを追加する面をfとし、その閉路をCfとする。 仮定により、Cfは3色で彩色することが可能である。
面fに頂点uを追加し、uからCf内の点に接続する。 Cfが3点しかない場合、どのように接続しても、新しくできた閉路は3色以内で彩色できる。 またCf外の彩色の組み合わせにも影響しない。

Cfが4点以上で異なる3色に接続する場合、4色目が必要で4色の閉路ができるが、 4色目は接続した部分と交換可能であり、新しくできた閉路を3彩色とすることが可能である。
交換できる理由について説明する。
この接続する3色が4色目と交換できない場合(接続する3色の組合せが1種類しかなく、且つ4色目と交換不可能な場合)、

閉路上の3色を1,2,3、新しく追加した色を4とし、4は1,3と接続するとすると,1 - 2,3,4 / 2 - 1,3,4 / 3 - 4, 2, 1が固定的に必要になる。 上記条件はK4で可能であるが、K4では交換可能である。 閉路の背後に必ずK3,K4をつなぐK3_3が必要となる。
クラトフスキー(Kuratowski)の定理により、これは交差のない平面としては存在できない。

またCf以外の閉路を3彩色した場合にはこのCfの交換可能である点が別の色となり、 やはり4彩色可能な組み合わせがある。よって任意の閉路を3彩色し、全体を4彩色可能である。
よって交差のない平面グラフは4色で彩色可能である。

(証明終わり)

彩色問題(2)

いろいろ考えて、NP完全、NP困難とされているk-彩色、彩色数がO(|V| |E|)でできそうな気がしてきた。
無理、無理。