Graf

Ako tražite vlastelinsku titulu, pogledajte Graf.

Graf je apstraktni matematički objekat, a crtež koji se sastoji od tačaka i linija je samo geometrijska predstava grafa. Međutim, uobičajeno je da se takva slika naziva grafom. Pa pošto je graf sastavljen iz tačaka i linija, koje spajaju po dve tačke, onda je odatle moguće izvesti i formalnu definiciju grafa.

Označeni graf sa 6 čvorova i 7 grana

Ovakva uopštena definicija omogućuje da graf primenjujemo ne samo u matematici, već i u informatici, elektrotehnici i tehnici uopšte, a takođe i u hemiji, lingvistici, ekonomiji i mnogim drugim oblastima.

Definicije

Kako je već prethodno napomenuto u definisanju pojma grafa se koristimo pojmovima iz teorije skupova. Tako jedna stroga definicija glasi

„Graf je uređeni par G = (X, ρ), gde je X konačan neprazan skup, a ρ binarna relacija u H.“

Dok jedna druga dopušta i beskonačan broj čvorova (i grana)

„Neka je X neprazan skup i ρ binarna relacija u H. Uređeni par G = (X, ρ) naziva se graf. Elementi skupa H su čvorovi grafa, a elementi skupa ρ grane grafa.“

Pojam grafa je moguće generalisati ako prihvatimo da je moguće da postoji više od jedne grane iste orijentacije, odnosno da mogu postojati i višestruke petlje. Takav graf se onda zove multigraf. Običan graf je onda poseban slučaj multigrafa.

Definicija takvog multigrafa bi bila

„Neka je X neprazan skup i U jedna kombinacija sa ponavljanjem skupa H². Uređeni par G = (X, U) naziva se multigraf.“

U svakom slučaju, graf je zadat ako su zadata dva skupa, skup čvorova i skup grana.

Vrste grafa

Graf koji ima konačan broj čvorova se zove konačan graf. Analogno, graf sa beskonačnim brojem čvorova se zove beskonačan graf.

Ako je svejedno da li je grana grafa AB isto što i BA i to važi za sve grane grafa, onda je ρ simetrična relacija, a graf je simetričan ili neorijentisan. Kod takvih grafova se izostavljaju strelice na crtežu.

Ako sve grane na grafu imaju strelice, odnosno orijentisane su, tada je ceo graf orijentisan ili antisimetričan.

Povezan graf je takav neorijentisani graf kod koga se bilo koja dva čvora mogu povezati putem. Ako postoje dva čvora koja se ne mogu povezati, graf je nepovezan.

Pojmovi

Grana grafa koja polazi iz jednog čvora i završava u istom čvoru se zove petlja.

Nepovezan graf se sastoji od bar dva nepovezana dela. Takvi delovi se zovu komponente povezanosti grafa.

Ako se udaljavanjem jednog čvora iz grafa on raspada, odnosno broj komponenata povezanosti se povećava, tada je taj čvor artikulacioni čvor.

Ako se udaljavanjem jedne grane graf raspada, grana se zove most grafa.

Stepen čvora grafa je broj grana grafa koji imaju kraj u čvoru. Ako grana spaja čvor sa samim sobom, onda se ona računa dva puta.

Grana koja spaja čvor sa stepenom jedan je viseća grana.

Vidi još

• Teorija grafova
• Hipergraf
• Dragoš Cvetković
• Planarni graf

Literatura

Graf na Wikimedijinoj ostavi