INTRODUCCION GRAFOS DIGRAFOS ÁRBOLES

SALIR
 TEORIA DE GRAFOS

TEORIA
INTERDISCIPLINARIA
CIENCIAS FISICA
SOCIALES

QUIMICA
LINGUISTICA AMPLIA GAMA
DE APLICACIONES INGENIERIA

ARQUITECTURA

INFORMATICA
COMUNICACIONES

SALIR
 MODELAR
GRAFOS SE UTILIZAN PARA SITUACIONES

MODELO:

ES UNA

REPRESENTACION SIMPLIFICADA

DEBE TENER DEBE IGNORAR

EN CUENTA

CARACTERISTICAS DETALLES
RELEVANTES INNECESARIOS

SALIR
DEFINICION INFORMAL

conjunto de PUNTOS o NODOS

GRAFO:
unidos por ARISTAS.

SALIR
 VER
DEFINICION FORMAL de GRAFO DEFINICION
INFORMAL

Un grafo es una terna G=(V,A,)

CONJUNTO FUNCION DE
DE VERTICES INCIDENCIA
CONJUNTO
V≠
DE ARISTAS  : A  V(2)

VER EJEMPLO V(2) es el conjunto formado por

subconjuntos de 1 o 2 elementos de V,
que son los extremos de la arista.

SALIR
 EJEMPLO:

Sea el grafo G =( V, A,  ) siendo los conjuntos:

V = { v1, v2, v3 , v4 , v5 } A = { a1 , a2 , a3, a4 , a5 }

Y la función de incidencia:  (a1)={v1, v2} ,  (a2) ={v3} ,

 (a3)={v4,v2} ,  (a4)={v1,v3 } ,  (a5)={ v1, v2}

¿QUIERES VER COMO SE PUEDE DIAGRAMAR?

a5
a3
a1 v2
v4
v1 a2
a4
v3 v5

SALIR
Otras DEFINICIONES de GRAFOS

VERTICES ADYACENTES GRADO O VALENCIA

ARISTAS ADYACENTES REPRESENTACION

MATRICIAL DE GRAFOS
ARISTAS INCIDENTES
EN UN VERTICE CAMINOS Y CICLOS

ARISTAS PARALELAS GRAFOS REGULARES

VERTICE AISLADO GRAFOS BIPARTITOS

BUCLES O LAZOS GRAFOS CONEXOS

GRAFO SIMPLE ISOMORFISMOS

SALIR
VERTICES ADYACENTES vi es adyacente a vj 
 ak  A tal que  (ak) = { vi ,vj }

¿QUE SIGNIFICA ESTO?

Que son vértices que están

EJEMPLO: unidos por alguna arista
a5
a3
a1 v2
v4
v1 a2 v2 es adyacente a v1 y a v4
pero no a v3
a4
v3 v5

SALIR
 vi es aislado   vk  V :
VERTICE AISLADO Si vi  vk . : vi no es adyacente a vk

¿QUE SIGNIFICA ESTO?

Que es un vértice que no es

adyacente a ningún otro.
EJEMPLO:
a5
a3
a1 v2
v4
v1 a2
a4
v3 v5 v5 es aislado

SALIR
ARISTAS PARALELAS ai es paralela a ak   (ai) =  (ak)

¿QUE SIGNIFICA ESTO?

Que son aristas comprendidas

entre los mismos vértices.
EJEMPLO:
a5
a3
a1 v2
v4
v1 a2
a5 y a1 son paralelas ya que
a4
ambas están comprendidas
v3 v5 entre los vértices v1 y v2.

SALIR
 ai es paralela a ak 
ARISTAS ADYACENTES |  (ai)   (ak) | = 1

¿QUE SIGNIFICA ESTO?

Que son aristas que tienen un

único vértice en común.
EJEMPLO:
a5
a3
a1 v2
v4
v1 a2
a3 y a1 son adyacentes ya que
a4 el único vértice en común entre
v3 v5 ambas es v2.

SALIR
 ai es BUCLE O LAZO 
BUCLES O LAZOS |  (ai) | = 1

¿QUE SIGNIFICA ESTO?

Que son aristas con ambos

extremos en el mismo vértice.
EJEMPLO:
a5
a3
a1 v2
v4
v1 a2
a4 a2 es BUCLE pues ambos extremos
de ella es el vérticev3.
v3 v5

SALIR
ARISTAS INCIDENTES ai es INCIDENTE a vk  vk   (ai)
EN UN VERTICE

¿QUE SIGNIFICA ESTO?

Que son aristas las aristas que

