Grafentheorie

Een graaf met zes punten/knopen/knooppunten

Een graaf is een netwerk, een tekening met punten die door middel van lijnen verbonden zijn.

Begrippenlijst

• Graad Het aantal buren van een punt.
• Ingraad Het aantal buren dat in het punt gaat.
• Uitgraad Het aantal buren dat uit het punt gaat.
• Eulercykel Cykel (cyclus, omloop) die langs alle lijnen gaat, het beginpunt en het eindpunt zijn hetzelfde.
• Eulerpad Pad dat langs alle lijnen gaat, het beginpunt en het eindpunt zijn nu niet hetzelfde.
• Buren De punten waarmee een punt verbonden is.
• Hamiltoncykel Cykel die langs alle punten gaat, het beginpunt en het eindpunt zijn hetzelfde.
• Hamiltonpad Pad die langs alle punten gaat, het beginpunt en het eindpunt zijn nu niet hetzelfde.
• Volledige graaf Graaf waar alle punten buren van elkaar zijn.
• Complementaire graaf Graaf waar de lijnen die er eerst niet waren er wel zijn en de lijnen die er wel waren er nu niet zijn.
• Isomorf Twee grafen waar dezelfde punten met elkaar verbonden zijn.
• Planaire graaf Een graaf die geen lijnen heeft die elkaar snijden.

Punten die met een ander punt verbonden zijn heten buren. Het aantal buren van een punt heet de graad van het punt. Bij een Eulerpad hebben het begin - en eindpunt een oneven graad. Bij een Eulercykel hebben het begin -en eindpunt een even graad. Als je een wandeling kunt maken in een graaf, dan zijn er 2 of minder punten met een oneven graad.

In een gerichte graaf zijn er twee soorten graden, namelijk de in -en de uitgraad. In een gerichte graaf geldt: ingraad + uitgraad = graad. In een gerichte graaf met een rondwandeling meet hetzelfde begin -en eindpunt zijn de in- en de uitgraad hetzelfde.

In een gerichte graaf is de ingraad van het beginpunt één groter dan de uitgraad van het beginpunt als het begin en het eindpunt hetzelfde zijn. Een cykel die langs alle punten gaat heet een Hamiltoncykel.

Het verschil tussen een Hamiltonpad en een Hamiltoncykel is dat bij een Hamiltoncykel het begin- en eindpunt hetzelfde zijn en bij een Hamiltonpad niet. Het complement van een graaf is een graaf waarin de lijn die er in de graaf zelf niet waren, er wel zijn en de lijnen die er wel waren worden niet getekend in het complement.

Een graaf waarin allen punten elkaars buren zijn, heet een volledige graaf. Het aantal lijnen in een graaf + het aantal lijnen in het complement van een graaf = het aantal lijnen in de volledige graaf. Het aantal lijnen in een volledige graaf met n punten is n • (n-1) ÷ 2.Twee grafen die de zelfde punten hebben en waar dezelfde punten verbonden zijn, heten isomorf.

Een graaf die geen lijnen heeft die elkaar snijden heet een planaire graaf.

Zie voor een vroege graaf en voor een verduidelijking van de theorie de Bruggen van Koningsbergen (puzzel).