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[uredi | uredi izvor]
Definicije u teoriji grafova variraju. Ovdje su navedeni samo neki od osnovnih načina definiranja grafova i povezanih matematičkih struktura.
Graf[uredi | uredi izvor]
U općenitom smislu pojma,[1][2] 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,[3] 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[uredi | uredi izvor]
Vanjski linkovi[uredi | uredi izvor]
 |
Commons ima datoteke na temu: Teorija grafova |
- 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)
