Minor (grafentheorie)

In de grafentheorie, een onderdeel van de wiskunde, is een minor van een graaf $G$ een graaf die uit $G$ kan worden voortgebracht door knopen te verwijderen, zijden te verwijderen, of zijden samen te trekken. De grafen kunnen ongerichte maar ook gerichte grafen zijn.

Minoren spelen een belangrijke rol bij het karakteriseren van eigenschappen van grafen, zoals planariteit.

Definitie

Een graaf $M$ is een minor van een graaf $G$ als het mogelijk is $M$ uit $G$ te verkrijgen door een willekeurig aantal keer een van de volgende bewerkingen uit te voeren:

• Verwijderen van een zijde: een zijde wordt uit de graaf verwijderd.
• Verwijderen van een knoop: een knoop die niet meer aan een zijde verbonden is wordt uit de graaf verwijderd.
• Samentrekken van een zijde: een zijde wordt uit de graaf verwijderd en diens eindpunten worden tot één knoop samengevoegd.

We schrijven in dit artikel $M\preceq G$ als $M$ een minor van $G$ is.

Zoals uit de definitie blijkt, is elke deelgraaf van $G$ ook een minor van $G$. We kunnen immers met de eerste twee regels alle knopen en zijden die niet tot de deelgraaf behoren verwijderen. Andersom is dat echter niet het geval: door een zijde samen te trekken ontstaat meestal geen deelgraaf van de oorsprongsgraaf.

Voorbeeld

Beschouw de grafen $M$ en $G$:

$M$:

$G$:

$M$ is een minor van $G$: hij ontstaat door eerst de in de volgende afbeelding gestippelde zijden en de daardoor ontstane geïsoleerde knoop te verwijderen, en vervolgens de grijze zijde samen te trekken.

Eigenschappen

De Amerikaan Neil Robertson en de Brit Paul Seymour hebben in een aantal artikelen van bij elkaar meer dan 500 bladzijden tussen 1983 en 2004 bewezen dat de minordening op isomorfieklassen van grafen een welpreorde is. Dat betekent dat:

• $\preceq$ reflexief en transitief is;
• er geen oneindig afdalende ketens $G_{0}\succeq G_{1}\succeq G_{2}\succeq \cdots$ bestaan; en
• er geen oneindige antiketens $G_{0},G_{1},\ldots$ bestaan waarbij, voor $i\neq k$, zowel $G_{i}\not \preceq G_{k}$ als $G_{k}\not \preceq G_{i}$.

Toepassingen

Gegeven een vaste graaf $M$ is het mogelijk in polynomiale tijd te beslissen of $M$ een minor is van een invoergraaf $G$.

Het feit dat $\preceq$ een welpreorde is, maakt het mogelijk graafeigenschappen die gesloten zijn onder de minor-operaties te karakteriseren met behulp van een eindig aantal verboden minoren: als een van de verboden minoren een minor is van de gegeven graaf, dan heeft die graaf de eigenschap niet, en andersom, als geen van de verboden minoren een minor is van de gegeven graaf, dan heeft die graaf de eigenschap wel. Samen met het hierboven genoemde resultaat betekent dat, dat het mogelijk is in polynomiale tijd te beslissen of een graaf die eigenschap heeft.

Een van de eigenschappen die gesloten is onder de minor-operaties is planariteit. Al in 1937 bewees Klaus Wagner dat een graaf planair is dan en slechts dan als $K_{5}$, de volledige graaf met vijf knopen, en $K_{3,3}$, de volledige bipartiete graaf met twee keer drie knopen, geen minoren ervan zijn (dit resultaat is verwant, maar niet gelijk aan, de beter bekende stelling van Kuratowski).

Referenties

• Graph Theory, J.A. Bondy, U.S.R. Murty, Springer 2008
• Graph Minor op MathWorld (geraadpleegd: 14 april 2022)
• Graph Minors XX. Wagner's Conjecture. N. Robertson, P.D. Seymour, Journal of Combinatorial Theory, Series B, Volume 92, Issue 2. Elsevier, 2004.