tienen a dicho vértice por extremo.
EJEMPLO:
a5
a3
a1 v2
v4
Las aristas a1, a3 y
v1 a2 a5 son incidentes en
el vértice v2
a4
v3 v5

SALIR
GRAFO SIMPLE G es simple si y sólo si no tiene
aristas paralelas ni bucles.

EJEMPLOS: a5
a3
a1 v2
v4
v1 a2
Este grafo NO es simple
a4
v3 v5

2 3 4

Este grafo SI es simple

1 5

SALIR
 REPRESENTACION MATRICIAL DE GRAFOS:

Sea un grafo G = (V, A, )

con V = { v1, v2,  , vn } y A = { a1, a2,  , am }

Se pueden definir dos matrices:

MATRIZ DE MATRIZ DE
ADYACENCIA INCIDENCIA

DEFINICION Y EJEMPLO DEFINICION Y EJEMPLO

SALIR
MATRIZ DE ADYACENCIA MATRIZ BOOLEANA de n x n

cuyos elementos 1 si vi es adyacente a v j

Ma(G) mij
0 si vi no es adyacente a v j

¿QUE SIGNIFICA ESTO?

Que la matriz de adyacencia es una matriz cuadrada, las filas y las

columnas representan los vértices, y los valores de los elementos son 1 si
ambos vértices son adyacentes, y valen 0 en caso de no serlo.

VER EJEMPLO

SALIR
 EJEMPLO:

Dado este grafo:

a6

a3 a7
2 3 4

a8
a1
a4 a5
1 a2 5
0 1 0 1 1
 
1 0 1 1 0
La matriz de adyacencia es: Ma(G) =
0 1 0 1 1
 
1 1 1 0 1
1 0 1 1 0 


SALIR
MATRIZ DE INCIDENCIA MATRIZ BOOLEANA de n x m

cuyos elementos 1 si vi es extremo de aj

Mi(G) mij
0 si vi no es extremo de aj

¿QUE SIGNIFICA ESTO?

Que la matriz de incidencia es una matriz rectangular, las filas representan

los vértices, y las columnas representan las aristas, y los valores de los
elementos son 1 si el vértice es extremo de la arista, y valen 0 en caso de
no serlo.

VER EJEMPLO

SALIR
 EJEMPLO:

Dado este grafo:

a6

a3 a7
2 3 4

a8
a1
a4 a5
1 a2 5

1 1 0 1 0 0 0 0
 
1 0 1 0 0 1 0 0
La matriz de incidencia es: Mi(G) = 
0 0 1 0 0 0 1 1
 
0 0 0 1 1 1 1 0
 
0 1 0 0 1 0 0 1

SALIR
 GRADO O VALENCIA

Sea un grafo G = ( V, A,  )
g(vi) = cantidad de aristas incidentes en vi
Función grado: g: V  N0
Nota: los bucles se cuentan doblemente.

EJEMPLO:
a5
a3 Los grados de los
a1 v2 vértices son:
v4 g(v1) = 3
v1 g(v2) = 3
a2 g(v3) = 3
a4 g(v4) = 1
g(v5) = 0
v3 v5

SALIR
 PROPIEDAD

En todo grafo se cumple que la suma de los grados de los vértices

es igual al doble de la cantidad de aristas.

En símbolos:
 g(v )= 2  A 
i

EJERCICIO

¿Cuál es la cantidad total de vértices de un grafo que tiene 2 vértices de grado

4, uno de grado 3, 5 de grado 2 y el resto colgantes (de grado 1) sabiendo que
en total hay 12 aristas?

VER SOLUCION

SALIR
 EJERCICIO

¿Cuál es la cantidad total de vértices de un grafo que tiene 2 vértices de grado

4, uno de grado 3, 5 de grado 2 y el resto colgantes (de grado 1) sabiendo que
en total hay 12 aristas?

SOLUCION:

Usando la propiedad anterior: 2  4 + 1  3 + 5  2 + x  1 = 2  12

Resolviendo: 21 + x = 24  x = 3 (cantidad de vértices colgantes)

Por lo tanto la cantidad total de vértices es:  V  = 2 + 1 + 5 + 3 = 11

UNA forma posible de dibujar
este grafo sería:

¿Te animas a dibujar otras posibilidades?

SALIR
 CAMINOS Y CICLOS EN GRAFOS:

CAMINO sucesión de aristas adyacentes distintas

CICLO (o circuito) camino cerrado (vértice inicial = vértice final)

LONGITUD de un camino cantidad de aristas que lo componen

