Euler-Kreise und -Wege Übung
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Javascript</language>
=Aufgabe 1 - Unterscheidung der Graphen=
Unterscheiden Sie die Graphen nach eulersch, semi-eulersch oder weder noch.<br>
a)[[Bild:Kerich_Uebungsaufgabe1_1.png]]<br>b)[[Bild:Kerich_Uebungsaufgabe1_2.png]]<br>c)[[Bild:Kerich_Uebungsaufgabe1_3.png]]<br>
d)[[Bild:Kerich_Uebungsaufgabe1_4.png]]<br>e)[[Bild:Kerich_Uebungsaufgabe1_5.png]]
=Aufgabe 2 - Worträtsel=
Bilden Sie einen Euler-Weg, der vom rotmarkierten Punkt beginnt ,sodass die abgelaufenen Kanten eine Lösungswortgruppe ergeben.<br>
[[Bild:Kerich_Uebung_worträtsel.png]]
=Aufgabe 3 - Algorithmus=
Wenden Sie einen der beiden in der Vorlesung behandelten Algorithmen zum Nachweisen der Eulerschkeit eines Graphen(Hierholzer/Fleury) an.<br>
[[Bild:Kerich_Uebung_Algorithmus.png]]
=Aufgabe 4 - Postbotenproblem=
Wenden Sie den Postbotenalgorithmus für folgenden Graphen an.<br>
[[Bild:Kerich_Uebung_Postbote.png]]
=Aufgabe 5 - Empirische Analyse=
Führen Sie eine empirische Analyse durch<br>
<code id="5667fea2c4493">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()+";");
}
}
}
</code>
<code id="5667fea2c4519">
public class Edge {
Vertice v1;
Vertice v2;
Edge(Vertice a, Vertice b){
this.v1=a;
this.v2=b;
}
}
</code>
<code id="5667fea2c4598">
public class Main {
public static void main(String args[]){
Algorithm a=new Algorithm();
a.isEulersch();
}
}
</code>
<code id="5667fea2c461d">
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;
}
}
</code>
=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.
[[Bild:uebung_Algorithmus_lsg.png]]<br>
Und die Lösung mit dem Agorithmus von Fleury:<br>
<popup>
[[Bild:fleury.gif]]
</popup>
----
Aufgabe 4:
Der vollständige Graph G' aus allen Knoten mit ungeraden Grad, die kürzesten Wege zwischen diesen sowie eingefügten Matchingkanten.
[[Bild:uebung_Postbote_lsg.png]]
<br>
Die Integrierung in den Graphen G.<br>
[[Bild:uebung_Postbote_lsg2.png]]
----
Aufgabe 6:
3 von vielen Möglichkeiten<br>
1. [[Bild:lsg_1.png]]
2. [[Bild:lsg_2.png]]
3. [[Bild:lsg_3.png]]