Seven Bridges van Königsberg

Het probleem van de zeven bruggen van Königsberg een probleem is geïnspireerd door een echte stad en een concrete situatie. Königsberg, eenmaal in Oost-Pruisen en nu een Russische enclave aan de Oostzee bekend als Kaliningrad, wordt doorkruist door de rivier Pregel en haar zijrivieren en heeft twee grote eilanden die zijn verbonden met elkaar en met de twee belangrijkste gebieden van de stad met zeven bruggen.

In de loop der eeuwen is herhaaldelijk voorgesteld de vraag of het mogelijk is met een wandeling naar een pad dat elke brug en slechts één keer kruist volgen en terug te keren naar het beginpunt. In 1736 geconfronteerd Leonhard Euler dit probleem blijkt dat de wandeling onmogelijk was uitgegaan.

Het lijkt niet op een historische basis hebben, maar eerder om een ​​urban legend, de uitspraak dat in 1750 de rijke burgers van Königsberg zondag passeggiassero voor hun steden proberen tevergeefs om het probleem op te lossen zijn.

Setting en oplossing van Euler

Euler heeft de verdienste van het probleem te hebben geformuleerd in termen van grafentheorie, abstraheren van de specifieke situatie van Königsberg; eerste geëlimineerd hij alle risico's, met uitzondering van de stedelijke gebieden afgebakend door de rivier de armen en bruggen die hen verbinden; secundair verving hij elk stedelijk gebied met een punt, nu genaamd de vertex of knooppunt en elke brug met een lijn segment, genaamd rand, boog of verbinding.

 → →

Vertegenwoordiging

Euler vertegenwoordigde de layout van de zeven bruggen met zoveel lijnen tussen de vier belangrijke gebieden van de stad, zoals in het eerste beeld. Merk op dat van de knooppunten A, B en D heengaan drie bruggen; uit knooppunt C, echter vijf bruggen. Dit zijn de graden van de knooppunten, respectievelijk, 3, 3, 5, 3.
Alvorens een conclusie, Euler gespeculeerd de verschillende situaties van de gebieden en bruggen: met vier knopen en vier bruggen zo laag mogelijk, bijvoorbeeld door A, en gaat terug door de bruggen slechts éénmaal. De mate waarin elk knooppunt een even getal. Als je begint met A tot D te bereiken, zal elk knooppunt gelijk zijn met uitzondering van twee knooppunten van oneven graad rang. Op basis van deze observaties, Euler vestigde de volgende stelling:

Daarom is het onmogelijk om te dekken Koningsbergen zoals vereist door de scriptie, omdat alle knooppunten oneven graad.

Opgemerkt wordt dat de grafiek theorie nauwe verbindingen met de topologie: de vorm van een grafiek of beter is dan een afbeelding van een grafiek of een variant daarvan door het verplaatsen van de hoekpunten en verstoren de lijnen die hen verbinden worden gewijzigd, teneinde handhaven de werkelijke verbindingen. Is niet als een koppeling kijkt recht of gebogen en zelfs als een hoekpunt is aan de ene of de andere kant ten opzichte van een verbinding van aangrenzende hoekpunten.

Euler aangetoond dat voor een grafiek om elk van een pad met de gewenste eigenschappen is mogelijk als en alleen als de grafiek niet hoekpunten die zijn bereikt door een oneven aantal randen. Zo'n reis wordt genoemd Eulerian circuit. Aangezien de grafiek opzichte Königsberg vier van deze hoekpunten, maakt de weg niet.

Als u de eis dat het begin en eindpunt samenvallen, dan kan er geen één of twee leiders geraakt door een oneven aantal randen vallen. Een dergelijk pad Euler pad genoemd.

Onder de grafiek Euleriaanse herinneren allemaal compleet grafieken van oneven orde, de Ster van David en kromzwaarden van Allah. Geen van volledige grafieken van zelfs bestelling plaats Eulerian.

Voor een bespreking van het probleem alleen wiskundige v. Eulerian Multigraph.

Belang in de geschiedenis van de wiskunde

In de geschiedenis van de wiskundige probleem van de bruggen van Königsberg is een van de eerste problemen grafentheorie formeel besproken; het kan ook worden beschouwd als een van de eerste problemen met betrekking tot de topologie. Je kan echter niet worden beschouwd als een van de eerste problemen combinatoriek, andere gebieden van de wiskunde waaraan grafentheorie gemaakt voor potentiële Als eerste combinatorische problemen vóór de achttiende eeuw aangepakt.

De vergelijking tussen een schematische kaart van Konigsberg en ook de weergave van de grafiek die het probleem vat is een goede indicatie van de gedachte dat de topologie zou de rigide vorm van de onderzochte voorwerpen.

Variaties

