Teoría de Grafos

Un Grafo G=(V,E)

Donde V, es el conjunto de vértices y donde E es el conjunto de arcos o aristas.

Se pueden representar.

Red de computadores.
Conexiones de vuelo de una aerolínea.
Circuitos electrónicos.

Son aplicables en:

Ingeniería en sistemas.
Ingeniería industrial.
Ingeniería electrónica.

Grafos conexos:

Un grafo es conexo si cada par de vértices está conectado por un camino (arista); es decir, si para cualquier par de vértices (a, b), existe al menos un camino (arista) posible desde a hacia b.

Grafos no conexos:

Un grafo no es conexo si para cada par de vértices no están conectados por un camino: es decir, si para cualquier par de vértices (a, b), no existe al menos un camino (arista) posible desde a hacia b.

Tipo de Grafos:

Existen dos tipos de Grafos los dirigidos y los no dirigidos.

Un grafo dirigido (o dígrafo) G consta de un conjunto V de vértices y un conjunto E de lados, tal que e

E esta asociado a un par ordenado único de vértices v y w y se escribe e = (v, w).

Ejemplo:

Un grafo (grafo no dirigido) G consta de un conjunto V de vértices o nodos y un conjunto E de lados, (ramas o aristas) tales que cada lado e

E esta asociado a un par no ordenado de vértices.

Si un lado e esta asociado a un único par de vértices v y w se escribe e = (v, w) o también se escribe e = (w, v).

Ejemplo:

Camino de Euler:

Es aquel camino que recorre todos los nodos pasando por todas las aristas solamente una vez. Una característica importante de los grafos que tienen camino de Euler es que siempre comienzan y terminan en nodos que terminan en valencia impar.

Circuito de Euler:

Es aquel ciclo que recorre todos los nodos pasando por todos las aristas solamente una vez.Un grafo tiene un Circuito de Euler si y solo si es conexo y todos sus nodos tienen valencia par.

Circuito de Hamilton:

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.

Matriz Adyacente:

Todo grafo simple puede ser representado por una matriz, que llamamos matriz de adyacencia.

Se trata de una matriz cuadrada de n filas X n columnas (siendo el número de vértices del grafo).

Para construir la matriz de adyacencia, cada elemento vale (1) cuando haya una arista que una los vértices y en caso contrario el elemento vale (0).

La matriz de adyacencia, por tanto, estará formada por ceros y unos.

Ejemplo: Vamos a construir la matriz de adyacencia del siguiente grafo:

Como tiene 5 vértices, será una matriz de 5 filas x 5 columnas

Referencias:

http://es.slideshare.net/pavelaliaga/teoria-de-grafos-12993009

http://mate.cucei.udg.mx/matdis/5gra/5gra2.htm

http://pogo-uvaq.blogspot.mx/2009/05/caminos-y-circuitos.html

http://campus.cva.itesm.mx/nazira/Tc1003/PDF/TODO/0702_Tc1003_TODO_Euler_Hamilton.pdfhttp://matematicasies.com/Matriz-de-adyacencia-de-un-grafo

Ejercicios:

En un torneo Nieve venció a los Faisanes una vez, el Rascacielos venció a la Tuna una vez, el Nieve venció al Rascacielos dos veces, los Faisanes vencieron a la tuna una vez y los Faisanes vencieron a Rascacielos una vez. En los ejercicios 1 al 4 use una grafica para modelar el torneo, los equipos son los vértices. Describa el tipo de grafica usada.

1) Hay una arista entre los equipos si los equipos jugaron.

2) Hay una arista entre los equipos si los equipos para cada juego jugado.

3) Hay una arista del equipo t al equipo j si t venció a j al menos una ves.

4) Hay una arista del equipo t al equipo j para cada victoria de t sobre j.

Respuestas:

1) Grafica no dirigida.