Grafen:           Spellingsfout?  Nee, hier wordt NIET het meervoud van een adellijk persoon bedoeld (graaf >> graven),
maar het meervoud van de wiskundige term graaf (graaf => grafen)

Definitie graaf:  Een graaf bestaat uit een eindige verzameling V waarvan
de elementen met punten worden aangegeven, en deelverzamelingen van V die aangegeven worden met verbindingslijn(en) tussen 2 punten.

Een graaf is een verzameling punten waarvan er sommige met elkaar verbonden kunnen zijn door verbindingen (lijnen).
De verbinding tussen 2 punten noemen we een weg. (bijv. de lijn tussen punt C en punt D)
Kortom: een graaf is een verzameling punten die d.m.v. wegen met elkaar verbonden zijn.

Een graaf is ook te omschrijven als een sterk vereenvoudigde weergave van een werkelijke situatie of plattegrond,
maar een graaf is GEEN tekening op schaal.  De lengte van een weg in een graaf zegt niets over de werkelijke afstand tussen knooppunten.

Een graaf is een schematische voorstelling die bestaat uit punten en verbindingslijnen tussen de punten.
De punten van een graaf worden knooppunten genoemd; de lijnen tussen de knooppunten heten wegen. 
In de simpele graaf hierboven lopen wegen tussen de knooppunten AB, BC, CD, AD en BE.
Tussen de punten B en D is geen rechtstreekse verbinding, evenals tussen A en C, E en F, enz. ...

 

Volledige graaf:  Een volledige graaf is een graaf waarin tussen elk paar knooppunten een tak bestaat.
In een volledige graaf zijn alle punten met elkaar verbonden d.m.v. rechtstreekse lijnen.

                   

simpele graaf                              gerichte graaf                              gemengde graaf

Gerichte graaf:  Een graaf met éénrichtingswegen.
Met pijlen wordt aangegeven in welke richting je bijv. van A naar B kunt gaan.

Gewogen graaf:  Er staan getallen bij de wegen, die afstanden of kosten aangeven.

Samenhangende graaf:  Een graaf is samenhangend als je vanaf ieder punt via de wegen bij elk ander punt komen.

 

Graad van een punt:  De graad van een punt is het aantal wegen dat verbonden is met dat betreffende punt.
Bijvoorbeeld als B is verbonden met 2 punten, nl. A en C, dan is de graad van B dus 2.

Graad van een graaf:  De graad van een graaf is de hoogste graad in een bepaald punt.

 

Planair:          Een graaf is planair als hij zodanig in het platte vlak getekend kan worden dat de wegen elkaar alleen in de punten van de graaf snijden.

Eulerwandeling:  Dit is een wandeling over alle wegen van de graaf die iedere weg precies 1 keer bevat en begin- en eindpunt gelijk zijn.
Bij elk punt komen een even aantal wegen samen

Hamiltongraaf:  Een graaf is een Hamiltongraaf als je een route kunt maken waarbij alle punten uit de graaf 1x worden aangedaan, en waarbij het startpunt hetzelfde is als het eindpunt.

Complete graaf:  Een complete graaf is een graaf waarin alle punten onderling verbonden zijn.

De Petersen-graaf speelt een belangrijke rol als zogenaamd kritisch voorbeeld: allerlei eigenschappen gaan juist wel of juist niet meer op voor de Petersen-graaf. De Deen Julius Petersen gebruikte hem op die manier in 1898 als eerste."

Isomorf:         Twee grafen zijn isomorf als het dezelfde grafen zijn alleen op een verschillende manier getekend.
Deze grafen zijn isomorf, want ze hebben evenveel punten en evenveel wegen die allemaal naar dezelfde punten gaan.

Beide grafen hierboven zijn gelijkwaardig

 

Compatibiliteitsgraaf: Voor het opstellen van verkeersstromen bij stoplichten.  De punten stellen verkeersstromen voor. Je moet punten verbinden als die verkeersstromen tegelijk kunnen rijden, en vervolgens subgrafen aanbrengen.

Boom:            Een samenhangende graaf zonder cyclus heet een boom(diagram).