Post on 15-Apr-2017
transcript
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Teorıa de grafosEstudios de Ingenierıa
Juan Gabriel Gomila
Frogames
juangabriel@frogames.es
10 de febrero de 2016
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Indice
1 Teorıa de grafosUn poco de historia
2 El concepto de grafoDefinicion geometrica del grafoDefinicion algebraica del grafo
3 Grafos y matricesRepresentacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matricesUn poco de historia
1 Teorıa de grafosUn poco de historia
2 El concepto de grafoDefinicion geometrica delgrafo
Definicion algebraica delgrafo
3 Grafos y matricesRepresentacion matricialIsomorfismo de grafosGrafos de Euler y grafos deHamilton
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matricesUn poco de historia
1 Teorıa de grafosUn poco de historia
2 El concepto de grafoDefinicion geometrica delgrafo
Definicion algebraica delgrafo
3 Grafos y matricesRepresentacion matricialIsomorfismo de grafosGrafos de Euler y grafos deHamilton
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matricesUn poco de historia
Origen de los grafos
La teorıa de grafos es una rama de la matematica que surge y sedesarrolla para dar soluciones a problemas muy concretos.El problema que la mayorıa de autores senalan como el origen de lateorıa de grafos es el problema de los puentes de Konigsberg
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matricesUn poco de historia
Origen de los grafos
Durante el siglo XVIII, la ciudad de Konigsberg (Prusia Oriental)estaba dividida en cuatro zonas por el rio Prevel. Habıa sietepuentes que comunicaban estas regiones como demuestra el dibujo:
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matricesUn poco de historia
Origen de los grafos
Los habitantes de la ciudad no tenıan ni BioFestes ni Univerlands,en lugar de tener vuestras mismas necesidades, necesitabanencontrar una manera de pasear por la ciudad que les permitiera ira una determinada region, cruzar cada puente una unica vez yvolver al lugar de partida.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matricesUn poco de historia
Origen de los grafos
Para resolver este problema, Euler represento las cuatro zonas de laciudad por cuatro puntos y los puentes por aristas que uniesen lospuntos, tal y como se ve en la figura:
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matricesUn poco de historia
Origen de los grafos
Actualmente, la teorıa de grafos se aplica dentro y fuera de lasmatematicas y sigue siendo un rama de investigacion muy activa.Sus aplicaciones son muy importantes en la ingenierıa y resultan degran utilidad para la representacion de datos, diseno de redes detelecomunicacion...
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
1 Teorıa de grafosUn poco de historia
2 El concepto de grafoDefinicion geometrica delgrafo
Definicion algebraica delgrafo
3 Grafos y matricesRepresentacion matricialIsomorfismo de grafosGrafos de Euler y grafos deHamilton
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
¿Que es un grafo?
Los grafos se pueden considerar formalmente como diagramas(representaciones geometricas) o bien algebraicamente como unpar de conjuntos (representacion algebraica). Veanse ambos tiposde definiciones:
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
1 Teorıa de grafosUn poco de historia
2 El concepto de grafoDefinicion geometrica delgrafo
Definicion algebraica delgrafo
3 Grafos y matricesRepresentacion matricialIsomorfismo de grafosGrafos de Euler y grafos deHamilton
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Definicion geometrica del grafo
Definicion
Geometricamente, un grafo G es un conjunto de puntos delespacio, algunos de los cuales estan unidos entre ellos mediantelıneas.
Este grafo puede simbolizar por ejemplo un mapa de carreterasdonde los puntos representan ciudades y las lıneas, las carreterasque las unen. En este caso, el grafo puede informar de las posiblescomunicaciones que existen entre las ciudades, pero este grafo Gtambien podrıa esquematizar un circuito electrico.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Definicion geometrica del grafo
Se ha de hacer constar que un grafo solo contiene informacionsobre la conectividad entre puntos y no da informacion geometricaen sentido euclıdeo (distancias, angulos...). Ası los siguientesdiagramas representan el mismo grafo.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
1 Teorıa de grafosUn poco de historia
2 El concepto de grafoDefinicion geometrica delgrafo
Definicion algebraica delgrafo
3 Grafos y matricesRepresentacion matricialIsomorfismo de grafosGrafos de Euler y grafos deHamilton
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Definicion algebraica del grafo
Definicion
Un grafo G se define como un par ordenado de conjuntosG = (V ,E ) = (V (G ),E (G )) donde:
V es un conjunto no vacıo de puntos V = {v1, v2, · · · , vn}denominados vertices, y
E es un conjunto de pares no ordenados de elementos de V ,denominados aristas
Si dos vertices u, v estan unidos por la misma arista, entoncesdıcese que son adyacentes y se representan por su arista por {u, v}En este caso tambien se dira que u y v son incidentes a la arista{u, v}
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Definicion algebraica de grafo
Para representar algebraicamente un grafo es necesario poderdistinguir los vertices y las aristas. Ası:
G = (V (G ),E (G ))
V = V (G ) = {v1, v2, v3, v4}; E = E (G ) = {e1, e2, e3, e4}Donde e1 = {v1, v2}, e2 = {v2, v3}, e3 = {v3, v4}, e4 = {v2, v4}
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Definicion algebraica de grafo
Definiciones
El numero de vertices del grafo G , |V (G )| se denomina elorden del grafo.
El numero de aristas del grafo G , |E (G )| se denomina eltamano del grafo.
Grafo trivial
Un grafo G es finito si |V (G )| y |E (G )| son finitos. Si un grafofinito tiene un vertice y no tiene ninguna arista, nos referiremos ael como grafo trivial (corresponde a un solo punto)
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Definicion algebraica de grafo
Ejemplo
El siguiente diagrama no corresponde a un grafo ya que contiene:
Aristas multiples: las aristas e4 y e5 se unen a los vertices v3 yv4 (multigrafo).
Bucles: la arista e6 une el vertice v2 con el mismo(pseudografo).
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Definicion algebraica de grafo
Ejemplo
Notese en este caso:
E (G ) = {e1 = {v1, v2}, e2 = {v2, v3}, e3 = {v1, v4},
e4 = {v3, v4}, e5 = {v3, v4}, e6 = {v2, v3}}
E (G ) no es un conjunto, ya que tiene elementos repetidos {v3, v4};es decir, las aristas e4 y e5 y la arista e6 comienzan y acaban en elmismo vertice.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Definicion algebraica de grafo
La definicion de grafo dada anteriormente se corresponde con ladefinicion que diversos autores dan de grafo simple. Y cuando sepermiten aristas multiples y/o bucles como los del ejemploanterior, se clasifica como grafo general.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Grafos dirigidos
Otro concepto que resulta util es el de digrafo o grafo dirigido.
Digrafo
Sea G un grafo simple (o grafo general). Si a cada arista se leasigna un sentido, se dira que es un digrafo.
Las aristas en estos casos son pares ordenados D1 6= D2.Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Grado de un vertice
Ariastas incidentes
Dıcese que una arista e es incidente con un vertice v si v esextremo de e.
Grado de un vertice
El grado de un vertice v , gr(v) es igual al numero de aristas queson incidentes con v .
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Grado de un vertice
Como cada arista es incidente a ambos vertices, se tiene elsiguiente resultado util:
Teorema
Sea G = (V ,E ) un grafo, V = {v1, v2, · · · , vn}, entonces la sumade los grados de los vertices de G es igual al doble del numero dearistas:
n∑i=1
gr(vi ) = 2|E |
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Grado de un vertice
Ejemplo
gr(v1) = 2 gr(v2) = 3 gr(v3) = 3 gr(v4) = 2
n∑i=1
gr(vi ) = 2 + 3 + 3 + 2 = 10 = 2 · 5 = 2|E |
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Grado de un vertice
Teorema
Un vertice es par o impar segun su grado sea par o impar.
Nota
El teorema anterior tamben es valido para grafos generales.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Grado de un vertice
Ejemplo
gr(v1) = 2 gr(v2) = 4 gr(v3) = 3 gr(v4) = 4
n∑i=1
gr(vi ) = 2 + 4 + 3 + 3 = 12 = 2 · 6 = 2|E |
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Grado de un vertice
Ejercicios
1 Dibujese, si es posible, un grafo con 5 vertices, de manera queel grado de cada vertice sea 3.
2 Dibujese, si es posible, un grafo con 5 vertices, de manera queel grado de cada vertice sea 2.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Caminoss
En un grafo que represente, por ejemplo, una red decomunicaciones es importante conocer la existencia de caminosque recorren todas las aristas o todos los vertices y que, en ciertamanera, sean los mas economicos. Para eso se van a ver lassiguientes definiciones basicas (la nomenclatura que se da aquı noes unica, hay autores que dan nombres diferentes):
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Caminos
Definicion
Un camino en un grafo G es una secuencia finita alternada devertices y aristas de G :
v0 → e1 = {v0, v1} → v1 → e2 = {v1, v2} · · · en = {vn−1, vn} → vn
v0, e1, v1, e2 · · · en, vnDonde cada arista tiene por extremo los vertices inmediatamenteprecedentes o siguientes de la secuencia. Por lo que el caminotambien se puede representar por la secuencia de verticesv0, v1, · · · , vn.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Caminos
Extremos del camino
Los vertices v0 y vn se denomina extremos del camino y se dice queel camino va de v0 a vn o que conecta v0 con vn.
Longitud del camino
La longitud del camino es el numero de aristas que contiene.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Caminos
Clasificacion de los caminos
Recorrido: camino sin aristas repetidas.
Camino simple: recorrido sin vertices repetidos excepto elprimero y el ultimo.
Camino cerrado: camino en el cual sus dos extremoscoinciden. Es decir, comienza y acaba en el mismo vertice. encaso contrario el camino es abierto.
Circuito: recorrido cerrado.
Ciclo: circuito que tambien es camino simple.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Caminos
Clasificacion de los caminos
Dado el grafo, clasifıquense los siguientes caminos:
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Caminos
Clasificacion de los caminosv2v3v4v5v2
v2v3v4v5
v6v2v3v4v5v2v1v6
v1v2v6v1
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Conectividad
Existen grafos en los cuales para cada par de vertices vi , vj hay, almenos, un posible camino que los conecta y otros casos en loscuales es imposible unir dos vertices dados.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Conectividad
Grafo conexo
Un grafo G dıcese conexo si existe un camino simple entrecualquier par de vertices vi , vj .En caso contrario, el grafo es no conexo y los vertices vi y vjpertenecen a diferentes componentes conexas del grafo. El numerode componentes conexos de un grafo se denota por K (G ).
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Definicion geometrica del grafoDefinicion algebraica del grafo
Conectividad
Ejemplo
G1 es un grafo conexo, mientras que G2 y G3 no lo son.K (G1) = 1,K (G2) = 2,K (G3) = 3.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Representacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
1 Teorıa de grafosUn poco de historia
2 El concepto de grafoDefinicion geometrica delgrafo
Definicion algebraica delgrafo
3 Grafos y matricesRepresentacion matricialIsomorfismo de grafosGrafos de Euler y grafos deHamilton
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Representacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
1 Teorıa de grafosUn poco de historia
2 El concepto de grafoDefinicion geometrica delgrafo
Definicion algebraica delgrafo
3 Grafos y matricesRepresentacion matricialIsomorfismo de grafosGrafos de Euler y grafos deHamilton
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Representacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
Representacion matricial de los grafos
Definicion
Sea G = (V ,E ) un grafo simple con V = {v1, v2, · · · , vn}. Sedefine su matriz de adyacencia como la matriz cuadrada:
A(G ) = (aij)n×n =
{1 si vi y vj son adyacentes0 en otro caso
Notese que A(G ) es una matriz simetrica y queaii = 0 ∀ i = 1, · · · , n.La matriz de adyacencia no es unica (depende de la ordenacion delos vertices).
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Representacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
Representacion matricial de los grafos
Definicion
Si G = (V ,E ) es un grafo general V = {v1, v2, · · · , vn}, sedefine A(G ) = (aij)n×n donde aij es el numero de aristas queunen vi con vj . Entonces, A(G ) es simetrica.
Si G = (V ,E ) es un digrafo V = {v1, v2, · · · , vn}, se defineA(G ) = (aij)n×n donde aij es el numero de aristas que unen vicon vj . Entonces, A(G ) no es simetrica.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Representacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
Representacion matricial de los grafos
Ejemplo
A(G ) =
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44
=
0 1 0 01 0 1 10 1 0 10 1 1 0
Con aij ∈ {0, 1} y aii = 0
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Representacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
Representacion matricial de los grafos
Ejemplo
A(G ) =
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44
=
0 1 0 11 1 1 00 1 0 21 0 2 0
En este caso aij puede ser mas grande que 1 ya que el grafo tienearistas multiples y aii 6= 0 (bucles)
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Representacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
Representacion matricial de los grafos
Teorema
Sea A(G ) la matriz de adyacencia de un grafo con n vertices.Entonces la entrada (i , j) de la matriz Am nos dara el numero decaminos de longitud m que conecten los vertices vi y vj .
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Representacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
Representacion matricial de los grafos
Ejemplo
Si se considera la matriz del ejemplo anterior:
A(G ) =
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44
=
0 1 0 01 0 1 10 1 0 10 1 1 0
Se tiene que:
A2(G ) =
1 0 1 10 3 1 11 1 2 11 1 1 2
; A3(G ) =
0 3 1 43 2 4 41 4 2 31 4 3 2
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Representacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
Representacion matricial de los grafos
Ejemplo
Considerese por ejemplo el elemento a14 de estas tres matrices.
El elemento a14 de A(G ) es cero, eso indica que no hayningun camino entre los vertices v1 y v4, pero eso no indicaque no se puedan conectar estos vertices.
El elemento a14 ∈ A2(G ) toma el valor 1, indicando ası queexiste un camino de longitud 2 que conecta v1 y v4. Estecamino sera: v1v2v4.
El elemento a14 ∈ A3(G ) toma el valor 1, entonces existe uncamino de longitud 3 que conecta v1 y v4. Este camino serav1v2v3v4.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Representacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
1 Teorıa de grafosUn poco de historia
2 El concepto de grafoDefinicion geometrica delgrafo
Definicion algebraica delgrafo
3 Grafos y matricesRepresentacion matricialIsomorfismo de grafosGrafos de Euler y grafos deHamilton
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Representacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
Isomorfismo de grafos
Definicion
Sean G (V ,E ) y G ′(V ′,E ′) dos grafos (o grafos generales sinbucles) y f : V −→ V ′ una aplicacion biyectiva tal que
{u, v} ∈ E ⇐⇒ {f (u), f (v)} ∈ E ′
Entonces se dira que f es un isomorfismo entre G y G ′ o que G yG ′ son grafos isomorfos.
En general no es facil determinar cuando dos grafos son o no sonisomorfos.Es claro que si dos grafos son isomorfos han de tener el mismonumero de vertices e igual numero de aristas, pero eso no essuficiente.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Representacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
Isomorfismo de grafos
Teorema
Si G y G ′ son grafos isomorfos, entonces:
si v ∈ V =⇒ gr(v) = gr(f (v))
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Representacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
Isomorfismo de grafos
Ejemplo
G y G ′ tienen el mismo numero de vertices y el mismo numero dearistas.∀ v ∈ V (G ), gr(v) = 2, pero en cambio gr(w3) = 1, por tanto Gy G ′ no pueden ser isomorfos.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Representacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
1 Teorıa de grafosUn poco de historia
2 El concepto de grafoDefinicion geometrica delgrafo
Definicion algebraica delgrafo
3 Grafos y matricesRepresentacion matricialIsomorfismo de grafosGrafos de Euler y grafos deHamilton
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Representacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
Grafos de Euler
Definicion
Sea G un grafo conexo
Un camino euleriano es un recorrido en el cual aparecen todaslas aristas.
Un circuito euleriano es un camino euleriano cerrado.
Un grafo euleriano es un grafo con un circuito euleriano.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Representacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
Grafos de Euler
Teorema
Sea G un grafo entonces:
Si G tiene un circuito euleriano, el grado de cada vertice espar.
Si G tiene un camino euleriano, el grafo G tiene exactamentedos vertices de grado impar (exactamente los vertices dondecomienza y acaba el camino).
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Representacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
Grafos de Euler
Ejemplos
Considerese el grafo siguiente:
La secuencia e2 e4 e5 e8 e1 e7 e3 e6 es un camino euleriano.
gr(v1) = 3, gr(v2) = 3, gr(v3) = 4, gr(v4) = 2, gr(v5) = 4
Teniendo dos vertices de grado 3, el camino comienza en uno deellos y acaba en el otro.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Representacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
Grafos de Euler
Ejemplo
Considerese el grafo que representa los puentes de Konigsberg.
Se observa que a, c y d tienen grado 3 y que b tiene grado 5.Como todos los vertices tienen grado impar se puede deducir queno existe ningun circuito euleriano. Por tanto el problema de lospuentes de Konigsberg no tiene solucion.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos
Teorıa de grafosEl concepto de grafo
Grafos y matrices
Representacion matricialIsomorfismo de grafosGrafos de Euler y grafos de Hamilton
Grafos de Hamilton
Definicion
Sea G un grafo:
Un camino de Hamilton es un camino que recorre todos losvertices solo una vez.
Un circuito de Hamilton es un camino de Hamilton cerrado(recorre todos los vertices solo una vez salvo los extremos).
Un grafo con un circuito de Hamilton se denomina un grafode Hamilton.
Juan Gabriel Gomila Tema 8 - Introduccion a la Teorıa de Grafos