de universiteiten van poldavië

[redwasp]

vrede,

niet zo lang geleden werd ik door mijn goede vriend e.s.pondiczery uitgenodigd om een serie lezingen te geven in de universiteiten in poldavië. de eerste lezing was natuurlijk aan het royal institute of poldavia, daarna volgden alle andere universiteiten, in de andere grote steden.

iedereen weet dat er in poldavië tussen iedere twee universiteitssteden precies één spoorbaan loopt, en dat dit ook de enige spoorbanen in het land zijn. die spoorbanen zijn zo schitterend, dat we alleen met de trein reisden.

nadat ik alle universiteitssteden had aangedaan, bleek dat ik overal vergeten was een handttekening te zetten. ik moest dus elk van die steden nog eens opnieuw aandoen. dat waas op zich prettig, want na mijn tweede rondrit had ik alle spoorbanen precies één keer gebruikt.

als je nu weet dat een spoorwegbrug heel duur is, en dat het aantal bruggen dus tot het strikte minimum beperkt is. hoeveel spoorwegbruggen zijn er dan in poldavië

vrede,

korneel

[laurensje]

nul

[bgf324]

waar ligt da?

[redwasp]

vrede,

Oorspronkelijk geplaatst door laurensje

nul

o? leg uit.

Oorspronkelijk geplaatst door bgf324

waar ligt da?

poldavië heeft het grote voordeel niet te bestaan.

vrede,

redwasp

[Renesse]

Ah, aangezien het niet bestaat, kunnen er dus geen bruggen zijn

[Knipp]

intuïtief denk ik dat er vijf universiteitssteden zijn, en met die voorzet kan je de oplossing wel binnen koppen denk ik

[Jazeker]

Brug of tunnel... ze weten het nog niet in A'pen, laat staan in Poldavië.

De vraag moet dus zijn hoeveel referenda er zijn geweest en met hoeveel ervan ook rekening werd gehouden.

[Knipp]

op dit forum worden er dagelijks tientallen smoezen verzonnen om gebrek aan inzicht te camoufleren ;
benieuwd naar de volgende smoes

[Firestone]

Oorspronkelijk geplaatst door Knipp

intuïtief denk ik dat er vijf universiteitssteden zijn, en met die voorzet kan je de oplossing wel binnen koppen denk ik

Het moeten er inderdaaf vijf zijn.
Nu nog het netwerk ontwerpen.
Ik gok op één brug, maar mijn ingenieurs zijn nog bezig met het ontwerp.

[Knipp]

Mijn smoezen fluisteren vijf.

[Firestone]

Hebbes !

Wel in de veronderstelling dat de twee lussen vertrekken en aankomen in de stad waarin het royal institute of poldavia zich bevindt.

[Knipp]

Mijn tekeningetje heeft tien lijnen en die snijden elkaar in vijf punten.
Maar da's msschn te rechtlijnig gedacht ?

[Firestone]

Zoiets:

[Knipp]

't Is de aard van het beestje, ik denk altijd vier bruggen te ver ....

*** onthoofdt vier fluisterende smoezen ***

[Knipp]

Oorspronkelijk geplaatst door Firestone

Zoiets:

Bijlage 61687

Ja. Is juist.
De hoofdstad mag ook buiten vierkant liggen, maakt ni uit denk ik.

Vier bruggen bespaard Firestone.

[vlijmscherp]

en nu wat uitleg aub???

[Knipp]

Oorspronkelijk geplaatst door vlijmscherp

en nu wat uitleg aub???

Ik mag niet. Ik ben geen lid van de Orde

[jevaly]

Oorspronkelijk geplaatst door vlijmscherp

en nu wat uitleg aub???

Vooreerst merken we op dat dit een complete graaf probleem is (en we maken de triviale assumptie dat een brug enkel gebouwd wordt bij het kruisen van twee spoorlijnen).
Dit betekent concreet dat er n(n-1)/2 spoorlijnen, met n het aantal universiteiten.
Vermits we elke universiteit net twee keer bezoeken moet het aantal spoorlijnen gelijk zijn aan 2n.
Dit geeft de volgende vergelijking:
n(n-1)/2 = 2n
Dit heeft twee oplossingen: n = 0 (er zijn geen universiteiten in Poldavië)
en n = 5

Er vanuit gaande dat onze vriend korneel geen fantast is (en er dus wel degelijk universiteiten in Poldavië zijn) gaan we nu op zoek naar het genus van deze complete graaf. Uit de stelling van Kuratowski ("een planaire graaf kan de subgraaf K5 en K3,3 niet bevatten) volgt onmiddellijk dat het aantal bruggen niet nul kan zijn. Uit de oplossing van Firestone blijkt dan dat 1 het minimaal aantal bruggen is (al kan men dat ook afleiden uit de simpele vaststelling dat de planaire graaf K4 een subset is van deze graaf).

extra: de oplossing van firestone gaat uit van kromme lijnen. Er is een oplossing die enkel gebruik maakt van rechte spoorwegen, wat de kost voor de Poldavische spoorwegen nog verder zou drukken. Welke?

[Knipp]

Ook zonder wiskundige opleiding kom je ver.

Elk stuk spoor wordt maar 1 keer gereden.
Bij het eerste bezoek zijn per stad al twee stukken spoor gereden.
Gekomen via een stuk. En vertrokken via een ander.
Bij het tweede bezoek hebben we nog twee andere stukken spoor nodig.
We moeten arriveren via een andere weg, en weer vertrekken via nog een andere weg.
Dat geeft vier sporen totaal per stad.
( en niet meer dan vier, of we kunnen ze niet allemaal afsporen in twee bezoekrondes )
Elke stad dus verbonden met vier andere.
Hence : 5 steden.

Simpelst mogelijk tekeningetje maken dan van zo'n netwerk.
Dat gaf mij vijf snijpunten.

De enige inspanning die ik nog had moeten doen : kan ik snijpunten elimineren door een traject anders te leggen ?
Dat zie je vrij makkelijk, zoveel mogelijk trajecten 'buitenom' doen gaan.
Zie tekeningetje v Firestone.

---

nu es kijken naar die extra ...

[Knipp]

Oorspronkelijk geplaatst door jevaly

extra: de oplossing van firestone gaat uit van kromme lijnen. Er is een oplossing die enkel gebruik maakt van rechte spoorwegen, wat de kost voor de Poldavische spoorwegen nog verder zou drukken. Welke?

zo op 't eerste zicht zie ik alleen een randgeval : vijf steden die op een rechte lijn liggen en op die lijn vier sporen leggen dan