Grafos y digrafos

UNIVERSIDAD NACIONAL DE LA MATANZA

DEPARTAMENTO DE INGENIERÍA E UINVESTGACIONES TECNOLÓGICAS

GUÍA TEÓRICA CON EJERCICIOS RESUELTOS
LIC. BETINA WILLINER ING. MARCELA BELLANI LIC. HÉCTOR CONRADO

MATEMATICA DISCRETA

GRAFOS Y DIGRAFOS
Nota a los alumnos: En las primeras 4 páginas hemos adoptado el formato de dos columnas para facilitar la comparación entre los elementos de un Grafo y unDigrafo. A partir de la pág. 6 sólo nos referimos a grafos.

COORDINADORA DE CÁTEDRA: C.C. ALICIA CICCINI

GRAFO Definición : Llamamos grafo a toda terna G = (V , A, ϕ ) donde : V : V ≠ φ conjunto de vértices . A: A ≠ φ conjunto de aristas. Función ϕ : A → V * / V * = {H ⊆ V / H = 1 ∨ H = 2} de incidencia Ejemplo: a1 v1 a3 a6 a2 a4 v2 a5

DIGRAFO Definición: Llamamos digrafo a toda terna G= (V , A, δ ) donde; V: V ≠ φ conjunto de vértices. A: A ≠ φ , conjunto de aristas.

δ : A → VXV
Ejemplo: a2 v1

Función de incidencia dirigida

a3 v2

a1 a4 v4 a6 Elementos : a5 a7 v3

v4 a7 Elementos : 1) Diremos que un vértice si v ∈ ϕ (a ) . Ej.: v1 es extremo de a1 .

v3

v ∈ V es extremo de una arista a ∈ A

1) diremos que v ∈ V es vértice inicial de a ∈ A si ∃w ∈ V / δ (a) = (v, w) ; y v ∈ V es vértice final de a ∈ A si ∃w ∈ V / δ (a ) = ( w, v) Ej.: v1 inicial de a2 y final de a1 . 2) Diremos que una arista llega a v si ∃w ∈ V / δ (a ) = ( w, v) ; y sale de v si ∃w ∈ V / δ (a ) = (v, w) .

2) Se dice que un vértice v y una arista a son incidentes si v ∈ ϕ (a) .

2

3) Una arista es un lazo si ϕ (a) = 1 . 4) Dos aristas a1 y a 2 son paralelas si ϕ (a1 ) = ϕ(a 2 ) . Ej.: a6 y a4. 5) Dos aristas no paralelas son adyacentes si ∃v ∈ V / ϕ (a1 ) ∩ ϕ (a 2 ) = {v} Ej.: a3 y a7. 6) Dos vértices son adyacentes cuando existe una arista que los une ∃a ∈ A / ϕ (a ) = {v1 , v 2 } . Ej.: v4 y v3. 7) Un grafo es simple cuando no tiene lazos ni aristas paralelas. Grado o valencia : de v ∈ V es el número de aristas incidentes en v . (el lazo se cuenta 2).Observación: gr (v) = 0 ⇒ v es vértice aislado.
gr (v) = 1 ⇒ v es vértice colgante. gr (v) = k ∀v ∈ V ⇒ G se llama k − regular .

3) Una arista es un lazo si δ (a ) = (v, v). 4) Dos aristas a1 y a 2 son paralelas si δ (a1 ) = δ (a 2 ) . Ej.: a2 y a4. Dos aristas a1 y a 2 son contraparalelas si δ (a1 ) = (v, w) ⇒ δ (a 2 ) = ( w, v) Ej.: a1 y a 2 . 5) Dos aristas no paralelas son adyacentes si δ (a1 ) = (w1 , v) y δ (a 2 ) = (v.w2 ) Ej.: a6 y a7 . 6) Dos vértices son adyacentes cuando ∃a ∈ A / δ (a) = (v1 , v 2 ) Ej.: v1 y v3. 6) Un digrafo es simple cuando no posee lazos ni aristas paralelas. Grado positivo : Número de aristas que llegan a v gr + (v) Grado negativo : Número de aristas que salen de v gr − (v) Grado total: gr + (v) + gr − (v) = gr (v) Grado neto: gn(v) = gr + (v) − gr − (v)Propiedades:

Propiedad:

∑ gr (v ) = 2 A
i =1 i

n

∑ gr

+

(vi ) = ∑ gr − (vi )
i

∑ gr (v ) = 2 A ∑ gn(v ) = 0
i

3

Relación de adyacencia : Ra ⊆ VXV
vi Rv j ⇔ vi y v j son adyacentes

Relación de incidencia : Ri ⊆ AXV

1 si (vi , v j ) ∈ R Ma =  0 si (vi , vj ) ∉ R
Ejemplo : (ejercicio 2a)

 1 si a j llega a vi  Mi = − 1 si a j sale de vi  0 si (a , v ) ∉ R j ii 

Ejemplo: (ejercicio 12a)
a1 a6 a2

v1
a b c d a b c d e 1 0 1 0 1 0 1 1 1 1 1 0 0 1 0 1 1 0 1  1 1 ⇒ Ma = 0 1 0  1 0 1 1  1 0 e 1 0 1 1 0 1 1 1  1 0 1 0  1 1 0 1 1 0 1 0  a5

v2 v3
a3 a4

v5 v4
Ejercicio 11: a2

Para hallar la función ϕ debemos nombrar las aristas:

v1 a
a6 a5 a7 a8 a3 a4 a1

v2
a5 a3 a4

b
a2 a1

c v3 v4
a6

e d

4

x

a1a2

a3

a4

a5

a6

a7

a8

ϕ (x)

{a, b} {b, c} {c, d } {d, e} {e, a} {a, d } {e, b} {b, d }

Nótese que la imagen de una arista es un conjunto de vértices y no un par ordenado ya que éstas no tienen orientación alguna por tratarse de un grafo. Comparar con la función δ (x) dada en el ejercicio 11. NOTA IMPORTANTE : De aquí en adelante abandonaremos el formato en dos...