Graf (diskret matematik)
object der består af knuder og links / From Wikipedia, the free encyclopedia
I matematikken, og mere specifikt i diskret matematik og grafteori, er en graf en struktur, der består af en mængde objekter og et relationsbegreb mellem par af objekter. Objekterne kaldes knuder (eller hjørner eller punkter), og relationen mellem par af knuder kaldes en kant. [1] Grafen afbildes ofte i diagrammatisk form som en mængde af prikker eller cirkler for knuderne, som er forbundet med linjer eller kurver for kanterne. Grafer kaldes i nogle discipliner for netværk. Denne slags grafer har intet at gøre med grafen for en funktion.
Kanterne kan være rettede eller urettede, svarende til relationens symmetriegenskaber. Når knuderne for eksempel repræsenterer festdeltagere, og en kant forbinder de mennesker, der har givet hånd til hinanden, er grafen ikke rettet, idet A har givet hånd til B, hvis B og kun hvis B har givet hånd til A. Når kantrelationen derimod skal modellere, at A skylder penge til B, så er grafen rettet, idet »at skylde penge« ikke nødvendigvis er gengældt. Den førstnævnte type graf kaldes en urettet graf, mens den sidstnævnte kaldes en rettet graf .
Grafer er det grundlæggende struktur studeret i grafteori. Ordet »graf« blev først brugt i denne forstand af James Joseph Sylvester i 1878. [2] [3]