BSIT Survival Kit

Introduction to Graphs

What Is a Graph?

A graph is a structure made of vertices (nodes) connected by edges (links). Graphs model relationships in almost every field: social networks, transportation, circuits, scheduling, and more.

Types of Graphs

Type	Description
Simple Graph	No multiple edges between the same pair; no self-loops.
Multigraph	Allows multiple edges between the same pair of vertices.
Directed Graph (Digraph)	Edges have direction (arrows); relation goes one way.
Undirected Graph	Edges have no direction; relation is two-way.
Connected Graph	There is a path between any two vertices.
Disconnected Graph	At least one pair of vertices has no path between them.
Weighted Graph	Edges are assigned numerical values.

Graph Terminology

Term	Definition
Vertex	A node or point in the graph.
Edge	A connection between two vertices.
Adjacent	Two vertices connected by an edge.
Degree (deg(v))	Number of edges incident on vertex v.
In-degree	Number of directed edges arriving at a vertex.
Out-degree	Number of directed edges leaving a vertex.
Loop	An edge that connects a vertex to itself. Contributes 2 to degree.
Path	A sequence of vertices connected by edges.
Simple Path	A path with no repeated vertices.
Circuit	A path that starts and ends at the same vertex.

Note: degree = in-degree + out-degree (for directed graphs)

The Handshaking Theorem

For any undirected graph G = (V, E) with m edges:

Sum of all deg(v) = 2m

The sum of all vertex degrees equals twice the number of edges.

Corollary: An undirected graph always has an even number of vertices with odd degree.

Example: A graph with 10 vertices each of degree 6: Sum of degrees = 6 × 10 = 60 = 2m → m = 30 edges.

Representing Graphs

Adjacency Matrix

An n × n matrix where entry (i, j) = 1 if there is an edge from vertex i to vertex j, and 0 otherwise.

For undirected graphs, the matrix is symmetric.

Adjacency List

Each vertex stores a list of its neighbors. More space-efficient for sparse graphs.

Trees

A tree is a connected, acyclic graph — it has no simple circuits.

Properties:

A tree with n vertices has exactly n − 1 edges.
There is exactly one path between any two vertices.

Types of Trees

Type	Description
General Tree	Each vertex can have any number of children.
Rooted Tree	A directed tree with exactly one root (in-degree 0).
External Node (Leaf)	A vertex with out-degree 0 (no children).
Internal Node	A vertex with out-degree ≥ 1 (has at least one child).

Real-World Applications of Graphs

Social Networks: Vertices = people; edges = connections/friendships.
Transportation Networks: Vertices = stops/locations; edges = routes. (Used in GPS mapping.)
Network Security: Vertices = IP addresses; edges = data packets.
Compilers: Used for data flow analysis and code optimization.
Robot Planning: Vertices = robot states; edges = transitions between states.

Exercises — Introduction to Graphs

ProPro activity

ProReviewer — locked

Drills, code labs, and full solutions.

Unlock →