Graf je skup bridova i čvorova koji opisuju odnose između objekata. Mogu biti usmjereni i neusmjereni te težinski i bestežinski. Koristi se za opisivanje relacija između dvaju objekata iz određene kolekcije. U ovom kontekstu odnosi se na neprazni skup vrhova i kolekciju bridova koji povezuju par vrhova.

Definicija Definiran je dvama odvojenim skupovima i pripadajućim odnosima među njima. Ti skupovi su skup čvorova , skup grana, lukova dva su odvojena skupa.Sveučilište u Zagrebu, Geodetski fakultet, Zavod za kartografiju i fotogrametriju Nada Vučetić: OSNOVE GEOINFORMATIKE: Neki pojmovi i definicije iz teorije grafova, Osnove teorije skupova (pristupljeno 8. siječnja 2020.)

Matematički definirano, graf G predstavlja uređenu trojku G = (V(G), E(G), φG. Sastavni su joj dijelovi: neprazan skup V = V(G), čiji su elementi vrhovi od G skup E(G) disjunktan s V(G), čiji su elementi bridovi od G funkcija incidencije φG, koja svakom bridu od G pridružuje neuređen par (ne nužno različitih) vrhova od G.

Kraći zapis koji se katkad primjenjuje za G = (V(G), E(G), φG jest

U usmjerenom grafu neki su bridovi jednosmjerni. Ako u usmjerenom grafu možemo iz čvora A doći u čvor B ne znači da možemo iz čvora B doći u čvor A. Jednosmjernih bridova nema u neusmjerenim grafovima.

U težinskim grafovima svaki brid ima svoju vrijednost. U bestežinskim grafovima vrijednost svakog brida prema dogovoru iznosi 1.

Brid koji počinje i završava u istom vrhu zove se petlja. Ciklus je zatvorena staza u kojoj su svi unutarnji vrhovi međusobno različiti.Teorija grafova i logistika, Hrvatski matematički elektronički časopis Drugim riječima, ciklus je staza koja počinje i završava u istome čvoru.

Povezan graf s n čvorova i n-1 bridova zove se stablo. U stablu nema ciklusa ni petlji.

Komponenta grafa je povezani dio grafa. U neusmjerenom grafu iz svakog čvora neke komponente možemo u svaki čvor te iste komponente. U nijednom grafu ne možemo preko bilo kojeg brida prijeći iz jedne komponente u drugu. Jedna komponenta može obuhvaćati i cijeli graf.

Čvor

Čvor je osnovna gradivna jedinica grafa.

Za svaki čvor je poznat ulazni te izlazni stupanj. Ulazni stupanj označava broj bridova koji ulaze u taj čvor, a izlazni stupanj iznosi broj bridova koji izlaze iz čvora. U neusmjerenim grafovima, zbroj ulaznih stupnjeva svih čvorova jednak je zbroju izlaznih stupnjeva svih čvorova, a iznosi dvostruki broj bridova.

Stablo

Stablo je povezan graf s n čvorova i n-1 bridova. U stablu postoji poseban čvor koji nazivamo korijen stabla. U stablu nema ciklusa ni petlji.

mini|lijevo|150px|Binarno stablo. mini|desno|150px|Potpuno binarno stablo. Binarno stablo

Binarno stablo ili binarno drvo usmjereno stablo u kojemu za svaki vrh postoje najviše dva brida kojima je taj vrh početna točka. Katkad se podrazumijeva da je binarno stablo ravninsko.Binarno stablo, Hrvatsko strukovno nazivlje Poseban je slučaj stabla u kojem svaki čvor ima najviše dvoje djece, koja se zovu lijevo dijete i desno dijete. Svaki čvor osim korijena ima točno jednog roditelja, a korijen nema nijednog roditelja. Listovi su čvorovi koji nemaju nijedno dijete.

Potpuno binarno stablo je binarno stablo u kojem su svi listovi jednake dubine, a svi ostali čvorovi imaju točno dvoje djece.

Vidi još Graf (struktura podataka) Nul-graf

Literatura Teorija grafova, Hrvatski matematički elektronički časopis

Izvori

Kategorija:Teorija grafova