Minora (teorija grafova)

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

Minora, vrsta grafa iz teorije grafova. Minora nekog grafa [math]\displaystyle{ G }[/math] graf dobiven nizom uklanjanja i kontraktiranja bridova i uklanjanja vrhova.[1]

Petersenov graf sadrži minore [math]\displaystyle{ K_{5} }[/math] i [math]\displaystyle{ K_{3,3} }[/math]. [1] Wagnerov teorem iz 1937. godine kaže da "Graf [math]\displaystyle{ G }[/math] je ravninski ako i samo ako mu ni [math]\displaystyle{ K_{5} }[/math] ni [math]\displaystyle{ K_{3,3} }[/math] nisu minore." [1]

Izvori

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