Prijeđi na sadržaj

Čvor (teorija grafova)

Izvor: Wikipedija

Vrh odnosno čvor, pojam iz teorije grafova. To je jedan od definirajućih dijelova grafa. Skup čvorova , skup grana, lukova dva su odvojena skupa. Ta dva odvojena skupa i pripadajući odnosi među njima definiraju graf. Čvorove se na grafovima prikazuje točkama. Čvorovi su povezani pravim ili krivim crtama, kao prikaz incidentnih odnosa. Dva čvora incidentna s nekom granom jesu susjedni čvorovi. Ako dvije grane imaju zajednički čvor, to su susjedne grane.[1]

Dio je skupa vrhova V = V(G) u grafu, koji su dio uređenog para G = (V, E) koji čine graf G. Drugi dio uređenog para čini skup bridova E = E(G) disjunktnih s V. Svaki brid e ∈ E spaja dva vrha u, v ∈ V koji se zovu krajevi od e. Vrhovi su u prikazu grafa obično nacrtani tako da je graf nacrtan u ravnini i pri tome su vrhovi točke, a spajaju ih dužine ili krivulje koje predstavljaju bridove.[2]

Skup vrhova se obično označava s V, prema engleskoj riječi vertex za vrh.[3] Analogno, skup se označava i s N, prema engleskoj riječi node za čvor.

Ako su istog stupnja svi vrhovi nekog grafa, za taj graf kažemo da je regularan.[4]

Izvori

[uredi | uredi kôd]
  1. Sveučilište u Zagrebu, Geodetski fakultet, Zavod za kartografiju i fotogrametrijuArhivirana inačica izvorne stranice od 19. kolovoza 2019. (Wayback Machine) Nada Vučetić: OSNOVE GEOINFORMATIKE: Neki pojmovi i definicije iz teorije grafova, Osnove teorije skupova (pristupljeno 8. siječnja 2020.)
  2. Sveučilište J. J. Strossmayera u Osijeku - Odjel za matematiku Iva Gregurić: Bojenje grafova, Osijek, 2011., str. 4, pristupljeno 14. veljače 2020.
  3. ElementArhivirana inačica izvorne stranice od 27. veljače 2020. (Wayback Machine) Uvod u teoriju grafova: 1. Pojam grafa, str. 3, pristupljeno 28. veljače 2020.
  4. Sveučilište J. J. Strossmayera u Osijeku - Odjel za matematiku Iva Gregurić: Bojenje grafova, Osijek, 2011., str. 4, pristupljeno 30. travnja 2020.