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.
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:
· 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.
----------------------- Metodo Imprime Peso
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
Nenhum comentário:
Postar um comentário