Part IV Teoria de grafos

Definition 12.4 (Grafo simple).

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

E⊆{{u,v}∣u,v∈V,u≠v}E\subseteq\left\{\left\{u,v\right\}\mid u,v\in V,u\neq v\right\}

A los elementos de EE 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).

Example 12.5.

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

Definition 12.6 (Multigrafo).

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

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

donde II es un conjunto finito y ∀i∈I\forall i\in I se verifica que ei={ui,vi}e_{i}=\left\{u_{i},v_{i}\right\} con ui,vi∈Vu_{i},v_{i}\in V, posiblemente iguales (puede pasar que ui=viu_{i}=v_{i} o ei=eke_{i}=e_{k}).

Definition 12.7 (Digrafo).

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

Definition 12.8 (Multidigrafo).

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

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

donde II es un conjunto finito y ∀i∈I\forall i\in I se verifica que ei∈V×Ve_{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