Ü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;
		int[] v = new int[cntVertex];
		for(int i = 0; i < cntVertex; i++)
			v[i] = i;
		HashSet<Edge> edges = new HashSet<Edge>();
		while (edges.size() < cntEdges){
			int i1 = r.nextInt(cntVertex);
			int i2 = r.nextInt(cntVertex);
			while (i1 == i2)
				i2 = r.nextInt(cntVertex);
			Edge e = new Edge(i1, i2);
			if (!edges.contains(e))
				edges.add(e);
		}
		try{
			Edge[] ed = cntEdges > 0 ? edges.toArray(new Edge[cntEdges]) : null;
			g.setGraph(v, ed);
			int[] gVert = g.getVertices();
			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();
			if ((gEd == null && ed != null) || (gEd != null && ed == null)){
				System.out.println("Different edge definition");
				return false;
			}
			if (ed != null){
				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){
			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]]
</popup>

=Grundbegriffe=

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

==Aufgabe==

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

==Aufgabe==

a) Finde mindestens zwei Artikulationen.

b) Finde mindestens zwei Brücken.

c) Führe eine Kontraktion mit K durch.

==Aufgabe==

a) Finde zwei Untergraphen

b) Skizziere aus einem Untergraphen verschiedene Teilgraphen

c) Erstelle einen induzierten Teilgraphen aus einem Rad

d) Erstelle einen spannenden Teilgraphen aus einem Rad


==Aufgabe==

Stell den Punkt I auf G um (gedanklich). Führe folgende Operationen durch:

a) Vereinigung

b) Durschnitt

c) Differenz

d) Erstelle aus einem Rad den Komplementärgraph