Predstavljanje grafova putem računara

Predstavljanje grafova putem računara

(šetnje po grafu, lista susjedstva, matrica incidencije, matrica susjedstva...)

naida.karovic@cetvrta-gimnazija.edu.ba adna.osmanovic@cetvrta-gimnazija.edu.ba

ŠTA JE GRAF?

Graf je skup objekata: vrhova, tačaka ili čvorova koje povezuju bridovi (crte, linije). Brid spaja dva čvora i to je odnos koji definiše graf.Ako vrhove povezuje brid, grafove se prikazuje crtanjem tačaka za svaki vrh i povlačenjem luka između dvaju vrhova.

Definicija

Graf G je uređen par (V,E) gdje je V konačan neprazan skup, a skup E predstavlja binarne relacije elemenata skupa V. Elementi skupa V se nazivaju čvorovi, a elementi skupa E grane. Broj elemenata skupa V naziva se red grafa.

ŠETNJA PO GRAFU

Rad sa grafovima podrazumjeva obilazak i prolazak tim istim grafom. Za razliku od stabla, graf nema početnog definisanog čvora. Praksa programera je da se taj čvor odabere slučajnim odabirom ili proslijedi kao parametar u funkciji algoritma. U slučaju da jedan čvor ima više susjeda, uvodi se dodatni vektor koji ima binarne vrijednosti i na početku stavimo 0 jer su svi čvorovi neposjećeni. Kada posjetimo prvi put čvor stavimo 1 i ne mijenjamo vrijednost prilikom naredne posjete tog istog čvora.

Pomoću sljedeća dva algoritma možemo vršiti šetnju po grafu:

ŠETNJA PO ŠIRINI

ŠETNJA PO DUBINI

Algoritam obilazak po širini (eng. breadth-first search BFS) polazi od polaznog čvora, koji smo slučajno odabrali ili proslijedili kao parameter funkcije, posjećuje susjede tog čvora, pa zatim susjede susjeda i tako sve dok svi čvorovi ne budu posjećeni. Za implementaciju ovog algoritma pogodna je struktura podataka red.

Algoritam obilazaka po dubini (eng. depth-first search DFS) polazi od polaznog čvora, kojeg smo slučajno odabrali ili proslijedili kao parametar funkcije, i ide u jednom pravcu ukoliko je to moguće. Kada dođe do zadnjeg čvora u jednom pravcu vraća se nazad do prvog čvora koji mu omogućava da ide u dubinu drugog i postupak se ponavlja dok svi čvorovi ne budu posjećeni.

VS

+info

+info

OTVORENA I ZATVORENA ŠETNJA

Niz u šetnji počinje i završava vrhom. Svaki vrh iz šetnje incidentan je prethodećem mu bridu i bridu koji mu slijedi u tom nizu. Vrh prethodeći bridu i vrh koji slijedi taj brid krajnji su vrhovi tog brida. Šetnja od vrha V0 do vrha Vi dužine je i u grafu G i čini je niz i bridova V0 V1, V2 V3...Vi-1 Vi Obično se šetnju označava s V0 V1, V2 V3......Vi-1 Vi Kad su prvi i zadnji vrh jednaki, šetnja je zatvorena. Ako su prvi i zadnji vrh različiti, šetnja je otvorena. Ako u ovoj vrsti šetnje nema ponavljanja vrhova pa prema tome ni bridova, zovemo je put.

Šetnja

LISTA SUSJEDSTVA

Graf također možemo predstaviti i pomoću liste susjedstva. Ovakav način predstavljanja grafa ima formu da za svaki čvor grafa imamo listu. Na osnovu liste susjedstva predstavljamo samo postojeće grane grafa. Kada je riječ o neusmjerenim grafovima ovakav način predstavljanja grafova je nebitan, jer svaka grana će se pojavljivati dva puta u listama. Jednom u listi od čvora u,a drugi put u listi od čvora v.

MATRICA INCIDENCIJE I MATRICA SUSJEDSTVA

ŠTA JE INCIDENCIJA?

Kod jednostavnih grafova svaki brid može se identificirati s parom različitih vrhova. Dva su vrha povezana bridom i naziva ih se incidentnima tom bridu, odnosno brid je incidentan tim dvama vrhovima. Stepen vrha V u grafu G predstavlja broj bridova koji su incidentni sa V pri čemu se petlje broje dva puta.

MATRICA INCIDENCIJE

Često je vrlo korisno relacije incidencije i susjedstva u grafu prikazati matricama. Neka je G graf sa V vrhovima (v1,...vn) i E bridovima (e1....en). Matrica incidencije grafa G je V x E matrica M(G)=(mij), broj koliko su puta Vi i Vj incidentni. Matrica incidencije potpuno određuje graf.

MATRICA SUSJEDSTVA

Matrica susjedstva grafa G je V x V matrica A(G)=(aij), gdje je aij broj bridova koji spajaju vrhove Vi i Vj. Matrica susjedstva je simetrična matrica (tj. ܽaij=aji), čiji su elementi negativni cijeli brojevi. Ako je graf jednostavan, ova matrica sadrži samo nule i jedinice te nule na glavnoj dijagonali. Često se graf unosi u računar upravo ovom matricom, iako to nije najefikasniji način pohrane grafa u računalu zbog dosta nula i ponavljanja već navedenih susjedstava. Obje matrice ovise o odabranom označavanju vrhova i bridova. Zbir elemenata u svakom redu matrice incidencije je 2 (jer svaki brid ima dva kraja). Zbir članova ݆j-tog reda matrice susjedstva jednak je broju bridova incidentnih s Vj.

Hvala na pažnji!