Sisältö

Kurssilla tutustutaan ensin graafiteorian peruskäsitteisiin: graafityypit (yksinkertainen graafi, multigraafi, suunnattu graafi, painotettu graafi), aligraafi, komplementtigraafi, graafien operaatiot, graafien esittäminen matriiseina, graafien isomorfisuus. Tämän jälkeen perehdytään graafien yhtenäisyyteen liittyviin käsitteisiin ja tuloksiin. Seuraavana asiana tarkastellaan puita, ja erityisesti graafin virittäviä puita, joilla on keskeinen asema monissa graafialgoritmeissa. Kurssin lopuksi käydään läpi tärkeitä graafien luokkia, kuten Eulerin graafit, Hamiltonin graafit, tasograafit ja k-värittyvät graafit.

Opetus

Kurssin luennoija on Lauri Hella (lauri.hella (ät) uta.fi); vastaanotto maanantaisin klo 15-16.

Harjoituksia ohjaa Tommi Karila.

Luennot:

ti 14-16  Paavo Koli (Pinni A)

to 14-16  Paavo Koli (Pinni A)

Harjoitukset:

to 12-14  Pinni A3111

pe 14-16 SJ212B (TTY)

Luennot

Luennot striimataan ja videot tallennetaan. Linkit striimeihin ja videoihin lähetetään kurssin osallistujille sähköpostilla.

Harjoitukset

Harjoitustehtävät ilmestyvät edellisen viikon torstaihin mennessä. Linkit tehtävien pdf-tiedostoihin tulevat tähän kohtaan.

Harjoitus 1   Harjoitus 2   Harjoitus 3   Harjoitus 4   Harjoitus 5   Harjoitus 6

Loppukoe

Loppukokeen aika ja paikka:

ti  12.12.  klo 14-17  Paavo Koli (Pinni A)

Materiaalit

Luennot perustuvat Pertti Koiviston ja Riitta Niemistön oppikirjaan Graafiteoriaa.

Luentokalvot ilmestyvät tällä sivulla sitä mukaa, kun kurssi etenee:   Osa1    Osa2    Osa3   Osa4

Kurssin suorittaminen

Kurssi suoritetaan loppukokeella ja aktiivisella osallistumisella harjoituksiin. Loppukokeessa on 4 tehtävää, ja siitä voi saada 4×6 = 24 pistettä. Hyväksyttyyn suoritukseen vaaditaan n. puolet tästä pistemäärästä. Lisäksi harjoitustehtävistä tulee tehdä vähintään 40 %.

Harjoitustehtäviä tekemällä voi saada myös 1-6 lisäpistettä, joiden avulla saa kompensoida loppukokeessa mahdollisesti epäonnistuneen tehtävän pisteet. Kompensaatiopistemäärä p määräytyy kaavasta  p = min{h,k+3}, missä h on harjoitusten lisäpisteet ja k on kompensoitavan tehtävän pisteet (olettaen siis, että h > k).