Resumos · Matemática Aplicada às Ciências SociaisPT · Secundário

Modelos de grafos

Um grafo é um conjunto de pontos (vértices) ligados por linhas (arestas) que modela relações e redes — estradas, circuitos de recolha, rotas de distribuição. Este tema estuda os conceitos de grafo, os grafos de Euler (percorrer todas as arestas, com o teorema de Euler e a eulerização) e os grafos de Hamilton (visitar todos os vértices, com o problema do caixeiro-viajante e os seus algoritmos). É um tema de raciocínio dedutivo e de otimização com aplicações reais.

4 secções~15 min de leitura4 competênciasNível Base 1 · Padrão 2 · Aprofundamento 1

T·0444 / 8

Perfil de exame

Representar situações reais por grafos e usar corretamente os seus conceitosAplicar o teorema de Euler a circuitos e caminhos eulerianos e eulerizar grafosDistinguir circuitos de Euler de circuitos de HamiltonResolver o problema do caixeiro-viajante com algoritmos, reconhecendo os seus limites

Operadores:representaidentificaaplicajustificadeterminacomparaanalisa

nível básico

Reconhecer e usar os conceitos de grafo e aplicar o teorema de Euler para decidir se existe circuito ou caminho euleriano.

nível avançado

Modelar problemas de otimização, aplicar heurísticas ao caixeiro-viajante e discutir criticamente a sua não-otimalidade e viabilidade económica.

Profundidade

Texto

Conteúdo · 4 secções

Modelos de grafos

Conceitos de grafos#

BaseAE-macs-grafos-introducao

Um grafo é um modelo feito de vértices (pontos) e arestas (linhas que unem pares de vértices). Serve para representar QUALQUER situação em que interessam as ligações entre elementos: os vértices podem ser cidades e as arestas estradas; os vértices cruzamentos e as arestas ruas; os vértices pessoas e as arestas amizades. O grafo abstrai a situação — o que importa é quem está ligado a quem, não a forma nem a distância no desenho. A Fig. 1 mostra um grafo com 5 vértices e 6 arestas.

Um grafo com 5 vértices e 6 arestas

Fig. 1Fig. 1 — Grafo de ordem 5 com 6 arestas. Graus: A(2), B(3), C(2), D(2), E(3); soma 12 = 2 × 6 (teorema dos apertos de mão).

Os conceitos básicos são poucos e precisos. Dois vértices são adjacentes se estiverem unidos por uma aresta. O grau de um vértice é o número de arestas que nele incidem (um laço — aresta de um vértice a si próprio — conta duas vezes). Um vértice isolado tem grau 0. A ordem do grafo é o número de vértices. Na Fig. 1, «A» tem grau 2, «B» tem grau 3, «C» grau 2, «D» grau 2 e «E» grau 3.

Estes números obedecem a uma lei simples e fundamental — o teorema dos apertos de mão: a soma dos graus de todos os vértices é igual ao DOBRO do número de arestas, porque cada aresta contribui com uma unidade para o grau de cada um dos seus dois extremos. Na Fig. 1, «2+3+2+2+3 = 12 = 2 × 6». Uma consequência imediata e muito útil: o número de vértices de grau ímpar é sempre PAR (não pode haver um número ímpar de vértices ímpares). Esta observação é a chave do estudo dos grafos de Euler.

Percorrer um grafo dá origem a mais dois conceitos. Um caminho é uma sequência de arestas que liga um vértice a outro sem repetir arestas; um circuito é um caminho fechado, que regressa ao vértice de partida. Um grafo diz-se conexo se houver um caminho entre quaisquer dois dos seus vértices — ou seja, se estiver «todo ligado», sem partes separadas. Conexidade, grau e paridade são os ingredientes com que se resolvem os grandes problemas do tema.

\sum_{v} \operatorname{grau}(v) = 2\,|A|

Teorema dos apertos de mão

A soma dos graus de todos os vértices é o dobro do número de arestas |A|. Consequência: o número de vértices de grau ímpar é sempre par.