CAMINO SIMPLE si todos los vértices son distintos

VER EJEMPLO CAMINOS ESPECIALES

SALIR
 EJEMPLO:
En el siguiente grafo: G =(V,A, φ ) con V = {1, 2, 3, 4, 5, 6, 7},
A={a, b, c, d, e, f, g, h, i, j}, busquemos caminos entre los vértices
“1” y “6”, e indiquemos la longitud de cada uno de ellos:
d

2 5
b c
a
3 e
h 7
i g
f
1 4 6

VER SOLUCION

SALIR
 Un posible camino es: C1= ( 1, a, 2, b, 3, f, 6 )
d

2 5
b c
a
3 e
h 7
i g
f
1 4 6

j La longitud de este camino es: long[C1] = 3

¿Este camino es SIMPLE?

Sí, este camino es SIMPLE pues no repite vértices.

VER OTRO CAMINO

SALIR
Otro posible camino es: C2 = ( 1, i, 4, j, 4, h, 3, c, 5, e, 6 )
d

2 5
b c
a
3 e
h 7
i g
f
1 4 6

j La longitud de este camino es: long[C2] = 5

¿Este camino es SIMPLE?

NO, este camino NO es SIMPLE pues repite el vértice 4.

VER CICLOS
SALIR
Un posible ciclo es: C1 = ( 1, a, 2, b, 3, h, 4, i, 1)
d

2 5
b c
a
3 e
h 7
i g
f
1 4 6

j La longitud de este ciclo es: long[C1] = 4

¿Este ciclo es SIMPLE?

Sí, este ciclo es SIMPLE pues no repite vértices.

VER OTRO CICLO

SALIR
Otro posible ciclo es: C2 = ( 3, c, 5, e, 6, f, 3 )
d

2 5
b c
a
3 e
h 7
i g
f
1 4 6

j La longitud de este ciclo es: long[C2] = 3

¿Este ciclo es SIMPLE?

Sí, este ciclo es SIMPLE pues no repite vértices.

VER OTRO CICLO

SALIR
Otro posible ciclo es: C3 = ( 1, a, 2, b, 3, c, 5, e, 6, f, 3, h, 4, i, 1 )
d

2 5
b c
a
3 e
h 7
i g
f
1 4 6

j La longitud de este ciclo es: long[C3] = 7

¿Este ciclo es SIMPLE?

No, este ciclo NO es SIMPLE pues repite el vértice 3.

CAMINOS ESPECIALES

SALIR
 CAMINOS Y CICLOS ESPECIALES

Hay unos tipos de caminos especiales, que son muy importantes por
sus aplicaciones:

CAMINOS Y CICLOS CAMINOS Y CICLOS

EULERIANOS HAMILTONIANOS

DEFINICION Y EJEMPLO DEFINICION Y EJEMPLO

SALIR
 CAMINOS Y CICLOS EULERIANOS

CAMINO DE EULER camino que pasa por todas las aristas

CICLO DE EULER Ciclo que pasa por todas las aristas del grafo

La condición necesaria y suficiente para que en un grafo exista camino euleriano es:
El grafo debe ser conexo, y
todos los vértices deben tener grado par, o a lo sumo dos grado impar.

La condición necesaria y suficiente para que en un grafo exista ciclo euleriano es:
El grafo debe ser conexo, y todos los vértices deben tener grado par.

VER EJEMPLO

SALIR
 CAMINOS Y CICLOS HAMILTONIANOS

camino simple que pasa por

CAMINO DE HAMILTON
todos los vértices

ciclo simple que pasa por

CICLO DE HAMILTON
todos los vértices

Observación: no necesariamente va a pasar por todas las aristas,

pues en muchos casos repetiría vértices y no sería hamiltoniano.

VER EJEMPLO

SALIR
 GRAFOS REGULARES

G es k-regular   v  V : g(v) = k
GRAFO K-REGULAR
Con k  N0

EJEMPLO:
2 Este grafo es 2-regular pues todos
Los vértices tienen grado 2.

1 3

5 4

VER GRAFOS Kn

SALIR
 ISOMORFISMOS DE GRAFOS

Dados dos grafos: G1 = ( V1, A1, 1) y G2 = ( V2, A2, 2)

Se dice que son isomorfos si y solo si existen dos funciones biyectivas
f: V1  V2 y g : A1  A2 tales que:  a  A1 : 2( g(a) ) = f( 1(a) )
Si no hay aristas paralelas, entonces es suficiente:
 u, v  V1 : {u, v}  A1  { f(u), f(v) }  A2
