Wikipedia

Diferencia entre revisiones de «Arista (teoría de grafos)»

Explorar historial interactivamente
← Ir a diferencia anteriorIr a siguiente diferencia →
Contenido eliminado Contenido añadido
VisualWikitexto
LucienBOT (discusión · contribs.)
185 543 ediciones
mejoro todo el artículo
Línea 1:
{{otros usos|Arista (desambiguación)}}
En [[teoría de grafos]], una '''arista''' corresponde a una [[relación matemática|relación]] entre dos [[vértice (teoría de grafos)|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)''.
[[Archivo:Ejemplos de aristas.png|thumb|200px|Imagen que muestra representaciones de los distintos tipos de aristas.]]
 
== Representación ==
En [[teoría de grafos]] las aristas, junto con los [[vértice (teoría de grafos)|vértices]], forman los elementos principales con los que trabaja esta disciplina, siendo consideradas las aristas las uniones entre [[nodo (teoría de grafos)|nodos]] o vértices (véase la primera figura). Usualmente las aristas denotan relaciones entre los vértices (vecindad, herencia, orden, etc.) y, como ejemplo, se usan para delimitar regiones en un [[Plano (geometría)|plano]] a partir de una nube de puntos (que serían los nodos).
[[Archivo:Ejemplos de aristas.png|thumb|Representaciones gráficas de un [[grafo no dirigido]], de un [[grafo dirigido]], y de un [[grafo etiquetado|grafo dirigido etiquetado]].]]
Gráficamente las aristas se representan, para el caso de los [[grafo no dirigido|grafos no dirigidos]], como una línea que une a los dos vértices. Si el grafo es [[grafo dirigido|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''.
Es normal que existan [[Grafo dirigido|grafos dirigidos]], en los que las aristas además de unir dos vértices suelen tener una dirección establecida (véase la segunda y tercera figura) de modo que a--->b sería una arista distinta que a<---b, pudiendo existir ambas en el mismo grafo a<===>b. Siendo estos [[grafo]]s conocidos como dirigidos.
 
Por otro lado, también en esta disciplina 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 (el camino de A a B puede tener un costo distinto que el de B a A, como se puede observar en la tercera figura de la imagen de la derecha).
 
No es obligatorio que todo vértice esté unido con otro por una arista. Tales vértices se llaman ''vértices'' o ''nodos aislados''.
Ambas informaciones se pueden combinar para formar un grafo dirigido con pesos (costes), tal y como se aprecia en la última figura de la imagen de la derecha.
 
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 (teoría de grafos)|bucle]].
Finalmente no existe obligación de que dados dos vértices exista una arista que las una.
 
== Véase también ==
 
* [[Vértice (teoría de grafos)|Vértice]]
 
* [[Grafo]]
== Referencias ==
* [[Teoría de grafos]]
* {{obra citada |título=Graph Theory |nombre=Reinhard |apellidos=Diestel |año=1997 |editorial=Springer-Verlag, Nueva York |idioma=inglés}}
 
[[Categoría:Teoría de grafos]]
Obtenido de «https://es.wikipedia.org/wiki/Arista_(teoría_de_grafos)»