Teoria dos grafos

Teoria dos grafos

1. Definição

   • Tema antigo, mas possuindo muitas aplicações hoje em dia
   • Ramo da matemática que estuda as relações entre os objetos de um determinado conjunto.
   • Grafo: um animal formado por dois conjuntos: um conjunto de coisas chamadas vértices e um conjunto de coisas chamadas arcos; cada arco está associado a dois vértices: o primeiro é a ponta inicial do arco e o segundo é a ponta final. Você pode imaginar que um grafo é um mapa rodoviário idealizado: os vértices são cidades e os arcos são estradas de mão única.

2. Exemplo de Aplicação

   • o problema das sete pontes de Königsberg: No século 18 havia na cidade de Königsberg um conjunto de sete pontes (identificadas pelas letras de a até f na figura abaixo) que cruzavam o rio Pregel . Elas conectavam duas ilhas entre si e as ilhas com as margens.
     • O Grafo utilizado como modelo é definido como segue: V = { m | m é uma ilha ou uma margem } A = { (m1,m2, p} | existe uma ponte p unindo as margens ou ilhas m1 e m2 } Os conjuntos acima são apresentados, a seguir, na forma extensiva, contendo todos seus elementos, extraídos do problema: V = { A, B, C, D } A = { (A,C,c), (A,C,d), (A,B,a), (A,B,b), (A,D,e), (B,D,f), (C,D,g) }.
       • A solução consiste em, partindo de qualquer vértice, tentar atravessar todas as arestas uma única vez e retornar ao vértice de origem. Euler, ao propôr a solução para este problema, se preocupou em descobrir em que tipos de grafos se pode fazer esse caminhamento fechado, passando por todas as arestas uma única vez. Esse tipo de caminhamento foi chamado 'caminho de Euler', e um grafo que consiste de um caminho de Euler foi denominado 'grafo de Euler'.

3. Tipos de Grafo

   • simples, completo, nulo , vazio;
   • trivial, regular,multigrafo, pseudografo;
   • convexo, árvore, floresta, subgrafo;
   • parcial, independente,planar, bipartido;
   • teorema das quatro cores, k-partido, emparelhamento.

4. Exercicio de exemplificação

   • Qual é o menor caminho entre Rita e Fabiana? A resposta para esse problema poderia ser bem custosa de acordo com a modelagem do mesmo, porém nota-se que com a utilização de grafos passa a ser um problema trivial. No exemplo utilizamos poucos objetos, porém a mesma resolução é escalável para N pessoas, N empresas e N universidades.
     • Resolução: Rita trabalha na mesma empresa que Nelson, que estuda na mesma universidade que Fabiana

Images and files in the map