Parte IV Teoria de grafos

Definición IV.1 (Grafo simple).

Un grafo simple $G$ es un par $G=(V,E)$ formado por un conjunto finito de vertices $V$ y un conjunto $E$ de pares no ordenados de vertices distintos, es decir,

E\subseteq\left\{\left\{u,v\right\}\mid u,v\in V,u\neq v\right\}

A los elementos de $E$ se les denomina aristas (no dirigidas o no orientadas).

Podemos representar geometricamente los grafos en el plano, identificando cada vertice con un punto del plano y cada arista con una linea que une los vertices correspondientes, dando una representacion pictorica del grafo (no unica).

Ejemplo IV.1.

Un grafo simple es, por ejemplo, el grafo $G=(V,E)$ donde $V=\left\{1,2,3,4\right\}$ y $E=\left\{\left\{1,2\right\},\left\{1,4\right\},\left\{1,3\right\}\right\}$ .

Definición IV.2 (Multigrafo).

Un multigrafo es un par $(V,E)$ formado por un conjunto finito de vertices $V$ y una familia finita $E$ de aristas no orientadas

E=\left\{e_{i}\right\}_{i\in I}

donde $I$ es un conjunto finito y $\forall i\in I$ se verifica que $e_{i}=\left\{u_{i},v_{i}\right\}$ con $u_{i},v_{i}\in V$ , posiblemente iguales (puede pasar que $u_{i}=v_{i}$ o $e_{i}=e_{k}$ ).

Definición IV.3 (Digrafo).

Un digrafo es un par $(V,E)$ donde $V$ es un conjunto finito y $E\subset(V\times V)-\Delta$ , siendo $\Delta=\left\{(x,x)\colon x\in V\right\}$ . A los elementos de $V$ se les denomina vertices y a los de $E$ aristas (dirigidas u orientadas).

Definición IV.4 (Multidigrafo).

Un multidigrafo es un par $(V,E)$ formado por un conjunto finito de vertices $V$ y una familia finita $E$ de aristas orientadas

E=\left\{e_{i}\right\}_{i\in I}

donde $I$ es un conjunto finito y $\forall i\in I$ se verifica que $e_{i}\in V\times V$ .

Tipo	Aristas	Aristas multiples?	Lazos?
Grado simple	No dirigidas	No	No
Multigrafo	No dirigidas	Si	Si
Digrafo	Dirigidas	No	No
Multigrafo	Dirigidas	Si	Si