Grafen

Inleiding

www.math4all.nl > MAThADORE-basic HAVO/VWO > 4/5/6 VWO wi-c > Discrete wiskunde > Matrices en grafen > Grafen > Inleiding

Probeer de vragen bij Verkennen zo goed mogelijk te beantwoorden.

Uitleg

www.math4all.nl > MAThADORE-basic HAVO/VWO > 4/5/6 VWO wi-c > Discrete wiskunde > Matrices en grafen > Grafen > Uitleg

Opgaven

1. Bekijk in de Uitleg hoe van de metroverbindingen tussen 6 stations in Amsterdam een graaf is gemaakt.
   1. Stel zelf de bijbehorende verbindingsmatrix `C` op .
   2. Bereken de graad van verbinding van deze graaf.
   3. Tussen welke waarden kan de graad van verbinding van een graaf liggen? Wanneer is er sprake van een hoge "dichtheid" van de verbindigen?
   4. Bereken `C^2`. Leg uit waarom deze matrix alle zogenaamde tweestapsverbindingen in de graaf weergeeft.
   5. Schrijf alle tweestapsverbindingen vanuit het Centraal Station op.
   6. Welke betekenis heeft de matrix `C + C^2`? Waarom komen er in deze matrix nog nullen voor?
   7. Welke driestapsverbindingen zijn er vanuit het Centraal Station mogelijk?
   8. Komen er in de matrix `C + C^2 + C^3` ook nog nullen voor? Waarom?


2. Onder de "diameter" van een graaf versta je het maximale aantal stappen dat nodig is om vanuit een willekeurig knooppunt in een willekeurig ander knooppunt te komen.
   1. Hoe groot is de diameter van de graaf van de vorige opgave?
   2. Van twee plaatsen die net zoveel stappen van elkaar verwijderd liggen als de diameter van de graaf bedraagt, zeg je dat ze diametraal liggen. Noem alle plaatsen die diametraal liggen.

Theorie

www.math4all.nl > MAThADORE-basic HAVO/VWO > 4/5/6 VWO wi-c > Discrete wiskunde > Matrices en grafen > Grafen > Theorie

Bestudeer eerst de Theorie. In de opgaven wordt je naar de Voorbeelden verwezen.

Opgaven

3. Bij een ongerichte graaf kun je een verbindingsmatrix opstellen. Die zegt iets over de mate waarin er verbindingslijnen zijn. In Voorbeeld 1 wordt zo'n verbindingsmatrix `C` gebruikt.
   1. Waarom is hier sprake van een ongerichte graaf?
   2. Reken zelf het voorbeeld na.
   3. De diameter (het maximale aantal stappen dat nodig is om van het éne knooppunt naar het andere te komen) is 2? Hoe zie je dat aan `C + C^2`?
   4. Welke driestapsverbindingen zijn er vanuit knooppunt `C`?
   5. Waarom zijn er maximaal 10 verbindingslijnen mogelijk? Welke verbindingslijnen ontbreken er?


4. Bekijk nu de graaf in Voorbeeld 2.
   1. Waarom is hier sprake van een gerichte graaf?
   2. Hoe kun je aan de directe-wegen-matrix `D` zien dat er sprake is van éénrichtingsverkeer?
   3. Bereken nu `D + D^2` en `D + D^2 + D^3` en leg met behulp van het resultaat uit dat de diameter van deze graaf 3 is.
   4. Geef een voorbeeld van een route die alleen in drie stappen mogelijk is.
   5. Waarom zijn er maximaal 20 directe wegen mogelijk? Hoeveel bedraagt nu de graad van verbinding?


5. Welke van de onderstaande grafen zijn gelijk?
   
   
   
   


6. In Voorbeeld 3 zie je hoe je vanuit een gegeven tweestapsverbindingsmatrix `C^2` de verbindingsmatrix `C` weer kunt terug vinden.
   1. Ga zelf na, dat de getekende graaf aan de gegeven matrix `C^2` voldoet.
   2. Stel nu de verbindingsmatrix `C` op.
   3. Controleer dat het kwadraat van de verbindingsmatrix `C` inderdaad de gegeven matrix is.


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 0 betekent dat iemand niet op de betreffende persoon heeft gestemd en dat het getal 1 betekent dat hij of zij dat juist wel heeft gedaan. De pijl van A naar B betekent dat A op B heeft gestemd.
   1. Is er bij elke uitslag van deze stemming sprake van een gerichte graaf?
   2. Stel een bij de uitslag behorende stemmatrix `K` op.
   3. 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 -1 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 volgende graaf geeft de negatieve keuzes weer:
   
   
   
   
   3. Verwerk ook deze negatieve stemmen in een matrix `N`.
   4. Hoe zou je de matrices `K` en `N` moeten combineren om uit te maken wie er woordvoerder wordt? Licht je antwoord toe.
   5. Levert het combineren van beide matrices een eerlijker stemming op? Verklaar je antwoord.

Verwerken

