Grafo universal

Grafo universal

En teoría de grafos, un grafo universal es un grafo infinito que contiene a todos los grafos finitos (o al menos numerables) como un subgrafo inducido. El primer grafo universal fue construido por R. Rado,[1] [2] actualmente llamado grafo de Rado o grafo aleatorio.

Trabajos más recientes[3] [4] se han enfocado en grafos universales para una familia de grafos particular F, correspondiente a aquella que contiene a todos los grafos finitos. Un grafo universal para una familia F de grafos también puede referirse a un miembro de una secuencia de grafos finitos que contiene a todos los grafos en F. Por ejemplo, cada árbol finito es un subgrafo de un grafo hipercubo suficientemente largo;[5] por lo tanto, un hipercubo puede decirse que es un grafo universal para los árboles.

En terminología matemática más antigua, la frase "grafo universal" fue a veces utilizada para denotar a los grafos completos.

Referencias

  1. ↑ Rado, R. (1964). «Universal graphs and universal functions» (en inglés). Acta Arithmetica 9:  pp. 331-340. 
  2. ↑ Radio, R. (1967). «Universal graphs» en A Seminar in Graph Theory. : 83-85, Holt, Reinhart, y Winston.
  3. ↑ Goldstern, Martin; Kojman, Menachem (1996). «Universal arrow-free graphs» (en inglés). Acta Math. Hungar 1973:  pp. 319–326. doi:10.1007/BF00052907. arΧiv:math.LO/9409206. 
  4. ↑ Cherlin, Greg; Shelah, Saharon; Shi, Niandong (1999). «Universal graphs with forbidden subgraphs and algebraic closure» (en inglés). Advances in Applied Math 22:  pp. 454-491. doi:10.1006/aama.1998.0641. arΧiv:math.LO/9809202. 
  5. ↑ Wu, A. Y (1985). «Embedding of tree networks into hypercubes» (en inglés). Journal of Parallel and Distributed Computing 2:  pp. 238-249. doi:10.1016/0743-7315(85)90026-7. 

Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • Anexo:Glosario de teoría de grafos — Grafo simple no dirigido, con 6 vértices y 7 aristas. A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal correspondiente. Todos los… …   Wikipedia Español

  • Glosario en teoría de grafos — Anexo:Glosario en teoría de grafos Saltar a navegación, búsqueda Grafo con 6 nodos A continuación se detallan los principales conceptos de la teoría de grafos. Para las definiciones formales o más detalladas, puede dirigirse al artículo principal …   Wikipedia Español

  • Grupo libre — grafo de Cayley del grupo libre de dos generadores, a y b. En teoría de grupos, un grupo G se dice libre si hay un subconjunto S de G, tal que todo elemento de G puede escribirse en una forma única como producto de finitos elementos de S y sus… …   Wikipedia Español

  • Teoría de grafos — Diagrama de un grafo con 6 vértices y 7 aristas. En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un… …   Wikipedia Español

  • Historiografía — Mujer escribiendo, de Johannes Vermeer. La historiografía, también denominada ciencia histórica …   Wikipedia Español

  • Teoría del orden — La teoría del orden es una rama de la matemática que estudia varias clases de relaciones binarias que capturan la noción intuitiva del orden matemático. Este artículo da una introducción detallada a este campo e incluye algunas de las… …   Wikipedia Español

  • Traducción automática mediante lengua intermedia — La traducción automática mediante lengua intermedia es una de las estrategias clásicas de traducción automática. La idea básica de este método indirecto de traducción es representar el texto inicial en una lengua intermedia abstracta e… …   Wikipedia Español

  • Teoría de categorías — En este artículo se detectaron los siguientes problemas: Necesita ser wikificado conforme a las convenciones de estilo de Wikipedia. Podría ser difícil de entender para lectores interesados en el tema. Por favor …   Wikipedia Español

  • Correspondencia matemática — Saltar a navegación, búsqueda Dados dos conjuntos: X e Y, y un Grafo f, que determina alguna Relación binaria entre algún elemento de X con algún elemento de Y, diremos que ese grafo: f, define una correspondencia entre X e Y, que representaremos …   Wikipedia Español

  • PSPACE-completo — En teoría de la complejidad computacional, la clase de complejidad PSPACE completo (PSPACE complete en inglés) es el subconjunto de los problemas de decisión en PSPACE y todo problema en PSPACE puede ser reducido a él en tiempo polinomial. Los… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”