Noesis
3.5.1Graphs

Graph definitions — directed, undirected, weighted, unweighted, simple, multigraph

2,139 words10 min readdifficulty · medium
🇮🇳 Yeh note Hinglish mein padho →

WHAT is a graph?

WHY this abstraction? Because relationships are everywhere: friends on a social network, cities linked by roads, web pages linked by hyperlinks, tasks that depend on other tasks. A graph strips away the specifics and keeps only "who is connected to whom", so one set of algorithms (BFS, Dijkstra, ...) solves thousands of different real problems.

Figure — Graph definitions — directed, undirected, weighted, unweighted, simple, multigraph

The four independent "switches"

Think of a graph type as four on/off switches. They are independent — you can mix them freely (e.g. a directed weighted multigraph).

Switch 1 — Directed vs Undirected

WHY it matters: a Facebook friendship is mutual → undirected. A Twitter "follow" is one-way → directed. On a directed graph you can be able to go A→BA \to B but not B→AB \to A.

Switch 2 — Weighted vs Unweighted

WHY: "How many hops to my friend?" ignores weight (unweighted, BFS). "Cheapest flight route?" needs weight (Dijkstra). Treating an unweighted graph as weighted is fine — just set every weight =1= 1.

Switch 3 — Self-loops allowed?

Switch 4 — Parallel edges allowed?

WHY a multigraph? Two cities can genuinely have two different roads between them, each with its own length. A simple graph would force you to keep only one — losing information.

HOW MANY edges can a graph have? (Derivation, not memorisation)

Simple undirected graph — max edges

Derive it from scratch — WHY:

  1. An edge is an unordered pair of distinct vertices (no self-loops → distinct; simple → at most one).
  2. So counting max edges = counting how many ways to choose 2 vertices out of nn.
  3. Number of ways to pick the first vertex: nn. The second (different): n−1n-1. That gives n(n−1)n(n-1) ordered pairs.
  4. But {u,v}\{u,v\} and {v,u}\{v,u\} are the same undirected edge → we double-counted. Divide by 2.
  5. Result: n(n−1)2\dfrac{n(n-1)}{2}. ∎

Simple directed graph — max edges

WHY: now (u,v)≠(v,u)(u,v) \ne (v,u), so we don't divide by 2. Each of nn vertices can point to each of the other n−1n-1 vertices → n(n−1)n(n-1).

Sum-of-degrees (Handshake Lemma)

Derive — WHY: when you add up degrees over all vertices, each edge {u,v}\{u,v\} is counted twice — once at uu and once at vv. So the total is exactly twice the number of edges. ∎ (Corollary: the number of odd-degree vertices is always even.)

Recall Feynman: explain to a 12-year-old

Imagine dots that are your friends, and you draw a line whenever two of them know each other. That whole drawing is a graph.

  • If "knowing" goes both ways (friends), draw a plain line — undirected.
  • If it's one-way ("I follow her, she doesn't follow me"), draw an arrow — directed.
  • If some friendships are stronger, write a number on the line — weighted.
  • Simple means: no friend is friends with themselves (no self-loop), and you never draw two lines between the same pair. If you do draw two lines (maybe two different roads between two towns), it's a multigraph. That's it — the rest of "graph theory" is just clever ways to walk along these lines.

Flashcards

What two sets define a graph G=(V,E)G=(V,E)?
VV = set of vertices (nodes), EE = set of edges connecting pairs of vertices.
Difference between a directed and an undirected edge?
Directed = ordered pair (u,v)(u,v), one-way; undirected = unordered pair {u,v}\{u,v\}, both ways.
What is a weighted graph?
A graph where each edge carries a number (cost/distance/time); unweighted treats all edges as equal (weight 1).
Define a self-loop.
An edge from a vertex to itself, (v,v)(v,v).
What are parallel edges?
Two or more edges connecting the same pair of vertices.
Define a simple graph.
A graph with no self-loops and no parallel edges (≤ 1 edge between any pair).
Define a multigraph.
A graph that allows parallel edges (and usually self-loops).
Max edges in a simple undirected graph on nn vertices?
(n2)=n(n−1)2\binom{n}{2} = \frac{n(n-1)}{2}.
Why divide by 2 for undirected max edges?
Because {u,v}={v,u}\{u,v\}=\{v,u\} — each unordered pair was counted twice in n(n−1)n(n-1).
Max edges in a simple directed graph (no self-loops)?
n(n−1)n(n-1) — no division by 2 since (u,v)≠(v,u)(u,v)\ne(v,u).
State the Handshaking Lemma.
∑vdeg⁡(v)=2m\sum_{v}\deg(v) = 2m; each edge contributes to two endpoints' degrees.
Corollary of the handshake lemma about odd degrees?
The number of vertices with odd degree is always even.
How do you model one undirected edge with directed edges?
As two arcs (u,v)(u,v) and (v,u)(v,u) — so edge count doubles.
What is KnK_n?
The complete graph: a simple graph where every pair of vertices is connected; it has n(n−1)2\frac{n(n-1)}{2} edges.
For directed graphs, what replaces degree?
In-degree (incoming arcs) and out-degree (outgoing arcs).

