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.

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. 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 $E=\{e_{1},e_{2},e_{3},e_{4},\dots ,e_{E}\}$ Graf G možemo definirati $G=(V,R)$, kao skup $V$ s relacijom $R\subseteq V\times V$. Elementi skupa V $v_{i}$ je obitelj točaka, tj. vrhovi ili čvorovi grafa, a elementi relacije $R$, tj. uređeni parovi $(v_{i},v_{j})$ nazivaju se bridovi, grane ili lukovi grafa, a to su spojnice među tim točkama.

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.

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.

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.

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.

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.

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

Šetnja je alternirajući niz vrhova i bridova.

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