In graafiteoria , Eulerin polku tai Eulerin polku , tai jopa Eulerin ketju , joka suuntaamattoman kuvaaja on polku , joka kulkee kaikki reunat , kerran reuna. Nimi annettiin viitaten Leonhard Euleriin . Jos tällainen polku palaa lähtöpisteeseen, puhumme Eulerian radasta tai Eulerian-syklistä tai jopa Eulerian-kiertueesta . Kaavion, joka hyväksyy Eulerian- piirin, sanotaan olevan Eulerian . Jos se myöntää Eulerian- kurssin , sen sanotaan olevan semi-Eulerian .
Eulerin polun käsitettä havainnollistetaan kirjekuoren suunnittelun ongelmalla. Kyse on kirjekuoren piirtämisestä nostamatta kynää ja piirtämättä samaa viivaa useita kertoja. Voimme mallintaa piirustuksen alla olevan kaavion avulla. Eulerin polku vastaa kuvaajan piirtämistä arkille nostamatta kynää.
Esimerkki kaaviosta, joka hyväksyy Eulerin polun.
Käsin piirustus nostamatta kynää
Seitsemän Königsbergin sillan ongelma on ongelma siitä, voidaanko Königsbergin kaupungin jokaisen sillan ylittää yhdellä kertaa, kerran jokaisella sillalla. Kuten alla olevassa kuvassa on esitetty, ongelma mallinnetaan seuraavan kaavion avulla: sillat muodostavat harjanteet ja saaret ja pankit kärjet. Koska tämä kaavio ei hyväksy Eulerin polkua, ongelmalla ei ole ratkaisuja.
|
Voimme myös tarkastella polyhedronin , esimerkiksi oktaedrin , kuvaajaa . Monikulmion kärjet ja reunat ovat vastaavasti kaavion kärjet ja reunat.
Aste on kärki on särmiä saapuvien tälläkärkipisteellä (tapaus reunat). Seuraavissa kaavioissa ilmoitetaan jokaisen kärjen asteet.
Kaavio 7 Königsbergin sillasta ja toinen kaavio kertoo viidestä kammiosta. Nämä kaaviot eivät hyväksy Eulerin polkuja. Näytetyt luvut ovat astetta.
1. ja 4. Kuvaajat, joilla on Eulerin polku, mutta ei Eulerin piiriä. 2. Kuvaaja ilman ratkaisua. 3. Kuvaaja, jolla on Eulerian-piiri.
Eulerin lause, jota kutsutaan myös Euler-Hierholzer-lauseeksi, tulee kahdeksi luonnehdinnaksi:
Euler osoitti tarvittavat olosuhteet vuonna 1736. Saksan matemaatikko Carl Hierholzer on julkaissut alla olevan täydellisen todistuksen vuonna 1873. Eulerille on joskus annettu vastaavuus, kuten Diestelin graafiteoria-kirjassa (katso Th. 1.8.1.). Kaksi suoraa suuntaa esitetään seuraavasti.
Oletetaan, että on olemassa Eulerin polku ja valitse se poistamalla käytetyt reunat. Jokaisesta huipun yli kulkevasta kohdasta (paitsi alussa ja lopussa) tähän huipulle saapuva harjanne ja siitä poistuva harjanne poistetaan. Siten, alku- tai loppupistettä lukuun ottamatta, asteen pariteetti pysyy muuttumattomana. Polun lopussa kaikki reunat poistetaan, mikä antaa mahdollisuuden tehdä johtopäätös pisteiden pariteetista.
Epäsuorat merkitykset, toisin sanoen, voidaan osoittaa seuraavasti.
Näytetään se, kun kaikki kärjet ovat tasaisessa asteessa. Aloitetaan mistä tahansa kaavion kärjestä s 0 . Lainataan reunoja poistamalla ne kaaviosta niin kauan kuin mahdollista. Koska asteet ovat tasaiset, palasimme välttämättä pisteeseen s 0 ja löysimme piirin s 0 - s 1 - ... - s 0 . Jos enempää reunoja ei ole jäljellä, meillä on Eulerian piiri. Muuten aloitamme prosessin uudelleen saadaksemme näkyviin toisen piirin, kärjestä i, josta reuna alkaa. Saamme sitten toisen piirin s i - ... - s i , jonka olemme juuri liittäneet edelliseen piiriin s i : n tilalle :
s 0 - s 1 - ... - s i - ... - s i - s i + 1 - ... s 0 .
Toistamme prosessin, kunnes olemme käyttäneet kaikki reunat ja saamme Eulerian-piirin.
Voimme itse asiassa kirjoittaa tietokoneohjelman Eulerin polun tai piirin laskemiseksi, jos sellaista on. Keskustellaan Hierholzerin vuonna 1873 julkaisemasta algoritmista , joka seuraa hänen todisteensa ajatusta (katso epäsuora merkitys yllä). Se toistaa piirien poiminnan, jotka liimataan rakentamaan Eulerian piiri. Tämä algoritmi voidaan toteuttaa, jotta algoritmi olisi lineaarisessa ajassa reunojen lukumäärässä (katso esimerkki 2.5.2 ja algoritmi 2.3.1 tuumaa). Tätä varten seuraavat toiminnot täytyy suorittaa vain vakiona:
Tätä varten riittää, että ylläpidetään tehokkaasti kaksoislinkitetyillä luetteloilla :
Pierre-Henry Fleury antoi toisen algoritmin vuonna 1883, mutta jonka toteutus tietokoneella olisi vähemmän tehokasta kuin Hierholzerin algoritmi. Hänen ajatuksensa on rakentaa piiri lainaamalla joka kerta etusijalla reuna, jonka poisto ei irrota kuvaajaa.
Yllä olevat tulokset viedään suunnattuihin kaavioihin. Tällaisen kuvaajan sanotaan olevan eulerialainen, jos sillä on seuraava ominaisuus:
Voimme järjestää kaavion kaaret siten, että kaksi peräkkäistä reunaa järjestyksen suhteen - missä järjestyksen viimeistä ja ensimmäistä reunaa pidetään peräkkäisinä - ovat peräkkäisiä kaaviossa.Tässä ominaisuus tarkoittaa jälleen kerran, että voimme "kulkea" kuvaajan seuraamalla kaaria niiden alkupäästä päätepäähän ja tietysti käyttämällä kutakin kaarta tarkalleen kerran ja palaamalla aloituspisteeseen. Kohdistamattoman version osalta näytetään seuraava lause:
Eulerin lause (suuntautunut versio) - Olkoon G orientoitu graafi. Seuraavat kolme ehdotusta vastaavat:
Liitettävyys riittää ulottamaan suuntaamattoman tapauksen kohdennettuun tapaukseen, ja Eulerian kaavio on välttämättä kytketty voimakkaasti.
Joissakin algoritmisissa kirjoissa (mutta myös Diestelin graafiteoriakirjassa, katso luku 10, s. 213), monimutkaisuusteorian puitteissa EULERIAN-ongelmaa, onko graafi Eulerian, verrataan usein HAMILTONIAN-ongelmaan. Hamiltonin kurssi , ts. reitti , joka kulkee täsmälleen kerran jokaisen kärjen kautta. Sen määrittäminen, että kaavio sallii Eulerin piirin, tapahtuu polynomiajassa (riittää tarkistamaan kaavion kärkipisteiden pariteetti). Siten Eulerin ongelma siitä, onko graafi Eulerian, kuuluu P-luokkaan . HAMILTONIAN-ongelma on etukäteen monimutkaisempi ratkaista algoritmisesti: se on NP-täydellinen ongelma , jolla on tärkeitä sovelluksia.