Kontrakcija brida (teorija grafova)

Izvor: Hrvatska internetska enciklopedija
Inačica 375508 od 9. prosinca 2021. u 17:28 koju je unio WikiSysop (razgovor | doprinosi) (Bot: Automatski unos stranica)
(razl) ←Starija inačica | vidi trenutačnu inačicu (razl) | Novija inačica→ (razl)
Skoči na:orijentacija, traži

Kontrakcija brida, operacija nad grafom u teoriji grafova. Kontrakcijom bridova uklanjanja se brid uz identifikaciju vrhova-krajeva tog brida. Nizom uklanjanja i kontraktiranja bridova i uklanjanja vrhova dolazi se do minore grafa [math]\displaystyle{ G }[/math]. Kod Petersenova grafa kontraktiranjem bridova incidentnih vrhovima vanjskog ciklusa, a koji ne pripadaju tom ciklusu, dobiva se minora [math]\displaystyle{ K_{5} }[/math]. Ako mu se ukloni središnji vrh i kontraktira brid incidentan svakom susjedu izbrisanog vrha, dobiva se minora [math]\displaystyle{ K_{3,3} }[/math].[1]

Izvori

  1. math.e Snježana Majstorović i Luka Boras: Petersenov graf, br. 27. (pristupljeno 25. svibnja 2020.)