Grafos

Disponível somente no TrabalhosFeitos
  • Páginas : 9 (2074 palavras )
  • Download(s) : 0
  • Publicado : 18 de novembro de 2012
Ler documento completo
Amostra do texto
Universidade Federal do Triângulo Mineiro Instituto de Ciências Tecnológicas e Exatas Departamento de Engenharia Mecânica

TEORIA DOS GRAFOS

Fagner Passarelli Lourenço Camila Fernanda A. Vieira

Novembro 2011

TEORIA DOS GRAFOS
Definição: Um grafo é uma estrutura de abstração que representa um conjunto de elementos denominados nós e suas relações de interdependência arestas.Representação Matemática: Denominando por V o conjunto de vértices da estrutura, e por A o conjunto das arestas ou ligações entre os vértices, um grafo pode ser representado por: G = (V,A). Um grafo nada mais é do que uma representação gráfica da interdependência entre elementos. Elementos estes, que são representados por nós, também chamados de vértices, como na figura abaixo:

Apesar de a figura acima jáo ser, um grafo é mais comumente representado da seguinte forma:

Grafo ponderado: Um grafo G = (V,A) é ponderado se existem valores numéricos associados a suas arestas ou nós.

Grafos ponderados normalmente são utilizados para representar mapas, por exemplo. Nos mapas, as ponderações associadas às arestas podem ser as distancias entre um local e outro (um vértice desse grafo e outro).Grafo rotulado: Definição: Um grafo valorado G = (V,A) tal que, para qualquer a número real c(a) associado. A, existe um

Essas atribuições são frequentemente referidas como o peso da ligação. Essa classificação é dada de acordo com a necessidade, ou não, da indicação do fluxo entre os vértices. Na prática este número pode representar: - custos, distâncias, capacidades, e/ou suprimentos edemandas; - tempo (trânsito, permanência, etc); - confiabilidade de transmissão; - probabilidade de ocorrer falhas; - capacidade de carga; - outros.

Multigrafo: Definição: Um grafo G = (V,A) é um multigrafo se existem mais de uma aresta ligando o mesmo par de vértices. Multigrafos podem ser usados, por exemplo, pra modelar as possíveis conexões de vôo oferecidas por uma linha aérea.

GrafoDirecionado: V≠ Definição: Um grafo direcionado é uma estrutura matemática G= (V,A), onde é um conjunto de vértices (ou nós) e A V x V é u conjunto de arcos (ou arestas) de .

Se o número de vértices em V é n, pode haver m = n² arcos no máximo. Nessa situação, pode haver 2m grafos distintos. Porém, podem ocorrer ainda grafos onde V é um conjunto infinito enumerável, assim como A. Um grafo Direcionado érepresentado matematicamente também por: G=(V,E) , onde V é o conjunto de vértices e E é uma relação binária em V (i.e., um conjunto de pares ordenados) das ligações. Exemplo de um grafo direcionado:

Grafo bipartido: Definição: Um grafo G é dito bipartido quando seu conjunto de Nós, N, pode ser dividido em dois conjuntos N1 e N2 tais que a interseção seja nula e a união seja todo o conjunto N esomente existem arestas em G ligando algum nó de N1 com algum nó de N2 e vice-versa.

Como exemplo conhecido de grafo bipartido temos o das três casas que tem que ser ligadas com agua, luz e telefone. Pegue as casas C1,C2,C3 e as estações A,L,T. Desenhe sem cruzar as ligações de C1 e C2 com A e L. Você forma um "quadrilátero" ou ciclo elementar AC1LC2.Veja que tanto faz o C3 estar dentro oufora. Ao ligar C3 a A e L temos dois ciclos encaixados. Basta dai verificar que tentar colocar o T em qualquer lugar não da pois alguém fica sem. Grafo completo: Definição: Um grafo G é dito completo se existir ao menos uma ligação associada a cada par de vértices. No caso não orientado isso significa exatamente uma ligação. Os grafos completos não orientados são também chamados de cliques edenotados como Kn, onde n representa o número de nós do grafo completo. Por analogia, os grafos completos bipartidos são denotados por Kpq, sendo p e q as cardinalidades das duas partições do grafo. Exemplo de grafo completo que também é um clique:

Grafo regular: Definição: O grau de um vértice de um grafo é o número de arestas incidentes no vértice. Um grafo é dito regular de grau r se todos os...
tracking img