Problema do Conjunto Independente Máximo

2558 palavras 11 páginas
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 . . . . . . . . . .

Relacionados

  • Teoria dos conjuntos
    1937 palavras | 8 páginas
  • O Problema dos 36 oficiais
    1000 palavras | 5 páginas
  • Normas relativas ao parecer do auditor independente
    4419 palavras | 18 páginas
  • Problemas dos pvd
    3509 palavras | 15 páginas
  • teoria dos conjuntos
    1798 palavras | 8 páginas
  • Resolução dos Exercícios da Lista de Máximos e Mínimos
    1330 palavras | 6 páginas
  • Problemas sociais do Brasil
    1193 palavras | 5 páginas
  • Problema do jantar dos filósofos
    1056 palavras | 5 páginas
  • Teoria dos Conjuntos
    2157 palavras | 9 páginas
  • 1 Teoria dos Conjuntos
    1990 palavras | 9 páginas