Gráfos

Um grafo é uma estrutura de dados formada por dois conjuntos: o conjunto dos vértices e o conjunto das arestas; um vértice é um ponto de referência para as arestas, e estas são ligações entre dois vértices. Você pode imaginar que um grafo é um mapa rodoviário idealizado: os vértices são cidades e as arestas são as estradas.

Exemplo 1: Digamos que os vértices de nosso grafo são 1, 2, 3, 4, 5, e as arestas são a, b, c, d, e, f. Então a seguinte tabela define um grafo: ponta A 1 2 3 4 5 1 linha A B C D E F ponta B 2 3 4 5 1 4

Se uma aresta A tem ponta inicial v e ponta final w, dizemos que a aresta vai de 1 até 2. Dizemos também que A sai de 1 e entra em 2. Às vezes, um aresta com ponta inicial 1 e ponta final 2 será denotado por (1,2) ou por 1—2 ou ainda por 12. Como se vê, estas arestas não tem uma direção; há quem goste de enfatizar esse fato dizendo que o grafo é não-dirigido, arestas que não possuem direção também são chamadas linhas.

Mas porém nem sempre um grafo é composto de linhas, este também pode ser composto por arcos, que nada mais são que uma aresta com uma direção. Quando o grafo possui este tipo de ligação, diz-se que o grafo é dirigido.

A natureza está cheia de grafos. Eis alguns exemplos:

Cada vértice é uma página na teia WWW. Cada arco é um link que leva de uma página a outra.

Os vértices são times de futebol e os arcos são os jogos entre os times durante um campeonato. É claro que o grafo é simétrico e não tem laços (mas pode ter arcos paralelos).

Cada vértice é uma espécie animal (cavalo, urso, coala, coelho, mosquito, etc. ) ou vegetal (cenoura, palmeira, eucalipto, alga, etc.). Há um arco de x para y se a espécie x se alimenta da espécie y.

Classificação dos grafos:

Dependendo de vários fatores, os grafos podem ser classificados de acordo com 11 características, veremos um breve resumo delas agora:

1) Sentido das arestas
2) Parcialidade
3) Numero