Grafos_2

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
Matriz de Adjacência, Matriz de Incidência e Isomorfismo
*
*
Matriz de Adjacência
Suponha que um grafo tem n nós, numerados n1, n2, ..., nn,Essa numeração impõe uma ordem arbitrária nos nós; lembre-se de que um conjunto é uma coleção não-ordenada. No entanto, isso é feito simplesmente para identificar os nós – não é dado significado algum ao fato de um nó aparecer antes de outro. Após a ordenação dos nós, podemos formar uma matriz n X n onde o elemento aij representa o número de arcos entre os nós ni e nj.Essa matriz é chamada de matriz de adjacência A do grafo em relação a essa ordem. Assim,
aij=p, se existem p arcos entre ni e nj.
*
*
Matriz de Adjacência
*
*
Matriz de Incidência
Na matriz de incidência as linhas estão associadas aos nós e as colunas aos arcos. Um elemento na linha i e coluna j é 1 se o nó i é incidente no arco j e 0 (zero) caso contrário. 
*
*
Matriz de Incidência
*
*
Lista de Adjacência
Um grafo com relativamente poucos arcos pode ser representado de modo mais eficiente armazenando-se apenas os elementos não-nulos da matriz de adjacência. Essa representação consiste em uma lista, para cada nó, de todos os nós adjacentes a ele. São usados ponteiros para se ir de um item na lista para o próximo. Essa estrutura é chamada de uma lista encadeada. Existe um arranjo de n ponteiros, um para cada nó, para começar cada lista. Essa lista de adjacência, embora precise de armazenagem extra para os ponteiros, ainda pode ser mais eficiente do que uma matriz de adjacência.
*
*
Isomorfismo
O conceito de isomorfismo vem formalizar a ideia de grafos que, apesar de não serem iguais, apresentam as mesmas propriedades estruturais. Dois grafos G=(N,A) e H=(M,L) são isomorfos se existe uma relação 1-1 entre os nós de N e de M que preserva adjacência, isto é, se i e j em N são adjacentes em G, então os nós correspondentes em M pela relação também são adjacentes em H e vice-versa. 
Se tivermos sorte de detectar por inspeção uma relação 1-1 que comprova o isomorfismo, ótimo. Caso contrário, temos que tentar verificar alguma diferença estrutural entre os grafos que evidencie não serem eles isomorfos. Os itens mais óbvios são número de nós e arcos, e grau de nós. Outros que podem ser úteis são: conectividade e planaridade dos grafos em questão.
*
*
Considere agora dois grafos isomorfos G=(N,A) e G’=(N’,A’). Seja I um subconjunto de N e I’ o subconjunto correspondente de N’, com respeito à relação 1-1 que evidencia o isomorfismo entre G e G’. Então os subgrafos de G e G’ obtidos pela remoção dos nós em I e I’ e os arcos a eles incidentes são também isomorfos. No exemplo a seguir ilustramos como utilizar este fato para mostrar que dois grafos não são isomorfos. Infelizmente não se conhece um método eficiente para determinar se dois grafos são ou não isomorfos.
*
*
Mostrar que os grafos G e H não são isomorfos
*
*
Note que os grafos em questão contêm o mesmo número de nós e arcos, e o grau de todos os nós é 2. No entanto o grafo G é desconexo enquanto que o grafo H é conexo (trata-se de um ciclo com seis nós). Portanto não se trata de grafos isomorfos.
*
*
Grafos Planares
Um grafo é planar se é possível desenhá-lo no plano de modo que as linhas correspondentes aos arcos não se cruzem. Tal desenho é uma realização gráfica planar do grafo, ou, simplesmente, realização planar.
Um grafo planar é um grafo que pode ser representado (em uma folha de papel, isto é, em um plano) de modo que seus arcos se intersectam apenas em nós.
*
*
Exemplos de grafo planar e grafo não-planar
K4 é um grafo planar, pois suas arestas não se cruzam, ou seja, cada nó tem grau 3 e as arestas não se cruzam, pois os nós são extremos das arestas.
K5 não é um grafo planar, pois não é possível desenhar todas as 10 arestas ligando os 5 nós sem que haja cruzamento entre elas.
*
*
Fórmula de Euler
O matemático suíço do século XVIII, Leonhard Euler, descobriu um fato sobre grafos planares. Um grafo simples e conexo divide o plano em um determinado número de regiões, incluindo regiões totalmente limitadas por arcos e uma região exterior ilimitada. Euler observou uma relação entre o número n de nós, o número a de arcos e o número r de regiões em um tal grafo. Essa relação é conhecida como a fórmula de Euler:
n – a + r = 2 
*
*
Exercício
1) Verifique a fórmula de Euler para K4.