De oorspronkelijke verklaring van het probleem betreft niet geïdentificeerd hoekpunten, die wordt alleen gekenmerkt door hun connecties. Er zijn variaties op dit thema nuttig om het probleem in het onderwijs en die zorg aan de hoekpunten van de grafiek met de personages en rollen identificeren voeren zijn.

Er staat dan ook dat aan de noordkant van de stad staat het Schloß, het kasteel voor degenen die nog niet weten het Duitse woord, en die van Prince Blue is gelegen aan de zuidelijke oever van de Rode Prins; de twee beginselen zijn broers, maar het is een zaak van de broers-messen; Oost-eiland is de Kirche, de kerk, de thuisbasis van de bisschop; Uiteindelijk in het centrale eiland is een Gasthaus, een taverne. Zoals we later bespreken de relatie tussen de notabelen van de stad, waaronder moeten realistisch worden beschouwd als de verhuurder, zijn ze niet altijd even makkelijk.

Zorgvuldig in chronologische volgorde van de feiten, moet eraan worden herinnerd dat veel inwoners van de stad vroeger de avond enigszins beperken het Gasthaus en vervolgens betast het bedrijf noemde het passeren van de brug; Sommige later teruggekeerd naar hun succes met meer plengoffers te vieren, maar niet bevredigend uitleggen hoe ze in staat waren om te zeggen zonder te weten hoe u de wandeling in het daglicht te herhalen.

De achtste brug van Prince Blue

Prince Blue, na analyse van het systeem van de bruggen met behulp van grafentheorie, is overtuigd van de onmogelijkheid van het passeren van de bruggen. Hij besluit om in het geheim bouwen van een brug die hem zal toelaten om de achtste in de avond naar de bruggen passeren vanaf zijn Schloß en eindigt bij het Gasthaus waar je kan bogen op zijn succes; en ook zorgt ervoor dat de Red Prince niet in staat is om hetzelfde te doen van zijn Schloß.

  • Waar hij bouwde de achtste brug Prince Blue?

De negende brug de Red Prince

The Red Prince, imbufalito voor de verhuizing broer, begrijpt dat hij kan reageren pas na het bestuderen van de grafentheorie; na zorgvuldige studie besluit hij om in het geheim te bouwen een andere brug die hem in staat stellen om de brug over te steken om zijn Schloß Gasthaus hier te komen en neem de zeik zijn broer, die onmogelijk om de bruggen op zijn eigen manier passeren.

  • Waar hij bouwde de negende brug de Red Prince?

De brug van de tiende bisschop

De bisschop moest de dure geschil stad met groeiende irritatie bij te wonen. Het leidde tot de vorming van twee facties herrieschoppers en heeft toename van het aantal bezoekers van de Gasthaus overdreven, ten nadele van de openbare orde. Dus ook hij na een zorgvuldige studie van grafentheorie, besluiten tot een tiende brug die het mogelijk maakt alle burgers om alle bruggen passeren en terug te keren naar hun eigen huis in de rustige familiebanden te bouwen.

  • Waar hij bouwde de tiende brug de bisschop?

Oplossingen

Verminder de stad, zoals hierboven, in een grafiek. Verven elk knooppunt, zoals in het klassieke probleem geen wandeling Euler mogelijk. Alle vier nodes een oneven aantal ribben.

De achtste brug Prince Blue

Euler wandelingen zijn mogelijk wanneer precies twee knooppunten beschikken over een oneven aantal randen, die zijn precies knooppunten start en het einde van de wandeling. Aangezien het probleem slechts vier knooppunten, allemaal met oneven graad, de wandeling begint en eindigt in het blauw knooppunt knooppunt oranje. Het is daarom noodzakelijk om een ​​nieuwe rand te trekken tussen de twee andere knooppunten. Omdat zij formeel een oneven aantal randen, moet u een even aantal randen te creëren in alle knooppunten die niet zijn de eerste en laatste. Een verandering van de pariteit van even graad in gelijke mate. Anders zou het genoeg zijn om een ​​brug die vertrok van wit naar oranje te bouwen. Zo had slechts twee punten een oneven aantal bruggen.

De negende brug Prince Rosso

Het probleem opgelost brug achtste, negende brug heeft een eenvoudige oplossing. Het vereist dat u om de rode knoop te gebruiken als een punt van vertrek en aankomst als de oranje. Om de pariteit van de knooppunten rode en blauwe wijzigen ontwerpt een rand tussen de twee.

De brug van de tiende bisschop

De tiende brug gaat in een iets andere richting. Bisschop wil dat elke burger terug naar het beginpunt. Dit is een Euleriaanse pad en vereist dat alle knopen van dezelfde rang. Nadat de oplossing van het negende brug knopen rood en oranje oneven mate zodat zij door toevoeging van een nieuwe rand ertussen moet worden gewijzigd.

(0)
(0)
Commentaren - 0
Geen reacties

Voeg een Commentaar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tekens over: 3000
captcha