Vertel over een niet-gericht graaf en zijn eigenschappen.

Een ongericht diagram is een paar $(V, E)$, waarbij $V$ de verzameling knooppunten (knopen) is, en $E$ de verzameling randen. Elke rand vertegenwoordigt een niet-ordelijke paar ${u, v}$ van knooppunten, waarbij $u, v \in V$.

Belangrijkste eigenschappen:

• Randen zonder richting: De verbinding tussen knooppunten is symmetrisch. Als er een rand is tussen $u$ en $v$, betekent dit dat je zowel van $u$ naar $v$ als van $v$ naar $u$ kunt bewegen.
• Graad van een knoop: Het aantal randen dat aan die knoop grenst. Wordt genoteerd als $deg(v)$.
• Som van de graden van alle knopen: In elke ongerichte graaf is de som van de graden van alle knopen gelijk aan het dubbele van het aantal randen. $\sum_{v \in V} deg(v) = 2|E|$.
• Pad: Sequentie van knopen $v_0, v_1, ..., v_k$, waarbij elk paar $(v_i, v_{i+1})$ een rand is.
• Cirkels: Een pad dat begint en eindigt in dezelfde knoop, en alle andere knopen uniek zijn.
• Connectiviteit: Een graaf wordt verbonden genoemd als er een pad bestaat tussen elk paar knopen. Een niet-verbonden graaf bestaat uit meerdere verbonden componenten.
• Gewogen graaf: Aan elke rand kan een numerieke waarde (gewicht) worden toegekend.
• Afwezigheid van lussen en meervoudige randen (simple graaf): In eenvoudige ongerichte grafen kan er tussen twee knopen hooguit één rand zijn, en randen verbinden geen knoop met zichzelf (geen lussen).
• Volledige graaf: Een graaf waarin elk paar verschillende knopen verbonden is door een rand. Wordt aangeduid als $K_n$, waarbij $n$ het aantal knopen is.
• Bipartiete graaf: De verzameling knopen kan worden verdeeld in twee disjuncte subsets $U$ en $W$, zodat elke rand een knoop uit $U$ verbindt met een uit $W$.