Grafos simples

GRAFOS SIMPLES

Un grafo es simple si a lo sumo sólo 1 arista une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Un grafo que no es simple se denomina Multigráfica o Grafo múltiple.

GRAFOS CONEXOS

Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b. Un grafo es fuertemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.

GRAFOS COMPLETOS

Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une. El conjunto de los grafos completos es denominado usualmente, siendo el grafo completo de n vértices. Un, es decir, grafo completo de n vértices tiene exactamente aristas.

GRAFOS BIPARTITOS

Un grafo G es bipartito si puede expresarse como G = {V_1 cup V_2, A} (es decir, sus vértices son la unión de dos grupos de vértices), bajo las siguientes condiciones:

* V1 y V2 son disjuntos y no vacíos.

* Cada arista de A une un vértice de V1 con uno de V2.

* No existen aristas uniendo dos elementos de V1; análogamente para V2.

Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes.

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

* Esubseteq {xinmathcal P(V): |x|=2} es un conjunto de pares no ordenados de elementos de V,.

Un par no ordenado es un conjunto de la forma {a,b}, de manera que {a,b} = {b,a}. Para los grafos, estos conjuntos pertenecen al conjunto potencia de V de cardinalidad 2, el cual se denota por mathcal P(V).

Grafo dirigido

Un grafo dirigido o digrafo es un grafo G = (V,E) donde:

* Vneqemptyset

* E subseteq {(a,b) in V times V: a neq b }, es un conjunto de pares ordenados de elementos de 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.

CONECTIVIDAD EN GRAFOS

A diferencia de los conceptos anteriores, que afectaban a vértices del grafo, la conectividad es una propiedad del grafo en su conjunto. Un grafo orientado puede ser conexo o fuertemente conexo. Un grafo orientado sólo puede ser conexo. Más concretamente, tenemos:

Diremos que un grafo es conexo si existe al menos un ciclo entre toda pareja de vértices. El concepto es aplicable tanto a grafos orientados como para no orientados: obsérvese que se ha definido ciclo tanto para grafos orientados como para no orientados. Diremos que un grafo orientado es fuertemente conexo si existe al menos un camino entre toda pareja de vértices. Todo grafo orientado fuertemente conexo será también conexo.

COMPONENTES DE UN GRAFO

Un grafo (G) es un diagrama que consta de un conjunto de vértices (V) y un conjunto de lados (L). A partir de esta figura se definen los siguientes elementos: vértices (nodos) se indican por medio de un pequeño círculo y se les asigna un número o letra. En el grafo anterior los vértices son V={a,b,c,d}.

LADOS (RAMAS O ARISTAS).

Son las líneas que unen un vértice con otro y se les asigna una letra, un número o una combinación de ambos. En el grafo anterior los lados son: L= {1,2,3,4,5,6}.

LADOS PARALELOS

Son aquellas aristas que tienen relación con un mismo par de vértices. En el grafo anterior los lados paralelos son: P={2,3}.

LAZO

Es aquella arista que sale de un vértice y regresa al mismo vértice. En el grafo anterior se tiene el lazo: A={6}

VALENCIA DE UN VÉRTICE

Es el número de lados que salen o entran a un vértice. En el grafo anterior las valencias de los vértices son:

Valencia (a)=2

Valencia (b)=4

Valencia (c)=2

Valencia (d)=3

Hay que observar como en el caso del vértice d el lazo solo se considera una vez, entrada o salida pero no ambos.

TIPOS DE GRAFOS

GRAFOS SIMPLES

Son aquellos grafos que no tienen lazos ni lados paralelos.

GRAFO COMPLETO DE N VERTICALES (KN )

Es el grafo en donde cada vértice está relacionado con todos los demás sin lazos ni lados paralelos. Se indica como kn en donde n es el número de vértices del grafo. La valencia en cada uno de los vértices de los grafos completos es (n - 1), y el número de lados está dado por la expresión Núm. De lados = n(n - 1)/2, en donde n es el número de

...