Exemplo resolvido

Graus e teorema dos apertos de mão

No grafo da Fig. 1 (arestas AB, BC, AD, DE, EC, BE), determina o grau de cada vértice, a soma dos graus e verifica o teorema dos apertos de mão. Quantos vértices têm grau ímpar?

Graus
A: {AB, AD} → 2. B: {AB, BC, BE} → 3. C: {BC, EC} → 2. D: {AD, DE} → 2. E: {DE, EC, BE} → 3.
Soma dos graus
2 + 3 + 2 + 2 + 3 = 12.
Verificação
Há 6 arestas, e 2 × 6 = 12: confirma o teorema dos apertos de mão.
Vértices ímpares
De grau ímpar são apenas B e E: dois vértices (um número par, como o teorema garante).

Resultado: Graus 2, 3, 2, 2, 3; soma 12 = 2 × 6; dois vértices de grau ímpar (B e E).

Erros frequentes

Contar mal o grau de um vértice, esquecendo que um laço conta duas vezes.
Confundir caminho (não repete arestas, extremos distintos) com circuito (caminho fechado).

Revisão ativa

Desenha um grafo com vértices A, B, C, D e arestas AB, BC, CD, DA e AC. Indica a ordem, o grau de cada vértice, verifica o teorema dos apertos de mão e diz se o grafo é conexo.

Evocação ativa

Recorda os pontos-chave — depois revela.

Fontes: Aprendizagens Essenciais de MACS — 11.º ano (Introdução aos grafos) (Direção-Geral da Educação (DGE))

Grafos de Euler: teorema e eulerização#

PadrãoAE-macs-grafos-euler

Um circuito de Euler é um circuito que percorre TODAS as arestas do grafo exatamente uma vez, regressando ao ponto de partida. É o modelo de muitas tarefas reais em que se quer passar por todas as LIGAÇÕES sem repetir: o percurso de um carteiro por todas as ruas, a recolha do lixo, a limpeza de ruas, a leitura de contadores. O problema histórico que deu origem ao tema é o das sete pontes de Königsberg, que Euler provou não ter solução — não é possível passar por todas as pontes uma só vez e regressar ao início.

O teorema de Euler resolve completamente a questão e consta do formulário do exame: um grafo conexo admite um circuito de Euler se e só se todos os seus vértices tiverem grau PAR. A justificação é intuitiva: sempre que o percurso passa por um vértice, «entra» por uma aresta e «sai» por outra, consumindo as arestas aos pares; para que nenhuma sobre e se regresse ao início, cada vértice tem de ter um número par de arestas. O grafo da Fig. 2, com todos os vértices de grau par, admite, por exemplo, o circuito de Euler «A–B–C–D–E–C–A».

Grafo com circuito de Euler

Fig. 2Fig. 2 — Todos os vértices têm grau par (A,B,D,E com 2; C com 4): pelo teorema de Euler, existe circuito de Euler, por exemplo A–B–C–D–E–C–A.

E se houver vértices de grau ímpar? Se existirem EXATAMENTE dois vértices de grau ímpar, o grafo não tem circuito de Euler, mas tem um caminho de Euler — um percurso que passa por todas as arestas uma vez sem regressar ao início, começando forçosamente num dos vértices ímpares e terminando no outro. Se houver mais de dois vértices de grau ímpar, não existe nem circuito nem caminho de Euler. O grafo da Fig. 3 tem dois vértices de grau ímpar (A e C): tem caminho, mas não circuito.

Grafo com dois vértices de grau ímpar

Fig. 3Fig. 3 — Quadrado com diagonal: A e C têm grau ímpar (3). Há caminho de Euler (de A a C), mas não circuito. Euleriza-se duplicando arestas entre A e C.

