グラフ内の最大のクリークの最小サイズを見つけるプログラム（Python）

グラフが与えられ、グラフ内の最大のクリークの最小サイズを見つけるように求められたとします。グラフのクリークは、頂点のすべてのペアが隣接している、つまり頂点のすべてのペアの間にエッジが存在するグラフのサブセットです。グラフ内で最大のクリークを見つけることは多項式時間では不可能であるため、小さなグラフのノードとエッジの数を考えると、グラフ内の最大のクリークを見つける必要があります。

したがって、入力がノード=4、エッジ=4のような場合。その場合、出力は2になります。

上のグラフでは、クリークの最大サイズは2です。

これを解決するには、次の手順に従います-

• 関数helper（）を定義します。これにはx、y
  がかかります
  • ga：=x mod y
  • gb：=y --ga
  • sa：=（x / y）+1の値の商
  • sb：=（x / y）の値の商
  • return ga * gb * sa * sb + ga *（ga-1）* sa * sa / 2 + gb *（gb-1）* sb * sb / 2
• i：=1
• j：=ノード+1
• i + 1
• p：=i +フロア値（（j --i）/ 2）
• k：=helper（nodes、p）
• k <エッジの場合、
  • i：=p
• それ以外の場合、
  • j：=p

例

理解を深めるために、次の実装を見てみましょう-

import math
def helper(x, y):
    ga = x % y
    gb = y - ga
    sa = x // y + 1
    sb = x // y
    return ga * gb * sa * sb + ga * (ga - 1) * sa * sa // 2 + gb * (gb - 1) * sb * sb // 2

def solve(nodes, edges):
    i = 1
    j = nodes + 1
    while i + 1 < j:
        p = i + (j - i) // 2
        k = helper(nodes, p)
        if k < edges:
            i = p
        else:
            j = p
    return j

print(solve(4, 4))

入力

4,4

出力

2