📂Graph Theory

Graphs and Networks in Mathematics

Definitions ¹

1. A set comprising vertices and lines connecting vertices is called a graph or a network. Let’s denote the set of vertices as $V$ and the set of lines as $E$.
2. Elements of $V(G) := V$ are called vertices or nodes of $G$.
3. Elements of $E(G) := E$ are called edges or links of $G$.
4. An edge that connects to the same vertex is called a loop.
5. If two vertices are connected by an edge, they are said to be adjacent.
6. A graph with directed edges is called a digraph.
7. A graph with a finite number of vertices, with only one edge connecting two vertices, no loops, and not being a digraph, is called a simple graph.

Explanation

Although not always, there is a tendency to prefer the term graph in pure mathematics and network in applied mathematics, even though the concepts are the same. However, whether one or the other, there are synonyms, and each term has significant influence in its field, so they are not usually used interchangeably.

1. Generally, a graph is as freely shaped as illustrated above.
2. The black circles represent each vertex, which do not embody the concept of location. In pure graph theory, the order of a graph is usually referred to the cardinality $n = |V(G)|$ of the vertex set. The order of the above graph is $5$.
3. The edges connecting vertices similarly only represent their relationships without embodying shape or length concepts. Note that Edge is correctly pronounced [에지] rather than [엗지] as often intuitively thought by Koreans. In pure graph theory, the size of a graph is usually referred to the cardinality $m = |E(G)|$ of the edge set. The size of the above graph is $8$. However, in applied network theory, size often refers to the graph’s order $|V(G)|$. This distinction must be made according to the context of the field.
4. The vertex at the top left has an edge connecting to itself, which is why it is called a loop.
5. Being adjacent means to be connected by an edge, emphasizing the relationship rather than any visible distance. If two vertices $u, v$ are adjacent, it is represented as $u \sim v$, and the set of vertices adjacent to vertex $v \in V(G)$ in graph $G$ is represented as the neighborhood $v$ like $N_{G} (v)$.
6. A digraph, as shown above, is a graph with directional edges. In a digraph, edges are sometimes called arcs. An edge going from vertex $u$ to $v$ is denoted as $u \to v$, with $u$ called the tail and $v$ called the head.
7. The term simple graph might sound complicated, but simply put, it refers to a clean graph like the above picture without loops, multi-edges, or directions. Generally, graph theory tends to focus on such simple structures.

Complex Definitions

These definitions, while making the concept of graphs easier to understand, somewhat lack rigor. Thus, the following more complex definitions are introduced. The concepts are essentially the same as those simply defined above, so there should not be much difficulty in understanding them if one is familiar with mathematical expressions.

1. $G := \left( V, \sim \right)$ is called a graph or a network with respect to a set $V \ne \emptyset$ and a binary relation $\sim \subset V^2$.
2. Elements of $V(G) := V$ are called vertices or nodes of $G$.
3. Elements of $E(G) := \sim$ are called edges or links of $G$.
4. For $v \in V(G)$, $(v,v) \in E(G)$ is called a loop.
5. If for $v_{1} , v_{2} \in V(G)$, $(v_{1} , v_{2} ) \in E(G)$ is true, then $v_{1}$ and $v_{2}$ are said to be adjacent.
6. If $\sim$ is not a symmetric relation, it’s called a digraph.
7. For a finite set $V$ with a symmetric relation $\sim \subset \left\{ (v_{1} , v_{2} ) \in V^2 \mid v_{1} \ne v_{2} \right\}$ acting as edges and having only one edge connecting two vertices, the graph is called a simple graph.