Ontwerp een algoritme dat nagaat of de toppen van een gegeven graaf met slechts twee kleuren kunnen worden gekleurd, zodanig dat twee adjacente toppen een verschillende kleur hebben. Denk ook na over de tijdscomplexiteit van je algoritme.

Opgave

Implementeer een Python-functie tweekleuren(graph:UndirectedGraph, kleur1:str, kleur2:str) die een ongerichte graaf en twee kleuren meekrijgt. De functie moet een dict teruggeven die elke top op 1 van de 2 gegeven kleuren afbeeldt. Indien de graaf niet met twee kleuren kan worden gekleurd, moet de functie None teruggeven.

We maken bij deze oefening gebruik van een eenvoudige grafenbibliotheek graphlib. De API van de deze bibliotheek vind je hier¹. Neem eerst en vooral eens de API en de bibliotheek zelf door en stel eventueel vragen hierover voor je begint te programmeren.

Belangrijke opmerking: om met de grafenbibliotheek te kunnen werken in PyCharm moet je het bestand graph_library.py² toevoegen aan dezelfde directory als waarin je ze gebruikt. Dan kun je ze gebruiken door ze te importeren met

from graph_library import *

Dit import statement mag wel niet mee ingediend worden op dodona.

Voorbeeld

>>> graph01 = undirected_graph_from_dict({1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [1, 3]})
>>> tweekleuren(graph01, 'paars', 'rood')
{Node(1): 'paars', Node(4): 'rood', Node(2): 'rood', Node(3): 'paars'}
>>> graph02 = undirected_graph_from_dict({1: [2, 3], 2: [1, 3], 3: [1, 2]})
>>> tweekleuren(graph02, 'groen', 'paars')
None