¿QUE ES UN GRAFO?

external image Konigsberg_bridges.png

Hablando intuitivamente, un grafo es un conjunto de nodos unidos por un conjunto de líneas o flechas. Por lo general, los nodos son entes de procesamiento o estructuras que contienen algún tipo de información y las líneas o flechas son conexiones o relaciones entre estos entes. Si se utilizan flechas para conectar los nodos decimos que el grafo es dirigido (también llamado dígrafo) porque las relaciones entre los nodos tienen una dirección.

En caso contrario el grafo es no dirigido. En cualquiera de los dos casos, bien sea que se utilicen líneas o flechas, a estas relaciones se les puede llamar simplemente aristas.
Frecuentemente las aristas también tienen algún tipo de información asociada (distancia, costo, confiabilidad, etc.), en cuyo caso estamos en presencia de un grafo pesado.
Las secuencias de aristas forman caminos o ciclos. Un ciclo es un camino que termina en el mismo nodo donde comenzó. Si el camino recorre todos los nodos del grafo es llamado tour. El número de aristas en un camino es la longitud del camino.

Se dice que un grafo es conexo si se puede llegar desde cualquier nodo hasta cualquier otro mediante un camino. De lo contrario no es conexo, pero puede dividirse en componentes conexas, que son subconjuntos de nodos y aristas del grafo original que si son conexos. Un grafo conexo sin ciclos es llamado un árbol.

Estos son apenas unos cuantos conceptos de lo que se conoce como la Teoría de Grafos. El objetivo de estas notas no es cubrir por completo dicha teoría sino enfocarnos en la implementación de este tipo de estructuras y las operaciones y algoritmos más comunes e importantes que se aplican sobre las mismas.

Definición

Un grafo G es un par ordenado G = (V,E), donde:
  • V es un conjunto de vértices o nodos, y
  • E es un conjunto de arcos o aristas, que relacionan estos nodos.
Normalmente V suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos. Se llama orden de G a su número de vértices, | V | .

Lazos o bucles
Un lazo o bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.

Grafo no Dirigido
Un grafo no dirigido o grafo propiamente dicho es un grafo G = (V,E) donde:
  • Vneqemptyset
    Vneqemptyset
  • Esubseteq {xinmathcal P(V): |x|=2}
    Esubseteq {xinmathcal P(V): |x|=2}
    es un conjunto de pares no ordenados de elementos de
    V,
    V,
    .

external image 220px-Kaari_suuntaamaton_graafiteoria.png
Grafo Dirigido

Un grafo dirigido o digrafo es un grafo G = (V,E) donde:
  • Vneqemptyset
    Vneqemptyset
  • E subseteq {(a,b) in V times V: a neq b },
    E subseteq {(a,b) in V times V: a neq b },
    es un conjunto de pares ordenados de elementos de
    V,
    V,
    .
Dada una arista (a,b), a es su nodo inicial y b su nodo final.
Por definición, los grafos dirigidos no contienen bucles.
Un grafo mixto es aquel que se define con la capacidad de poder contener aristas dirigidas y no dirigidas. Tanto los grafos dirigidos como los no dirigidos son casos particulares de este.
external image 220px-Kaari_suunnattu_graafiteoria.png

Ejemplo de Grafo
La imagen es una representación del siguiente grafo:
  • V:={1,2,3,4,5,6}external image 250px-6n-graf.png
  • E:=1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6
El hecho que el vértice 1 sea adyacente con el vértice 2 puede ser denotado como 1 ~ 2.
  • En la Teoría de las categorías una categoría puede ser considerada como un multigrafo dirigido, con los objetos como vértices y los morfismos como aristas dirigidas.
  • En ciencias de la computación los grafos dirigidos son usados para representar máquinas de estado finito y algunas otras estructuras discretas.
  • Una relación binaria R en un conjunto X es un grafo dirigido simple. Dos vértices a, b en X están conectados por una arista dirigida ab si aRb.

Vídeo de Concepto de Grafo - Matematica Discreta