8. Op Tahiti, een eiland in de Grote Oceaan, bevindt zich alleen langs de kust een hoofdweg die alle plaatsen met elkaar verbindt.
   
   
   
   Je let in deze opgave alleen op de plaatsen Papeete (de hoofdstad), Punaauia, Papara, Papeari en Mahina.
   1. Teken een graaf waarin de genoemde plaatsen de knooppunten vormen en de verbindingslijnen aangeven of twee plaatsen rechtstreeks door de hoofdweg met elkaar verbonden zijn.
   2. Stel de bijbehorende verbindingsmatrix `C` op.
   3. Welke tweestapsverbindingen zijn er vanuit de hoofdstad Papeete?
   4. Bereken `C + C^2`. Welke betekenis heeft deze matrix en waarom komen er geen nullen in voor?
   5. Hoeveel bedraagt de graad van verbinding van deze graaf?
   6. Waarom is de "dichtheid" van deze graaf klein? Klopt dit met de graad van verbinding die je hebt gevonden?


9. In een ontwikkelingsland zijn de verbindingen vaak minimaal. In feite zijn er twee karakteristieke situaties:
   1. Er is in het land één belangrijke stad (meestal de hoofdstad) waar vandaan en naartoe alle verbindingen lopen.
   2. Er is een ringweg aangelegd die alle plaatsen met elkaar verbindt.
   Nu zeg je in een graaf dat er sprake is van minimale verbinding als weliswaar elk knooppunt met minstens één ander knooppunt is verbonden, maar er toch zo weinig mogelijk verbindingen zijn.
   1. Teken bij beide situaties een graaf. Gebruik bij elke situatie 6 knooppunten. Ga na of er bij beide sprake is van minimale verbinding.
   2. Bereken de graad van verbinding in elk van beide situaties.
   3. Bepaal van de beide grafen de diameter. Leg uit welk karakteristieke verschil er bestaat tussen de diameter in situatie 1 en die in situatie 2.
   4. Bekijk de vorige opgave nog eens. Van welke van beide situaties is daar sprake? Waarom is dat op een eiland als Tahiti ook de meest voor de hand liggende oplossing voor de verbindingen?


10. Bij een bepaalde graaf hoort een verbindingsmatrix `C`. Gegeven is:

    `C^2 = ((1 , 1 , 1 , 1 , 0),(1 , 1 , 1 , 1 , 0),(1 , 1 , 1 , 1 , 0),(1 , 1 , 1 , 1 , 0),(0 , 0 , 0 , 0 , 4))`

    1. Welke betekenis heeft het getal 4 in deze matrix?
    2. Teken een bijbehorende graaf. Zijn er meerdere mogelijkheden?
    3. Stel de bij die graaf horende verbindingsmatrix `C` op.
    4. Hoe groot is maximaal aantal stappen dat je nodig hebt om van het éne punt naar het andere te komen in deze graaf?


11. In een woestijngebied liggen een zestal plaatsen in de buurt van oasen. Ze onderhouden met elkaar een netwerk van radioverbindingen. Nu hebben radioverbindingen afhankelijk van de sterkte van de zendinstallatie een beperkt bereik. Het kan dus zijn dat de zender uit plaats A wel sterk genoeg om plaats B te bereiken, maar dat de zender in plaats B niet sterk genoeg is om plaats A te bereiken. De graaf geeft weer of vanuit een bepaalde plaats één van de andere bereikt kan worden met behulp van de radiozender.
    
    
    
    
    1. Waarom is er sprake van een gerichte graaf?
    2. Hoeveel uitzendingen zijn er minstens nodig om een bericht van E naar B te sturen door middel van de radiozenders?
    3. Stel een matrix `R` op waarin voor elk tweetal plaatsen staat vermeld of er een rechtstreekse radioverbinding bestaat.
    4. Bereken de matrix `R + R^2 + R^3`. Welke betekenis heeft deze matrix?
    5. Stel een matrix `A` op waarin voor elk tweetal plaatsen het minimale aantal radio-uitzendingen staat dat nodig is om een bericht van de ene naar de andere plaats over te brengen.
    6. Stel je voor dat je in één van deze plaatsen een zendinstallatie mag bouwen die alle andere plaatsen kan bereiken. In welke plaats zou je dat dan doen? Verklaar je antwoord.

Testen

12. In dit berggebied maakte men voor het transport vroeger gebruik van de rivieren en van bergpaden. De rivieren werden gebruikt als er stroomafwaarts goederen moesten worden vervoerd; de bergpaden werden gebruikt als het vervoer stroomopwaarts moest plaatsvinden.
    
    
    
    Je ziet hier de bergpaden en de rivieren waarmee de verbindingen werden onderhouden tussen een vijftal plaatsen. Het meer, waaraan A en B liggen, wordt voor vervoer in beide richtingen gebruikt.
    1. Teken een gerichte graaf van het stelsel van transportwegen tussen deze vijf plaatsen.
    2. Stel bij die graaf een passende directewegenmatrix `R` op.
    3. Welke betekenis heeft de matrix `R + R^2`? Bevat deze matrix nog nullen?
    Tegenwoordig worden de waterwegen niet langer voor vervoer van goederen gebruikt. Alle bergpaden zijn geasfalteerde wegen geworden waarlangs vrachtauto’s heen en weer rijden. Verder is er een snelweg met een grote brug langs het meer aangelegd die A en B met elkaar verbindt.
    4. Teken een nieuwe graaf van transportwegen voor deze situatie.
    5. Stel nu een bijpassende verbindingsmatrix `C` op.
    6. Vanuit punt D moet je om in B te komen via E rijden. Dit kun je een tweestapsverbinding vanuit D noemen. Schrijf alle tweestapsverbindingen vanuit B op.
    7. Hoe groot is de graad van verbinding van de graaf?
    8. Hoeveel nullen bevat de matrix `C + C^2`? Verklaar waarom dit zo is.