INTRODUCCION A GRAFOS

El origen de la palabra grafo es griego y su significado etimológico es "trazar". Aparece con gran
frecuencia como respuesta a problemas de la vida cotidiana, algunos ejemplos podrían ser los
siguientes: un gráfico de una serie de tareas a realizar indicando su secuenciación (un organigrama),
grafos matemáticos que representan las relaciones binarias, una red de carreteras, la red de enlaces
ferroviarios o aéreos o la red eléctrica de una ciudad. En cada caso, es conveniente representar
gráficamente el problema dibujando un grafo como un conjunto de puntos (vértices) con líneas
conectándolos (arcos).
Ejemplos

Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas
(aristas).
Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas
con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los
vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden
ser cables o conexiones inalámbricas).

Historia y problema de los puentes de Königsberg

El primer artículo científico relativo a grafos fue escrito por el matemático suizo Leonhard Euler en 1736. Euler se basó
en su artículo en el problema de los puentes de Königsberg. La ciudad de Kaliningrado, originalmente Königsberg, es
famosa por sus siete puentes que unen ambas márgenes del río Pregel con dos de sus islas. Dos de los puentes unen
la isla mayor con la margen oriental y otros dos con la margen occidental. La isla menor está conectada a cada margen
por un puente y el séptimo puente une ambas islas. El problema planteaba lo siguiente: ¿es posible dar un paseo
comenzando desde cualquiera de estas regiones, pasando por todos los puentes, recorriendo solo una vez cada uno y
regresando al mismo punto de partida?
Abstrayendo este problema y planteándolo con la (entonces aún básica) teoría de grafos, Euler consigue demostrar que
el grafo asociado al esquema de puentes de Königsberg no tiene solución, es decir, no es posible regresar al vértice de
partida sin pasar por alguna arista dos veces.
De hecho, Euler resuelve el problema más general: ¿qué condiciones debe satisfacer un grafo para garantizar que se
puede regresar al vértice de partida sin pasar por la misma arista más de una vez? Si definimos como «grado» al
número de líneas que se encuentran en un punto de un grafo, entonces la respuesta al problema es que los puentes de
un pueblo se pueden atravesar exactamente una vez si, salvo a lo sumo dos, todos los puntos tienen un grado par.

DEFINICIONES Y TERMINOLOGIA FUNDAMENTAL

Vértice
Un vértice (también llamado “nodo”) es una parte fundamental de un grafo. Puede tener un nombre, que
llamaremos “clave”. Un vértice también puede tener información adicional. A esta información adicional la
llamaremos “carga útil”.
Arista
Una arista (también llamada “arco”) es otra parte fundamental de un grafo. Una arista conecta dos vértices para
mostrar que hay una relación entre ellos. Las aristas pueden ser unidireccionales o bidireccionales. Si las aristas
de un grafo son todas unidireccionales, decimos que el grafo es un grafo dirigido o un digrafo.
Ponderación
Las aristas pueden ponderarse para mostrar que hay un costo para ir de un vértice a otro. Por ejemplo, en un
grafo de carreteras que conectan una ciudad con otra, la ponderación en la arista puede representar la distancia
entre las dos ciudades.
 Un bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final
coinciden.
 Dos o más aristas son paralelas si relacionan el mismo par de vértices.
 Ruta
