Isomorfismo de grafos

Isomorfismo de grafos

En teoría de grafos, un isomorfismo entre dos grafos G y H es una biyección f entre los conjuntos de sus vértices  f: V(G) \rightarrow V(H) que preserva la relación de adyacencia. Es decir, cualquier par de vértices u y v de G son adyacentes si y solo si lo son sus imágenes, f(u) y f(v), en H.

A pesar de su diferente aspecto, los dos grafos que se muestran a continuación son isomorfos:

Grafo G Grafo H Un isomorfismo
entre G y H
Graph isomorphism a.svg Graph isomorphism b.svg f(a) = 1

f(b) = 6

f(c) = 8

f(d) = 3

f(g) = 5

f(h) = 2

f(i) = 4

f(j) = 7

Dos grafos con matrices de adyacencia respectivas A y B serán isomofos si y solo si existe una matriz permutación P tal que B = P A Pt.[1]

Problema del isomorfismo de grafos

La determinación de si dos grafos con el mismo número de vértices n y aristas m son isomorfos o no se conoce como el problema del isomorfismo de grafos. Este problema admite un ataque por fuerza bruta que exigiría comprobar si las n! biyecciones posibles preservan la adyacencia, pero no se conoce un algoritmo eficiente, al menos para el caso general. En este contexto, eficiencia debe interpretarse como crecimiento del número de pasos inferior a O(en).

El problema del isomorfismo de grafos presenta una curiosidad en teoría de complejidad computacional al ser uno de los pocos problemas citados por Garey y Johnson en 1979 pertenecientes a NP de los que se desconoce si es resoluble en tiempo polinómico o si es NP-completo (actualmente está en revisión la demostración de que el problema está en P).[2]

Referencias

  1. Jonathan L. Gross, Jay Yellen.Handbook of Graph Theory. CRC Press, 2004. ISBN 158488090
  2. *Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 978-0716710455, OCLC 11745039 

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Problema de isomorfismo de subgrafos — Saltar a navegación, búsqueda En complejidad computacional, el Problema de isomorfismo de subgrafos, también a veces llamado Problema de matching de subgrafos, es un problema de decisión NP completo, que formalmente, se define de la siguiente… …   Wikipedia Español

  • Homeomorfismo de grafos — Este término no debe confundirse con isomorfismo de grafos. En Teoría de grafos, decimos que dos grafos G1 y G2 son homeomorfos si ambos pueden obtenerse a partir de un mismo grafo por una sucesión de subdivisiones elementales de aristas. Suele… …   Wikipedia Español

  • Vértice (teoría de grafos) — Para otros usos de este término, véase vértice. Un grafo con 6 vértices y 7 aristas. En teoría de grafos, un vértice o nodo es la unidad fundamental de la que están formados los grafos. Un grafo no dirigido está formado por un conjunto de… …   Wikipedia Español

  • Árbol (teoría de grafos) — Para otros usos de este término, véase Árbol (desambiguación). Árbol Árbol etiquetado con 6 vértices y 5 aristas. El único camino simple que conecta los vértices 2 y 6 es 2 4 5 6 …   Wikipedia Español

  • Base de datos orientada a grafos — Saltar a navegación, búsqueda Las bases de datos orientadas a grafos (BDOG) representan la información como nodos de un grafo y sus relaciones con las aristas del mismo, de manera que se pueda usar teoría de grafos para recorrer la base de datos… …   Wikipedia Español

  • Clase de isomorfismo — Una clase de isomorfismo es una colección de objetos matemáticos isomorfos con cierto objeto matemático. Un objeto matemático consiste generalmente en un conjunto y algunas relaciones matemáticas y operaciones definidas sobre este conjunto. A… …   Wikipedia Español

  • Clase de isomorfismo — Una clase de isomorfismo es una colección de objetos matemáticos isomorfos con cierto objeto matemático. Un objeto matemático consiste generalmente en un conjunto y algunas relaciones matemáticas y operaciones definidas sobre este conjunto. A… …   Enciclopedia Universal

  • NP-completo — En teoría de la complejidad computacional, la clase de complejidad NP completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP completo. Se puede decir que los… …   Wikipedia Español

  • Grafo autocomplementario — El estilo de esta traducción aún no ha sido revisado por terceros. Si eres hispanohablante nativo y no has participado en esta traducción puedes colaborar revisando y adaptando el estilo de ésta u otras traducciones ya acabadas …   Wikipedia Español

  • Complejidad computacional — Saltar a navegación, búsqueda La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica, los recursos requeridos durante el cómputo de un algoritmo para resolver un problema. Los recursos… …   Wikipedia Español

Compartir el artículo y extractos

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