Oppgave 1

A, B, C, D, E, F, G
A, C, B, D, E, F, G
A, B, C, D, F, E, G
A, C, B, D, F, E, G

Oppgave 2

  private Node asyklisk(Node p)  // rekursiv dybde-først-traversering
  {
    p.besøkt = true;
    for (Node q : p.kanter)  // alle naboene til p
    {
      if (!q.besøkt)
      {
        q.forrige = p;
        Node r = asyklisk(q);
        if (r != null) return r;
      }
      else if (p.forrige != q)
      {
        q.forrige = p;
        return q;  // en sykel er funnet og q inngår
      }
    }
    return null;  // ingen sykel så langt
  }

  public String asyklisk()  // virker også for ikke-sammenhengende grafer
  {
    if (noder.size() <= 1) return null;

    String resultat = null;  // denne skal returneres til slutt

    for (Iterator<Node> i = noder.values().iterator(); i.hasNext(); )
    {
      Node p = i.next();

      if (!p.besøkt)
      {
        Node r = asyklisk(p);  // kaller den rekursive metoden

        if (r != null)  // vi har funnet en sykel
        {
          StringJoiner sj = new StringJoiner(", ", "[", "]");
          sj.add(r.navn);  // starter sykeltraverseringen i r

          Node s = r.forrige;  // hjelpenode for sykeltraversering

          while (s != r)  // går rundt sykelen
          {
            sj.add(s.navn);
            s = s.forrige;
          }

          sj.add(r.navn);  // legger inn r på nytt
          resultat = sj.toString();
          break;
        }
      }
    }

    nullstill();
    return resultat;  // nodene i en sykel
  }

Oppgave 3

  public boolean asyklisk()  // hører til klassen MGraf
  {
    if (antall <= 2) return true;  // tom graf eller maks to noder

    forrige = new int[antall];
    boolean[] besøkt = new boolean[antall];

    int i = 0;                    // strater i noden med indeks 0
    forrige[i] = -1;
    return asyklisk(i, besøkt);   // kaller den rekursive metoden
  }

  private boolean asyklisk(int i, boolean[] besøkt)
  {
    besøkt[i] = true;

    for (int j = 0; j < antall; j++)
    {
      if (graf[i][j])  // kant fra i til j
      {
        if (!besøkt[j])
        {
          forrige[j] = i;
          if (!asyklisk(j, besøkt)) return false;
        }
        else if (forrige[i] != j) return false;  // en sykel
      }
    }
    return true;
  }

Oppgave 4

Oppgave 5