Graafiteoria A
Syksy 2007


Luennot ja harjoitukset

Kurssilla on joka toinen viikko luento ja joka toinen viikko harjoitukset.  Aika ja paikka ovat
ma  16-18   Pinni A1078

Luennot pidetään siis   10.9.   24.9.   8.10.   29.10.   5.11.   ja   26.11.
Harjoitukset ovat   17.9.   1.10.   15.10.   12.11.   19.11.   ja   3.12.

HUOM!  Ohjelmaa muutettu:  5.11.  on luento ja  12.11.  harjoitus.

Prof. Lauri Hella (lauri.hella@uta.fi, tavattavissa luentojen yhteydessä sekä vastaanotolla ma 13.00-14.00)
pitää sekä luennot että harjoitukset.

Loppukoe

Maanantaina  10.12.  klo 16-18   Pinni A1078.

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

Luennot noudattavat luentomonistetta

Pertti Koivisto - Riitta Niemistö,  Graafiteoriaa.
HUOM: Koska kurssilla on varsin vähän luentoja suhteessa käsiteltävän asian määrään, kurssin suorittaminen edellyttää tavallista suurempaa itsenäisen työskentelyn määrää.  Luennoilla ei käydä läpi kaikkia asioita yksityiskohtaisesti, vaan osa jätetään opiskelijan itsensä luettavaksi.

Kurssin suorittaminen ja arvostelu

Kurssi suoritetaan loppukokeella ja aktiivisella osallistumisella harjoituksiin. Loppukokeesta annetaan  0-24  pistettä ja harjoitustehtävien suorittamisesta  0-12  pistettä harjoitusaktiivisuudesta mukaan.  Läpipääsyyn vaaditaan yhteensä n. 18 pistettä.

Viikkoharjoitustehtävät

Tehtävät jaetaan harjoitusta edeltävällä luennoilla, jolloin ne löytyvät myös 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.9.                         1.1 Määritelmiä - 1.6 Komplementtigraafi                                             1-16              
    24.9.                         1.7  Graafioperaatioita - 2.3  Yhtenäinen graafi                                   17-32
                                            (2.2  Lyhin painotettu polku  jätetään pois!)
    8.10.                         2.3  Yhtenäinen graafi - 2.7  Irrotus ja irrotusjoukko                           32-47         
    29.10                        2.8  Yhtenäisyysaste - 3.1  Puu                                                            47-61
    5.11.                         3.1  Puu - 3.7  Perussilmukka ja perusirrotusjoukko                            62-79
                                           (3.4 Minimaalinen virittävä puu  jätetään pois!)
    26.11.                       4.1 Eulerin graafi - 4.4  Graafin värittäminen                                       83-96