Quando um grafo não admite circuito de Euler mas se quer, ainda assim, percorrer todas as arestas e voltar ao início (por exemplo, um camião do lixo que tem de regressar à garagem), recorre-se à eulerização: acrescentam-se duplicados de arestas já existentes até que todos os vértices fiquem com grau par. Cada aresta duplicada corresponde, na prática, a repetir uma rua. No grafo da Fig. 3, basta duplicar as arestas de um caminho entre os dois vértices ímpares «A» e «C» (por exemplo, repetir «A–B» e «B–C») para tornar todos os graus pares — o objetivo é usar o MENOR número possível de repetições, minimizando o percurso extra.

Exemplo resolvido

Decidir sobre circuitos e caminhos de Euler

Para o grafo da Fig. 3 (quadrado ABCD com a diagonal AC), decide se existe circuito de Euler, caminho de Euler, ou nenhum, e indica como eulerizá-lo.

Graus
A: {AB, AD, AC} → 3; B: {AB, BC} → 2; C: {BC, CD, AC} → 3; D: {CD, AD} → 2.
Vértices ímpares
Há exatamente DOIS vértices de grau ímpar: A e C.
Conclusão de Euler
Pelo teorema de Euler, não há circuito (nem todos os graus são pares), mas há caminho de Euler, que começa em A e termina em C (ou vice-versa).
Eulerização
Para obter um circuito, duplicam-se arestas de um caminho entre os ímpares A e C, por exemplo AB e BC: A e C passam a grau 4 e B a grau 4 — todos pares.

Resultado: Sem circuito de Euler; há caminho de Euler de A a C. Euleriza-se duplicando AB e BC (todos os graus ficam pares).

Erros frequentes

Confundir circuito de Euler (percorre todas as ARESTAS) com circuito de Hamilton (visita todos os VÉRTICES).
Concluir que existe circuito de Euler quando há vértices de grau ímpar — nesse caso, no máximo, há caminho de Euler (se forem exatamente dois).

Revisão ativa

Um grafo conexo tem os graus dos vértices iguais a 2, 4, 2, 3 e 3. Justifica se admite circuito de Euler, caminho de Euler, ou nenhum, e explica como o eulerizarias para admitir um circuito.

Evocação ativa

Recorda os pontos-chave — depois revela.

Fontes: Aprendizagens Essenciais de MACS — 11.º ano (Grafos de Euler) (Direção-Geral da Educação (DGE))

Grafos de Hamilton e o problema do caixeiro-viajante#

PadrãoAE-macs-grafos-hamilton

Um circuito de Hamilton é um circuito que visita cada VÉRTICE do grafo exatamente uma vez, regressando ao ponto de partida. A distinção em relação a Euler é subtil mas essencial: Euler percorre todas as ARESTAS (ligações), Hamilton visita todos os VÉRTICES (pontos). É o modelo de quem quer passar por todas as cidades, todos os clientes ou todos os pontos de entrega, sem repetir, e voltar ao início — não interessa percorrer todas as estradas, mas visitar todos os locais.

Ao contrário de Euler, não existe um teorema simples que diga, pela contagem dos graus, se um grafo tem circuito de Hamilton. É um problema muito mais difícil: em geral, é preciso procurar. Quando cada aresta tem um peso — uma distância, um custo, um tempo, um consumo — surge o problema do caixeiro-viajante: encontrar o circuito de Hamilton de MENOR peso total. A Fig. 4 mostra quatro cidades A, B, C, D, todas ligadas entre si, com os custos (em €) de cada ligação direta.

Grafo ponderado do caixeiro-viajante

Fig. 4Fig. 4 — Quatro cidades com o custo (€) de cada ligação direta. O circuito de Hamilton de menor custo é A–B–D–C–A, com 40 €.

Com poucos vértices, pode resolver-se por força bruta: listar todos os circuitos de Hamilton possíveis e escolher o de menor peso. Para 4 cidades a partir de A, há apenas três circuitos distintos (cada um percorrido nos dois sentidos): «A–B–C–D–A» (8+10+11+25 = 54 €), «A–B–D–C–A» (8+12+11+9 = 40 €) e «A–C–B–D–A» (9+10+12+25 = 56 €). O melhor é «A–B–D–C–A», com 40 €. A força bruta garante a solução ótima, mas o número de circuitos cresce explosivamente com o número de cidades (para «n» cidades há «(n−1)!/2» circuitos), tornando-a impraticável já para poucas dezenas de locais.

