Teoria Dos Grafos

Definições básicas

• Grafo – Um grafo G é definido por G = (V, E), sendo que V representa o conjunto de nós e E, o conjunto de arestas (i, j), onde i, j 2 V . Dois nós i, j são vizinhos, denotado por i _ j, se eles estão conectados por uma aresta. A Figura 1.1 mostra dois exemplos de grafos: o grafo G1 consiste dos conjuntos V = {a, b, c, d, e} e E = {e1, e2, e3, e4, e5, e6}; G2 possui o nó 1 que não e conectado com nenhum outro nó do grafo.

Figura 1.1: Exemplos de grafos.

Quando o grafo possui mais nós não adjacentes do que nós adjacentes, ele é chamado de grafo esparso. Aresta associada a um mesmo nó constitui um laço ou loop.

• Grafo direcional – Um grafo é dito direcional, ou dígrafo, quando é necessário ser estabelecido um sentido (orientação) para as arestas. O sentido da aresta é indicado através de uma seta, como ilustrado na Figura 1.2. Nesta situação, a aresta passa a ser denominada de arco.

• Complemento de um grafo – O complemento de um grafo G, representado por G, é o grafo com o mesmo conjunto de vértices de G e tal que i _ j em G se eles não forem vizinhos em G. A Figura 1.3 apresenta um exemplo de grafo complementar.

• Grafo completo – Se todos os vértices de G são mutuamente adjacentes, o grafo é dito completo, como mostra o exemplo da Figura 1.4.

Figura 1.2: Exemplo de um dígrafo.

Figura 1.3: Um grafo G e seu complemento G.

Figura 1.4: G é um grafo completo.
• Grafo Ponderado– Em um grafo ponderado, um peso ou conjunto de pesos é associado a cada aresta, representado da forma w(i, j), ou seja, w (1, 2) é o peso associado à aresta que une os nós 1 e 2. Já em um grafo com atributos A, definido por G = (V, E, A), os valores são associados aos nós de G.

• Árvore – Um grafo conexo sem ciclos é chamado de árvore.

Grau de um grafo

• Grau – Grau de um nó i (ou valência), denotado por deg (i) é o número |E (i)| de arestas em i. Um nó de grau 0 é um nó isolado. A equação a seguir dá o grau médio de um grafo.

• Grafo regular – É o