Kontrakcija brida (teorija grafova)

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 . Kod Petersenova grafa kontraktiranjem bridova incidentnih vrhovima vanjskog ciklusa, a koji ne pripadaju tom ciklusu, dobiva se minora . Ako mu se ukloni središnji vrh i kontraktira brid incidentan svakom susjedu izbrisanog vrha, dobiva se minora .[1]

Izvori

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