Matematicas Discretas

Introducción

La Teoría de Grafos juega un papel importante en la fundamentación matemática de las Ciencias de la Computación. Los grafos constituyen una herramienta básica para modelar fenómenos discretos y son fundamentales para la comprensión de las estructuras de datos y el análisis de algoritmos.

Base Teórica

Cuerpo Teórico

Caminos

Ciclos

En Teoría de grafos, un grafo ciclo o simplemente ciclo es un grafo que se asemeja a un polígono de n lados. Consiste en un camino cerrado en el que no se repite ningún vértice a excepción del primero que aparece dos veces como principio y fin del camino. Un Grafo ciclo de n vértices se denota Cn. El número de vértices en un grafo Cn es igual al número de aristas, y cada vértice tiene grado par, por lo tanto cada vértice tiene dos aristas incidentes.

Si es un ciclo Cn, el grafo tiene n vértices y n aristas formadas de la siguiente manera:

Propiedades

Un grafo ciclo es:

• Conexo.- En efecto, si tomamos 2 vértices cualquiera, siempre hay 2 caminos distintos (sin vértices comunes a excepción de los vértices extremos) que los conectan. Luego, por el Teorema de Whitney (1932), los ciclos tienen índice de conexión:

Los ciclos son también 2-conexo por aristas, en efecto, dado 2 vértices cualesquiera, siempre hay 2 caminos distintos (sin aristas comunes entre ambos) que los conectan. Luego, por el Teorema de Menger (1927), los ciclos tienen índice de arista conexión: Los ciclos al tener el índice de arista conexión igual a 2 carecen de aristas puentes.

• Regular.- Es claro que los ciclos son 2-regulares, ya que dado un ciclo de n vértices, todos sus grados son iguales a dos: con i=1...n

Algoritmo para determinar si se forman ciclos

Algoritmo: Para determinar si al agregar una arista a una grafo se forma algún ciclo

//Siendo una arista nueva con nodos adyacentes A y B

1. Tomamos cualquier nodo adyacente a la arista que vamos a generar (Por ejemplo A)

2. Verificamos que no tenga aristas hacia B, y de ser así lo marcamos

3. Repetimos el proceso (2) con cada uno de los nodos adyacentes al nodo A y hasta marcar todos los nodos conectados.

4. Si en todo el recorrido no encontró ninguna arista hacia B, entonces no se generan ciclos al agregar la arista nueva.

Un Grafo ciclo dirigido de longitud 8.

Grafo ciclo dirigido

Un grafo ciclo dirigido es una versión dirigida de un grafo ciclo, con todas las aristas orientadas hacia una misma dirección.

En un Grafo ciclo dirigido, el grado de salida del vértice es 1 y el de entrada también es 1.

Ciclo Euleriano

Un ciclo o circuito euleriano es aquel camino que recorre todas las aristas de un grafo cortando cinco veces por cada arco (arista) del grafo, siendo condición necesaria que regrese al vértice inicial de salida (ciclo = camino en un grafo donde coinciden vértice inicial o de salida y vértice final o meta). Una definición más formal lo define como: "aquel ciclo que contiene todas las aristas de un grafo solamente una vez".

Para saber si un grafo es euleriano:

1) Todos sus vértices tienen grado par.

2) Algoritmo para obtener el circuito euleriano:

1. Obtener un circuito euleriano.

2. Elegir una arista con extremo en el circuito anterior y repetir el proceso.

3. Unir los distintos circuitos obtenidos y tendremos el circuito buscado.

En un grafo euleriano pueden existir varios circuitos eulerianos diferentes.

Ejemplo:

En la imagen, es un ciclo euleriano, luego es un grafo euleriano.

Un grafo es una representación, un modelo, compuesto por un número determinado de vértices (nodos) y un número de arcos (aristas) que los relacionan, cada arista o arco tiene la capacidad de relacionar dos nodos. La palabra ciclo se emplea en teoría de grafos para indicar un camino cerrado en un grafo, es decir, en que el nodo de inicio y el nodo final son el mismo.

Nota:

Un grafo conexo admite un ciclo euleriano no cerrado si y sólo si exactamente dos vértices tienen grado impar

EJERCICIO:

Desarrollar el siguiente ciclo euleriano recorriendo todas las aristas del grafo sin repetirlas:

Solución:

R=[a,b,c,d,b,e,d,f,e,c,a}

Ciclo Hamiltoreano

En el campo matemático de la teoría de grafos, un camino hamiltoniano en un grafo es un camino, una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano.

El problema de encontrar un ciclo (o camino) hamiltoniano en un grafo arbitrario se sabe que es NP-completo.

Los caminos y ciclos hamiltonianos fueron nombrados después que William Rowan Hamilton, inventor del juego de Hamilton, lanzara un juguete que involucraba encontrar un ciclo hamiltoniano en las aristas de un grafo de un dodecaedro. Hamilton resolvió este problema usandocuaterniones, pero esta solución no se generaliza a todos los grafos.

Un camino hamiltoniano es un camino que pasa por cada vértice exactamente una vez. Un grafo que contiene un camino hamiltoniano se denomina un ciclo hamiltoniano si es un ciclo que pasa por cada vértice exactamente una vez (excepto el vértice del que parte y al cual llega). Un grafo que contiene un ciclo hamiltoniano se dice grafo

...