Gegeven een graaf \(G=(V,E)\), een toppenbedekking (of vertex cover) is een deelverzameling \(S \subset V\) van de toppen van \(G\), zodanig dat voor elke boog \((u,v) \in E\) ofwel \(u\) ofwel \(v\) ofwel allebei tot \(S\) behoren.

Gegeven een geheel getal \(k\) en een graaf \(G\), gevraagd is te bepalen of er een toppenbedekking van \(G\) met hoogstens \(k\) toppen bestaat.

Implementeer een recursief algoritme dat dit probleem exact oplost voor kleine waarden van \(k\) (zie referentie).

Opgave

Schrijf een Python-functie kVertexCover(graph: dict, k: int). Deze functie neemt een graaf en een getal \(k\) als zijn argumenten. De functie geeft een toppenbedekking van grootte \(k\) terug indien deze bestaat, anders wordt None teruggegeven.

Voorbeelden

>>> kVertexCover({'A': ['B', 'E'], 'B': ['A', 'C', 'D','E', 'F'], 'C': ['B'], 'D':['B'], 'E':['A', 'B'], 'F': ['B'] }, 2)
{'A', 'B'}
>>> kVertexCover({'A': ['B', 'E'], 'B': ['A', 'C', 'D','E', 'F'], 'C': ['B'], 'D':['B'], 'E':['A', 'B'], 'F': ['B'] }, 3)
{'A', 'B'}
>>> kVertexCover({'A': ['B', 'E'], 'B': ['A', 'C', 'D','E', 'F'], 'C': ['B'], 'D':['B'], 'E':['A', 'B'], 'F': ['B'] }, 1)
>>> kVertexCover({'A': ['B', 'E'], 'B': ['A', 'E', 'C'], 'C': ['B', 'D', 'F'], 'D': ['C'], 'E': ['A', 'B', 'F'], 'F':['C', 'E']}, 3)
{'E', 'C', 'A'}
>>> kVertexCover({'A': ['B', 'E'], 'B': ['A', 'E', 'C'], 'C': ['B', 'D', 'F'], 'D': ['C'], 'E': ['A', 'B', 'F'], 'F':['C', 'E']}, 2)

Referentie