Grafos-P1 - Exercícios

Prévia do material em texto

Respes ­ Respondam por favor!   
      mmm ­ Não sei se tá certo, alguém confirma!   
 
Graph Theory ­ Bondy & Murdy 
E­BOOK: https://www.sugarsync.com/pf/D7620516_3198631_66631 
Exercícios Aula 01: 
Pessoal, ta facil de entender, quem quiser: 
http://www.munif.com.br/munif/arquivos/A1­Definicoes%20basica%20Grafoss.pdf?id=43 
 
 
ALGUEM JA TEM A PROVA DA TARDE????? 
1-Ciclo grau >=2 prova q tem ciclo 
 
2-matriz provar q a soma da linha da matriz de incidencia eh o grau do vertice 
alguem sabe fazer ? 
 
3-grafo com 12 vertices com pelo menos um vertice de grau 5, 4 3 conexo fale o menor 
numero de E(G) 
alguem sabe fazer o 3? 
11(desenhe) 
4-kn,n n-regular mostre um subgrafo G criado a partir da deleçao de um vertice nao eh mais 
n-regular 
 
5-grafo simples de 6 vertices provar q naum tem automorfismo sem ser o trivial 
 
 
1) Qual é a quantidade máxima de vértices n(G) que um grafo completo não direcionado G 
pode ter de modo que G seja um grafo planar? 
 
Temos que trivialmente o K_1, K_2 e K_3 são planares. O K_4 pode ser representado como a 
imagem abaixo: 
 
O vertice 4 pode ser incluido dentro ou fora da região definida pelas arestas do K_3 (um triangulo 
com duas regiões, dentro e fora), sem acabar com a planaridade. 
Ao adicionar o 5º vértice temos que ele ira pertencer a uma das 4 regiões definidas pelo K_4. 
Sem perda de generalidade, se adicionarmos o vértice na região R_1, as arestas que incidem 
em V_5, com excessão de uma, irão incidir nos outros vértices sem quebrar a planaridade. Mas, 
para este exemplo, o vértice 2 não poderá ser atingido sem que a planaridade seja destruída. E 
isso é válido para todas as outras possibilidades de regiões para se colocar o 5º vértice. Sempre 
haverá um vertice que não poderá ser atingido sem destruir a planaridade. Logo o maior número 
de vértices de um grafo completo planar é 4. isso ta certo mesmo? 
 
Beijos para a minha mãe =D 
 
2) O grafo das palavras é definido sendo cada palavra um vértice e duas palavras são 
adjacentes se diferirem exatamente em uma letra. Por exemplo, rato e ralo são adjacentes 
segundo a definição dada. Faça uma figura contendo um grafo das seguintes palavras: 
caiado, cavado, cavalo, girafa, girava, ralo, ramo, rata, rato, remo, reta, rota, vaiado, 
varado, virada, virado, virava. (Ficaram 2 grafos, alguém v um jeito de juntar?) 
 
ralo ­ ramo ­ remo 
   |     / 
  rato ­  rata ­ reta 
                |      / 
              rota  
 
    girafa ­    girava 
             |       \ 
   vaiado ­  virada ­ virava 
     |        X       | 
   varado ­ virado 
      | 
cavado ­ caido 
   | 
cavalo 
  
3) Um cubo de dimensão k, ou um k­cubo é o grafo no qual os vértices são todas as 
sequências b1, b2, ..., bk em que cada bi pertence a {0, 1}. Dois vértices são adjacentes se 
diferirem em exatamente uma posição. Desenhe cubos de dimensões 1, 2 e 3. 
 
Q1 →  V(Q1) = {0,1} 
  E(Q1) = {e1} 
  Ψq1(e1) = {0,1} 
 
Q2 →  V(Q2) = {00,01,10,11} 
  E(Q2) = {e1,e2,e3,e4} 
      Ψq2(e1) = {00,01}; 
Ψq2(e2) = {00,10}; Ψq2(e3) = 
{11,10}; Ψq2(e4) = {11,01}; 
 
 
Q3 → V(Q3) = {000,001,010,100,110,101,011,111} 
E(Q23 = {e1,e2,e3,e4,e5,e6,e7,e8,e9,e10,e11,e12} 
Ψq3(e1) = {000,001}; Ψq3(e2) = {000,010}; Ψq3(e3) = {000,100}; Ψq3(e4) = {001,101}; 
Ψq3(e5) = {001,011}; Ψq3(e6) = {010,110};Ψq3(e7) = {010,011}; Ψq3(e8) = {100,110}; Ψq3(e9) = 
{100,101}; Ψq3(e10) = {110,111}; Ψq3(e11) = {101,111}; Ψq3(e12) = {011,111}; 
 
Para entregar Aula 01: 
 
Seja um grafo não orientado Xn (n ≥ 1) em que o conjunto de vértices V(Xn) é definido por                                     
todos os subconjuntos não vazios do conjunto de números pares {2, 4, …, 2n} e sejam                               
dois vértices adjacentes somente se os seus conjuntos de números diferem em                       
exatamente 2 elementos. 
A questão é que deve ser determinado o número de diferenças entre os conjuntos de                             
vértices dos grafos. 
Uma diferença entre dois conjuntos de vértices pode ser sanada por 1) remover, 2)                           
incluir ou 3) trocar um elemento em um dos conjuntos. 
 
