Aplicações Práticas da Teoria dos Grafos

Problema das Câmeras da UFSC / Lobos

V = {v | v é uma área}

A = {(v1, v2) | v1 e v2 pertencem a V e a demarcação de v2 está ao lado da área demarcada v1 sem outras áreas entre elas}

Solução: Encontrar o subconjunto internamente estável máximo e a sua cardinalidade será o número máximo de territórios para se colocar os lobos.

Algoritmo de Inundação

Função:

G.háCiclos(v, vAnterior, jaVisitados)
  // v = vértice atualmente em foco
  // vAnterior = vértice em foco no passo anterior
  // jaVisitados = coleção contendo os vértices já visitados

  Se v ∈ jáVisitados Então
    retorna verdadeiro
  Fim Se // v recebe mensagem m
  jáVisitados.adiciona(v)
  Para cada vAdj adjacente a v faça
    Se vAdj = vAnterior Então
      G.inunda(v, vAnterior, jáVisitados, m)
    Fim Se
  Fim Para

Complexidade: O(m)

Avaliação de Aproveitamento do Curso

V = {e | e é um exame}

A = {(e1, e2) | e1 e e2 pertencem a V e um aluno irá fazer o exame e1 e e2}

Solução: Colorir o grafo e o número cromático será o número mínimo de dias para realizar todos os exames.

Problema dos Dançarinos

V = {d | d é um dançarino}

A = {(d1, d2) | d1 e d2 pertencem a V e o dançarino d1 pode fazer par com o dançarino d2}

Solução: Encontrar o emparelhamento perfeito e os pares de dançarinos serão os pares do emparelhamento. Caso não seja possível encontrar um emparelhamento perfeito, encontre um emparelhamento máximo e os dançarinos que ficarem sem par receberão um par que será contratado, e após as contratações, o emparelhamento será perfeito.

Grafo de Alunos de uma Mesma Fase

Um grafo não é planar se contiver nele K₅ ou K_3,3. Como ele não é bipartido, K_3,3 não ocorrerá. Logo, o grafo será planar se não contiver K₅, em outras palavras, se 5 estudantes não pertencerem à mesma fase.

Representatividade dos Alunos

G(V,A)

V = {f | f é um formando}

A = {(f1, f2) | f1 e f2 ∈ V e o formando f1 indicou o formando f2 para compor a comissão}

Solução: Ao analisar o grafo gerado, podemos definir os alunos que farão parte da comissão com base no conjunto externamente estável minimal que pode ser obtido a partir do grafo.

Problema das Barracas nos Cruzamentos / Damas no Tabuleiro

G(V,A)

V = {c | c é um cruzamento}

A = {(c1, c2) | c1 e c2 ∈ V e o cruzamento c1 é imediatamente ligado ao cruzamento c2 por uma trilha no parque}

Solução: Construímos o grafo acima e encontramos o conjunto independente maximal. Este conjunto conterá os cruzamentos que não são próximos de outros cruzamentos. A cardinalidade desse conjunto independente maximal será o número máximo de barracas de pipoca a serem instaladas sem estarem muito próximas umas das outras.