Übung Grundbegriffe der Graphentheorie 1

Wiki-Quelltext dieser Seite.

<language>Java</language>
==Datenstrukturen für Graphen==
*Gegeben ist folgendes <tt>IGraph</tt> Interface mit einer Hilfsklasse <tt>Edge</tt> zur einfacheren Behandlung von Kanten
<code id="562d004e971ca">
interface IGraph{
	// provides vertices as numbers (ascending, 0-based)
	// and edges between them (edges can be null if there is none)
	void setGraph(int[] vertices, Edge[] edges);
	
	// checks if IGraph returns correct vertices and edges
	int[] getVertices(); // returns vertices ascending
	Edge[] getEdges(); // returns edges 
	
	boolean isAdjacent(int v1, int v2); // returns whether v1 is connected to v2
	int getDegree(int vertex); // returns the degree of a certain vertex
	int getSize(); // returns the size of the class properties
}
class Edge{
	public int v1;
	public int v2;
	public Edge(int v1, int v2){
		// from smaller to greater for improved comparison
		this.v1 = v1 < v2 ? v1 : v2;
		this.v2 = v1 < v2 ? v2 : v1;
	}
	@Override
	public int hashCode() {
		return v1*31+v2;
	}
	@Override
	public boolean equals(Object o){
		if(o instanceof Edge)
		{
			Edge e = (Edge) o;
			return (this.v1 == e.v1 && this.v2 == e.v2);
		}
		return false;
	}
}
</code>

===Aufgabe===
*Erstelle 2 Klassen die das <tt>IGraph</tt> Interface implementieren
*# als Adjazenzmatrix
*# als Adjazenzliste
*Analysiere empirisch die Effizienz dieser beiden Datenstrukturen hinsichtlich
*#Speicherbedarf
*#Ermittlung des Knotengrades
*#Prüfung auf Adjazenz zweier Knoten

===Hilfestellung===
*Es wird ein Graph-Generator bereitgestellt, der das <tt>IGraph</tt> Interface benutzt um zufällige Graphen zu erzeugen
*Mit <tt>generate</tt> werden dem Graph <tt>g</tt> eine entsprechende Menge von Knoten (<tt>cntVertex</tt>) und Kanten (<tt>cntEdges</tt>) zur Initialisierung übergeben
*Die richtige Umsetzung der Speicherung wird mit den Funktionen <tt>getVertices</tt> und <tt>getEdges</tt> automatisch geprüft
<code id="562d004e9724b">
import java.util.Random;
import java.util.HashSet;

class GraphGenerator{
	private GraphGenerator() { }
	private static Random r = new Random();
	// isolated vertices possible
	// no loops possible
	// only one edge between a certain vertex pair
	public static boolean generate(IGraph g, int cntVertex, int cntEdges){
		if (g == null || cntEdges > (long) cntVertex*(cntVertex-1)/2)
			return false; // no graph instance passed or invalid vertex/edge count
		int[] v = new int[cntVertex]; // the new list of vertices
		for(int i = 0; i < cntVertex; i++)
			v[i] = i; // enumerated 0-based
		HashSet<Edge> edges = new HashSet<Edge>(); // result set of edges
		while (edges.size() < cntEdges){ // edge count not reached
			int i1 = r.nextInt(cntVertex); // generate 2 indexes
			int i2 = r.nextInt(cntVertex); // within vertex count
			while (i1 == i2) // when a loop was generated
				i2 = r.nextInt(cntVertex); // generate another index
			Edge e = new Edge(i1, i2); // indexes used as an edge
			if (!edges.contains(e)) // edge not there already?
				edges.add(e);
		}
		try{ // try to set generated vertices and edges at the given graph instance
			Edge[] ed = cntEdges > 0 ? edges.toArray(new Edge[cntEdges]) : null;
			g.setGraph(v, ed);
			// Check for validity of the graph instance
			int[] gVert = g.getVertices(); // should deliver the same vertices as given
			if (gVert.length != v.length){
				System.out.println("Wrong vertex count");
				return false;
			}
			for(int i = 0; i < gVert.length; i++){
				if (v[i] != gVert[i]){
					System.out.println("Different vertex");
					return false;
				}
			}
			Edge[] gEd = g.getEdges(); // should deliver the same edges as given
			if ((gEd == null && ed != null) || (gEd != null && ed == null)){
				System.out.println("Different edge definition");
				return false;
			}
			if (ed != null){ // compare edges
				if (ed.length != gEd.length){
					System.out.println("Different edge count");
					return false;
				}
				for(Edge ge : gEd){
					if (!edges.contains(ge)){
						System.out.println("Different edge");
						return false;
					}
					edges.remove(ge);
				}	
			}
		}
		catch(Exception ex){ // if anything goes wrong with the graph instance
			ex.printStackTrace();
			return false;
		}
		return true;
	}
}
</code>
*Deine implementierte Klasse <tt>YourGraph</tt> könnte also folgendermaßen mit einem Zufallsgraphen getestet werden
<code id="562d004e972bd">
public static void main(String[] args){
	YourGraph graph = new YourGraph(); // instantiate your class
	if (!GraphGenerator.generate(graph,10,15)) // generate a random graph with 10 vertices and 15 edges
		System.out.println(graph.getClass().getSimpleName() + " generation failed!");
	int d = graph.getDegree(5); // determine degree of vertex 5
	boolean b = graph.isAdjacent(3,8); // determine whether vertices 3 and 8 are connected
}
</code>
<popup name="Lösungen">
[[File:RaZ_GraphAdjMatList.zip]]<br>
[[Bild:RaZ_Effizienz.png]]
</popup>

