## Les 5: Grafen en Matrices

### Grafen

Een zogeheten 'graaf' is een schematische weergave van knopen en wegen. Een simpele variant is hieronder getekend.

Een rode stip op de graaf betekent dat er een verbinding is tussen twee wegen. Een kruising van wegen zonder stip heeft dus geen verbinding.

De knooppunten van een graaf kunnen we weergeven in een verbindingstabel. In het verbindingstabel geef je alle knooppunten aan. Vervolgens geef je met een 1 of 0 aan of er verbinding is tussen de knooppunten. 1 betekent dat er een verbinding is, 0 betekent dat er geen verbining is. In het voorbeeld hieronder is de tabel ingevuld voor de graaf uit de vorige opdracht.

Bijvoorbeeld:

Naar \ Van | A | B | C | D | E
--- | --- | --- | --- | --- | ---
A | X | 1 | 0 | 0 | 0
B | 1 | X | 1 | 1 | 0
C | 0 | 1 | X | 1 | 1
D | 0 | 1 | 1 | X | 1
E | 0 | 1 | 1 | 1 | X

Een graaf waarbij je van punt x naar punt y kunt én ook van punt y naar punt x is een symmetrische graaf.

Een graaf waarbij je van punt x naar punt y kunt, maar niet van punt y naar punt x is een gerichte graaf.

De richting in een gerichte graaf wordt aangegeven met een pijl.

Bijvoorbeeld:

In de algebra kennen we ook matrices. Een matrix is een manier om getallen die een verband hebben ook samen weer te geven. Zo'n matrix is een soort tabel zonder lijnen, waarin cijfers boven en naast elkaar zijn weergegeven. Hoeveel getallen worden weergegeven bepaalt ook de vorm van een matrix. Hieronder zie je een voorbeeld van een matrix.

Als er een m aantal rijen en een n aantal kolommen is, spreekt men van een m × n-matrix. Je geeft bij het beschrijven van een matrix dus eerst het aantal rijen aan, gevolgd door het aantal kolommen. De matrix hierboven is dus een 2 × 3-matrix.

De getallen in een matrix noem je de elementen van de matrix. 2×3-matrix A (hierboven) heeft 2×3 elementen. Dat zijn dus ook 6 elementen. Het element op het kruispunt van de r-de rij en de k-de kolom wordt genoteerd als het rk-element. Omdat de matrix in ons voorbeeld 'A' heet, kunnen we elementen uit die matrix aangeven met Ark. Zo is in ons voorbeeld A12 = -1 en A23 = 5

Matrices die dezefde vorm hebben kun je met elkaar optellen. Schematisch gaat dit zo:

Bijvoorbeeld:
Als:
Dan:
Dus:

Matrices vermenigvuldigen heeft iets weg van het optellen van matrices maar is net iets lastiger. Je vermenigvuldigt de rijen van de eerste matrix met de kolommen van de tweede matrix. Schematsich gaat dit dus zo:

Als we dit in een voorbeeld met cijfers laten zien wordt het misschien duidelijker:

Bijvoorbeeld:
Als:
Dan:
Dus:
Dus: