Spectrale grafentheorie

Abstract

Deze masterproef richt zich op de wiskundige takken lineaire algebra en grafentheorie en de brug tussen de twee. Een graaf biedt een krachtig model voor domeinen zoals netwerken, wiskunde, biologie... en het is interessant om op grootschalige problemen algebraïsche methodes te kunnen toepassen. Bijvoorbeeld, in netwerkanalyse kan de structuur van een sociaal netwerk worden onderzocht om invloedrijke personen te identificeren. Zo kan een graaf geschreven worden als een adjacency matrix of Laplaciaan, waarop lineaire algebra kan toegepast worden. Zo kan de tweede kleinste eigenwaarde van de Laplaciaan (een kenmerk van de matrix) bijvoorbeeld waardevolle informatie geven over de samenhang en onderlinge connectiviteit van de graaf.

De motivatie van het werk is om te achterhalen of de eigenwaarden van deze matrices meer waardevolle informatie kunnen bieden dan de inverse van de matrix van een graaf. Om dit te onderzoeken, wordt een literatuurstudie over spectrale grafentheorie gepresenteerd, inclusief een eigen interpretatie van bewijzen en visuele voorbeelden. Daarnaast biedt de proef een basis in lineaire algebra als introductie tot de gebruikte methoden. Verder wordt er gekeken naar de praktijk en hoe de eigenwaarden van een matrix bepaald worden.

De besproken eigenschappen wijzen er inderdaad op dat eigenwaarden unieke inzichten kunnen bieden op een graaf. Het is echter niet aangetoond of dit ook met een inverse operatie zou kunnen.