13 Graflar, Ağlar ve Incidence Matrisleri

Dört alt-uzay fizikselleşir — potansiyel, akım, ağaç, çevrim

Bölüm bilgisi

Strang’in videosu: YouTube — Lecture 12: Graphs, Networks, Incidence Matrices (≈48 dk)
OCW sayfası: MIT 18.06SC — Lecture 12
Okuma süresi: ≈40 dk

13.1 Bu Derste Ne Var?

Bu ders uygulama dersi: matris gerçek bir yapıdan (graf) doğuyor, dört temel alt-uzay fiziksel anlam kazanıyor.

Incidence matrisi: graf → matris.
Dört alt-uzayın fiziksel anlamı: null = potansiyel, sol null = Kirchhoff Akım Yasası, satır = ağaç.
Euler formülü: düğüm − kenar + çevrim = 1.
AᵀCA çerçevesi: uygulamalı matematiğin temel denklemi.

“A transpose y equals zero is probably the most fundamental equation of applied mathematics.” — Strang, 20:07

flowchart LR
    G["Graf (düğüm + yönlü kenar)"] --> A["Incidence matris A<br/>(m kenar × n düğüm)<br/>-1, +1 her satırda"]
    A --> NA["N(A) = sabit potansiyel<br/>(grounding, gauge)"]
    A --> NAT["⭐ N(Aᵀ) = Kirchhoff<br/>Aᵀy = 0 (korunum)<br/>çevrim akımları"]
    A --> ROW["C(Aᵀ) = ağaçlar<br/>(çevrimsiz alt-graf)"]

    A --> ATA["⚡ AᵀA = graph Laplacian<br/>simetrik, pozitif yarı-tanım"]
    ATA --> ML["Spectral clustering<br/>GCN, PageRank"]

    A --> EULER["Euler: n - m + çevrim = 1"]

    style NAT fill:#fff3e0,stroke:#e67e22,stroke-width:2px
    style ATA fill:#fce4ec,stroke:#c2185b,stroke-width:3px
    style ML fill:#fce4ec,stroke:#c2185b,stroke-width:2px

flowchart LR
    G["Graf (düğüm + yönlü kenar)"] --> A["Incidence matris A<br/>(m kenar × n düğüm)<br/>-1, +1 her satırda"]
    A --> NA["N(A) = sabit potansiyel<br/>(grounding, gauge)"]
    A --> NAT["⭐ N(Aᵀ) = Kirchhoff<br/>Aᵀy = 0 (korunum)<br/>çevrim akımları"]
    A --> ROW["C(Aᵀ) = ağaçlar<br/>(çevrimsiz alt-graf)"]

    A --> ATA["⚡ AᵀA = graph Laplacian<br/>simetrik, pozitif yarı-tanım"]
    ATA --> ML["Spectral clustering<br/>GCN, PageRank"]

    A --> EULER["Euler: n - m + çevrim = 1"]

    style NAT fill:#fff3e0,stroke:#e67e22,stroke-width:2px
    style ATA fill:#fce4ec,stroke:#c2185b,stroke-width:3px
    style ML fill:#fce4ec,stroke:#c2185b,stroke-width:2px

Şekil 13.1: Graf → incidence A → dört alt-uzay fizikselleşir; AᵀA = graph Laplacian.

Builder Notu — Graf Matrisleri ML’de

Incidence / adjacency → GNN’lerin girdi yapısı.
Graph Laplacian $L = A^T A$ → spectral clustering (Fiedler), GCN konvolüsyon, label propagation.
Null = gauge özgürlüğü → $L$’nin sıfır özdeğeri = bağlı bileşen sayısı.
Sol null = çevrimler → grafın homolojisi; topolojik veri analizi (TDA).

13.2 Graf ve Incidence Matrisi

Strang’in örneği: 4 düğüm, 5 kenar.