Veja alguns exemplos: 
{2, 4} e {6, 8} diferem em 2 elementos. Troca de 2 por 6 e de 4 por 8. 
{2} e {4} diferem em um elemento. Troca de 2 por 4. 
{2, 4} e {2} diferem em um elemento. Remove 4. 
{2} e {2, 4, 6} diferem em 2 elementos. Acrescenta 4 e 6. 
{2,4,6} e {2,6,8} diferem em apenas um elemento. Neste caso basta trocar o 4 pelo 8 no                                 
primeiro conjunto e o os conjuntos se tornam iguais. 
 
 
Para cada um dos grafos X1, X2, X3 e X4: 
 
a) Descreva­os em função de V(G), E(G) e ΨG(e). 
  V(X)  E(X)  Ψx(e) 
X1  {2}  vazio  vazio 
X2  { {2}, {4}, {2,4} }  vazio  vazio 
X3  { {2}, {4}, {6}, {2,4}, 
{2,6}, {4,6}, {2,4,6} } 
e1, e2, e3, e4, e5, e6  Ψx3(e1) = { {2}, {2,4,6}
} 
Ψx3(e2) = { {4}, {2,4,6}
} 
Ψx3(e3) = { {6}, {2,4,6}
} 
Ψx3(e4)= { {2}, {4,6}} 
Ψx3(e5)= { {4}, {2,6}} 
Ψx3(e6)= { {6}, {2,4}} 
 
 
b) Faça um desenho dele. 
 
c) Diga se é um grafo planar. 
 
X1 ­ planar 
X2 ­ planar 
X3 ­ planar 
 
d) Caso mudássemos o enunciado, para que dois vértices sejam adjacentes caso seus                         
conjuntos numéricos sejam diferentes em exatamente 1 elemento, diga se o grafo seria                         
ou não planar. Justifique. 
 
X1 ­ continua planar pois ainda não existirá nenhuma aresta 
X2 ­ planar 
X3­  planar 
 
e) Caso mudássemos o enunciado, para que dois vértices sejam adjacentes caso seus                         
conjuntos numéricos sejam diferentes em até 2 elementos, diga se o grafo seria ou não                             
planar. Justifique. 
 
X1 ­ existirá uma aresta ligando o vértice 2 a ele mesmo. Seu conjunto numérico será diferente                                 
em 0 elementos. No entanto o grafo se manterá planar. 
 
X2 ­ planar. 
 
X3 ­ não planar. O grafo se tornaria completo. Não é possível uma construção do grafo sem que 
pelo menos 2 arestas se cruzem. 
 
Exercícios Aula 02: 
 
Exemplo 4: Dado o grafo G abaixo, defina um automorfismo não trivial de G. 
G=(V(G), E(G), ΨG(e)); 
V(G)={v1, v2, v3, v4}; 
E(G)={e1, e2, e3}; 
ΨG(e1)={v1, v2}; ΨG(e2)={v1, v3}; ΨG(e3)={v1, v4}; 
O grafo G é simples, assim, basta encontrar uma permutação αG(v) de seus vértices que 
preserve as adjacências. O desenho abaixo representa G. 
 
 
Podemos permutar v2 e v3, preservando as adjacências. Deste modo o nosso automorfismo será 
definido por: 
ΘGG(v1)=v1, ΘGG(v2)=v3, ΘGG(v3)=v2, ΘGG(v4)=v4 e ΦGG(e1)=e1, ΦGG(e2)=e2, ΦGG(e3)=e3. 
O grafo resultante será: 
 
Como exercício, prove que as adjacências são mantidas. 
 
1) Verifique se os pares de grafos abaixo são isomorfos: 
(a)   
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}; 
H=(V(H), E(H), ΨH(e)); 
V(H)={v1, v2, v3, v4, v5, v6, v7, v8}; 
E(H)={e1, e2, e3, e4, e5, e6, e7, e8, e9, e10}; 
ΨH(e1)={v1, v2}; ΨH(e2)={v1, v7}; 
ΨH(e3)={v2, v8}; ΨH(e4)={v7, v8}; 
ΨH(e5)={v1, v3}; ΨH(e6)={v3, v4}; 
ΨH(e7)={v3, v5}; ΨH(e8)={v4, v6}; 
ΨH(e9)={v5, v6}; ΨH(e10)={v4, v2}; 
 
 
Definição: Dois grafos G e H são isomorfos, isto é, G ≅ H se houver bijeções                               
ϴGH(v):V(G)→V(H) e ΦGH(e):E(G)→E(H) tais que ΨG(e)={u,v}, ∀ e ∈ E(G), ∀ u,v ∈ V(G) se e                               
somente se ΨH(ΦGH(e))={ϴGH(u),ϴGH(v)}. O par de funções (ϴGH(v), ΦGH(e)) é um                     
isomorfismo entre G e H. 
 
desenhando o grafo G  Desenhando H e renomeando os vértices e 
arestas (?­ Como assim renomeando? o grafo 
já foi passado. Não entendi,alguém 
explica?­Camila) 
   
 
 
Considerando o grau dos vértices, tenta­se encontrar o isomorfismo para: 
ϴGH(v1) = u1,  ϴGH(v1) = u2,  ϴGH(v1) = u3,  ϴGH(v1) = u4(?­ Não entendi nada daqui pra baixo, 
alguém explica?­Camila) 
 
Para ϴGH(v1) = u1: 
● ϴGH(v3) = u3, ϴGH(v5) = u5, impossível encontrar ϴGH(v4), pois não existe aresta que 
ligue u3 a outro vértice de grau 2. 
ou 
 
● ϴGH(v3) = u2, ϴGH(v5) = u8,impossível encontrar ϴGH(v4), pois não existe aresta que 
ligue u2 a outro vértice de grau 2. 
 
Para ϴGH(v1) = u2 
● ϴGH(v8) = u2, ϴGH(v5) = u8 
 
