Basics and Representation of Graph Theory

I. Concepts and Introduction

Graph Theory is a branch of discrete mathematics and is the study of graphs.

A graph is a mathematical structure used to model pairwise relations between objects, consisting of "nodes" or "vertices" and edges that connect these vertices.

It is important to note that the set of vertices in a graph cannot be empty, but the set of edges can be empty. A graph can be undirected, meaning the edges do not have a direction when connecting vertices. Otherwise, the graph is directed. The left image below is a typical undirected graph structure, while the right one is a directed graph. The graphs discussed in this section are undirected graphs.

Graph Classification: Unweighted and weighted graphs. If the edges connecting nodes have associated values, it is a weighted graph; otherwise, it is an unweighted graph.

Graph Connectivity: In graph theory, a connected graph is based on the concept of connectivity. In an undirected graph G, if there is a path connecting vertex i to vertex j (and vice versa), then i and j are connected. If G is a directed graph, all edges in the path connecting i and j must be in the same direction. If every pair of vertices in the graph is connected, the graph is called a connected graph. If this graph is directed, it is called a strongly connected graph (note: paths must exist in both directions). Graph connectivity is a fundamental property of graphs.

Complete Graph: A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.

Self-loop Edge: An edge where the start and end points are the same vertex.

Parallel Edges: Multiple edges connecting the same pair of vertices.

II. Application Description

Graphs can be used to model many types of relationships and processes in physical, biological, social, and information systems. Many real-world problems can be represented using graphs. Therefore, graph theory serves as a powerful mathematical tool in many disciplines such as operational research, control theory, information theory, network theory, game theory, physics, chemistry, biology, social sciences, linguistics, and computer science. When emphasizing its application to real-world systems, a network is sometimes defined as a graph where the relationships of attributes (such as names) are associated with nodes and/or edges.

III. Graph Representation Forms

Adjacency Matrix: 1 indicates a connection, 0 indicates no connection.

Adjacency List: Only expresses information about vertices connected to the given vertex.

Adjacency lists are suitable for sparse graphs (Sparse Graph).

Adjacency matrices are suitable for dense graphs (Dense Graph).

Java Example Code

Source Code Download: Download

(1) Adjacency Matrix

src/tutorialpro/graph/DenseGraph.java File Code:

package tutorialpro.graph;

/**
 * Adjacency Matrix
 */
public class DenseGraph {
    // Number of vertices
    private int n;
    // Number of edges
    private int m;
    // Whether the graph is directed
    private boolean directed;
    // Graph data
    private boolean[][] g;

    // Constructor
    public DenseGraph(int n, boolean directed) {
        assert n >= 0;
        this.n = n;
        this.m = 0;
        this.directed = directed;
        // Initialize g as a boolean matrix of n*n, where each g[i][j] is false, indicating no edges
        g = new boolean[n][n];
    }
    // Return the number of vertices
    public int V() { return n; }
    // Return the number of edges
    public int E() { return m; }

    // Add an edge to the graph
    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++;
    }

    // Verify if there is an edge from v to w
    boolean hasEdge(int v, int w) {
        assert v >= 0 && v < n;
        assert w >= 0 && w < n;
        return g[v][w];
    }
}

**(2) Adjacency List**

## src/tutorialpro/graph/SparseGraph.java File Code:

package tutorialpro.graph;

import java.util.Vector;

/**

• Adjacency List */ public class SparseGraph { // Number of vertices private int n; // Number of edges private int m; // Whether the graph is directed private boolean directed; // Graph data private Vector<Integer>[] g;

// Constructor
public SparseGraph(int n, boolean directed) {
    assert n >= 0;
    this.n = n;
    this.m = 0;   
    this.directed = directed;
    // Initialize g with n empty vectors, indicating that each g[i] is empty, i.e., no edges
    g = (Vector<Integer>[]) new Vector[n];
    for (int i = 0; i < n; i++)
        g[i] = new Vector<Integer>();
}
// Return the number of vertices
public int V() { return n; }
// Return the number of edges
public int E() { return m; }
// Add an edge to the graph
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++;
}

// Verify if there is an edge from v to w in the graph
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;
}

}