Grafos

Materia: #técnicas_y_diseños_de_algoritmos

Tags: Estructura

Grafos

Un grafo $G = (V, X)$ es un par de conjuntos, donde $V$ es un conjuntos de puntos o nodos o vértices y $X$ es un subconjunto del conjunto de pares no ordenados de elementos distintos de $V$ . Los elementos de $X$ se llaman aristas o ejes.

Si no aclaramos lo contrario, por lo general, en el curso llamaremos

n_{G} = | V |

m_{G} = | X |

. Cuando esté claro a qué grafo nos referimos, evitaremos el subíndice.

Dados $v$ y $w \in V$ , si $e = (v, w) \in X$ se dice que $v$ y $w$ son adyacentes y que $e$ es incidente a $v$ y $w$ . La vecindad de un vértice $v$ , $N (v)$ , es el conjunto de los vértices adyacentes a $v$ . Es decir:

N (v) = {w \in V : (v, w) \in X}

Dibujar los grafos es sumamente útil para entender muchas de sus propiedades. Los vértices son representados mediante puntos y las aristas mediante líneas uniendo los vértices que la definen. No hay una única forma de dibujar un grafo, las posiciones relativas de los vértices son irrelevantes, como así también la de las aristas.

graph LR

id1((1))
id2((2))
id3((3))
id4((4))
id5((5))
id6((6))
id7((7))

id1 --- id2
id2 --- id3
id3 --- id4
id4 --- id1
id1 --- id5
id6 --- id7

En el ejemplo del dibujo, esta representado el grafo $G = (V, X)$ , donde

\begin{aligned} V & = {v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6}, v_{7}} \\ X & = {(v_{1}, v_{2}), (v_{2}, v_{3}), (v_{3}, v_{4}), (v_{1}, v_{4}), (v_{1}, v_{5}), (v_{6}, v_{7})} \end{aligned}

En el dibujo ingresamos números en los nodos para simplificar la notación, pero podría dibujarse un nodo sin distinción entre los nodos (aunque no tendría mucha utilidad).

Multígrafos y pseudografos

Un multígrafo es un grafo en el que puede haber varias aristas entre el mismo par de vértices distintos.

Un pseudografo es un grafo en el que puede haber varias aristas entre cada par de vértices y también puede haber aristas (loops) que unan a un vértice con sí mismo.

En la materia, si no aclaramos lo contrario, cuando nos referimos al término grafo, asumimos que no hay aristas múltiples ni loops.

X pasa a ser un multiconjunto de aristas.

flowchart LR

id1((1))
id2((2))
id3((3))
id4((4))
id5((5))
id6((6))

id1 --- id1
id1 --- id2
id2 --- id3
id2 --- id3
id2 --- id6
id3 --- id6
id3 --- id5
id3 --- id4
id4 --- id6
id4 --- id5
id4 --- id5
id4 --- id5
id6 --- id6

En el dibujo se ve representado un multipseudografo.

Grado de los vértices

El grado de un vértice $v$ en el grafo $G$ , $d_{G} (v)$ es la cantidad de aristas incidentes a $v$ en $G$ . Llamaremos $Δ (G)$ al máximo grado de los vértices de $G$ , y $δ (G)$ al mínimo.

Si está claro al grafo que nos referimos, lo notaremos como

d (v)

Las vértices y las aristas de un grafo están relacionadas por la siguiente formula:

\sum_{v \in V} d (v) = 2 m

Un grafo se dice completo si todos sus vértices son adyacentes entre sí. Notaremos como $K_{n}$ al grafo completo de $n$ vértices. Un grafo completo de $n$ vértices, siguiendo la formula de antes, tiene exactamente $m_{K_{n}} = \frac{n (n - 1)}{2}$ artistas.

flowchart LR

id1((1))
id2((2))
id3((3))
id4((4))

id1 --- id2
id2 --- id3
id3 --- id4
id4 --- id1
id1 --- id3
id2 --- id4

En el dibujo se puede ver un ejemplo de grafo completo.

Dado un grafo $G = (V, X)$ , su grafo complemento, que notaremos $\bar{G} = (V, \bar{X})$ , tiene el mismo conjunto de vértices y un par de vértices son adyacente en $\bar{G}$ si, y solo si, no son adyacentes en $G$ . También puede ser notado como $G^{c}$ .

flowchart LR

id1((1))
id2((2))
id3((3))
id4((4))
id5((5))

id1 --- id2
id1 --- id3
id2 --- id3
id2 --- id4
id3 --- id5
id4 --- id5

flowchart LR

id1((1))
id2((2))
id3((3))
id4((4))
id5((5))

id1 --- id5
id2 --- id5
id3 --- id4
id1 --- id4

En los dibujos podemos ver dos grafos, cada uno siendo el complemento del otro.

Dado un grafo $G$ de $n$ vértices y $m$ aristas, decimos que $\bar{G}$ tiene $m_{\bar{G}} = \frac{n (n - 1)}{2} - m$ aristas.

Subgrafos y subgrafos inducidos

Dado un grafo $G = (V_{G}, X_{G})$ , un subgrafo de $G$ es un grafo $H = (V_{H}, X_{H})$ tal que $V_{H} \subseteq V_{G}$ y $X_{H} \subseteq (X_{G} \cap (V_{H} \times V_{G}))$ . Lo notamos como $H \subseteq G$ .

