Grafos

 

 

Uma forma de passar o tempo em uma viagem de avião é olhar os impressos nos bolsos das poltronas. Este material geralmente inclui um mapa com as rotas da comapnhia aérea que voce está usando, tal como mostrada na Fig. 1. Todas estas informações sobre rotas podem ser expressas de forma verbal; por exemplo, existe uma rota direta entre Chicago e Nashville, mas não existe entre St. Louis e Nashville. No entanto a forma verbal será muito confusa, e não será capaz de passar as informações tão rapidamente e de forma tão clara quanto o mapa. Existem muitos casos em que "uma figura vale por centenas de palavras".

Em inglês, o termo usado para disignar um grafo é graph que também é comumente usado de forma coloquial para designar qualquer representação visual de dados (gráficos, em português). Outras formas comuns incluem o gráfico de barras, o gráfico de figuras e o gráfico de setores. Existem também os gráficos de funções em sistemas de coordenadas retangulares. Adotaremos uma definição de grafo muito específica que não menciona nada sobre uma representação visual. No entanto, figuras como a mostrada na Fig. 1 são imediatamente entendidas como coerentes com nossa definição de grafo, de forma que também chamaremos este tipo de figuras de grafos.

 

Figura 1: rotas aéreas

 

Definição: Grafos, Vértices e Arestas

Um grafo é um tripla ordenada (N,A,g) onde

N é um cojunto não-vazio de vértices (nós ou nodos)

A é um conjunto de arestas (arcos)

g é uma função que associa cada aresta a um par não-ordenado x-y de vértices chamados extremos de a

Os grafos tratados aqui terão sempre um número finito de vértices e arestas

 

Exemplos

  1. O conjunto de vértices do mapa da empresa aérea da Fig. 1 é { Chicago, Nashville, Miami, Dallas, St. Louis, Albuquerque, Phoenix, Denver, San Francisco, Los Ângeles}.Existem 16 arestas, por exemplo Phoenix-Albuquerque, Albuquerque-Dallas, etc. Considere a Fig. 2

 

Fig. 2: grafo

Neste grafo temos 5 vértices e 6 arestas. A função que associa as arestas aos seus extremos assume os seguintes valores: g(a1)=1-2, g(a2)=1-2, g(a3)=2-2, g(a4)=2-3, g(a5)=1-3, g(a6)=3-4

Dois vértices de um grafo são ditos adjacentes se forem os extremos de uma mesma aresta. Um laço em um grafo é uma aresta com extremos n-n para algun nó n. Um grafo pode não conter laços. Neste caso é chamado sem laços. Duas arestas que tenham os mesmos extremos são chamadas arestas paralelas. Um grafo simples é um grafo que não tem arestas paralelas nem laços. Um vértice isolado não é adjacente a qualquer outro vértice. O grau de um vértice é o número de arestas que o tem como ponto extremo. Como a função g, que relaciona cada aresta a seus extremos, é entendida como função propriamente dita, cada aresta tem um único par de extremos. Se g for uma função injetiva então haverá apenas uma aresta associada a cada par de vértices e o grafo não terá arestas paralelas. Um grafo completo é aquele no qual todos os vértices distintos são adjacentes. Neste caso, g é quase uma função sobrejiva - todo par x-y de vértices distintos está no conjunto imagem de g mas não há um laço em cada vértice, de forma que pares do tipo x-y não devem ter imagem.

Um subgrafo de um grafo consiste de um conjunto de vértices e um conjunto de arestas que são subconjuntos dos conjuntos de vértices e arestas originais, respectivamente, nos quais os extremos de qualquer aresta precisam ser os mesmos que no grafo original. Em outras palavras, é um grafo obtido apagando-se parte do grafo original e deixando o restante sem alterações. A Fig. 3 mostra dois subgrafos da Fig. 2.

 

 

 Fig. 3: subgrafos

Um caminho de um vértice no a um vértice nk é uma sequência no, ao, n1, a1, , nk-1, ak-1, nk de vértices e arestas onde, para cada i, os extremos da aresta aI são ni - nI+1. O comprimento de um caminho é um número de arestas que ele contém. Se uma aresta for usada mais de uma vez, ela deve ser contada tantas vezes quantas vezes for usada. Um grafo é dito conexo se houver um caminho entre quaisquer dois vértices. Um ciclo em um grafo é um caminho de algum vértice no até no, sem repetir vertices (exceto no) e arestas.

 

Grafos Isomorfos

Dois grafos podem parecer muito diferentes em suas representações gráficas, mas serem, ainda assim, o mesmo grafo de acordo com nossa definição. Considere os grafos mostrados nas Fig. 4:

 

(a) (b) (c)

Figura 4 - Grafos "iguais"

 

Os grafos da Fig. 4 são os mesmos. Eles tem os mesmos vértices, as mesmas arestas e a mesma função de associação de arestas e seus extremos. Na representação de um grafo, as arestas podem interceptar-se em pontos que não sejam vértices do grafo. Embora não se pareça com (a) e (b) o grafo (c) também é o mesmo. Se mudarmos os rótulos dos vértices e arestas do grafo (a) segundo a correspondência que se segue, os grafos se tornarão os memos:

f1: 1® a

2® c

3® b

4® d

 

f2: a1® e2

a2® e1

 

As estruturas que são iguais a menos de um novo rotulamento são chamadas de isomorfas. Para mostrar que duas estruturas são isomorfas, precisamos produzir novos rótulos (uma aplicação - função injetiva e sobrejetiva entre os elementos de ambas as estruturas) e então mostrar as que as propriedades importantes das estruturas são preservadas pelo novo rotulamento. No caso de grafos, os elementos são os vértices e arestas. A "propriedade importante" em um grafo é a lista de quais arestas conectam quais vértices.

As aplicações f1 e f2 descritas acima são funções injetivas e sobrejetivas dos vértices e arestas do grafo da Fig. 4 (a) nos vértices e arestas do grafo da Fig. 4 (c). Além disso se uma aresta a no grafo (a) tem extremos x-y então a aresta f2(a) no grafo (c) tem extremos f1(x)-f1(y) e vice-versa. Por exemplo a aresta a1 em (a) tem extremos 1-3, enquanto que a aresta correspondente e2 em (c) tem extremos a-b, que são vértices em (c) correspondentes aos vértices 1-3 de (a). Podemos, então, formalizar a idéia

 

Definição"Grafos Isomorfos

Dois grafos (N,A1,g1) e (N2,A2,g2) são isomorfos se existirem bijeções f1:N1® N2 e f2: A1® A2, tais que para cada aresta aÎ A1, g1(a) = x-y, se e somente se, g2[f2(a)]=f1(x) -f1(y)

 

 

 

 

Para determinar que dois grafos são isomorfos requer que encontremos a bijeção (ou, para grafos não simples, as bijeções) e então mostremos que a propriedade da adjacência (ou relação entre arestas e seus extremos) é preservada. Para mostrar que dois grafos não são isomorfos, precisamos mostrar que a(s) bijeção(ões) necessária(s) não existe(m). Entretanto este método se tornaria inviável em grafos que tivessem um grande número de arestas e vértices. Podemos procurar outras razões pelas quais tais bijeções não existem e portanto descobrir se existe ou não o isomorfismo. Apesar de não ser uma tarefa simples em todos os casos, existem certas condições sob as quais se torna fácil ver que dois grafos não são isomorfos. Essas condições incluem: