Opgave O3

En todelt graf G=(U,W,E), hvor U={0,...,n₁-1}, W={0,...,n₂-1} og |E|=m kan passende repræsenteres eksternt på følgende måde:

    n1
    n2
    m
    u1  w1
    u2  w2
    ...
    um  wm.

Her angiver u_i og w_i kanten (u_i,w_i)E hvor u_iU og w_iW. Grafen fra introduktionen har i denne repræsentation følgende udseende:

    5
    5
    10
    0  0
    0  1
    0  3
    1  0
    1  1
    1  2
    2  2
    2  4
    3  1
    4  1

Opgave 3 består af seks dele, hvoraf den sidste er frivillig:

1. Skriv i Java en metode, der læser en sådan ekstern repræsentation af en todelt graf og konstruerer den tilsvarende parringsgraf.
2. Skriv et Java-program der implementerer algoritmen Størst mulig pardannelse. Programmet kan med fordel indeholde en klasse der realiserer en parringsgraf med følgende interface:

       public interface ParringsGraf {
          public void farvGraf();
          public boolean findesSkifteVej();
          public void opdaterGraf();
          public void farvHvid();
       }
   

   Det færdige program skal kunne kaldes som følger:

       java MaxParring filnavn
   

   hvor filnavn indeholder en todelt graf i ovenstående eksterne repræsentation. Programmet skal nu køre algoritmen på denne graf og udskrive resultatet.
3. Test programmet ved at køre det på et udvalg af små grafer, hvor resultatet er kendt, og kontroller, at programmet giver det rigtige resultat.
4. Brug programmet til at løse følgende skemaplanlægningsproblem fra Vorrevangsskolen: Filen vorrevang.gph indeholder den eksterne repræsentation af en todelt graf (U,W,E). Her angiver U lærerne, W klasserne og en kant (u,w)E at lærer u kan undervise klasse w. Hvor mange klasser kan undervises samtidigt og af hvilke lærere?
5. Brug programmet til at løse følgende repræsentant-problem: I Vorrevangsskolens 5.b går disse 18 elever:

   Anders, Bodil, Camilla, Doris, Esben, Frida, Gert, Hassan, Ida, Jane, Klaus, Liv, Morten, Nicolai, Ofelia, Peter, Rasmus, Sine

   Klassen er ved at øve sig på en skolekomedie, hvor de er på scenen som følger

   Scene	Medvirkende
   1	Doris, Esben, Hassan, Jane, Peter, Sine
   2	Liv, Sine
   3	Hassan, Klaus, Peter
   4	Frida, Hassan, Nicolai, Ofelia, Rasmus, Sine
   5	Bodil, Hassan, Liv, Peter, Sine
   6	Hassan, Peter, Rasmus, Sine
   7	Bodil, Hassan, Liv, Peter
   8	Anders, Ida, Klaus, Morten, Nicolai
   9	Bodil, Peter, Sine
   10	Camilla, Doris, Gert, Ofelia, Rasmus
   11	Bodil, Klaus, Liv, Peter
   12	Hassan, Klaus, Sine
   13	Alle

   5.b's klasselærer vil gerne have valgt en elev-repræsentant for hver scene til at stå for rekvisitter. Repræsentanten for en scene skal selv være med i scenen, og ingen elev må repræsentere mere end 1 scene. Hvordan kan sådanne 13 repræsentanter vælges (om overhovedet)? Klasselæreren overvejer at droppe scene 12. Hvordan stiller sagen sig så?

6. Frivillig Kør programmet på et antal tilfældige grafer og sammenhold den observerede udførelsestid med den analyserede udførelsestid.
   Til generering af tilfældige grafer kan bruges programmet RandomGraf kaldt som følger:

       java RandomGraf filnavn n1 n2 m
   

   Det giver en tilfældig graf med n1 venstre-, n2 højreknuder og m kanter, som gemmes i filen filnavn i ovenstående eksterne repræsentation.
   Man behøver naturligvis ikke bruge dette program hvis man hellere vil ``gøre arbejdet selv''.

Den samlede besvarelse

Den samlede obligatoriske opgave udgøres af opgave O1, O2 og O3. Disse tre opgaver beskriver et sammenhængende forløb der omhandler udformning, implementation, test og brug af et program til løsning af størst mulig pardannelse i en todelt graf, og det forventes at der afleveres en sammenhængende rapport der beskriver denne proces; samtidigt skal der afleveres kildekode. Følgende konkrete krav forventes opfyldt.

Rapporten (som skal være forsynet med den officielle forside [ps,pdf,LaTeX] skal udformes så den kan læses og forstås af en datalogistuderende på jeres eget niveau. Det betyder, at I må antage at læseren kender til grafer, algoritmer, O-notation, med mere.

Med mindre I har aftalt andet med jeres instruktor, skal rapporten skrives på dansk eller engelsk. Der er ingen særlige krav til typografi eller tekstbehandling. Rapporten må gerne være håndskrevet, men den skal kunne læses.

Udover de i O1, O2 og O3 eksplicit angivne krav, skal rapporten indeholde følgende elementer (ikke nødvendigvis i denne rækkefølge):

• Dokumentation af det færdige program: En kortfattet og præcis beskrivelse af programmets virkemåde der gør det muligt for én, der i forvejen kender Java, at forstå programmet. Til dokumentation hører en beskrivelse af hvordan I har afprøvet programmet og resultatet af denne afprøvning.
• Programteksten som bilag.
• Eventuelle eksperimentelle resultater som bilag.

Ved aflevering af den obligatoriske opgave skal den færdige Java-kode samtidigt være tilgængeligt for instruktoren. Det angives i opgaven hvor denne kode kan findes (husk at gøre det læsbart for instruktorerne).

Bemærkninger