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:

package example.graph;

/**
* 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:

package example.graph;

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