Si $H \subseteq G$ y $H \neq G$ , entonces $H$ es subgrafo propio de $G$ , hecho que notamos $H \subset G$ .

$H$ es un subgrafo generador de $G$ si $H \subseteq G$ y $V_{G} = V_{H}$ .

Un subgrafo $H = (V_{H}, X_{H})$ de $G = (V_{G}, X_{G})$ , es un subgrafo inducido si todo par $u, v \in V_{H}$ con $(u, v) \in X_{G}$ entonces también $(u, v) \in X_{H}$ . Un subgrafo inducido de $G = (V_{G}, X_{G})$ por un conjunto de vértices $V^{'} \subseteq V_{G}$ , se denota como $G_{[V^{'}]}$ .

flowchart LR

name(Grafo G)
id1((1))
id2((2))
id3((3))
id4((4))
id5((5))

id1 --- id2
id1 --- id3
id2 --- id4
id3 --- id5
id3 --- id4
id4 --- id5

flowchart LR

name(Grafo H)
id1((1))
id2((2))
id3((3))
id4((4))
id5((5))

id1 --- id2
id2 --- id4
id3 --- id5
id4 --- id5

flowchart LR

name(Grafo I)
id1((1))
id2((2))
id3((3))
id5((5))

id1 --- id2
id1 --- id3
id3 --- id5

Analizando los dibujos, podemos decir que $H$ es un subgrafo no inducido de $G$ . Por otro lado, $I$ es un subgrafo inducido de $G$ por ${v_{1}, v_{2}, v_{3}, v_{5}}$ .

Moverse por el grafo

Existen muchas formas de moverse a través de un grafo dado. En particular, vamos a utilizar los siguientes conceptos:

Un recorrido en un grafo es una secuencia alternada de vértices y aristas $P = v_{0} e_{1} v_{1} e_{2} \dots v_{k - 1} e_{k} v_{k}$ tal que un extremo de la arista $e_{i}$ es $v_{i - 1}$ y el otro es $v_{i}$ para $i = 1, \dots, k$ . Decimos que $P$ es un recorrido entre $v_{0}$ y $v_{k}$ .
En los grafos (no multi ni pseudo) un recorrido queda definido por la secuencia de vértices: $P = v_{0} v_{1} \dots v_{k - 1} v_{k}$ .
Un camino es un recorrido que no pasa dos veces por el mismo vértice.
Una sección de un camino $P = v_{0} e_{1} v_{1} e_{2} \dots v_{k - 1} e_{k} v_{k}$ es un subsecuencia $v_{i} e_{i + 1} v_{i + 1} e_{i + 2} \dots v_{j - 1} e_{j} v_{j}$ de términos consecutivos de $P$ , y lo notamos como $P_{v_{i} v_{j}}$ .
Un circuito es un recorrido que empieza y termina en el mismo vértice.
Un ciclo o circuito simple es un circuito de 3 o más vértices que no pasa dos veces por el mismo vértice.

flowchart LR

id1((1))
id2((2))
id3((3))
id4((4))
id5((5))

id1 --- id2
id1 --- id3
id2 --- id3
id2 --- id4
id2 --- id5
id3 --- id5
id4 --- id5

\begin{aligned} P_{1} & = v_{2} v_{3} v_{1} v_{2} v_{4} es recorrido pero no camino \\ P_{2} & = v_{1} v_{2} v_{5} v_{4} es camino \\ C_{1} & = v_{1} v_{3} v_{2} v_{4} v_{5} v_{2} v_{1} es circuito pero no ciclo \\ C_{2} & = v_{2} v_{3} v_{5} v_{4} v_{2} es ciclo \end{aligned}

Dado un recorrido $P$ , su longitud, $l (P)$ es la cantidad de aristas que tiene. Por otro lado, la distancia entre dos vértices $v$ y $w$ , $d (v, w)$ , se define como la longitud del recorrido más corto entre $v$ y $w$ . En caso de no existir un recorrido entre $v$ y $w$ se dice que $d (v, w) = \infty$ . Para todo vértice $v$ se cumple que $d (v, v) = 0$ .

La función distancia cumple las siguientes propiedades para todo $u$ , $v$ y $w$ pertenecientes a $V$ :

$d (u, v) \geq 0$ y $d (u, v) = 0$ si y sólo si $u = v$ .
$d (u, v) = d (v, u)$
$d (u, w) \leq d (u, v) + d (v, w)$

Grafos conexos

Un grafo $G$ se dice conexo si existe un camino entre todo par de vértices. Por otro lado, llamamos componente conexa de $G$ a un subgrafo conexo maximal (no esta incluido estrictamente en otro subgrafo conexo) de $G$ .

flowchart LR

id1((1))
id2((2))
id3((3))
id4((4))
id5((5))
id6((6))
id7((7))
id8((8))
id9((9))
id10((10))

id1 --- id2
id3 --- id4
id4 --- id1
id1 --- id5
id5 --- id3
id6 --- id7
id8 --- id9
id9 --- id10
id10 --- id8

En este dibujo podemos ver un grafo no conexo con 3 componentes conexas.

flowchart LR

id1((1))
id2((2))
id3((3))
id4((4))
id5((5))

id1 --- id2
id2 --- id3
id4 --- id1
id1 --- id5

Por otro lado, en esta otra imagen se puede ver un grafo conexo.