Grafo dual

Grafo dual
El grafo G es dual del G', y viceversa.

En teoría de grafos, un grafo dual G' de un grafo planar G es un grafo que tiene un vértice por cada región de G, y una arista por cada arista en G uniendo a dos regiones vecinas.

Contenido

Propiedades

G' y G″ son duales de G, pero no isomorfos.
  • Si G' es el grafo dual de un grafo planar G, entonces G' también es un grafo planar (que puede tener bucles y aristas múltiples).
  • Si G' es el grafo dual de un grafo planar G, entonces el grafo dual de G' es G.
  • Si G es un grafo planar, entonces puede que no exista un único grafo dual para G, en el sentido que G puede tener grafos duales no-isomorfos, dependiendo de la distribución particular de los planos. En la figura, G′ y G″ no son isomorfos porque G′ tiene un nodo con grado 6 (la región exterior) que G″ no tiene (ver diagrama).

Grafo autodual

Un grafo autodual es aquel que es isomorfo a su dual.

Propiedades

Sean dos grafos planares G=(V,E) y G'=(V',E'), cuyos conjuntos de regiones son R y R' , respectivamente, entonces:

  • |E'| = |E|
  • |V'| = |R|
  • |R'| = |V|

Referencias

  • H. Whitney, Non-separable and planar graphs, Trans. Amer. Math. Soc. 34 (1932), 339–362.

Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Poliedro dual — Saltar a navegación, búsqueda El octaedro y el cubo son poliedros duales. Poliedro dual o conjugado, en geometría, es el poliedro cuyos vértices se corresponden con el centro de las cara del otro poliedro dado. El poliedro dual del dual es… …   Wikipedia Español

  • Coloración de grafos — Una vértice coloración propia del grafo de Petersen con 3 colores, el número mínimo posible. En Teoría de grafos, la coloración de grafos es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a elementos del …   Wikipedia Español

  • Cohomología de Čech — En matemáticas, específicamente la topología algebraica, la Cohomología de Čech es una teoría de cohomología basada en las propiedades de conjuntos abiertos y recubrimientos de espacio topológico. Se llama así por el matemático de la República… …   Wikipedia Español

  • Triangulación de Delaunay — Una triangulación de Delaunay /dəlo ne/, a veces escrito fonéticamente «Deloné», es una red de triángulos que cumple la condición de Delaunay. Esta condición dice que la circunferencia circunscrita de cada triángulo de la red no debe contener… …   Wikipedia Español

  • 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

  • Grammatik des Neugriechischen — Die Neugriechische Sprache ist in einer kontinuierlichen Entwicklung aus dem Altgriechischen hervorgegangen und bildet einen eigenen Zweig der Indogermanischen Sprachfamilie. Sie hat grammatisch einige ursprüngliche Merkmale dieser Sprachfamilie… …   Deutsch Wikipedia

  • Neugriechische Grammatik — Die Neugriechische Sprache ist in einer kontinuierlichen Entwicklung aus dem Altgriechischen hervorgegangen und bildet einen eigenen Zweig der Indogermanischen Sprachfamilie. Sie hat grammatisch einige ursprüngliche Merkmale dieser Sprachfamilie… …   Deutsch Wikipedia

  • Árbol de expansión — Un árbol de expansión (aristas azules gruesas) de un grafo de rejilla. En el campo matemático de la teoría de grafos, un árbol de expansión T de un grafo conexo, no dirigido G es un árbol compuesto por todos los vértices y algunas (quizá todas)… …   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

Compartir el artículo y extractos

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