hvad der gør en Euler kredsløb muligt ?

Definition

En Eulerske sti i en graf berører alle kant gang og kun én gang . En Eulerske kredsløb er en Eulerske sti , der starter og slutter på samme punkt. Denne type kredsløb blev først teoretiseret af matematiker Leonhard Euler . Han først beskrev dem , mens du arbejder på de syv broer af Konigsberg problem : Givet en bestemt serie af broer forbinder flere punkter , hvis det var muligt at konstruere en sti , der ville krydse hver bro kun én gang . Euler fastslået, at dette problem havde ingen løsning , der fastsætter grundlaget for grafteori .

Betingelser for en Eulerske kredsløb

For en Eulerske kredsløb skal være muligt , har ethvert punkt i grafen for at have et lige antal stier , der forbindelse til den. Det betyder, at en Eulerske kredsløb er muligt for enhver graf , hvor hver knude har 2 , 4 eller et tilsvarende antal linjer, der forbinder til den. Som en følge heraf tager den faktiske udformning og konfiguration af grafen ikke noget , alle , der rent faktisk betyder noget, er antallet af stier for hver linje .

Konstruktion af en Eulerske Sti til en graf

En graf kan have en Eulerske vej , hvis det følger to betingelser : det skal have alle sine stier i samme plan (tænk på et fly som en flad overflade , som en bordplade eller et stykke papir ) , og der er visse restriktioner på " hjørner " af grafen . Der kan ikke være mere end to hjørner , som har et ulige antal linjer , der kommer fra dem . Hvis disse betingelser er opfyldt , kan en Eulerske sti ske ved hjælp af en proces, der kaldes Fleury 's algoritme . Først skal du starte på en knude med et ulige antal stier , der fører fra det . Så kan du flytte langs en kant , at hvis du skulle slettet den , vil grafen fortsat være tilsluttet-medmindre der er noget andet valg. I dette tilfælde er kanten slettet . Ved udgangen af algoritmen , en Eulerske sti ( eller i nogle tilfælde , en Eulerske kredsløb ) er dannet .


Kommentarer

Vi ønsker, at dine argumenter og meninger er velkomne. Være objektiv og medfølelse. Mange mennesker læser hvad du skriver. Gør debat til en bedre oplevelse for både dem og dig selv. Mellem 20:00 og 08:00 det er lukket for kommentering og vi fjerner automatisk kommentarer med sjofle ord, defineret af vores moderatorer.

link:

  • Om os
  • Advertising
  • Fortæl redaktionen
  • Få nyhedsbreve
  • RSS-feed

Redaktør: Karin Christofferse
Nyheder redactor: Morten Nyberg

Kundeservice: Stig Ole Salomon,
Flemming Sørensen

Tel: +45 00 99 99 00
Fax: +45 00 99 99 01

© Copyright 2014 Einsten.net - All rights reserved.