# data[].attributes.body
A primeira casa tem a seguinte sequência

2-1-3-4-5-2-3,

A segunda casa tem a seguinte sequência

11-9-8-10-9-12-11-10-12

# data[].attributes.body
1. Um grafo é o conjunto de pontos e linhas que ligam entre si todos ou alguns desses pontos.

Um grafo conexo é um grafo no qual existe sempre uma sequência de arestas a unir quaisquer dois dos seu vértices.

Um grafo completo é um grafo simples em que todos os pares de vértices são adjacentes.

O grau de um vértice é o número de arestas incidentes nesse vértice.

A ordem de um grafo é o número de vértices desse grafo.

# data[].attributes.body
A sequência de letras a iniciar na letra f é

F-E-D-G-B-C-D-F-A-B

# data[].attributes.body
A ordem do grafo é 6 e o grau de todos os seus vértices é 2

# data[].attributes.body
Um caminho é um passeio ou percurso aberto que começa num vértice e termina noutro diferente.

Circuito- Se um percurso é fechado e n~~ao repete nenhuma aresta ele designa-se um circuito. Um circuito começa e termina no mesmo vértice.

Um caminho de Euler ou um caminho euleriano é um caminho que passa uma única vez em cada aresta.

Um circuito de Euler é um circuito que passa uma única vez em cada aresta (sem repetir nenhuma)de um

grafo conexo.

# data[].attributes.body
A-B-H-K-M-O.

# data[].attributes.body
4.3 9 pessoas estavam no evento

(1+2++3+4+5+6+7+8=36)

# data[].attributes.body
Eulerizar um grafo

Consiste em duplicar arestas já existentes (entre vértices adjacentes) com o objetivo de ficar com um grafo

conexo em que todos os vértices tenham grau par. A melhor eulerização é a que acrescenta o menor

número de arestas, de modo a que se obtenha um novo grafo em que todos os vértices tenham grau par

Adicionar arestas de forma correta significa que o número de repetições de arestas seja igual ao número de

arestas acrescentadas.

# data[].attributes.body
1.3 9-12-10-7-6-3-5-1-2-4-1-8-11-4-9-12-10-2

# data[].attributes.body
Circuito Hamiltoniano

É um 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).

Num grafo chama-se circuito de Hamilton (ou hamiltoniano) a um caminho que começa e acaba no

mesmo vértice, passando por todos os vértices e não mais do que uma vez por cada um deles.

Um grafo que admite um circuito hamiltoniano é chamado um grafo de Hamilton ou um grafo

hamiltoniano.

Um caminho que percorra todos os vértices de um grafo conexo, sem repetições de vértices, chama-se

caminho de Hamilton ou caminho hamiltoniano.

ST-A-B-G-ST

ST-A-G-B-ST

ST-B-A-G-ST

ST-B-G-A-ST

ST-G-A-B-ST

ST-G-B-A-ST

SEQUÊNCIAS DE MENOR DISTÂNCIA

ST-A-G-B-ST

ST-B-G-A-ST

número mínimo de km que o camião percorre

semanalmente 753KM

# data[].attributes.body
A(41)-D(50)-B(122)-C(64)-A

# data[].attributes.body
Árvore é um grafo conexo que não possui qualquer circuito.

Árvore geradora ou abrangente é um subgrafo de um grafo conexo que tem todos os vértices desse

grafo e é uma árvore.

Algoritmo de Kruskal: as arestas do grafo, conexo, vão-se unindo por ordem crescente dos pesos, desde

que não se formem circuitos e que se garanta que no final todos os vértices estão na árvore.

# data[].attributes.body
São precisas 11h16 para que realizar o

percurso entre as 5 cidades.

Algoritmo de Prim:

• começa-se num vértice qualquer do grafo original (conexo),

• seleciona-se a aresta com menor peso nesse vértice;

• em cada passo seguinte, observam-se as arestas que saem de qualquer vértice já alcançado

para um vértice não incluído na árvore. Escolhemos a que tem menor peso ( e que não forme

circuito).

• termina-se quando todos os vértices do grafo fizerem parte da árvore.

# data[].attributes.body
Demora 11H44 para realizar o percurso

# data[].attributes.body
Digrafo: é um grafo em que as arestas têm um sentido associado.

Caminho crítico: Percurso representado por uma sequência de tarefas (representadas por vértices) e que

corresponde ao maior somatório dos pesos dos vértices que o compõe. Permite calcular o tempo mínimo na

realização de um conjunto de tarefas.

2.2. TA-TD-TE-TH 19dias

TA-TB