Grafo

Índice

Introducción 2
Isomorfismo de grafos 3
Problema del isomorfismo de grafos 4
Conclusión: 5
Bibliografía: 5

Introducción
Es importante considerar diversos aspectos de losgrafos ya que nos ayuda a tener un análisis y facilitación de diversos valores en donde se genera un valor fundamental.
Cada una de los teoremas nos ayuda a tener mas amplio un conocimiento yclasificación de los circuitos, ya que nos facilita el procedimiento, pero se dividen en diferentes grafos como son: grafo isomorfo, un multígrafo es un grafo con varias aristas entre dos vértices, un pseudografoes un grafo en el que hay aristas (lazos) que tienen el mismo extremo, un digrafo es un grafo donde a cada arista se le indica un sentido mediante una flecha, los multidigrafos o pseudomultidigrafosson combinaciones de los anteriores, entre otros.
 

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 quepreserva 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 quese muestran a continuación son isomorfos:
Grafo G | Grafo H | Un isomorfismo
entre G y H |
| | f(a) = 1 f(b) = 6f(c) = 8f(d) = 3f(g) = 5f(h) = 2f(i) = 4f(j) = 7 |
Dos grafos con matrices deadyacencia respectivas A y B serán isomofos si y solo si existe una matriz permutación P tal que B = P A Pt.[]

Problema del isomorfismo de grafos
La determinación de si dos grafos con el mismo númerode 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! biyeccionesposibles 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...