Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es...
-
Upload
carolina-rico-pereyra -
Category
Documents
-
view
228 -
download
0
Transcript of Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es...
![Page 1: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/1.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
Otra DefiniciónDefinición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos.
En efecto, un árbol es un pequeño grafo conectado con n vértices.
![Page 2: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/2.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
Árboles
![Page 3: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/3.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
Definiciones equivalentes de Árboles
• Es un grafo conectado sin ciclos• Es un grafo conectado donde |E|=|V|-1• Es un grafo donde removiendo algún arco, alguna
hoja queda desconectada.• Es un grafo donde existe un único y simple camino
entre dos vértices
![Page 4: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/4.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
![Page 5: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/5.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
![Page 6: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/6.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
Definición Recursiva
![Page 7: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/7.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
Se procede a definir la recursividad en términos de versiones simples de alguna regla particular.
• Caso Base : Corresponde a la definición de los casos simples.
• Inducción : Corresponde a la construcción de los casos, dependiendo de los casos simples
![Page 8: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/8.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
![Page 9: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/9.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
Lema: Cada x que está en S, posee el mismo número de a’s que de b’s.
Demostrar por Inducción Estructural sobre la definición de S.
![Page 10: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/10.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
Demostración: Sea
EQ={ strings con la misma cantidad de a y de b}
![Page 11: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/11.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
![Page 12: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/12.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
![Page 13: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/13.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
Tipos de Datos RecursivosÁrbol Binario Recursivo
![Page 14: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/14.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
![Page 15: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/15.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
![Page 16: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/16.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
![Page 17: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/17.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
![Page 18: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/18.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
![Page 19: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/19.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
![Page 20: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/20.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
![Page 21: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/21.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
![Page 22: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/22.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
![Page 23: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/23.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
Caso Inductivo: HacerDer, se aplica lo mismo que en HacerIzq
![Page 24: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/24.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182
![Page 25: Matemáticas para Ciencias de la Computación MCC3182 Otra Definición Definición 2: Un árbol es un grafo conectado con n vértices y n-1 arcos. En efecto,](https://reader033.fdocumento.com/reader033/viewer/2022051418/5665b4971a28abb57c927554/html5/thumbnails/25.jpg)
Matemáticas para Ciencias de la ComputaciónMCC3182