Abrir menu principal

Aresta (teoria dos grafos)

conexão entre um conjunto de dois vértices de um grafo
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 arestasEditar

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ênciaEditar

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émEditar