Teorija grafova

U matematici i računarstvu teorija grafova jest proučavanje grafova, koji su matematičke strukture korištene za modeliranje parova odnosa između objekata. Graf u ovom kontektstu napravljen je od tjemena, čvorova, ili tačaka koje se spajaju ivicama, lukovima ili linijama. Može biti neusmjeren, što znači da nema razlike između dva tjemena povezana s ivicom, ili njeni vrhovi mogu biti usmjereni sa jednog tjemena na drugo. Grafovi su jedan od primarnih predmeta studija u diskretnoj matematici.

 Definicije 
Definicije u teoriji grafova variraju. Ovdje su navedeni samo neki od osnovnih načina definiranja grafova i povezanih matematičkih struktura.

 Graf 
U općenitom smislu pojma,Iyanaga and Kawada, 69 J, str. 234Biggs, str. 4. graf je poredani par G = (V, E) koji se sastoji od skupa V tjemena ili čvorova ili tačaka zajedno sa skupom E ivica ili lukova ili linija, koji su dvoelementni podskupovi od V (npr., ivica je povezana sa dva tjemena, a relacija je predstavljena kao neporedani par tjemena s obzirom na određene ivice). Da bi se izbjegla dvosmislenost, ova vrsta grafa može se opisati upravo kao neusmjeren i jednostavan.

Drugi smisao grafa proistječe iz različitih koncepcija ivice skupa. U općenitijem smislu,Graham et al., p. 5. V je skup zajedno s relacijama događaja koji su povezani sa svakom ivicom dva tjemena. U drugom uopćenom smislu E je multiskup neporedanih parova (ne nužno različitih) tjemena. Većina autora taj tip objekta naziva multigraf ili pseudograf.

Tjemena koja pripadaju ivici zovu se krajevi ili krajevi čvorova ruba. W tjeme može postojati u grafu i ne pripadati ivici.

V i E često se uzimaju kao ograničeni i većina dobro poznatih rezultata nije istinita (ili su različiti) za neograničene grafove jer većina argumenata potpada pod ograničen slučaj. Red grafa je |V|, njegov broj tjemena. Veličina grafa je |E|, njegov broj ivica. Stepen ili valencija tjemena je broj ivica koje se na to spajaju, gdje se ivica koja spaja tjeme sa sobom (petlja) broji dvaput.

Za ivicu {x, y} teoretičari grafova često koriste nešto skraćenu notaciju xy.

 Reference 

 Vanjski linkovi 

 Teorija grafova (autor Reinhard Diestel) 
 Teorija grafova s primjerima 

 Teorija grafova  (lekcije)