Problema do Conjunto Independente Máximo

Universidade Federal de São João del Rei
Departamento de Ciência da Computação
Algoritmos e Estrutura de Dados III
Professor Leonardo Chaves Dutra da Rocha
Trabalho Prático 3
Problema do Conjunto Independente Máximo
André Bustamante de Carvalho

Antônio Carlos Abrão Filho

Sumário
1

1

1.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Conjunto de Vértices Independentes . . . . . . . . . . . . . .
1.3 NP-Completude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

Problema Proposto

1
2
3

Soluções Implementadas

5

2.1 Solução Ótima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Pseudo código . . . . . . . . . . . . . . .. . . . . . . . . . . . 5
2.1.2 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.3 Complexidade . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Solução Gulosa . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 7
2.2.1 Pseudo código . . . . . . . . . . . . . . .. . . . . . . . . . . . 7
2.2.2 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.3 Complexidade . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Solução por vértices de maior grau . . . . . . . . . . . . . . . 9
2.3.1 Pseudo código . . . . . . . . . . . . . . .. . . . . . . . . . . . 9
2.3.2 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3.3 Complexidade . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3

11

3.1 Testes Realizados . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 Tempo de Execução . . . . . . . . . . . . . . . . . . . . .
3.2 Gráficos dos Resultados . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 Considerações . . . . . . . . . . . . . . . . . . . . . . . . . .

5

Desempenho e Complexidade

11
11
12
14

Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

1