Para ϴGH(v1) = u3 
 
 
Para ϴGH(v1) = u4 
 
 
Dedução: 
****outra maneira mais fácil de provar o não isomorfismo! 
G possui 2 arestas cujos vertices de suas duas pontas possuem grau 3: e5 e e10 
ΨG(e5)={v1, v3}; dG(v1)= 3 dG(v3)= 3 
ΨG(e10)={v6, v8}; dG(v6)=3 dG(v8)= 3 
 
H possui 3 arestas cujos vertices de suas duas pontas possuem grau 3: a5, a10, e a1 
ΨH(e1)={v1, v2};  dG(v1)= 3 dG(v2)= 3 
ΨH(e5)={v1, v3};  dG(v3)= 3 
ΨH(e10)={v4, v2};    dG(v4)= 3 
 
Portanto é impossível achar uma relação Φ 
 
 (b) 
 
 
 
 
2) Quantos possíveis automorfismos possui o grafo K4? Justifique. 
24 automorfismos, sendo eles a permutação entre os vértices: 
{ {1,2,3,4},{1,2,4,3},{1,3,2,4},{1,3,4,2},{1,4,2,3},{1,4,3,2}, 
{2,1,3,4},{2,1,4,3},{2,3,1,4},{2,3,4,1},{2,4,1,3},{2,4,3,1}, 
{3,1,2,4},{3,1,4,2},{3,2,1,4},{3,2,4,1},{3,4,1,2},{3,4,2,1}, 
{4,1,2,3},{4,1,3,2},{4,2,1,3},{4,2,3,1},{4,3,1,2},{4,3,2,1} } 
 
3) Prove que, para que dois grafos G e H sejam isomorfos, a bijeção ϴGH(v) precisa 
mapear vértices de mesmo grau. 
Suponha que seja mapeado um grafo de grau diferente, existirá uma aresta que não consiguirá 
ser mapeada.. depois temos q pensar em um jeito de formular essa ideia.. vc quer tentar? temos 
que usar ϴGH(v) e ΦGH(e) e a definição ΨH(ΦGH(e))={ϴGH(u),ϴGH(v)} 
 
­> E se usar redução ao absurdo? Por exemplo: 
 
Sejam G e H isomorfos (dado), seja E u pertencente a G e v pertencente a H vértices, como são 
isomorfos temos ϴGH(v) = u e a volta também é verdade.  
Supondo que u possui um uma aresta e E E(H), tal que seja incidente (aresta a mais). Se d(v) 
difere de d(u), isso é um absurdo pois não é possível mapear vértices de mesmo?? grau. 
 
Para entregar Aula 02: 
 
Dado o grafo G abaixo resolva: 
G=(V(G), E(G), ΨG(e)); 
V(G)={v1, v2, v3, v4, v5, v6, v7, v8, v9, v10}; 
E(G)={e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11, e12, e13, e14, e15}; 
Ψ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}; ΨG(e11)={v1, v9}; ΨG(e12)={v2, v9}; 
ΨG(e13)={v7, v9};  ΨG(e14)={v8, v9};  ΨG(e15)={v9, v10}; 
 
a) Desenhe o grafo G. 
 
b) Calcule o grau de cada vértice e os graus mínimo e máximo de G. 
dg(v1)=4  dg(v2)=3  dg(v3)=3  dg(v4)=2  dg(v5)=2 
dg(v6)=3  dg(v7)=3  dg(v8)=4  dg(v9)=5  dg(v10)=1 
 
 
(g)=min(dg(v10))=1 
(g)=min(dg(v9))=5 
 
c) Defina e desenhe um automorfismo de G. Justifique conforme feito para o Exemplo 3, 
mas não é necessário provar a volta, isto é, não é preciso provar que se ΨH(e) = {u, v}, 
então  ΨH(ΦHG(e))={ϴHG(u),ϴHG(v)}. Basta provar que se ΨG(e)={u, v}, então 
ΨG(ΦGH(e))={ϴGH(u),ϴGH(v)}. 
 
H=(V(H), E(H), ΨH(e)); 
V(H)={v1, v2, v3, v4, v5, v6, v7, v8, v9, v10}; 
E(H)={e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11, e12, e13, e14, e15}; 
ΨH(e1)={v1, v2};  ΨH(e2)={v1, v7};  ΨH(e3)={v2, v8};  ΨH(e4)={v7, v8};   
ΨH(e5)={v1, v6}; ΨH(e6)={v6, v4};  ΨH(e7)={v6, v5};  ΨH(e8)={v4, v3}; 
ΨH(e9)={v5, v3};  ΨH(e10)={v3, v8}; ΨH(e11)={v1, v9}; ΨH(e12)={v2, v9}; 
ΨH(e13)={v7, v9};  ΨH(e14)={v8, v9};  ΨH(e15)={v9, v10}; 
 
 
ϴGH(v1) = v1  ϴGH(v6) = v3 
ϴGH(v2) = v2  ϴGH(v7) = v7 
ϴGH(v3) = v6  ϴGH(v8) = v8 
ϴGH(v4) = v4  ϴGH(v9) = v9 
ϴGH(v5) = v5  ϴGH(v10) = v10 
 
ΦGH(e1) = e1  ΦGH(e6) = e6  ΦGH(e11) = e11 
ΦGH(e2) = e2  ΦGH(e7) = e7  ΦGH(e12) = e12 
ΦGH(e3) = e3  ΦGH(e8) = e8  ΦGH(e13) = e13 
ΦGH(e4) = e4  ΦGH(e9) = e9  ΦGH(e14) = e14 
ΦGH(e5) = e5  ΦGH(e10) = e10  ΦGH(e15) = e15 
 
