Definição de grafo. Vértice, aresta, caminho e ciclo, conectividade, árvore e floresta, grafo bipartido, subgrafo induzido, minors, hiper-grafo, grafo direcionado e orientado, multigrafo. Tour de Euler. Ciclo de Hamilton. Casamentos (matching): em grafos gerais ou bipartidos. Grafos planares: Teorema de Kuratowsky, dualidade. Coloração: mapas e grafos planares. Coloração de vértices e de arestas. Grafos Perfeitos. Representação computacional de grafos: matriz de adjacência e lista de adjacência. Busca em Amplitude. Busca em Profundidade e aplicações: Ordenação topológica, componentes fortemente conexas, componentes biconexas. Árvores geradoras: algoritmos de Kruskal e de Prim. Problema da Árvore de Steiner. Problema do Caminho Mais Curto em grafos: Algoritmos de Dijikstra, de Bellman-Ford, e de Floyd-Warshall. Classes de Problemas: P, NP e NP-Completo.