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.

O conxunto de arestas dun grafo chámase comunmente E, ás veces sendo frechas chámase A. O conxunto de vértices chámase V:

• 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 u e v 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.

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).

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.

• 
  Gráfico G
• 
  O grafo adxunto L (G)

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 ${\displaystyle L^{-1}(G)}$ 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.

Wikimedia Commons ten máis contidos multimedia na categoría:  Aresta

• Uma Introdução Sucinta à Teoria dos Grafos

• Léxico da teoría de grafos
• Teoría de grafos
• Aresta

• Graph Theory (LibreTexts).