ΨG(ΦGH(e1))={ϴGH(v1),ϴGH(v2)} 
ΨG(e1)={v1,v2} 
 
ΨG(ΦGH(e5))={ϴGH(v1),ϴGH(v3)} 
ΨG(e5)={v1,v6} 
 
ΨG(ΦGH(e6))={ϴGH(v3),ϴGH(v4)} 
ΨG(e5)={v6,v4} 
 
ΨG(ΦGH(e7))={ϴGH(v3),ϴGH(v5)} 
ΨG(e5)={v6,v5} 
ΨG(ΦGH(e8))={ϴGH(v4),ϴGH(v5)} 
ΨG(e5)={v6,v5} 
 
ΨG(ΦGH(e9))={ϴGH(v5),ϴGH(v6)} 
ΨG(e5)={v5,v3} 
 
ΨG(ΦGH(e10))={ϴGH(v6),ϴGH(v8)} 
ΨG(e5)={v3,v8} 
 
 
d) Quantos possíveis automorfismos existem em G? Justifique. Não é preciso provar 
cada automorfismo. 
Acredito que seja 2. (ERRADO)[Vi gente falando que encontrou 8]  
 
Exercícios Aula 03: Bipartidos e K­regulares. 
 
1) Verifique se o grafo de Petersen é bipartido. 
 
2) Prove que um grafo bipartido completo Kn',n'' é um grafo k­regular. 
Isto não faz sentido, um grafo bipartido completo só vai ser k­regular se n’ = n”, mas 
como o exercício não fala nada sobre isso... eu não entendi. ­ Fernanda 
 
3) Dado um subconjunto V'(Kn) não vazio dos vértices de um grafo completo Kn, qual é a 
vizinhança de V'(Kn)? Justifique. 
 
4) Verifique a validade da afirmação: “Todo grafo bipartido é k­regular.” 
Grafo bipartido completo Kn'n" com n' != n" é um exemplo de grafo bipartido que não é 
k­regulares. 
Prova que grafo bipartido completo Kn'n" com n' != n" não é k­regular: 
 
De acordo com a definição de grafo bipartido completo Kn'n": 
 ­ n' é o número de vertices pertencentes a V'(Kn'n") e n" o número de vertices 
pertencentes a V"(Kn'n"). 
 ­ todo o vertice u pertencente a V'(Kn'n") é adjacente a todos os vertices v pertencente a 
V"(Kn'n"). 
 
Sendo assim, todo vertice vertice u pertencente a V'(Kn'n") possui grau n" e todo vertice 
v pertencente a V"(Kn'n") possui grau n'. Como n' != n" então o vertice u tem grau 
diferente do vertice v. Portanto não é k­regular. 
­Fernanda. ACHO que é isso... 
 
5) Verifique a validade da afirmação: “Todo completo é k­regular.” 
 
6) O grafo x­cubo (ou n­cubo), referido por Qx, é definido pelo grafo cujo número de 
vértices n(Qx) = 2x, tal que cada vértice é um elemento da sequência de símbolos (∊1, ∊2, 
... ∊x), onde i ∈ {1, 2, ..., x}, ∊i = 0 ou 1. As arestas são definidas entre os vértices que 
diferem em exatamente uma coordenada ∊i. 
1. Descreva por conjuntos e desenhe os grafos Q2, Q3 e Q4.  
2. Verifique se não planares, bipartidos e/ou k­regulares. 
3. Defina a vizinhança do conjunto formado por todos os vértices tal que ∊1=0. 
 
Para entregar Aula 03: Bipartidos e K­regulares. 
 
Prove que todo o grafo x­cubo Qx é k­regular. (Veja a definição de grafo x­cubo no 
Exercício 6.) Defina o valor de k em função de x. Justifique as respostas. 
 
Exercícios Aula 04: Representações de Grafos e Subgrafos 
 
1. Escreva as matrizes de adjacências e de incidências dos grafos abaixo: 
(a) G=(V(G),E(G),ΨG(e)); 
V(G)={v1, v2}; 
E(G)={e1, e2, e3, e4, e5}; 
ΨG(e1)={v1, v1}; ΨG(e2)={v1, v1}; ΨG(e3)={v1, v2}; ΨG(e4)={v1, v2}; ΨG(e5)={v2, v2}; 
 
Matriz de Incidencia  Matriz de Adjacencia 
 
  e1  e2  e3  e4  e5 
v1  2  2  1  1  0 
v2  0  0  1  1  2 
 
 
  v1  v2 
v1  4  2 
v2  2  2 
 
 
 
(b) G=(V(G),E(G),ΨG(e)); 
V(G)={v1, v2, v3, v4}; 
E(G)={e1, e2, e3, e4, e5, e6, e7, e8, e9, e10}; 
ΨG(e1)={v1, v2}; ΨG(e2)={v1, v3}; ΨG(e3)={v1, v4}; ΨG(e4)={v1, v4}; ΨG(e5)={v2, v2}; 
ΨG(e6)={v2, v2}; ΨG(e7)={v2, v4}; ΨG(e8)={v3, v4}; ΨG(e9)={v4, v4}; ΨG(e10)={v4, v4}; 
Matriz de Incidencia  Matriz de Adjacencia 
 
  e
1 
e
2 
e
3 
e
4 
e
5 
e
6 
e
7 
e
8 
e
9 
e10 
v1                     
v2                     
v3                     
v4                     
 
 
  v1  v2  v3  v4 
v1         
v2         
v3         
v4         
 
 
 
2. Descreva na forma de matriz de adjacências e na forma de matriz de incidências os 
grafos resultantesda remoção da aresta e4 do vértice v1 dos grafos do Exercício 1. 
Matriz de Incidencia  Matriz de Adjacencia 
 
  e
