Neural Sync Active

Graph Fundamentals

Registry Synced

Graph Fundamentals

1049 words

5 min read

Reading compass

Now · 🎯 Learning Objectives

Graph Fundamentals

🎯 Learning Objectives

By the end of this topic, you will be able to:

Define a graph and its components (vertices, edges)
Distinguish between directed and undirected graphs
Represent graphs using adjacency matrices and adjacency lists
Compute the degree (in-degree/out-degree) of vertices
Identify special graphs: complete, simple, bipartite

📋 Prerequisites

Sets — sets of vertices and edges
Basic matrix multiplication for adjacency matrix operations

📖 Core Content

18.1 Intuition: Modeling Relationships

A graph is a mathematical structure for modeling pairwise relationships. Think of a social network: people are vertices (nodes), friendships are edges (connections). Graphs are everywhere:

Social networks (Facebook friends)
Road maps (cities connected by roads)
The internet (web pages linked by URLs)
Dependency management (packages depend on other packages)

💡 Why this matters: Graph algorithms power Google Maps (shortest path), Facebook's friend suggestions, package managers (dependency resolution), and recommendation systems.

18.2 Formal Definition

A graph

G = (V, E)

consists of:

$V$ : a set of vertices (nodes)
$E$ : a set of edges (pairs of vertices)

18.2.1 Types of Graphs

(Diagram)

Type	Description	Edge Notation
Undirected	Edges have no direction	$(u,v) = (v,u)$
Directed	Edges have a direction	$u \to v$
Simple	No loops, no multiple edges	Standard
Complete $K_n$	Every pair of vertices connected	$n(n-1)/2$ edges
Bipartite	Vertices split into 2 sets, edges only between sets

18.3 Graph Representations

18.3.1 Adjacency Matrix

|V| \times |V|

matrix

A

where:

A[i][j] = \begin{cases} 1 & \text{if edge } (i, j) \in E \\ 0 & \text{otherwise} \end{cases}

For undirected graphs:

A

is symmetric. For weighted graphs:

A[i][j] =

weight (not just 0/1). Example: Graph with vertices

\{1,2,3\}

and edges

\{(1,2), (2,3), (3,1)\}

A = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{bmatrix}

18.3.2 Adjacency List

For each vertex, store a list of its neighbors. Example (same graph):


pseudo
1 → [2, 3]
2 → [1, 3]
3 → [1, 2]

Representation	Memory	Edge Lookup	Neighbor Iteration
Matrix	$O(V^2)$	$O(1)$	$O(V)$
List	$O(V + E)$	$O(degree)$	$O(degree)$

18.4 Degree of Vertices

	Definition	Notation
Degree (undirected)	Number of edges incident to vertex	$\deg(v)$
In-degree (directed)	Number of edges entering $v$	$\deg^-(v)$ or $\text{in}(v)$
Out-degree (directed)	Number of edges leaving $v$	$\deg^+(v)$ or $\text{out}(v)$

Handshaking Lemma: In any undirected graph,

\sum_{v \in V} \deg(v) = 2|E|

. In a directed graph,

\sum \deg^-(v) = \sum \deg^+(v) = |E|

18.5 Special Graphs

Graph	Definition	#Edges	Example
Complete $K_n$	All $n(n-1)/2$ possible edges	$n(n-1)/2$	$K_5$ has 10 edges
Cycle $C_n$	$n$ vertices in a cycle	$n$	$C_4$ is a square
Path $P_n$	$n$ vertices in a line	$n-1$
Bipartite $K_{m,n}$	Complete bipartite	$m \cdot n$	$K_{3,3}$

18.6 Worked Examples

Example 1: Draw the graph

G = (V, E)

with

V = \{1,2,3,4\}

and

E = \{(1,2), (2,3), (3,4), (4,1), (1,3)\}

. Write its adjacency matrix.

A = \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{bmatrix}

Example 2: For a directed graph with edges

1 \to 2

2 \to 3

3 \to 1

1 \to 3

, find in-degrees and out-degrees.

Vertex	In-degree	Out-degree
1	1 (from 3)	2 (to 2, 3)
2	1 (from 1)	1 (to 3)
3	2 (from 1, 2)	1 (to 1)

Verify:

\sum \text{in} = \sum \text{out} = 4 = |E|

✓

📐 Key Formulas — Summary Table

Concept	Formula	Notes
Complete graph edges	$n(n-1)/2$	$K_n$
Bipartite edges	$m \cdot n$	$K_{m,n}$
Handshaking (undirected)	$\sum \deg(v) = 2	E
Handshaking (directed)	$\sum \text{in}(v) = \sum \text{out}(v) =	E
Adjacency matrix size	$V \times V$
Adjacency list memory	$O(V+E)$

⚠️ Common Pitfalls

Pitfall 1: Confusing Directed and Undirected Edge Notation

In directed:

(u,v)

means

u \to v

, not

v \to u

. In undirected:

(u,v) = (v,u)

Pitfall 2: Forgetting Symmetry in Undirected Adjacency Matrix

Undirected graphs have symmetric adjacency matrices:

A[i][j] = A[j][i]

Pitfall 3: Degree Counting

In directed graphs, the total degree concept doesn't apply directly — we use in-degree and out-degree separately.

📝 Practice Questions

Q1: How many edges does $K_6$ have?

$6(5)/2 = 15$

$\boxed{15}$ Q2: Draw the adjacency matrix for a directed graph with $1 \to 2$ , $2 \to 3$ , $3 \to 1$ .

> A = \begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix} >

> \boxed{\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}} >

Q3: In an undirected graph with sum of degrees = 24, how many edges?

$2|E| = 24 \implies |E| = 12$

$\boxed{12}$ Q4: List the adjacency list for $K_3$ .

$1 \to [2,3]$ , $2 \to [1,3]$ , $3 \to [1,2]$

$\boxed{1:[2,3], 2:[1,3], 3:[1,2]}$ Q5: Can a simple graph have a vertex of degree 0?

Yes — an isolated vertex.

$\boxed{\text{Yes}}$ Q6: What is the sum of in-degrees in any directed graph with 10 edges?

$10$

$\boxed{10}$ Q7: Draw $C_4$ and give its adjacency matrix.

> A = \begin{bmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{bmatrix} >

$\boxed{\text{Cycle graph with 4 vertices}}$ Q8: How many vertices does $K_{3,4}$ have? How many edges?

Vertices: $3+4 = 7$ , Edges: $3\cdot4 = 12$

$\boxed{7 \text{ vertices, } 12 \text{ edges}}$

🔗 Cross-References

Next topic: Graph Traversal — BFS, DFS
Related: DAGs & Topological Sort
Across courses: BSCS1001 Computational Thinking (graph algorithms); BSMA1003 Maths 2 (graph theory in linear algebra) Join Discord Previous9.3 Integration TechniquesNext10.2 Graph Traversal (BFS/DFS)