グラフ理論の基礎と表現

一、概念とその紹介

グラフ理論（Graph Theory）は離散数学の一分野であり、グラフ（Graph）を研究する学問です。

グラフは、オブジェクト間のペア関係をモデル化するための数学的構造であり、「ノード」または「頂点」（Vertex）と、これらの頂点を接続する「辺」（Edge）で構成されます。

注意すべき点として、グラフの頂点集合は空であってはなりませんが、辺の集合は空でも構いません。グラフは無向の場合があります。これは、グラフ内の辺が頂点を接続する際に方向を区別する必要がないことを意味します。そうでない場合、グラフは有向であると呼ばれます。下の左図は典型的な無向グラフの構造であり、右図は有向グラフに属します。この章で紹介するグラフはすべて無向グラフです。

グラフの分類：重みなしグラフと重み付きグラフ。ノードとノードを接続する辺に対応する数値があるかどうかで、あれば重み付きグラフ、なければ重みなしグラフです。

グラフの連結性：グラフ理論において、連結グラフは連結の概念に基づいています。無向グラフGにおいて、頂点iから頂点jへの経路が存在する場合（もちろんjからiへの経路も必ず存在します）、iとjは連結しているといいます。Gが有向グラフの場合、iとjを結ぶ経路のすべての辺は同一方向でなければなりません。グラフ内の任意の2点が連結している場合、そのグラフは連結グラフと呼ばれます。このグラフが有向グラフである場合、強連結グラフと呼ばれます（注意：双方向に経路が必要です）。グラフの連結性はグラフの基本的な性質です。

完全グラフ：完全グラフは単純な無向グラフであり、その中の異なる頂点の各ペアの間にちょうど1本の辺が接続されています。

自己ループ辺：辺の始点と終点が同じ点であること。

平行辺：2つの頂点の間に複数の辺が接続されていること。

二、適用説明

グラフは、物理学、生物学、社会学、情報システムにおいて、多くの種類の関係やプロセスをモデル化するために使用でき、多くの実際の問題はグラフで表現できます。したがって、グラフ理論は、オペレーションズリサーチ、サイバネティクス、情報理論、ネットワーク理論、ゲーム理論、物理学、化学、生物学、社会科学、言語学、コンピュータサイエンスなど、多くの分野における強力な数学的ツールとなっています。現実世界のシステムへの応用を強調する場合、ネットワークはグラフとして定義されることがあり、そこでは属性（例えば名前）間の関係がノードまたはエッジ（あるいはその両方）の形で関連付けられます。

三、グラフの表現形式

隣接行列：1 は接続されていることを表し、0 は接続されていないことを表します。

隣接リスト：頂点に接続されている頂点の情報のみを表現します。

隣接リストは疎グラフ（Sparse Graph）の表現に適しています。

隣接行列は密グラフ（Dense Graph）の表現に適しています。

Java サンプルコード

ソースコードパッケージのダウンロード：Download

(1) 隣接行列

src/サンプル/graph/DenseGraph.java ファイルのコード：

package サンプル.graph;

/**
* 隣接行列
 */
public class DenseGraph {
    // ノード数
    private int n;
    // 辺数
    private int m;
    // 有向グラフかどうか
    private boolean directed;
    // グラフの具体的なデータ
    private boolean[][] g;

    // コンストラクタ
    public DenseGraph( int n , boolean directed ){
        assert n >= 0;
        this.n = n;
        this.m = 0;
        this.directed = directed;
        // gはn*nのブール行列として初期化され、各g[i][j]はfalseであり、辺が存在しないことを示します
        // falseはboolean型変数のデフォルト値です
        g = new boolean[n][n];
    }
    // ノード数を返す
    public int V(){ return n;}
    // 辺数を返す
    public int E(){ return m;}

    // グラフに辺を1つ追加する
    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] = true;
        if( !directed )
            g[w][v] = true;
        m ++;
    }

    // グラフにvからwへの辺があるかどうかを検証する
    boolean hasEdge( int v , int w ){
        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;
        return g[v][w];
    }
}

（2）隣接リスト

src/サンプル/graph/SparseGraph.java ファイルのコード：

package サンプル.graph;

import java.util.Vector;

/**
* 隣接リスト
 */
public class SparseGraph {
    // ノード数
    private int n;
    // 辺数
    private int m;
    // 有向グラフかどうか
    private boolean directed;
    // グラフの具体的なデータ
    private Vector<Integer>[] g;

    // コンストラクタ
    public SparseGraph( int n , boolean directed ){
        assert n >= 0;
        this.n = n;
        this.m = 0;  
        this.directed = directed;
        // gはn個の空のvectorとして初期化され、各g[i]が空であること、すなわち辺が存在しないことを示します
        g = (Vector<Integer>[])new Vector[n];
        for(int i = 0 ; i < n ; i ++)
            g[i] = new Vector<Integer>();
    }
    // ノード数を返す
    public int V(){ return n;}
    // 辺数を返す
    public int E(){ return m;}
    // グラフに辺を1つ追加する
    public void addEdge( int v, int w ){
        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;
        g[v].add(w);
        if( v != w && !directed )
            g[w].add(v);
        m ++;
    }

    // グラフにvからwへの辺があるかどうかを検証する
    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;
    }
}
その他の拡張