Übung Grundbegriffe der Graphentheorie 1

Aus ProgrammingWiki

Archivierte Version vom 2015-11-02T20:11:43+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Datenstrukturen für Graphen
- 1.1 Aufgabe
- 1.2 Hilfestellung
2 Grundbegriffe

Datenstrukturen für Graphen

Gegeben ist folgendes IGraph Interface mit einer Hilfsklasse Edge zur einfacheren Behandlung von Kanten

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;
	}
}

Aufgabe

Erstelle 2 Klassen die das IGraph Interface implementieren
1. als Adjazenzmatrix
2. als Adjazenzliste
Analysiere empirisch die Effizienz dieser beiden Datenstrukturen hinsichtlich
1. Speicherbedarf
2. Ermittlung des Knotengrades
3. Prüfung auf Adjazenz zweier Knoten

Hilfestellung

Es wird ein Graph-Generator bereitgestellt, der das IGraph Interface benutzt um zufällige Graphen zu erzeugen
Mit generate werden dem Graph g eine entsprechende Menge von Knoten (cntVertex) und Kanten (cntEdges) zur Initialisierung übergeben
Die richtige Umsetzung der Speicherung wird mit den Funktionen getVertices und getEdges automatisch geprüft

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;
	}
}

Deine implementierte Klasse YourGraph könnte also folgendermaßen mit einem Zufallsgraphen getestet werden

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
}

Grundbegriffe

Aufgabe - Zuordnung

Knoten	Kantenzug	geschlossener Kantenzug	einfacher Weg	Weg	einfacher Kreis	Kreis
{A,B,C}	Details nein	Details nein	Details ja	Details ja	Details nein	Details nein
{M,G,H,M}	Details nein	Details nein	Details nein	Details nein	Details ja	Details ja
{L,M,G,H,M,L}	Details nein	Details ja	Details nein	Details nein	Details nein	Details nein
{Q,O,N,P,Q,M}	Details nein	Details nein	Details nein	Details ja	Details nein	Details nein
{G,E,D,G,F,D,G,E}	Details ja	Details nein	Details nein	Details nein	Details nein	Details nein
{L,H,G,E,D,G,M,L}	Details nein	Details nein	Details nein	Details nein	Details nein	Details ja

Aufgabe - Strukturelle Umformungen

a) Finde mindestens zwei Artikulationen.

Konten {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

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

Übung Grundbegriffe der Graphentheorie 1

Inhaltsverzeichnis

Datenstrukturen für Graphen

Aufgabe

Hilfestellung

Grundbegriffe

Aufgabe - Zuordnung

Aufgabe - Strukturelle Umformungen

Aufgabe - Teilgraphen

Aufgabe

Suche