Arista (teoría de grafos)
En teoría de grafos, una 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.
Representación
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 un coste 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 llaman vé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.
Véase también
Referencias
- Diestel, Reinhard (1997), Graph Theory (en inglés), Springer-Verlag, Nueva York.
| Control de autoridades |
|
|---|
Datos: Q3297804