Caminos y circuitos.

Camino.
Es una sucesión de lados que van de un nodo x a un nodo w (dichos lados se pueden repetir).

Circuito o ciclo.
Es un camino del nodo w al nodo w, esto es, un camino que regresa al mismo nodo de donde salió.


Circuito simple de longitud n.
Es aquel camino del nodo w al nodo w que solamente tiene un ciclo en la ruta que sigue.

Camino simple de longitud n.
Es una sucesión de lados que van de un nodo x a un nodo w, en donde los lados que componen dicho camino son distintos e iguales a n. Esto significa que no se puede pasar dos veces por una misma arista.

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.

Algoritmo de Fleury.
Nos permite determinar un circuito de Euler:
1)Verificar que el grafo sea conexo y que todos los nodos tengan valencia par. Si no cumple el grafo no tiene circuito de Euler y finalizar.
2)Si cumple con la condición anterior, seleccionar un nodo arbitrario para iniciar el recorrido.
3)Escoger una arista a partir del nodo actual. Esa arista seleccionada no debe de ser “lado puente”, a menos que no exista otra opción.
4)Desconectar los nodos que están unidos por la arista seleccionada.
5)Si todos los nodos del grafo ya estan desconectados, ya se tiene un circuito de Euler y finalizar. De otra manera continuar con el paso 3.

Representación matricial de grafos

Matriz de adyacencia.
Es una matriz cuadrada en la cual los nodos del grafo se indican como renglones y como columnas. El orden de los nodos es el mismo que guardan los renglones y las columnas de la matriz. Se coloca 1 como elemento de la matriz cuando existe una relación entre uno y otro vertice, o bien un 0 cuando no exista relación alguna.

Nota: en una matriz de adyacencia no es posible representar lados paralelo.

Matriz de incidencia.
En esta matriz se colocan los nodos del grafo como renglones y las aristas como columnas. En esta matriz si es posible representar lados paralelos. Al sumar los elementos de cada una de los renglones se obtiene la valencia de los nodos, al sumar las columnas es posible distinguir cuando se trata de un lazo ya que su suma es 1.

Grafos.

Grafo.
Los grafos son representaciones de redes y por medio de ellos se pude expresar en forma visual y sencilla la relación entre elementos.
En computación los grafos se utilizan para mostrar las relaciones entre archivos en una base de datos, entre registros en una estructura de datos, entre computadoras en una red.

Partes de un grafo.
Un grafo (G) es un diagrama que consta de un conjunto de nodos (Vértices) y un conjunto de aristas (lados).

Nodos. Se indican por medio de un pequeño circulo y se le asigna un numero o una letra.

Aristas. Son las lineas que unen un nodo con otro y se les asigna una letra un numero o una combinación de ambos.

Aristas paralelas. Son las aristas que tienen relación con un mismo par de nodos.

Lazo. Es aquella arista que sale de un nodo y regresa al mismo nodo.

Valencia de un nodo. Es el numero de aristas que salen o entran a un nodo.

Tipos de grafos.

Grafos simples. Son aquellos grafos que no tienen lazos ni aristas paralelas.

Grafo completo de orden N. Es el grafo en donde cada nodo esta relacionado con todos los demas, sin lazos ni lados paralelos. Se indica Kn en donde n es el numero de nodos. La valencia de cada uno de los nodos de los grafos completos esta dada por la expresión:
numero de aristas= n(n-1)/2
en donde n es el numero de nodos.

Grafo bipartito completo. Es el grafo que esta compuesto por dos conjuntos de nodos, uno de ellos A={a1, a2, a3, ....., an} y otro B={b1, b2, .....,bm} y en el que cada nodo de A esta unido con todos los nodos de B, pero entre los nodos del mismo conjunto no existe ninguna arista que los una. Se indica como Kn,m en donde n y m es el numero de nodos de cada uno de los conjuntos.

Grafo dirigido. Es el grafo en donde las aristas tienen asociadas una dirección.


Complemento de un grafo. Es el grafo que le falta al grafo G, de forma que entre ambos forman un grafo completo de n vertices. Este grafo no tiene lazos ni ramas paralelas.