Teoria de Grafos - Outras Definições

Grafo Direcionado G é um par (V,E), onde V é um conjunto finito e E é uma relação binária em V.
Grafo Não Direcionado G = (V,E) é um par onde o conjunto de arestas E consiste em pares de vértices não orientados. A aresta (vi,vj) e (vj,vi) são consideradas a mesma aresta.


Outras definições:

• Loop: uma aresta associada ao par de vértices (vi,vi)
• Arestas paralelas: quando mais de uma aresta está associada ao mesmo par de vértices
• Grafo simples: um grafo que não possui loops e nem arestas paralelas
• Dois vértices são ditos adjacentes se eles são pontos finais de uma mesma aresta
• Duas arestas não paralelas são adjacentes se elas são incidentes a um vértice comum
• Quando um vértice vi é o vértice final de alguma aresta ej, vi e ej são incidentes

O número de arestas incidentes a um vértice vi é chamado de grau, d(vi), do vértice i
A soma dos graus de todos os vértices de um grafo G é duas vezes o número de arestas de G.



Referências: Material dos professores Max do Val Machado e Raquel Mini