Graph Theory: Introduction and Basic Terminology of Graphs
Definition
A graph is a mathematical structure represented as , where:
- is a non-empty set of vertices or nodes
- is a set of edges that connect pairs of vertices
If the edges have a direction, the graph is called a directed graph or digraph. If the edges do not have direction, it is called an undirected graph.
In simple terms, a graph is a collection of points and lines joining some of those points. The formal definition allows us to study many kinds of networks using the same mathematical language.
Example:
If and , then the graph has three vertices and two edges.
Main Content
1. Vertices, Edges, and the Structure of a Graph
Vertices
- are the basic objects of a graph. They may represent people, computers, cities, tasks, or any other entities in a system.
Edges
- are the connections between vertices. They indicate a relationship, such as friendship, communication, travel route, or dependency.
A graph is built from these two components:
- A vertex can stand alone without any edge.
- An edge always connects two vertices in an undirected graph, or one vertex to another in a directed graph.
Example:
Consider three cities: Delhi, Mumbai, and Chennai.
- Cities = vertices
- Roads between them = edges
A simple representation can be:
Delhi ----- Mumbai
\ /
\ /
Chennai
In this figure, the cities are vertices and the roads are edges.
Graphs may also have:
Loops
- : an edge that starts and ends at the same vertex
Multiple edges
- : more than one edge between the same pair of vertices
Weights
- : numerical values associated with edges, such as distance or cost
These features help graphs model real-life problems more accurately.
2. Types of Graphs
Undirected graph
- : Edges have no direction. If vertex is connected to , then is also connected to . Example: friendship on social media where the relationship is mutual.
Directed graph (digraph)
- : Edges have a direction. If there is an edge from to , it does not necessarily mean there is an edge from to . Example: one-way roads or follower relationships on social platforms.
Other important graph types include:
Simple graph
- : No loops and no multiple edges.
Multigraph
- : Multiple edges between the same pair of vertices may exist.
Weighted graph
- : Edges carry values such as distance, time, or cost.
Complete graph
- : Every pair of distinct vertices is connected by an edge.
Null graph
- : A graph with vertices but no edges.
Example of directed graph:
A → B → C
↑ ↓
└───────── D
This means movement or relation follows the arrow direction.
3. Basic Terminology Used in Graph Theory
Adjacent vertices
- : Two vertices are adjacent if they are connected by an edge.
Incident edge
- : An edge is incident on the vertices it connects.
Degree of a vertex
- : The number of edges incident on a vertex in an undirected graph. A loop contributes twice to the degree.
In-degree and out-degree
- : In a directed graph, in-degree is the number of incoming edges and out-degree is the number of outgoing edges.
Path
- : A sequence of edges connecting a sequence of vertices.
Length of a path
- : The number of edges in the path.
Cycle
- : A path that starts and ends at the same vertex.
Connected graph
- : A graph in which there is a path between every pair of vertices.
Disconnected graph
- : A graph that is not connected.
Subgraph
- : A graph formed from a subset of vertices and edges of a larger graph.
Example:
Suppose the graph has vertices and edges .
- is adjacent to and
- Degree of = 2
- A path from to is
- If you travel from to to , that forms a cycle only if the graph allows such repeated edges appropriately
These terms are the language of graph theory and are essential for describing graph properties precisely.
Working / Process
1. Identify the real-world problem or relationship
- Determine what the vertices and edges should represent.
- Example: In a railway network, cities are vertices and railway lines are edges.
2. Construct the graph model
- Choose whether the graph is directed or undirected.
- Decide whether weights, loops, or multiple edges are needed.
- Draw or represent the graph using a diagram, adjacency list, or adjacency matrix.
3. Analyze the graph using terminology and properties
- Check adjacency, degree, paths, cycles, and connectivity.
- Use graph-theoretic tools to solve the problem, such as finding shortest paths, connected components, or network routes.
Example workflow:
- Problem: Find the shortest route between two cities
- Model: Weighted graph
- Process: Represent cities as vertices and roads as weighted edges
- Analysis: Apply graph algorithms like shortest path methods
Advantages / Applications
- Graph theory provides a clear and powerful way to model complex relationships in a simple mathematical form.
- It is widely used in computer science for network design, data structures, routing, databases, and algorithm development.
- It is useful in real-world systems such as social networks, transportation systems, electrical circuits, communication networks, biological networks, and project scheduling.
Additional applications include:
Shortest path problems
- in GPS and navigation systems
Network flow analysis
- in logistics and communication
Scheduling and dependency management
- in operating systems and project planning
Social network analysis
- to study relationships and influence
Molecular chemistry
- to represent bonds between atoms
Graph theory is especially valuable because it helps identify:
- Efficient routes
- Bottlenecks
- Connectivity issues
- Central or important vertices
- Structural patterns in data
Summary
Graph theory studies vertices and edges as a way to represent relationships in a system. It introduces essential terms such as degree, path, cycle, adjacency, and connectivity, which help in understanding and analyzing networks. This topic forms the foundation for many practical applications in mathematics, computer science, and engineering.