Six Degrees en andere netwerken

Je hebt vast wel eens gehoord van six degrees of separation : binnen zes connecties ben je verbonden met iedereen op aarde. Van jou naar al je vrienden, familie, kennissen en iedereen die je een keer een hand hebt gegeven is de eerste stap. Van hen naar hun vrienden, kennissen, etc, is de tweede stap. En zo ben je altijd in of binnen zes stappen bij wie dan ook (je favoriete popster of acteur, of juist iemand behorend tot een stam die aan de Amazone leeft). In het programma 'De wereld rond in 6 stappen' probeert iedere week een duo om een vooraf vastgestelde beroemdheid te bereiken via 6 tussenpersonen.

Als je dit principe uit wilt tekenen gebruik je waarschijnlijk elk persoon als een puntje en hebben mensen die elkaar kennen een lijntje tussen hun beide puntjes. Zo’n figuur heet een graaf en grafen kun je voor ontzettend veel dingen gebruiken. Een totaal ander voorbeeld van een graaf is het verkeer, zowel op de weg als via internet, of alle relaties die er zijn of zijn geweest op een high school. Zo’n netwerk kan er erg ingewikkeld en zelfs artistiek uitzien zoals het Center for Complex Network Research laat zien in hun gallery.

Het principe van een graaf is erg simpel, je hebt punten en verbindingen daartussen, en eventueel nog wat eigenschappen, maar wiskundig gezien kunnen ze ook op zo’n manier beschreven worden dat je er heel handig aan kunt rekenen. Zo kun je bepalen wat de kortste route is voor een postbode die z’n ronde doet!

Een van de bekendste problemen in de grafentheorie is al zo’n 300 jaar oud. Dit is het Koningsberger bruggenprobleem: de stad Koningsberg heeft vier verschillende regio’s met daartussen zeven bruggen; hoe kun je een rondje lopen waarbij je in alle vier de regio’s komt en elke brug maar één keer passeert? En waarom kan het wel of niet?

Een ander probleem behandelt eerder de ruimtes tussen de lijnen dan de lijnen zelf van een graaf: hoeveel kleuren heb je nodig de graaf in te kleuren terwijl vlakken die elkaar raken nooit dezelfde kleur hebben? Kortom: hoeveel kleuren heb je nodig voor een atlas?

Probeer zelf maar eens een antwoord op deze problemen te vinden!

Handige links:

• Six Degrees of Separation

Opmerkingen

Heb je vragen of lijkt het je leuk hier je profielwerkstuk over te doen? Neem dan contact op met het Betasteunpunt.