Aresta (teoría de grafos)

En teoría de grafos, unha aresta, tamén chamada ligazón ou liña, é unha conexión entre dous vértices dun grafo. Estes dous vértices son os extremos da aresta. Un vértice que ten unha orientación (vértice orientado) chámase máis frecuentemente arco ou frecha. Na teoría de autómatas, as arestas chámanse transicións.

Un grafo cuxos vértices son todos non dirixidos dise que son non orientados, e un grafo cuxos vértices están todos dirixidos dise que está orientado ou dirixido; se só se orientan certas arestas, dise que o grafo é mixto.
miniatura| Un grafo dirixido con tres vértices e catro frechas (dúas delas representadas sobre a mesma liña). 
O conxunto de arestas dun grafo chámase comunmente , ás veces sendo frechas chámase . O conxunto de vértices chámase :

 un grafo non dirixido é unha parella G = (V, E);
 un grafo dirixido é unha parella G = (V, A);
 un grafo mixto é unha terna G = (V, E, A).

Unha aresta desígnase a miúdo polos dous vértices  e  que conecta, en forma de par {u, v} (ou un conxunto unitario {u} no caso dun bucle) se non está dirixido, ou un par (u, v) se está dirixido (ou orientado). Así, a aresta {1, 2} liga os vértices 1 e 2, e o arco (ou frecha) (7, 9) leva do vértice 7 ao vértice 9.

 Representacións 
En informática, os vértices dos grafos están codificados máis frecuentemente polas matrices de adxacencia dos vértices (é dicir, para cada vértice, a fila con un 1 dos seus veciños e un 0 dos que non o son).

 Grafo adxunto 
A partir dun grafo dado pódese deducir o grafo das súas arestas, chamado grafo adxunto ou grafo de liñas. Esquécense os vértices do grafo orixinal (chamado grafo raíz) e os seus vértices convértense nos vértices do novo grafo, conservando as súas adxacencias anteriores.No caso de grafos simples non dirixidos, o grafo raíz sempre se pode atopar, a non ser que sexa un grafo triángulos ou un grafo de garfo, que ambos os dous  teñen un grafo triángulo como grafo adxunto. No entanto, non todos os grafos son grafcos adxuntos: o grafo raíz  pode non existir. Os grafos adxuntos son xeralmente moi densos, porque todas as arestas incidentes no mesmo vértice forman unha clique no grafo adxunto.

 Notas 


 Véxase tamén 

 Bibliografía 
 Uma Introdução Sucinta à Teoria dos Grafos
 Outros artigos 
 Léxico da teoría de grafos
 Teoría de grafos
 Aresta
 Ligazóns externas 
  Graph Theory (LibreTexts).

Categoría:Teoría de grafos