Esto significa que si en el primer grafo hay una arista entre dos vértices, los corres-
pondientes a estos vértices en el segundo grafo también deben estar unidos por
una arista.
En pocas palabras, dos grafos son isomorfos cuando tienen la misma estructura,
es decir sus vértices están relacionados de igual forma aunque estén dibujados
de manera distinta.

VER condiciones VER EJEMPLO

SALIR
 DEFINICION FORMAL de DIGRAFO

Un digrafo es una terna G=(V,A, )

CONJUNTO FUNCION DE
DE VERTICES CONJUNTO INCIDENCIA
V≠ DE ARISTAS
DIRIGIDAS  : A  VXV

Observaciones:
La función de incidencia  le hace corresponder a cada arista un PAR ORDENADO
de vértices, al primero se lo llama EXTREMO INICIAL de la arista, y el segundo es
el VERTICE FINAL.
Los caminos y los ciclos se definen de la misma forma que para los grafos
no dirigidos, pero hay que respetar el sentido de las aristas.

VER EJEMPLO

SALIR
 DEFINICION de ARBOL

Un ARBOL es un grafo conexo y sin ciclos.

Condición necesaria y suficiente:
Un árbol es un grafo en el cual entre todo par de vértices existe un único
camino simple.
Propiedades básicas de los árboles:
• Al agregar una arista entre dos vértices de un árbol, deja de ser árbol.
• Todas las aristas de un árbol son puentes.
• En todo árbol se cumple que: V = A + 1

BOSQUE: es un grafo no conexo en el cual cada una de las componentes

es un árbol.
Propiedad: En un bosque de k componentes: V = A + k

VER EJEMPLO

SALIR
 CAMINOS Y CICLOS HAMILTONIANOS

EJEMPLO: A

B C

D E

Un posible ciclo hamiltoniano es: (A, B, D, F, E, C, A)

SALIR
CAMINOS Y CICLOS EULERIANOS

Este grafo no tiene ciclo euleriano

pues hay dos vértices de grado 3.
Tiene solo camino euleriano.

Este grafo tiene ciclo euleriano pues

todos sus vértices tienen grado par.

SALIR
 GRAFOS BIPARTITOS

Sea un grafo simple G = ( V, A,  ) con V ={ v1, ..., vn } y A ={ a1, ..., am }

G es BIPARTITO  V = V1 U V2 con V1    V2    V1  V2 = 

  ai  A :  (ai) = { vj , vk } con vj  V1  vk  V 2

O sea, los grafos BIPARTITOS son grafos cuyo conjunto de vértices

está particionado en dos subconjuntos: V1 y V2 tales que los vértices
de V1 pueden ser adyacentes a los vértices de V2 pero los de un
mismo subconjunto no son adyacentes entre sí.

VER EJEMPLO

VER GRAFOS Kn,m

SALIR
 GRAFOS COMPLETOS Kn

Sea n  N : Kn = ( V, A,  ) tal que:

 v, w  V: v  w   a  A :  (a) = { v, w }
O sea, los Kn son grafos simples de n vértices en los cuales cada vértice
es adyacente a todos los demás.

EJEMPLOS: K5
K4
K3

EJERCICIO: En una fiesta hay 8 personas que en un determinado

momento llenan sus copas de sidra y brindan entre ellos, todos con todos.
¿Cuántos choques de copas hay en total?

VER SOLUCION
SALIR
Solución:

Podemos considerar en K8, donde los vértices son las personas y

las aristas representan los choques de copas, ya que cada persona
choca su copa con todos los demás excepto con sí mismo.

Utilizando la propiedad:  g(vi)= 2 A 

Como todos los vértices tienen grado 7, nos queda:

87=2A   A  = 28

En total hay 28 choques de copas.

Para pensar:
1)¿Los Kn son grafos k-regulares? ¿Con qué valor de k?
2)¿Qué particularidad tienen las matrices de adyacencia de
los grafos Kn?

SALIR
 EJEMPLO:

En el siguiente grafo, cuyo conjunto de vértices es: V = { 1, 2, 3, 4, 5 }

Si consideramos los subconjuntos: 1

V1 = { 1, 2, 3 } V2 = { 4, 5 } 4
2
Vemos que todas las aristas que hay,
tienen un extremo en V1 y el otro en V2. 5
Por lo tanto es BIPARTITO. 3

Nota: la definición no exige que deba haber arista entre todo par de
vértices (uno de V1 y el otro de V2 ) sino que dice que las aristas que
existan deben estar comprendidas entre un vértice de cada subconjunto.
En este ejemplo, no hay arista entre 2 y 4, la cual estaba permitida.