1 
e
2 
e
3 
e
5 
e
6 
e
7 
e
8 
e
9 
e10 
v1                   
v2                   
v3                   
v4                   
 
 
  v1  v2  v3  v4 
v1         
v2         
v3         
v4         
 
 
3. Dado o grafo orientado abaixo, escreva sua matriz de adjacências. 
G=(V(G),E(G),PG(e)); 
V(G)={v1, v2, v3, v4}; 
E(G)={e1, e2, e3, e4, e5, e6, e7, e8}; 
PG(e1)=(v1, v3); PG(e2)=(v1, v3); PG(e3)=(v2, v1); PG(e4)=(v3, v1); 
PG(e5)=(v2, v4); PG(e6)=(v3, v3); PG(e7)=(v3, v4); PG(e8)=(v4, v3); 
Matriz de Incidencia  Matriz de Adjacencia 
 
  e
1 
e
2 
e
3 
e
4 
e
5 
e
6 
e
7 
e
8 
v1                 
v2                 
v3                 
v4                 
 
 
  v1  v2  v3  v4 
v1         
v2         
v3         
v4         
 
 
 
4. Prove que um subgrafo H de um grafo G é isomorfo a G se e somente se H=G. 
 
Para qualquer subgrafo H do grafo G, se então E(H) < E(G) ou V(H) < V(G), logo é                =G / H                      
impossível a bijeção mapear a bijeção ϴHG(v):V(H)→V(G). 
Portanto para exibir o isomorfismo entre G e H,obrigatoriamente G=H. 
 
Definção: 
Para provar que um grafo H é isomórfico a um grafo G, basta encontrar uma bijeção 
ϴGH(v):V(G)→V(H) 
para a qual seja possível mapear todas as arestas por uma bijeção ΦGH(e):E(G)→E(H) e que                             
mantenha a relação das funções ΨG(e) e ΨH(e) conforme descrito na definição. Este processo                           
pode ser feito exaustivamente verificando todas as bijeções possíveis dos vértices de G e H.  
Logo, assim que encontrarmos todas as bijeções de H em G, teremos que H=G. 
(Curiosidade →  Este procedimento tem complexidade n(G)!) 
 
Para entregar Aula 04: Representações de Grafos e Subgrafos 
 
Prove que para um grafo não­direcionado a matriz de adjacências é simétrica. 
 
Exercícios Aula 05: Caminhos e Ciclos  
 
1. Prove que um grafo é bipartido se e somente se ele não possui ciclos de grau impar. 
 
2. Qual é o comprimento do maior caminho que pode ser definido a partir do grafo K3,6? 
Justifique. 
 
3. Escreva a definição de caminho para grafos orientados. 
 
Exercícios Aula 06:  Grafos Conexos, Grafos Acíclicos e Grafos Direcionados 
 
1. A definição de grafos conexos e a afirmação provada no Exercício 3 são análogas. 
Portanto, prove que existe um caminho entre quaisquer pares de vértices de um grafo se 
e somente se existe pelo menos uma aresta entre quaisquer bipartições dos vértices 
deste grafo. 
 
2. Prove que o Corolário 1 desta aula está correto. 
Corolário 1: Um grafo simples e acíclico de pelo menos três vértices tem ao menos um vértice 
de grau menor que dois. 
 
 
 
3. Mostre que um grafo composto pelos vértices e arestas de um ciclo é bipartido se e 
somente se o número de vértices do ciclo for par. 
 
4. Prove que não há outros torneios de quatro vértices que não sejam isomorfos a um 
dos quatro grafos apresentados no Exemplo 2. 
 
5. Quantos torneios não isomórficos de cinco vértices existem? Justifique. 
 
6. De um exemplo de um grafo orientado k­regular que não é um grafo direcionado 
k­regular. 
 
 
Aula 07 ­ Lista de Exercícios para Revisão 
 
1. Mostre que a somatória dos graus de saída de um grafo direcionado G é igual m(G). 
 
Prova por indução: 
 
Hipótese: 
Mostre que a somatória dos graus de saída de um grafo direcionado G é igual m(G). 
Base: 
­assumindo para m(G)=0, teremos que  existe um grafo G qualquer em que não existe 
conexão entre os vértices. 
­(mais interessante) assumindo para m(G)=1, teremos que o grafo direcionado G tem uma 
aresta que incide em um vértice u e um vértice v, podendo assumir que u=v e que u,v ∈ V(G), logo 
o grua de saída de u é d(G out)[u]=1. 
 
Passo: Assim que 1 aresta é adicionado em E(G), temos que o grau de saída de um vértice é 
incrementado em 1. 
 
 
2. Mostre que os grafos abaixo não são isomórficos.
 
 
3. Qual é o maior número possível de vértices em um grafo com 19 arestas, sendo todos 
os vértices de grau maior ou igual a três? Justifique. 
 
 
4. Um grafo assimétrico é aquele que não possui nenhum automorfismo, com exceção do 
automorfismo trivial. Mostre que grafo G=(V(G), E(G), ΨG(e)), tal que V(G)={v1, v2, …, 
vn(G)} e dG(v1)=n(G)­1 não é assimétrico se o seu subgrafo G' dado pela remoção do 
vértice v1 também não for assimétrico. 
 
 
5. Repita a prova do exercício anterior, mas agora considerando que dG(v1)=0. 
 
 
6. Dado um grafo conexo qualquer, quantas arestas adicionais são necessárias para que 
este grafo continue conexo ao incluir mais cinco vértices a ele? Justifique. 
 