Connections

  • Graph representations — adjacency list vs matrix (how these definitions are stored)
  • BFS — breadth first search (shortest path on unweighted graphs)
  • Dijkstra's algorithm (shortest path on weighted, non-negative graphs)
  • Topological sort (only on directed acyclic graphs)
  • Complete graph $K_n$ and dense vs sparse graphs
  • Handshaking lemma and degree sequences
  • Trees as special graphs (connected, acyclic, m=n−1m = n-1)

Concept Map

contains

contains

connects pairs of

counted by

configured by

switch 1

switch 2

switch 3

switch 4

arc is ordered pair enables

weights enable

forbidden in

allowed in

allowed in

Graph G = V,E

Vertices V

Edges E

n = size of V and m = size of E

Four independent switches

Directed vs Undirected

Weighted vs Unweighted

Self-loops allowed

Parallel edges allowed

Topological sort

Dijkstra shortest path

Simple graph

Multigraph

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Graph ka matlab simple hai: dots aur unko jodne wali lines. Dots ko hum vertices (nodes) bolte hain aur lines ko edges. Bas itna hi base hai — baaki saare fancy words sirf yeh batate hain ki line kaisi behave karti hai. Yaad rakho formula G=(V,E)G=(V,E), jahan VV vertices ka set hai aur EE edges ka set.

Char "switches" se graph ka type decide hota hai (mnemonic DWSP). Direction: line plain hai (undirected, dono taraf chalti hai jaise Facebook friend) ya arrow wali (directed, ek taraf jaise Twitter follow). Weight: line par koi number likha hai (weighted — cost, distance) ya nahi (unweighted, sab edges barabar). Self-loop: koi vertex apne aap se juda hai kya? Parallel edges: ek hi pair ke beech do lines? Agar self-loop aur parallel dono nahi hain to graph simple hai; agar parallel allowed hain to multigraph.

Max edges samajhna important hai. Simple undirected mein n(n−1)2\frac{n(n-1)}{2} — divide by 2 isliye kyunki edge {u,v}\{u,v\} aur {v,u}\{v,u\} ek hi cheez hai (ek handshake do logon ka, par count ek). Directed mein divide nahi karte, n(n−1)n(n-1), kyunki (u,v)(u,v) aur (v,u)(v,u) alag arrows hain. Aur handshaking lemma: sab degrees ka sum =2m=2m, kyunki har edge apne dono endpoints par ek-ek baar count hota hai.

Yeh definitions kyun zaroori? Kyunki real problems — Google Maps roads, social networks, task dependencies — sab graphs hain. Agar tumne type galat samajh liya (jaise undirected ko directed treat kiya, ya weights ignore kiye), to tum galat algorithm lagaoge: BFS unweighted ke liye, Dijkstra weighted ke liye, topological sort sirf directed acyclic ke liye. Toh pehle type pehchano, phir algorithm chuno.

Go deeper — visual, from zero

D1FoundationsEvery symbol from zero · 1,821 wordsD2Visual walkthroughThe derivation in pictures · 1,865 wordsD3Worked examplesEvery scenario covered · 2,637 wordsD4ExercisesGraded, full solutions · 2,494 wordsD5Question bankConcept traps, quick reveals · 1,465 words

Test yourself — Graphs

L1 RecognitionL2 RecallL3 ProductionL4 ApplicationL5 Mastery

Connections

Dijkstra's algorithm — greedy, priority queue, O((V+E) log V) — no negative edgesCoding · 3.5.10Topological sort — DFS-based, Kahn's algorithm (BFS-based)Coding · 3.5.7