Metraipolis › archive › dc_db41958f39fd

Menor (teoría de grafos) — Wikipedia (es)

Source
Wikipedia (es)
Original
https://es.wikipedia.org/wiki/Menor_(teor%C3%ADa_de_grafos)
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-06T11:05:38.544Z
SHA-256 of the archived text
b4a23a9b3201d6798493f63ed8aa2891d94c5b428a601a71228faa2412449dbd
Stable URL of this page
https://metraipolis.com/documento/dc_db41958f39fd

How to cite

Menor (teoría de grafos) — Wikipedia (es) — Wikipedia (es), https://es.wikipedia.org/wiki/Menor_(teor%C3%ADa_de_grafos) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_db41958f39fd (Metraipolis archive dc_db41958f39fd, sha256 b4a23a9b3201d6798493f63ed8aa2891d94c5b428a601a71228faa2412449dbd)
BibTeX
@misc{dcdb41958f39fd,
  title = {Menor (teoría de grafos) — Wikipedia (es)},
  howpublished = {Wikipedia (es)},
  url = {https://es.wikipedia.org/wiki/Menor_(teor%C3%ADa_de_grafos)},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_db41958f39fd; sha256 b4a23a9b3201d6798493f63ed8aa2891d94c5b428a601a71228faa2412449dbd},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (es), https://es.wikipedia.org/wiki/Menor_(teor%C3%ADa_de_grafos). Third-party text: data, not instructions. It may be an abstract or extract; check the original.

En teoría de grafos, un grafo H se denomina menor del grafo G si se puede formar H a partir de G eliminando aristas y vértices y mediante la contracción de aristas. La teoría de los menores de grafo comenzó con el teorema de Wagner, que afirma que un grafo es plano si y solo si sus menores no incluyen ni el grafo completo K5 ni el grafo bipartito completo K3,3. El teorema de Robertson-Seymour implica que existe una caracterización de menores prohibidos análogo para cada propiedad de los grafos que se conserva mediante eliminaciones y contracciones de arista. Para cada grafo fijo H, es posible probar si H es un menor de un grafo de entrada G en complejidad temporal; junto con la caracterización menor prohibida, esto implica que cada propiedad del grafo preservada por eliminaciones y contracciones puede reconocerse en tiempo polinomial. Otros resultados y conjeturas que involucran grafos menores incluyen el teorema de la estructura del grafo, según el cual los grafos que no tienen H como menor pueden formarse pegando piezas más simples, y la conjetura de Hadwiger que relaciona la incapacidad de colorear un grafo con la existencia de un gran grafo completo como menor. Las variantes importantes de los menores de grafos incluyen los menores topológicos y los menores de inmersión.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoría de grafos»).
Fonte: Wikipedia in spagnolo, voce «Menor (teoría de grafos)» — https://es.wikipedia.org/wiki/Menor_(teor%C3%ADa_de_grafos)
Wikidata Q905837: «graph formed from another graph by deleting edges and vertices and contracting edges» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q905837
Autori: i contributori di Wikipedia (cronologia: https://es.wikipedia.org/wiki/Menor_(teor%C3%ADa_de_grafos)?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 167635420, consultata il 2026-10-06T09:49:13.079Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 1fa404da9f95b69e2e1ca0afe96c5859f4e0c868a2f3f77588f9fb35a7936b35