Euler-Kreise und -Wege Übung

Aus ProgrammingWiki

Archivierte Version vom 2015-12-10T18:01:29+00:00. Aktuelle Version

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.

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.

Aufgabe 6: 1. 2. 3.

Euler-Kreise und -Wege Übung

Inhaltsverzeichnis

Aufgabe 1 - Unterscheidung der Graphen

Aufgabe 2 - Worträtsel

Aufgabe 3 - Algorithmus

Aufgabe 4 - Postbotenproblem

Aufgabe 5 - Empirische Analyse

Aufgabe 6 - Zeichnen

Lösungen

Suche