Matemáticas - Teoría de grafos

arista corresponde a una relación entre dos vértices de un grafo.

Para caracterizar un grafo G son suficientes únicamente el conjunto de todas sus aristas, comúnmente denotado con la letra E (del término en inglés edge), junto con el conjunto de sus vértices, denotado por V. Así, dicho grafo se puede representar como G(V,E), o bien G = (V,E).

En un grafo, dos vértices son adyacentes si están conectados por una arista. En tal caso, cada uno de estos vértices es incidente a dicha arista.

Gráficamente las aristas se representan, para el caso de los grafos no dirigidos, como una línea que une a los dos vértices. Si el grafo es dirigido, entonces la arista se representa como una flecha, que parte del nodo origen y apunta al nodo destino.

Algebraicamente, dados dos vértices a y b pertenecientes al conjunto V, una arista se define, para un grafo no dirigido, como el conjunto e = {a,b} (o {b,a}), en tanto que para un grafo dirigido, como el par ordenado e = (a,b) (donde (b,a) representaría una arista diferente, con el nodo origen y destino cambiados). En ambos casos, e ∈ E.

Por otro lado, también es normal que las aristas lleven asociadas una etiqueta (un número, una letra o un valor cualquiera) que indica una información asociada a ambos vértices, a veces uncoste o indicación del trabajo necesario para recorrer el camino de un vértice al otro.

No es obligatorio que todo vértice esté unido con otro por una arista. Tales vértices se llamanvértices o nodos aislados.

Tampoco es necesario que ambos nodos unidos por una arista sean distintos. Dado un vértice a, de existir una arista {a, a} o bien (a, a), entonces decimos que el grafo posee un bucle.

Representaciones gráficas de ungrafo no dirigido, de un grafo dirigido, y de un grafo dirigido etiquetado.

arista de corte o istmo es una arista que al ser eliminada en ungrafo incrementa el número de componentes conexas de éste. Equivalentemente, una arista es un puente si y sólo si no está contenida en ningún ciclo.

Un grafo sin puentes es equivalente a un grafo conexo con conectividad 2.

Un importante problema abierto que involucra puentes es el llamado Cycle Double Cover Conjecture ("Conjetura del Ciclo de Doble Cobertura"),¹ propuesto por Seymour y Szekeres (1978 y 1979, independientemente), que establece que todo grafo sin puentes admite un conjunto de ciclos que contiene cada arista exactamente dos veces.

Un grafo con 6 aristas de corte (marcadas en rojo)

aristas múltiples (también llamadas aristas paralelas o una multi-arista), son dos o más aristas que son incidentes (es decir, que conectan) a al menos dosvértices. Los grafos sin aristas múltiples son llamados grafos simples.

Dependiendo del contexto, un grafo puede definirse de manera que permita o no la presencia de aristas múltiples (del mismo modo que a veces se permite y a veces no la presencia de bucles):

• En un contexto en que se permiten la presencia de aristas múltiples y bucles, un grafo sin bucles es usualmente llamado multigrafo.¹
• En un contexto en que no se permiten aristas múltiples y bucles, un multigrafo o pseudografo es definido para referirse a un "grafo" que puede tener bucles y aristas múltiples.²

Las aristas múltiples son útiles, por ejemplo, en la consideración de redes eléctricas, desde un punto de vista de teoría de grafos.³

Un grafo planar permanece planar si es añadida una arista entre dos vértices ya unidos por una arista; por lo tanto, la agregación de aristas múltiples preserva la planaridad.

Cuando un grafo admite aristas múltiples, se llama multigrafo.

pathfinding en inglés, al trazado por una aplicación de computadora, del camino más corto entre dos puntos. Esta área de investigación está basado mayormente en el Algoritmo de Dijkstra para la búsqueda de la ruta más corta.

La búsqueda de ruta en el contexto de los videojuegos se refiere a la forma en que una entidad en movimiento encuentra un camino alrededor de un obstáculo; el contexto más frecuente se encuentra en los videojuegos de estrategia en tiempo real (en el que el jugador orienta las unidades en torno a un área de juego que contiene los obstáculos), pero esta modalidad se encuentra en los videojuegos más modernos. La importancia de la búsqueda de rutas ha crecido tanto en importancia como los entornos de los juegos se han vuelto cada vez más complejos, y como resultado, varios paquetes de software de IA ya han desarrollado los algoritmos para resolver el problema.

Los videojuegos de estrategia en tiempo real generalmente contienen grandes áreas de terreno abierto que suele ser relativamente fácil de atravesar, en el que es muy común que más de una unidad esté viajando a la vez; esto crea una necesidad diferente, y a menudo son necesarios algoritmos más complejos para evitar un atasco de tráfico en los puntos más circulados del mapa o terreno, o cuando las unidades están en contacto unas con otras. En los juegos de estrategia los mapas normalmente están divididos en tiles, que actúan como nodos en el algoritmo de pathfinding.

Géneros estructurados más abiertos, tales como los videojuegos de disparo en primera persona que a menudo tienen más áreas cerradas (o una mezcla entre abierta y cerrada) que no están tan simplemente divididos en nodos, ha dado lugar al uso de mallas de navegación. Estos son construidos por la colocación de nodos en el mundo del juego, que almacenan detalles de qué nodos son accesibles desde el mismo.

Rutas equivalentes entre A y B en un entorno 2D