MATA1410 Johdatus verkkoteoriaan (4 op)

Verkkoteorian alkeita.

Esimerkiksi kirja Harary: Graph Theory kattaa kurssin sisällön.

Opintojakson suorittamisen jälkeen opiskelija

• hallitsee verkkoteorian keskeiset tulokset ja määritelmät, kuten puut, kaksijakoiset verkot, verkkojen yhtenäisyyden ja tasoverkot.
• tuntee verkkojen, multiverkkojen, pseudoverkkojen, painotettujen verkkojen ja suunnattujen verkkojen määritelmät.
• tuntee verkkojen isomorfisuuden käsitteen ja osaa vertailla kahden verkon välistä isomorfisuutta esimerkiksi verkkojen naapurimatriiseita ja naapurilistoja vertailemalla.
• hallitsee keskeisimpien verkkoalgoritmien käytön verkkoihin liittyvien ongelmien ratkaisemisessa ja tarkastelussa.
• tuntee Eulerin ja Hamiltonin verkot sekä kauppamatkustajan ongelman.
• tuntee tasoverkkoihin liittyvän Eulerin kaavan ja Kuratowskin tasoverkkojen karakterisointilauseen, sekä osaa hyödyntää näitä tasoverkkoihin liittyvissä tarkasteluissa.
• tuntee verkkojen väriluvun ja tasoverkkojen värilauseet.
• osaa soveltaa induktiota verkkoihin liittyvien tuloksien todistamiseksi.
• on tutustunut verkkoteorian historiaan ja joihinkin sen sovelluksiin.

Luentototeutus järjestetään vuorovuosittain Johdatus kombinatoriikkaan -opintojakson kanssa. Suunnitellut toteutusajankohdat syksy 2024 ja syksy 2026.

Lukion matematiikan pitkä oppimäärä. Kurssien Todistamisen perusteet tai Johdatus matematiikkaan suorittamisesta on hyötyä.

Luentomoniste,

Harary: Graph Theory.

Trudeau: Introduction to Graph Theory,

Balakrishnan: Introduction to Discrete Mathematics,

Chartrand & Lesniak: Graphs & Digraphs,

Behzad, Chartrand & Lesniak-Foster: Graphs & Digraphs.