O mínimo de arestas para adicionar no grafo G qualquer para que esse mantenha­se conexo são 
5 arestas. 
 
7. Um grafo é auto­complementar se for isométrico ao seu complemento. De um exemplo 
de um grafo auto­complementar com três ou mais vértices. Justifique. 
 
 
 
8. Prove que o grafo formado pelos vértices e arestas de um ciclo qualquer é bipartido se 
o ciclo for par. 
 
 
 
9. Dada uma bipartição V'(G) e V''(G) de um grafo G, mostre que a soma dos graus dos 
vértices contidos em cada bipartição é a mesma. 
 
Extras 
 
Aula 05 ­ Caminos e Ciclos 
Se um grafo G for simples, então a sequência dos vértices PV(G)(i) define 
automaticamente a sequência de arestas PE(G)(j) do caminho P. Como exercício, prove 
esta afirmação.  
 
Prova por indução: 
Base: 
Seja um grafo G qualquer em que G=(V(G), E(E), ΨG(e)): 
V(G)={v1, v2} 
E(G)={e1} 
ΨG(e1)={v1, v2}, então: 
 
P[V(G)](i) = {v1,v2} e P[E(G)](i) = {e1} e o caminho completo P=(v1,e1,v2),  obrigatóriamente nesta 
sequencia. 
 
Passo: Seja k ∈ N, V(G)={v1,v2,v3,...,vk, v(k+1)} e E(G)={e1,e2,e3,...,e(k­1)}, temos que : 
­ ΨG(ek)={vk, v(k+1)} 
­ P[V(G)](i) = {v1,v2,v3,...,vk, v(k+1)} 
­ P[E(G)](i) = {e1,e2,e3,...,e(k­1), ek} 
e o caminho completo será P=(v1,e1,v2,e2,v3,e3,..., v(k­1), e(k­1), vk, ek, v(k+1)) 
 
Resumo das aulas, Teoria: ­­Camila 
     
O que está grifado era pra fazer como exercício, não sei se está certo 
     
Aula 1 
 
Teoria de grafos: disciplina q estuda objetos combinatórios denominados grafos. 
 
Exemplos de prob.s resolvidos c/ grafos: 
 
 
1.Dado um conjunto de pessoas d uma rede social, determinar se 
2  pessoas estão relacionadas por amigos em comum. 
 
 
 
 
 
 
2.Dado 1 conj. d cidades e rodovias q as ligam, determinar o 
menor caminho p/ percorrer 1 determinado o número d cidades. 
 
 
3.Dada 1 imagem colorida, separar os pixels em grupos d cores 
semelhantes. 
 
Grafos: modelo p/ resolver prob.s d muitas áreas da ciência. 
Ñ direcionado: 1 grafo G é definido c/o 1 tripla ordenada (V(G), E(G), 
ΨG(e)), onde V(G) é 1 conj. d vértices do grafo G, E(G) é 1 conj. d arestas d 
G e ΨG(e) é 1 função d incidência q associa 1 aresta e ∈ E(G) a 1 
multiconjunto d vértices {u, v} ⊂ V(G) de cardinali// 2. 
Pontas das arestas: Seja V(G)={u, v, w}, E(G)={e, f} e ΨG(e)={u,v}, 
ΨG(f)={u,w}, u e v são pontas da aresta e e u e w são pontas da aresta f. 
 
Direcionado: 1 grafo G é definido por 1 tripla ordenada (V(G), E(G), ΡG(e)), 
onde V(G) e E(G), 
possuem o msm significado q no grafo não orientado e ΡG(e) é 1 função d 
incidência q associa uma aresta e ∈ E(G) a um par ordenado d vértices (u, v) ≔ 
{{u}, {u, v}}², sendo {u, v} ⊂ V(G). 
Cauda/Cabeça: Seja V(G)={u, v, w}, E(G)={e, f} e PG(e)=(u,v), PG(f)=(u,w), u é a 
cauda das arestas e e f, e v e w são as cabeças das arestas e e f, v e w são sucessores diretos 
de u, e u é predecessor direto de v e w. 
 
número d vértices de G: n(G) = |V(G)|. 
número d arestas de G: m(G) = |E(G)|. 
 
Aresta Incidente: (entre aresta e vertice) 
Em grafo ñ direcionado:se v é 1 das ptas da aresta e é incidente em v. 
Em grafo direcionado: se v é a cauda ou a cabeça da aresta e é incidente em v. 
 
Vertices Adjacentes: (entre vertice e vertice) 
Em grafo ñ direcionado: se os dois vértices são pontas de uma mesma aresta. 
Em grafo direcionado: Dois vértices u, v ∈ V(G), são adjacentes em no grafo direcionado G, se ∃ 
e ∈ E(G) | PG(e) = (u, v), ou seja, se u é cauda de e e v é cabeça de e. 
 
Arestas Adjacentes: (entre aresta e aresta) 
Em grafo ñ direcionado: se duas arestas possuírem ao menos um vértice em comum. 
Em grafo direcionado: Duas arestas e, f ∈ E(G) são ditas adjacentes em um grafo direcionado G, 
se ∃ v ∈ V(G) | PG(e) = (u, v), PG(f) = (v, w), ∀ u, w, v ∈ V(G), ou seja, se duas arestas possuírem 
ao menos um vértice em comum. 
 
