Opgave O2

En todelt graf kan angives på formen G=(V₁,V₂,E), hvor V₁={1,...,n₁}, V₂={1,...,n₂} og E er en mængde af par (v₁,v₂), hvor v₁V₁ og v₂V₂.

Opgaven går ud på at designe en hensigtsmæssig realisation af parringsgrafen G', hvor V₁ hhv. V₂ er de firkantede hhv. runde knuder, så

• Farv G' får udførelsestid O(m+n) (m=|E|, n=n₁+n₂).
• Opdater G' mht. får udførelsestid proportional med længden af .

Opgave 2 består af tre dele:

1. Angiv (der er altså ikke tale om en implementation) en sådan hensigstmæssig repræsentation af G'.
2. Skriv algoritmen (gerne i pseudokode) der realiserer Farv G', og argumentér for udførelsestiden.
3. Skriv algoritmen (gerne i pseudokode) der realiserer Opdater G' mht. og argumentér for udførelsestiden.

Uagtet at der ikke er tale om en implementation, vil det være nyttigt ved besvarelsen at tage hensyn til følgende filer, Node.java, Edge.java, Sequence.java, Locator.java, som tilsammen indeholder tre klasser, som det stærkt anbefales at benytte til den endelige implementation.