Arista (Teoría de Grafos)
En la teoría de grafos, una arista es una conexión entre dos vértices, que representa una relación o enlace entre ellos.
Definition
Una arista en un grafo es una línea que conecta dos vértices, representando una relación entre esas dos cosas; las aristas pueden llevar información adicional, una arista ponderada podría representar distancia o costo, y una arista dirigida (flecha) representa una relación de una sola vía. Formalmente, una arista $\{u, v\}$ (no dirigida) o $(u, v)$ (dirigida) conecta los vértices $u$ y $v$, un grafo ponderado asigna un peso numérico $w(e)$ a cada arista, y un grafo simple no tiene autolazos ni aristas múltiples entre el mismo par. En el formalismo del conjunto de aristas, $E \subseteq \{\{u,v\}: u,v \in V, u \neq v\}$ para grafos simples no dirigidos; la conectividad de aristas $\lambda(G)$ es el número mínimo de aristas cuya eliminación desconecta $G$, y por el teorema de Menger es igual al número máximo de caminos disjuntos en aristas entre cualesquiera dos vértices.
Example
En un mapa de vuelos, cada ruta de vuelo es una arista que conecta dos vértices de aeropuerto; en una red de amistad, cada amistad es una arista. El algoritmo de camino más corto de Dijkstra encuentra el camino desde el origen hasta el destino con peso total de arista mínimo, requiriendo pesos no negativos. El número cromático de aristas (índice cromático) $\chi'(G)$ es el número mínimo de colores necesarios para que ningún par de aristas incidentes comparta color; el teorema de Vizing dice que $\chi'(G)$ es o bien $\Delta(G)$ o $\Delta(G)+1$, donde $\Delta$ es el grado máximo.
Key Insight
La densidad de aristas $|E|/|V|^2$ va de $0$ (grafo vacío) a $1$ (grafo completo); las redes del mundo real como internet y las redes sociales son dispersas pero con una estructura local interesante. El teorema de Vizing divide los grafos en clase 1 ($\chi' = \Delta$) y clase 2 ($\chi' = \Delta+1$); determinar a qué clase pertenece un grafo es NP-difícil en general, vinculando la coloración de aristas con la complejidad computacional.