eindknopen

Eindknopen is een term uit de grafentheorie en informaticatoepassingen die verwijst naar knopen aan de rand van een graf. In een graf zonder richting (ongedvijeled) is een eindknoop een knoop met graad 1, wat betekent dat het precies één verbinding heeft met de rest van het netwerk. In bomen, een speciale soort graf zonder cycli, komen eindknopen ook wel bladeren genoemd: knopen zonder kinderen.

In gerichte grafen kunnen eindknopen verwijzen naar knopen met geen uitgaande verbindingen (sinks) of, afhankelijk van de context, naar meer algemene terminale knopen. De term eindknoop wordt vaak gebruikt als synoniem voor leaf of terminal node.

Eigenschappen: In een eindige, verbonden boom met n knopen bestaan er ten minste twee eindknopen. Een niet-eindknoop in een boom heeft doorgaans meerdere verbindingen (graad minstens 2). Leefomstandigheden van eindknopen maken hen tot belangrijke uiteinden van paden en structuren in grafen.

Voorbeelden: Een padgraf met vier knopen heeft twee eindknopen aan de uiteinden. Een stergraf met één centrale knoop en meerdere buitenknopen heeft alle buitenknopen als eindknopen.

Toepassingen: Eindknopen worden gebruikt bij het identificeren van endpoints in netwerken, bij analyse van routes en connectiviteit, en in datastructuren zoals bomen en bijphylogenetische bomen waar eindknopen de uiteindelijke of extante elementen voorstellen.

Zie ook: blad (grafentheorie), knoop (grafentheorie).