gers

Grafos

Algoritmos y Estructuras de Datos III

Grafos
Definiciones:
Un grafo G = (V , X ) es un par de conjuntos, donde V es un
conjunto de puntos o nodos o v´rtices y X es un
e
subconjunto del conjunto de pares no ordenados de elementos
distintos de V .
Los elementos de X se llaman aristas, ejes o arcos.
Dados v y w ∈ V , si e = (v , w ) ∈ X se dice que v y w son
adyacentes y que ees incidente a v y w .
Notaci´n: n = |V | y m = |X |
o

Multigrafos y seudografos

Definiciones:
Un multigrafo es un grafo en el que puede haber varias
aristas entre el mismo par de nodos distintos.
Un seudografo es un grafo en el que puede haber varias
aristas entre cada par de nodos y tambi´n puede haber aritas
e
(loops) que unan a un nodo con s´ mismo.
ı
Definiciones de acuerdo ala nomenclatura del libro de Harary.

Grafos
Definiciones:
El grado de un nodo v es la cantidad de aristas incidentes a v .
Notaci´n: d(v ) es el grado de v .
o

Grafos
Definiciones:
El grado de un nodo v es la cantidad de aristas incidentes a v .
Notaci´n: d(v ) es el grado de v .
o

Teorema:
La suma de los grados de los nodos de un grafo es igual a 2 veces
el n´mero de aristas, esdecir
u
n

d(vi ) = 2m
i=1

Grafos
Definiciones:
Un grafo se dice completo si todos los nodos son adyacentes
entre s´
ı.
Notaci´n: Kn es el grafo completo de n nodos.
o
Dado un grafo G = (V , X ), el grafo complemento tiene el
mismo conjunto de nodos y un par de nodos son adyacente si
y solo si no son adyacentes en G .
Notaci´n: G es el grafo completo de G .
o ¯

GrafosDefiniciones:
Un grafo se dice completo si todos los nodos son adyacentes
entre s´
ı.
Notaci´n: Kn es el grafo completo de n nodos.
o
Dado un grafo G = (V , X ), el grafo complemento tiene el
mismo conjunto de nodos y un par de nodos son adyacente si
y solo si no son adyacentes en G .
Notaci´n: G es el grafo completo de G .
o ¯
¿Cu´ntas aristas tiene un grafo completo de n nodos?
a
¯
Si Gtiene n nodos y m aristas, ¿cu´ntas aristas tiene G ?
a

Caminos y circuitos
Definiciones:
Un camino en un grafo es una sucesi´n de aristas e1 e2 . . . ek
o
tal que un extremo de ei coincide con uno de ei−1 y el otro
con uno de ei+1 para i = 2, . . . , k − 1.
Hay otras formas de definir un camino...
Un camino simple es un camino que no pasa dos veces por el
mismo nodo.
Un circuito es uncamino que empieza y termina en el mismo
nodo.
Un circuito simple es un circuito de 3 o m´s nodos que no
a
pasa dos veces por el mismo nodo.

Distancia
Definiciones:
La longitud de un camino es la cantidad de aristas que tiene
ese camino.
La distancia entre dos nodos v y w de un grafo se define
como la longitud del camino m´s corto entre v y w .
a
Notaci´n: d(v , w ) denota ladistancia entre v y w .
o
Para todo nodo v , d(v , v ) = 0.
Si no existe camino entre v y w se dice que d(v , w ) = ∞.
Proposici´n: Si una camino P entre v y w tiene longitud d(v , w ),
o
P debe ser un camino simple.

Distancia

Proposici´n:
o
La funci´n de distancia cumple las siguientes propiedades para
o
todo u, v , w pertenecientes a V :
d(u, v ) ≥ 0 y d(u, v ) = 0 si y s´lo si u = v .o
d(u, v ) = d(v , u).
d(u, w ) ≤ d(u, v ) + d(v , w ).

Subgrafos
Definiciones:
Un grafo se dice conexo si existe un camino entre todo par de
nodos.
Dado un grafo G = (V , X ), un subgrafo de G es un grafo
H = (V , X ) tal que V ⊆ V y X ⊆ X ∩ (V × V ).
Un subgrafo H = (V , X ) de G = (V , X ), es un subgrafo
inducido si para todo par de nodos u, v ∈ V ,
(u, v ) ∈ X ⇐⇒ (u, v ) ∈ X .Una componente conexa de un grafo G es un subgrafo
conexo maximal de G .

Grafos bipartitos
Definiciones:
Un grafo G = (V , X ) se dice bipartito si existe una partici´n
o
V1 , V2 del conjunto de nodos V tal que:
V = V1 ∪ V2 ,

V1 ∩ V2 = ∅,

V1 = ∅,

V2 = ∅

y tal que todas las aristas de G tienen un extremo en V1 y
otro en V2 .
Un grafo bipartito con partici´n V1 , V2 , es...