Metoder til at finde mindste snit i en graf.
En graf består af punkter og kanter - hver kant forbinder 2 punkter,
og ikke alle punktpar har en forbindende kant. En graf, hvor man kan
komme fra hvert punkt til hvert andet punkt kaldes sammenhængende.
Et snit er en "mindste" mængde af kanter med den egenskab, at hvis
disse kanter fjernes falder grafen fra hinanden. Det mindste snit er
det blandt samtlige, der indeholder færrest kanter, og i forbindelse
med mange optimeringsproblemer er det relevant at finde et sådant.
Mulige fremgangsmåder til at løse mindste snit-problemet skal
undersøges, og deres effektivitet analyseres. Der skal implementeres
en eller flere metoder, og disses effektivitet i praksis skal
undersøges.
Opgavestiller
Professor
Jens Clausen,
Informatik og Matematisk Modellering, 4525 3387
Email: jc@imm.dtu.dk