MO405 - Prova I1

Criada: 2012-03-29

Enunciado distribuido na sala.

Gabarito

  1. Código para decidir se grafo é bipartido, com certificado:

    boolean bipartido()
    |  Mapa d
    |  Fila f
    |  Mapa pred
    |  Conjunto X
    |  Conjunto Y
    |  for v in G.V() do
    |  |  if v not in d.keys() then
    |  |  |  d(v) ← 0
    |  |  |  f.push(v)
    |  |  |  X.add(v)
    |  |  |  while not f.empty() do
    |  |  |  |  u ← f.pop()
    |  |  |  |  for p in G.N(u) do
    |  |  |  |  |  if not p in d.keys() then
    |  |  |  |  |  |  d(p) ← d(u) + 1
    |  |  |  |  |  |  pred(p) ← u
    |  |  |  |  |  |  if d(p) mod 2 = 0 then
    |  |  |  |  |  |  |  X.add(p)
    |  |  |  |  |  |  else
    |  |  |  |  |  |  |  Y.add(p)
    |  |  |  |  |  |  f.push(p)
    |  |  |  |  |  else
    |  |  |  |  |  |  if d(p) + d(u) mod 2 = 0 then
    |  |  |  |  |  |  |  // ciclo impar: p...v...up
    |  |  |  |  |  |  |  Mapa ciclo
    |  |  |  |  |  |  |  x ← u
    |  |  |  |  |  |  |  while x != v and do
    |  |  |  |  |  |  |  |  ciclo(pred(x)) ← x
    |  |  |  |  |  |  |  |  x ← pred(x)
    |  |  |  |  |  |  |  x ← p
    |  |  |  |  |  |  |  while x != v and not x in ciclo.keys() do
    |  |  |  |  |  |  |  |  ciclo(x) ← pred(x)
    |  |  |  |  |  |  |  |  x ← pred(x)
    |  |  |  |  |  |  |  ciclo(u) ← p
    |  |  |  |  |  |  |  return false
    |  return true

    Quando acabar, se o resultado for true, "X" e "Y" terão a bipartição; se for false, o mapa "ciclo" terá o ciclo ímpar.

  2. 55432221
    _4321121
    __210111
    ___00011
    ___000_0

    Grafo: grafo com sequência de graus 55432221

    55542111
    _4431011
    __320001 (aqui se vê que não é simples)
    ___00000 (tive que tirar 2 do 2 e 1 do 1)

    Grafo: (em construção) grafo com sequência de graus 55542111

    55532211
    _4421111
    __310011
    ___00000

    Grafo: (em construção) grafo com sequência de graus 55532211

  3. (em construção)
  4. 40 árvores espalhadas.

Critérios de correção

  1. Componentes conexas: quase ninguém prestou atenção nisso. Não tirei ponto.

    Detecção correta de bipartido: vale 2,0 pontos.

    Construção correta de ciclo ímpar e de bipartição: vale 1,0 ponto cada. Sem código, vale 0,5 ponto cada.

  2. Quase todo mundo acertou todos. Se fez não simples onde havia simples, perdeu 0,5. Se esqueceu vértice, perdeu 0,5.

  3. Quase todo mundo acertou tudo. Se faltou vértice, perdeu 0,5.

  4. Aqui depende se a pessoa usou determinantes ou recursão em G-e e G.e.

    Para determinantes, o importante é: (1) construir a matriz de graus na diagonal e adjacências negativadas, (2) tirar uma linha e uma coluna e (3) calcular o determinante. Se falhou significativamente em alguma destas fases, perdeu 0,5. Se falhou em todas, nota zero.

    Para recursão, o importante é: (1) saber dividir em G-e e G.e, principalmente não esquecer as arestas múltiplas em G.e, e (2) fazer bem os casos base. Se falhou significativamente em alguma destas fases, perdeu 0,5. Se falhou em todas, nota zero.

MO405 Home

© 2012 João Meidanis