Teorija grafova

S Wikipedije, slobodne enciklopedije
Jump to navigation Jump to search
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[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]

  1. ^ Iyanaga and Kawada, 69 J, str. 234
  2. ^ Biggs, str. 4.
  3. ^ Graham et al., p. 5.

Vanjski linkovi[uredi | uredi izvor]

  • 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 (lekcije) (en)