grafiiteoriasta

Graafiteoria on matematiikan haara, joka tutkii graafeja eli rakenteita, joissa on solmuja ja reunoja. Graafi merkitään G=(V,E), missä V on solmujen joukko ja E reunoista muodostuva joukko. Reunat voivat olla suunnattuja (suunnattu graafi) tai ei-suunnattuja (suuntaamaton graafi). Painotetuissa grafiteorioissa reunoille voidaan liittää luku, joka kuvaa esimerkiksi kustannusta tai kapasiteettia.

Keskeisiä käsitteitä ovat solmujen aste deg(v) sekä suunnatuissa graafeissa sisään-aste ja ulos-aste. Polku on sarja peräkkäisiä reunoja, joilla yhdistetään solmuja; kierto (sykl) on polku, joka palautuu alkusolmuunsa. Graafi on yhdistetty, jos siitä voidaan päästä mihin tahansa solmuun ilman irrotuksia; puu on yhdistetty graafi, jossa ei ole kiertoa.

Planaarisuus tarkoittaa, että graafin voi piirtää tasolle ilman reunoja leikkaavia toisiaan. Kuratowskin teoreeman mukaan graafi on planaarinen, jos sillä ei ole K5- tai K3,3-subgrafien kiertoja. Väritys tutkii, kuinka monta väriä tarvitaan naapurien erottamiseen. Tärkeitä rakenteita ovat puut, kiertovirrat ja paritukset.

Algoritmit ovat keskeisiä: BFS ja DFS yhteyksien ja kiertojen havaitsemiseen; Dijkstra lyhyimmän polun löytämiseen ei-negatiivisilla reunoilla sekä Bellman-Ford negatiivisilla arvoilla. Puun rakentamiseen Prim ja Kruskal. Kaikki-väliä etäisyyksiä ratkaistaan Floyd–Warshallilla. Reittejä ja virtoja hyödynnetään käytännön ongelmissa.

Sovelluksiin kuuluvat tietoliikenneverkot, sosiaaliset verkostot, logistiikka sekä biologia ja kemia. Graafiteoria on monipuolinen ala, ja sen alalajit kuten algebra- ja satunnaisgraafiteoria sekä topologinen graafiteoria tarjoavat työkaluja moniin tutkimuskohteisiin.