Diferencias

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

--- algoritmos-oia:grafos:definiciones [2018/01/05 18:00]
santo
+++ algoritmos-oia:grafos:definiciones [2018/01/05 18:20]
santo
@@ Línea 8: / Línea 8: @@
 //Grafo dirigido// o //digrafo//: Es un grafo en el cual importa la dirección en la cual apuntan las aristas. Es decir, $A-B$ y $B-A$ son aristas totalmente diferentes, ya que una sale de $A$ y llega a $B$, mientras que la otra sale de $B$ y llega hasta $A$.
+//Grafo subyacente//: El grafo subyacente de un grafo dirigido, es el grafo no dirigido que resulta de "ignorar" todas las direcciones de las aristas. Es decir, tiene los mismos nodos, y las mismas aristas, pero sin que importe ya la dirección (se borran las "flechas" del dibujo, cambiando a "rayas").
 //Loop//, //bucle//, //autoeje// o //rulo//: Es un eje que tiene ambos extremos iguales: en el dibujo, es un "rulo" sobre un cierto nodo. Pueden estar tanto en un grafo dirigido, como en un grafo no dirigido.
@@ Línea 15: / 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 45: / Línea 52: @@
 //Grafo conexo//: Un grafo es conexo, cuando para cualquier par de vértices del grafo, existe un camino que va de uno a otro.
-//Componente conexa//: Una componente conexa de un grafo, es un **subgrafo conexo maximal**. Es decir, un subgrafo de $G$, que sea conexo, y que si le agregamos cualquier otra cosa de $G$, ya deja de ser conexo. Si lo imaginamos en un dibujo, es cada una de las "partes" o "pedazos" en que $G$ está dividido.
+//Componente conexa//: Una componente conexa de un grafo **no dirigido**, es un **subgrafo conexo maximal**. Es decir, un subgrafo de $G$, que sea conexo, y que si le agregamos cualquier otra cosa de $G$, ya deja de ser conexo. Si lo imaginamos en un dibujo, es cada una de las "partes" o "pedazos" en que $G$ está dividido.
+//Grafo débilmente conexo//: Un grafo **dirigido** se dice débilmente conexo, cuando **el subyacente** es conexo (es decir, si ignoramos las direcciones, todos los nodos están conectados en una sola componente).
+//Componente débilmente conexa//: Una componente débilmente conexa de un grafo dirigido, es un subgrafo débilmente conexo maximal. Son exactamente lo mismo que las componentes conexas del grafo subyacente.
+//Grafo fuertemente conexo//: Un grafo **dirigido** se dice fuertemente conexo, si para todo par de nodos $a,b \in V$, existe un camino **desde $a$ hacia $b$**. Es decir, se puede viajar desde cualquier nodo hasta cualquier otro, **en ambas direcciones**.
+//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.
+//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.
+//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