5.1 Network in Graph Theory
Basic Concepts of Graph Theory
A graph is a set of dynamic or static structures consisting of dots called vertices connected by lines called edges.
- Vertices / Nodes ($V$): Points or dots representing entities. $d(v)$ represents the degree of vertex $v$.
- Edges ($E$): Lines or arcs connecting pairs of vertices.
- Graph representation: $G = (V, E)$
Degree of a Graph
The degree of a vertex is the number of edges connected to that vertex. The sum of degrees for all vertices in a graph is always equal to twice the total number of edges:
$$\sum d(v) = 2E$$
Types of Graphs
- Simple Graph: An unweighted, undirected graph without loops or multiple edges.
- Multiple Edges: Two or more edges connecting the same pair of vertices.
- Loop: An edge that connects a vertex to itself. A loop adds 2 to the degree of that vertex.
- Directed Graph: A graph where each edge has a specified direction (indicated by arrows).
- In-degree ($d_{in}(v)$): Number of edges pointing into vertex $v$.
- Out-degree ($d_{out}(v)$): Number of edges pointing away from vertex $v$.
- Undirected Graph: A graph without specific directions on its edges.
- Weighted Graph: A graph where each edge is assigned a numerical value (weight, such as distance, cost, or time).
- Unweighted Graph: A graph where edges carry no numerical weights.
Subgraphs and Trees
Subgraph
A subgraph is a part of a graph or the whole graph itself. A graph $G_1 = (V_1, E_1)$ is a subgraph of $G = (V, E)$ if $V_1 \subseteq V$ and $E_1 \subseteq E$.
Tree
A tree is a connected subgraph with the following properties:
- It contains no loops or multiple edges.
- All vertices are connected.
- For a tree with $V$ vertices, the number of edges $E$ is always $V - 1$:
$$E = V - 1$$
- There is exactly one unique path between any pair of vertices.
Spanning Tree
A tree that connects all vertices of a connected graph. A minimum spanning tree is a spanning tree with the minimum total weight among all possible spanning trees.