Täiendav võimalus koduste ülesannete tulemuse parandamiseks

Vastavalt lahendatud koduste ülesannete arvule saab iga üliõpilane ühe järgmisest neljast tulemusest:

  1. kursus läbimata,
  2. (mitte midagi),
  3. 5 punkti kontrolltööde või eksami tulemusele lisaks,
  4. 10 punkti kontrolltööde või eksami tulemusele lisaks.
Lahendades käesoleval lehel toodud ülesande, on võimalik oma tulemust ühe taseme võrra tõsta. Ülesanne tuleks ära lahendada sessi lõpuks. Soovitav on siiski ta mulle natuke varem esitada, et ma saaksin ta üle vaadata ja puuduste ilmnemisel tagasi saata.

Ü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...

Ülesanne neile, kelle matriklinumber lõppeb numbriga 0, 2, 4, 6 või 8

Realiseerida minimaalse kaaluga täieliku kooskõla leidmise algoritm. Programmi väljundis tahaks mingil kujul näha ka suurusi Omega ja pi.

Ülesanne neile, kelle matriklinumber lõppeb numbriga 1, 3, 5, 7 või 9

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.

Programmide sisendid

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.