OM

TEORÍA DE GRAFOS

.C
DD
Contenidos:
•

LA
Elementos principales de un grafo.
• Grafos: simples, planos y conexos.
FI
• Matrices de incidencia y adyacencia.
• Recorridos eulerianos.


Matemática 2 online. Cátedra Zorzoli 1

Este archivo fue descargado de [Link]
 Teoría de Grafos

OM
Un grafo es una terna ordenada por medio de la cual se establecen relaciones entre los diferentes
elementos que constituyen un sistema o conjunto. Son muy utilizados en la vida cotidiana cuando
queremos representar en una forma acotada y sencilla las relaciones entre los objetos.

.C
Un grafo G se indica de la siguiente manera: G = ( V, A;𝝋)

DD
Conjunto de Vértices o nodos. Relación existente entre Vértices y Aristas.

Conjunto de Aristas que relacionan los nodos.

LA
Grafo G
A
FI a B
c b El grafo G está formado por:
g C 5 vértices
f
7 aristas

d
𝝋 = 𝑨, 𝑩 ; 𝑨, 𝑬 ; 𝑩, 𝑪 ; 𝑩, 𝑫 ; 𝑩, 𝑫 ; 𝑪, 𝑫 ; 𝑫, 𝑬
E e D

Matemática 2 online. Cátedra Zorzoli 2

Este archivo fue descargado de [Link]
Ejercicio 1

OM
Considerá el grafo que se presenta a continuación y respondé:
A a B
b C G
j

.C
c d e
g
E

DD
D f
i
h F

LA
1) ¿Qué elementos lo componen?. Enumeralos e indicá el grado de cada uno de sus vértices.
2) ¿Se trata de un grafo simple?
3) ¿Es un grafo plano?
FI
4) ¿Es conexo?
5) ¿Cuáles son sus matrices de adyacencia y de incidencia?


6) ¿Admite recorridos eulerianos?

Este archivo fue descargado de [Link]

 1) ¿Qué elementos lo componen?. Enumeralos e indicá el grado de cada uno de sus vértices.

OM
A a B
b C G
j

c d e

.C
g
E
Grado de un vértice: estará
D

DD
f
i dado por el número de
h F
aristas que inciden en él.

LA
Vértices = 7 A, B, C, D, E, F, G
Aristas = 10 a, b, c, d, e, f, g, h, i, j
FI Grado de los Vértices
A B C D E F G

3 3 2 4 3 4 1

Matemática 2 online. Cátedra Zorzoli 4

Este archivo fue descargado de [Link]
 Este grafo no es simple porque posee una arista múltiple
2) ¿Se trata de un grafo simple?
entre los vértices A y D y además tiene un lazo en el

OM
vértice F.
A a B
b C G Un grafo es simple cuando no existen múltiples
j
aristas entre cada par de vértices y/o no contiene
c d e bucles o lazos. Dicho de otra forma, es un grafo

.C
g que no contiene lazos ni aristas múltiples.
E

DD
f
i
h F

3) ¿Es un grafo plano? Este grafo es plano porque, como se puede observar, sus aristas solo
se cruzan en sus vértices. Un grafo es plano cuando puede ser dibujado sin

LA
que sus aristas se crucen.
La condición necesaria y suficiente para que un
grafo sea plano, es que no contenga como subgrafo
al grafo K3,3 ni al grafo K5. (Teorema de Kuratowski).
FI
4) ¿Es conexo? Este grafo es conexo, porque desde cualquier
Un grafo es conexo cuando desde cualquier
vértice es posible llegar a cualquier otro a través

vértice es posible llegar, por medio de una
de una cadena cadena a otro vértice.

Matemática 2 online. Cátedra Zorzoli 5

Este archivo fue descargado de [Link]
5) ¿Podrías construir sus matrices de adyacencia vértices y de incidencia?

OM
A a B
b C G
j

c d e
g

.C
E

D f
i Matriz de adyacencia

DD
h F
de Vértices
Adyacencia de Vértices A B C D E F G
Matriz que tiene 𝑛 filas por 𝑛 columnas, siendo 𝑛 el A 0 1 0 2 0 0 0 3

LA
número de vértices. Si se trata de un grafo simple, en B 1 0 1 0 1 0 0 3 Grado de los
el cruce entre una fila y una columna se escribe un 1 C 0 1 0 0 0 0 1 2 vértices
si los vértices son adyacentes y un 0 si no lo son. Si se
FI D 2 0 0 0 1 1 0 4
presentan lazos y/o aristas múltiples se evaluarán las
conexiones de esos vértices. E 0 1 0 1 0 1 0 3