É por isso que, na prática, se recorre a algoritmos aproximados (heurísticas): procedimentos rápidos que encontram uma boa solução, embora sem garantia de ser a melhor. A Aprendizagem Essencial sublinha precisamente a discussão sobre a «utilidade e a viabilidade económica (e não só) da procura de soluções ótimas»: muitas vezes, uma solução quase-ótima obtida rapidamente vale mais do que a solução perfeita que demoraria semanas a calcular. A próxima secção trabalha duas heurísticas clássicas e mostra, honestamente, que podem falhar o ótimo.

N = \dfrac{(n-1)!}{2}

Número de circuitos de Hamilton

Num grafo completo com n vértices, há (n−1)!/2 circuitos de Hamilton distintos. Ex.: n = 4 dá 3 circuitos; n = 6 já dá 60; n = 10 dá 181 440.

Exemplo resolvido

Caixeiro-viajante por força bruta

Para as quatro cidades da Fig. 4 (AB=8, AC=9, AD=25, BC=10, BD=12, CD=11), determina o circuito de Hamilton de menor custo a partir de A.

Circuito A–B–C–D–A
8 + 10 + 11 + 25 = 54 €.
Circuito A–B–D–C–A
8 + 12 + 11 + 9 = 40 €.
Circuito A–C–B–D–A
9 + 10 + 12 + 25 = 56 €.
Comparação
Dos três, o de menor custo é A–B–D–C–A, com 40 €.

Resultado: O circuito ótimo é A–B–D–C–A, com um custo total de 40 €.

Erros frequentes

Aplicar o teorema de Euler (contagem de graus) para decidir sobre a existência de circuito de Hamilton — não há critério análogo.
Ao listar circuitos de Hamilton, contar como diferentes o mesmo circuito percorrido nos dois sentidos.

Revisão ativa

Para as quatro cidades da Fig. 4 (custos AB=8, AC=9, AD=25, BC=10, BD=12, CD=11), lista os três circuitos de Hamilton a partir de A, calcula o peso de cada um e indica o circuito ótimo.

Evocação ativa

Recorda os pontos-chave — depois revela.

Fontes: Aprendizagens Essenciais de MACS — 11.º ano (Grafos de Hamilton) (Direção-Geral da Educação (DGE))

Algoritmos para o caixeiro-viajante e otimização#

AprofundamentoAE-macs-grafos-hamilton

O algoritmo do vizinho mais próximo é a heurística mais intuitiva: partindo de uma cidade, vai-se sempre para a cidade ainda não visitada mais próxima (de menor peso), até visitar todas, regressando por fim à cidade de partida. É rápido e fácil de aplicar. No grafo da Fig. 4, a partir de «A»: a ligação mais barata é «A–B» (8); de «B», as cidades ainda não visitadas são C (BC = 10) e D (BD = 12), pelo que se escolhe a mais barata, «B–C» (10); de «C» resta apenas «D» (CD = 11); e regressa-se por «D–A» (25). O percurso é «A–B–C–D–A = 8+10+11+25 = 54 €» (ver Fig. 5).

Comparação de algoritmos para o caixeiro-viajante

Fig. 5Fig. 5 — Comparação de métodos. O vizinho mais próximo (54 €) falha o ótimo (40 €); a ordenação dos pesos, aqui, acerta. Nenhuma heurística garante o ótimo em geral.

Ora, 54 € NÃO é o custo ótimo — a força bruta mostrou que o melhor circuito é «A–B–D–C–A», com 40 €. O vizinho mais próximo falhou porque, ao escolher gulosamente as ligações baratas no início, ficou «encurralado» e foi obrigado a usar no fim a ligação carésima «D–A» (25 €). Esta é a lição honesta a reter: o algoritmo do vizinho mais próximo dá SEMPRE um circuito, mas não garante o ótimo — usá-lo como se desse a melhor solução é um erro frequente e perigoso.

