Matrices en grafen > Grafen
123456Grafen

Voorbeeld 3

Bij een bepaalde graaf met vier knooppunten P, Q, R en S hoort een verbindingsmatrix C met de knooppunten van links naar rechts en van boven naar beneden in alfabetische volgorde.
Teken een bijpassende graaf als: C 2 = ( 3 1 1 0 1 2 1 1 1 1 2 1 0 1 1 1 ) .

> antwoord

De kentallen van C 2 geven het aantal tweestapswegen tussen twee punten van de graaf aan.

  • Er zijn 3 tweestapswegen van P naar P, dus P is met elk der andere punten verbonden.

  • Er is maar 1 tweestapsweg van S naar S, dus S is alleen met P verbonden.

  • Er zijn 2 tweestapswegen van Q naar Q, dus Q is met P en R verbonden.

  • Er zijn 2 tweestapswegen van R naar R, dus R is met P en Q verbonden.

Nu kun je de graaf maken.

Opgave 6

In Voorbeeld 3 zie je hoe je vanuit een gegeven tweestapsverbindingsmatrix C 2 de verbindingsmatrix C weer kunt terug vinden.

a

Ga zelf na, dat de getekende graaf aan de gegeven matrix C 2 voldoet.

b

Stel nu de verbindingsmatrix C op.

c

Controleer dat het kwadraat van de verbindingsmatrix C inderdaad de gegeven matrix is.

Opgave 7

Een groep van zes personen moet uit hun midden een woordvoerder kiezen. Ze houden een geheime stemming. Er mag maar op één persoon worden gestemd. De uitslag daarvan vind je in de volgende graaf:

Stel je voor dat het getal betekent dat iemand niet op de betreffende persoon heeft gestemd en dat het getal betekent dat hij of zij dat juist wel heeft gedaan. De pijl van A naar B betekent dat A op B heeft gestemd.

a

Is er bij elke uitslag van deze stemming sprake van een gerichte graaf?

b

Stel een bij de uitslag behorende stemmatrix K op.

c

Wie zou er worden gekozen? Leg uit hoe je dat met behulp van de stemmatrix kunt vaststellen.

Eén van de zes groepsleden vindt deze stemprocedure niet zorgvuldig genoeg. Zij stelt voor om ieder lid ook een stem met een "waarde" van te laten uitbrengen op de persoon die je absoluut niet ziet zitten als woordvoerder. Opnieuw mag iedereen maar op één persoon een negatieve stem uitbrengen. De graaf hiernaast geeft de negatieve keuzes weer.

d

Verwerk ook deze negatieve stemmen in een matrix N .

e

Hoe zou je de matrices K en N moeten combineren om uit te maken wie er woordvoerder wordt? Licht je antwoord toe.

f

Levert het combineren van beide matrices een eerlijker stemming op? Verklaar je antwoord.

verder | terug