Teorija grafova

Crtanje grafa

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, 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, 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.

Vanjski linkovi

• Teorija grafova (autor Reinhard Diestel) (en)
• Teorija grafova s primjerima (en)
• Hazewinkel, Michiel, ured. (2001), "Graph theory", Matematička enciklopedija, Kluwer Academic Publishers, ISBN 978-1556080104
• Teorija grafova Arhivirano 16. 1. 2012. na Wayback Machine (lekcije) (en)