grafos _ conceptos_basicos

Vista previa del material en texto

UNSL MATEMATICA DISCRETA 2018
TRABAJO PRACTICO
Grafos
Conceptos Básicos
1. Explique por qué ninguna de los grafos de la figura 1 tiene una trayectoria del vértice a al vértice
a que pasa por cada arista exactamente una vez.
a
b
cd
e
a b c
def
ghi
Figura 1
2. Pruebe que cada uno de los grafos de la figura 2 tiene una trayectoria del vértice a al vértice a que
pasa por cada arista exactamente una vez, encontrando dicha trayectoria por inspección.
a
b
cd
e
f
a b c
d
e
f
gh
i
Figura 2
3. Para cada uno de los siguientes grafos G � pV,Eq de la figura 3:
(a) Especifique los conjuntos V y E.
(b) Encuentre (si hubiera) un par de vértices adyacentes.
(c) Encuentre (si hubiera) todos los grupos de aristas paralelas.
(d) Encuentre (si hubiera) todos los lazos.
(e) Encuentre (si hubiera) todos los vértices aislados.
(f) Determine si G es un grafo simple.
4. Hallar una relación de recurrencia y una fórmula expĺıcita para el número de aristas de Kn, inspec-
cionando dibujos de los grafos correspondientes a valores pequeños de n.
5. En cada ı́tem de la figura 4, determine si el grafo dibujado es bipartito. En caso de serlo, especifique
los conjuntos disjuntos de vértices mencionados en la definición de grafo bipartito.
6. Dibuje K1,3, K2,3 y K3,3. Deduzca una fórmula expĺıcita para el número de aristas en Km,n.
1
UNSL MATEMATICA DISCRETA 2018
v1
v2 v3
v4
e5
e1
e2
e6
e3
e4
v1
v2
v3
Figura 3
a b c
d e
a
b
c
d e
a b c d
e f g h
i
j k
Figura 4
7. El Grafo de Intersecciones de una familia de conjuntos A � tA1, A2, . . . , Anu es el grafo que tiene
a A como conjunto de vértices y para k, j : tAk, Aju es una arista si Ak X Aj � ∅. Construir el
grafo de intersecciones de las familias
(a) A1 � t�k | k P Nu, A2 � t2k | k P Zu, A3 � t2k� 1 | k P Zu, A4 � t3k | k P Zu, A5 � t�1, 0, 1u.
(b) B1 � tx P R |x   0u, B2 � tx P R | � 1   x   0u, B3 � tx P R | 0   x   1u, B4 � tx P
R | � 1   x   1u, B5 � tx P R | � 1   xu, B6 � R.
8. Para el grafo representado en la figura 5:
(a) Encuentre una trayectoria de longitud mı́nima de d a f .
(b) Encuentre una trayectoria de longitud mı́nima de d a f que pase por cada vértice exactamente
una vez.
a
b c
d e f
Figura 5
9. Para el grafo ponderado representado en la figura 6:
(a) Encuentre una trayectoria de longitud mı́nima de b a d.
(b) Encuentre una trayectoria de longitud mı́nima de b a d que pase por cada vértice exactamente
una vez.
10. Considere el grafo de la figura 7: Para cada uno de los siguientes ı́tems, determine si la trayectoria
que se indica es:
(a) una trayectoria simple
(b) un ciclo
(c) un ciclo simple
2
UNSL MATEMATICA DISCRETA 2018
a
b
c
d e
8
2
4 6
6
12 9
3
5
4
Figura 6
(1) pb, bq.
(2) pa, d, c, d, eq.
(3) pb, c, d, a, b, e, d, c, bq.
(4) pa, d, c, b, eq.
(5) pdq.
a b
c
d
e
Figura 7
11. En cada ı́tem, dibuje un grafo que tenga las propiedades indicadas o explique por qué no existe tal
grafo.
(a) Seis vértices, cada uno de grado 3.
(b) Cuatro vértices, cada uno de grado 1.
(c) Cuatro aristas; cuatro vértices de grados 1, 2, 3 y 4.
(d) Grafo simple; seis vértices de grados 1, 2, 3, 4, 5 y 5.
(e) Grafo simple; cinco vértices de grados 2, 2, 4, 4 y 4.
12. En cada grafo de la figura 8, encontrar todos los subgrafos que tienen al menos un vértice del grafo
dado, representarlos mediante un dibujo y dar el conjunto de vértices y de aristas .
a
b c
a b
Figura 8
13. Para cada grafo de la figura 9, determinar si tiene un ciclo de Euler. Si lo tiene, mostrar uno.
14. Analizar y responder:
(a) Un grafo completo Kn, ¿cuándo contiene un ciclo de Euler?
(b) Un grafo bipartito Km,n, ¿cuándo contiene un ciclo de Euler?
3
UNSL MATEMATICA DISCRETA 2018
a b
c d e
fg
a
b
c
d
e
f
g
h
i
j
a b
c
d
e
Figura 9
n vértices
m vértices
Figura 10
15. ¿Para qué valores de m,n P N, el grafo de la figura 10 tendrá un ciclo de Euler
16. (a) Demuestre que si G � pV,Eq es un grafo conectado con una arista e que se encuentra en
un ciclo, el grafo G̃ � pV,E � teuq (que se obtiene eliminando en G la arista e) sigue siendo
conectado.
(b) Dé un ejemplo de un grafo conectado tal que la eliminación de cualquier arista (sin eliminar
los vértices incidentes en ella) produzca un grafo no conectado.
17. Sea n P N y r, s P N0 tales que n � r � s y s es par. Mostrar que existe un grafo G de orden n con
r vértices de grado par y s vértices de grado impar.
18. Sea G � pV,Eq un grafo y sea C � tpv, wq P V � V | existe una trayectoria de v a wu. Demostrar
que C es una relación de equivalencia sobre V pGq.
19. Un vértice v en un grafo conectado G es un punto de articulación si la eliminación de v y todas las
aristas incidentes en v desconecta a G.
(a) Dé un ejemplo de un grafo conectado con seis vértices que tenga exactamente dos puntos de
articulación.
(b) Dé un ejemplo de un grafo conectado con seis vértices que no tenga puntos de articulación.
(c) Demuestre que un vértice v en un grafo conectado G es un punto de articulación si y sólo si
existen vértices w, x P V pGq con la propiedad de que toda trayectoria de w a x pasa por v.
20. Si G es un grafo bipartito de orden v y tamaño e, entonces e ¤ v2{4.
21. Un grafo no trivial G se llama irregular si ningún par de vértices tiene el mismo grado. Probar que
no hay grafos irregulares.
4