Una ruta en un grafo es una secuencia de vértices que están conectados por las aristas. Formalmente definiríamos
una ruta como w1,w2,...,wnw1,w2,...,wn tal que (wi,wi+1)∈E para todo 1≤i≤n−1. La longitud de la ruta no
ponderada es el número de aristas en la ruta, específicamente n−1. La longitud ponderada de la ruta es la suma de
las ponderaciones de todos las aristas en la trayectoria. Por ejemplo, en la Figura 2 la ruta desde V3 hasta V1 es la
secuencia de vértices (V3,V4,V0,V1. Las aristas
son {(v3,v4,7),(v4,v0,1),(v0,v1,5)}{(v3,v4,7),(v4,v0,1),(v0,v1,5)}.
 Ciclo
Un ciclo en un grafo dirigido es una ruta que comienza y termina en el mismo vértice. Por ejemplo, en la Figura 2 la
ruta (V5,V2,V3,V5) es un ciclo. Un grafo sin ciclos se denomina grafo acíclico. Un grafo dirigido sin ciclos se
denomina grafo acíclico dirigido o GAD.

TIPOS DE GRAFOS:

GRAFO SIMPLE

Un grafo se denomina simple si no tiene bucles y no existe más que un camino para unir dos nodos

MULTIGRAFO

Acepta mas de una arista entre dos nodos o vértices

PSEUDOGRAFO

Permiten los bucles (aristas que conectan un vértice consigo mismo)

GRAFO DIRIGIDO
  Las aristas tienen una orientación, graficada por medio de una flecha
 No permite más de una arista entre dos vértices

MULTIGRAFO DIRIGIDO

Permite tener múltiples aristas dirigidas relacionando dos vértices

EJEMPLO N° 1
Describe una estructura discreta basada en un grafo que se pueda utilizar para representar rutas aéreas y sus
horarios de vuelo( Indicacion: Dota de estructura a un grafo dirigido).

Con esas definiciones a mano podemos definir formalmente un grafo. Un grafo puede ser representado
por G donde G=(V,E). Para el grafo G, V es un conjunto de vértices y E es un conjunto de aristas. Cada arista es una
tupla (v,w) donde w,v∈V. Podemos añadir un tercer componente a la tupla de la arista para representar una
ponderación.
La Figura 2 muestra otro ejemplo de un digrafo ponderado simple. Formalmente podemos representar este grafo como
el conjunto de seis vértices:

V={V0,V1,V2,V3,V4,V5}V={V0,V1,V2,V3,V4,V5}
y el conjunto de nueve aristas:

E={(v0,v1,5),(v1,v2,4),(v2,v3,9),(v3,v4,7),(v4,v0,1),(v0,v5,2),(v5,v4,8),(v3,v5,3),(v5,v2,1)}
TIPOS DE GRAFOS

GRAFO NO DIRIGIDO

Las aristas no están ordenadas:

(v, w) = (w,v) donde v es su nodo inicial, y w es su nodo final.

La red de carreteras de un país representa en general un grafo no dirigido,puesto que una misma
carretera puede ser recorrida en ambos sentidos
GRAFOS DIRIGIDOS(O DIGRAFOS)

Las aristas son pares ordenados:

< v, w > DIF <w, v>

<v, w> w = cabeza de la arista, v = cola

Un ejemplo de grafo dirigido lo constituye la red de aguas de una ciudad ya que cada tubería sólo
admite que el agua la recorra en un único sentido

Conceptos asociados a grafos:

 Diremos que un grafo es completo si A=VxV, o sea, si para cualquier pareja de vértices existe
una arista que los une(en ambos sentidos si el grafo es no dirigido).El número de aristas será:
 o grafos dirigidos:


grafos no dirigidos:

donde n=|V|

 Un grafo dirigido es simétrico si para toda arista (x,y)perteneciente a A también aparece la

arista (y,x)perteneciente a A;y es antisimétrico si dada una arista (x,y) perteneciente a A implica
que (y,x) no pertenece a A.

 Tanto a las aristas como a los vértices les puede ser asociada información.A esta información se
le llama [Link] la etiqueta que se asocia es un número se le llama peso,costo o [Link]
grafo cuyas aristas o vértices tienen pesos asociados recibe el nombre de grafo etiquetado o
ponderado.

 Se llama orden del grafo a su número de vértices,

ADYACENCIA

INCIDENCIA
  Se dice que un vértice x es incidente a un vértice y si existe un arco que vaya
de x a y ((x,y)pertenece a A),a x se le denomina origen del arco y a y extremo del [Link] igual
forma se dirá que y es adyacente a x. En el caso de que el grafo sea no dirigido si x es
adyacente(resp. incidente) a y entonces y también es adyacente (resp. incidente) a x..

GRADO DE UN VERTICE

El grado de un vértice n es el número de arcos incidentes a él.

En el caso de los grafos orientados, el grado de entrada de un vértice n es el número de arcos que llegan a él y el
grado de salida de un vértice n es el número de arcos que salen de él.

Por lo tanto, el grado de un vértice es la suma de los grados de entrada y de salida del vértice

El grado de entrada de un vértice v, denotado por ð-(v) es el numero de aristas que tienen a v como vértice final

El grado de salida de un vértice v, denotado por ð+(v) es el numero de aristas que tienen a v como vértice inicial.
EJEMPLO:
Determinar los grados de entrada y de salida de los vértices del siguiente grafo.
CAMINOS

Un camino en un grafo es una sucesión finita en la que aparecen alternadamente vértices y

aristas de dicho grafo.

Un camino es una secuencia de arcos en que el extremo final de cada arco coincide con el
extremo inicial del siguiente en la secuencia.
Tipos de caminos
Camino euleriano: es un camino o circuito que contiene todas las aristas apareciendo cada
una de ellas exactamente una vez. Un grafo que admite dicho circuito se denomina grafo
euleriano
Camino hamiltoniano: es un camino simple que contiene todos los vértices apareciendo
cada uno de ellos exactamente una vez. Un ciclo que a su vez es un camino hamiltoniano se
denomina ciclo hamiltoniano


Se dice que dos arcos son adyacentes cuando tienen un vértice común que es a la vez origen de
uno y extremo del otro.


Dado un grafo G=(V,A),diremos que G'=(V,A') con es un grafo parcial de G y
' ' '
un subgrafo de G es todo grafo G =(V ,A ) con y donde A' será el conjunto de
todas aquellas aristas que unían en el grafo G dos vértices que están en V'. Se podrían combinar
ambas definiciones dando lugar a lo que llamaremos subgrafo parcial
REPRESENTACION DE GRAFOS
MATRICES DE ADYACENCIA