\\n\\n

Graph Theory Basics and Representation

\\n\\n

1. Concepts and Introduction

\\n\\n

Graph Theory is a branch of discrete mathematics that studies graphs.

\\n\\n

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

\\n\\n

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

\\n\\n

\\n\\n

Classification of Graphs: Unweighted and Weighted Graphs. If the edges connecting nodes have numerical values associated with them, it is a weighted graph; otherwise, it is an unweighted graph.

\\n\\n

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 naturally from j to i as well), then i and j are said to be connected. If G is a directed graph, then all edges in the path connecting i and j must be in the same direction. If any two vertices in the graph are connected, the graph is called a connected graph. If this graph is a directed graph, it is called a strongly connected graph (Note: paths must exist in both directions). The connectivity of a graph is a fundamental property.

\\n\\n

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

\\n\\n

Self-loop: An edge whose start and end point is the same vertex.

\\n\\n

Parallel Edges: Multiple edges exist between two vertices.

\\n\\n

2. Application Description

\\n\\n

Graphs can be used to model many types of relationships and processes in physical, biological, social, and information systems. Many practical problems can be represented using graphs. Therefore, graph theory has become a powerful mathematical tool in numerous fields such as operations research, cybernetics, 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 relationships between attributes (e.g., names) are associated in the form of nodes and/or edges.

\\n\\n

3. Graph Representation Forms

\\n\\n

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

\\n\\n

\\n\\n

Adjacency List: Only expresses the information of vertices connected to a vertex.

\\n\\n

\\n\\n

Adjacency lists are suitable for representing sparse graphs.

\\n\\n

Adjacency matrices are suitable for representing dense graphs.

\\n\\n

Java Example Code

\\n\\n

Source Code Package Download: Download

\\n\\n

(1) Adjacency Matrix

\\n\\n

src//graph/DenseGraph.java File Code:

\\n\\n

package .graph;\\n\\n/**\\n * Adjacency Matrix\\n */\\npublic class DenseGraph {\\n    // number of nodes\\n    private int n;\\n    // number of edges\\n    private int m;\\n    // whether it is a directed graph\\n    private boolean directed;\\n    // specific data of the graph\\n    private boolean[][] g;\\n\\n    // Constructor\\n    public DenseGraph(int n, boolean directed) {\\n        assert n >= 0;\\n        this.n = n;\\n        this.m = 0;\\n        this.directed = directed;\\n        // ginitialize to n*nboolean matrix, each gare all false, indicates no edges\\n        // falsedefault value for boolean variable\\n        g = new boolean;\\n    }\\n\\n    // return the number of nodes\\n    public int V() { return n; }\\n\\n    // return the number of edges\\n    public int E() { return m; }\\n\\n    // add an edge to the graph\\n    public void addEdge(int v, int w) {\\n        assert v >= 0 && v = 0 && w = 0 && v = 0 && w < n;\\n        return g;\\n    }\\n}

\\n\\n

(2) Adjacency List

\\n\\n

src//graph/SparseGraph.java File Code:

\\n\\n

package .graph;\\n\\nimport java.util.Vector;\\n\\n/**\\n * Adjacency List\\n */\\npublic class SparseGraph {\\n    // number of nodes\\n    private int n;\\n    // number of edges\\n    private int m;\\n    // whether it is a directed graph\\n    private boolean directed;\\n    // specific data of the graph\\n    private Vector<Integer>[] g;\\n\\n    // Constructor\\n    public SparseGraph(int n, boolean directed) {\\n        assert n >= 0;\\n        this.n = n;\\n        this.m = 0;\\n        this.directed = directed;\\n        // ginitialize to n empty vectors, denotes each gare all empty, which means no edges\\n        g = (Vector<Integer>[]) new Vector;\\n        for (int i = 0; i < n; i++)\\n            g = new Vector<Integer>();\\n    }\\n\\n    // return the number of nodes\\n    public int V() { return n; }\\n\\n    // return the number of edges\\n    public int E() { return m; }\\n\\n    // add an edge to the graph\\n    public void addEdge(int v, int w) {\\n        assert v >= 0 && v = 0 && w = 0 && v = 0 && w < n;\\n        for (int i = 0; i < g.size(); i++)\\n            if (g.elementAt(i) == w)\\n                return true;\\n        return false;\\n    }\\n}