Muestra las diferencias entre dos versiones de la página.
Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
algoritmos-oia:grafos [2018/01/05 21:39] santo [Representación en la computadora] |
algoritmos-oia:grafos [2018/07/05 14:25] (actual) santo [Representación en la computadora] |
||
---|---|---|---|
Línea 89: | Línea 89: | ||
Similarmente, el uso típico de las listas de adyacencia es recorrer los **vecinos** de un cierto nodo. En nuestro ejemplo, los vecinos del nodo $x$ solamente pueden ser $x-2, x-3, x-7, x+2, x+3$ o $x+7$. Basta entonces verificar cuáles de esos números están entre 1 y 100, y tendremos todos los vecinos de $x$, sin necesidad de armarse todas las listas de adyacencia completas de antemano (aunque podríamos). En casos como este hay incluso [[algoritmos-oia:grafos:bfs:distintas-movidas-en-tablero|trucos comunes]] para programar más fácilmente estos "movimientos". | Similarmente, el uso típico de las listas de adyacencia es recorrer los **vecinos** de un cierto nodo. En nuestro ejemplo, los vecinos del nodo $x$ solamente pueden ser $x-2, x-3, x-7, x+2, x+3$ o $x+7$. Basta entonces verificar cuáles de esos números están entre 1 y 100, y tendremos todos los vecinos de $x$, sin necesidad de armarse todas las listas de adyacencia completas de antemano (aunque podríamos). En casos como este hay incluso [[algoritmos-oia:grafos:bfs:distintas-movidas-en-tablero|trucos comunes]] para programar más fácilmente estos "movimientos". | ||
+ | === Aristas como entidad === | ||
+ | |||
+ | En los ejemplos anteriores, no almacenamos "la arista" en ningún lado, sino que tenemos directamente en cada lugar donde hace falta (la matriz, la lista de adyacencia , etc) directamente la información de la arista. En algunos problemas conviene guardar en la matriz o en las listas directamente "el índice" o "el puntero" a la arista en sí, sobre todo si esta tiene información que puede cambiar. En los casos más comunes hacer esta separación no es necesaria, pero como a veces puede ser útil o hasta necesario se explica este concepto [[algoritmos-oia:grafos:aristas-como-entidad|aquí]]. | ||
===== Algún ejemplito de problema ===== | ===== Algún ejemplito de problema ===== | ||
Línea 109: | Línea 112: | ||
Y estas son las únicas dos situaciones posibles, ya que si no empezamos desde un nodo sino desde el medio de una arista, y vamos desde ahí hacia un nodo, luego vamos a tener que hacer la otra parte de la arista y obviamente si podemos, podemos también empezar desde uno de estos nodos y terminar el mismo con el mismo camino. | Y estas son las únicas dos situaciones posibles, ya que si no empezamos desde un nodo sino desde el medio de una arista, y vamos desde ahí hacia un nodo, luego vamos a tener que hacer la otra parte de la arista y obviamente si podemos, podemos también empezar desde uno de estos nodos y terminar el mismo con el mismo camino. | ||
- | Entonces, sabemos que es condición necesaria que haya $2$ ó $0$ nodos que estén en una cantidad impar de aristas. Puede verse, pensando en esto de "salir" y "entrar" del nodo que es una condición necesaria. | + | Entonces, sabemos que es condición necesaria que haya $2$ ó $0$ nodos que estén en una cantidad impar de aristas. Puede verse, pensando en esto de "salir" y "entrar" del nodo que es una condición suficiente. |
Esto de "a cuántas aristas pertenece un nodo" se llama el **grado** de un nodo, y puede verse junto con otras definiciones [[algoritmos-oia/grafos/definiciones|acá]]. | Esto de "a cuántas aristas pertenece un nodo" se llama el **grado** de un nodo, y puede verse junto con otras definiciones [[algoritmos-oia/grafos/definiciones|acá]]. | ||