Metraipolis › archive › dc_edfe4b949bc8
Grafo de distancias unitarias — Wikipedia (es)
- Source
- Wikipedia (es)
- Original
- https://es.wikipedia.org/wiki/Grafo_de_distancias_unitarias
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T23:29:52.978Z
- SHA-256 of the archived text
0c74eea3acf5791c2aecc3199348543c36fb07d76fb0876ffa0dd482b9f2e977- Stable URL of this page
https://metraipolis.com/documento/dc_edfe4b949bc8
How to cite
Grafo de distancias unitarias — Wikipedia (es) — Wikipedia (es), https://es.wikipedia.org/wiki/Grafo_de_distancias_unitarias (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_edfe4b949bc8 (Metraipolis archive dc_edfe4b949bc8, sha256 0c74eea3acf5791c2aecc3199348543c36fb07d76fb0876ffa0dd482b9f2e977)
BibTeX
@misc{dcedfe4b949bc8,
title = {Grafo de distancias unitarias — Wikipedia (es)},
howpublished = {Wikipedia (es)},
url = {https://es.wikipedia.org/wiki/Grafo_de_distancias_unitarias},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_edfe4b949bc8; sha256 0c74eea3acf5791c2aecc3199348543c36fb07d76fb0876ffa0dd482b9f2e977},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (es), https://es.wikipedia.org/wiki/Grafo_de_distancias_unitarias. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
En matemáticas, particularmente en teoría geométrica de grafos, un grafo de distancias unitarias es aquel formado a partir de una colección de puntos en el plano, de manera que la distancia entre dos puntos directamente conectados entre sí sea siempre exactamente uno. Para distinguir estos grafos de una definición más amplia que permite que algunos pares de vértices no adyacentes estén a distancia uno, también se les puede llamar grafos de distancia unitaria estricta o grafos de distancia unitaria fiel. Como familia hereditaria de grafos, se pueden caracterizar mediante subgrafos inducidos prohibidos. Los grafos de distancia unitaria incluyen el grafo cactus, los grafos de cerillas y los grafos de peniques, así como el grafo hipercubo. Los grafos de Petersen generalizados son grafos de distancia unitaria no estricta. Un problema planteado por Paul Erdős, conocido como el problema de la distancia unitaria, pide hallar el número máximo posible de pares de distancia unitaria determinados por n {\displaystyle n} puntos en el plano euclídeo. De forma equivalente, solicita el número máximo de aristas en un grafo de distancia unitaria con n {\displaystyle n} vértices. El mejor límite superior conocido es O ( n 4 / 3 ) . {\displaystyle O(n^{4/3}).} . El mejor límite inferior conocido es Ω ( n 1.014 ) {\displaystyle \Omega (n^{1.014})} (para n ) {\displaystyle n)} suficientemente grande). El número de colores necesarios para colorear T grafos de distancia unitaria también es desconocido. En el problema de Hadwiger-Nelson equivalente para el plano, algunos grafos de distancia unitaria requieren cinco colores, y cada grafo de distancia unitaria puede colorearse con siete colores. Para cada número algebraico α , {\displaystyle \alpha ,} existe un grafo de distancia unitaria con dos vértices que deben estar a una distancia α . {\displaystyle \alpha .} Según el teorema de Beckman-Quarles, las únicas transformaciones del plano que preservan todos los grafos de distancia unitaria son isometrías. Es posible construir un grafo de distancia unitaria de manera eficiente, dados sus puntos. Encontrar todas las distancias unitarias tiene aplicaciones en búsqueda de patrones, donde puede ser un primer paso para encontrar copias congruentes de patrones más grandes. Sin embargo, determinar si un grafo dado puede representarse como un grafo de distancia unitaria es NP difícil, y más específicamente completo para la teoría existencial de los números reales.
Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoría de grafos»).
Fonte: Wikipedia in spagnolo, voce «Grafo de distancias unitarias» — https://es.wikipedia.org/wiki/Grafo_de_distancias_unitarias
Wikidata Q745378 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q745378
Autori: i contributori di Wikipedia (cronologia: https://es.wikipedia.org/wiki/Grafo_de_distancias_unitarias?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 174698642, consultata il 2026-10-07T23:08:54.938Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: ec327c7a9068faa55f197d58d5031421f73f7c225d44818818510a00a15840fd