031029 Graafiteoria

Luennot  Laskuharjoitukset   Välikokeet    Kirjallisuus     Suorittaminen   

Tiedotuksia:

2. Välikokeen koealue: Luentomonisteesta kappale 6.4  luvut 7-10 sekä luentomuistiinpanot
                                         Laskuharjoitustehtävät  48-85.

Vanhoja välikokeita:  Kevät 2011 1. Välikoe , Kevät 2010 1. Välikoe , Kevät 2009 1. Välikoe , Kevät 2007 1. Välikoe , Kevät 2006 1. Välikoe ,

Luennoin keväällä 2012 kurssin 031029S Graafiteoria. Kurssi soveltuu sähkö/tietotekniikan jatko-opintokurssiksi sekä matematiikan opintojen syventäväksi kurssiksi.

 Esitiedot:

 Varsinaisesti matematiikan esitietoja ei tarvita, tosin diskreetin matematiikan perusteiden tietämyksestä on hyötyä. Hyvän pohjan antaa mm. TTK:n Matematiikan jaoksen kurssi Tietotekniikan matematiikka tai Matemaattisten tieteiden laitoksen kurssi Diskreetti matematiikka.

Kurssin laajuus:

Kurssin laajuus on 8 opintopistettä. Luonnontieteellisen tiedekunnan opiskelijat voivat  laajentaa kurssin laajuuden 10 opintopisteeksi harjoitustyön avulla.

Luentoja kurssiin sisältyy 40 h ja laskuharjoituksia 20 h.

Ilmoittautuminen

Kurssille ilmoittaudutaan Weboodissa

Aikataulu:

Luentoajat  ovat Ma  14 - 16 ja To 10-12 . Laskuharjoitukset pidetään maanantaisin  klo 12-14 . Ensimmäinen luentokerta on 16.1.2010.  


Välikoeajat

Tiivistelmä luennoista

 Täydennän  luentotiivistelmää  (päivitetty 28.2.2012) aina hyvissä ajoin ennen luentoa. Luentotiivistelmä ei ole täydellinen kurssimateriaali, vaan lähinnä kirjoitusvaivaa vähentävä määritelmien ja tulosten luettelo. Allaolevaan taulukkoon lisään luentojen aiheet  ja laskuharjoituksissa käsiteltävät tehtävät.

 Viikkoaikataulu

Viikko

Luentojen aiheet

Laskuharjoitukset

3

Ma: Merkintöjä ja peruskäsitteitä. Luentomonisteesta kappaleet 2.1-2.5

To:Graafien esitysmuodot, asteet ja tyypit sekä aligraafit. Luentomonisteesta kappaleet 2.6-2.8 ja alkua 2.9:stä.

Luentokalvot

 Ei harjoituksia

4

Ma: Graafien komponentit, blokit ja sillat. Keveimmät polut, Dijkstran algoritmi (kappaleet 2.9 ja 2.10).

To: Graafien operaatioita. Puut alkua  (kappaleet 2.11 ja 3.1).

Luentokalvot

Tehtävät 1-10. Tehtävät allaolevasta linkistä.

Harjoitustehtäviä 1

5

Ma: Puun lehtien lukumäärä. Kevein graafin virittävä puu. Kruskalin ja Primin algoritmit. (kappaleet 3.1-3.3)

To: Kaksijakoiset graafit. Sovitukset (kappaleet 4.1 ja 4.2)

Luentokalvot

Tehtävät 11-18. Tehtävät löytyvät allaolevasta linkistä.


Harjoitustehtäviä 2

6

Ma Sovitukset jatkoa. Erilliset edustajat (kappale 4.3).

Etäisyys graafeissa. (luku 5)

To: Etäisyys graafeissa jatkoa. Graafin yhtenäisyys alku.

Luentokalvot

Tehtävät 19-28. Tehtävät löytyvät allaolevasta linkistä.


Harjoitustehtäviä 3

7

Ma: Graafien yhtenäisyys(luku 6)

Pe: Graafien yhtenäisyys jatkoa. Viansieto (luku 6)

Luentokalvot

Tehtävät 29-38. Tehtävät löytyvät allaolevasta linkistä.


Harjoitustehtäviä 4

8

Ma: Viansieto jatkoa

To: Eulerin graafit Postimies -ongelma. (Luku 7 alku)

Luentokalvot

 Tehtävät 39-47. Tehtävät löytyvät allaolevasta linkistä.

Harjoitustehtäviä 5

Tehtävän 47 ratkaisu

9

Ma: Hamiltonin graafi ja Kauppamatkustaja ongelma

To: Pisteiden väritykset. Viivojen väritykset

Luentokalvot

Tehtävät 48-53. Tehtävät löytyvät allaolevasta linkistä.


Harjoitustehtäviä 6

10

 Ma: Ei luentoja

To: Ei harjoituksia
 Ma: Ei harjoituksia

11

Ma: Tasograafit

To: Tasograafit jatkoa.

Luentokalvot

 Tehtävät 54-62. Tehtävät löytyvät allaolevasta linkistä.

Harjoitustehtäviä 7

12

Ma. Tasograafin väritys. Pintaupotukset

To: Suunnatut graafit ja turnaukset. Siirtoverkot

Luentokalvot

 Tehtävät 63-69 ja 71-72. Tehtävät löytyvät allaolevasta linkistä.

Harjoitustehtäviä 8
13

Ma:     Maksimivirtaus. Max-flow Min-cut

To: Max-Flow Min-Cut jatkoa. Viimeinen luento.

Luentokalvot		 Tehtävät 70 ja 73-82. Tehtävät löytyvät allaolevasta linkistä.

Harjoitustehtäviä 9

14

 Ei luentoja
 Tehtävät 83-85. Tehtävät löytyvät allaolevasta linkistä. Viimeinen harjoitus.
Harjoitustehtäviä 10

 

Kirjallisuus:

 

R. Diestel                                                  Graph Theory

F. Harary:                                                   Graph Theory

J.A. Bondy, U.S.R. Murty                       Graph Theory with Applications

 

 

Sisältö

 

Kurssilla käsitellään mm. seuraavia aiheita:

 

Puut. Sovitukset ja kaksijakoiset graafit. Etäisyys ja saavutettavuus graafeissa. Eulerin ja Hamiltonin graafit. Kaupparatsu- ja Postimiesongelmat. Graafien väritykset. Tasograafit. Suunnatut graafit .  Siirtoverkot.

 

Kurssin suorittaminen

Kurssi voidaan suorittaa kahdella eri tavalla:

A. Välikokeet.

Keväällä 2012 järjestetään kaksi välikoetta (kts. ajat ).

Molemmissa välikokeissa 4 tehtävää, joista jokaisen maksimipistemäärä on 6 pistettä.

Kokeiden maksimipistemäärä on 48 pistettä.

Varma läpipääsy 24 pisteellä.

B. LOPPUKOE:

 

Vaatimuksena koko kurssimateriaali

5 tehtävää  á 6 pistettä. maksimi 30 pistettä.

Varma läpipääsy 14 pisteellä

 

Keväällä 2012 on 1 loppukoe (kts aika), kesällä 2012 1 loppukoe ja  syksyllä 2012 2 loppukoetta.