O que é arestas?

Arestas em Grafos

Em teoria dos grafos, uma aresta é uma linha que conecta dois vértices. Formalmente, uma aresta é um par não ordenado de vértices.

Tipos de Arestas:

  • Aresta Não Direcionada (ou Aresta): Conecta dois vértices sem uma direção específica. Em outras palavras, a aresta pode ser atravessada em ambas as direções. Representadas simplesmente por uma linha entre os vértices.

  • Aresta Direcionada (ou Arco): Conecta dois vértices com uma direção específica. A aresta pode ser atravessada apenas na direção indicada. Representadas por uma seta entre os vértices, indicando a direção. Grafos direcionados são construídos com estas arestas.

  • Aresta Ponderada: Possui um valor associado, geralmente representando um custo, distância ou capacidade. Este valor é chamado de "peso" da aresta. Grafos ponderados utilizam estas arestas.

  • Laço (Loop): Uma aresta que conecta um vértice a ele mesmo.

  • Arestas Múltiplas (ou Arestas Paralelas): Duas ou mais arestas que conectam os mesmos dois vértices.

Conceitos Relacionados:

  • Incidência: Uma aresta é dita incidente a um vértice se este vértice é um dos extremos da aresta.

  • Grau de um Vértice: O número de arestas incidentes a um vértice. Em grafos direcionados, há um grau de entrada (número de arestas que chegam ao vértice) e um grau de saída (número de arestas que saem do vértice).

  • Caminho: Uma sequência de vértices conectados por arestas.

Aplicações:

Arestas são elementos fundamentais na representação de relacionamentos entre entidades em diversos domínios, como:

  • Redes Sociais: Representam conexões entre usuários.
  • Redes de Transporte: Representam estradas, rotas aéreas ou linhas ferroviárias entre cidades.
  • Redes de Computadores: Representam conexões entre dispositivos.
  • Circuitos Eletrônicos: Representam conexões entre componentes.