Lista de Ejercicios Lenguajes Formales
Enviado por Cristel garriazo • 29 de Junio de 2023 • Tareas • 1.198 Palabras (5 Páginas) • 78 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]
...