Parte IV Teoria de grafos

Definición 12.1 (Grafo simple).

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

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

A los elementos de E\displaystyle 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.

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

Definición 12.2 (Multigrafo).

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

E={ei}i∈I\displaystyle E=\{e_{i}\}_{i\in I}

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

Definición 12.3 (Digrafo).

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

Definición 12.4 (Multidigrafo).

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

E={ei}i∈I\displaystyle E=\{e_{i}\}_{i\in I}

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