Grafos

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1538 palavras )
  • Download(s) : 0
  • Publicado : 17 de março de 2013
Ler documento completo
Amostra do texto
Resumo
Neste trabalho iremos falar sobre a aplicação da álgebra linear, mas especificamente a utilização de matrizes e suas propriedades a fim de formular problemas e simplificar suas resoluções além de poder implementar computacionalmente em casos de maior complexidade. Com essa ferramenta podemos atuar em áreas como análise de estruturas organizacionais, estatísticas, ciências físicas dentreoutras.
Introdução
A teoria de grafos, área recente da matemática é utilizada para formulações de modelos em problemas de áreas como ciências sociais, negócios, ciências físicas entre outras e tem aplicações como comunicação, estudo de estruturas organizacionais e sociais.
Uma maneira de traduzir os grafos é utilizando matrizes e suas propriedades para obter resultados úteis na resolução eanálise de problemas nas áreas citadas.
O primeiro problema envolvendo grafos foi “As pontes de Königsberg”, que foi resolvido por Leonhard Euler em 1735. O problema envolvia o rio Pregelarme que cortava Königsberg que ficava na Prússia e dividia a região em quatro “ilhas” e existiam 7 pontes.O problema era saber se existia uma forma de passar por todas as pontes atravessando-as apenas uma vez.Euler simplificou o problema em um simples conjunto de quatro pontos (vértices) e sete caminhos (arestas).

Outras utilizações
1852 - “O Problema das 4-Cores” (Francis Guthris / De Morgan)
O teorema das quatro cores pode ser resolvido graças a implementação computacional de grafos.

1856 -“O Problema dos Ciclo Hamiltoniano” (William R. Hamilton)



É possível um cavalo fazer umarota pelo tabuleiro de xadrez, isto é,
visitar cada quadrado exatamente uma vez e retornar para o seu quadrado inicial?



Século XX - Grande interesse pela Teoria dos Grafos
1930 - Resultados teóricos fundamentais (Kuratiwski, König, Minger)
1971 - PROBLEMA DE STEINER EM GRAFOS (Hakimi et. al.)
Daí por diante utilizamos grafos para reolusão de uma infinidade de problemas matemáticos,computacionais, sociais entre outros.

* Digráficos
Também chamado grafo orientado, o digráfico é um conjunto de pontos finitos (vértices) junto a um conjuntos de segmentos que os ligam (arestas) e esse segmento é orientado de Pi para Pj ou Pj para Pi sendo estas arestas diferentes.


Os digráficos podem ser utilizados para representar um caminho de um ponto a outro, influência de umponto em outro, ação de um ponto em outro. Assim por exemplo, em um digráfico que representa influência da pessoa Pi sobre uma pessoa Pj podemos dizer que o ponto de onde saem mais arestas é o líder já que este influência mais pontos.
Falta por fim escrever esse raciocínio em forma de matriz e operar com elas parta obter diversas informações.

Métodos
Como vimos na definição dedigráficos temos segmentos orientados que relacionam pontos. Esses digráficos obedecem algumas propriedades como:
i. A aresta PiPj ≠PjPi
ii. Um ponto Pi pode não estar ligado a nenhum outro ponto.
iii. Nenhum vértice pode ser alcançado a partir de si mesmo por uma única aresta. (não há ciclos).
Agora podemos definir uma matriz de um digráfico G com n pontos que vamos chamar de A(G)nXn,cujo i-jésimo elemento é 1 se houver uma aresta ligando Pi e Pj , caso contrário o elemento é zero. O nome da matriz formada é Matriz adjacência.




Exemplo 1:
AG=0101001101011010

Comentário: Sabendo que os elementos de uma matriz são representados como uma “coordenada” i para linha e j para coluna temos que matriz A=[aij].
Exemplo 2:
a11 a12
a21 a22Assim de volta ao exemplo 1, se queremos saber se há um segmento de P1 a P3, então devemos ver a linha 1, coluna 3, ou seja, o elemento a13.
Para observar que elemento esta ligado a mais pontos basta observar quem tem mais uns em sua linha. No caso do exemplo 1 temos que cada ponto do digráfico esta ligado a outros dois já que temos dois números um em cada linha.
O raciocínio é análogo...
tracking img