10º Ano
11º Ano
Modelos Matemáticos:
Modelos de Grafos:
Conceitos:
Grafo: Representação esquemática constituída por vértices e por arestas.
Vértice: Ponto constituinte de um grafo.
Aresta: Segmento que une vértices.
Arestas Adjacentes: Arestas incidentes no mesmo vértice.
Arestas Paralelas: Arestas distintas que ligam os mesmos vértices.
Lacete: Aresta que liga um vértice a ele próprio.
Vértice Isolado: Vértice que não tem arestas adjacentes.
Vértices Adjacentes: Vértices que têm pelo menos uma aresta que os liga.
Grafo Conexo: Grafo no qual existe sempre uma sequência de arestas a unir quaisquer dois
dos seus vértices.
Grafo Simples: Grafo que não tem arestas paralelas nem lacetes.
Multigrafo: Grafo que tem arestas paralelas e/ou lacetes.
Ordem de um Grafo: Número de vértices constituintes do grafo.
Dimensão do Grafo: Número de arestas constituintes do grafo.
Grafo Completo: Grafo em que qualquer par de vértices está ligado por uma aresta. Este tem
uma notação especial e é denominado por Kn, em que n representa a ordem do grafo.
Grau ou Valência: Número de arestas que incidem num vértice.
Grafo Regular: Grafo em que todos os vértices têm o mesmo grau.
Grafo Orientado ou Dígrafo: Grafo cujas arestas têm sentidos.
Caminho: Sequência alternada de vértices e arestas adjacentes.
Circuito: Caminho que começa e acaba no mesmo vértice. O seu comprimento é igual ao
número de arestas que o constituem.
Caminho de Euler: Caminho que percorre todas as arestas de um grafo uma única vez. Apenas
pode ser feito se tiver, no máximo, 2 vértices de grau impar.
Circuito de Euler: Circuito que passa por todas as arestas do grafo uma única vez. Apenas pode
ser feito se tiver todos os vértices com grau par.
Grafo de Euler: Grafo conexo e com todos os seus vértices com grau par.
Eulerização de um Grafo: Processo através do qual se procura duplicar algumas das arestas
existentes num grafo conexo e sem circuito de Euler, de modo que se obtenha um novo grafo
em que todos os vértices tenham grau par.
Melhor Eulerização: Eulerização que acrescenta o número mínimo de arestas.
Circuito de Hamilton: Caminho que percorre todos os vértices de um grafo conexo uma única
vez, começando e terminando no mesmo vértice (único que se repete).
Grafo de Hamilton: Grafo em que se pode encontrar, pelo menos, um circuito de Hamilton.
Peso: Número que se atribui a cada uma das arestas de um grafo.
Grafo Pesado ou Ponderado: Grafo com arestas pesadas ou ponderadas.
Circuitos de Hamilton e Grafos-grelha: Se o número de colunas e linhas for par, o grafo-grelha
tem circuitos de Hamilton;
Se ou o número de colunas ou o número de linhas for ímpar, o grafo-grelha tem circuitos de
Hamilton;
Se ambos o número de colunas e o número de linhas forem impares, o grafo-grelha não tem
circuitos de Hamilton.
Fórmulas:
Relação entre Arestas e os Graus dos Vértices:
∑GV = 2A
GV: Grau dos Vértices
A: Número de Arestas
Ordem dos Grafos Kn
(n-1)!
n: Ordem do Grafo
Dimensão dos Grafos Kn
n(n−1)
2
n: Ordem do Grafo
Procedimentos:
Melhor Eulerização:
1º Passo – Parte-se do grafo dado e acrescentam-se arestas por duplicação das já existentes,
até que se obtenha um grafo conexo e só com vértices de grau par.
2ª Passo – As arestas que acrescentamos devem ter uma cor diferente de modo que se
destaquem das do grafo original.
3ª Passo – Indicar um circuito de Euler (verificação)
Eulerização de Grelhas não Retangulares:
1ª Passo – Localizar todos os vértices de grau ímpar.
2º Passo – Formar pares de vértices de grau ímpar.
3º Passo – Procurar o comprimento do caminho menor entre cada par.
4º Passo – Se necessário, reorganizar os pares de modo de modo que a soma do número de
arestas que se acrescenta seja mínima.
