Brid (teorija grafova)

Brid, grana, luk, matematički objekt iz teorije grafova.

Skup bridova se obično označava s E, prema engleskoj riječi edge za brid.^[1]

Graf je u gruboj definiciji skup objekata: vrhova, točaka ili čvorova koje povezuju bridovi odnosno crte (linije). Brid (grana, luk) spaja dva čvora i to je odnos koji definira graf. Ako vrhove povezuje brid, grafove se prikazuje crtanjem točaka za svaki vrh i povlačenjem luka između dvaju vrhova.^[2] U pojednostavljenoj definiciji grafa, sastoji se od skup čvorova (vrhova), skup grana (lukova, bridova; eng. edges, arcs) te pripadnih odnosa među njima. Skup grana označavamo obično s ${\displaystyle E=\{e_{1},e_{2},e_{3},e_{4},\dots ,e_{E}\}}$^[3] Graf G možemo definirati ${\displaystyle G=(V,R)}$, kao skup ${\displaystyle V}$ s relacijom ${\displaystyle R\subseteq V\times V}$. Elementi skupa V ${\displaystyle v_{i}}$ je obitelj točaka, tj. vrhovi ili čvorovi grafa, a elementi relacije ${\displaystyle R}$, tj. uređeni parovi ${\displaystyle (v_{i},v_{j})}$ nazivaju se bridovi, grane ili lukovi grafa, a to su spojnice među tim točkama.^[4]

Dva čvora incidentna s nekom granom jesu susjedni čvorovi. Ako dvije grane imaju zajednički čvor, to su susjedne grane. Ako grana ima samo jedan vrh, onda je to petlja.^[3]

Skup bridova u grafu obično se označava s E(G). Bridovi mogu biti usmjereni ili ne. Ako su grafu svi bridovi usmjereni, tad je graf usmjereni graf (digraf), u suprotnom je neusmjereni graf.^[2]

Za pravi graf uzima se da je neusmjeren i kod njega crta od točka u do točke v istovjetna je crti od v do točke u. Ako imamo usmjerenost, gdje brid može biti usmjeren od jednog vrha prema drugome, ta dva smjera nisu istovjetni i smatra ih se različitim bridovima (lukovima). Kod neusmjerenih grafova tada su dva vrha pridružena jednom bridu međusobno ravnopravna.^[2]

Ako brid počinje i završava u istom vrhu tad je on petlja. Postoji li brid i drugi brid kojima odgovaraju isti vrhovi (npr. početni i krajnji), brid je višestruk, odnosno ako su dva ili više bridova incidentni s istim parom vrhova, oni su višestruki. Da bi graf imao naziv jednostavnog, jedan od uvjeta je da između bilo koja dva vrha nema više od jednog brida, odnosno svaka dva vrha spojena su s najviše jednim bridom i nema petlji, tj. nema petlja ni dvije grane koje spajaju isti par čvorova. U takvom grafu svaki se brid može poistovjetiti s parom različitih vrhova. Brid povezuje dva vrha koje se tad naziva incidentnima tom bridu, odnosno brid je incidentan tim dvama vrhovima.^[2][5][6]

Stupanj vrha v u grafu G je broj bridova koji su incidentni s v, pri čemu se petlje broje dva puta. Konačan li je skup bridova E(G) konačan, tada je ukupni zbroj stupnjeva svih bridova jednak dvostrukom broju bridova. Ako postoji brid između vrhova u i v, vrhovi su susjedni.^[2]

Svakom se bridu može pridružiti realan broj, čime je graf proširen težinskom funkcijom i to je težinski graf.^[2] Ako grane (bridove, lukove) označimo s ${\displaystyle e_{1},e_{2},\dots }$, onda je težina grane w(e), npr. za granu ${\displaystyle e_{1}}$ to je ${\displaystyle w(e_{1})}$.^[6]

Šetnja je alternirajući niz vrhova i bridova.^[2]

Kod ravninskog grafa grane se sijeku samo u čvorovima, pri čemu je sve nacrtano na ravnini.^[6]

1. ↑ Element  Arhivirana 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.
2. ↑ ^{a b c d e f g} math.e, hrvatski matematički elektronički časopis Maja Fošner i Tomaž Kramberger: Teorija grafova i logistika br. 14, ISSN ISSN 1334-6083 (pristupljeno 23. prosinca 2019.)
3. ↑ ^{a b} Sveučilište u Zagrebu, Geodetski fakultet, Zavod za kartografiju i fotogrametriju  Arhivirana 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, str. 1 (pristupljeno 30. travnja 2020.)
4. ↑ Veleučilište u Rijeci  Arhivirana inačica izvorne stranice od 14. veljače 2021. (Wayback Machine) Osnove teorije grafova str. 5
5. ↑ Sveučilište J. J. Strossmayera u Osijeku - Odjel za matematiku Iva Gregurić: Bojenje grafova, Osijek, 2011., str. 5, pristupljeno 14. veljače 2020.
6. ↑ ^{a b c} Sveučilište u Zagrebu, Geodetski fakultet, Zavod za kartografiju i fotogrametriju  Arhivirana 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, str. 2 (pristupljeno 30. travnja 2020.) Pogreška u citiranju: nevaljala <ref> oznaka; ime "Vučetić2" definirano više puta s različitim sadržajem