Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:grafos:definiciones [2018/01/05 18:06]
santo
+++ algoritmos-oia:grafos:definiciones [2018/01/05 18:36] (actual)
santo
@@ Línea 17: / Línea 17: @@
 //Grafo simple//: Un grafo no dirigido, sin autoejes ni multiejes.
-//Grado de un nodo//: Es la cantidad de aristas que tienen al nodo como extremo. Si el grafo es dirigido, se habla en su lugar de "grado de entrada" (que cuenta la cantidad de ejes que **entran** al nodo) y "grado de salida" (que cuentan la cantidad de ejes que **salen** del nodo). En un grafo dirigido con autoejes, estos suman uno tanto al grado de entrada como al grado de salid del nodo (porque "salen y entran" al mismo). Similarmente, en un grafo no dirigido con autoejes, la convención más usual es que un autoeje se cuenta "2 veces" para definir el grado de un nodo (porque lo toca "dos veces", una en cada extremo).
+//Grado de un nodo//: Es la cantidad de aristas que tienen al nodo como extremo. Si el grafo es dirigido, se habla en su lugar de //grado de entrada// (que cuenta la cantidad de ejes que **entran** al nodo) y //grado de salida// (que cuentan la cantidad de ejes que **salen** del nodo). En un grafo dirigido con autoejes, estos suman uno tanto al grado de entrada como al grado de salid del nodo (porque "salen y entran" al mismo). Similarmente, en un grafo no dirigido con autoejes, la convención más usual es que un autoeje se cuenta "2 veces" para definir el grado de un nodo (porque lo toca "dos veces", una en cada extremo). Se suele notar $d(v)$ al grado de $v$, $d^+(v)$ a su grado de salida de $v$, y $d^-(v)$ a su grado de entrada. A veces se define el //grado neto// de un nodo, como la diferencia $d^0(v) = d^+(v) - d^-(v)$. Si se estuviera trabajando con varios grafos al mismo tiempo, de manera tal que puede ser confuso en cuál se debe mirar el grado, se puede indicar debajo: Por ejemplo $d_G(v)$ sería el grado de $v$ en $G$, y $d^+_H(w)$ sería el grado de salida de $w$ en $H$.
+//Fuente// o //source//: Es un nodo en un grafo dirigido al cual no entran aristas: Es decir, su grado
+de **entrada** es $d^-(s) = 0$.
+//Sumidero// o //sink//: Es un nodo en un grafo dirigido del cual no salen aristas: Es decir, su grado de **salida** es $d^+(s) = 0$.
 //Camino//: Hay dos definiciones posibles de camino en un grafo, prácticamente equivalentes:
@@ Línea 56: / Línea 61: @@
 //Componente fuertemente conexa//: Una componente fuertemente conexa de un grafo dirigido, es un subgrafo fuertemente conexo maximal. No alcanza con mirar el subyacente, y [[algoritmos-oia:grafos-dirigidos:componentes-fuertemente-conexas-en-dirigidos|su cálculo]] es más complicado que el de las componentes conexas o débilmente conexas.
+//Grafo traspuesto//: El grafo traspuesto de un grafo dirigido $G$, que se suele notar $G^t$, es el grafo que se obtiene de $G$ invirtiendo el sentido de todas las aristas. Es decir, por cada arista $x \rightarrow y$ en $G$, se pone en $G^t$ una arista $y \rightarrow x$
+//Bosque//: Un bosque es un grafo no dirigido, sin **ciclos simples**.
+//Árbol//: Un bosque conexo. Notar que de esta definición y la anterior, cada componente conexa de un bosque es un árbol. Equivalentemente, un árbol es un grafo en el cual **existe un único camino simple** entre cada par de nodos. Notar que en un árbol no se puede hablar de "padres" ni de "hijos", a menos que se fije una raíz (ver //árbol con raíz//).
+//Hoja//: Es un nodo en un grafo no dirigido que tiene grado 1: $d(h) = 1$. Son especialmente importante en los árboles, ya que todo árbol no trivial tiene al menos dos hojas, y se puede "desarmar" todo el árbol "podando hojas" sucesivamente.
+//Á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 todo nodo hasta la raíz.
+  * 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).
+//Hoja en un árbol con raíz//: En un árbol con raíz, se utiliza una definición de hoja diferente a la de un grafo no dirigido habitual: Una hoja es un nodo **que no tiene hijos**. Notar que en un árbol con un único nodo, la raíz es una hoja en este caso, aunque tenga grado 0. Por otro lado, si la raíz tiene un único hijo, entonces no se la considera una hoja, a pesar de tener grado 1.
+//Nodo interno//: En un árbol (o en un árbol con raíz) se suelen llamar //nodos internos// o //nodos interiores//, a los nodos que no son hojas.
+//DAG// o //grafo dirigido acíclico//: Un DAG (directed acyclic graph) o grafo dirigido acíclico, es un grafo dirigido **sin ciclos**. Notar que el grafo subyacente podría estar lleno de ciclos, es decir no tiene por qué ser un bosque.
+//Grafo dirigido transitivo//: Un grafo dirigido se dice transitivo, si cada vez que hay una arista $A \rightarrow B$, y una arista $B \rightarrow C$, también se encuentra en el grafo una arista $A \rightarrow C$. Se denomina la //clausura transitiva// de un grafo dirigido $G$, al grafo que resulta de agregarle a $G$ las mínimas aristas posibles para que se vuelva transitivo. Equivalentemente, la clausura transitiva se obtiene con los mismos nodos, y poniendo un eje desde $x$ hasta $y$, si en el grafo $G$ existe un **camino** desde $x$ hasta $y$.

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página