UDESC – DCC BCC DISCIPLINA : TEG0001 – Teoria dos Grafos PRIMEIRA LISTA DE EXERCÍCIOS

1.) Identifique para cada um dos três grafos abaixo:

. número de nós e arcos;

. o grau de cada nó;

. Compare a soma de todos os graus dos nós de cada grafo com o

número de arcos. O que você pode concluir ?

2.) O grafo de interseção de uma coleção de conjuntos A1;A2; ...;An é o

grafo que tem um vértice para cada um dos conjuntos da coleção e

tem uma aresta conectando os vértices se esses conjuntos têm uma

interseção não vazia. Construa o grafo de interseção para as

seguintes coleções de conjuntos:

a.)

A1 = {0; 2; 4; 6; 8}

A2 = {0; 1; 2; 3; 4}

A3 = {1; 3; 5; 7; 9}

A4 = {5; 6; 7; 8; 9}

A5 = {0; 1; 8; 9}

b.)

A1 = {... ;-4;-3;-2;-1; 0}

A2 = {... ;-2;-1; 0; 1; 2; :...}

A3 = {... ;-6;-4;-2; 0; 2; 4; 6; ...}

A4 = {...;-5;-3;-1; 1; 3; 5;...}

A5 = {... ;-6;-3; 0; 3; 6; ...}

3.) Forneça a função G que é parte da definição formal do grafo

direcionado ilustrado

4.) Responda as perguntas a seguir sobre o grafo abaixo:

a.) O grafo é simples ?

b.) O grafo é completo ?

c.) O grafo é conexo ?

d.) Voce pode encontrar dois caminhos de 3 para 6 ?

e.) Voce pode encontrar um ciclo ?

f.) Voce pode encontrar um arco cuja remoção transformará o grafo

em um grafo acíclico ?

1

3

3a

cb

d

g.) Voce pode encontrar um arco cuja remoção transformará o grafo

em um grafo não conexo ?

5.) Esboce um desenho para cada um dos grafos indicados a seguir:

a.) Um grafo simples com três nos, cada um de grau 2;

b.) Um grafo com quatro nós e ciclos de comprimento 1,2,3, e 4;

c.) Um grafo não completo com 4 nós, cada um de grau 4.

6.) Quantos vértices e quantas arestas têm os grafos abaixo?

a.) Kn (grafo completo)

b.)

c.)

7.) Quantas arestas tem um grafo com vértices de graus 5; 2; 2; 2; 2; 1?

Desenhe um possível grafo.

1

2

4

3a5 5

6

7

a7

a6

a4

a1

a2

a3

8.) Existe um grafo simples com cinco vértices dos seguintes graus? Se

existir, desenhe um possível grafo.

a.) 3; 3; 3; 3; 2 b.) 1; 2; 3; 4; 5 c.) 1; 2; 3; 4; 4 d.) 3; 4; 3; 4; 3 e.) 0; 1; 2; 2; 3 f.) 1; 1; 1; 1; 1

9.) Seja o grafo G abaixo. Determine o grau de cada vértice e o grau

total de G.

10.) Prove o Teorema do aperto de mãos ou handshaking: Seja G

um grafo. A soma dos graus de todos os vértices de G é duas vezes o

número de arestas de G. Especificamente, se os vértices de G são v1;

v2; ... ; vn, onde n é um inteiro positivo, então

Grau de G = grau(v1) + grau(v2) + . . . + grau(vn)

= 2 x ( o número de arestas de G).

11.) Desenhe K6 e K3,4.

12.) Qual dos grafos a seguir não é isomorfo aos outros e porque

?

ba

c

13.) Determine se cada um dos grafos abaixo é bipartido.

a.)

b.)

c.)

d.)

e.)

14.) Qual dos grafos a seguir não é isomorfo aos outros e por que?

15.) Verifique se os dois grafos são isomorfos. Se forem, forneça

uma função ou funções que estabalecem o isomorfismo. Se não

forem, explique por que:

a.)

b.)

16.) Um grafo simples é um grafo que não possui laços nem

arestas paralelas. Num grafo simples, uma aresta com vértices (nós

terminais) u e v é representada por uv. Determinar quais são os

grafos com quatro vértices {u; v;w; x} e duas arestas, sendo que uma

delas é a aresta uv?

cba

e

d

e

a

3c

2

1

b5

d4

V6

V1

f

V3d

V5

V4

b

V2

a

a

e

c

b

17.) O fecho transitivo direto (FTD) de um vértice v é o conjunto

de todos os vértices que podem ser atingidos por algum caminho

iniciando em v.

Dado o grafo abaixo calcular o FTD a partir do vértice V5.

18.) O fecho transitivo inverso (FTI) de um vértice v é o conjunto

de todos os vértices a partir dos quais se pode atingir v por algum

caminho. Dada a figura abaixo calcular o FTI para o vértice V5.

19.) Prove que dois grafos não são isomorfos se:

a.) Um tem mais nós do que o outro;

b.) Um tem mais arcos do que o outro;

c.) Um tem arcos paralelos e outro não;

d.) Um tem um laço e o outro não;

e.) Um tem um nó de grau K e o outro não;

f.) Em é conexo e o outro não;

g.) Um tem um ciclo e o outro não.

20.) Desenhe todos os grafos não isomorfos simples com três nós

21.) Desenhe todos os grafos não isomorfos simples com quatro

nós

22.) Prove que o K23 é um grafo planar

23.) Prove que o grafo da figura a seguir é planar

24.) Se um grafo planar simples e conexo tem seis nós, todos de

grau 3, em quantas regiões ele divide o plano ?

25.) Se todos os nós de um grafo planar simples e conexo tem

