Teoria de grafos

TEORÍA DE GRAFOS Y APLICACIONES

Página |1

MAESTRÍA:
Ingeniería de Sistemas

ASIGNATURA:
Teoría de Grafos y Aplicaciones

CATEDRÁTICO:
Dr. Julián Guadalupe Tapia Aguilar

TEMA:
Resumen Teoría de Grafos Isomorfismo

ALUMNO:

ISC Manuel David Moreno Carrillo

Villahermosa, Tabasco Septiembre 2010

TEORÍA DE GRAFOS Y APLICACIONES

Página |2

CONCEPTO COMPLEMENTARIO DEGRAFO Un grafo G es un conjunto ordenado finito triple, es decir contiene un conjunto no vacio de puntos u objetos llamados vértices o nodos (V), unidos por enlaces o trayectorias que se denominan aristas o lados (E) y una función de incidencia o relación () que asocia a cada E con un par no ordenado de V. En otras palabras, si e es una arista y u y v es un vértice de tal forma que G(e) = uv,entonces se dice que e está uniendo a u y v y con ello los vértices son llamados el fin de e. Con todo esto se pueden representar relaciones binarias entre elementos de un grupo o dicho redundantemente un conjunto. Podemos representar todo esto con la fórmula G = (V(G), E(G), G). CLASES DE GRAFOS Grafo Simple Es el grafo convencional compuesto de vértices y aristas, en las que estás última no poseenninguna dirección o ruta determinada, tanto puede ir de un lado como de otro pero solo de un modo, simplemente es una medio representativo del resultado de alguna función o grupo de variables en un grupo. V(G) = a,b,c,d E(G) = 1,2,3,4,5,6

G(e1) = ab/ba, G(e2) = ac/ca, G(e3) = bd/db G(e4) = ad/da, G(e5) = bc/cb, G(e6) = dc/cd
Grafo Múltiple o Multigrafo Dado que se tiene un grafo simple,un multígrafo se forma a partir de 2 o más aristas conectadas a un par de vértices que ya se encuentran enlazadas. Permite crear una nueva ruta en el trayecto de las aristas y de las funciones. V(G) = a,b,c,d E(G) = 1,2,3,4,5,6,7,8,9,10,11,12

G(e1) = ab/ba, G(e2) = ac/ca, G(e3) = bd/db, G(e4) = ad/da G(e5) = bc/cb, G(e6) = dc/cd, G(e7) = ab/ba, G(e8) = bc/cb G(e9) = cd/dc, G(e10) =da/ad, G(e11) = ac/ca, G(e12) = bd/db
Grafo Enlazado o Pseudografo Cuando la trayectoria de una arista, bajo una función o simple enlace requiere que se redirija a si misma este tipo de grafo se denomina pseudografo. El enlace resultante se conoce como bucle, ciclo o circuito por su forma. V(G) = a,b,c,d E(G) = 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16

G(e1) = ab/ba, G(e2) = ac/ca, G(e3) =bd/db, G(e4) = ad/da G(e5) = bc/cb, G(e6) = dc/cd, G(e7) = ab/ba, G(e8) = bc/cb G(e9) = cd/dc, G(e10) = da/ad, G(e11) = ac/ca, G(e12) = bd/db G(e13) = aa, G(e14) = bb, G(e15) = cc, G(e16) = dd

TEORÍA DE GRAFOS Y APLICACIONES

Página |3

Los anteriores son grafos no dirigidos, porque el trayecto puede tomarse desde cualquiera de sus vértices y no representan una secuencia demovimientos, en este caso su trayectoria se marca como camino simple. En caso de que una función o un resultado o evento genere un camino único se denominará a este grafo dirigido (dígrafo, multidigrafo o pseudodigrafo). Cuando un vértice es inicio y fin de un trayecto se llama cíclico a ese proceso, si al llegar al vértice continua hacia otro se denomina acíclico. En los grafos dirigidos se denominadapozo al vértice que indica el inicio de un trayecto y no tiene alguna flecha saliendo de ellos. GRADO DE UN GRAFO El grado en un grafo no dirigido se mide en cada vértice, o sea determina el número de aristas que lo unen o inciden con otro vértice (vecinos). La función para indicarlo se denota como (v) o gr(v). Todo grafo no dirigido tiene un número par de vértices de grado impar. Por ejemplo:gr(a) = 1 gr(b) = 3 gr(c) = 3 gr(d) = 3 gr(e) = 1 gr(f) = 0 gr(a) = 4 gr(b) = 4 gr(c) = 4 gr(d) = 4
Nota: no se consideran los bucles para la suma de grados

Aquellos que tienen grado cero se les conoce como aislados, y a aquellos que poseen solo un grado se les denominan colgante o de hoja. Expresado en fórmula esto es ???? ?? = 2??
??∈??

A esta fórmula también es conocida como el...