Grafos

En matemáticas y ciencias de la computación, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto. Son objeto de estudio de la teoría de grafos.

Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas o arcos).

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).

Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las ciencias exactas y las ciencias sociales.

Definición:

Un Grafo G es una terna [V, A, g] formada por un conjunto no vacío, cuyos elementos se denominan vértices, un conjunto a cuyos elementos son llamados Aristas y una aplicación g que a cada elemento x ∈ A le asocia un par no ordenado de vértices {u, v} (Puede ser u = v). Cuando x ∈ A y g (x) = {u, v}, entonces se dice que u y v son extremos de la arista x o que la arista x incide o tiene incidencias en u y v; también se dice que u y v son vértices adyacentes o que están conectados por la arista x.

Grafo Dirigido:

Un grafo dirigido es aquel en el que todas sus aristas tienen sentido o dirección.

La relación sobre V no es simétrica. Las aristas se representan como un par ordenado (u,v). 

Grafo no dirigido:

Un grafo no dirigido es aquel en el que todas sus aristas son bidireccionales.

La relación sobre V es simétrica. Las aristas se representan como pares no ordenados {u,v}, u,v Є V y u ≠ v.

Grafo ponderado:

Un grafo ponderado, pesado o con costos es un grafo donde cada arista tiene asociado un valor o etiqueta, para representar el costo, peso, longitud, etc.

Camino:

En teoría de grafos, un camino  es una sucesión de vértices y aristas dentro de un grafo, que empieza y termina en vértices, tal que cada vértice es incidente con las aristas que le siguen y le preceden en la secuencia.

• Un camino cerrado es un camino cuyo vértice inicial y final coinciden.
• Un camino abierto es un camino cuyo vértice inicial y final no coinciden.
• Un camino simple es un camino sin vértices repetidos, salvo quizás el primero y el último (por lo tanto, es un tipo especial de recorrido, pues tampoco tiene aristas repetidas).

 
Ciclo: 

Un ciclo es un camino donde el origen del camino es igual a su destino. Formalmente es camino desde v1, v2, ... , vk tal que v1=vk.

• Un ciclo Euleriano es un ciclo que pasa por todas las aristas del grafo una única vez.
• Un ciclo Hamiltoniano es un ciclo que pasa por todos los vértices del grafo una única vez (en caso que el vértice inicial y final no coinciden, se suele hablar también de camino Hamiltoniano).

 

Bucle: 

Un bucle es una arista que conecta a un vértice consigo mismo. Es un ciclo de longitud 1

Grafo conexo:

Un grafo no dirigido es conexo si existe un camino entre cada par de vértices.

Conexo

                                       

No conexo 

Grafo fuertemente conexo:

Un grafo dirigido se denomina fuertemente conexo si existe un camino desde cualquier vértice a cualquier otro vértice.

Grafo Débilmente Conexo:

Si un grafo dirigido no es fuertemente conexo, pero el grafo subyacente (sin sentido en los arcos) es conexo, el grafo es débilmente conexo.

Propiedades:

• Adyacencia: dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.
• Incidencia: una arista es incidente a un vértice si ésta lo une a otro.
• Ponderación: corresponde a una función que a cada arista le asocia un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo. Esto se usa mucho para problemas de optimización, como el del vendedor viajero o del camino más corto.
• Etiquetado: distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto.

 

Matriz adyacencia:

(Se le llama matriz conexión en caso de que sea un grafo dirigido) Todo grafo simple puede ser representado por una matriz, que llamamos matriz de adyacencia.

Se trata de una matriz cuadrada de n filas y n columnas (siendo n el número de vértices del grafo).

Para construir la matriz de adyacencia, cada elemento a_{ij} vale 1 cuando haya una arista que una los vértices i y j. En caso contrario el elemento a_{ij} vale 0.

La matriz de adyacencia, por tanto, estará formada por ceros y unos.

Matriz incidencia:

1. Las columnas de la matriz representan las aristas del grafo.
2. Las filas representan a los distintos nodos.
3. Por cada nodo unido por una arista, ponemos un uno (1) en el lugar correspondiente, y llenamos el resto de las ubicaciones con ceros (0).

Árbol (teoría de grafos)

En teoría de grafos, un árbol es un grafo en el que cualquier par de vértices están conectados por exactamente un camino, o alternativamente, es un grafo conexo acíclico.

-Marycé Martínez 

CI: 28.563.108