SALIR
 GRAFOS CONEXOS

RELACION DE CONEXIÓN:

Dado un grafo G = ( V, A, ), en el conjunto V se define la siguiente relación:

vi R vj   camino de vi a vj  vi = vj
Esta relación es de equivalencia y por lo tanto pueden hallarse las clases
de equivalencia, a las que se denomina COMPONENTES CONEXAS.

GRAFO CONEXO:

Un grafo es conexo si y sólo si tienen una única componente conexa.

Un grafo es conexo si y sólo si existe algún camino entre todo par de vértices.

DESCONEXION
VER EJEMPLO DE GRAFOS

SALIR
 GRAFOS BIPARTITOS COMPLETOS Kn,m

Son grafos bipartitos de n+m vértices con TODAS las aristas posibles.

EJEMPLOS:
K3,3
K3,2

La cantidad de aristas de un grafo Kn,m es n • m

SALIR
 GRAFOS CONEXOS

EJEMPLOS:

t
Este grafo es conexo ya que de cualquier
x vértice se puede llegar a cualquier otro a
través de un camino.
z

y w u
e

Este grafo NO es conexo pues b

por ejemplo no existe ningún
camino entre los vértices a y c.
c
a d f

VER COMPONENTES
SALIR
 GRAFOS CONEXOS

Sin embargo, está formado por dos subgrafos que cada uno de ellos
sí es conexo, se llaman COMPONENTES CONEXAS:

Una componente conexa:

La otra componente conexa:

a d

c
f

SALIR
 CONDICIONES NECESARIAS PARA QUE DOS GRAFOS SEAN ISOMORFOS:

Deben tener la misma cantidad de vértices.

Deben tener la misma cantidad de aristas.

Deben tener los mismos grados de los vértices.

Deben tener caminos de las mismas longitudes.

Si uno tiene ciclos, el otro también debe tenerlos.

Etc.

Observación: las condiciones mencionadas son necesarias (es decir que sí o sí se

deben cumplir para que los grafos san isomorfos) pero no son suficientes
( o sea que aunque se cumplan puede ser que los grafos no sean isomorfos)
Para estar seguros que dos grafos son isomorfos,
una condición que es suficiente es que tengan la misma matriz de adyacencia.

VER EJEMPLO

SALIR
 EJEMPLO:

Analicemos si los siguientes grafos son isomorfos:

G1: B y G2: Z

D
W
A

X Y
C

Solución:
Ambos tienen 4 vértices y 5 aristas.
Definamos la función biyectiva, haciendo corresponder los
vértices con iguales grados:
f(A) = Y ; f(B) = Z ; f(C) = X ; f(D) = W

SALIR
 En la definición decía que si entre dos vértices del primer grafo había una
arista, también debía haber arista entre los vértices correspondientes en
el segundo grafo.
Por ejemplo entre A y B hay una arista en G1, y también hay una arista
entre f(A) y f(B) en G2.
Esto mismo habría que revisar para cada arista, ello se puede hacer todo
junto con la matriz ORDENANDO CONVENIENTEMENTE los vértices:

A B C D Y Z X W
A 1 1 1 0 Y 1 1 1 0
B 1 0 1 1 Z 1 0 1 1
C 1 1 0 0 X 1 1 0 0
D 0 1 0 0 W 0 1 0 0

Como las matrices son iguales podemos asegurar que G1 es isomorfo a G2.

SALIR
 DESCONEXION DE GRAFOS
Ver subgrafos
~Gv
Dado un grafo G = ( V, A,  ) conexo

ISTMO O PUNTO
v  V es istmo  ~Gv es no conexo
DE CORTE

O sea, un istmo es un vértice tal que al suprimirlo desconecta al grafo

PUENTE a  A es puente  ~Ga es no conexo

O sea, un puente es una arista tal que al suprimirla desconecta al grafo

CONJUNTO
B  A es desconectante  ~GB es no conexo
DESCONECTANTE

O sea, un conjunto de aristas es deconectante si al suprimirlo desconecta

SALIR
 CONJUNTO B  A es de corte  B es desconectante y
DE CORTE además  C  B, C no es desconectante

O sea, un conjunto de aristas es de corte si al suprimirlo desconecta al grafo, pero

ningún subconjunto propio debe hacerlo, es decir, el conjunto de corte está formado
únicamente por las aristas necesarias para desconectar y no por otras.

EJEMPLO: 4
1 a b
c
3
f e d
2 5 6

