Aus ProgrammingWiki

Inhaltsverzeichnis

1 Aufgabe 1 - Unterscheidung der Graphen
2 Aufgabe 2 - Worträtsel
3 Aufgabe 3 - Algorithmus
4 Aufgabe 4 - Postbotenproblem
5 Aufgabe 5 - Empirische Analyse
6 Aufgabe 6 - Zeichnen
7 Lösungen

Aufgabe 1 - Unterscheidung der Graphen

Unterscheiden Sie die Graphen nach eulersch, semi-eulersch oder weder noch.
a)
b)
c)
d)
e)

Aufgabe 2 - Worträtsel

Bilden Sie einen Euler-Weg, der vom rotmarkierten Punkt beginnt ,sodass die abgelaufenen Kanten eine Lösungswortgruppe ergeben.

Aufgabe 3 - Algorithmus

Wenden Sie einen der beiden in der Vorlesung behandelten Algorithmen zum Nachweisen der Eulerschkeit eines Graphen(Hierholzer/Fleury) an.

Aufgabe 4 - Postbotenproblem

Wenden Sie den Postbotenalgorithmus für folgenden Graphen an.

Aufgabe 5 - Empirische Analyse

Führen Sie eine empirische Analyse durch

import java.util.ArrayList; import java.util.Random; public class Algorithm { Random r= new Random(); Vertice V; Vertice Start[]=new Vertice[2]; Vertice A=new Vertice("A"); Vertice B=new Vertice("B"); Vertice C=new Vertice("C"); Vertice D=new Vertice("D"); Vertice E=new Vertice("E"); Vertice F=new Vertice("F"); Vertice G=new Vertice("G"); Vertice H=new Vertice("H"); ArrayList<Edge> listeE= new ArrayList<Edge>(); ArrayList<Edge> listeTour=new ArrayList<Edge>(); ArrayList<Edge> listeCircle=new ArrayList<Edge>(); ArrayList<Vertice> listeV= new ArrayList<Vertice>(); int ungeradeNodes=0; Edge e1=new Edge(A,B); Edge e2=new Edge(A,F); Edge e3=new Edge(B,C); Edge e4=new Edge(B,E); Edge e5=new Edge(B,D); Edge e6=new Edge(C,D); Edge e7=new Edge(D,E); Edge e8=new Edge(D,H); Edge e9=new Edge(E,H); Edge e10=new Edge(E,F); Edge e11=new Edge(F,H); Edge e12=new Edge(G,H); Edge e13=new Edge(F,G); Edge e14=new Edge(A,G); public void isEulersch(){ vAndEadd();//listen Befüllen for (Edge e:listeE){ e.v1.addGrad(); e.v2.addGrad(); } int z=0; for (Vertice N:listeV) { if(N.getGrad()%2==1){ if (z!=2){ Start[z]=N; z++; } ungeradeNodes++; } } if (ungeradeNodes==2){ System.out.println("ein EulerWeg"); Startweg(); Hierholz(); System.out.println("Alle Kanten"); for(Edge le:listeTour){ System.out.println(le.v1.getName()+":"+le.v2.getName()+";"); } } if (ungeradeNodes==0){ System.out.println("Ein Eulerkreis"); Start[0]= listeV.get(r.nextInt(listeV.size())); Hierholz(); System.out.println("Alle Kanten"); for(Edge le:listeTour){ System.out.println(le.v1.getName()+":"+le.v2.getName()+";"); } } if (ungeradeNodes>2){ System.out.println("Kein Eulerkreis bzw. Eulerweg Graph"); } } void Hierholz(){ boolean x=false; firstV(); while(!listeE.isEmpty()){ Edge so=null; //Prüfung ob nächster Knoten einen Kreis ergibt for(Edge E:listeE){ if(E.v2==Start[0]&&V==E.v1||E.v1==Start[0]&&V==E.v2){ so=E; V=Start[0]; listeCircle.add(so); listeE.remove(so); x=true; break; } } if (!x){ for(Edge E:listeE){ if(E.v1==V){ V=E.v2; so=E; listeCircle.add(so); listeE.remove(so); break; } else{ if(E.v2==V){ V=E.v1; so=E; listeCircle.add(so); listeE.remove(so); break; }} } } if(Start[0]==V){ x=false; for(Edge g:listeCircle){ listeTour.add(g);} System.out.println("Kreis:"); for(Edge hhz:listeCircle){ System.out.println(hhz.v1.getName()+":"+hhz.v2.getName()+";"); } for(Edge K:listeCircle){ int gh=0; for(Edge T:listeE){ if (K.v1==T.v1||K.v2==T.v1){ Start[0]=T.v1; gh++; break; } if (K.v1==T.v2||K.v2==T.v2){ Start[0]=T.v2; gh++; break; } } if (gh>0){ listeCircle.clear(); break; } } firstV(); } } } void vAndEadd(){ listeE.add(e1); listeE.add(e4); listeE.add(e8); listeE.add(e9); listeE.add(e5); listeE.add(e6); listeE.add(e7); listeE.add(e2); listeE.add(e3); listeE.add(e11); listeE.add(e12); listeE.add(e13); listeV.add(A); listeV.add(B); listeV.add(C); listeV.add(D); listeV.add(E); listeV.add(F); listeV.add(G); } void firstV(){ V=Start[0]; for(Edge E:listeE){ if(E.v1==Start[0]){ V=E.v2; listeCircle.add(E); listeE.remove(E); break; } if(E.v2==Start[0]){ V=E.v1; listeCircle.add(E); listeE.remove(E); break; } } } void Startweg(){ System.out.println("Weg:"); boolean x=false; while(Start[0]!=Start[1]){ Edge so=null; for(Edge E:listeE){ if(E.v1==Start[0]&&E.v2==Start[1]){ so=E; Start[0]=E.v2; listeCircle.add(so); listeE.remove(so); x=true; break; } else{ if(E.v2==Start[0]&&E.v1==Start[1]){ so=E; Start[0]=E.v1; listeCircle.add(so); listeE.remove(so); x=true; break; }} } for(Edge E:listeE){ if(x){ break; } if(E.v1==Start[0]){ Start[0]=E.v2; so=E; listeCircle.add(so); listeE.remove(so); break; } else{ if(E.v2==Start[0]){ Start[0]=E.v1; so=E; listeCircle.add(so); listeE.remove(so); break; }} } } for(Edge g:listeCircle){ listeTour.add(g);} listeCircle.clear(); for(Edge le:listeTour){ System.out.println(le.v1.getName()+":"+le.v2.getName()+";"); } } }

public class Edge { Vertice v1; Vertice v2; Edge(Vertice a, Vertice b){ this.v1=a; this.v2=b; } }

public class Main { public static void main(String args[]){ Algorithm a=new Algorithm(); a.isEulersch(); } }

public class Vertice { private int grad=0; private String name; Vertice(String name){ this.name=name; } void addGrad(){ grad++; } int getGrad(){ return grad; } String getName(){ return name; } }

Aufgabe 6 - Zeichnen

Zeichnen Sie mindestens 3 Graphen mit 5 Knoten die einen Eulerkreis beinhalten.

Lösungen

Aufgabe 1: a) nicht eulersch b) eulersch c) semi-eulersch d) eulersch e) nicht eulersch

Aufgabe 2: Lösungswort: great work

Aufgabe 3: Eine von vielen möglichen Lösungen des Hierholzer Algorithmuses:
Und die Lösung mit dem Agorithmus von Fleury:

Aufgabe 4: Der vollständige Graph G' aus allen Knoten mit ungeraden Grad, die kürzesten Wege zwischen diesen sowie eingefügten Matchingkanten:
Die Integrierung in den Graphen G (rot = doppelte Kante):

Anwendung des Hierholzer Algorithmus: