Übung Grundbegriffe der Graphentheorie 1
Aus ProgrammingWiki
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==
{| 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.
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==
a) Finde zwei Untergraphen
[[Bild:Ghx8 ;_RadUntergraph.png]]
[[Bild:Ghx8 ;_RadUntergraphB.png]]
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