Uma alternativa é o algoritmo da ordenação dos pesos (ou das arestas mais baratas): ordenam-se todas as arestas por ordem crescente de peso e vão-se acrescentando, uma a uma, desde que não se feche um circuito antes do tempo nem se crie um vértice com três ligações. No grafo da Fig. 4: aceita-se «A–B» (8) e «A–C» (9); rejeita-se «B–C» (10, fecharia o triângulo A–B–C sem passar por D); aceita-se «C–D» (11); e aceita-se «B–D» (12), que fecha o circuito «A–B–D–C–A». O custo é «8+9+11+12 = 40 €» — aqui coincide com o ótimo, e é melhor do que o vizinho mais próximo.

Comparar os dois algoritmos (Fig. 5) revela o essencial: heurísticas diferentes dão resultados diferentes, e nenhuma garante, em geral, a solução ótima. A escolha do algoritmo é um compromisso entre rapidez e qualidade. A Aprendizagem Essencial enquadra estas ideias em problemas reais de logística — localização de armazéns e de aterros, rotas de distribuição, menor consumo de combustível ou menor poluição — e pede que se discuta a viabilidade económica de procurar a solução perfeita. Como ampliação de nível de projeto, a AE sugere ainda a coloração de grafos e o número cromático (por exemplo, colorir um mapa com o menor número de cores), fora do essencial avaliado.

Exemplo resolvido

Vizinho mais próximo e a sua não-otimalidade

Aplica o algoritmo do vizinho mais próximo, a partir de A, ao grafo da Fig. 4 (AB=8, AC=9, AD=25, BC=10, BD=12, CD=11) e compara com o circuito ótimo (40 €).

De A
As ligações a partir de A: AB=8, AC=9, AD=25. A mais barata é AB (8). Vai para B.
De B
Cidades novas a partir de B: C (BC=10) e D (BD=12). A mais barata é BC (10). Vai para C.
De C e regresso
Só falta D: CD=11. Vai para D. De D regressa a A: DA=25 (única forma de fechar).
Custo e comparação
A–B–C–D–A = 8+10+11+25 = 54 €. É maior do que o ótimo (40 €): a heurística falhou, encurralada pela ligação cara D–A.

Resultado: Vizinho mais próximo: A–B–C–D–A, 54 € — pior do que o ótimo (40 €). A heurística não garante a melhor solução.

Erros frequentes

Usar o algoritmo do vizinho mais próximo como se desse sempre a solução ótima do caixeiro-viajante.
Na ordenação dos pesos, aceitar uma aresta que fecha um circuito prematuro ou que cria um vértice com três ligações.

Revisão ativa

Para o grafo da Fig. 4, aplica o algoritmo do vizinho mais próximo a partir de B e compara o custo obtido com o circuito ótimo (40 €), comentando se a heurística acertou.

Evocação ativa

Recorda os pontos-chave — depois revela.

Fontes: Aprendizagens Essenciais de MACS — 11.º ano (Grafos de Hamilton; algoritmos e otimização) (Direção-Geral da Educação (DGE))

Referências e fontes

Fontes

Direção-Geral da Educação (DGE)

Aprendizagens Essenciais de MACS — 11.º ano (Introdução aos grafos)

Modelos de grafos

4 secções~15 min de leitura4 competênciasNível Base 1 · Padrão 2 · Aprofundamento 1

Modelos de grafos

Pontos-chave

Graus e teorema dos apertos de mão

Pontos-chave

Decidir sobre circuitos e caminhos de Euler

Pontos-chave

Caixeiro-viajante por força bruta

Pontos-chave

Vizinho mais próximo e a sua não-otimalidade

Fontes

Modelos de grafos

Pontos-chave

Graus e teorema dos apertos de mão

Pontos-chave

Decidir sobre circuitos e caminhos de Euler

Pontos-chave

Caixeiro-viajante por força bruta

Pontos-chave

Vizinho mais próximo e a sua não-otimalidade

Fontes