Grafos

Matemáticas Discretas

Ejercicios de Grafos 1

1. Considera Μ y Ν las dos matrices adyacentes siguientes:
[pic]
a) Escribe explícitamente (conjunto de vértices, conjunto de aristas)V= {a,b,c,d,e}
A= {1,2,3,4}
b) Determina si son grafos conexos. Si no lo son determina sus componentes conexas.
No son grafos conexos. Sus componentes conexos son:
M={(a,b),(b,a)} y {(c,d),(c,e),(d,c),(d,e),(e,c)(e,d)}
c) Encuentra el grado de cada vértice utilizando la matriz
VA(M)=1 grado
VB(M)=1 grado
VC(M)=2 grados
VD(M)=2grados
VE(M)=2 grados
d) Dibuja los grafos

[pic][pic]

2. Considera los siguientes:
[pic]
a) ¿Cuáles son conexos? Si un grafo no es conexo, encuentra sus componentes conexas.El grafo 1,3 y 4 son conexos. El grafo 2 No es conexo, por tal motivo, sus componentes conexos son: {(a,d),(d,e),(e,a),(d,a),(e,d),(a,e)}
b) ¿Cuáles son grafos?
Tanto el 1,2,3 y 4 songrafos
c) ¿Cuáles no tienen lazos?
Los grafos 1,2 y 3 no tienen lazos

3. Construir un grafo de 5 vértices, los cuales tengan grados 1, 2, 2, 3, 4.
[pic]

4. ¿Cuántasaristas tiene un grafo (grafo simple) si sus vértices tienen los siguientes grados 4,3,3,2,2? Dibuja tal grafo.
Tiene 7 Aristas
[pic]

5. Considera el siguiente grafo:Encontrar:
a) Todos los caminos simples de A a F.
(A,B),(B,C),(C,F) y (A,D),(D,E),(E,F)
b) Todos los recorridos de A a F.
(A,B),(B,E),(E,C),(C,F) y (A,D),(D,E),(E,F)
c) Todos losciclos que incluyen el vértice A
1. (A,B),(B,C),(C,F),(F,E),(E,D),(D,A)
2. (A,B),(B,E),(E,D),(D,A)
3. (A,D),(D,E),(E,B),(B,A)
4.(C,B),(B,A),(A,D),(D,E),(E,F)(F,C)
5. (B,A),(A,D),(D,E),(E,B)
6. (D,A),(A,B),(B,E),(E,D)
7. (B,E),(E,D),(D,A),(A,B)
8. (D,E),(E,B),(B,A),(A,D)
9. (E,D),(D,A),(A,B),(B,E)
10....