Estruturas de Dados

Um grafo não-direcionado, ou simplesmente grafo é um conjunto de pontos com linhas conectandos alguns desses pontos. Os pontós são chamados de nós ou vértices e as linhas são chamadas arestas.

O número de arestas de um nó específico é o grau do nó. Cada dois nós só podem ter uma aresta ligando-os. Na figura anterior, todos os nós tem grau 2.

Ao representar um grafo, utilizamos um conjunto com um par $i,j$ para reperesentar uma aresta que liga os nós $i$ e $j$. No caso do grafo não-direcionado, a ordem de $i$ e $j$ não importa, e os pares $(i,j)$ e $(j,i)$ representam a mesma aresta.

No caso do grafo direcionado, representamos cada aresta com uma tupla $(i,j)$ para representar uma aresta que sai do nó $i$ e chega ao nó $j$. No caso dos grafos direcionados, os pares $(i,j)$ e $(j,i)$ representam arestas diferentes. Em grafos direcionados o grau de um nó é divido em grau de entrada, que é o número de arestas que chega no nó, e grau de saída, que é o número de arestas que inicia no nó.

Formalmente, um grafo é composto por dois conjuntos $G=(V,E)$, onde $V$ é o conjunto de vértices e $E$ é o conjunto de arestas do grafo. Por exemplo, podemos descrever o grafo apresentado anteriormente como:

Um subgrafo de um grafo $G$ é um grafo formado com um subconjunto de vértices e arestas de G. O subconjunto de vértices deve incluir todos os vértices que estão relacionados as arestas do subconjunto de arestas, porém pode incluir vértices adicionais. Um subgrafo induzido é um subgrafo formado por um subconjunto de vértices e todas as arestas que conectam esses vértices.

Um caminho é uma sequência de arestas que unem uma sequência de vértices. Um caminho aberto é um caminho onde o primeiro e o último vértices são diferentes, um caminho fechado é um caminho que começa e termina no mesmo vértice. Um caminho simples é um caminho onde não ocorrem repetições de vértices ou arestas.

Um ciclo ocorre quando é possível criar uma caminho fechado em um grafo.

Um grafo conexo ou grafo conectado é um grafo onde é possível atingir qualquer vértice de um grafo a partir de um vértice qualquer deste grafo. Um grafo fracamente conectado é um grafo direcionado onde a substituição das arestas por arestas não direcionadas forma um grafo conectado. Um grafo fortemente conectado é um grafo conexo direcionado (existem arestas para ambos os lados em todos os pares de vértices).

Um grafo rotulado é um grafo cujos vértices e/ou arestas possuem rótulos. Em alguns casos, chamamos um grafo rotulado de grafo ponderado, quando os rótulos das arestas representam um custo para aquela aresta.

Uma auto-aresta é uma aresta que tem nas suas duas pontas o mesmo vértice. Um grafo contendo uma auto-aresta não é mais um grafo simples, e é tratado como um multigrafo.