| marp | theme | paginate | backgroundColor |
|---|---|---|---|
true |
gaia |
true |
- Professor: Carlos Alvaro Quintella
- Revisão: 10/05/2023
Grafos Introdução
Exemplos de uso de grafos
- Uso de Grafos na Biologia
- Uso de Grafos na Engenharia
- Uso de Grafos na Matemática
- Sociologia
Origem dos Grafos
- Leonard Euler
- Teoria de Grafos
Problemas Classicos Resolvidos com Grafos
- Kevin Bacon
- Problema das Quatro Cores
- O Problema do Caixeiro Viajante (PCV)
Mais Aplicações
- Sistemas Complexos
- Modelos de Redes Complexas
Classificação dos Grafos
- Grafos Direcionados
- Grafos Ponderados
- Conectados ou desconectados
- Ciclos ou acíclicos
- Subgráfo
- Grafo Completo
- Grafo Bipartido
- Grafo Planar
- Árvore
Grafos Famosos Propriedades de Grafos Links
Grafos são estruturas matemáticas usadas para representar relações entre objetos. Eles consistem em um conjunto de vértices (também conhecidos como nós) conectados por arestas (também conhecidas como arcos).
-
O nós representam elementos e as arestas relacões entre os elementos.
-
Grafos são uma ferramenta poderosa em muitas áreas, incluindo ciência da computação, matemática, física, biologia, engenharia, sociologia, entre outras.
- Modelagem de redes de computadores
- Encontrar caminhos mais curtos e otimizados
- Mapear uma cidade
- Estudar redes sociais
- Identificar problemas de congestionamento e sobrecargas
- BioInformática representando sequencias de DNA
- Jogos
Os grafos são usados na análise de redes de interação de proteínas e outros compostos em sistemas biológicos. Cada proteína é representada por um vértice, e as interações entre elas são representadas por arestas. Esse tipo de grafo é usado para identificar padrões de interação e entender melhor a dinâmica molecular em sistemas biológicos.
Os grafos são usados para modelar redes de transporte, como estradas e ferrovias. Cada ponto de interseção na rede é representado por um vértice, e as conexões entre eles são representadas por arestas. Esse tipo de grafo é usado para planejar rotas eficientes, prever o fluxo de tráfego e identificar gargalos na rede.
Os grafos são usados para estudar propriedades geométricas de objetos, como a topologia de superfícies. Cada ponto na superfície é representado por um vértice, e as conexões entre eles são representadas por arestas. Esse tipo de grafo é usado para entender melhor as propriedades topológicas dos objetos e como eles se relacionam entre si.
Os grafos são usados para modelar redes sociais, como grupos de amigos em redes sociais online. Cada pessoa é representada por um vértice, e as conexões entre elas (como amizades e interações) são representadas por arestas. Esse tipo de grafo é usado para entender melhor a estrutura social e a dinâmica de grupos de pessoas em redes sociais.
Leonhard Euler foi um matemático suíço que viveu no século XVIII. Ele é considerado um dos mais importantes matemáticos da história, tendo feito contribuições significativas em áreas como análise matemática, teoria dos números, geometria, álgebra, física e mecânica.
Euler nasceu em 1707 em Basileia, na Suíça, e foi educado em casa por seu pai, um pastor protestante. Desde cedo, Euler demonstrou talento para a matemática, e começou a publicar trabalhos matemáticos ainda na adolescência.
Em 1727, Euler mudou-se para São Petersburgo, na Rússia, para trabalhar na Academia de Ciências local. Lá, ele fez importantes contribuições para a teoria dos números, a análise matemática e a física matemática, além de trabalhar na cartografia e na mecânica.
Euler teve uma vida bastante produtiva e publicou mais de 800 trabalhos ao longo de sua carreira, abrangendo uma ampla gama de áreas da matemática e da física. Ele também trabalhou em estreita colaboração com outros matemáticos famosos de sua época, como Johann Bernoulli e Daniel Bernoulli.
Além de seu trabalho científico, Euler também teve um impacto significativo na história da matemática através de sua extensa correspondência com outros matemáticos e cientistas de sua época. Ele era conhecido por sua habilidade em comunicar ideias matemáticas de forma clara e acessível, e suas cartas foram uma fonte importante de inspiração para outros matemáticos.
Euler faleceu em 1783, aos 76 anos, deixando um legado duradouro na matemática e na ciência. Muitas das áreas que ele ajudou a desenvolver continuam a ser estudadas e aplicadas até hoje, e sua contribuição para a matemática e para a ciência em geral é inestimável.
A história dos grafos remonta ao século XVIII, quando o matemático suíço Leonhard Euler investigou o problema das Sete Pontes de Königsberg. Esse problema perguntava se era possível caminhar pela cidade de Königsberg, passando uma única vez por cada uma das sete pontes que cruzavam o rio Pregel.
Euler percebeu que esse problema poderia ser modelado como um grafo, em que os vértices representavam as áreas da cidade e as arestas representavam as pontes. Ele mostrou que era impossível atravessar todas as pontes apenas uma vez, e que a solução do problema dependia da propriedade de um grafo conhecida como grau par.
A partir desse problema, Euler desenvolveu a teoria dos grafos, introduzindo conceitos fundamentais como caminhos, ciclos, conectividade, planaridade e coloração de grafos. Seu trabalho foi fundamental para a matemática moderna e é considerado um marco na história dos grafos.
Desde então, os grafos se tornaram uma ferramenta fundamental em muitas áreas, como engenharia, ciência da computação e física. Eles são usados para modelar problemas complexos, como redes de computadores, mapas de estradas, fluxos de tráfego, redes de energia, sistemas de comunicação, entre outros.
Na ciência da computação, os grafos são frequentemente usados para resolver problemas de otimização, como encontrar o caminho mais curto entre dois pontos em uma rede, ou encontrar a árvore geradora mínima em um grafo ponderado. Algoritmos populares como o algoritmo de Dijkstra, o algoritmo de Bellman-Ford, o algoritmo de Kruskal e o algoritmo de Prim são usados para resolver esses tipos de problemas.
Antes do advento da computação, muitos desses problemas eram resolvidos por força bruta, o que exigia uma quantidade considerável de tempo e recursos. No entanto, com o avanço da tecnologia e o poder computacional disponível, tornou-se possível utilizar abordagens mais eficientes e inteligentes para resolver esses problemas. Os algoritmos mencionados acima são exemplos de algoritmos que exploram a estrutura dos grafos de forma otimizada, permitindo encontrar soluções mais rápidas e precisas.
Esses algoritmos são fundamentais em áreas como roteamento de redes, planejamento de rotas, análise de redes sociais, logística, entre outros. A capacidade de resolver problemas complexos de otimização usando grafos tem implicações significativas no mundo real, proporcionando melhorias em eficiência, economia de recursos e tomada de decisões informadas.
A teoria dos seis graus de separação, também conhecida como a teoria de Kevin Bacon, é uma hipótese que sugere que qualquer pessoa no mundo pode estar conectada a qualquer outra pessoa por um caminho de, no máximo, seis relações de amizade ou conhecidos em comum.
A teoria foi popularizada pelo jogo "Six Degrees of Kevin Bacon", que desafia os participantes a conectar qualquer ator de Hollywood a Kevin Bacon em seis ou menos filmes. A ideia por trás do jogo é que Bacon é uma espécie de centro do universo cinematográfico, tendo trabalhado com tantos atores que, em teoria, qualquer um pode ser conectado a ele em seis ou menos filmes.
A teoria dos seis graus de separação tem suas origens em um estudo conduzido pelo psicólogo social Stanley Milgram em 1967.
Milgram pediu a um grupo de pessoas selecionadas aleatoriamente em Nebraska que enviassem uma mensagem para um destinatário específico em Massachusetts, mas eles não poderiam enviá-la diretamente.
Em vez disso, eles deveriam enviá-la para uma pessoa conhecida, que então enviaria para outra pessoa conhecida, e assim por diante, até que a mensagem chegasse ao destinatário.
Milgram descobriu que a média de graus de separação entre os remetentes e o destinatário final era de 5,2.
Desde então, a teoria dos seis graus de separação foi aplicada a muitos campos, incluindo sociologia, antropologia, psicologia e ciência da computação. Os cientistas sociais a usam para entender como as pessoas se relacionam umas com as outras e como as informações se espalham através de redes sociais. Na ciência da computação, a teoria é aplicada em algoritmos de busca em grafos, que permitem encontrar caminhos mais curtos entre dois pontos em redes complexas.
Embora a teoria dos seis graus de separação seja frequentemente citada como verdadeira, alguns críticos argumentam que a hipótese é simplista e que existem muitas variáveis, como distâncias geográficas e barreiras culturais, que podem afetar a conexão entre as pessoas. No entanto, a teoria continua sendo uma ideia popular e intrigante que destaca a conectividade da sociedade moderna e a capacidade das redes sociais de unir pessoas de diferentes partes do mundo.
O problema das quatro cores é um problema de coloração de mapas que diz respeito a determinar se é possível colorir um mapa plano (também conhecido como plano topológico) com apenas quatro cores, de forma que países ou regiões adjacentes recebam cores diferentes.
O problema surgiu pela primeira vez em 1852, quando o matemático inglês Francis Guthrie observou que era possível colorir um mapa da Inglaterra com apenas quatro cores. Ele então questionou se era possível fazer o mesmo para qualquer mapa. No entanto, apesar de muitos matemáticos terem tentado resolver o problema, ninguém conseguiu encontrar uma prova definitiva até o século XX.
Em 1976, o matemático norte-americano Kenneth Appel e seu colega Wolfgang Haken finalmente conseguiram provar que qualquer mapa pode ser colorido com apenas quatro cores. Eles usaram um método computacional complexo, conhecido como "prova assistida por computador", que envolvia a análise de uma grande quantidade de casos específicos. Embora a prova tenha sido criticada por alguns matemáticos por não ser totalmente compreensível, ela é amplamente aceita como a solução definitiva para o problema.
📺 The Four Color Map Theorem - Numberphile
O problema das quatro cores tem implicações práticas em várias áreas, incluindo cartografia, computação gráfica, design gráfico e até mesmo em questões políticas e diplomáticas, onde pode ser necessário colorir regiões de um mapa para representar áreas de influência ou territórios disputados.
Embora o problema das quatro cores tenha sido resolvido, ele continua sendo um exemplo importante de como problemas matemáticos aparentemente simples podem levar a descobertas surpreendentes e aplicáveis em várias áreas.
(travelling salesman problem)É um problema que tenta determinar a menor rota para percorrer uma série de cidades (visitando uma única vez cada uma delas), retornando à cidade de origem. Ele é um problema de otimização NP-difícil inspirado na necessidade dos vendedores em realizar entregas em diversos locais (as cidades) percorrendo o menor caminho possível, reduzindo o tempo necessário para a viagem e os possíveis custos com transporte e combustível.
-
O problema do caixeiro-viajante (representado na Figura 1) consiste na procura de um circuito que possua a menor distância, começando numa cidade qualquer, entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial.
-
O tamanho do espaço de procura aumenta exponencialmente dependendo de n, o número de cidades, uma vez que existem muitos circuitos possíveis (a posição inicial é arbitrária, e a ordem do circuito pode ser invertida).
Embora o PCV seja um problema difícil de resolver, ele tem diversas aplicações práticas em áreas como logística, transporte, planejamento de rotas, design de circuitos, genética, entre outras. Algumas das principais aplicações do PCV são:
- Logística e transporte: O PCV é utilizado para otimizar a rota de entrega de mercadorias, minimizando a distância percorrida e os custos de transporte. Empresas de entregas, serviços de correio e distribuidoras podem se beneficiar ao encontrar a sequência mais eficiente de paradas.
- Planejamento de rotas: O PCV é aplicado em sistemas de navegação GPS, onde é necessário encontrar o percurso mais curto para um motorista visitar vários destinos. Além disso, é usado em planejamento urbano, para otimizar o transporte público e determinar rotas eficientes para coleta de lixo ou manutenção de infraestruturas.
-
Design de circuitos e microchips: No campo de design de circuitos e microchips, o PCV é usado para minimizar o tempo de percurso de sinais elétricos entre componentes, otimizando a disposição física dos elementos.
-
Genética e bioinformática: O PCV é aplicado em estudos genéticos para determinar a ordem de sequenciamento de genes, a fim de minimizar o custo e o tempo necessário para sequenciar o DNA.
-
Planejamento de rotas de veículos: Empresas de transporte, como táxis, serviços de compartilhamento de carros ou até mesmo aplicativos de transporte, podem usar o PCV para otimizar a alocação de veículos e rotas para atender a um grande número de clientes.
Os SCs são sistemas de múltiplos elementos interconectados e interativos. Eles são encontrados em várias áreas, como física, biologia, economia, ecologia e ciências sociais.
-
Redes Complexas é uma área que estuda os padrões de interconexão em sistemas complexos.
-
Um grafo pode ser uma representação abstrata dessas interconexões, com nós e arestas representando os elementos e as conexões, respectivamente.
Os modelos de redes complexas são ferramentas importantes para estudar e compreender os padrões de interconexões em sistemas complexos do mundo real. Eles permitem simular e analisar as propriedades das redes, reproduzindo características observadas em diversos domínios. Esses modelos são essenciais para compreender os mecanismos subjacentes, como a propagação de informações e a formação de comunidades, além de auxiliar na tomada de decisões e na otimização desses sistemas.
- O modelo Erdős-Rényi é um dos modelos mais simples e clássicos de redes complexas. Ele se baseia em uma distribuição aleatória de arestas entre os nós de uma rede, onde cada par de nós tem uma probabilidade independente de ser conectado. Esse modelo é útil para estudar propriedades estatísticas das redes complexas.
- O modelo Watts-Strogatz foi proposto para capturar características específicas de redes sociais e foi inspirado pelo fenômeno dos "seis graus de separação". Ele começa com uma rede regular, na qual cada nó está conectado aos seus vizinhos mais próximos. Em seguida, ele introduz aleatoriamente conexões adicionais para criar um efeito de "mundo pequeno" na rede, onde a maioria dos nós pode ser alcançada a partir de qualquer outro em um pequeno número de etapas.
Matematicamente os grafos são representados por dois conjuntos, um conjunto não vazio de Vertices (conjunto V). E um conjunto que pode vir a ser vazio de arestas ou arcos (conjunto E)*.
Nota: No inglês: E=Edges e V=Vertices.
Não é permitido que uma aresta tenha mais de dois Vértices.
Vertices:
V = {1, 2, 3, 4, 5, 6, 7, 8, 9}
Arcos (direcionados):
A = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (3, 5), (4, 5), (4, 6), (5, 6), (5, 7), (6, 7), (6, 8), (7, 8), (7, 9), (8, 9), (1, 4), (2, 5), (3, 6), (4, 7), (5, 8)}
-
Os grafos direcionados têm arestas que apontam em uma direção específica (representadas como uma seta).
-
Já os grafos não-direcionados, chamados de simples, não têm direção nas arestas.
Os grafos ponderados atribuem um peso ou valor numérico a cada aresta, enquanto os grafos não-ponderados não atribuem pesos.
Um grafo é conectado se houver um caminho entre todos os seus vértices, caso contrário, é desconectado.
Um grafo contém um ciclo se houver um caminho fechado que passe por um mesmo vértice duas vezes ou mais, caso contrário, é acíclico.
graph LR
A["Vértice 1"]
B["Vértice 2"]
C["Vértice 3"]
D["Vértice 4"]
E["Vértice 5"]
HA{Hiperaresta A} -- A,B,C -->
HB{Hiperaresta B} -- B,C,D -->
HC{Hiperaresta C} -- D,E -->
HD{Hiperaresta D} -- A,E -->
Um subgrafo G' do grafo G = (V, E) é um grafo (V', E') tal que V' ⊆ V e E' ⊆ E.
"⊆", que representa a relação de "subconjunto" em matemática.
Um grafo completo é aquele em que existe uma aresta entre cada par de vértices. Um grafo completo com n vértices possui n(n-1)/2 arestas.
Um grafo é dito bipartido se os vértices podem ser divididos em dois conjuntos disjuntos de tal forma que cada aresta conecta um vértice em um conjunto a um vértice no outro conjunto.
Um grafo planar é aquele que pode ser desenhado em um plano de tal maneira que nenhuma aresta se cruze.
Uma árvore é um grafo acíclico conectado, ou seja, um grafo em que qualquer par de vértices está conectado por exatamente um caminho e não há ciclos.
Grafo Petersen: O grafo Petersen é um pequeno grafo que serve como exemplo e contraexemplo para muitas propriedades em teoria dos grafos. Ele é nomeado após Julius Petersen, que o apresentou em 1898.
Grafo de Moore: Um grafo de Moore é um grafo regular (todos os vértices têm o mesmo grau) e distância-regular que possui o maior número de vértices possível para sua girth (menor ciclo).