Kenar 1: $1 \to 2$
Kenar 2: $2 \to 3$
Kenar 3: $1 \to 3$
Kenar 4: $1 \to 4$
Kenar 5: $3 \to 4$

Her kenar bir satır. Kenar $i \to j$ için satırda $i$ kolonunda $-1$, $j$ kolonunda $+1$:

\[ A = \begin{pmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ 0 & 0 & -1 & 1 \end{pmatrix} \]

Seyrek (her satırda 2 sıfır-olmayan). İlk 3 kenar bir çevrim → satır 1 + satır 2 = satır 3 → bağımlı.

“Loops correspond to linearly dependent rows.” — Strang, 8:54

13.3 Null Uzayı — Potansiyeller ve Grounding

$\mathbf{x}$ = düğüm potansiyelleri. $A\mathbf{x}$ = kenar potansiyel farkları:

\[ A\mathbf{x} = (x_2 - x_1, x_3 - x_2, x_3 - x_1, x_4 - x_1, x_4 - x_3)^T \]

$A$ = fark operatörü (graf gradyanı).

$A\mathbf{x} = \mathbf{0}$ ⟺ tüm farklar sıfır ⟺ tüm potansiyeller eşit:

\[ N(A) = \{c (1, 1, 1, 1)^T\}, \quad \dim N(A) = 1 \]

\[ r = n - 1 = 3 \]

Grounding: Bir düğümü 0 yaparak referansı sabitle. Bu gauge özgürlüğü ($L$’nin sıfır özdeğeri = bağlı bileşen sayısı).

13.4 Sol Null Uzayı — Kirchhoff Akım Yasası ⭐

$\mathbf{y}$ = kenar akımları. $A^T \mathbf{y} = \mathbf{0}$ = Kirchhoff Akım Yasası (KCL).

$A^T$’nin her satırı bir düğüm → “giren akım = çıkan akım”.

Düğüm 1: $-y_1 - y_3 - y_4 = 0$ (üç çıkış toplamı).

“Kirchhoff’s Current Law is a balance equation, a conservation law. In equals out.” — Strang, 28:43

Boyut: $\dim N(A^T) = m - r = 5 - 3 = 2$.

13.5 Loop Akımları — Bazlar

Bir çevrim etrafında dolaşan akım her zaman KCL’i sağlar. İki bağımsız çevrim:

\[ \mathbf{y}_1 = (1, 1, -1, 0, 0)^T, \quad \mathbf{y}_2 = (0, 0, 1, -1, 1)^T \]

Büyük çevrim = $\mathbf{y}_1 + \mathbf{y}_2$ (kenar 3’te akımlar birbirini götürür) → bağımsız değil.

$\dim N(A^T)$ = bağımsız çevrim sayısı.

13.6 Ağaç (Tree)

Çevrimsiz graf. Bağımsız kenar = ağacın kenarı. Bir grafın bağımsız kenar sayısı = $n - 1$ (ağacın kenar sayısı).

13.7 Euler Formülü

Boyut sayımını birleştir:

\[ \text{çevrim} = m - r = m - (n - 1) = m - n + 1 \]

\[ \boxed{n - m + \text{çevrim} = 1} \]

Örnekte: $4 - 5 + 2 = 1$ ✓. Lineer cebir bir topoloji teoremini kanıtladı.

“The number of nodes minus the number of edges plus the number of loops is one. It’s known as Euler’s Formula.” — Strang, 41:52

Builder Notu: Euler formülü topolojik veri analizi (TDA) ve homolojinin kalbidir. Persistent homology bir veri bulutunun çoklu ölçekte “deliklerini” sayar — graf düzeyinde çevrim sayısı = ağın redundancy/dayanıklılık ölçüsü.

13.8 AᵀCA Çerçevesi — Uygulamalı Matematiğin Temeli

Üç fiziksel adım:

Potansiyel farkları: $\mathbf{e} = A\mathbf{x}$ (gradyan).
Ohm Yasası: $\mathbf{y} = C\mathbf{e}$ (iletkenlik).
KCL: $A^T \mathbf{y} = \mathbf{f}$ (korunum, dış kaynak $\mathbf{f}$).

Birleştir:

\[ \boxed{A^T C A \, \mathbf{x} = \mathbf{f}} \]

“There’s the basic equation of applied math.” — Strang, 46:22

Her yerde: elektrik devreleri, yapısal mekanik, ısı akışı, akışkanlar. Denge (equilibrium) problemlerinin evrensel iskeleti.

13.9 Graph Laplacian = AᵀA

$C = I$ özel hâli: $A^T A$. Her zaman simetrik, pozitif yarı-tanımlı.

import numpy as np

A = np.array([[-1, 1, 0, 0], [0, -1, 1, 0], [-1, 0, 1, 0],
              [-1, 0, 0, 1], [0, 0, -1, 1]], dtype=float)

L = A.T @ A
print("L (graph Laplacian) =\n", L)
print("\nSimetrik?", np.allclose(L, L.T))

eigvals = np.linalg.eigvalsh(L)
print("\nÖzdeğerler =", np.round(eigvals, 6))   # en küçük ~0 (sabit pot.)
print("rank(A) =", np.linalg.matrix_rank(A))

$L$’nin köşegen = düğüm derecesi; köşegen-dışı = bağlı düğümlere $-1$. Sabit vektör $L$’nin null uzayında → sıfır özdeğer.

Builder Notu — Graph Laplacian ML’de

Spectral clustering: En küçük (Fiedler) özvektör grafı zayıf-bağlı yerden böler.
GCN: Normalize $L$ konvolüsyon çekirdeği.
Diffusion / heat kernel: PageRank, label propagation, GraphSAGE.
Sıfır özdeğer sayısı = bağlı bileşen sayısı.
$L$’nin spektrumu grafın geometrisini kodlar.

13.10 Bu Dersin Özeti

Graf → düğüm + yönlü kenar.
Incidence matrisi: kenar × düğüm.
Null = sabit potansiyel (gauge); rank $n - 1$.
$A$ = fark operatörü; grounding.
Ağaç = çevrimsiz; bağımsız kenarlar.
Sol null = Kirchhoff.
Loop akımları = sol null bazı.
Euler: $n - m + \text{çevrim} = 1$.
AᵀCA denge denklemi.
$A^T A$ = graph Laplacian, spectral yöntemler.

Tek bir cümle

Bir graf bir incidence matrisine dönüşür; dört alt-uzay fizikselleşir — null = potansiyel, sol null = Kirchhoff korunumu (çevrimler), satır = ağaçlar. AᵀCA denge denklemi, AᵀA graph Laplacian olarak graf öğrenmesinin merkezi.

13.11 Kontrol Soruları

Soru 1: 3 düğüm üçgen graf (1→2, 2→3, 1→3) — incidence matris, rank.

\[ A = \begin{pmatrix} -1 & 1 & 0 \\ 0 & -1 & 1 \\ -1 & 0 & 1 \end{pmatrix} \]

$r_1 + r_2 = r_3$ → bağımlı. rank = $n - 1 = 2$.

Soru 2: Üçgen grafın null uzayı ve anlamı.

$N(A) = \{c (1, 1, 1)^T\}$, dim 1.

Fiziksel: potansiyeller sabite kadar belirli; bir düğümü topraklayarak (potansiyel = 0) belirsizlik giderilir.

Soru 3: 6 düğüm, 9 kenar bağlı graf — kaç bağımsız çevrim?

Euler: $6 - 9 + \text{çevrim} = 1 \to$ çevrim = 4.

Alternatif: $r = n - 1 = 5$; çevrim = $m - r = 4$. ✓

Soru 4: Graph Laplacian GNN ve spectral clustering’de nasıl?

Sıfır özdeğer: $L(1, \dots, 1) = \mathbf{0}$ → $L$’nin sıfır özdeğeri. Sayısı = bağlı bileşen sayısı.

Spectral clustering: En küçük sıfırdan sonraki özvektör (Fiedler) grafı zayıf bağlı yerden böler.

GCN: Normalize $L$ konvolüsyon çekirdeği; her katman komşu özelliklerini Laplacian ağırlıklarıyla toplar.

$L$’nin spektrumu grafın tüm spektral/difüzyon davranışını kodlar.

13.12 Egzersizler

Egzersiz 1. 4 düğüm yol grafı (1→2, 2→3, 3→4) için incidence yaz. Ağaç mı? Rank, çevrim sayısı.

Egzersiz 2. $A = \begin{pmatrix} -1 & 1 & 0 \\ 0 & -1 & 1 \\ -1 & 0 & 1 \\ -1 & 0 & 1 \end{pmatrix}$ — null ve sol null boyutu. (3. ve 4. satır aynı → ne anlama gelir?)

Egzersiz 3. Bağlı graf, 10 düğüm, 15 kenar — rank, null boyut, çevrim, Euler doğrulaması.

Egzersiz 4. (Python) Graph Laplacian özdeğerleri.

Egzersiz 5. İspatla: Bağlı grafta $\dim N(A) = 1$, sabit vektör tarafından spanlanır. (İpucu: $A\mathbf{x} = \mathbf{0}$ komşu düğümlerin eşit potansiyelini gerektirir; bağlılık tüm grafa yayar.) Bu, Laplacian’ın tam bir sıfır özdeğerine sahip olmasını açıklar.

13.13 Sonraki Ders İçin Hazırlık

Ders 13: Quiz 1 İncelemesi

Chapter 1-3’ün toplu tekrarı: eliminasyon, LU, vektör uzayları, dört alt-uzay, rank, Ax = b, bağımsızlık/baz/boyut.

Ders 13 öncesi

Ders 1-12 egzersizlerini gözden geçir.
A.T @ A ile Laplacian’ı incele.

13.14 Anahtar Kavramlar (Cheat Sheet)

Kavram	Tanım	Strang’da
Graf	Düğüm + yönlü kenar	2m38
Incidence matris	Kenar × düğüm, $-1, +1$	5m49
Loop = bağımlı satır	Çevrimler bağımlılık	8m01
$A$ = fark operatörü	$A\mathbf{x}$ = potansiyel farkları	13m19
Null = sabit potansiyel	dim 1, rank $n-1$	15m22
Grounding	Referansı sabitle	18m06
KCL: $A^T\mathbf{y} = \mathbf{0}$	Korunum	25m50
Loop akımları	Sol null bazı	33m19
Ağaç	Çevrimsiz	39m06
Euler	$n - m + \text{çevrim} = 1$	41m52
$A^T C A$	Uygulamalı mat. denge	46m22

13.15 ML Bağlantıları Özeti

7 köprü

Incidence / adjacency → GNN girdi yapısı.
Graph Laplacian ($A^T A$) → Spectral clustering, GCN, label propagation.
Null = gauge → Laplacian sıfır özdeğer = bağlı bileşen sayısı.
Sol null = çevrimler → Homoloji, TDA, persistent homology.
$A^T C A$ denge denklemi → Physics-informed models, FEM.
Korunum → Akış, optimal transport, GNN aggregation.
Euler / topoloji → Veri bulutunun deliklerini sayma; TDA.

Tek bir şey alıp gideceksen

Graf → incidence matris → dört alt-uzay fizikselleşir (potansiyel, akım, ağaç, çevrim). $A^T C A$ denge denklemi her yerde; $A^T A$ = graph Laplacian graf öğrenmesinin merkezi.

--- title: "Graflar, Ağlar ve Incidence Matrisleri" subtitle: "Dört alt-uzay fizikselleşir — potansiyel, akım, ağaç, çevrim" --- ::: {.callout-note title="Bölüm bilgisi"} - **Strang'in videosu:** [YouTube — Lecture 12: Graphs, Networks, Incidence Matrices](https://www.youtube.com/watch?v=6-wh6yvk6uc) (≈48 dk) - **OCW sayfası:** [MIT 18.06SC — Lecture 12](https://ocw.mit.edu/courses/18-06sc-linear-algebra-fall-2011/resources/graphs-networks-incidence-matrices/) - **Okuma süresi:** ≈40 dk ::: ## Bu Derste Ne Var? {#sec-bu-derste} Bu ders **uygulama** dersi: matris gerçek bir yapıdan (graf) doğuyor, dört temel alt-uzay fiziksel anlam kazanıyor. 1. **Incidence matrisi**: graf → matris. 2. **Dört alt-uzayın fiziksel anlamı**: null = potansiyel, sol null = Kirchhoff Akım Yasası, satır = ağaç. 3. **Euler formülü**: düğüm − kenar + çevrim = 1. 4. **AᵀCA çerçevesi**: uygulamalı matematiğin temel denklemi. > *"A transpose y equals zero is probably the most fundamental equation of applied mathematics."* — Strang, 20:07 ```{mermaid} %%| label: fig-concept-map %%| fig-cap: "Graf → incidence A → dört alt-uzay fizikselleşir; AᵀA = graph Laplacian." flowchart LR G["Graf (düğüm + yönlü kenar)"] --> A["Incidence matris A (m kenar × n düğüm) -1, +1 her satırda"] A --> NA["N(A) = sabit potansiyel (grounding, gauge)"] A --> NAT["⭐ N(Aᵀ) = Kirchhoff Aᵀy = 0 (korunum) çevrim akımları"] A --> ROW["C(Aᵀ) = ağaçlar (çevrimsiz alt-graf)"] A --> ATA["⚡ AᵀA = graph Laplacian simetrik, pozitif yarı-tanım"] ATA --> ML["Spectral clustering GCN, PageRank"] A --> EULER["Euler: n - m + çevrim = 1"] style NAT fill:#fff3e0,stroke:#e67e22,stroke-width:2px style ATA fill:#fce4ec,stroke:#c2185b,stroke-width:3px style ML fill:#fce4ec,stroke:#c2185b,stroke-width:2px ``` ::: {.callout-tip title="Builder Notu — Graf Matrisleri ML'de"} - **Incidence / adjacency** → GNN'lerin girdi yapısı. - **Graph Laplacian** $L = A^T A$ → spectral clustering (Fiedler), GCN konvolüsyon, label propagation. - **Null = gauge özgürlüğü** → $L$'nin sıfır özdeğeri = bağlı bileşen sayısı. - **Sol null = çevrimler** → grafın homolojisi; topolojik veri analizi (TDA). ::: ## Graf ve Incidence Matrisi {#sec-incidence} Strang'in örneği: 4 düğüm, 5 kenar. - Kenar 1: $1 \to 2$ - Kenar 2: $2 \to 3$ - Kenar 3: $1 \to 3$ - Kenar 4: $1 \to 4$ - Kenar 5: $3 \to 4$ Her kenar bir satır. Kenar $i \to j$ için satırda $i$ kolonunda $-1$, $j$ kolonunda $+1$: $$ A = \begin{pmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ 0 & 0 & -1 & 1 \end{pmatrix} $$ **Seyrek** (her satırda 2 sıfır-olmayan). İlk 3 kenar bir çevrim → satır 1 + satır 2 = satır 3 → **bağımlı**. > *"Loops correspond to linearly dependent rows."* — Strang, 8:54 ## Null Uzayı — Potansiyeller ve Grounding {#sec-null-potansiyel} $\mathbf{x}$ = düğüm potansiyelleri. $A\mathbf{x}$ = kenar potansiyel farkları: $$ A\mathbf{x} = (x_2 - x_1, x_3 - x_2, x_3 - x_1, x_4 - x_1, x_4 - x_3)^T $$ **$A$ = fark operatörü** (graf gradyanı). $A\mathbf{x} = \mathbf{0}$ ⟺ tüm farklar sıfır ⟺ tüm potansiyeller eşit: $$ N(A) = \{c (1, 1, 1, 1)^T\}, \quad \dim N(A) = 1 $$ $$ r = n - 1 = 3 $$ **Grounding:** Bir düğümü 0 yaparak referansı sabitle. Bu **gauge özgürlüğü** ($L$'nin sıfır özdeğeri = bağlı bileşen sayısı). ## Sol Null Uzayı — Kirchhoff Akım Yasası ⭐ {#sec-kirchhoff} $\mathbf{y}$ = kenar akımları. $A^T \mathbf{y} = \mathbf{0}$ = **Kirchhoff Akım Yasası (KCL)**. $A^T$'nin her satırı bir düğüm → "giren akım = çıkan akım". Düğüm 1: $-y_1 - y_3 - y_4 = 0$ (üç çıkış toplamı). > *"Kirchhoff's Current Law is a balance equation, a conservation law. In equals out."* — Strang, 28:43 Boyut: $\dim N(A^T) = m - r = 5 - 3 = 2$. ## Loop Akımları — Bazlar {#sec-loop} Bir çevrim etrafında dolaşan akım her zaman KCL'i sağlar. İki bağımsız çevrim: $$ \mathbf{y}_1 = (1, 1, -1, 0, 0)^T, \quad \mathbf{y}_2 = (0, 0, 1, -1, 1)^T $$ Büyük çevrim = $\mathbf{y}_1 + \mathbf{y}_2$ (kenar 3'te akımlar birbirini götürür) → bağımsız değil. **$\dim N(A^T)$ = bağımsız çevrim sayısı.** ## Ağaç (Tree) {#sec-agac} Çevrimsiz graf. Bağımsız kenar = ağacın kenarı. Bir grafın bağımsız kenar sayısı = $n - 1$ (ağacın kenar sayısı). ## Euler Formülü {#sec-euler} Boyut sayımını birleştir: $$ \text{çevrim} = m - r = m - (n - 1) = m - n + 1 $$ $$ \boxed{n - m + \text{çevrim} = 1} $$ Örnekte: $4 - 5 + 2 = 1$ ✓. **Lineer cebir bir topoloji teoremini kanıtladı.** > *"The number of nodes minus the number of edges plus the number of loops is one. It's known as Euler's Formula."* — Strang, 41:52 **Builder Notu:** Euler formülü **topolojik veri analizi (TDA)** ve **homolojinin** kalbidir. Persistent homology bir veri bulutunun çoklu ölçekte "deliklerini" sayar — graf düzeyinde çevrim sayısı = ağın redundancy/dayanıklılık ölçüsü. ## AᵀCA Çerçevesi — Uygulamalı Matematiğin Temeli {#sec-AtCA} Üç fiziksel adım: 1. **Potansiyel farkları:** $\mathbf{e} = A\mathbf{x}$ (gradyan). 2. **Ohm Yasası:** $\mathbf{y} = C\mathbf{e}$ (iletkenlik). 3. **KCL:** $A^T \mathbf{y} = \mathbf{f}$ (korunum, dış kaynak $\mathbf{f}$). Birleştir: $$ \boxed{A^T C A \, \mathbf{x} = \mathbf{f}} $$ > *"There's the basic equation of applied math."* — Strang, 46:22 **Her yerde:** elektrik devreleri, yapısal mekanik, ısı akışı, akışkanlar. Denge (equilibrium) problemlerinin evrensel iskeleti. ## Graph Laplacian = AᵀA {#sec-laplacian} $C = I$ özel hâli: $A^T A$. **Her zaman simetrik, pozitif yarı-tanımlı.** ```{python} #| label: code-laplacian #| code-fold: false import numpy as np A = np.array([[-1, 1, 0, 0], [0, -1, 1, 0], [-1, 0, 1, 0], [-1, 0, 0, 1], [0, 0, -1, 1]], dtype=float) L = A.T @ A print("L (graph Laplacian) =\n", L) print("\nSimetrik?", np.allclose(L, L.T)) eigvals = np.linalg.eigvalsh(L) print("\nÖzdeğerler =", np.round(eigvals, 6)) # en küçük ~0 (sabit pot.) print("rank(A) =", np.linalg.matrix_rank(A)) ``` $L$'nin köşegen = düğüm derecesi; köşegen-dışı = bağlı düğümlere $-1$. **Sabit vektör $L$'nin null uzayında** → sıfır özdeğer. ::: {.callout-tip title="Builder Notu — Graph Laplacian ML'de"} - **Spectral clustering:** En küçük (Fiedler) özvektör grafı zayıf-bağlı yerden böler. - **GCN:** Normalize $L$ konvolüsyon çekirdeği. - **Diffusion / heat kernel:** PageRank, label propagation, GraphSAGE. - **Sıfır özdeğer sayısı = bağlı bileşen sayısı**. - $L$'nin spektrumu grafın geometrisini kodlar. ::: ## Bu Dersin Özeti {#sec-ozet} 1. **Graf** → düğüm + yönlü kenar. 2. **Incidence matrisi**: kenar × düğüm. 3. **Null = sabit potansiyel** (gauge); rank $n - 1$. 4. **$A$ = fark operatörü**; grounding. 5. **Ağaç** = çevrimsiz; bağımsız kenarlar. 6. **Sol null = Kirchhoff**. 7. **Loop akımları** = sol null bazı. 8. **Euler**: $n - m + \text{çevrim} = 1$. 9. **AᵀCA** denge denklemi. 10. **$A^T A$ = graph Laplacian**, spectral yöntemler. ::: {.callout-important title="Tek bir cümle"} Bir graf bir incidence matrisine dönüşür; dört alt-uzay fizikselleşir — null = potansiyel, sol null = Kirchhoff korunumu (çevrimler), satır = ağaçlar. **AᵀCA** denge denklemi, **AᵀA** graph Laplacian olarak graf öğrenmesinin merkezi. ::: ## Kontrol Soruları {#sec-sorular} ::: {.callout-note collapse="true" title="Soru 1: 3 düğüm üçgen graf (1→2, 2→3, 1→3) — incidence matris, rank."} $$ A = \begin{pmatrix} -1 & 1 & 0 \\ 0 & -1 & 1 \\ -1 & 0 & 1 \end{pmatrix} $$ $r_1 + r_2 = r_3$ → bağımlı. **rank = $n - 1 = 2$**. ::: ::: {.callout-note collapse="true" title="Soru 2: Üçgen grafın null uzayı ve anlamı."} $N(A) = \{c (1, 1, 1)^T\}$, dim 1. **Fiziksel:** potansiyeller sabite kadar belirli; bir düğümü topraklayarak (potansiyel = 0) belirsizlik giderilir. ::: ::: {.callout-note collapse="true" title="Soru 3: 6 düğüm, 9 kenar bağlı graf — kaç bağımsız çevrim?"} Euler: $6 - 9 + \text{çevrim} = 1 \to$ **çevrim = 4**. Alternatif: $r = n - 1 = 5$; çevrim = $m - r = 4$. ✓ ::: ::: {.callout-note collapse="true" title="Soru 4: Graph Laplacian GNN ve spectral clustering'de nasıl?"} **Sıfır özdeğer:** $L(1, \dots, 1) = \mathbf{0}$ → $L$'nin sıfır özdeğeri. **Sayısı = bağlı bileşen sayısı.** **Spectral clustering:** En küçük sıfırdan sonraki özvektör (Fiedler) grafı zayıf bağlı yerden böler. **GCN:** Normalize $L$ konvolüsyon çekirdeği; her katman komşu özelliklerini Laplacian ağırlıklarıyla toplar. $L$'nin spektrumu grafın tüm spektral/difüzyon davranışını kodlar. ::: ## Egzersizler {#sec-egzersizler} **Egzersiz 1.** 4 düğüm yol grafı (1→2, 2→3, 3→4) için incidence yaz. Ağaç mı? Rank, çevrim sayısı. **Egzersiz 2.** $A = \begin{pmatrix} -1 & 1 & 0 \\ 0 & -1 & 1 \\ -1 & 0 & 1 \\ -1 & 0 & 1 \end{pmatrix}$ — null ve sol null boyutu. (3. ve 4. satır aynı → ne anlama gelir?) **Egzersiz 3.** Bağlı graf, 10 düğüm, 15 kenar — rank, null boyut, çevrim, Euler doğrulaması. **Egzersiz 4.** *(Python)* Graph Laplacian özdeğerleri. **Egzersiz 5.** *İspatla:* Bağlı grafta $\dim N(A) = 1$, sabit vektör tarafından spanlanır. (İpucu: $A\mathbf{x} = \mathbf{0}$ komşu düğümlerin eşit potansiyelini gerektirir; bağlılık tüm grafa yayar.) Bu, Laplacian'ın tam bir sıfır özdeğerine sahip olmasını açıklar. ## Sonraki Ders İçin Hazırlık {#sec-sonraki} **Ders 13: Quiz 1 İncelemesi** Chapter 1-3'ün toplu tekrarı: eliminasyon, LU, vektör uzayları, dört alt-uzay, rank, Ax = b, bağımsızlık/baz/boyut. ::: {.callout-warning title="Ders 13 öncesi"} - Ders 1-12 egzersizlerini gözden geçir. - `A.T @ A` ile Laplacian'ı incele. ::: ## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet} | Kavram | Tanım | Strang'da | |--------|-------|-----------| | **Graf** | Düğüm + yönlü kenar | 2m38 | | **Incidence matris** | Kenar × düğüm, $-1, +1$ | 5m49 | | **Loop = bağımlı satır** | Çevrimler bağımlılık | 8m01 | | **$A$ = fark operatörü** | $A\mathbf{x}$ = potansiyel farkları | 13m19 | | **Null = sabit potansiyel** | dim 1, rank $n-1$ | 15m22 | | **Grounding** | Referansı sabitle | 18m06 | | **KCL: $A^T\mathbf{y} = \mathbf{0}$** | Korunum | 25m50 | | **Loop akımları** | Sol null bazı | 33m19 | | **Ağaç** | Çevrimsiz | 39m06 | | **Euler** | $n - m + \text{çevrim} = 1$ | 41m52 | | **$A^T C A$** | Uygulamalı mat. denge | 46m22 | ## ML Bağlantıları Özeti {#sec-ml-baglantilar} ::: {.callout-tip title="7 köprü"} 1. **Incidence / adjacency** → GNN girdi yapısı. 2. **Graph Laplacian ($A^T A$)** → Spectral clustering, GCN, label propagation. 3. **Null = gauge** → Laplacian sıfır özdeğer = bağlı bileşen sayısı. 4. **Sol null = çevrimler** → Homoloji, TDA, persistent homology. 5. **$A^T C A$ denge denklemi** → Physics-informed models, FEM. 6. **Korunum** → Akış, optimal transport, GNN aggregation. 7. **Euler / topoloji** → Veri bulutunun deliklerini sayma; TDA. ::: ::: {.callout-important title="Tek bir şey alıp gideceksen"} Graf → incidence matris → dört alt-uzay fizikselleşir (potansiyel, akım, ağaç, çevrim). **$A^T C A$** denge denklemi her yerde; **$A^T A$ = graph Laplacian** graf öğrenmesinin merkezi. :::