Laço: 
Em grafo ñ direcionado: se o grafo possui uma aresta que incide duas vezes no 
mesmo vértice. 
Em grafo direcionado: Existe um laço em um grafo direcionado G, quando dada 
uma aresta e ∈ E(G), PG(e) = (u, u), para qualquer u ∈ V(G), ou seja, se o grafo possui uma aresta 
que incide cabeça e cauda no mesmo vértice. 
Aresta Invertida: Só em grafos direcionados. Dada uma aresta e ∈ E(G), em um grafo direcionado 
G, a aresta f é denominada aresta invertida de e se PG(e)=(u, v) e PG(f)=(v, u), para ∀ u, v ∈ V(G). 
 
 
Planar: quando existe uma representação gráfica na 
qual suas arestas se interceptam apenas sobre os 
vértices, ou seja, sobre suas pontas, cabeças ou 
caudas. 
 
 
 
Simples: se não tiver laços e não tiver mais de uma aresta entre dois 
vértices. 
Escrita na Forma de conjunto: um grafo G não orientado (V(G), E(G), 
ΨG(e)) onde não ∃ e ∈ E(G) | ΨG(e)={u,u}, ∀ u ∈ V(G) e não existem duas 
arestas e, f de modo que ∃ e ∈ E(G) | ΨG(e)={u,v}, ∀ u,v ∈ V(G), não pode 
∃ f ∈ E(G) | ΨG(f)={v,u}, ∀ u,v ∈ V(G). 
 
 
Completo: (Kn) G é um grafo não direcionado e simples em que ∀ u, w ∈ V(G) | u 
≠ v, ∃ e ∈ E(G) | ΨG(e) = {u, v}, ou seja, existe uma e somente uma aresta ligando 
cada par de vértices distintos do grafo G. O grafo completo com n(G) vértices é 
expresso por Kn. m(Kn) = (n(n­1))\2. 
 
 
Vazio: se E(G) = ∅ . 
 
 
 
Complemento ­ só de grafo simples G: o complemento 
possui o mesmo conjunto de vértices de G e contém as 
arestas que complementam G para transformá­lo em um 
grafo completo. 
 
Finito: se ambos seus conjuntos de vértices V(G) e de arestas E(G) são finitos. 
 
Aula 2 
     
Grau : (dG(v)) de um vértice v é dado pelo número de arestas de G incidentes a v. Como o 
conceito de incidência se aplica tanto para a cabeça como para a cauda das arestas de grafos 
direcionados, o conceito para grafos direcionados continua o mesmo. No entanto, é possível  
definir também os conceitos de grau de entrada dinG(v) e de grau de saída doutG(v) de um vértice 
v de um grafo direcionado G pelo número de cabeças e caudas que incidem em v, 
respectivamente. Um laço incide duas vezes sobre o mesmo vértice, somando duas unidades ao 
seu grau. 
Grau min.: δ(G) = min(dG(v)), ∀ v ∈ V(G) 
Grau max.: Δ(G) = max(dG(v)), ∀ v ∈ V(G) 
 
Isomorfismo: 
 
Grafos Idênticos: 
Não direcionados: Dois grafos G e H são idênticos, quando G=H, se V(G)=V(H), E(G)=E(H), e 
ΨG(e)=ΨH(e), ∀ e ∈ E(G). Deste modo, os grafos G e H podem ser desenhados da mesma 
maneira. 
Direcionados: Dois grafos G e H são idênticos, quando G=H, se V(G)=V(H), E(G)=E(H), e 
PG(e)=PH(e), ∀ e ∈ E(G). Deste modo, os grafos G e H podem ser desenhados da mesma 
maneira. 
 
Isomorfos: Dois grafos G e H são isomorfos, isto é, G ≅ H se houver bijeções ΘGH(v):V(G)→V(H) 
e ΦGH(e):E(G)→E(H) tais que ΨG(e)={u,v}, ∀ e ∈ E(G), ∀ u,v ∈ V(G) se e somente se 
ΨH(ΦGH(e))={ΘGH(u),ΘGH(v)}. O par de funções (ΘGH(v), ΦGH(e)) é um isomorfismo entre G e 
H. 
Para provar que um grafo H é isomórfico a um grafo G, basta encontrar uma bijeção 
ΘGH(v):V(G)→V(H) para a qual seja possível mapear todas as arestas por uma bijeção 
ΦGH(e):E(G)→E(H) e que mantenha a relação das funções ΨG(e) e ΨH(e) conforme descrito na 
definição. Este processo pode ser feito exaustivamente verificando todas as bijeções possíveis 
dos vértices de G e H. Este procedimento tem complexidade n(G)!. 
 
Automorfismo: de um grafo G é um isomorfismo G em G, isto é, do grafo nele mesmo. Quando 
G é um grafo simples, o automorfismo consiste em uma permutação αG(v) dos vértices v ∈ V(G) 
que preserva as adjacências.  
 
Aula 3 
   
 
Grafos bipartidos : Um grafo G=(V(G),E(G),ΨG(e)) é bipartido se 
existem os conjuntos V'(G) ⊂ V(G) e V''(G) ⊂ V(G), sendo V'(G) ≠ ∅, 
V''(G) ≠ ∅, V'(G) ∩ V''(G) = ∅ e V'(G) ∪ V''(G) = V(G) tal que ∀ e ∈ 
E(G), ΨG(e) = {u, v} se u ∈ V'(G) e v ∈ V''(G). Isto é, em um grafo 
bipartido os vértices podem ser divididos em dois subconjuntos tal 
que todas as arestas possuem uma ponta em cada um dos 
conjuntos.  
 
     
 
 
Bipartido Completo: se ∀ u, v, sendo u ∈ V'(G) e v ∈ 
V''(G), existe uma aresta e ∈ E(G), tal que ΨG(e)={u,v}. 
Ou seja, um grafo bipartido completo, além de ser 
bipartido contém uma aresta para cada par de vértices 
formado por um elemento de cada bipartição. O grafo 
bipartido completo é denotado por Kn',n'', onde 
n'=|V'(Kn,n)| e n''=|V''(Kn,n)|.  
 
