Übung Grundbegriffe der Graphentheorie 1

Aus ProgrammingWiki

Archivierte Version vom 2015-10-28T12:17:22+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;
		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;
	}
}

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

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

Übung Grundbegriffe der Graphentheorie 1

Inhaltsverzeichnis

Datenstrukturen für Graphen

Aufgabe

Hilfestellung

Grundbegriffe

Aufgabe

Aufgabe

Aufgabe

Aufgabe

Suche