En teoría de grafos, un grafo dualG' de un grafo planarG 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.
Si G' es el grafo dual de un grafo planar G, entonces G' también es un grafo planar (que puede tener bucles y ser un multigrafo, es decir, tener 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.
Datos:Q2294516
Multimedia:Dual graphs
Agosto 17, 2021
grafo, dual, teoría, grafos, grafo, dual, grafo, planar, grafo, tiene, vértice, cada, región, arista, cada, arista, uniendo, regiones, vecinas, grafo, dual, viceversa, Índice, propiedades, grafo, autodual, propiedades, referenciaspropiedades, editar, duales, p. En teoria de grafos un grafo dual G de un grafo planar G es un grafo que tiene un vertice por cada region de G y una arista por cada arista en G uniendo a dos regiones vecinas El grafo G es dual del G y viceversa Indice 1 Propiedades 2 Grafo autodual 2 1 Propiedades 3 ReferenciasPropiedades Editar G y G son duales de G pero no isomorfos Si G es el grafo dual de un grafo planar G entonces G tambien es un grafo planar que puede tener bucles y ser un multigrafo es decir tener aristas multiples 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 unico grafo dual para G en el sentido que G puede tener grafos duales no isomorfos dependiendo de la distribucion particular de los planos En la figura G y G no son isomorfos porque G tiene un nodo con grado 6 la region exterior que G no tiene ver diagrama Grafo autodual EditarUn grafo autodual es aquel que es isomorfo a su dual Propiedades Editar 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 EditarH Whitney Non separable and planar graphs Trans Amer Math Soc 34 1932 339 362 Datos Q2294516 Multimedia Dual graphsObtenido de https es wikipedia org w index php title Grafo dual amp oldid 120662020, wikipedia, wiki, leyendo, leer, libro, biblioteca,
