communicatienetwerk

© h.hofstede (h.hofstede@hogeland.nl)

Een communicatienetwerk.

Je wilt natuurlijk dat een communicatienetwerk zo stabiel en betrouwbaar mogelijk is. Dat betekent dat je niet graag wilt dat, het hele netwerk niet meer werkt als er één verbinding uitvalt.

Links staat een netwerk waarin elk knooppunt is verbonden met elk ander knooppunt, dus het netwerk klopt. Maar zodra er een lijn of knooppunt uitvalt is meteen niet meer elk punt bereikbaar. Rechts heb je dat probleem niet (kenners herkennen natuurlijk direct graaf K₆). Maar ja, rechts zijn wel veel meer verbindingslijnen nodig. En dat is duur.....

De graaf links heet een boom, en eigenschappen daarvan zullen we later bekijken. Deze les kijken we naar iets beter verbonden grafen. We gaan in het algemeen bekijken hoe we een n-verbonden netwerk kunnen ontwerpen in een situatie van k knooppunten (en dan niet n = 1 want dat is de linkerfiguur).

Hoe ontwerp ik bij k knooppunten een n-verbonden graaf (n > 1)
met zo weinig mogelijk verbindingslijnen?

Eerst kunnen we vaststellen dat het aantal benodigde verbindingslijnen minstens gelijk is aan ¹/₂ • n • k.
Immers: vanuit elk van de k knooppunten moeten minstens n verbindingslijnen lopen, en elke verbindingslijn zit aan twee knooppunten vast.

We zullen een methode bekijken om zo'n graaf met precies ¹/₂ • n • k verbindingslijnen te ontwerpen. Dat is dan meteen een optimale graaf, immers minder is onmogelijk.
Voor dat ontwerpen bekijken we drie verschillende gevallen.

geval 1: n is even

Noem de knooppunten 1, 2, ..., k , 1, 2, ..., k
Verbind twee knooppunten met elkaar als hun afstand in deze rij gelijk is aan ¹/₂n of minder.

Bijvoorbeeld: in een 6-verbonden graaf met 10 knooppunten verbind je twee knooppunten met elkaar als hun afstand 3 of minder is.
Dus wordt knooppunt 3 verbonden met 4, 5, 6 en 2, 1, 10. Zó dus:

Hiernaast zie je de graaf die dat oplevert.

geval 2: n is oneven, k is even.

Maak eerst de graaf met n één lager zoals hierboven.
Voeg daarna extra verbindingslijnen toe: vanaf elk knooppunt naar het knooppunt met afstand ¹/₂k in de rij (dus "die aan de overkant"). Ga zelf maar na dat het aantal verbindingslijnen dan weer ¹/₂ • n • k is
Hieronder zie je de 5-verbonden graaf met 10 knooppunten.

geval 3: n is oneven, k is oneven.

Maak weer eerst de graaf met n één lager zoals hierboven.
Voeg daarna extra verbindingslijnen toe:
• vanaf knooppunt 1 naar de knooppunten met afstand. ¹/₂(k ± 1) in de rij   (dus "die beiden aan de overkant").
• vanaf de knooppunten tussen nr. 1 en nr. ¹/₂(k + 1): naar het knooppunt met afstand ¹/₂(k + 1) in de rij
    ("één voorbij de helft")
Ga zelf maar na dat het aantal verbindingslijnen dan weer ¹/₂ • n • k is
Hieronder zie je de 5-verbonden graaf met 9 knooppunten.

Gewogen verbindingslijnen.

Dit wordt een erg korte paragraaf.
Het probleem is "Is er een methode om bij gewogen verbindingslijnen de n-verbonden graaf met k knooppunten te ontwerpen, zodat het totale gewicht minimaal is?"

nee.