=Grundbegriffe=

[[Bild:Ghx8 ;_FFahrrad.png|800px]]

==Aufgabe - Zuordnung==

{| class="wikitable"
|-
! Knoten  !! Kantenzug !! geschlossener Kantenzug !! einfacher Weg !! Weg !! einfacher Kreis !! Kreis 
|-
|{A,B,C}       || <popup>nein</popup>|| <popup>nein</popup> || <popup>ja</popup> ||<popup>ja</popup>|| <popup>nein</popup> ||<popup>nein</popup>               
|-
|{M,G,H,M}          || <popup>nein</popup>|| <popup>nein</popup> || <popup>nein</popup> ||<popup>nein</popup>|| <popup>ja</popup> ||<popup>ja</popup>           
|-
|{L,M,G,H,M,L}          || <popup>nein</popup>|| <popup>ja</popup> || <popup>nein</popup> ||<popup>nein</popup>|| <popup>nein</popup> ||<popup>nein</popup>   
|-
|{Q,O,N,P,Q,M}         || <popup>nein</popup>|| <popup>nein</popup> || <popup>nein</popup> ||<popup>ja</popup>|| <popup>nein</popup> ||<popup>nein</popup>                
|-
|{G,E,D,G,F,D,G,E}         || <popup>ja</popup>|| <popup>nein</popup> || <popup>nein</popup> ||<popup>nein</popup>|| <popup>nein</popup> ||<popup>nein</popup>              
|-
|{L,H,G,E,D,G,M,L}          || <popup>nein</popup>|| <popup>nein</popup> || <popup>nein</popup> ||<popup>nein</popup>|| <popup>nein</popup> ||<popup>ja</popup>             
|}

==Aufgabe - Strukturelle Umformungen==

a) Finde mindestens zwei Artikulationen.

Knoten {J} und {L}


b) Finde mindestens zwei Brücken.

Kanten {Q,M} und {J,K}


c) Führe eine Kontraktion mit K durch.

Ergebnis: Kante {J,K} und Knoten {K} werden entfernt, sodass ein Fahrrad ohne Lenkrad übrigbleibt

==Aufgabe - Teilgraphen==

a) Finde zwei Untergraphen
</code>
<popup name="Lösungen">
[[Bild:Ghx8 ;_RadUntergraph.png]]
[[Bild:Ghx8 ;_RadUntergraphB.png]]
</popup>



b) Skizziere aus einem Untergraphen verschiedene Teilgraphen

[[Bild:Ghx8 ;_RadinduzteilgraphB.png]]
[[Bild:Ghx8 ;_RadTeilgraphA.png]]
[[Bild:Ghx8 ;_RadTeilgraphB.png]]

c) Erstelle einen induzierten Teilgraphen aus einem Rad

[[Bild:Ghx8 ;_RadUntergraphB.png]]


d) Erstelle einen spannenden Teilgraphen aus einem Rad

[[Bild:Ghx8 ;_RadinduzteilgraphB.png]]

==Aufgabe==

Stell den Punkt I auf G um. Führe folgende Operationen durch mit den beiden Rädern durch:

a) Durschnitt

[[Bild:Ghx8 ;_DurchschnittA.png|50px]]

b) Vereinigung

[[Bild:Ghx8 ;_VereinigungA.png]]

c) Differenz

[[Bild:Ghx8 ;_RadUntergraphB.png]]

d) Erstelle aus einem Rad den Komplementärgraph

[[Bild:Ghx8 ;_KomplA.png]]