Introdução a Teoria dos Grafos

Para começar, vamos dar um breve introdução à teoria dos grafos, explanando os principais conceitos para que se possa entender os próximos tutoriais.

1- O que é um Grafo?

A teoria dos grafos busca estudar as relações entre objetos de um conjunto. Um grafo é formalmente definido como:

G=(V,E) onde,

G é o Grafo que é formado por um conjunto não-vazio de vértices(V) e arestas (E), um conjunto não ordenado de pares de V.

As arestas conectam dois vétices e podem ou não ter direção e pesos associados. Se as arestas são direcionadas, o grafo formado por elas é denominado um grafo direcionado, orientado ou dígrafo.

Um grafo dito trivial é um grafo com um único vértice.

Em resumo:

Um grafo pode ser representado por G=(V,E)

V = conjunto não vazio de arestas

E= conjunto não ordenado de pares de V chamado arestas. E é um par formado por {vértice, vértice destino ligado por uma aresta}

Na representação gráfica V são os nós (a,b,c,d,e) e E são retas que interligam 2 nós.

Nesse exemplo temos G=(V,E), onde V={a,b,c,d,e} e E={{a,b},{b,c},{b,d},{c,d},{d,e}}

Quando dois vértices são ligados por uma aresta e ,esses vértices são ditos incidentes a aresta e.

O grau (d) de um vértice é o número de arestas incidentes à ele.

No exemplo:

d(a)=1

d(b)=3

d(c)=2

d(d)=3

d(e)=1

Se V(conjunto de vértices é finito, então d(V)=2*E. Em outras palavras, se temos um conjunto finito de arestas, o grau total dos vértices de um grafo G é dado pelo dobro do número de arestas.

Dois vértices são adjacentes se existe uma aresta entre eles. No exemplo: (a,b) são adjacentes assim como, (b,d),(c,d),(b,c),(d,e).

Podemos usar uma matriz de adjacência para representar um grafo direcionado finito ou não direcionado finito: Dado um grafo com n vértices, a matriz de adjacência terá o tamanho nXn cujo o valor na linha i e coluna j fornece o número de arestas do i-ésimo ao j-ésimo vértices.

No exemplo acima, temos o grafo com a sua respectiva matriz de adjacência. As linhas e colunas representam os vértices do grafo. Quando temos um aresta ligando dois vértices, as células correspondentes recebem o valor 1. Por exemplo linha A coluna C vale 1, pois há uma aresta ligando esses dois vértices. Já linha A coluna D é igual a 0 pois não existe uma aresta que ligue os vértices A e D.

Um grafo conexo é um grafo que se pode estabelecer um caminho  de qualquer vértice para qualquer outro vértice.

Um grafo k-conexo é aquele que mesmo após remover k-1 vértices  ainda é possível estabelecer um caminho entre vértices.

Fonte: Imagens:
http://wikiciencias.casadasciencias.org/wiki/images/c/cb/Matrizadjacencias.png
http://www.gpec.ucdb.br/pistori/disciplinas/discreta/aulas/figuras/fig1.gif

Texto:
https://pt.wikipedia.org/wiki/Teoria_dos_grafos