Lista de Ejercicios Lenguajes Formales
Cristel garriazoTarea29 de Junio de 2023
1.198 Palabras (5 Páginas)131 Visitas
[pic 1]
[pic 2]
ESTRUCTURAS DISCRETAS II
Lista de Ejercicios Lenguajes Formales
1. Determine cuál de los siguientes grafos tienen circuitos de Euler. Si el grafo no tiene un circuito de Euler, explique por qué no. Si tiene un circuito de Euler, describa uno.
[pic 3]
Es Euleriano ya que todos los No es Euleriano ya que no todos
vértices del grafo son de grado los vértices son de grado par.
par además de ser conexo.
Circuito Euleriano:
<v1,e1,v2,e2,v5,e7,v4,e6,v5,e3,v2,e4,v3,e5,v4,e8,v1>
[pic 4]
Es Euleriano porque todos sus Es Euleriano ya que todos sus
vértices son de grado par y es vértices son de grado par y es
conexo. conexo.
[pic 5]
A pesar de tener todos los grados No es Euleriano ya que no todos
de los vértices de grado par no es los vértices poseen grado par y
Euleriano ya que no hay forma de no forma ni un circuito Euleriano
hacer un circuito Euleriano, y no es
convexo.
2. Para cada uno de los siguientes grafos, determine si hay una trayectoria de Euler de u a w. Si existe, encuentre dicha trayectoria.
[pic 6]
No hay trayectoria de Euler
Hay trayectoria de Euler:
<u,v1,v0,v7,u,v2,v3,v4,v2,v6,v4,w,v6,v5,w>
[pic 7]
Hay trayectoria de Euler:
<u,v1,v2,v3,u,v0,v7,v6,v3,v4,v6,w,v5,v4,w>
3. Para los siguientes grafos, encuentre los circuitos hamiltonianos para los grafos que los tengan. Explique por qué los otros grafos no los tienen.
[pic 8]
No es grafo hamiltoneano ya que Si es Hamiltoneano ya que
no posee circuito hamiltoneano posee circuito hamiltoneano:
Camino Hamiltoneano: <d,a,b,c,e,f,g,d>
<d,b,c,g,f,e,a>
[pic 9]
Si es Hamiltoneano ya que No es Hamiltoneano por que
Posee circuito hamiltoneano: no posee circuito hamiltoneano
<v1,v5,v4,v7,v6,v2,v3,v0,v1> Camino Hamiltoneano:
<b,a,e,h,g,f,c,d>
4. Encuentre las matrices de adyacencia para los siguientes grafos
[pic 10]
[pic 11][pic 12][pic 13][pic 14]
1 | 0 | 0 | 0 |
0 | 1 | 1 | 2 |
0 | 1 | 1 | 0 |
0 | 2 | 0 | 0 |
0 | 0 | 1 | 1 |
0 | 0 | 1 | 0 |
1 | 2 | 0 | 0 |
1 | 0 | 0 | 1 |
[pic 15]
0 | 2 | 1 |
2 | 0 | 0 |
1 | 0 | 0 |
[pic 16][pic 17][pic 18][pic 19]
1 | 0 | 2 | 0 |
0 | 0 | 2 | 0 |
2 | 1 | 0 | 2 |
0 | 0 | 2 | 0 |
5. De los siguientes grafos, determine si son conexos, realice los gráficos y encuentre A2 y A3
[pic 20]
[pic 21]
Si es conexo.
[pic 22]
0 | 2 | 2 | 2 |
0 | 1 | 1 | 1 |
0 | 1 | 1 | 1 |
0 | 1 | 2 | 0 |
[pic 23]
0 | 2 | 2 | 0 |
0 | 2 | 1 | 1 |
0 | 1 | 2 | 1 |
0 | 3 | 2 | 1 |
[pic 24][pic 25]
Si es Conexo
[pic 26]
1 | 4 | 1 | 0 |
2 | 2 | 4 | 0 |
5 | 4 | 3 | 0 |
0 | 1 | 0 | 0 |
[pic 27]
1 | 3 | 4 | 1 |
0 | 1 | 1 | 0 |
0 | 4 | 4 | 2 |
0 | 1 | 2 | 1 |
[pic 28][pic 29]
Si es conexo.[pic 30]
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
[pic 31]
0 | 1 | 0 |
1 | 0 | 0 |
0 | 0 | 0 |
[pic 32][pic 33][pic 34][pic 35]
0 | 1 | 0 |
1 | 0 | 0 |
0 | 0 | 0 |
[pic 36]
0 | 0 | 0 |
0 | 0 | 0 |
0 | 0 | 0 |
[pic 37][pic 38][pic 39]
[pic 40]
0 | 1 | 0 |
1 | 0 | 1 |
0 | 1 | 0 |
[pic 41][pic 42]
0 | 0 | 0 |
0 | 0 | 1 |
0 | 1 | 0 |
[pic 43][pic 44][pic 45]
1 | 0 | 0 | 0 |
0 | 1 | 0 | 0 |
0 | 0 | 0 | 2 |
0 | 0 | 2 | 0 |
[pic 46]
0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 |
0 | 0 | 0 | 1 |
0 | 0 | 1 | 0 |
6. Del siguiente grafo:
[pic 47]
a. ¿Cuántos caminos de longitud 2 existen de v2 a v3?
b. ¿Cuántos caminos de longitud 2 existen de v3 a v4?
...