Directe verbindingen

Beste Wisfaq,

Ik zit met de volgende vraag: Ik moet bepalen of het mogelijk is voor een luchtvaarmaatschappij om een directe verbinding te onderhouden tussen elke stad in een set ter grootte van m en r andere steden in de set in de volgende gevallen:

m en r zijn beide oneven
m en r zijn beide even

Ik weet eigenlijk niet waar ik moet beginnen. Ik heb een een aantal figuren getekend en vermoed dat beide gevallen niet mogelijk zijn. Echter lukt het met niet om het in zijn algemeenheid aan te tonen en ik hoop dat jullie me hier mee kunnen helpen.

Vriendelijke groet,

Steven Bakker

steven
Student universiteit - zaterdag 24 februari 2007

Antwoord

Dag Steven,

De vraag is dus: kan je een r-reguliere graaf maken met m toppen. r-regulier betekent dat elke top (dus elke stad) verbonden is met exact r andere toppen.

Geval 1: m en r zijn beide oneven. Dit kan inderdaad niet: als elk van de m toppen moet verbonden zijn met r andere, betekent dit dat er m*r (= oneven getal) keren een top met een andere wordt verbonden. Echter, een boog (dus een verbinding) verbindt telkens twee steden, dus die m*r zou zeker even moeten zijn, een strijdigheid.

Geval 2: je kan meteen zien dat dit zeker voor een aantal gevallen mogelijk is. Denk bijvoorbeeld aan de situatie met r=0. Of minder triviaal: m=4 en r=2, verbind A met B; B met C; C met D; D met A. Nu, hoe toon je aan dat dit mogelijk is voor willekeurige r (kleiner dan m)? Dat kan bv op deze manier:

- Kies willekeurige r (even). Teken de complete graaf met r+1 toppen (dus r+1 toppen die onderling allemaal verbonden zijn). Voeg nu een extra top toe (noem die A). Neem nu r/2 willekeurige, disjuncte bogen in je complete graaf, en schuif telkens die nieuwe top A ertussen. Dus als je de boog B-C kiest, dan vervang je die door de bogen B-A en A-C. Dit verandert niks aan het aantal bogen dat vertrekt in B of in C, en de nieuwe top A is ook in orde, want ook daar vertrekken nu 2*r/2=r bogen.

- Inductie: blijf dit procédé herhalen, je r blijft vast maar het aantal toppen mag eender wat zijn, zolang het maar groter is dan r.
NB je moet wel nog even nagaan dat je altijd r/2 disjuncte bogen kan kiezen (dus deze bogen mogen geen eindpunten gemeen hebben), maar dat is niet zo moeilijk.

Overigens: ook m even en r oneven is geen probleem. Dat kan je op een soortgelijke manier aantonen, al moet je per inductiestap wel twee toppen tegelijk toevoegen (m kan immers enkel even zijn), elk van die toppen in (r-1)/2 bogen tussenschuiven, en die twee ook onderling nog eens verbinden. Maar dat was dus niet gevraagd.

Groeten,
Christophe.

Christophe
zondag 25 februari 2007

©2001-2024 WisFaq