En teoria de grafos, un grafo H es denomina menor del grafo G si es pot formar H a partir de G eliminant arestes i vèrtiços i per mig de la contracció d'arestes.

En el costat esquerre, es mostra el grafo complet en tres vèrtiços K3. És creat per contracció d'arestes a partir del grafo IK3, que a la seua volta està contingut en Y. Llavors K3 és un menor de Y

La teoria dels menors de grafo va començar en el teorema de Wagner, que afirma que un grafo és pla si i solament si els seus menors no inclouen ni el grafo complet K5 ni el grafo bipartito complet K3,3.[1] El teorema de Robertson-Seymour implica que existix una caracterisació de menors prohibits anàlec per a cada propietat dels grafos que es conserva per mig d'eliminacions i contracció d'aresta.[2]

Per a cada grafo fix H, és possible provar si H és un menor d'un grafo d'entrada G en complexitat temporal; junt en la caracterisació menor prohibida, açò implica que cada propietat del grafo preservada per eliminacions i contracció pot reconéixer-se en temps polinomial.

Atres resultats i conjectura que involucren grafos menors inclouen el teorema de l'estructura del grafo, segons el qual els grafos que no tenen H com a menor poden formar-se pegant peces més simples, i la conjectura de Hadwiger que relaciona l'incapacitat de colorear un grafo en l'existència d'un gran grafo complet com a menor. Les variants importants dels menors de grafos inclouen els menors topològics i els menors d'immersió.

Definicions

Una contracció d'aresta és una operació que elimina una aresta d'un grafo mentres fusiona simultàneament els dos vèrtiços que estava conectant. Un grafo H és un menor d'un atre grafo no dirigit G si es pot obtindre un grafo isomorfo a H de partir de G contraent algunes arestes, eliminant algunes arestes i eliminant alguns vèrtiços aïllats. L'orde en que es realisa una seqüència de dites contracció i eliminacions en G no afecta al grafo resultant H.

Els grafos menors a sovint s'estudien en el context més general dels menors matroides. En este context, és comú supondre que tots els grafos estan conectats, estant permesos bucles i arestes múltiples (és dir, són multigrafos en lloc de grafos simples); la contracció d'un bucle i l'eliminació d'una aresta de tall són operacions prohibides. Este punt de vista té la ventaja de que les eliminacions d'aresta deixen el ranc d'un grafo sense canvis, i les contracció d'aresta sempre reduïxen el ranc en un.

En atres contexts (com en l'estudi de pseudobosques) té més sentit permetre l'eliminació d'una aresta de tall i permetre grafos desconectats, pero prohibir els multigrafos. En esta variació de la teoria de grafos menors, un grafo sempre se simplifica despuix de qualsevol contracció d'aresta per a eliminar els seus bucles propis i arestes múltiples.[3]

Una funció f es denomina monòtona menor si, sempre que H siga menor de G, es té que f(H) ≤ f(G).

Eixemple

En el següent eixemple, el grafo H és menor del grafo G:

H. 

G.  


El següent diagrama ilustra açò. Primer es construïx un subgrafo de G eliminant les arestes discontínues (i el vèrtiç aïllat resultant), i després es contrau l'aresta grisa (fusionant els dos vèrtiços que conecta):

 

Vore també

Notes

  1. ↑ Lovász (2006), p. 77;Wagner (1937a).
  2. ↑ Lovász (2006), theorem 4, p. 78;Robertson y Seymour (2004).
  3. ↑ Lovász (2006) is inconsistent about whether to allow self-loops and multiple adjacencies: he writes on p. 76 that "parallel edges and loops llaure allowed" but on p. 77 he states that "a graph is a forest if and only if it does not contain the triangle K3 as a minor", true only for simple graphs.

Referències


Referències