Minor (grafentheorie)
In de grafentheorie, een onderdeel van de wiskunde, is een minor van een graaf  een graaf die uit  kan worden voortgebracht door knopen te verwijderen, zijden te verwijderen, of zijden samen te trekken. Minoren spelen een belangrijke rol bij het karakteriseren van eigenschappen van grafen, zoals planariteit.

Definitie 
Een graaf  is een minor van een graaf  als het mogelijk is  uit  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  als  een minor van  is.

Zoals uit de definitie blijkt, is elke subgraaf van  ook een minor van , maar andersom is dat niet het geval: door een zijde samen te trekken ontstaat meestal geen subgraaf van de oorsprongsgraaf.

Voorbeeld 
Beschouw de grafen  en :

: 

: 

 is een minor van : 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 relatie  is een welpreorde op isomorfieklassen van grafen. Dat betekent dat:
  reflexief en transitief is;
 er geen oneindig afdalende ketens  bestaan; en
 er geen oneindige antiketens  bestaan waarbij, voor , zowel  als .

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

Het feit dat  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 de verboden minoren een minor zijn van de gegeven graaf, dan heeft die graaf de eigenschap niet. 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 , de volledige graaf met vijf knopen, en , 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)

Grafentheorie