Grafo

De Wikipedia, la enciclopedia libre

Este artículo sólo presenta definiciones básicas. Para un punto de vista más amplio, consúltese Teoría de los grafos.

En matemáticas y en ciencias de la computación, un grafo es el objeto abstracto básico de estudio en teoría de los grafos. Informalmente, un grafo se concibe y se representa como un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas. Las aristas pueden tener dirección (grafo dirigido).

[editar] Definiciones

[editar] Grafo no dirigido

Un grafo no dirigido $G\,$ es un par ordenado $G = (V, E) \,$ donde

$V\,$ un conjunto (llamado de vértices o nodos),
$E \subset V \times V$ , subconjunto de pares no ordenados de vértices (llamado de aristas o lados).

$V\,$ (y por tanto también $E\,$ ) suele ser un conjunto finito, y muchos de los resultados más conocidos sobre grafos no son ciertos para grafos infinitos.

[editar] Grafo dirigido

Un grafo dirigido (también llamado digrafo) $G\,$ es un par ordenado $G = (V, E) \,$ donde

$V\,$ un conjunto (llamado de vértices o nodos),
$E \subset V \times V$ , subconjunto de pares ordenados de vértices (llamado de arcos).

[editar] Variantes sobre las principales definiciones

Algunas aplicaciones requieren extensiones más generales a las dos propuestas clásicas de grafos. Un bucle es una arista (dirigida o no) donde coinciden el vértice inicio y el fin. Aunque la definición original los permite, según la aplicación concreta pueden ser válidos o no. A veces $E$ o $A$ pueden ser un multiconjunto, pudiendo haber más de una arista entre cada par de vértices. La palabra grafo (a secas) puede permitir o no múltiples aristas entre cada par de vértices, dependiendo del autor de la referencia consultada. Si se quiere remarcar la inexistencia de múltiples aristas entre cada par de vértices (y en el caso no dirigido, excluir bucles) el grafo puede llamarse simple. Por otra parte, si se quiere asegurar la posibilidad de permitir múltiples aristas, el grafo puede llamarse multigrafo (a veces se utiliza el término pseudografo para indicar que se permiten tanto bucles como múltiples aristas entre cada par de vértices).

[editar] Propiedades

Dos aristas de un grafo son llamadas adyacentes si tienen un vértice en común. De forma similar, dos vértices son llamados adyacentes si una arista los une. Se dice que una arista es incidente a un vértice si ésta lo une a otro.

Si un grafo sólo tiene un vértice y ninguna arista, se le conoce como trivial. Si un grafo no tiene ni vértices ni aristas, se conoce como vacío ó nulo, aunque no hay un consenso sobre si deba de seguir existiendo, ya que no cumple con muchas propiedades.

En un grafo ó digrafo ponderado, a cada arista se le asocia un valor, como costo, peso, longitud, etc. según sea lo que modele, en general se usan para problemas de optimización como el problema del vendedor o el camino óptimo.

Normalmente los vértices y las aristas de un grafo, por su naturaleza como elementos de un conjunto, son distinguibles. Este tipo de grafos son llamados etiquetados, también pueden sólo etiquetarse los vértices o áristas.

[editar] Ejemplos

La imagen es una representación del siguiente grafo:

V:={1,2,3,4,5,6}
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.

[editar] Grafos importantes

Un grafo completo es un grafo simple en el que cada par de vértices están unidos por una arista, es decir contiene todas las posibles aristas.
Un grafo planar o plano es aquel que puede ser dibujado en el plano (R²) sin cruce de aristas.
Un árbol es un grafo conexo sin ciclos.
Grafo bipartito
Grafo perfecto
Los grafos de Petersen y sus generalizaciones.