Grafos, grafos simples, subgrafos. Isomorfismo de grafos. Representação computacional. Algoritmos de buscas. Grafos orientados. Trilhas, caminhos e ciclos. Distância. Caminho mínimo. Conectividade de vértices e arestas. Grafos hamiltonianos. Problemas de caixeiro viajante. Grafos eulerianos. Problema do carteiro chinês. Árvores, árvore geradora mínima. Teoria do NP completo. Classes P, NP, NP-completo, NP-Difícil. Reduções polinomiais. Prova de NP-completude. Noções de planaridade. Noções de coloração de vértices. Número cromático. Noções de casamentos. Casamentos perfeitos. Noções de fluxos em redes. |