Herramientas de usuario
algoritmos-oia:grafos
Diferencias
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:38] santo |
algoritmos-oia:grafos [2018/07/05 14:25] (actual) santo [Representación en la computadora] |
||
|---|---|---|---|
| Línea 87: | Línea 87: | ||
| Por ejemplo, la matriz de adyacencia se usa accediendo a posiciones $(i,j)$ para ver si hay arista entre $i$ y $j$. En nuestro ejemplo, en lugar de usar una matriz, para ver si hay arista entre $i$ y $j$ podemos simplemente hacer la diferencia ''abs(j-i)'', y ver si es 2, 3 o 7 para decidir allí mismo si hay arista. Esto podría programarse incluso en una función, ''hayArista(int i,int j)'', que funcionaría como si fuera la matriz de adyacencia, pero sin tener que armarla. | Por ejemplo, la matriz de adyacencia se usa accediendo a posiciones $(i,j)$ para ver si hay arista entre $i$ y $j$. En nuestro ejemplo, en lugar de usar una matriz, para ver si hay arista entre $i$ y $j$ podemos simplemente hacer la diferencia ''abs(j-i)'', y ver si es 2, 3 o 7 para decidir allí mismo si hay arista. Esto podría programarse incluso en una función, ''hayArista(int i,int j)'', que funcionaría como si fuera la matriz de adyacencia, pero sin tener que armarla. | ||
| - | 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á]]. | ||
algoritmos-oia/grafos.1515188334.txt.gz · Última modificación: 2018/01/05 21:38 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
