Email: r.f.daceri-artist@centainesdestyles.nl

Thema: RFD WISKUNDE GRAFENTHEORIE

Discrete wiskunde

Discrete wiskunde is de studie van wiskundige structuren die fundamenteel discreet zijn, dat wil zeggen dat er gehele, los van elkaar staande zaken bekeken worden.
Hiermee onderscheidt de discrete wiskunde zich van de continue wiskunde, zoals analyse. De meeste objecten die bestudeerd worden binnen de discrete wiskunde zijn
aftelbare verzamelingen, zoals de natuurlijke getallen. De afgelopen decennia is de discrete wiskunde vooral opgekomen binnen de informatica omdat onderwerpen uit
de discrete wiskunde en de daarbij behorende notaties erg nuttig zijn om zaken en concepten uit te drukken met betrekking tot computeralgoritmes en programmeertalen.
Daarom wordt in de meeste informaticaopleidingen ook de nodige aandacht besteed aan discrete wiskunde. De grafentheorie is een deelgebied van de discrete wiskunde
dat zich bezighoudt met de studie van grafen.

Grafentheorie

Grafen worden veel toegepast in de informatica, bijvoorbeeld bij het modelleren van netwerken, het vinden van de kortste route in een netwerk, en bij patroonherkenning
Een graaf is een wiskundige abstracte structuur om relaties tussen objecten te modelleren. De meeste grafen bestaan uit twee objecten, de objecten in een systeem (vertices)
en de verbindingen (edges). Iets anders gezegd: Een graaf bestaat uit een verzameling punten, knopen genoemd, die door lijnen, ook wel zijden of bogen genoemd, met elkaar
verbonden kunnen zijn. Het bestuderen van deze grafen noemen wiskundigen de grafentheorie.

De belangrijkste concepten binnen de grafentheorie:

• Knopen en zijden; De basiscomponenten van een graaf. Knopen (of vertices) zijn de punten, en zijden (of edges) zijn de lijnen die de knopen verbinden.
  
• Gerichte en ongerichte grafen; In een gerichte graaf hebben de zijden een richting (pijlen), terwijl in een ongerichte graaf de zijden geen richting hebben.
  
• Gewogen grafen; Grafen waarbij aan de zijden gewichten zijn toegekend, vaak gebruikt om afstanden of kosten weer te geven.
  
• Bipartiete grafen; Grafen waarvan de knopen in twee disjuncte verzamelingen kunnen worden verdeeld, zodanig dat er geen zijden zijn tussen knopen van dezelfde verzameling.
  

Een graaf (G) kan in een formule, concreet en abstract worden beschreven. Een graaf bestaat uit een verzameling knopen of vertices (V) die zijn verbonden door een verzameling
linken of edges (E). In formulevorm ziet dit er als volgt uit:

• G = {V, E}
• V = {v1, v2, …, vn}
• E V x V = {e1, e2, …, en}
• e = (vx, vy)

Twee grafen noemen we “isomorf” als ze wiskundig gezien hetzelfde zijn. Dat wil zeggen dat de “structuur” van de grafen gelijk is, dus dat de knooppunten op dezelfde manier met elkaar verbonden zijn.
In een plaatje van een graaf betekent dat, dat het er alleen om gaat OF er een verbindingslijn tussen twee knooppunten loopt, en niet HOE die is getekend.

Twee voorbeelden met R-Shiny

In de applicatie ziet u twee visualisaties die met de grafentheorie te maken hebben:

1. Het Dijkstra model
Dit is een model met fictieve vliegroutes vanaf Amsterdam naar drie eindbestemmingen: Sydney, Tokio en Mexico.
De verschillende omstandigheden om en op de vliegroutes worden met een nummer aangeduid en deze gewichten zijn weer bepalend bij de keuze van de vliegroutes.
De nummers worden bij het maken met de R-Shiny ‘radioButtons’ van een bestemmingskeuze ‘at random’ aan de trajecten toegekend.
Telkens als u een bestemming aangeeft wordt met behulp van het Dijkstra algoritme automatisch een route in beeld gebracht.


Het Dijkstra model is een algoritme voor het vinden van de kortste paden tussen knooppunten in een gewogen grafiek, die bijvoorbeeld wegennetwerken kan voorstellen.
Het werd in 1956 bedacht door computerwetenschapper Edsger W. Dijkstra en drie jaar later gepubliceerd. Als de knooppunten van de grafiek bijvoorbeeld steden voorstellen,
en de kosten van randen de gemiddelde afstanden tussen paren steden die door een directe weg met elkaar verbonden zijn, dan kan het algoritme van Dijkstra worden gebruikt
om de kortste route tussen de ene stad en alle andere steden te vinden. Dit algoritme doet geen poging tot directe ‘verkenning’ naar de bestemming, zoals men zou verwachten.
Integendeel, het algoritme breidt zich vanaf het startpunt naar buiten uit en houdt interactief rekening met elk knooppunt dat dichterbij is in termen van kortste pad-afstand
totdat de bestemming wordt bereikt. Als het op deze manier wordt begrepen, is het duidelijk hoe het algoritme noodzakelijkerwijs de kortste weg vindt. Het algoritme van Dijkstra
wordt vaak gebruikt in grafieken waarbij de randgewichten positieve gehele getallen of reële getallen zijn. Het kan worden gegeneraliseerd naar elke grafiek waarbij de randgewichten
gedeeltelijk zijn geordend. In veel vakgebieden, met name kunstmatige intelligentie, staat het algoritme van Dijkstra of een variant daarvan bekend als uniform ‘cost search’ en
is het geformuleerd als een voorbeeld van het meer algemene idee van ‘best-first search’.

2. SUDOKU puzzels
Met behulp van een R-Shiny ‘actionButton’ wordt er telkens opnieuw een sudoku puzzel gegenereerd en getoond. Het tweede plaatje toont de oplossing van de puzzel.

Een sudoku is een puzzel bestaande uit negen bij negen vakjes die gegroepeerd zijn als negen blokken van drie bij drie vakjes. In de vakjes moeten de cijfers 1 tot en met 9 ingevuld worden
op zo’n manier dat in elke horizontale lijn en in elke verticale kolom en in elk van de negen blokjes de cijfers 1 tot en met 9 één keer voorkomen. In een aantal vakjes zijn de cijfers al ingevuld.
Een sudoku is dus een bijzonder geval van een Latijns vierkant. We spreken van een sudokugraaf, want elk punt (elke cel) is namelijk verbonden met de punten die horen bij de cellen uit dezelfde rij,
dezelfde kolom en hetzelfde blok.