ISTMOS: vértice 3 y vértice 5. PUENTES: arista d, arista a y arista b.

CONJUNTOS DESCONECTANTES: B1 = { b, e } , B2 = { a, f, e } , etc.

De los dos conjuntos anteriores B1 es DE CORTE

SALIR
 SUB-GRAFOS

Dado un grafo G = ( V, A,  ) , se denomina subgrafo al grafo

G’ = ( V’, A’, /A’ ) tal que V’  V  A’  A  /A’ es la función 
restringida a A’.

Para obtener subgrafos de un grafo dado se puede:

• suprimir uno o varios vértices y las aristas incidentes en ellos

• suprimir solamente una o varias aristas.

Si se suprime un vértice v, el subgrafo restante es ~Gv

Si se suprime un vértice a, el subgrafo restante es ~Ga

También se puede obtener un subgrafo generado por un conjunto de

vértices.

VER EJEMPLOS

SALIR
 EJEMPLO:

Dado el grafo: G = ( V, A ,  )
b e

c
g

a d f

Algunos subgrafos son:

~Ga,e,g: ~Gc:
b
b e
c
g
d f
a d f

SALIR
 EJEMPLO:

V = { w1, w2, w3 , w4 } A = { a1, a2, a3, a4, a5, a6 }

(a1)=(w1,w2) (a2)=(w2,w3) (a3)=(w4,w4)
(a4)=(w2,w1) (a5)=(w4,w1) (a6)= (w2,w3)

Se puede diagramar de la siguiente forma:

a3
a4

w1
a5 Extremo inicial de a5: w4
a2 a1
w4 Extremo final de a5: w1
w3
w2 BUCLE: a3
a6
ARISTAS PARALELAS: a2 y a6
ARISTAS ANTIPARALELAS: a1 y a4
CAMINO: C = ( w4, a5, w1, a1, w2, a2, w3)

Camino simple: si todos los vértices son distintos.

Camino elemental: si todas las aristas son distintas.

SALIR
 FUNCION GRADO EN UN DIGRAFO

GRADO POSITIVO cantidad de arcos que “entran” al vértice. Se denota g+(v)

GRADO NEGATIVO cantidad de arcos que “salen” del vértice. Se denota g-(v)

GRADO TOTAL suma de los grados positivo y negativo. Se denota g(v)

GRADO NETO Diferencia entre grado positivo y negativo. Se denota gN(v)

Propiedades:
VER EJEMPLO
 g+(vi)=A ;  g-(vi)=A
 g(vi) = 2  A  ;  gN(vi) = 0
¿Qué es un POZO
y una FUENTE?

SALIR
 EJEMPLO:
a3
a4

a5
a2 a1 w1
w4
w3
w2
a6

Grados positivos:
g+(w1) = 2 ; g+(w2) = 1 ; g+(w3) = 2 ; g+(w4) = 1
Grados negativos:
g-(w1) = 1 ; g-(w2) = 3 ; g-(w3) = 0 ; g-(w4) = 2
Grados totales:
g(w1) = 3 ; g(w2) = 4 ; g(w3) = 2 ; g(w4) = 3
Grados netos:
gN(w1) = 1 ; gN (w2) = -2 ; gN (w3) = 2 ; gN (w4) = -1

SALIR
 POZO es un vértice v tal que g-(v) = 0

O sea, v no es extremo inicial de ninguna arista.

FUENTE es un vértice v tal que g+(v) = 0

O sea, v no es extremo final de ninguna arista.

EJEMPLO:
w1
w4
w3
w2

w1 es POZO, y w2 es FUENTE.

SALIR
 REPRESENTACION MATRICIAL DE DIGRAFOS:

Sea un digrafo simple G = (V, A, )

con V = { v1, v2,    , vn } y A = { a1, a2,  , am }

MATRIZ DE ADYACENCIA MATRIZ BOOLEANA de n x n

1 si a  A : (a)  (vi , v j)
Ma(G) cuyos elementos mij 
 0 en caso contrario

MATRIZ DE INCIDENCIA MATRIZ BOOLEANA de n x m

1 si vi es vértice inicial de a j


Mi(G) cuyos elementos mij - 1 si vi es vértice final de a j
0 si vi no es extremo de a j



VER EJEMPLO

SALIR
EJEMPLO:
a6
a9

a3 a7
2 3 4 0 1 0 1 1
 
a8
0 1 1 1 0
Ma(G) = 0
a1 0 0 0 0
a4 a5  
0 0 1 0 0
a2
1 5 0 0 1 1 0 


