Home

Aula 21

10/05/2001

Elaborada por:

Eduardo Bentes Nº 12493

Vítor Robalo     Nº 14235

       Implementação de grafos

Assuntos Abordados na Aula:

• Matriz Adjacente

Grafos sem orientação

Grafos com orientação

Grafos com dois sentidos

• Lista Adjacente

Grafos sem orientação

Grafos com orientação

• Matriz de Incidencia

Grafos sem orientação

Grafos com orientação

Matriz de adjacência:

       M(i, j) = 1     se arco (i,j) existe

       M(i, j) = 0     senão existe arco (i,j)

Nota: i e j são vértices

•  Para Grafos Sem Orientação

Matriz:

Quando um dos vétices tem ligação com outro na tabela é representado com 1 

Quando um dos vértices não tem ligação com outro na tabela é representado com 0    

    Como se pode verificar é uma matriz simétrica pois ao traçar-mos uma diagonal, o que temos na parte inferior é igual à parte superior

• Parte superior da matriz escrita sobre forma de um número binário

(111100011000101)_bin=(30917)_dec   

• O grafo pode ser codificado do seguinte modo:

 (30917,6) Onde 6 representa o número de vértices da matriz

Atenção:

Se existir um arco de um vértice para ele próprio temos de contar com a diagonal da matriz

Exemplo:

• Grafos Com Orientação:

  • No caso do grafo ter orientação (mas não existindo arcos nas duas direcções) 

Na ligação directa entre dois vértices o valor correspondente na tabela é 1

Na ligação inversa entre dois vértices o valor correspondente na tabela é -1

Quando nenhum dos vértices tem ligação com outro na tabela é representado com 0

    A tabela é construída tendo em conta o peso dos arcos. Caso exista arco, a entrada na tabela é zero ou o peso do arco, se não existir arco a entrada na tabela é 1.

                 Nota: Qualquer grafo com N vértices vai precisar de N² espaços

Lista de adjacências:

Nota: Um vértice não é adjacente se houver possibilidade de lhe aceder.

• Sem orientação

    Temos uma lista com todos os vértices e possuímos um apontador para os vértices onde existe ligação da seguinte forma:

• Com orientação

    Aqui temos em conta a orientação dos arcos

Matriz de incidências:

• Sem orientação:

M(i, j) = 1 se i é fim de j

M(i, j) = 0 se i não é fim de j

---

Nota: i representa vértice e j representa o arco

---

    A tabela é constituída na parte superior com os vértices e na parte esquerda o numero do arco. Na tabela é colocado a 1 os vértices do caminho e todos os outros a 0.

•   Com orientação :

 

M(i, j) = 1 se j é início de i

M(i, j) = -1 se j é fim de i

M(i, j) = 0 se não

     A tabela é constituída na parte superior com os vértices e na parte esquerda o numero do arco. Na tabela é colocado a 1 os vértices do caminho com ligação directa, é colocado a -1 com ligação inversa e todos os outros a 0.

Sites a visitar:

• www.cut-the-knot.com/do_you_know/graphs.html

• www.inf.ufsc.br/grafos/

• www.informatik.hu-berlin.de/~weinert/graphs.html