Teorija grafova

Grafovi su sastavljeni od tačaka, odnosno čvorova (vrhova), i linija među njima, odnosno grana.

Stepen čvora a grafa je broj grana grafa koji imaju kraj u tom čvoru.

Ulazni stepene čvora je broj orijentisanih grana koje ulaze u taj čvor, izlazni stepen je je broj orijentisanih grana koje izlaze iz tog čvora.

Ako je stepen svakog čvora isti, onda je graf regularan.

Dve (ili više) grane grafa su paralelne ako spajaju dva ista čvora.

Grana može da spaja čvor sa samim sobom, i tada se naziva petljom.

Izolovan čvor nema nijednu granu.

Graf je prazan ako nema nijednu granu.

Kompletan graf je graf, kod koga su svaka dva čvora spojena granom.

Planarni grafovi su oni grafovi koji se mogu nacrtati u ravni tako da im se grane ne seku.

šetnja: sekvenca čvor-grana-čvor-grana-...-čvor (čvorovi kao i grane se mogu se ponavljati)
linija: spojene grane, pri čemu svaka grana učestvuje samo jednom
put je takva linija, koja prolazi kroz određeni čvor samo jedanput.
zatvoren put (ili kružni put) je put koji se završava u istom čvoru u kojem i počinje.

 

Povezan graf je takav graf kod koga su bilo koja dva čvora povezana putem.

Ojlerov put je put, koji obilazi svaku granu tačno jednom.
Hamiltonov put je put koji posećuje svaki čvor tačno jednom..
Hamiltonov krug je Hamiltonov put koji je zatvoren.

 

Stablo: graf u kome su svaka dva čvora povezana tačno jednom stazom. Drugačije rečeno, svaki povezan graf bez ciklova je stablo..
Broj čvorova stabla=broj grana+1

Šuma: svaka komponenta šume je stablo.
Broj čvorova šume=broj grana+broj komponenata.