0% completed
A graph is a data structure used to represent relationships or connections between objects. A graph consists of two main parts:
- Vertices (Nodes): Represent the individual objects.
- Edges (Links): Represent the connections between those objects.
A graph is often denoted as G(V, E) where:
Vis the set of vertices.Eis the set of edges connecting pairs of vertices.
Example
Consider a graph with five nodes A, B, C, D, and E, and the following connections:
This graph forms a network of connections, where you can traverse from one node to another based on the defined edges.
As the graph grows larger, it can become highly interconnected, forming complex relationships and paths.
Why Are Graphs Important?
Graphs are a fundamental and flexible data structure used in many real-world scenarios—especially those involving networks, hierarchies, and dependencies.
They are ideal for modeling things like:
- Routes and maps
- User connections in social media
- Communication networks
- Dependencies in task scheduling
- Web page links and recommendations
Common Graph Terminologies
Understanding baseline graph terminologies is essential for understanding complex graph concepts. Like the other concepts, graph theory has some baseline terminologies. These terminologies are the most commonly used jargon in graphs. Understanding these jargons empower you better understand and communicate the graph concept.
Here are some of the most commonly used graph terminologies:
1. Node in Graph
A "node" (also known as a "vertex") is a fundamental building block of a graph. A graph is a mathematical representation of a set of vertices (nodes) and the connections (edges) between those objects. The links between nodes can be either directed or undirected, depending on whether the relationship has a specific direction. In the following figure, A, B, C, D, and E are the nodes in the graph, also known as vertices.
2. Adjacent Nodes
Two nodes are said to be adjacent if an edge is connected directly. The set of nodes adjacent to a particular node is known as its neighborhood. As in the figure 2, the nodes A and B are adjacent.
3. Digraph
A digraph, short for directed graph, is a type of graph in which edges have a direction or are represented by arrows. Each edge connects two vertices (nodes), but the direction of the edge indicates a one-way relationship between the nodes. In other words, if there is an edge from vertex A to vertex B, you can only travel from A to B along that edge.
4. Loop in Graph
A "loop" in a graph refers to an edge that connects a vertex to itself. In other words, it is an edge that starts and ends at the same vertex. Loops can exist in both directed and undirected graphs.
In an undirected graph, a loop is simply an edge that connects a vertex to itself. It forms a cycle of length 1. For example, if you have a graph with a single vertex v, and there is an edge from v to itself, then it forms a loop.
In a directed graph, a loop is an arc (directed edge) that starts and ends at the same vertex. It forms a directed cycle of length 1. For example, if you have a graph with a single vertex v, and there is a directed edge from v to itself, then it forms a loop.
5. Degree of a Node
The degree of a node is the number of edges connected to it.
The degree of a node in an undirected graph is defined as the number of edges connected to that node.
- As in the below figure, the degree of Node A is two because it has two neighbors.
- The degree of Node C is 4, as it has a total 4 edges that are connected.
- C is connected to B ? 1 edge
- C is connected to E ? 1 edge
- C has a self-loop ? 1 edge (counts as 2 in undirected graphs)
- Total degree of C = 1 + 1 + 2 = 4
In a directed graph, there are two degrees:
-
The in-degree (number of incoming edges)
-
The out-degree (number of outgoing edges).
In the below graph, the degree of node A is two because two edges are outgoing, and the degree of node C is 1.
6. Path
A sequence of vertices in which each consecutive pair of vertices is connected by an edge. For example in the above figure, there is a path from vertex A to B.
7. Cycle
A path in which the first and last vertices are the same, forming a closed loop. The following figure shows a route from A to B, B to D, D to C, and C to A. So here, the cycle completes because we start from vertex A and end again at A vertex.
Table of Contents
Example
Why Are Graphs Important?
Common Graph Terminologies
- Node in Graph
- Adjacent Nodes
- Digraph
- Loop in Graph
- Degree of a Node
- Path
- Cycle