Lista de Exercícios - Grafos - UFMG - Matemática Discreta

Lista de Exercícios 9 Grafos UFMGICExDCC DCC111 Matemática Discreta Ciências Exatas Engenharias 2o Semestre de 2014 1 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 c A1 xx 0 A2 x 1 x 0 A3 x0 x 1 A4 x 1 x 1 A5 xx 1 A6 R 2 Pode haver um grafo simples com 15 vértices cada um com grau 5 3 Determine se cada um dos grafos abaixo é bipartido a e c d a b b b a c d e 1 c f a b c d e d f a b c d e e f a b c d e 4 Quantos vértices e quantas arestas têm os grafos abaixo a Kn grafo completo b Kmn grafo bipartido completo c Cn grafo ciclo d Qn grafo cubo e Wn grafo roda 5 Quantas arestas tem um grafo com vértices de graus 5 2 2 2 2 1 Desenhe um possível grafo 6 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 7 Quantos subgrafos com pelo menos um vértice tem K3 8 Desenhe todos os subgrafos do grafo abaixo c a b d 9 Para que valores de n os grafos abaixo são regulares a Kn 2 b Cn c Wn d Qn 10 Quantos vértices tem um grafo regular de grau 4 com 10 arestas 11 O grafo complementar G de um grafo simples G tem os mesmos vértices de G Dois vértices são adjacentes em G se e somente se eles não são adjacentes em G Determine os seguintes grafos a Kn b Kmn c Cn d Qn 12 Se o grafo simples G tem v vértices e e arestas quantas arestas tem G 13 Mostre que se G é um grafo simples com n vértices então G G Kn 14 O grafo reverso de um grafo dirigido G V E representado por Gr é o grafo dirigido V F onde u v F se e somente se v u E Desenhe os grafos Gr correspondentes aos seguintes grafos a e a b c d b d a b c e c e b c a f d 15 Seja G um grafo dirigido Mostre que G Gr se e somente se a relação associada com G é simétrica 16 Represente a matriz de adjacência do grafo Q3 17 Seja uma matriz simétrica quadrada formada apenas por 0s e 1s que tem apenas 0s na diagonal principal Essa matriz pode representar a matriz de adjacência de um grafo simples 18 O que representa a soma das entradas de uma coluna de uma matriz de adjacência de um grafo não dirigido E de um grafo dirigido 19 O que representa a soma das entradas de uma coluna de uma matriz de incidência de um grafo não dirigido 3 20 Os pares de grafos abaixo são isomorfos a b 21 Mostre que o isomorfismo de grafos simples é uma relação de equivalência 22 Mostre que os vértices de um grafo bipartido com dois ou mais vértices podem ser ordenados de tal forma que a sua matriz de adjacência tem a forma 0 A B 0 onde as quatro entradas acima são blocos retangulares 23 Um grafo simples G é dito ser autocomplementar se G e G são isomorfos Apresente um grafo simples autocomplementar com cinco vértices 24 Para que inteiros n o grafo Cn é autocomplementar 25 Seja G V E um grafo simples Seja R uma relação em V formada por pares de vértices u v tal que existe um trajeto path de u para v ou tal que u v Mostre que R é uma relação de equivalência 26 Apresente um grafo que tenha um circuito Euleriano e um circuito Hamiltoniano mas que não sejam idênticos 27 Um grafo possui oito vértices e seis arestas Esse grafo é conexo Justifique a resposta 28 Nos grafos abaixo assuma que cada vértice possui um identificador único vi i 1 Cada variável usada é um número inteiro positivo maior ou igual a 1 ou um outro valor específico conforme o caso Para cada letra diga quantas soluções distintas podem ser obtidas a Árvores geradoras de um grafo Cn n 3 b Circuitos Hamiltonianos de um grafo Kn n 3 começando num vértice vi 1 i n c Circuitos Eulerianos de um grafo Kmm m 2 m 2a e começando num vértice vi 1 i 2m Grafo Kmm m 2 m 2a é o grafo bipartido completo sendo que m é um número par Os grafos bipartidos completos que podemos ter são da forma K22 K44 K66 Ou seja cada vértice está conectado a exatamente m outros vértices Como m é par o grau de cada vértice é par e assim é possível haver circuitos Eulerianos 29 Determine os componentes fortemente conexos de cada grafo dirigido abaixo a d b c a e b f b c a i h d e g 30 Seja uma árvore com n vértices a Quantas arestas têm essa árvore b Prove esse resultado por indução matemática 5