Incidence matrix — Hinglish notes

3.5.3 · Coding › Graphs

Incidence matrix KYA hota hai?

Ise scratch se KAISE banayein (construction se derivation)

Hum koi formula yaad nahi karte — hum matrix ko generate karte hain.

Har vertex list karo → ye rows ko label karenge.
Har edge ko us vertex pair ke roop mein list karo jise wo join karta hai → ye columns ko label karenge.
Har column (edge) ke liye, uske do endpoints ki rows mein mark lagao.

Worked Example 1 — Undirected

Graph: vertices ${1, 2, 3}$ , edges $e_{1} = (1, 2), e_{2} = (2, 3), e_{3} = (1, 3)$ (ek triangle).

	$e_{1}$	$e_{2}$	$e_{3}$
$1$	1	0	1
$2$	1	1	0
$3$	0	1	1

Row 1 = 1 0 1 KYU? Vertex 1 sirf edges $e_{1}$ aur $e_{3}$ mein hai. → Ye step KYU? Hum har edge scan karte hain aur poochte hain "kya vertex 1 ek endpoint hai?"
Degrees check karein: har row ka sum 2 hai → har vertex ki degree 2 hai. Triangle ke liye sahi. ✔

Worked Example 2 — Directed

Edges: $e_{1} : 1 \to 2$ , $e_{2} : 2 \to 3$ , $e_{3} : 1 \to 3$ .

	$e_{1}$	$e_{2}$	$e_{3}$
$1$	$- 1$	0	$- 1$
$2$	$+ 1$	$- 1$	0
$3$	0	$+ 1$	$+ 1$

$B_{1, 1} = - 1$ KYU? Edge $e_{1}$ vertex 1 ko leave karti hai (vertex 1 tail hai). → Ye step KYU? Convention: tail negative, head positive.
Check: har column ka sum 0 hai. ✔

Worked Example 3 — Self-loop

Edge $e_{1}$ vertex 1 par ek loop hai (ek edge $1 \to 1$ ).

	$e_{1}$
$1$	2

2 KYU (undirected mein) 1 ki jagah? Ek loop vertex 1 ko dono endpoints se touch karta hai, isliye ye degree mein 2 add karta hai. → Ye step KYU? Row-sum = degree rule consistent rehta hai (loops degree mein 2 add karte hain).

Common mistake Steel-manned common mistakes

Mistake 1: "Incidence matrix square ( $n \times n$ ) hota hai." Ye sahi kyun lagta hai: adjacency matrix square hoti hai, isliye students assume karte hain ki saari graph matrices aisi hoti hain. Fix: incidence do alag sets (vertices vs edges) ko relate karta hai, isliye ye $n \times m$ hai. Sirf jab $n = m$ ho tabhi ye coincidence se square dikhta hai.

Mistake 2: "Column mein teen 1's ho sakte hain." Ye sahi kyun lagta hai: ek vertex ke paas bahut saari edges ho sakti hain, isliye lagta hai ek edge bahut saari vertices ko touch kar sakti hai. Fix: ek edge ke exactly do endpoints hote hain, isliye har column mein exactly do non-zeros hote hain (ya loop ke liye "2" ki ek entry).

Mistake 3: "Directed graphs mein undirected ki tarah 1/0 use karo." Ye sahi kyun lagta hai: 1 = "connected" intuitive lagta hai. Fix: signs ke bina direction information kho jaati hai. $- 1$ (tail) / $+ 1$ (head) use karo taaki column sums zero ho jaayein aur $L = B B^{T}$ kaam kare.

Recall Feynman: ek 12-saal ke bacche ko samjhao

Ek dosto ki list socho. Side mein sabke naam likho. Upar har dosti likho jaise "Dosti #1". Agar wo insaan us dosti ka hissa hai toh box mein tick lagao. Kyunki ek dosti hamesha do logon ko jorti hai, isliye har column mein exactly do ticks aate hain. Apni row ke ticks gino aur tumhe pata chalega tumhare kitne dost hain. Wo tick-grid hi incidence matrix hai — dosto ko pure numbers mein likhne ka tarika taaki computer unhe padh sake.

Flashcards

n vertices aur m edges wale graph ke incidence matrix ki dimensions kya hoti hain?

n \times m

(rows = vertices, columns = edges).

Ek undirected incidence matrix mein har column mein kitne non-zero entries hote hain?

Exactly do (do endpoints), ya self-loop ke liye sirf ek "2".

Row

i

ka sum (undirected) kiske barabar hota hai?

Vertex

v_{i}

ki degree ke.

Ek directed incidence matrix mein edge ke tail aur head ko kaunsi values se mark karte hain?

Tail =

- 1

, Head =

+ 1

Directed incidence matrix mein har column ka sum 0 KYU hota hai?

Har edge mein ek tail (

- 1

) aur ek head (

+ 1

) hota hai; wo cancel ho jaate hain.

Ek self-loop ek undirected incidence matrix mein kaise dikhta hai?

Us vertex ki row mein

2

ki ek entry ke roop mein (loop degree mein 2 add karta hai).

Incidence matrix Handshake Lemma ko kaise prove karta hai?

Columns se total 1's gino =

2 m

; rows se gino =

\sum de g (v_{i})

; isliye

\sum de g = 2 m

Directed incidence matrix B ke terms mein graph Laplacian kya hai?

L = B B^{T}

Connections

Adjacency matrix — alternative $n \times n$ representation (vertex-to-vertex).
Graph Laplacian — oriented incidence matrix se $L = B B^{T}$ ke roop mein banta hai.
Degree of a vertex — yahan ek row sum ke barabar hota hai.
Handshake Lemma — incidence marks count karne se nikalta hai.
Sparse graph representations — bade graphs ke liye incidence lists/CSR.