Problema 1: Carteiro Chinês (Hélio, Ivan, Thiago)

Dado um grafo G= (V, E), encontrar um passeio fechado que visite todas as arestas de G com um número mínimo de repetições de arestas.

Problema 2: Caixeiro Viajante (Hermano, Ronan, Edmundo)

Dado um grafo G=(V, E) completo e ponderado, encontrar um ciclo que visite todos os vértices de G cuja soma dos pesos das arestas seja mínimo.

Problema 3: Coloração de Vértices (Emanuelle, Luciana, Cibele)

Dado um grafo G=(V,E), determinar o menor inteiro k  tal que os vértices de G possam ser coloridos com k cores respeitando a condição de que quaisquer dois vértices adjacentes de G têm cores distintas.

Problema 4: Coloração de Arestas (Camila, Karolinna, Anderson)

Dado um grafo G=(V,E), determinar o menor inteiro k tal que as arestas de G possam ser coloridas com k cores respeitando a condição de que quaisquer duas arestas adjacentes de G têm cores distintas.

Problema 5: Emparelhamento Máximo (Jonathan, Michel, José Maria)

Dado um grafo G=(V,E), determinar o maior conjunto de arestas  duas a duas não adjacentes de G.

Problema 6: Conjunto Independente Máximo (Wládia, Luana, Débora)

Dado um grafo G=(V,E), determinar o maior conjunto de vértices dois a dois não adjacentes de G.

Problema 7: Clique Máxima

Dado um grafo G=(V,E), determinar o maior conjunto de vértices dois a dois adjacentes de G.

Problema  8: Cobertura de Vértices (Raphaela, Anecy, Karla)

Dado um grafo G=(V,E), determinar o menor conjunto de vértices de G tal que toda aresta de G é incidente a pelo menos um vértice do conjunto.

Problema 9: Cobertura de Arestas (Kleber, Davi, Jivago)

Dado um grafo G=(V,E), determinar o menor conjunto de arestas de G tal que todo vértice de G é incidente a pelo menos uma aresta do conjunto.

Problema 10: Cobertura por Cliques

Dado um grafo G=(V,E), determinar o menor conjunto de cliques de G tal que todo vértice G está em pelo menos uma das cliques desse conjunto.

Problema 11: Planaridade (Carlos Eduardo Barbosa)

Dado um grafo G=(V,E), determinar se G é planar.

Problema 12:  Corte de Vértices (Helber Wagner/Mario Victor)

Dado um grafo conexo G=(V,E), determinar o número mínimo de vértices que precisam ser removidos para que G torne-se desconexo.

Problema 13: Caminho Crítico (Marco Diego, Agnelo, Rafael Ivo)

Dado um grafo orientado e acíclico G=(V,E), determinar o caminho mais longo de G.

Problema 14: Semente em Dígrafos

Dado um grafo orientado G=(V,E), determinar se G possui um conjunto independente de vértices S tal que qualquer vértice de V-S é destino de algum arco que tem origem em um vértice de S.

Problema 15: Conjunto Dominante (Ricardo Sergio, Victor Silveira)

Dado um grafo orientado G=(V,E), determinar se G possui um conjunto independente de vértices S tal que qualquer vértice de V-S é adjacente a algum vértice de S.

Problema 16: Árvore de Steiner

Dado um grafo ponderado G=(V,E) e uma partição de V(G)=(R,O), determinar um subgrafo T de G que : i) seja uma árvore; ii) contenha todos os vértices de R e

iii) contenha um número qualquer de vértices de O (pode ser nenhum); e tal que a soma dos pesos das arestas de T seja mínimo.

Problema 17: Cintura e Maior caminho do Grafo (Carlos Eduardo Pontual, Heraldo, Bruno)

Dado um grafo G=(V,E), determinar o menor ciclo de G e o seu maior caminho.