Matrices en grafen

Matrices en grafen > Grafen

Verwerken

Opgave 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.

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.

Stel de bijbehorende verbindingsmatrix $C$ op.

Welke tweestapsverbindingen zijn er vanuit de hoofdstad Papeete?

Bereken $C + C^{2}$ . Welke betekenis heeft deze matrix en waarom komen er geen nullen in voor?

Hoeveel bedraagt de graad van verbinding van deze graaf?

Waarom is de "dichtheid" van deze graaf klein? Klopt dit met de graad van verbinding die je hebt gevonden?

Opgave 9

In een ontwikkelingsland zijn de verbindingen vaak minimaal. In feite zijn er twee karakteristieke situaties:

Situatie 1: Er is in het land één belangrijke stad (meestal de hoofdstad) waar vandaan en naartoe alle verbindingen lopen.
Situatie 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.

Teken bij beide situaties een graaf. Gebruik bij elke situatie $6$ knooppunten. Ga na of er bij beide sprake is van minimale verbinding.

Bereken de graad van verbinding in elk van beide situaties.

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.

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?

Opgave 10

Bij een bepaalde graaf hoort een verbindingsmatrix $C$ . Gegeven is:

$C^{2} = (\begin{matrix} 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 \end{matrix})$

Welke betekenis heeft het getal $4$ in deze matrix?

Teken een bijbehorende graaf. Zijn er meerdere mogelijkheden?

Stel de bij die graaf horende verbindingsmatrix $C$ op.

Hoe groot is maximaal aantal stappen dat je nodig hebt om van het éne punt naar het andere te komen in deze graaf?

Opgave 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.

Waarom is er sprake van een gerichte graaf?

Hoeveel uitzendingen zijn er minstens nodig om een bericht van $D$ naar $F$ te sturen door middel van de radiozenders?

Stel een bij de graaf passende wegenmatrix $R$ op.

Bereken de matrix $R + R^{2} + R^{3}$ . Welke betekenis heeft deze matrix?

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.

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.

verder | terug