lista2_grafos

Prévia do material em texto

Lista de exercícios #2
Grafos e Algoritmos Computacionais
1 - Um nó é dito folha se possui grau <= 1. Uma árvore é dita enraizada se possui 
um nó escolhido especialmente para ser a raiz da árvore. Uma árvore binária 
possui as seguintes propriedades: 
P1) cada vértice v possui um vizinho pai(v), exceto a raiz.
P2) cada vértice v possui no máximo dois vizinhos filho(v)
Mostre que o número de folhas menos um é igual ao número de vértices com dois 
filhos. 
3 - Mostre que toda árvore é um grafo bipartido.
4 - Seja G(V,E) um grafo conexo. Mostre que |E| >= |V|-1
5 - Seja G(V,E) um grafo qualquer. Se |E| >= |V|-1 podemos concluir que G é 
conexo?
6 - Seja G(V,E) um grafo conexo com n vértices. Mostre que G é árvore se e 
somente se G possui n-1 arestas.
7 - Construa um grafo sem triângulos, com número cromático igual a 3 com o 
menor número de vértices possível.
8- Como é possível construir um grafo cujo número cromático seja igual a um 
inteiro k?
9 - Qual o menor número de dias que precisamos para agendar provas para sete 
disciplinas de maneira que nenhum aluno faça duas provas no mesmo dia? A 
tabela abaixo indica quais disciplinas possuem alunos em comum.
1 2 3 4 5 6 7
1 1 1 1 1 1
2 1 1 1
3 1 1 1
4 1 1 1 1
5 1 1
6 1 1 1 1
7 1 1 1
10 - Demonstre a fórmula de Euler |V| + f = |E| + 2 
11 - Considere grafos com o número de vértices citados abaixo. M(G) é o número 
máximo de arestas que G pode possuir, e P(G) é o número máximo de arestas 
que G pode possuir permanecendo planar. Calcule M(G) e P(G) para cada um dos 
grafos abaixo e justifique a resposta.
a) G3 = (V1, E1) e |V3| = 3
b) G4 = (V4, E4) e |V4| = 4
c) G5 = (V5, E5) e |V5| = 5
d) G6 = (V6, E6) e |V6| = 6
e) G7 = (V7, E7) e |V7| = 7
f ) G8 = (V8, E8) e |V8| = 8
 
12 - Considere grafos bipartidos com o número de vértices citados abaixo. Calcule 
M(G) e P(G) para cada um dos grafos abaixo e justifique a resposta.
a) G2,2, onde Va é particionado em Va1 e Va2, |Va1| = 2 e |Va2| = 2
b) G2,3, onde Va é particionado em Va1 e Va2, |Va1| = 2 e |Va2| = 3
c) G2,4, onde Va é particionado em Va1 e Va2, |Va1| = 2 e |Va2| = 4
d) G2,5, onde Va é particionado em Va1 e Va2, |Va1| = 2 e |Va2| = 5
e) G2,6, onde Va é particionado em Va1 e Va2, |Va1| = 2 e |Va2| = 6
f ) G3,3, onde Va é particionado em Va1 e Va2, |Va1| = 2 e |Va2| = 6
g) G3,4, onde Va é particionado em Va1 e Va2, |Va1| = 2 e |Va2| = 6
13 - Mostre que um grafo é bibartido sse possui 2-coloração. Note que a 2-
coloração não é necessariamente a menor coloração possível, como é o caso do 
do grafo totalmente desconexo, que pode ser bipartido e ainda assim o número 
cromático é 1.