Vastavalt lahendatud koduste ülesannete arvule saab iga üliõpilane ühe järgmisest neljast tulemusest:
Ülesande lahenduseks on programm, mis mulle saata tuleb (kindlasti koos lähtetekstiga). Mu soov on, et iga lahendaja selle programmi iseseisvalt kirjutaks. Seda, kas kaks programmi on tegelikult üks ja seesama programm, on tegelikult nende tekstidele peale vaadates väga lihtne kindlaks teha...
Realiseerida minimaalse kaaluga täieliku kooskõla leidmise algoritm. Programmi väljundis tahaks mingil kujul näha ka suurusi Omega ja pi.
Loengus toodud Vizingi teoreemi tõestus (see esimene, mis ainult lihtgraafide kohta käis) on konstruktiivne, s.t. temast on lihtsasti leitav algoritm, mis graafi G servad Delta(G)+1 värviga värvib. Ülesandeks ongi see algoritm realiseerida.
Fikseerime siinkohal ära, kust programm oma sisendid saab ja millisel kujul nad on.
Sisend saadakse failist, mille nime võib programm küsida või võtta selle
käsurealt (võite ise valida, millise mooduse realiseerite). Sisendfaili
esimesel real on kaks naturaalarvu n ja m, mis on
vastavalt graafi tippude ja servade arvuks. Seejuures n on vähemalt
1 (programm ei pea seda kontrollima).
Graafi tippudeks on naturaalarvud 1, 2,..., n.
Sisendfaili
järgmisel m real on igaühel kas kolm või kaks naturaalarvu
(sõltuvalt ülesandest). Iga rida kirjeldab ühte serva, esimesed kaks arvu on
selle serva otstipud. Servad on suunamata, nii et nende kahe arvu järjekord
ei ole oluline. Garanteeritud on, et samade tippude vahel on ülimalt üks
serv. Minimaalse kaaluga täieliku kooskõla leidmise ülesandes näitab kolmas
arv serva kaalu; see arv on täisarv (s.t. võib olla negatiivne). Servade
värvimise ülesandes kolmandat arvu ei ole.
Minimaalse kaaluga täieliku kooskõla ülesandes on garanteeritud, et graafis
leidub mingi täielik kooskõla.