Graafiteoria
Kevät 2011

Luennot ja harjoitukset

Huom: luentosalit ovat muuttuneet!

Luennot
ma  14-16   B3116   Pinni B
to    12-14   A1081   Pinni A
Harjoitukset
1. ryhmä   ma  10-12   C6   päätalo
2. ryhmä   ti     16-18   A1078   Pinni A
Luennot alkavat maanantaina 10.1. ja päättyvät maanantaina 21.2. Ensimmäiset harjoitukset ovat 17-18.1. ja viimeiset harjoitukset ovat 21-22.2.

Luennoija:  Prof. Lauri Hella (lauri.hella[ät]uta.fi, tavattavissa luentojen yhteydessä sekä vastaanotolla to 15-16).

Harjoitukset:  Raine Rönnholm (raine.ronnholm[ät]uta.fi).

Loppukoe

Torstaina  24.2.  klo 12-14   Väinö Linna -sali    Linna.

Kurssin sisältö

Kurssilla tutustutaan graafiteorian peruskäsitteisiin, kuten yksinkertainen graafi, multigraafi, suunnattu graafi, puu jne.  Lisäksi perehdytään yhtenäisyyden eri muotoihin ja käsitellään lyhyesti tasograafeja ja graafien värityksiä.

Luennoilla käytetään luentomonistetta

Pertti Koivisto - Riitta Niemistö,  Graafiteoriaa.

Kurssin suorittaminen ja arvostelu

Kurssi suoritetaan loppukokeella ja aktiivisella osallistumisella harjoituksiin. Loppukokeesta annetaan  0-24  pistettä. Harjoitustehtävien suorittamisesta saa pisteitä seuraavan taulukon mukaan:

    0-8   0 p       9-13   1 p       14-18   2 p       19-23   3 p       24-28   4 p       29-33   5 p       34-42   6 p

Nämä pisteet eivät ole lisäpisteitä, vaan niillä voi korvata yhden loppukokeessa mahdollisesti epäonnistuneen tehtävän pisteet. Läpipääsyyn vaaditaan n. 12 pistettä.

Viikkoharjoitustehtävät

Tehtävät annetaan harjoitusta edeltävän viikon maanantaina, jolloin ne löytyvät tältä kotisivulta.

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

Luentojen eteneminen

Alla on esitetty kunakin viikkona käsiteltävät aiheet ja vastaavat sivut oppikirjassa.

    Luento                      Luentoaiheet                                                                                      Kirjan sivut

    10. ja 13.1.                1.1 Määritelmiä - 1.6 Komplementtigraafi                                                   1-16
    17. ja 20.1.                1.7 Graafioperaatioita - 2.1 Polku                                                              17-29
    24. ja 27.1.                2.3 Yhtenäinen graafi - 2.7 Irrotus ja irrotusjoukko (alku)                         31-44
    31.1. ja 3.2.               2.7 Irrotus ja irrotusjoukko (loppu) - 2.10 Mengerin lause                         44-59
    7. ja 10.2.                  3.1 Puu - 3.2 Virittävä puu & 3.5 Metsä - 3.7 Perussilmukka ja ...        60-66 & 71-79
    14. ja 17.2.                4.1 Eulerin graafi - 4.4 Graafin värittäminen                                              83-96