Herramientas de usuario
algoritmos-oia:grafos:definiciones
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa | |||
|
algoritmos-oia:grafos:definiciones [2018/01/05 18:36] santo |
algoritmos-oia:grafos:definiciones [2018/01/05 18:36] (actual) santo |
||
|---|---|---|---|
| Línea 71: | Línea 71: | ||
| //Árbol con raíz//: Un árbol con raíz es un grafo dirigido, cuyo grafo subyacente es un árbol, y con una raíz distinguida, de manera tal que se cumpla una de las siguientes dos variantes: | //Árbol con raíz//: Un árbol con raíz es un grafo dirigido, cuyo grafo subyacente es un árbol, y con una raíz distinguida, de manera tal que se cumpla una de las siguientes dos variantes: | ||
| - | * Dirigido hacia la raíz: existe camino dirigido desde toda nodo hasta la raíz. | + | * Dirigido hacia la raíz: existe camino dirigido desde todo nodo hasta la raíz. |
| * Dirigido hacia las hojas: existe camino desde la raíz hasta cualquier otro nodo. | * Dirigido hacia las hojas: existe camino desde la raíz hasta cualquier otro nodo. | ||
| Notar que si en un árbol se fija uno de sus nodos como raíz, existe una única manera de convertirlo en un árbol con raíz dirigido hacia la raíz. Y su grafo traspuesto será la única forma de conseguir un árbol con raíz dirigido hacia las hojas. Esto hace que las dos formas de ver el árbol con raíz sean equivalentes. En la versión dirigida hacia la raíz, el nodo destino de la única arista saliente de un nodo $u$ que no sea la raíz se llama el //padre// de $u$. Similarmente, se dice que $u$ es //hijo// de $v$, si $v$ es el padre de $u$. El padre de un nodo es el primer nodo en el único camino hacia la raíz, y la raíz es el único nodo sin padre (muchas veces se toma la convención de que la raíz es su propio padre, pues puede resultar muy conveniente a la hora de implementar). | Notar que si en un árbol se fija uno de sus nodos como raíz, existe una única manera de convertirlo en un árbol con raíz dirigido hacia la raíz. Y su grafo traspuesto será la única forma de conseguir un árbol con raíz dirigido hacia las hojas. Esto hace que las dos formas de ver el árbol con raíz sean equivalentes. En la versión dirigida hacia la raíz, el nodo destino de la única arista saliente de un nodo $u$ que no sea la raíz se llama el //padre// de $u$. Similarmente, se dice que $u$ es //hijo// de $v$, si $v$ es el padre de $u$. El padre de un nodo es el primer nodo en el único camino hacia la raíz, y la raíz es el único nodo sin padre (muchas veces se toma la convención de que la raíz es su propio padre, pues puede resultar muy conveniente a la hora de implementar). | ||
algoritmos-oia/grafos/definiciones.1515177360.txt.gz · Última modificación: 2018/01/05 18:36 por santo
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
