Grundlagen der Graphentheorie und Darstellung
1. Konzept und Einführung
Die Graphentheorie ist ein Teilgebiet der diskreten Mathematik, einer Disziplin, die Graphen untersucht.
Ein Graph ist eine mathematische Struktur zur Modellierung paarweiser Beziehungen zwischen Objekten, bestehend aus "Knoten" oder "Ecken" (Vertex) und den "Kanten" (Edge), die diese Knoten verbinden.
Es ist erwähnenswert, dass die Knotenmenge eines Graphen nicht leer sein darf, die Kantenmenge jedoch leer sein kann. Ein Graph kann ungerichtet sein, was bedeutet, dass die Kanten im Graphen beim Verbinden von Knoten keine Richtung unterscheiden. Andernfalls wird der Graph als gerichtet bezeichnet. Die linke Abbildung unten ist eine typische ungerichtete Graphenstruktur, während die rechte Abbildung ein gerichteter Graph ist. Die in diesem Kapitel vorgestellten Graphen sind alle ungerichtet.

Klassifizierung von Graphen: ungewichtete Graphen und gewichtete Graphen. Ob die Kanten, die Knoten verbinden, mit numerischen Werten verknüpft sind; wenn ja, handelt es sich um einen gewichteten Graphen; andernfalls um einen ungewichteten Graphen.
Graphzusammenhang:In der Graphentheorie basiert der zusammenhängende Graph auf dem Konzept des Zusammenhangs. In einem ungerichteten Graphen G, wenn es einen Pfad gibt, der Knoten i mit Knoten j verbindet (natürlich muss es auch einen Pfad von j nach i geben), dann heißen i und j verbunden. Wenn G ein gerichteter Graph ist, müssen alle Kanten im Pfad, der i und j verbindet, in dieselbe Richtung weisen. Wenn je zwei Knoten im Graphen verbunden sind, wird der Graph als zusammenhängender Graph bezeichnet. Wenn der Graph gerichtet ist, wird er als stark zusammenhängender Graph bezeichnet (Hinweis: Pfade müssen in beide Richtungen existieren). Der Zusammenhang eines Graphen ist eine grundlegende Eigenschaft von Graphen.
Vollständiger Graph:Ein vollständiger Graph ist ein einfacher ungerichteter Graph, in dem genau eine Kante jedes Paar verschiedener Knoten verbindet.
Schleifenkante:Anfangs- und Endpunkte einer Kante sind Knoten.
Parallele Kante:Zwischen zwei Knoten existieren mehrere Kanten.
II. Hinweise zur Anwendbarkeit
Graphen können verwendet werden, um viele Arten von Beziehungen und Prozessen in physikalischen, biologischen, sozialen und Informationssystemen zu modellieren, und viele praktische Probleme können durch Graphen dargestellt werden. Daher ist die Graphentheorie zu einem leistungsstarken mathematischen Werkzeug für viele Disziplinen wie Operations Research, Kybernetik, Informationstheorie, Netzwerktheorie, Spieltheorie, Physik, Chemie, Biologie, Sozialwissenschaften, Linguistik und Informatik geworden. Wenn die Anwendung auf reale Systeme betont wird, wird ein Netzwerk manchmal als ein Graph definiert, in dem Beziehungen zwischen Attributen (wie Namen) in Form von Knoten und/oder Kanten zugeordnet sind.
3. Darstellungsformen von Graphen
Adjazenzmatrix:1 bedeutet verbunden, 0 bedeutet nicht verbunden.

Adjazenzliste:Stellt nur Informationen über mit einem Knoten verbundene Knoten dar

Adjazenzliste eignet sich zur Darstellung dünn besetzter Graphen.
Adjazenzmatrix eignet sich zur Darstellung dichter Graphen.
Java-Beispielcode
Quellcode-Paket-Download:Download
(1) Adjazenzmatrix
Code der Datei src/example/graph/DenseGraph.java:
/**
* Adjazenzmatrix
*/
public class DenseGraph {
// Knotenanzahl
private int n;
// Kantenanzahl
private int m;
// Gibt an, ob es ein gerichteter Graph ist
private boolean directed;
// Spezifische Daten des Graphen
private boolean[][] g;
// Konstruktor
public DenseGraph( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0;
this.directed = directed;
// g wird als eine n*n boolesche Matrix initialisiert, wobei jedes g[i][j] false ist, was anzeigt, dass keine Kanten vorhanden sind
// false ist der Standardwert für boolesche Variablen
g = new boolean[n][n];
}
// Gibt die Anzahl der Knoten zurück
public int V(){ return n;}
// Gibt die Anzahl der Kanten zurück
public int E(){ return m;}
// Fügt eine Kante zum Graphen hinzu
public void addEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
if( hasEdge( v , w ) )
return;
g[v][w] = wahr;
if( !directed )
g[w][v] = wahr;
m ++;
}
// Prüft, ob eine Kante von v nach w im Graphen vorhanden ist
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
return g[v][w];
}
}
(2) Adjazenzliste
Code der Datei src/example/graph/SparseGraph.java:
import java.util.Vector;
/**
* Adjazenzliste
*/
public class SparseGraph {
// Knotenanzahl
private int n;
// Kantenanzahl
private int m;
// Gibt an, ob es ein gerichteter Graph ist
private boolean directed;
// Spezifische Daten des Graphen
private Vector<Integer>[] g;
// Konstruktor
public SparseGraph( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0;
this.directed = directed;
// g wird als n leere Vektoren initialisiert, was bedeutet, dass jedes g[i] leer ist, d. h. keine Kanten.
g = (Vector<Integer>[])new Vektor[n];
for(int i = 0 ; i < n ; i ++)
g[i] = new Vector<Integer>();
}
// Gibt die Anzahl der Knoten zurück
public int V(){ return n;}
// Gibt die Anzahl der Kanten zurück
public int E(){ return m;}
// Fügt eine Kante zum Graphen hinzu
public void addEdge( int v, int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
g[v].hinzufügen(w);
if( v != w && !directed )
g[w].hinzufügen(v);
m ++;
}
// Prüft, ob eine Kante von v nach w im Graphen vorhanden ist
boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ;
assert w >= 0 && w < n ;
for( int i = 0 ; i < g[v].size() ; i ++ )
if( g[v].elementAt(i) == w )
return true;
return false;
}
}