grau 4 e se o número de arcos é 12, em quantas regiões ele divide o

plano ?

26.) Determinar se os grafos abaixo são planares (encontrando

uma representação planar) ou não (encontrando um subgrafo

homeomorfo a K5 ou K33 ).

b.)

c.)

4

5

1 2

3

6

27.) Identificar quais dos grafos abaixo possuem:

. múltiplos arcos;

. contem um loop;

. são simples;

. são conectados;

. contem um nó isolado.

. Para cada um dos grafos escrever a sequencia dos graus.

f d

ba

e

c

g

28.) Dado que tem-se 4 nós, construir todos os possíveis grafos

simples a partir dos 4 nós.

29.) Encontre o número de nós e de arcos em cada um dos

seguintes grafos:

. grafos nulos

. grafos cíclicos

. grafos completos

. grafos bipartidos

30.) Desenhe os seguintes grafos:

. grafo simples com 5 nós e 6 arcos

. dois grafos regulares distintos com 5 nós

.grafo simples com sequencia do grau dada por: (2,2,2,3,3)

. grafo com sequencia do grau dada por: (2,2,2,2,3)

. dois grafos distintos com 6 nós, 9 arcos e sequencia do grau dada

por: (2,2,3,3,3,5)

31.) Dado os 3 cenários, compostos cada um de três grafos,

identificar para cada cenário os dois grafos que são iguais.

32.) Dada uma população de uma determinada cidade composta

de N rapazes e moças. Como pode ser modelado o relacionamento

do conjunto de rapazes e moças que tem interesse em sair juntos?

33.) Considerando que você faz parte de um site de

relacionamentos (Facebook), como consegue-se identificar quais são

as pessoas que possuem relacionamento com você ? Como voce

sabe se duas pessoas quaisquer possuem relacionamento ? Qual o

menor caminho entre você e uma determinada pessoa ? O que voce

pode concluir dos problemas 1 e 2 ?

34.) Mostre que a desigualdade a <= 3*n – 6 é válida para

, o que mostra que está desigualdade é uma condição

necessária, mas não suficiente, para um grafo com n >=3 ser

planar

35.) Dado o grafo G:

3.a) Determinar se os grafos abaixo são subgrafos de G.

G1

G2

G3

36.) Dado o grafo G a seguir

Determinar se os grafos abaixo são clique de G:

G1

G2

Qual é o maior clique de G ?

37.) Identificar se os grafos abaixo são conexos

38.) Identificar se os grafos abaixo são conexos ou não.

39.) Dado o grafo G no canto superior esquerdo da figura abaixo,

verificar se os demais grafos apresentados são ou não subgrafos de

G.

40.) (Implementa o algoritmo de busca de nós de um grafo G em

profundidade utilizando pilhas ao invés de chamadas recursivas.

41.) Determine se as declarações abaixo: falsa(F) ou verdadeira

(V)

a.) Cada grafo desconexo possui um nó isolado ( ).

b.) Um grafo é conectado se e somente se algum nó está conectado

a todos os outros nós ( ).

42.) Determine se contêm as seguintes características:

a.) Um caminho que não é uma trilha.

b.) possui uma trilha que não é fechada que não é um

caminho.

43.) Dado o grafo abaixo, determinar:

. caminhos máximos.

. clique máximo.

. conjunto máximo de nós independentes.

b

d

a

c

44.) Provar que se um grafo possui um circuito Euleriano, então

cada vértice do grafo tem grau par.

45.) Se cada vértice de um grafo tem grau par, então o grafo tem

um circuito Euleriano?

46.) Uma casa possui uma divisão representada pela planta

abaixo. É possível uma pessoa sair do cômodo A, terminar no

cômodo B e passar por todas as portas da casa exatamente uma

única vez? Se sim, apresente um possível trajeto.

A planta da casa pode ser representada pelo grafo abaixo:

47.) Determine se o grafo abaixo tem um circuito Euleriano. Em

caso positivo ache um circuito Euleriano para o grafo.

48.) Verificar se os grafos abaixo são isomorfos.

49.) Os grafos apresentados abaixo são isomorfos ?

50.) Suponha que uma companhia aérea recebeu permissão para

voar nas seguintes rotas, conforme grafo apresentado abaixo.

Visando economizar combustível, determinar o conjunto de rotas (arvore

geradora) que interconecta todas as cidades.

51.) Prove que, em qualquer grafo simples G com n nós e a arcos,

(2*a <= n**2 – n)

52.) Prove que um grafo simples conexo com n nós tem pelo

menos n-1 arcos (Sugestão: Mostre que essa proposição pode ser

enunciada na forma “Um grafo simples conexo com m arcos tem, no

máximo, m+1 nós”.

53.) Dado o grafo abaixo, a remoção de qualquer uma das três

arestas do circuito leva a uma árvore. Determinar as três árvores

geradoras.

54.) Dada a figura abaixo:

. Indique percursos simples e não simples em G1

a

b

G1

a

b c

d

e

ca b

d e2

. Indique percursos elementares em G2

. Todo percurso elementar é simples. Todo percurso simples é

elementar? Explique.

. Indique um ciclo em G1 e um ciclo elementar em G2

. Indique um caminho de comprimento 4 em G2 e um percurso de

comprimento 6 em G2.

55.) Dado o grafo abaixo, localizar um depósito de distribuição de

mercadorias numa rede de rodovias para abastecer diversos clientes

com localizações fixas e conhecidas de maneira a minimizar a soma

das distâncias, aos clientes. Neste caso os nós do grafo representam

os clientes.

56.) Calcule o centro, o diâmetro, a mediana e os vértices

periféricos de cada um dos grafos abaixo:

a

b c

d e

f

g h

i j

a

b c

d e

f