1 1 0 1 0 0 0 0 
 
 1 0 1 0 0 1 0 0 
Mi(G) =  0 0  1 0 0 0  1  1 
 
0 0 0 1 1 1 1 0 
 
 0 1 0 0 1 0 0 1 

SALIR
 GRAFO ASOCIADO A UN DIGRAFO

Dado un digrafo, si se cambian las aristas dirigidas por aristas no dirigidas,

se obtiene el grafo asociado. Es decir hay que ignorar el sentido de las aristas.
Si en el digrafo original hay aristas paralelas o antiparalelas,
en el grafo asociado sólo se representa una de ellas.

EJEMPLO:

Digrafo: Grafo asociado:

SALIR
 CONEXIDAD EN DIGRAFOS
Ver GRAFO
ASOCIADO
DÍGRAFO CONEXO: es todo aquel cuyo grafo asociado sea conexo.

DÍGRAFO FUERTEMENTE CONEXO: es todo aquel en el que exista

algún camino entre todo par de vértices.

EJEMPLOS:
B Este digrafo si bien es
A
conexo, NO es FUERTE-
MENTE CONEXO, ya que
C D por ejemplo no existe
camino alguno que salga del
vértice C y llegue al vértice
E B.

Lo que sí hay son dos COMPONENTES

Este dígrafo es conexo y FUERTEMENTE CONEXAS:
además es fuertemente conexo. C D
B
A

SALIR
 CAMINOS DE EULER Y HAMILTON EN DIGRAFOS

Se definen de forma similar que para grafos no dirigidos, pero hay que respetar
el sentido de las aristas.

Condición necesaria y suficiente para que exista ciclo de Euler en un digrafo:

 v  V : g+(v) = g-(v)

EJEMPLO: 1
A B
5 2
6
4
D
C
3

En este digrafo existe ciclo de Euler: C = (A,1,B,2,D,3,C,4,B,5,C,6,A)

y un posible ciclo de Hamilton: C = (A,1,B,2,D,3,C,6,A)

SALIR
 ISOMORFISMOS DE DIGRAFOS

Es lo mismo que para grafos, pero hay que tener en cuenta el sentido
de las aristas.

EJEMPLO:
D2 A D
5 4
D1

B E
3
6

1 2 C F

Estos dos digrafos son isomorfos?

VER SOLUCION
SALIR
 SOLUCION:
Si definimos la función: f : V1  V2 tal que f(1) = A ; f(2) = D ;
f(3) = B ; f(4) = E ; f(5) = C ; f(6) = F
y construimos las matrices de adyacencia:

Matriz de D1 Matriz de D2
1 2 3 4 5 6 A D B E C F
1 0 1 0 1 0 1 A 0 1 0 1 0 1
2 0 0 0 0 0 0 D 0 0 0 0 0 0
3 0 1 0 1 0 1 B 0 1 0 1 0 1
4 0 0 0 0 0 0 E 0 0 0 0 0 0
5 0 1 0 1 0 1 C 0 1 0 1 0 1
6 0 0 0 0 0 0 F 0 0 0 0 0 0

Como las matrices son iguales, entonces los dígrafos son isomorfos.

SALIR
 EJEMPLOS:

¿Cuáles de los siguientes grafos son árboles?

G1 G2 G3 G4

SOLUCION:

G1 no es árbol pues tiene un ciclo de longitud 3.

G3 no es árbol pues no es conexo.
G2 y G4 sí son árboles.

SALIR
 ARBOLES DIRIGIDOS

Un digrafo simple es un árbol dirigido si su grafo asociado es un árbol.

De los árboles dirigidos nos interesa estudiar los árboles con raíz.

ARBOL DIRIGIDO CON RAIZ

Es un árbol dirigido en el cual el grado entrante (positivo) de cada

vértice es igual a 1, salvo un único vértice con grado positivo igual
a cero, llamado raíz.

EJEMPLOS:
Indica cuales de los siguientes árboles dirigidos tienen raíz:

SALIR
 ELEMENTOS DE UN ARBOL

Un vértice v de un árbol se dice que es HOJA cuando g(v) = 1

Los VERTICES INTERNOS son todos aquellos que no son la raíz ni las hojas.

Se llama RAMA a todo camino que va desde la raíz a alguna hoja.

OTRAS DEFINICIONES

v es antecesor de w  existe un único camino simple de v a w.

w es sucesor de v en el caso anterior
v es padre de w  existe una arista de v a w.
w es hijo de v en el caso anterior.
v y w son hermanos si tienen el mismo padre.

