GRAFOS

Consideramos informalmente, grafo como um conjunto não vazio de pontos V (vértices, nós, nodos) podendo ou não haver ligações entre eles através de linhas (arcos, arestas). A cada aresta do grafo podemos associar um par de nós do grafo.


Alguns exemplos de aplicações dos grafos:
1. Modelagem de circuitos digitais
2. Representação de processos em sistemas paralelos ou distribuídos.
3. Simulação e avaliação de desempenho

· Um grafo G é constituído por um conjunto N de elementos e por uma relação binária A entre estes elementos.

Escreve-se: G = (N, A).
· N são denominados nós (ou vértices).
· A são denominados arcos (ou arestas).

Ex:

N={1, 2, 3, 4}
A={(1, 2), (1, 4), (2, 1), (3, 1), (3, 2), (3, 4), (4, 2)}

· Nós ligados por arcos são ditos adjacentes (do ex. 3 é adjacente de 1, 2 e 4).
· Arcos são incidentes de um nó (partem dele) ou incidentes a um nó (chegam nele)
- incidentes do nó 2 – (partem dele) - (2, 1), (3, 2) e (3, 4)
- incidente no nó 1 - (1, 2)
· O grau de um nó é igual ao número de arcos que incidem a ele.
· Um caminho é a seqüência de arcos e nós percorridos com o objetivo de ligar dois nós não adjacentes.
(Ex: (1,2) e (2,3) é o caminho que liga o nó 1 ao nó 3. )
· Um circuito é um caminho que pode ser percorrido infinitamente dentro do grafo. Ex: (1,2), (2,4), (4,1); ou (3,3).
· Ramo Incidente num vértice v, é qualquer ramo para o qual v é vértice destino. No caso de ramo não orientado é incidente nos dois vértices que o ramo liga.
· Anel é um ramo de um grafo que liga um vértice a si próprio
· Ramos Paralelos são ramos que ligam os mesmos nós
· Multigrafo é um grafo que contem ramos paralelos, caso contrário será Grafo Simples
· Multiplicidade (peso) de um ramo valor que indica o número de ramos, com o mesmo sentido, que ligam 2 nós. Pode generalizar-se este conceito de peso e associar-se a cada ramo um valor inteiro que representará um atributo do ramo. Por exemplo, no caso de representação de um mapa das rua de uma cidade, poder-se-ia considerar em cada ramo um número (peso) que poderia ser a densidade de tráfego.
· Vértice Isolado é um vértice que não é origem nem destino de nenhum ramo.
Grafo Nulo é um grafo constituído só por vértices isolados.
· Um grafo conexo é aquele que possui um nó a partir do qual existem caminhos para todos os demais nós.
· Um subgrafo é aquele onde é considerado apenas um subconjunto dos nós do grafo original.
· Um grafo parcial, considera-se um subconjunto dos arcos do grafo original, permanecendo todos os nós.Ex:

· Um grafo é acíclico quando não possui circuitos.

· Uma rede é um tipo especial de grafo que possui um nó fonte, a partir do qual todos os demais nós são atingidos e um nó sorvedouro, do qual não parte nenhum nó.

· Os grafos vistos até agora são dígrafos, ou grafos dirigidos, nos quais a relação binária não é simétrica, ou seja, não implica em retorno.

· Grafos valorados (weighted graphs): Um número pode ser associado aos nós ou arcos de um grafo (dirigido ou não).

Ex:

· Existem maneiras diferentes dese representar um grafo, como por exemplo, matrizes de adjacência e listas de adjacência

MATRIZ DE ADJACÊNCIA

- Usar uma matriz para representar um grafo permite:obter caminhos, ciclos e outras características dos grafos.
- Preferível em grafos pequenos.
- Requer apenas um bit por entrada.

Este grafo é representado por uma matriz quadrada M (n x n) cujos elementos são mij em que:
- As linhas correspondem aos vértices origem e as colunas aos vértices destino.

- mij=1 se (vi,vj) Î E (existe ligação entre i e j)

- mij=0 não existe ligação entre i e j.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Abaixo está a 1ª classe Grafos que a gente fez e alguns metodos.....

Estão com alguns erros, pois são apenas as ideias iniciais, mas estes já foram corrigidos nas postagens acima.

----------------------- Classe Grafos

----------------------- Método Gerar grafos

----------------------- Metodo Set Aresta

----------------------- Metodo Imprime Peso

Metodo parentAninhados

O método parentAninhados tem a função de representar graficamente uma arvore binária através de parênteses como mostra a imagem a seguir:

1 – 4: Método que faz interface entre o usuário e a programação para mostrar uma árvore representada graficamente através dos parentes aninhados.
7: Verifica se o nó raiz passado é ou não nulo.
9: Imprimi na tela o “(” mais o valor do nó.
10: Chama recursivamente o método passando o valor do nó filho da esquerda.
11: Chama recursivamente o método passando o valor do nó filho da direita.
12: Imprimi na tela o “)”.

Metodo arvoreHierarquicaII

O método arvoreHierarquicaII tem a função de representar graficamente uma arvore binária através de uma arvore de hereditária como mostra a imagem a seguir:

