USI3G Trabalho1

Trabalho 1 – Grafos Introdução

1) Pesquise e diferencie caminho HAMILTONIANO de EULERIANO

CAMINHO HAMILTONIANO: Um caminho Hamiltoniano num grafo é um caminho simples que contém todos os vértices do grafo, ou seja, é o caminho que permite passar por todos os vértices de um grafo G, passando por todos apenas uma só vez por cada.

CAMINHO EULERIANO: Um caminho Euleriano num grafo é um caminho simples que contém todas as arestas do grafo, ou seja, é o caminho que usa cada aresta exatamente uma vez.

2) A) Defina um grafo em sua notação.
Um grafo G é um par de conjuntos (V,E), tal que V=V(g)={V1,...,Vn} é o conjunto dos vértices e E=E(g) é o conjunto das Arestas a cada uma das quais correspondem um subconjunto de V(g) de cardinalidade 2.

B) Desenhe o grafo

Caminho Simples ( De A á D)
A-B-C-D

Caminho Não Simples
B-C-D-B-A

F) De um significado semântico para o seu grafo Grafo simples com 5 vértices com um vértice isolado e contendo dois vértices com três incidências e dois com duas incidências.

3) Faça um grafo da linha Férrea de Minas Gerais com base em mapas reais.

4) O que são grafos Isomorfos? Dê 2 exemplos de tais grafos.

Em teoria dos grafos, um isomorfismo dos grafos G e H é uma bijeção entre os conjuntos de vértices de G e H

de tal forma que quaisquer dois vértices u e v de G são adjacentes em G se e somente se ƒ(u) e ƒ(v) são adjacentes em H. Este tipo de bijeção é comumente chamado de "bijeção com preservação de arestas", de acordo com a noção geral de isomorfismo sendo uma bijeção de preservação-de-estrutura.

5) Vá a São Paulo partindo de Montes Claros e passe por um caminho não simples