Introducing 

Prezi AI.

Your new presentation assistant.

Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.

Loading…
Transcript

Grafos: Teoria e Programação

Grafos?

Um grafo G é constituído de um conjunto V não vazio de objetos, chamados vértices (ou nós), e um conjunto A de pares não ordenados de elementos de V , chamados de arestas. Denotamos o grafo por G (V, A) ou simplesmente G.

Grafos?

Definição formal da matemática!

Não ajudou muito! Certo?

É um conjunto de pontos, chamados vértices...

É um conjunto de pontos, chamados vértices...

É um conjunto de pontos, chamados vértices...

Conectado por linhas,

chamadas arestas!

Pode representar relações? Pode!

Mas como surgiu?

As idéias básicas de grafos foram introduzidas no século XVIII , pelo famoso matemático suíço Leonhard Euler. Ele usou grafos para resolver o problema hoje conhecido como As sete pontes de Königsberg.

Este foi o ponto de partida para se dar início à teoria dos grafos!

As sete pontes de Könisberg

A cidade de Königsberg é banhada pelo rio Pregel que, ao atravessar a cidade se ramifica formando uma ilha que está ligada à parte restante da cidade por sete pontes.

Dizia-se que os habitantes da cidade, nos dias de descanso e sol, tentavam efetuar um percurso que os obrigasse a passar por todas as pontes, mas apenas uma vez em cada uma.

Será que era possível?

As pontes...

É possível andar por toda a cidade de tal modo que cada ponte seja atravessada exatamente uma vez?

As pontes...

Vamos remodelar o problema?

O problema agora consiste em percorrer todos os arcos (arestas), passando por cada um apenas uma vez, sem levantar o lápis do papel.

Definição Informal...

Abstração que permite codificar

relacionamentos entre pares de objetos!

Objetos? Quais?

Pessoas, cidades, empresas, países,

páginas web, filmes, etc.

Objetos? Quais?

Relações?

Amizade, conectividade, produção, língua

falada, etc.

Relações?

Podemos concluir que...

Exemplos???

Transporte Aéreo

Objeto: Cidades

Relacionamento: Vôo comercial entre duas cidades.

Transporte Aéreo

São Paulo

BH

Cuiabá

Porto Alegre

Atores que atuaram no mesmo filme!

Objetos: Atores

Relacionamento: Atores que atuaram no mesmo filme brasileiro

Atores que atuaram no mesmo filme!

Meu tio matou um cara

Selton Mello

Wagner Moura

Débora

Secco

Lázaro

Ramos

Cláudia Abreu

Computadores?

Objeto: Computadores

Relacionamento: Computadores que estejam conectados em uma rede

Computadores?

O que aprender?

O que aprender?

A teoria dos Grafos é bastante detalhada! Há grafos de diversos tipos!

Uma árvore é um grafo! Existem também os dígrafos!

Aprenderemos também que os grafos possuem graus! Que há grafos completos, conexos, desconexos, bipartidos, grafos planares, entre outros tantas nomenclaturas!

É possível fazer busca em grafos! Aplicação muito útil e essencial.

A teoria dos grafos está presente na maioria das aplicações atuais.

Representar grafos...

V = {v1, v2, v3, v4, v5} e

A = {(v1, v2), (v1, v3), (v2, v4), (v3, v4), (v4, v5), (v1, v2), (v2, v2)}.

E esse?

V = {1, 2, 3, 4, 5} e

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

É um grafo????

V = {a, b, c} e A = { }.

Qual a necessidade?

Qual a necessidade?

Será mesmo importante?

É mais do que necessário!

É essencial!

Como seria a Inteligência Artificial sem o que sabemos dos Grafos?

O que seria das Redes de Computadores, sem a teoria dos Grafos?

Redes Neurais? Deep Learning? Algoritmos de Roteamento?

O que seria da Internet? IoT? Big Data?

GPS!!!!

Aplicações

Vamos lá! Aplicações é o que não faltam para demonstrar o potencial e a importância de se aprender GRAFOS!

Redes Neurais Artificiais

Redes Neurais Artificiais

Malha do Sistema Elétrico

Malha do Sistema Elétrico

Problema: Quantas linhas precisam falhar (no mínimo) para termos um apagão?

Como ligar ao sistema uma nova localidade com o menor custo possível?

Se houver um dano na rede e precisar isolar parte do sistema para proteger todo o resto, qual parte devo isolar?

Smart Grids! Como gerenciar?

Cidades Inteligentes?

Alocação de Frequências

Alocação de Frequências

GPS

Como calcular a menor rota?

Caminho mais rápido? Caminho com menos trânsito?

GPS

Redes Sociais!

Vamos pensar...

Vamos pensar...

O problema consiste em fornecer água, telefone e eletricidade a 3 casas sem cruzar seus “tubos”

E colorir mapas?

Qual o número mínimo de cores para colorir um mapa sem que os vértices vizinhos tenham a mesma cor?

E o problema das pontes??

Learn more about creating dynamic, engaging presentations with Prezi