De definities in de grafentheorie lopen uiteen. Hieronder volgen enkele van de meer elementaire manieren om grafieken en verwante wiskundige structuren te definiëren.
GrafiekEdit
Een grafiek (soms ongerichte grafiek genoemd ter onderscheiding van een gerichte grafiek, of eenvoudige grafiek ter onderscheiding van een meerzijdige grafiek) is een paar G = (V, E), waarbij V een verzameling is waarvan de elementen hoekpunten worden genoemd (enkelvoud: vertex), en E een verzameling gepaarde hoekpunten is, waarvan de elementen randen worden genoemd (soms links of lijnen).
De hoekpunten x en y van een rand {x, y} worden de eindpunten van de rand genoemd. Men zegt dat de rand x en y verbindt en incident is op x en y. Een hoekpunt kan tot geen enkele rand behoren, in welk geval het niet verbonden is met een ander hoekpunt.
Een multigraaf is een veralgemening die toestaat dat meerdere randen hetzelfde paar eindpunten hebben. In sommige teksten worden multigrafieën gewoon grafieken genoemd.
Soms mogen grafieken ook lussen bevatten, dat zijn ribben die een hoekpunt met zichzelf verbinden. Om lussen toe te staan, moet de bovenstaande definitie worden veranderd door de randen te definiëren als multisets van twee hoekpunten in plaats van twee sets. Zulke veralgemeende grafieken worden grafieken met lussen genoemd of gewoon grafieken als uit de context duidelijk is dat lussen zijn toegestaan.
In het algemeen wordt verondersteld dat de verzameling hoekpunten V eindig is; dit impliceert dat de verzameling ribben ook eindig is. Oneindige grafieken worden soms beschouwd, maar worden vaker gezien als een speciaal soort binaire relatie, omdat de meeste resultaten voor eindige grafieken niet opgaan voor het oneindige geval, of een heel ander bewijs nodig hebben.
Een lege grafiek is een grafiek met een lege verzameling hoekpunten (en dus een lege verzameling ribben). De orde van een grafiek is het aantal hoekpunten |V|. De grootte van een grafiek is het aantal ribben |E|. In sommige contexten, zoals voor het uitdrukken van de computationele complexiteit van algoritmen, is de grootte echter |V| + |E| (anders zou een niet-lege grafiek een grootte 0 kunnen hebben). De graad of valentie van een hoekpunt is het aantal ribben dat ermee verbonden is; voor grafieken met lussen wordt een lus tweemaal geteld.
In een grafiek van orde n is de maximale graad van elk hoekpunt n – 1 (of n als lussen zijn toegestaan), en het maximale aantal ribben n(n – 1)/2 (of n(n + 1)/2 als lussen zijn toegestaan).
De ribben van een grafiek definiëren een symmetrische relatie op de hoekpunten, die de adjacentierelatie wordt genoemd. Twee hoekpunten x en y zijn aangrenzend als {x, y} een rand is. Een grafiek kan volledig worden gespecificeerd door zijn adjacency matrix A, die een n × n {\displaystyle n keer n}
vierkante matrix, waarbij Aij het aantal verbindingen van hoekpunt i naar hoekpunt j aangeeft. Voor een eenvoudige grafiek is A i j ∈ { 0 , 1 } {\displaystyle A_{ij}\in \{0,1}}
, wat respectievelijk ontkoppeling of verbinding aangeeft, terwijl A i i = 0 {\displaystyle A_{ii}=0}
(dat wil zeggen, een rand kan niet bij hetzelfde hoekpunt beginnen en eindigen). Grafieken met zelflussen worden gekenmerkt door enkele of alle A i i {\displaystyle A_{ii}}
gelijk zijn aan een positief geheel getal, en multigrafieken (met meerdere randen tussen hoekpunten) worden gekenmerkt door een aantal of alle A i j {\displaystyle A_{ij}}
gelijk zijn aan een positief geheel getal. Ongerichte grafieken hebben een symmetrische adjacentiematrix ( A i j = A j i {\displaystyle A_{ij}=A_{ji}}
).
Directed graphEdit
Een gerichte grafiek of digraph is een grafiek waarin de ribben een oriëntatie hebben.
In een beperkte maar zeer gangbare betekenis van de term is een gerichte grafiek een paar G = ( V , E ) {Displaystyle G=(V,E)}
bestaande uit:
- V {Displaystyle V}
, een verzameling hoekpunten (ook wel knooppunten of punten genoemd);
- E ⊆ { ( x , y ) ∣ ( x , y ) ∈ V 2 en x ≠ y } {Displaystyle E{(x,y)\mid (x,y)\in V^{2}};{textrm {en}};x ≠ y}}
, een verzameling ribben (ook wel gerichte ribben, gerichte links, gerichte lijnen, pijlen of bogen genoemd) die geordende paren van hoekpunten zijn (d.w.z. dat een ribbe geassocieerd is met twee verschillende hoekpunten).
Om dubbelzinnigheid te voorkomen, kan dit type object precies een gerichte eenvoudige grafiek worden genoemd.
In de rand ( x , y ) {{displaystyle (x,y)}
geleid van x {\displaystyle x}
naar y {\displaystyle y}
, de hoekpunten x {\displaystyle x}
en y {\displaystyle y}
worden de eindpunten van de rand genoemd, x {{\displaystyle x}
de staart van de rand en y {\displaystyle y}
de kop van de rand. Men zegt dat de rand x {\displaystyle x}
en y {\displaystyle y}
en incident te zijn op x {{\displaystyle x}
en op y {{\displaystyle y}
. Een hoekpunt kan in een grafiek bestaan en niet tot een rand behoren. De rand ( y , x ) {\displaystyle (y,x)}
wordt de omgekeerde rand van ( x , y ) {\displaystyle (x,y)} genoemd.
. Meervoudige randen, die volgens de bovenstaande definitie niet zijn toegestaan, zijn twee of meer randen met zowel dezelfde staart als dezelfde kop.
In een algemenere betekenis van de term die meervoudige randen toestaat, is een gerichte grafiek een geordend drietal G = ( V , E , ϕ ) {\displaystyle G=(V,E,\phi )}
bestaande uit:
- V {Displaystyle V}
, een verzameling hoekpunten (ook wel knooppunten of punten genoemd);
- E {\displaystyle E}
, een verzameling ribben (ook wel gerichte ribben, gerichte links, gerichte lijnen, pijlen of bogen genoemd);
- ϕ : E → { ( x , y ) ∣ ( x , y ) ∈ V 2 en x ≠ y } {{(x,y)}^{2};{{{{}]en};x ≠ y}}
, een incidentiefunctie die elke rand met een geordend paar hoekpunten verbindt (d.w.z. dat een rand met twee verschillende hoekpunten is verbonden).
Om dubbelzinnigheid te voorkomen, kan dit type object precies een directed multigraph worden genoemd.
Een lus is een rand die een vertex met zichzelf verbindt. Gerichte grafen zoals gedefinieerd in de twee definities hierboven kunnen geen lussen hebben, omdat een lus die een hoekpunt x {{displaystyle x}
met zichzelf verbindt de rand is (voor een gerichte enkelvoudige graaf) of incident is op (voor een gerichte multigraaf) ( x , x ) {{displaystyle (x,x)}
die niet in { ( x , y ) ∣ ( x , y ) ∈ V 2 en x ≠ y } {{(x,y)} in V^{2}};{{{}}]en}};x ≠ y}}
. Om lussen toe te staan moeten de definities dus worden uitgebreid. Voor gerichte eenvoudige grafieken is de definitie van E {{Displaystyle E}
worden gewijzigd in E ⊆ { ( x , y ) ∣ ( x , y ) ∈ V 2 } {{(x,y)}}}
. Voor gerichte multigraven is de definitie van ϕ {\displaystyle \phi }
worden gewijzigd in ϕ : E → { ( x , y ) ∣ ( x , y ) ∈ V 2 } {{(x,y)\mid (x,y)\in V^{2}}
. Om dubbelzinnigheid te voorkomen, kunnen deze typen objecten respectievelijk een gerichte enkelvoudige graaf die lussen toelaat en een gerichte multigraaf die lussen toelaat (of een koker) worden genoemd.
De randen van een gerichte enkelvoudige graaf die lussen toelaat G {Displaystyle G}
is een homogene relatie ~ op de hoekpunten van G {\displaystyle G}
die de adjacentierelatie van G {{\displaystyle G}} wordt genoemd
. Concreet betekent dit dat voor elke rand ( x , y ) {\displaystyle (x,y)}
, de eindpunten x {\displaystyle x}
en y {\displaystyle y}
worden geacht aan elkaar te grenzen, wat wordt aangeduid met x {{\displaystyle x}
~ y {\displaystyle y}
.
Gemengde grafiekEdit
Een gemengde grafiek is een grafiek waarin sommige randen gericht kunnen zijn en sommige ongericht. Het is een geordend drietal G = (V, E, A) voor een gemengde eenvoudige grafiek en G = (V, E, A, ϕE, ϕA) voor een gemengde multigrafiek met V, E (de niet-gerichte randen), A (de gerichte randen), ϕE en ϕA gedefinieerd zoals hierboven. Directe en ongedirecte grafieken zijn speciale gevallen.
Gewogen grafiek
Een gewogen grafiek of netwerk is een grafiek waarin aan elke zijde een getal (het gewicht) wordt toegekend. Dergelijke gewichten kunnen bijvoorbeeld kosten, lengtes of capaciteiten vertegenwoordigen, afhankelijk van het probleem in kwestie. Dergelijke grafieken komen in vele contexten voor, bijvoorbeeld in problemen met het kortste pad, zoals het traveling salesman problem.