Graf (matematika)

Izvor: Wikipedija
Prijeđi na navigaciju Prijeđi na pretraživanje
Graf. Čvorovi su imenovani brojevima od 1 do 6.

Graf je skup bridova i čvorova koji opisuju odnose između objekata. Mogu biti usmjereni i neusmjereni te težinski i bestežinski.

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.

Usmjereni težinski graf. Iz čvora C se ne može u nijedan drugi čvor. Iz nijednog čvora ne možemo u čvor A, pa čak ni iz njega samog.

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.[1] 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[uredi VE | uredi]

Č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[uredi VE | uredi]

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

Binarno stablo.
Potpuno binarno stablo.

Binarno stablo[uredi VE | uredi]

Binarno stablo ili binarno drvo[3] je poseban 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.[2] 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š[uredi VE | uredi]

Logotip Zajedničkog poslužitelja
Na Zajedničkom poslužitelju postoje datoteke vezane uz: Graf (matematika)

Literatura[uredi VE | uredi]

Izvori[uredi VE | uredi]