LISTA 7 DE GRAFOS

UNIVERSIDADE FEDERAL DO PARÁ
INSTITUTO DE CIÊNCIAS EXATAS E NATURAIS
PROGRAMA DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO

Aluna: Alessandra Priscila Alves de Oliveira
Professor: Nelson Neto
Matrícula: 201520070012

GRAFOS – LISTA 7

1. Prove as afirmativas abaixo ou dê contra-exemplo
a) O vértice de grau máximo pertence, obrigatoriamente, a um conjunto dominante mínimo.
Resposta: A afirmação não é correta. Isso porque um vértice de grau máximo não precisa ser necessariamente adjacente a todos os vértices do conjunto dominante mínimo, como pode ser visto no exemplo abaixo, no qual temos um grafo G cujo seu vértice de maior grau (4) não pertence ao conjunto dominante mínimo, representado por C = {1, 5, 6}. Portanto, nem sempre o vértice de grau máximo pertence a um conjunto dominante mínimo.

b) Um conjunto independente maximal de um grafo conexo é sempre dominante.
Resposta: Essa afirmação é verdadeira. Um conjunto independente máximo é formado pelo número máximo de vértices que não têm adjacências entre si. Em um grafo que é conexo os vértices devem ter adjacências com outros vértices que não fazem parte do conjunto. E assim o conjunto satisfaz a necessidade do conjunto dominante de ter os vértices não pertencentes ao conjunto como adjacentes a pelo menos um vértice do conjunto.
c) Um conjunto dominante mínimo de um grafo conexo pode não ser independente.
Resposta: Essa afirmação é verdadeira, pois o conjunto dominante precisa ter um conjunto de vértices que tenha todos os vértices do grafo no conjunto ou adjacente a um dos vértices do conjunto.
d) Todos os vértices saturados por um acoplamento formam um subconjunto independente de vértices.
Resposta: A afirmação não é correta. Isso porque cada aresta independente do acoplamento irá conectar dois vértices e em um acoplamento saturado os vértices terão adjacência com os vértices do grupo, o que vai contra a definição de conjunto independente de vértices.

2. Considere o grafo M abaixo e trabalhe os seguintes