Circuito de euler

Definición. Sea G un grafo sin vértices aislados. Un circuito que contiene todas las aristas de G recibe el nombre de circuito euleriano. Un circuito euleriano es una trayectoria que empieza y termina en el mismo vértice y recorre cada arista exactamente una vez.  

Condiciones a saber si un grafo es un circuito  euler.

1) Un grafo no dirigido G tiene un paseo de Euler si y solo si tiene cero o dos vértices de valencia impar.

2) Si un grafo no dirigido G tiene un circuito de Euler entonces todo vértice de G tiene valencia par, además de ser conexo.

3) Si G es un grafo no dirigido con vértices {v1, v2, ..., vn} y la suma (v1), (v2), ..., (vn) es par, entonces el grafo tiene un circuito de Euler.

4) Un grafo G tiene un camino de Euler de v w si y solo si v y w son los únicos vértices de valencia impar.

EJEMPLOS:

(a) No lo admite porque v4 es un vértice aislado.
(b) No lo admite porque cualquier ciclo utilizará la arista e1 dos veces. 
(c) El circuito v1 e1 v2 e2 v1 es euleriano. 
(d) El circuito v3 e3 v1 e1 v2 e2 v3 es euleriano. 
(e) No admite ningún circuito euleriano. 
(f) v1 e1 v2 e2 v3 e3 v4 e4 v2 e5 v5 e6 v1 es un circuito euleriano. 

Ejercicio:
Demostrar si existe un circuito euler o no en el siguiente grafo.

siguiendo los siguientes puntos se veran que el rafo si contiene un circuito euler.

Camino euler: a,b,d,e,b,c,e,f,c,a

Referencias:

https://www.dc.uba.ar/materias/aed3/2013/1c/teorica/algo3_teo_euleriano.pdf

Teoria de grafos

Los grafos son representaciones de las redes, y por medio de ellos se pueden expresar en forma visual y sencilla la relación entre elementos de distinto tipo, por ejemplo se pueden usar para representar la estructura de una empresa en lo que se conoce como “organigrama”, o bien para modelar una red eléctrica, telefónica, de carreteras, de agua potable, de alcantarillado, etc.



-Una gráfica (o gráficas no dirigidas) "G" consisten en un conjunto "V" de vértices (o nodos) y un conjunto de aristas (o arcos) tal cual aristas e se asocia con un par no ordenado de vértices.

Si existe una arista única e asociada con los vértices "U" y "W". se escribe e = (V,W)  ó    e=(V,W).en este contexto (V,W) denota una arista entre "V" y "W" en una gráfica no dirigida y no es un par ordenado.

-Una gráfica dirigida (o digrafica) "G" Consiste en un Conjunto "V" de vértices (o nodos)  y un conjunto "E" de aristas (o arcos) tales que cada arista e "E" esta asociada con un par ordenado de vértices.

Si hay una arista única e asociada con el par ordenado (V,W) de vértices se escribe así e = (V,W) que denota una arista de "V" a  "W"

Vértices (nodos)
Se indican por medio de un pequeño círculo y se les asigna un número o letra. En el grafo anterior los vértices son V= {a,b,c,d}.

Lados (ramas o aristas)
Son las líneas que unen un vértice con otro y se les asigna una letra, un numero o una combinación de ambos. En el grafo anterior los lados son: L= {1, 2, 3, 4, 5, 6}.

Lados paralelos
Son aquellas aristas que tienen relación con un mismo par de vértices. En el grafo anterior los lados paralelos son: P={2,3}.

Lazo
Es aquella arista que sale de un vértice y regresa al mismo vértice. En el grafo anterior se tiene el lazo: A= {6}

Valencia de un vértice
Es el numero de lados que salen o entran a un vértice. En el grafo anterior las valencias de los vértices son:

Valencia (a)=2
Valencia (b)=4
Valencia (c)=2
Valencia (d)=3

Hay que observar como en el caso del vértice del lazo solo se considera una vez, entrada o salida pero no ambos.

EJERCICIO!


En un torneo. El nieve, venció a los Faisanes 1 vez. El Rascacielos venció al Tuna 1 vez. El nieve venció al Rascacielos 2 veces. Los Faisanes al Tuna 1 vez y al Rascacielos también 1 vez.

Realice los ejercicios del 1 al 4 y describa el tipo de grafica (No dirigida, Dirigida, Simple)

1.- Dibujar un vértice si hubo un partido.
2.- Dibujar un vértice por cada partido.
3.- Dibujar un vértice si hubo una victoria.
4.- Dibujar un vértice por cada victoria.

1.-

2-

3.-

4.-

Referencias:

http://campus.cva.itesm.mx/nazira/Tc1003/PDF/TODO/0701_Tc1003_TODO_Grafos.pdf

Ciclo De Hamilton

Los caminos o ciclos hamiltonianos se llaman así en honor de William Rowan Hamilton, inventor de un juego que consistía en encontrar un ciclo hamiltoniano en las aristas de un grafo de un dodecaedro. Hamilton resolvió este problema usando cuaterniones, aunque su solución no era generalizable a todos los grafos.

Definición: Un circuito o ciclo hamiltoniano es un ciclo simple que contiene todos los vértices de G. Un circuito hamiltoniano es una trayectoria que empieza y termina en el mismo vértice y pasa por cada vértice una sola vez. 

Ejemplos y Ejercicio: ¿Cuál de los grafos siguientes admite un circuito hamiltoniano? 

Solución:
-(a) No admite circuitos hamiltonianos. El razonamiento es el siguiente: Si se empieza en v1, v2, v3, v4 y si se está en los demás vértices, en el v5 se estará dos veces. Si se empieza en v5, para luego ir a los vértices v1 o v4 ó a v3 o v2 respectivamente, se tendrá que pasar de nuevo por v5 (puesto que se empezará en v5). Para completar el circuito, se debe regresar a v5, por lo que se pasa tres veces por él.

-(b) Un ciclo hamiltoniano es: v1 e1 v2 e2 v3 e3 v4 e4 v1 Teorema. Sea G un grafo conexo con n vértices, donde n≥3. Si la suma de los grados de cada par de vértices no adyacentes es mayor o igual a n, entonces G tiene un circuito hamiltoniano. 


Refrencias:
http://campus.cva.itesm.mx/nazira/Tc1003/PDF/TODO/0702_Tc1003_TODO_Euler_Hamilton.pdf

Matriz de adyacencia.

Es una matriz cuadrada en la cual los vértices del grafo se indica como filas y como columnas: el orden de los vértices es el mismo que guardan las filas y las columnas de la matriz.se coloca un 1 como elemento de la matriz cuando existe una relación entre uno y otro vértice , o bien un 0 cuando no exista relación alguna.

ejemplo:

G=(V, E)

V={VI, V2, V3, V4, V5}

E={(V1, V1), (V1, V2), (V2, V3), (V2, V4), (V2, V5), (V3, V4), (V4, V5), (V5, V1)}

A=

EJERCICIO.

OBTENER lo siguiente.

¿Tiene camino de Euler?

-No

¿Tiene circuito de Euler?

-No

¿Tiene circuito de Hamilton?

-No

Obtener:

-Conjunto de vértices(V)

V={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

-Conjunto de aristas(A)

A={a, b, d, e, f, g, h, i, j, k, l, m, n, p}

-Conjunto de lazos(L)

L={c, o}

-Conjunto de lados paralelos(P)

P={b, p}

-Obtener el matriz de adyacencia.

referencias.

http://docencia.udea.edu.co/regionalizacion/teoriaderedes/informaci%F3n/C1_RepresentacionMatrices.pdf