Petlja (teorija grafova)

Izvor: Hrvatska internetska enciklopedija
Skoči na:orijentacija, traži

Petlja, matematički objekt iz teorije grafova. Vrsta je brida.[1]

Graf je u gruboj definiciji skup objekata: vrhova, točaka ili čvorova koje povezuju bridovi odnosno crte (linije). Brid 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.[1]

Ako brid počinje i završava u istom vrhu tad je on petlja, [1] odnosno to je brid koji je incidentan samo s jednim vrhom.[2]

Ako je grana s jednim vrhom, onda je to petlja.[3]

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

Izvori

  1. 1,0 1,1 1,2 1,3 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.)
  2. Sveučilište J. J. Strossmayera u Osijeku - Odjel za matematiku Iva Gregurić: Bojenje grafova, Osijek, 2011., str. 5, pristupljeno 14. veljače 2020.
  3. Sveučilište u Zagrebu, Geodetski fakultet, Zavod za kartografiju i fotogrametriju Nada Vučetić: OSNOVE GEOINFORMATIKE: Neki pojmovi i definicije iz teorije grafova, Osnove teorije skupova, str. 1 (pristupljeno 30. travnja 2020.)