Grafos

Historia

El nacimiento del concepto GRAFOS se puede situar, por el año 1730, cuando Euler (matemático) se convirtió en el padre de la Teoría de Grafos al modelar un famoso problema no resuelto, llamado el “problema de los puentes de Königsberg”.

g1

Un río con dos islas atraviesa la ciudad. Las islas están unidas, entre sí y con las orillas, a través de siete puentes. El problema consistía en establecer un recorrido que pasará una y solo una vez por cada uno de los siete puentes, partiendo de cualquier punto y regresando al mismo lugar.

Para probar que no era posible, Euler sustituyó cada zona de partida por un punto y cada puente por un arco, creando así un grafo, el primer grafo, diseñado para resolver un problema.

La eficacia de los grafos se basa en su gran poderío de abstracción y la muy clara representación de cualquier relación (de orden, precedencia, etc) lo que facilita enormemente tanto la fase de modelado como de resolución del problema. Gracias a la Teoría de Grafos se han desarrollado una gran variedad de algoritmos y métodos de resolución eficaces que nos permiten tomar una mejor decisión .


Grafo
g2

g3

Llamaremos grafo, G, al par ordenado formado por un conjunto finito no vacío, V , y un conjunto, E, de pares no ordenados de elementos del mismo.

E es una relación

g4

Vértice: Sea un vértice:

g5     

Arista: Llamaremos arista a

g6


Multigrafos

Llamaremos de esta forma a los grafos en los que haya pares de vértices unidos por más de una arista.

PseudoGrafos

Llamaremos pseudografos a los grafos en los que existan aristas cuyos extremos coinciden, es decir, aquellos en los que existan aristas que unen vértices consigo mismos. A tales aristas las llamaremos bucles o lazos.

g10.png


Tipos de Grafos

Grafo Dirigido

Es cuando la relación que la forma NO es simétrica

g11

Grafo No Dirigido

Cuando la relación que forma es simétrica entonces podemos evitar poner las flechas y ver a donde apuntan.

g12.jpg

Se anota entonces los elementos así: 

g13.png


Grafo Conexo

Es en el que para cualquier par de vértices, existe al menos una trayectoria (una sucesión de vértices adyacentes que no repite vértices) de V1  a V2.

g20


SubGrafo

Grafo Original

g21

Subgrafos

g22.jpgg28.jpg

Subgrafo Inducido

g23.jpg


Camino

Es una secuencia ordenada del estilo:

g25.png

también se puede poner como:

g26

Longitud

Podemos definir su longitud como el número de aristas que lo forman.


Recorrido

L es un recorrido si es un camino abierto y no pasa por la misma arista 2 veces.

  • Circuito

Es un camino cerrado y no pasa por la misma arista 2 veces

  • Camino Simple

Es un camino abierto de a  en el menor número de vértices posibles.

  • Ciclo Elemental

Es un circuito donde no se repite ningún vértice (salvo el primero que coincide con el último).


Grafo Asociado

Se puede definir como:

g30.png

Grafo Original

g32.jpg

Grafo Asociado

g31.jpg


Componentes

1

2

 g21  g32

Grado

g40.png

Llamaremos grado o valencia de un vértice al numero de aristas que inciden en  el.

Tenemos entonces:

  • Vértice Aislado, es aquel que no está unida a nada
  • Grafo Regular, cuando todos sus vértices tienen el mismo grado.

En cualquier grafo se verifica:

  • La suma de todos sus grados es igual al doble del numero de sus aristas.
  • El numero de vertices de grado impar es par.

 

Un lazo vale por 2 para los grados

 


Recorrido  y Circuito Euleriano

Es el recorrido o circuito donde pasa por todas las aristas sin repetir ningún vértice más que el inicial y el final.

Así definimos un que un grafo es euleriano si es que existe un recorrido euleriano.

Si un grafo es conexo entonces existe un:

  • Circuito Euleriano ssi todos sus vértices son de grado par.
  • Recorrido Euleriano ssi tiene exactamente 2 vértices de grado impar.

 


Grado de Entrada y Salida

Grado de salida de un grafo es la suma de los los grados individuales y así para la entrada.

Un grafo dirigido conexo tiene un:

  • Circuito Euleriano ssi:

Grado de Salida es igual al de entrada

  • Recorrido Euleriano ssi existe se cumplen estas 3 cosas:
    • Hay un vértice con un grado más de entrada que de salida
    • Hay un vértice con un grado más de salida que de entrada
    • Todos los demás tienen el mismo grado

 


Recorrido  y Circuito Hamiltoniano

Es el recorrido o circuito donde pasa por todas los vértices sin repetir ningún vértice más que el inicial y el final.

Así definimos un que un grafo es euleriano si es que existe un recorrido euleriano.

Si un grafo es conexo entonces existe un:

  • Ciclo Hamiltoniano: Un ciclo simple en un grafo o multigrafo G se dice que es de Hamilton, si contiene a todos los vértices de G.

Esto es un poco complejo de explicar, pero ahí vamos:

Vamos a quitar ciertos vértices, y vamos a ver el subgrafo inducido de los que faltan, el número de componentes de este nuevo grafo es debe ser igual o menor al número de vértices que quitamos.

Sea U un subconjunto no vacío de V  y sea c(G\U) el numero de componentes conexas del subgrafo G\U  entonces la condicion necesaria es c(G\U)  = |U|

 


Isoformismo

De manera compleja es:

Dos grafos se dice que son isomorfos cuando existe una relación biyectiva entre los conjuntos de sus vértices que conserva la adyacencia.

De manera coloquial:

Son los mismos, mismas aristas y mismos vértices

image28

 


Algoritmo de Camino más Corto

(Algoritmo de Dijkstra)
g51.gif

Los pasos son:

Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.

  1. Sea a = x (tomamos a como nodo actual).
  2. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos nodos no marcados vi.
  3. Para el nodo actual, calculamos la distancia tentativa desde dicho nodo a sus vecinos con la siguiente fórmula: dt(vi) = Da + d(a,vi). Es decir, la distancia tentativa del nodo ‘vi’ es la distancia que actualmente tiene el nodo en el vector D más la distancia desde dicho el nodo ‘a’ (el actual) al nodo vi. Si la distancia tentativa es menor que la distancia almacenada en el vector, actualizamos el vector con esta distancia tentativa. Es decir: Si dvi) < Dvi → Dvi = dt(vi)
  4. Marcamos como completo el nodo a.
  5. Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.

 

 


Árboles

 

Un árbol es un grafo que:

  • Es dirigio
  • Es conexo
  • Todos los vértices tienen grado de entrada 1 excepto  un vértice

g52.jpg

Árboles Binario

  • Máximo 2 hijos
  • Se distingue entre hijo derecho o izquierdo

g53.png

 


Recorridos

Podemos recorrer un árbol binario de muchas maneras:

Anchura

Procesamos todos los elementos a la vez un nivel y luego pasamos al siguiente nivel:

anchura

Pero hay otra forma, por profundidad, estos son muy interesantes y conocidos, así que se los dejo:

Profundidad

PreOrden

  1. Primero se procesa la raíz
  2. Procesamos el árbol izquierdo
  3. Procesar el árbol derecho
preorden

Proceso

arbol

Resultado


InOrden

  • Procesamos el árbol izquierdo
  • Primero se procesa la raíz
  • Procesar el árbol derecho
inorden

Proceso

arbol

Resultado


PostOrden

  • Procesamos el árbol izquierdo
  • Procesar el árbol derecho
  • Primero se procesa la raíz

postorden

arbol-34

 

 

 

btn1 btn
btn

 

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s