1 – 4: Método que faz interface entre o usuário e a programação para mostrar uma árvore representada graficamente através dos arvore hierárquica II.
7: Verifica se o nó raiz passado é ou não nulo.
9: Imprimi a variável space que guarda os espaços em branco dados para a identação da árvore e o valor do nó atual.
10: Acrescenta espaços em branco à variável space.
11: Chama recursivamente o método passando o valor do nó filho da esquerda e os espaços em branco guardados em space.
12: Chama recursivamente o método passando o valor do nó filho da direita e os espaços em branco guardados em space.

Metodo arvoreHierarquicaI

O método arvoreHierarquicaI tem a função de representar graficamente uma arvore binária através de uma arvore de hereditária como mostra a imagem a seguir:

A diferença da imagem para como a arvore será representada no programa é que a árvore estará deitada, ou seja, a raiz da arvore ficará na extrema esquerda e a partir daí a arvore vai crescendo para a direita, ao invés de ser feito de cima para baixo.

1 – 4: Método que faz interface entre o usuário e a programação para mostrar uma árvore representada graficamente através dos arvore hierárquica I.
7: Verifica se o nó raiz passado é ou não nulo.
8: Acrescenta espaços em branco à variável space.
9: Chama recursivamente o método passando o valor do nó filho da direita e os espaços em branco guardados em space.
10: Imprimi na tela os espaços em branco que contem na variável space e o valor do nó.
11: Chama recursivamente o método passando o valor do nó filho da esquerda e os espaços em branco guardados em space.
14: No momento em que sai da condição da linha 7, a variável space recebe o caracter de quebra de linha.

Metodo isEstrBinary

O método isEstrBinary consiste em realizar uma verificação para saber se uma árvore é estritamente binária.
Uma árvore estritamente binária é nomeada dessa forma quando os nós têm ou os dois nós filhos ou não tem nenhum.


1 – 4: Método que faz interface entre o usuário e a programação para saber se uma árvore é ou não estritamente binária.
7: Verifica se o nó raiz passado é ou não nulo.
10: Condição que verifica se os nós filhos da esquerda e direita do nó raiz são nulos.
11: Se a verificação acima for verdadeira então o método retorna true.
12: Uma segunda verificação é realizada para saber se os nós filhos da esquerda e direita do nó raiz são diferente de nulos.
14: Condição for verdadeira então verifica se o lado da esquerda e o lado da direita de toda a árvore são estritamente binários.
15: Se a condição for verdadeira então é retornado true
17: Senão false será retornado20: Se a condição da linha 12 for falsa então é retornado false.

Metodo isFull

Uma árvore binária cheia é aquela em que a raiz e todos os nós internos tem dois nós filhos, portanto o objetivo do método isFull é verificar se uma árvore dada pelo usuário é ou não cheia.

O método que da linha 1 até a 10 é o método que faz a interface com o usuário e o código que verifica se a árvore é ou não cheia.
Nesse método de interface há uma diferença dos demais já apresentados:
Nele verificamos a altura dos dois lados da árvore utilizando o método já apresentado height. Se um lado for maior que o outro então não será necessário fazer o restante da verificação e o próprio método de interface retorna false para o usuário.
Se os dois lados da árvore tiverem o mesmo tamanho então chama-se a função de verificação da árvore.

13: Verifica se o nó raiz passado é ou não nulo
15: Se o nó filho direito e esquerdo forem iguais a nulo então retorna o valor true.
16: Se a condição da linha 15 for verdadeira então o valor true é retornado ao método de interface
17: Senão, é feita uma condição que verifica se a árvore do lado direito e do lado esquerdo são verdadeiros.
20: Caso a condição da linha 17 for verdadeira, então o valor true é retornado.
22: Caso contrario é retornado o valor false.
O valor true é retornado quando os nós filhos esquerdo e direito são nulos porque sabemos que o método chegou até o final da árvore. Se no meio do caminho fosse visto que a árvore não é cheia então o valor retornado é false, pois o método não permite que o restante da árvore seja verificada.

Metodo IsDegenerate

Diz-se que uma árvore é degenerada quando ela tem somente um filho. Um bom exemplo de árvore degenerada que temos são as tão famosas pilhas e listas encadeadas que nos colocaram medo por algum tempo.


123 - 126: Método que faz interface entre o usuário e a “real” programação do método.
282: Verifica se a raiz da árvore não é nula.
284: Verifica se o nó em questão tem dois filhos. Se tiver então a árvore não é degenerada.
285: Se a árvore contiver dois filhos então, nesse momento, a função retorna falso.
286: Senão, verifica se existe nó filho da esquerda.
287: Se tiver filho na esquerda então, chama-se a própria função passando como parâmetro o filho da esquerda.
288: Senão, verifica se existe nó filho da direita.
287: Se tiver filho na direita então, chama-se a própria função passando como parâmetro o filho da direita.
288: Quando nenhuma das condições acima satisfazer, então quer dizer que chegou ao final da árvore, e se até o final da árvore o sistema ainda não retornou falso quer dizer que árvore é degenerada e então retorna true.