Lista de Exercícios-2021 2

UNIVERSIDADE FEDERAL DO CEARÁ - CAMPUS DE CRATEÚS CURSO: CIÊNCIA DA COMPUTAÇÃO e SISTEMAS DE INFORMAÇÃO DISCIPLINA: MATEMÁTICA DISCRETA PROFESSORA: LÍLIAN DE OLIVEIRA CARNEIRO ALUNO(A): LISTA DE EXERCÍCIOS 1. O grafo abaixo que representa os estados do Brasil é definido da seguinte maneira: cada vértice é um dos estados do Brasil; dois estados são adjacentes se têm uma fronteira comum. Com base em tais informações faça o que se pede: (a) Qual é a ordem desse grafo? (b) Qual é o grau dos vértices BA e CE, respectivamente? (c) Este grafo possui vértices pendentes? Se sim, indique tais vértices. (d) O grafo é completo? Por quê? (e) Apresente um subgrafo do grafo dado. (f) Apresente um caminho e indique o seu comprimento. 2. Dado o grafo abaixo, faça o que se pede: (a) Represente o grafo por uma matriz de adjacência. (b) Use uma lista de adjacência para representar o grafo. 3. Desenhe um grafo não orientado representado pela matriz de adjacência   1 2 0 1 2 0 3 0 0 3 1 1 1 0 1 0   . 4. A proposição “todo passeio é um caminho” é verdadeira ou falsa? Por quê? 5. Sabendo que um grafo completo com n vértices, denotado por Kn, é um grafo em que todo par de vértices forma uma aresta. Qual é o número de arestas de um Kn?