Menor (teoria de grafos)
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.

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:
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
- ↑ Lovász (2006), p. 77;Wagner (1937a).
- ↑ Lovász (2006), theorem 4, p. 78;Robertson y Seymour (2004).
- ↑ 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
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- Pegg, Ed, Jr.(2002).«Book Review: The Colossal Book of Mathematics».Notices of the American Mathematical Society.49(9): 1084–1086.doi:10.1109/TED.2002.1003756..
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
- .
Referències
- Este artícul conté una traducció derivada de «Menor (teoría de grafos)» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.