NP-হার্ডনেস মোকাবিলা — অ্যাপ্রক্সিমেশন ও হিউরিস্টিক

# ভার্টেক্স কভারের জন্য একটি সত্যিকারের গ্রিডি 2-অ্যাপ্রক্সিমেশন, ব্রুট-ফোর্স সত্যিকারের
# মিনিমামের বিপরীতে যাচাইসহ

import itertools

def greedy_vertex_cover(edges):
    remaining = set(frozenset(e) for e in edges)
    cover = set()
    while remaining:
        edge = next(iter(remaining))          # যেকোনো একটি আনকভার্ড এজ
        u, v = tuple(edge)
        cover.add(u)
        cover.add(v)                           # দুটো প্রান্তবিন্দুই কভারে যোগ
        remaining = {e for e in remaining if u not in e and v not in e}
    return cover

def brute_force_min_vertex_cover(vertices, edges):
    edge_sets = [frozenset(e) for e in edges]
    vertices = list(vertices)
    for size in range(len(vertices) + 1):      # ছোট সাইজ থেকে শুরু -- প্রথম সফল = মিনিমাম
        for subset in itertools.combinations(vertices, size):
            subset_set = set(subset)
            if all(e & subset_set for e in edge_sets):
                return subset_set
    return set(vertices)

# উদাহরণ ১: একটি ডিসজয়েন্ট ম্যাচিং -- গ্রিডির জন্য সবচেয়ে "টাইট" (worst-case) কেস
vertices1 = [1, 2, 3, 4, 5, 6]
edges1 = [(1, 2), (3, 4), (5, 6)]

greedy1 = greedy_vertex_cover(edges1)
optimal1 = brute_force_min_vertex_cover(vertices1, edges1)
print("গ্রাফ ১ (ডিসজয়েন্ট এজ):")
print("  গ্রিডি কভার  :", sorted(greedy1), "| সাইজ", len(greedy1))
print("  প্রকৃত মিনিমাম:", sorted(optimal1), "| সাইজ", len(optimal1))
print("  রেশিও:", len(greedy1) / len(optimal1), "(<=2 হওয়ার কথা)")
assert len(greedy1) <= 2 * len(optimal1)

# উদাহরণ ২: একটি ত্রিভুজ + একটি পেন্ডান্ট এজ
vertices2 = [1, 2, 3, 4]
edges2 = [(1, 2), (2, 3), (1, 3), (3, 4)]

greedy2 = greedy_vertex_cover(edges2)
optimal2 = brute_force_min_vertex_cover(vertices2, edges2)
print("\nগ্রাফ ২ (ত্রিভুজ + পেন্ডান্ট):")
print("  গ্রিডি কভার  :", sorted(greedy2), "| সাইজ", len(greedy2))
print("  প্রকৃত মিনিমাম:", sorted(optimal2), "| সাইজ", len(optimal2))
print("  রেশিও:", len(greedy2) / len(optimal2), "(<=2 হওয়ার কথা)")
assert len(greedy2) <= 2 * len(optimal2)

print("\n>> উভয় গ্রাফেই গ্রিডি অ্যাপ্রক্সিমেশন প্রকৃত মিনিমামের সর্বোচ্চ ২ গুণ -- গ্যারান্টি নিশ্চিত")