← K,3,3 
     
Grafos k­regulares : Um grafo G é k­regular se ∀ v ∈ V(G), dG(v)=k. Isto é, no grafo k­regular, 
todos os vértices possuem o mesmo grau k.  
 
 
Grafo de Petersen: Seja um conjunto de vértices V(G) de um grafo G 
composto por todos os 
subconjuntos de {1,2,3,4,5} que tem exatamente dois elementos. Digamos 
que dois elementos 
u, v ∈ V(G) são adjacentes se u ∩ v = ∅.  
 
     
Vizinhança : Dado um conjunto de vértices V'(G) ⊂ V(G) de um grafo G, a vizinhança ΓG(V'(G)) é 
definida por: 
v ∈ ΓG(V'(G)) se v ∉ V'(G) e se ∃ u ∈ V'(G), tal que ΨG(e) = {u, v} para alguma aresta e ∈ E(G). 
Ou seja, a vizinhança de um subconjunto de vértices de um grafo é definida por todos os 
vértices do grafo que não pertencem ao subconjunto e que são adjacentes a algum vértice do 
subconjunto. 
A vizinhança ΓG(v) de um vértice u ∈ V(G) é definida por:  
v ∈ ΓG(u) se v ≠ u e ∃ e ∈ E(G) tal que ΨG(e) = {u, v}. Ou seja, a vizinhança de um vértice de 
um grafo é dada pelo conjunto de todos os outros vértices que são adjacentes a ele.  
 
Obs: 
● Para prova uma afirmação falsa, prova por contradição. 
● Quando 1 grafo tem laço ele não é bipartido. 
● Quando 1 grafo forma um ciclo com um número impar de arestas, não é bipartido. Quando 
for número par de aresta pode ou não ser bipartido. 
 
Aula 4 
     
Matriz de incidências : Seja o grafo G=(V(G), E(G), ΨG(e)), a matriz MG de dimensões n(G) x 
m(G) é chamada matriz de incidências de G quando MG ≔ (m(v, e)), onde v ∈ V(G), e ∈ E(G) e 
m(v, e) ∈ {0, 1, 2} é o número de incidências da aresta e sobre o vértice v. Note que apenas um 
laço contribui com valor dois em uma matriz de incidência. Esta matriz pode ser útil para estudar o 
grau de cada vértice. Basta somar os elementos da linha do vértice e temos o seu grau. 
 
Teorema 1: Para qualquer grafo G=(V(G), E(G), ΨG(e)), ∑ dG ( v)=2 m(G) 
Prova: Considere a matriz de incidências MG de G. A soma dos elementos na linha 
correspondente ao vértice vi ∈ V(G) é precisamente dG(vi), e portanto, ∑_(v∈V (G) ) d G ( v) é a 
soma de v∈V (G ) todas as linhas de MG. 
A soma dos elementos de uma coluna de MG é 2, pois ΨG(e) mapeia ei ∈ V(G) sobre exatamente 
dois vértices, sendo a aresta um laço ou não, ela sempre possui duas pontas, portanto ∑_(v∈V 
(G) ) 2 é e∈ E (G) 
a soma de todos os elementos de MG. Igualando as duas expressões acima, temos que : 
∑ _(v∈V (G) ) dG ( v)= ∑ _(e∈E (G) ) 2=2∣E (G)∣=2 m(G) , como queríamos demonstrar. 
 
Matriz de adjacências : Seja o grafo G=(V(G), E(G), ΨG(e)), a matriz AG de dimensões n(G) x 
n(G) é chamada matriz de adjacências de G quando AG ≔ (a(u, v)), onde u e v ∈ V(G) e a(u, v) ∈ N 
é o númerode arestas e ∈ E(G) para as quais ΨG(e)={u, v}. Note que os laços contam duas vez 
para o vértice sobre o qual eles incidem, como se fossem adjacentes pelos dois sentidos em que 
a aresta pode ser percorrida , isto é, na tabela linha x coluna e coluna x linha. Esta tabela é útil 
para esboçar um bom posicionamento para os vértices em um desenho sem muitos cruzamentos. 
 
Subgrafos : Sejam os grafos G=(V(G), E(G), ΨG(e)) e H=(V(H), E(H), ΨH(e)) dado que 
V(H)=V(G), E(H)=E(G) \ e, para e ∈ E(G), e ΨH(e) = ΨG(e) ∀ e ∈ E(H), dizemos que o grafo H é o 
resultado da remoção da aresta e de G. Assim, m(H) = m(G) – 1 e n(H) = n(G). 
Sejam os grafos G=(V(G), E(G), ΨG(e)) e H=(V(H), E(H), ΨH(e)) dado que V(H)=V(G) \ v, sendo 
v ∈ V(G), E(H)=E(G) ­ E'(G), sendo e ∈ E'(G) se ΨG(e) = {u, v}, ∀ u ∈ V(G), e ΨH(e) = ΨG(e), 
∀ e ∈ E(H), dizemos que o grafo H é o resultado da remoção do vértice v de G. Assim, 
m(H) = m(G) ­ dG(v) e n(H) = n(G) – 1. 
Mais formalmente, um grafo H=(V(H), E(H), ΨH(e)) é dito subgrafo de G=(V(G), E(G), ΨG(e)), se 
V(H) ⊂ V(G), E(H) ⊂ E(G) e se ΨH(e) = ΨG(e), ∀ e ∈ E(H).  
 
Aula 5 ­ Caminhos e ciclos.