F 0 0 0 1 1 2 0 4
G 0 0 1 0 0 0 0 1
3 3 2 4 3 4 1
Matemática 2 online. Cátedra Zorzoli
Este archivo fue descargado de [Link]
5) ¿Podrías construir sus matrices de adyacencia y de incidencia?

OM
A a B
b C G
j

c d e Matriz de incidencia
g

.C
E
A B C D E F G
D f
i a 1 1 0 0 0 0 0

DD
h F
b 0 1 1 0 0 0 0
c 1 0 0 1 0 0 0
Incidencia

LA
Matriz que tiene 𝑛 filas y 𝑘 columnas, donde cada fila d 1 0 0 1 0 0 0
corresponde a una arista y cada columna a un vértice. e 0 1 0 0 1 0 0
Cada fila suma
En el lugar de cruce de la fila con la columna se escribe
FI f 0 0 0 0 1 1 0 2
un 1 si la arista incide en el vértice y un 0 si no hay g 0 0 0 1 1 0 0
incidencia. En el caso de encontrarnos con un lazo se h 0 0 0 1 0 1 0
colocará un 2 para indicar que la arista se conecta dos

i 0 0 0 0 0 2 0
veces con el mismo vértice.
j 0 0 1 0 0 0 1
Grado de los
3 3 2 4 3 4 1
Matemática 2 online. Cátedra Zorzoli vértices
7
Este archivo fue descargado de [Link]
6) ¿Admite recorridos eulerianos? Este grafo no admite recorridos eulerianos porque
posee 4 vértices de grado impar.

OM
A a B
b C G
j Al incorporar la arista que une los
c d e vértices E y G (color verde, porque

.C
g no pertenece al grafo original) el
E grafo obtenido admite recorrido
D euleriano restringido.

DD
f
i
h F

Un grafo admite recorrido euleriano cuando se lo puede recorrer pasando una única vez por cada arista.

LA
✓ Recorrido euleriano general: el vértice donde se inicia el recorrido coincide con el de finalización y en este
caso todos los vértices del grafo son de grado par.
✓ Recorrido euleriano restringido: el vértice donde se inicia el recorrido no coincide con el de finalización y en
FI
este caso el grafo tiene solo dos vértices de grado impar. En estos vértices es donde comienza y finaliza el
recorrido.


Matemática 2 online. Cátedra Zorzoli 8

Este archivo fue descargado de [Link]
 Ejercicio 2
Se plantea la construcción de una vivienda con las siguientes restricciones:

OM
➢ Un único dormitorio que posee baño en suite. D B
➢ Un living-comedor con salida al exterior. L-C Todo, a excepción del baño en suite,
➢ Un toilette. T se conecta por medio de un hall de H
➢ Una cocina-comedor diario. C-CD distribución.

.C
a) Realizá un esquema en el que se muestren los ambientes de la vivienda y confeccioná el

DD
grafo asociado a la estructura circulatoria de la misma.
b) Construí el grafo de vecindades (considerando la contigüidad de los ambientes).
En ambos casos no olvides incluir el vértice Ext. que representa al exterior.

LA
B
T
D
L-C
FI Ext.
H


C-CD

Matemática 2 online. Cátedra Zorzoli 9

Este archivo fue descargado de [Link]
 Ejercicio 2

OM
a) Confeccioná el grafo asociado a la estructura circulatoria de la vivienda

.C
B B
T T

DD
D D
Ext. Ext.
L-C
H L-C
H

LA
C-CD C-CD
FI
Estructura circulatoria


Matemática 2 online. Cátedra Zorzoli 10

Este archivo fue descargado de [Link]
 b) Construí el grafo de vecindades (considerando la contigüidad de los ambientes)

OM
Grafo de vecindades interior Grafo de vecindades completo

.C
B

DD
B
T T
D L-C D L-C Ext.

LA
H H

C-CD
FI C-CD


Matemática 2 online. Cátedra Zorzoli 11

Este archivo fue descargado de [Link]
 Grafo circulatorio Grafo de vecindades

OM
B

.C
B T
T D L-C Ext.

DD
D
Ext.
L-C H
H

LA
C-CD
C-CD
FI
Grafo: simple, plano y conexo que No admite recorrido Grafo: simple, plano y conexo que admite recorrido

euleriano porque tiene cuatro vértices de grado impar. euleriano restringido porque posee dos vértices de
Vértices: B, T, C-CD y Ext. todos de grado 1. grado impar. Vértices: D y Ext. ambos de grado 5.

Matemática 2 online. Cátedra Zorzoli 12

Este archivo fue descargado de [Link]