VER EJEMPLO

SALIR
 EJEMPLO:

a
RAIZ

b c

d e f g h PADRE de l y m

i j k l m

o p
HOJAS

HOJAS que son HIJOS de C

HOJAS

SALIR
 El nivel de la raíz es cero: n(r) = 0
NIVEL DE UN VERTICE Cada vértice tiene un nivel más que su padre:
si p es padre de v  n(v) = n(p) + 1

ALTURA DE UN ARBOL Es el mayor NIVEL alcanzado por las HOJAS.

ARBOL BALANCEADO Si todas las hojas están en el nivel h o h-1

Un árbol con raíz es n-ario   v  V : g-(v)  n

ARBOL n-ario
Es decir, cada vértice puede tener a lo sumo n hijos.

ARBOL n-ario REGULAR Si todos los vértices tienen la misma cantidad

de hijos, salvo las hojas que no tienen hijos.

ARBOL n-ario REGULAR Si además de ser n-ario regular, todas

PLENO o COMPLETO las hojas se hallan en el mismo nivel.

Si n=2 entonces se dice árbol BINARIO.

Si n=3 entonces se dice árbol TERNARIO.

SALIR
 RECORRIDOS DE ARBOL

¿Qué significa RECORRER UN ARBOL?

Significa nombrar todos los vértices del árbol siguiendo un determinado orden.
Las siguientes son las definiciones recursivas de los recorridos de árboles:

ORDEN PREVIO O ORDEN SIMETRICO ORDEN

PRE-ORDEN O IN-ORDEN POSTERIOR O
POST-ORDEN

VER EJEMPLO
SALIR
RECORRIDOS DE ARBOL

EJEMPLO: a

b c

d e f g

h i j

k l

Recorrido en orden previo: a b d e h i k l c f g j

Recorrido en orden simétrico: d b h e k i l a f c j g
Recorrido en orden posterior: d h k l i e b f j g c a

SALIR
 REPRESENTACION DE EXPRESIONES ALGEBRAICAS

¿Cómo se representan expresiones algebraicas mediante árboles?

Si  es una operación binaria, el resultado de operar a con b se representa
de la siguiente forma:


a b

El operador es la raíz y los operandos son los hijos o subárboles.

Si leemos este árbol en orden simétrico, obtenemos la expresión usual: a  b

Cuando representamos expresiones algebraicas, son comunes los siguientes

nombres:
Notación Polaca: es el orden PREVIO
Notación usual o infija: es el orden SIMETRICO
Notación polaca inversa: es el orden POSTERIOR

VER EJEMPLO
SALIR
 ¿Para qué se usa la notación polaca inversa?
Por ejemplo, algunas calculadoras, utilizan notación
polaca inversa para resolver las operaciones. Disponen
de un stack o pila, en la que van almacenando los
operandos, y a medida que se ingresa un operador,
calculan el resultado de los dos últimos elementos de
la pila, dejando el resultado en su lugar.

¿Sabes qué es una pila?

Una pila es una lista de elementos, en la cual se van
agregando nuevos elementos por un extremo y se sacan por
el mismo extremo. Se las llama LIFO (Last In First Out)

¿Cómo se resuelve una operación?

Por ejemplo, si tienes que resolver 2/[(4+3)  (9-23)] con una de
esas calculadoras, lo debes hacer en notación polaca inversa, o sea
orden posterior.

VER OPERACION

SALIR
Lo leemos en notación polaca inversa: 2 4 3 + 9 2 3  -  /

1) Al ingresar el 2, como es un operando lo guarda en la pila:

2) Luego viene el 4 y lo guarda también:
3) Lo mismo ocurre al ingresar el 3: 3
4) Pero al ingresar el + , como es un operador, 8
2
extrae los dos últimos elementos de la pila, en este 39
1
caso, entre el 4 y el 3, los opera y dicho resultado 4
7
lo coloca en la pila:
5) Al ingresar el 9 lo coloca en la pila, como así 0.2857
2
también al 2 y al 3:
6) Cuando ingresamos el  , extrae los dos últimos elementos de la
pila, en este caso el 2 y el 3, realiza la operación ( 2 al cubo) y la
coloca en la pila:
7) Con el - hace lo mismo, toma el 9 y el 8, los resta y el resultado
lo pone en la pila:
8) Al ingresar el signo  , opera los dos últimos que hay ahora,
el 7 y el 1, el resultado lo coloca en la pila:
9) Por último, con el signo / hace lo mismo, operando el 2
y el 7, y quedando el resultado final en la base de la pila:

SALIR