Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
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.
Definição formal da matemática!
Não ajudou muito! Certo?
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!
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?
É possível andar por toda a cidade de tal modo que cada ponte seja atravessada exatamente uma vez?
O problema agora consiste em percorrer todos os arcos (arestas), passando por cada um apenas uma vez, sem levantar o lápis do papel.
Abstração que permite codificar
relacionamentos entre pares de objetos!
Pessoas, cidades, empresas, países,
páginas web, filmes, etc.
Amizade, conectividade, produção, língua
falada, etc.
Objeto: Cidades
Relacionamento: Vôo comercial entre duas cidades.
São Paulo
BH
Cuiabá
Porto Alegre
Objetos: Atores
Relacionamento: Atores que atuaram no mesmo filme brasileiro
Meu tio matou um cara
Selton Mello
Wagner Moura
Débora
Secco
Lázaro
Ramos
Cláudia Abreu
Objeto: Computadores
Relacionamento: Computadores que estejam conectados em uma rede
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.
V = {v1, v2, v3, v4, v5} e
A = {(v1, v2), (v1, v3), (v2, v4), (v3, v4), (v4, v5), (v1, v2), (v2, v2)}.
V = {1, 2, 3, 4, 5} e
A = {(1, 2), (2, 3), (1, 4), (1, 3)}.
V = {a, b, c} e A = { }.
Será mesmo importante?
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!!!!
Vamos lá! Aplicações é o que não faltam para demonstrar o potencial e a importância de se aprender GRAFOS!
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?
Como calcular a menor rota?
Caminho mais rápido? Caminho com menos trânsito?
O problema consiste em fornecer água, telefone e eletricidade a 3 casas sem cruzar seus “tubos”
Qual o número mínimo de cores para colorir um mapa sem que os vértices vizinhos tenham a mesma cor?