Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm ra kích thước tối thiểu của clique lớn nhất trong biểu đồ (Python)

Giả sử chúng ta được cung cấp một đồ thị và được yêu cầu tìm ra kích thước nhỏ nhất của clique lớn nhất trong đồ thị. Một nhóm của đồ thị là một tập hợp con của đồ thị trong đó mọi cặp đỉnh đều kề nhau, tức là tồn tại một cạnh giữa mọi cặp đỉnh. Không thể tìm được nhóm lớn nhất trong một biểu đồ trong thời gian đa thức, vì vậy với số lượng nút và số cạnh của một biểu đồ nhỏ, chúng ta sẽ phải tìm ra nhóm lớn nhất trong đó.

Vì vậy, nếu đầu vào giống như các nút =4, các cạnh =4; thì đầu ra sẽ là 2.

Chương trình tìm ra kích thước tối thiểu của clique lớn nhất trong biểu đồ (Python)

Trong biểu đồ trên, kích thước tối đa của một nhóm là 2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Xác định một hàm trợ giúp (). Điều này sẽ lấy x, y
    • ga:=x mod y
    • gb:=y - ga
    • sa:=thương số của giá trị (x / y) + 1
    • sb:=thương số của giá trị (x / y)
    • return ga * gb * sa * sb + ga * (ga - 1) * sa * sa / 2 + gb * (gb - 1) * sb * sb / 2
  • i:=1
  • j:=node + 1
  • while i + 1
  • p:=i + giá trị sàn của ((j - i) / 2)
  • k:=helper (các nút, p)
  • nếu k
  • i:=p
  • nếu không,
    • j:=p
  • trả lại j
  • Ví dụ

    Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

    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))
    

    Đầu vào

    4,4

    Đầu ra

    2