Aresta (teoria dos grafos)

Tipos de arestas.

Em teoria dos grafos, uma aresta junto com os vértices ou nodos formam as unidades fundamentais das quais os grafos são formados[1]: um grafo não dirigido consiste de um conjunto de vértices e um conjunto de arestas (pares de vértices não ordenados), enquanto um digrafo é constituído por um conjunto de vértices e um conjunto de arcos (pares ordenados de vértices). As arestas são consideradas as uniões entre os vértices. Uma aresta é dita incidente aos elementos de um par de vértices que não são necessariamente distintos.[2] Normalmente as arestas denotam as relações entre os vértices (vizinhanca, grau, herança, etc..)

Tipos de arestas

Uma aresta pode ser não-direcionada ou direcionada. No segundo caso, o par de vértices é ordenado e o vértices são chamados vértice-inícial e vértice-final. Arestas com o mesmo vértice-inicial e o mesmo vértice final ( u, v ) são ditas paralelas.[2]

Relação de adjacência

As arestas de um grafo ou digrafo G=(V, E) induzem uma relação chamada de relação de adjacência.[3] Portanto um vértice v é adjacente a um vértice w se e somente se v-w é uma aresta que pertence ao conjunto E.

Referências

  1. ↑ Szwarcfiter, Jayme Luiz (1988). Grafos e algoritmos computacionais. Rio de Janeiro: Campus. p. 35-73. ISBN 85-7001-341-8 
  2. ↑ a b Even, Shimon (1979). Graph Algorithms. Rockville, Maryland: Computer Science Press. p. 1. ISBN 0-914894-21-8 
  3. ↑ BAASE, Sara (1988). Computer Algorithms. Introduction to Design and Analysis (em inglês) 2ª ed. Reading, Massachusetts: Addison-Wesley. p. 149. ISBN 0-201-06035-3 

Ver também

Teoria dos grafos