Grafos-P2-Exercicios

Prévia do material em texto

Grafos ­ Prova 2 ­ Exercicios 
 
Aulas de Grafos em Espanhol com a Dona Florinda (entendível) 
Aula 1 ­> http://www.youtube.com/watch?v=pzca71UtH­A&list=PL5098BF5A01819B3B&index=1 
Nessa aula 1 tem vários conceitos que ficam fáceis de entender, tem aula de fluxo no canal também (nas 
últimas aulas) 
Canal no Youtube 
http://www.youtube.com/playlist?list=PL5098BF5A01819B3B 
 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Aula 08: Corte em Grafos 
1. Um grafo é chamado par quando todos os seus vértices possuem grau par. Prove que um grafo é 
par se e somente se |∂(V'(G))| é par para todo V'(G) ⊂ V(G). 
Tentativa de resposta: Supondo G = (V(G), E(G), ΨG(e)) um grafo par, ou seja, para qualquer v 
pertencente a G, d(v) = 2k, com k ∈ N. Considere V’(G), um subconjunto qualquer de V(G) tal que V’(G) ⊂ V(G) 
e V’(G) ≠ ∅. O corte em aresta de V’(G) será E[V’(G),V’’(G)] sendo V’’(G) = V(G) \ V’(G), além disso, e ∈ 
E[V’(G) , V’’(G)] se ΨG(e) = {v’,v’’}, tal que v’ ∈ V’(G) e v’’ ∈ V’’(G).  
 
 
Tentativa 2 de resposta: (Prova por contradição)  
Suponha um grafo par G = (V(G), E(G), ΨG(e)). 
Dado um corte em V’(G) tal que V'(G) ⊂ V(G) e V'(G) ≠ ∅, temos que ∂(V'(G)) = ∂(V'’(G)) com V'’(G) = 
V(G)\V’(G). 
Suponha que |∂(V'(G))| seja ímpar, então, |∂(V'’(G))| é impar também. Seja v’ ∈ V’ e v’’ ∈ V’’ sendo que v’ e v’’ 
devem ser pares, pois pertencem a V(G). 
­ Caso símples (G contendo apenas 2 vértices): Seja e tal que ΨG(e) = {v’, v’’}, porém v’ e v’’ terão grau 
ímpar, o que é uma contradição. Sejam e e f tal que ΨG(e) = {v’, v’’} e ΨG(f) = {v’, v’’}, porém |∂(V'(G))| e 
|∂(V'’(G))| terão grau par, o que é uma outra contradição. 
­ Caso mais complicado (V(G) contém mais de dois vértices): Sejam qualquer vértice v’’’ ∈ V’, sendo 
v’’’ tendo grau par. Seja e, f e e’  tal que ΨG(e) = {v’, v’’’}, ΨG(f) = {v’’, v’’’} e ΨG(e’) = {v’, v’’}. Nesse caso, v’, v’’ e 
v’’’ terão grau par, porém |∂(V'(G))| e |∂(V'’(G))| terão grau par também, o que é uma contradição. 
 
Tentativa 3 de resposta: (prova baseada na solução do ex. 2 da lista de revisão feita pelo professor) 
Ida: Suponha que G seja par. Seja G’ = (V(G’), E(G’), ΨG’(e)), o subgrafo gerador de G formado pelos vértices 
V'(G) ⊂ V(G). Neste caso temos que 2|E(G’)| + |∂(V(G’))| =  G(v )∑ 
v  ε V (G )′ ′
d ′    
2*m(G’) + |∂(V(G’))| = 2K1 + 2K2 + 2K3 +... + 2Kn(G’) 
 |∂(V(G’))| = 2*(K1 + K2 + K3 +... + Kn(G’)  ­ m(G’)) 
 |∂(V(G’))| = 2K (K = qualquer coisa, o importante é que é par) 
Logo,  |∂(V(G’))|  é par. 
 
Volta: Suponha por absurdo que G não é par. Então existem pelo menos 2 vértices ímpares, pois  G(v)∑
 
v ε V (G)
d  
= 2*m(G) por definição, é par. 
Seja V’(G) = {v, w} tal que existe e  E’(G) tal que ΨG(e) = {(v, w)}. Neste caso |V’(G)| = 2 e como v e w sãoε  
ímpares e há uma aresta que incide nos dois vértices, e e  |∂(V’(G))|, |∂(V’(G))| é ímpar, ou seja, dado por 2K +ε  
1. Logo |∂(V’(G))|  é ímpar e |V’(G)| é par, o que é uma contradição. 
 
 
2. Prove que todo corte mínimo é um enlace. (tenso) 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Aula 09: Subgrafos Induzidos e Geradores 
1. Prove que todo corte mínimo é um enlace. (mesma da aula 8, pergunta 2) 
 
2. Verifique sob quais condições um torneio possui um ciclo Hamiltoniano. 
 
3. Desenhe os subgrafos induzidos do grafo G sob as condições descritas abaixo: 
G=(V(G),E(G),ΨG(e)); 
V(G)={v1, v2, v3, v4, v5, v6, v7, v8}; E(G)={e1, e2, e3, e4, e5, e6, e7, e8}; 
ΨG(e1)={v1, v2}; ΨG(e2)={v1, v3}; ΨG(e3)={v4, v5}; ΨG(e4)={v6, v7};  
ΨG(e5)={v7, v8}; ΨG(e6)={v5, v6}; ΨG(e7)={v3, v5}; ΨG(e8)={v2, v3};  
(a) G[{v1, v3, v4, v5}] 
 
(b) G[{e1, e2, e3, e4}] 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Aula 11: Passeios e Trilhas 
1. Prove que se um passeio W não possui vértices repetidos então W é um caminho. 
pela definição de passeio temos qupela definição de passeio temos que se um passeio não tem 
vertices repetidos ele é um caminho (PROVAVELMENTE TÁ ERRADO)e se um passeio não tem 
vertices repetidos ele é um caminho (PROVAVELMENTE TÁ ERRADO) 
 
2. Escreva a definição de passeio e de trilha para grafos direcionados. 
Um passeio W em um grafo G=(V(G),E(G),PG(e)) é definido pela dupla ordenada  
W = (WV(G)(i), WE(G)(j)) definida por WV(G)(i):I → V(G) com I={1, 2, …, k}, WE(G)(j):J → E(G) com J={1, 2, 
…, k­1} e k ∈ ℝ* finito, tal que, dados i, i' ∈ I, W[V(G)(i]) = vi, WV(G)(i) = vi' e WE(G)(i) = ei, temos que P(G)(ei) 
= {vi, vi'} se e somente se i' = i + 1. Nesta definição, WV(G)(i) e WE(G)(j) podem ser tratadas como 
sequências ou como funções. 
 
Uma trilha T em um grafo G=(V(G),E(G),PG(e)) é definido pela dupla ordenada T = (T[V(G)](i), T[E(G)] (j)) 
definida por TV(G)(i): I → V(G) com I={1, 2, …, k}, TE(G)(j):J → E(G) com J={1, 2, …, k­1} e k {1, 2, …, m(G)} ∈ 
, tal que, dados j, j' ∈ J, TE(G)(j) = ej, TE(G)(j') = ej', temos que ej ≠ ej' se e somente se j≠ j' e que, dados i, i' ∈ 
I, TV(G)(i) = vi, TV(G)(i) = vi' e TE(G)(i) = ei, temos que PG(ei) = {vi, vi'} se e somente se i' = i + 1. Nesta 
definição, TV(G)(i) e TE(G)(j) podem ser tratadas como sequências ou como funções.  
Assim, uma trilha é um passeio no qual não há repetição de arestas e um caminho é uma trilha no qual não há 
repetição de vértices. 
 
3. Dado um grafo bipartido completo Kn',n'' quais são as condições sob as quais existe uma trilha que 
passa por todos os seus vértices. Justifique. 
Explicação informal: 
Para que o grafo bipartido completo Kn’,n’’ que passe por todos os vértices existentes no grafo, n’ e n’’ devem 
diferenciar em no máximo 1 vértice, e somente 1 um vértice. 
n’ = n’’ ou n’ = n’’ + 1 ou n’’ = n’ + 1 
Prova por indução: 
Base: Seja n’=1 e n’’=2: 
 
Passo: Partindo­se de um vértice k em n’, sempre teremos que [k+1] estará presente em n’’ e que os vertices 
[k] e [k+1] estão ligados por uma única aresta. 
 
4. Dados todos os possíveis torneios com quatro vértices, encontre a menor trilha minimal e a trilha 
máxima para cada um deles. 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Aula 12: Grafos Eulerianos 
1. Escreva um teorema que defina uma trilha Euleriana com respeito ao grau dos vértices, do modo 
como foi feito para o Teorema 1 desta aula. 
Possivel teorema (CORRIJAM) 
Um grafo G é chamado de trilha Euleriana quando existe uma trilha não fechada que percorre todos os                                   
vértices e arestas de G. 
FALTA A PROVA DO TEOREMA! 
 
2. Verifique se todo grafo Euleriano possui o mesmo número de vértices e arestas. 
 
Verificar através de contradição? Pelo desenho abaixo já prova que não (grafo euleriano de 5 vértices e 10 
arestas) 
 
3. Qual é a diferença entre um ciclo Hamiltoniano e um grafo Euleriano? Verifique se todo ciclo 
Hamiltoniano é um grafo Euleriano e vice­versa. 
Tacioli:  
Ciclo hamiltoniano  se resume em um grafo que possui um ciclo que tem que passar somente uma vez a 
cada vertice(exceto o vertice inicial(ele repete para fechar o ciclo e só ele)  
Já um grafo euleriano é quando tem uma trilha fechada(ou seja um ciclo, que NAO pode repetir arestas), que 
percorre todos os vertices e arestas do grafo, (podendo repetir vertices) 
Um ciclo hamiltoniano não necessariamente é um grafo euleriano, mas um grafo euleriano é sempre 
um ciclo hamiltoniano. Aeee!leleke lek lek lek lek 
(Daniel: Mas se um ciclo hamiltoniano não pode repetir vértices e um grafo euleriano pode, como que um 
euleriano é sempre um hamiltoniano?) 
 
Luis onde ta esse negocio de hamiltoniano, não to achando . . .aula 09mas ta um lixo la, entra aqui 
http://www.professeurs.polymtl.ca/michel.gagnon/Disciplinas/Bac/Grafos/EulerHam/euler_ham.html#
Hamilton 
Principal diferença é que no ciclo hamiltoniano nao pode repetir vertices intermediarios, e nografo 
euleriano pode. E tambem que no grafo euleriano precisamos passar por TODAS arestas, já no ciclo 
hamiltoniano não precisamos,  
 
(CHUTE) Um ciclo Hamiltoniano é um ciclo que passa por todos os vértices de um dado grafo exatamente 
uma vez (tirando o inicial), enquanto um grafo Euleriano é um grafo que possuí uma trilha fechada que passa 
por todos os vértices qualquer número de vezes e por todas as arestas exatamente uma vez. 
 
Possível provar que nem todo ciclo Hamiltoniano é um grafo Euleriano por contradição e vice versa, a partir de 
um grafo base: 
 
Exemplo: grafo possuí ciclo Hamiltoniano (AB, BC, CD, DE, EA) e também possuí circuito Euleriano, porém 
eles são distintos um do outro. 
 
4. Sob quais condições um grafo bipartido completo é um grafo Euleriano? Justifique. 
Sabe­se que um grafo bipartido completo é tal que, para G=(V(G),E(G),PG(e)), com V(G) = V1 + V2, para todo 
v E V1 e u E V2, existe uma aresta tal que PG(e) = {v, u} 
Sendo tam(V1) = m e tam(V2) = n, cada vértice de V1 deverá estar conectado a todos os outros vértices de 
V2, e vice­versa. Isso implica que o grau de cada vértice em V1 será n, e o grau de cada vértice em V2 será 
m. Sabendo que um grafo Euleriano precisa que todos os vértices possuam grau par, tem­se que o tamanho 
dos subconjuntos V1 e V2 deve ser par. Logo, as condições são: 
1. Que o número total de vértices (n + m) seja par 
2. Que o tamanho de cada subconjunto de vértices também seja par (K6,2 é valido, K3,5 não é) 
(justificativa é suficiente?) 
 
5. Sob quais condições um grafo bipartido completo é uma trilha Euleriana? Justifique. 
Continuando do desenvolvimento do exercício anterior, sabe­se que uma trilha Euleriana somente é possível 
se existirem no máximo 2 vértices com grau ímpar. Por outro lado, se nenhum vértice possuir grau ímpar, 
será possível um grafo Euleriano. Vamos remover esse caso limitando então o número de vértices de grau 
ímpar de 1 a 2. Com isso dito, por definição, todo grafo bipartido completo vai possuir somente n vértices de 
grau m e m vértices de grau n. Logo, qualquer grafo onde o tamanho de cada subconjunto de vértices seja 
maior que 2 fere o pré­requisito para uma trilha Euleriana. 
­ Supondo então um grafo bipartido completo K2,m ­ 2 , onde m seria o número de vértices do grafo, isto é, 
tam(V1) = 2 e tam(V2) = m ­ 2. Todos os vértices de V2 possuíriam então grau 2 (par), enquanto V1 possuíra 2 
vértices com grau (m ­ 2). Se m for ímpar, pré­requisito para trilha euleriana é então satisfeito. 
Logo, primeiro caso para um grafo bipartido completo ser trilha Euleriana: tam(V1) = 2 e tam(V2) = m ­ 2, com 
m (número de vértices do grafo) ímpar 
­ Analogamente, supondo um grafo K1,m ­ 1 , todos os vértices de V2 possuíriam grau 1, enquanto o vértice 
singular de V1 possuíria grau m ­ 1. Como os vértices de V2 possuíriam então grau ímpar, para atender ao 
pré­requisito dito, é necessário que eles sejam no máximo 2 vértices, e que o vértice de V1 possua grau par. 
Se V2 for de tamanho 1, o vértice de V1 possuí grau ímpar, quebrando o pré­requisito. Se V2 for de tamanho 2, 
V1 possuí grau 2, respeitando o pré­requisito. 
Logo, segundo caso para um grafo bipartido completo ser trilha Euleriana: K1,2 ou K2,1 
 
6. Sob quais circunstâncias um torneio é um grafo Euleriano? 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Aula 15: Árvores 
1. Desenhe todas as florestas possíveis com 4 vértices. 
 
2. Prove que toda árvore não trivial tem ao menos dois vértices de grau 1. 
Sabe­se que o número de vértices de uma árvore é n, e o número de arestas é m = n ­ 1. A soma dos graus 
de todas os vértices é igual a 2m = 2(n­1) = 2n ­ 2. O grau médio então de cada vértice é (2n ­ 2)/n = 2 ­ 2/n 
Como n é numero não­negativo, sabemos então que 2 ­ 2/n < 2. Sabemos que uma árvore é acíclica e 
conexa, logo todo vértice possuí grau de no mínimo 1. Como o grau médio da árvore é menor que 2, sabemos 
que deve existir pelo menos um vértice de grau 1. 
 
3. Prove que, a partir de qualquer árvore não orientada G, é possível criar uma ramificação com raiz 
em qualquer um de seus vértices por atribuir uma orientação às arestas de G. 
Prova por indução: 
Base: Seja R uma árvore não orientada com 2 vertices u,v e uma aresta e1 que ΨG(e1)={u,v}. Agora, 
atribuindo direção para a arvore e sendo que u é raiz, temos que PG(e1)={u,v}, assim u é cauda e v é cabeça. 
Passo: Seja agora R uma árvore não direcionada e não trivial (de somente de um vértice) e maior que 2 
vertices. Temos que admitir direcionamente é necessário decidir quem será a raiz da árvore agora orientada 
em quem serão os nós folhas e intemediários. 
 
4. Prove que, dada uma ramificação é possível criar um caminho com início na sua raiz v e término em 
qualquer outro vértice v'. 
Prova por indução: 
Base: Dado uma arvore R de 2 vértices, v (raiz) e v’, e a aresta e1, então incidem nos vertices v e v’ a aresta 
e1, então ΨG(e1)={v,v’}, e o caminho será P(R)={v, e1, v’}. 
Passo: Suponha R uma árvore e vertices v (raiz) e v’, então se adicionar um vertice u entre os vertices v e v’ 
ainda teremos uma caminho da forma P(R)={v, e1, u, e2, v’} 
existem 2 arestas e1 e e2 que incidem ΨG(e1)={v,u} e ΨG(e2)={u,v’}, assim existe um caminho sempre entre 
os vertices v e v’. 
 
5. A fórmula de Cayley diz que o número de árvores geradoras de um grafo Kn é dado por  .nn−2  
Prove que a fórmula de Cayley é verdadeira. 
Melhor explicação que achei: 
http://legauss.blogspot.com.br/2010/09/uma­prova­topologica­para­o­teorema­de.html 
 
6. Aplique o algoritmo de busca em árvore sobre o grafo K3,3 tendo um vértice qualquer como o 
inicial. 
Explicação da AULA: 
Busca em árvore consiste em um algoritmo para encontrar árvores maximais em um dado grafo de  
entrada. Se o grafo dado for conexo, este algoritmo produz uma árvore geradora. 
O algoritmo é executado da seguinte maneira: 
Algoritmo de busca em árvores: 
Entrada: Um grafo G = (V(G),E(G),ΨG(e)) e um de seus vértices r. 
Saída: Uma árvore R. 
Auxiliares: Vértice u e v, aresta e. 
01: V(R) ←  {v} 
02: E(R) ← ∅ 
03: enquanto ∂G(V(R)) ≠ ∅ faça 
04:  e ←  Rand( ∂G(V(R))) 
05:  V(R) ← V(R){v}, dado  ∪ ΨG(e)={u,v}, u ∈ V(R), v ∉ V(R) 
06:  E(R) ← E(R){e} ∪ 
07: retorne R 
FAZER PARA K 3,3 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Aula 16: Busca em Largura e em Profundidade 
1. Prove que, dado um grafo conexo de entrada, o mapa de níveis do Algoritmo 1 representa não só a 
distância entre um vértice qualquer e a raiz na árvore geradora resultante, mas também no grafo 
original. 
 
Algoritmo 1: Busca em largura. 
Entrada: Grafo G, vértice r. 
Saída: Mapas de predecessores P e de níveis L. 
Auxiliares: Fila Q, vértices u, v, vetor de cores C. 
01: Q   ← ∅ 
02: para todo u ∈ V(G) faça 
03: C(u) ←  branco 
04: C(r) ← preto 
05: P(r) ←  NIL 
06: L(r) ← 0 
07: Insere(Q, r) 
08: enquanto Q ≠ ∅ faça 
09:  u ←  Remove(Q) 
10: para todo v ∈ Γ(u) faça 
11: se C(v) = branco então 
12: C(v) ←   preto 
13: P(v) ← u 
14: L(v) ←  L(u) + 1 
15: Insere(Q, v) 
16: retorne P e L 
 
slide 8 → http://www.ic.unicamp.br/~fkm/disciplinas/mc448/2012s1/slides/aula17.pdf 
 
2. Qual é o nível máximo atingido pelo Algoritmo 2 em um grafo composto pelos vértices e arestas de 
um cíclo de compriemento 5? Justifique.  
4, pois como o primero nível não conta, no inicio do alg ele irá percoorrer os vertices até voltar ao nó raiz, e 
assim irá iniciar a volta. 
 
Algoritmo 2: Busca em profundidade. 
Entrada: Grafo G, vértice r. 
Saída: Mapas de predecessores P e de níveis L. 
Auxiliares: Pilha S, vértices u, v, vetor de cores C. 
01: S   ← ∅ 
02: para todo u ∈ V(G) faça 
03:  C(u) ←  branco  
04: C(r) ←  preto 
05: P(r)  ← ​1 
06: L(r)  ← 0  
07: Insere(S, r) 
08: enquanto S ≠ ∅ faça 
09:  u ←  Remove(S)10: para todo v ∈ Γ(u) faça 
11: se C(v) = branco então 
12: C(v) ←  preto 
13: P(v) ←  u 
14: L(v) ←  L(u) + 1 
15: Insere(S, v) 
16: retorne P e L 
 
http://www.ic.unicamp.br/~fkm/disciplinas/mc448/2012s1/slides/aula18.pdf 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Aula 17: Fluxo em Redes 
1. Verifique se w define uma função de fluxo em G. Em caso afirmativo, defina os vértices fonte e 
sorvedouro e a intensidade do fluxo. 
G=(V(G),E(G),PG(e)); 
V(G)={v1, v2, v3, v4, v5, v6};  
E(G)={e1, e2, e3, e4, e5, e6, e7, e8, e9}; 
PG(e1)=(v1, v2); PG(e2)=(v1, v5); PG(e3)=(v2, v6); PG(e4)=(v3, v1);  
PG(e5)=(v3, v4); PG(e6)=(v3, v5); PG(e7)=(v5, v4); PG(e8)=(v6, v1); PG(e9)=(v6, v3);  
w(e1)=0; w(e2)=3; w(e3)=3; w(e4)=1; w(e5)=1; w(e6)=0; w(e7)=3; w(e8)=1; w(e9)=2; 
 
2. Corrija o raciocínio na sentença a seguir, tendo em vista o grafo G e a função de fluxo w: 
“A soma dos fluxos de saída do vértice v1 é 2, mas algo deve estar errado, pois a soma dos fluxos de 
saída do conjunto de vértices S(G)={v1,v3} é 4, mas também deveria ser 2 pois w é um fluxo.” 
G=(V(G),E(G),PG(e)); 
V(G)={v1, v2, v3, v4};  
E(G)={e1, e2, e3, e4, e5}; 
PG(e1)=(v1, v2); PG(e2)=(v1, v3); PG(e3)=(v2, v3); PG(e4)=(v2, v4); PG(e5)=(v3, v4); 
w(e1)=2; w(e2)=0; w(e3)=2; w(e4)=0; w(e5)=2; 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ 
Aula 18: Lista de Exercícios para Revisão 2 
1. Verifique se um grafo G bipartido e maximal com relação ao número de arestas é par se o número 
de vértices de cada partição for impar. 
 
2. Um grafo impar é aquele no qual todo vértice possui grau impar. Mostre que um grafo  
G=(V(G),E(G),ΨG(e)) é impar se e somente se |∂(V'(G))|=|V'(G)| % 2, para V'(G) V(G) ⊂ e x % y significa 
o resto da divisão de x por y. 
 
3. Dado o grafo abaixo, verifique se os conjuntos {e1, e2}, {e1, e2, e5} e {e2, e3, e5, e6} são cortes. 
Em caso afirmativo, diga se se trata de um enlace. Justifique. 
G=(V(G), E(G), ΨG(e)); 
V(G)={v1, v2, v3, v4, v5, v6, v7, v8}; 
E(G)={e1, e2, e3, e4, e5, e6, e7, e8, e9, e10}; 
ΨG(e1)={v1, v2}; ΨG(e2)={v1, v7}; ΨG(e3)={v2, v8}; ΨG(e4)={v7, v8}; ΨG(e5)={v1, v3}; 
ΨG(e6)={v3, v4}; ΨG(e7)={v3, v5}; ΨG(e8)={v4, v6}; ΨG(e9)={v5, v6}; ΨG(e10)={v6, v8}; 
 
4. Dado um grafo G=(V(G),E(G),ΨG(e)) com n(G) vértices e m(G) arestas, quantos subgrafos 
geradores e quantos subgrafos induzidos possui G? Justifique. 
 
5. Prove que todo ciclo mínimo em um grafo simples é um subgrafo induzido. 
 
6. Verifique se o grafo de Petersen é grafo Euleriano ou uma trilha Euleriana. 
 
  
Grafo de Petersen 
Proposição 25 : Se G é hamiltoniano, então c(G − S) ≤|S| para todo S ⊂ V (G) 
não­vazio. 
Demonstração. Basta notar que c(G − S) ≤ c(C − S) ≤|S| para todo circuito 
hamiltoniano C ⊆ G. 
 
Vejamos um contra­exemplo para a recíproca do resultado acima. O grafo 
de Petersen, mostrado na figura ao lado, não é hamiltoniano. Podemos 
verificar, caso­a­caso, que a remoção de qualquer subconjunto próprio e 
não­vazio de vértices S, o número de componentes do grafo obtido é sempre 
menor ou igual a |S|. 
 
(http://www.ime.usp.br/~jair/ci065/ → proposição 25) 
 
 
7. Dada a árvore R, mostre que Δ(R)=k se R possui pelo me\nos k folhas. 
 
8. Mostre que uma floresta F com n(F) vértices e n(F)­1 arestas é uma árvore. 
 
9. Qual é o nível mínimo atingido pelos algoritmos de Busca em Largura e de Busca em Profundidade 
nos grafos: 
 
1. De Petersen 
 
 
2. K3,5 
 
 
3. K4 
 
 
10. Dado o torneio G abaixo e uma função de peso nas arestas w(e), de modo que o valor máximo de 
w(e) é 5, defina w(e) para as arestas de G de modo que w seja uma função de fluxo máxima nas 
seguintes condições: 
1. Pelo menos dois arestas possuem peso 1. 
2. Pelo menos três arestas possuem peso 1. 
3. Pelo menos quatro arestas possuem peso 1. 
G=(V(G), E(G), PG(e)); 
V(G)={v1, v2, v3, v4}; 
E(G)={e1, e2, e3, e4, e5, e6}; 
PG(e1)=(v1, v2); PG(e2)=(v1, v3); PG(e3)=(v1, v4); PG(e4)=(v2, v3); 
PG(e5)=(v2, v4); PG(e6)=(v3, v4); 
 
   
 
Prova da tarde 
 
1) fluxo. Mostrar que o grafo tem um fluxo, falar quais vertices são as fontes ou sorvedouros, calcular 
a intensidade do fluxo. 
cade a orientação??? 
*O peso de v6­>v3 é 2 
2) dado que v(g) é par, todo  (V'(G)) C V(G) é parδ  
Prova por indução (by Aruã): 
Base: Tenha um grafo G que só vai ter um vértice e nenhuma aresta. O corte deste vértice é 0. 
Hipótese: Tenha um grafo G par com K vértices. O corte de um conjunto de vértices V’, para V’ contido em 
V(G) é par. 
Passo: dado um grafo com K + 1 vértices. O corte trivial de qualquer um dos vértices v E V(G) é par, e ele vai 
gerar um grafo G’, com V(G’) = V(G) ­ v, voltando na hipótese. Logo, fica provado por indução. 
 
3) Dada uma trilha fechada minimal mostrar que contem os mesmos vertices e arestas de um ciclo 
“O conceito de minimalidade é semelhante. Podemos dizer que nem todo cíclo de um grafo é mínimo, mas 
todo ciclo é minimal, pois não há como estender um cíclo incluindo outros vértices ou arestas.” (Slide 8) 
 
 
4) Sob quais condiçoes um torneio não é um ciclo hamiltoniano 
Por Rédei, todo torneio possuí um caminho hamiltoniano (i.e não fechado). 
Sabe­se que um ciclo hamiltoniano não pode repetir vértices. Considere­se que em um ciclo hamiltoniano 
direcionado, o grau de entrada de cada vértice deve ser no minimo  1, e o grau de saída idem, para haver a 
possibilidade de um caminho fechado completo. Um torneio é definido como um digrafo onde cada par de 
vértices possuí entre eles apenas uma aresta. Logo, uma condição é que para um torneio ser ciclo 
hamiltoniano, ele precisa ter em cada vértice grau de entrada e saída igual a 1. 
 
5) Dada uma ramificação de G, mostrar que a partir da raiz r é possivel chegar em qualquer v