Jeg har tenkt at vi har et flytnettverk med kanter mellom du to noder i hver sin gruppe dersom de misliker hverandre. Jeg skjønner hvordan jeg finner maksimalflyt, men ikke hvordan dette forteller meg hvilke noder (om dette er mennesker) jeg kan eller ikke kan ta med meg i ostesmaksgruppen?

Basert på et Piazza-spørsmål fra 2015

Startegien i slike tilfeller er å prøve å være litt grundig og systematisk, og bruke det du har fått av informasjon.

Oppgitt i oppgaven (altså introen, og spesifikk info om 3b):

  1. Gitt en avdeling med folk og konflikter mellom dem, vil vi finne en størst mulig gruppe der ingen misliker hverandre.
  2. Grafen av personer og konflikter er bipartitt.
  3. I en bipartitt graf vil antall kanter i en maksimal matching være lik antall noder i et minimalt nodedekke (vertex cover).
  4. Komplementet til et nodedekke er en uavhengig mengde (independent set).

To noder er uavhengige om de ikke er naboer.

Et første trinn er å prøve å trekke ut essensen av problem-instansen og ønsket resultat – forenkle det ned til sekvenser, grafer, tall, etc., og fjerne irrelevante detaljer. (Dette er tolknings-trinnet fra problemguiden.) I stedet for folk og konflikter, tenker vi noder og kanter, og får et nytt første punkt:

  1. Gitt en graf, finn en størst mulig uavhengig mengde.

Sammen med punkt 2, betyr det altså at vi er ute etter en størst mulig uavhengig mengde i en bipartitt graf. Fra punkt 4 har vi at vi like gjerne kan finne et nodedekke, og fra punkt 3 har vi at vi kan finne dette vha. bipartitt matching, som vi igjen kan finne ved hjelp av flyt (som er det kapittel 26.3 handler om). Med andre ord:

  1. Bruk flyt til å finne en perfekt matching.
  2. Bruk denne til å finne et minimalt nodedekke (beskrevet i oppgaven).
  3. Komplementet er en maksimal uavhengig mengde (beskrevet i oppgaven).

Og det er altså løsningen vår.