Problemas em Grafos

Problema 1

1. Em um certo reino, existem 300 cidades, e cinco estradas partem de cada cidade. Quantas estradas existem no reino?


Problema 2

Na cidade de Micrópolis, há 7 telefones. Um candidato a prefeito prometeu que ampliaria a rede de telefonia de modo que cada um dos 7 telefones esteja conectado diretamente a exatamente 5 outros telefones. É possível que ele cumpra sua promessa?

Use o  seguinte Teorema

Em todo grafo G=(V,E), a soma dos graus dos vértices é igual ao dobro do número de arestas, ou
seja,

$\sum_{v \in V}$ d(v) =2*|E| 

Problema 3

 Existem 105 cidades em Arbórea. Algumas delas são conectadas por estradas, e cada par de cidades é

conectado por um e somente um caminho simples. Quantas estradas existem?

Teorema: Seja G = (V,E) um árvore , |V| = n e |E| = m, então  m = n -1.

Problema 4

Mostre que em toda festa, existem pelo menos duas que possuem deram a mesma quantidade de  apertos

de mão nos participantes da festa.

Separe em dois casos:

Caso 1) Existe uma pessoa que não apertou a mão de ninguém.

Caso 2) Cada pessoa apertou a mão de pelo menos uma pessoa.

Problema 4

É possível caminhar pela casa da figura abaixo de forma que cada porta da casa seja usada exatamente

uma vez? Justifique.

Problema 5

Verifique se os grafos são bipartidos:

Problema 6

Seja G = (V;E) um grafo simples conexo não-euleriano. Queremos construir um grafo H que seja euleriano e que contenha G como subgrafo. Considere os seguintes possíveis processos de construção:

(I) Acrescenta-se um novo vértice, ligando-o a cada vértice de G por uma aresta.

(II) Acrescenta-se um novo vértice, ligando-o a cada vértice de grau ímpar de G por uma aresta.

(III) Cria-se uma nova cópia G' do grafo G e acrescenta-se uma aresta ligando cada par de vértices correspondentes.

(IV) Escolhe-se um vértice arbitrário de G e acrescentam-se arestas ligando este vértice a todo vértice de grau ímpar de G.

(V) Duplicam-se todas as arestas de G.

(VI) Acrescentam-se arestas a G até se formar o grafo completo com |V| vértices.

Quais dos processos acima sempre constroem corretamente o grafo H?

(a) Somente (II) e (IV)                 (b) Somente (II), (IV) e (V)         (c) Somente (III), (V) e (VI)

(d) Somente (II), (IV), (V) e (VI)               (e) Somente (I), (III), (IV) e (V)

Problema 7

Todo um grafo possui n vértices, cada um dos quais com grau no mínimo (n−1)/2, então ele é

conexo. Falso ou Verdadeiro?

Problema 8

É possível que a seguintes listas de números sejam os graus de todos os vértices de um grafo simples?

i) 2,2,2,3 

ii) 1,2,2,3,4

iii) 3,4,3,3,2

iv) 4,4,4,4,2

Nos casos em que a resposta é afirmativa, represente um grafo nessas condições.

Problemas 9

É possível que os cavalos do tabuleiro (I) fiquem na posição do tabuleiro (II) ?

Problema 10

Podemos desenhar uma estrela de cinco pontas sem tirar o lápis do papel . Justifique

Problema 11

Podemos desenhar um envelope sem tirar o lápis do papel mas não terminamos no

mesmo ponto que começamos. Justifique

Problema 12

Uma criança diz ter posto a ponta do lápis numa das bolinhas e com movimentos contínuos

(sem levantar e sem retroceder o lápis) traçou as linhas que formam o desenho da casa,

traçando cada linha uma única vez. Rudini, professor de Matemática Discreta, acha que ela

está trapaceou pois não foi capaz de achar nenhuma seqüência que pudesse produzir tal

resultado. Você concorda com Rudini?

Problema 13

Três casas e têm de ser ligadas ao gás, à água e à electricidade. Será possível encontrar um

grafo tal que as (linhas que representam as) arestas não se cruzam?

Prove por absurdo, usando o Teorema de Euler F = A – V +2.

Problema 14

Residência do bilionário Count Van Diamond, que acaba de ser assassinado.  Sherlock Gomes (um conhecido detetive que nas horas vagas é um estudioso da Teoria dos Grafos) foi chamado para investigar o caso. 

O mordomo alega ter visto o jardineiro entrar na sala da piscina (lugar onde ocorreu o assassinato) e logo em seguida deixar sair daquela sala pela mesma porta que havia entrado.

O jardineiro, contudo, afirma que  ele não poderia ser a pessoa vista pelo mordomo, pois ele havia entrado na casa, passado por todas as portas uma única vez e, em seguida, deixado a casa.

Sherlock Gomes avaliou a planta da residência e em poucos minutos declarou solucionado o caso.

a) Quem poderia ser o suspeito indicado por Sherlock Gomes?

b)      Qual o raciocínio utilizado pelo detetive para apontar o suspeito? 

Problema 15

Mostre que os números de 1 a 16 podem ser escritos numa reta, de tal modo que a soma de quaisquer dois

números adjacentes seja um quadrado perfeito.

Problema 16

Mostre que os números de 1 a 16 não pode ser escritos ao redor de uma circunferência, de tal modo que a

soma de quaisquer dois números adjacentes seja um quadrado perfeito.

Problema 1,3 e 4 retirados de 

http://www.obm.org.br/export/sites/default/semana_olimpica/docs/2006/grafos_onofre.pdf

Problema 2 e 9 retirados de 

http://www.obm.org.br/export/sites/default/revista_eureka/docs/artigos/grafos_dupla.pdf