Eulerin polku

 Tähän artikkeliin tai osioon ei ole merkitty lähteitä, joten tiedot kannattaa tarkistaa muista tietolähteistä.
Voit auttaa Wikipediaa lisäämällä artikkeliin tarkistettavissa olevia lähteitä ja merkitsemällä ne ohjeen mukaan.
Königsbergin siltojen graafi
Ratkaisu "avatulle kirjekuoren tapaukselle".

Eulerin polku on suunnatussa tai suuntaamattomassa graafissa oleva polku, joka kulkee graafin jokaisen kaaren kautta täsmälleen kerran. Jos Eulerin polku palaa lopuksi takaisin lähtösolmuun, se on Eulerin kierros. Käsitteet on tehnyt tunnetuksi sveitsiläinen matemaatikko Leonhard Euler, joka ratkaisi vuonna 1736 kuuluisan Königsbergin siltaongelman.

Välttämätön ehto Eulerin kierrokselle on jokaisen solmun asteen parillisuus. Graafissa on Eulerin polku, jos siinä on Eulerin kierros, tai jos täsmälleen kahden solmun aste on pariton. Lisäksi graafin tulee olla yhtenäinen. Königsbergin siltojen graafissa on neljä paritonasteista solmua, joten siitä ei löydy Eulerin polkua.

Eulerin polun konstruointi

Oletetaan, että meillä on yhtenäinen graafi, jossa on korkeintaan kaksi paritonasteista solmua. Voimme löytää "Fleuryn algoritmilla" graafista Eulerin polun. Aloitamme polun paritonasteisesta solmusta, tai mielivaltaisesta solmusta mikäli graafissa ei ole paritonasteisia solmuja. Jokaisella askeleella liikumme solmusta toiseen siten, että valitun kaaren poistaminen ei tee graafin jäljellä olevista kaarien joukosta epäyhtenäistä. Sen jälkeen poistamme kyseisen kaaren graafista. Lopussa olemme käyneet läpi kaikki kaaret, ja niiden poistamisjärjestys antaa Eulerin polun.

Sovelluksia

Eulerin polkuja käytetään bioinformatiikassa dna-ketjujen rakentamisessa.

Katso myös

Kirjallisuutta

Aiheesta muualla

Wikimedia Commonsissa on kuvia tai muita tiedostoja aiheesta Eulerin polku.

Read other articles:

المركز السعودي لكفاءة الطاقة

المركز السعودي لكفاءة الطاقة تفاصيل الوكالة الحكومية البلد السعودية  تأسست 2010 المركز  السعودية الإدارة موقع الويب http://www.seec.gov.sa/ تعديل مصدري - تعديل   المركز السعودي لكفاءة الطاقة هو مركز وطني حكومي سعودي يتولى مسؤولية الإشراف على ترشيد ورفع كفاءة استهلاك الطاقة، و...

 

سيدي قدور العلمي

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (يونيو 2023) سيدي قدور العلمي معلومات شخصية الاسم الكامل عبد القادر بن محمد بن أحمد بن أبي القاسم الإدريسي العلمي الحمداني الميلاد سنة 1742  مكناس الوفاة سنة 1850 (107–108 ...

 

Teófilo (imperador)

Esta página cita fontes, mas que não cobrem todo o conteúdo. Ajude a inserir referências. Conteúdo não verificável pode ser removido.—Encontre fontes: ABW  • CAPES  • Google (N • L • A) (Maio de 2019) Teófilo Imperador e Autocrata dos Romanos Soldo com imagem de Teófilo Reinado 829 - 842 Consorte Teodora Antecessor(a) Miguel II, o Amoriano Sucessor(a) Miguel III, o Ébrio Nascimento 813 Morte 20 de janeiro de 8...

Exit (game show)

American TV series or program ExitGenreGame showPresented byCurt DoussettCountry of originUnited StatesOriginal languageEnglishNo. of seasons1No. of episodes6 (list of episodes)ProductionExecutive producers Craig Plestis Danny Fenton Michael Binkow Scott St. John Running time42 minutesProduction companiesSmart Dog MediaZig Zag ProductionsOriginal releaseNetworkSyfyReleaseJune 4 (2013-06-04) –July 9, 2013 (July 9, 2013) Exit is an American game show on Syfy that premiered...

 

The Church of Jesus Christ of Latter-day Saints in the Baltics

The Church of Jesus Christ of Latter-day Saints in the BalticsAn LDS Church meetinghouse in Kaunas, Lithuania.AreaEurope NorthMembers3,362 (2022)[1][2][3]Districts3Branches14Missions1Family History Centers9[4] The Church of Jesus Christ of Latter-day Saints in the Baltics refers to the Church of Jesus Christ of Latter-day Saints (LDS Church) and its members in the Baltic states namely Estonia, Latvia and Lithuania. The Baltic Mission encompasses these countries...

 

البعثة الإسبانية خوان رامون خمينيز

هذه المقالة بحاجة لصندوق معلومات. فضلًا ساعد في تحسين هذه المقالة بإضافة صندوق معلومات مخصص إليها. البعثة الإسبانية خوان رامون خمينيز (بالإسبانية: Instituto Español Juan Ramón Jiménez) هي مدرسة دولية إسبانية في مدينة الدار البيضاء المغربية. تديرها وزارة التعليم الإسبانية.[1] تتخ...

サンライズ (アニメ制作ブランド)

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）出典検索?: サンライズ アニメ制作ブランド – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2021年2月） バンダイナムコホー...

 

Robert Pattinson

English actor (born 1986) Robert PattinsonPattinson in 2018BornRobert Douglas Thomas Pattinson (1986-05-13) 13 May 1986 (age 37)London, EnglandOccupationActorYears active2004–presentPartnerSuki Waterhouse (2018–present)RelativesLizzy Pattinson (sister)[1]AwardsFull listSignature Robert Douglas Thomas Pattinson[2][3] (born 13 May 1986) is an English actor. Known for starring in both big-budget and independent films, Pattinson has ranked among the world's h...

 

西本願寺本三十六人家集

重之集の帖末部分 「えだわかぬ はるにあへども むもれ木は もえもまさらで としへぬるかな 源重之集」 西本願寺本三十六人家集（にしほんがんじぼん さんじゅうろくにんかしゅう）は、三十六歌仙の和歌を集めた平安時代末期の装飾写本である。三十六人家集のまとまった写本としては最古のもので、国宝に指定されている。京都市・西本願寺（浄土真宗本願寺派本...

Varosha, Famagusta

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Varosha, Famagusta – news · newspapers · books · scholar · JSTOR (July 2012) (Learn how and when to remove this template message) Place in Famagusta District, CyprusVarosha Βαρώσια (Greek)Maraş (Turkish)Varosha in 2006VaroshaCoordinates: 35°0...

 

Setermoen

Village in Northern Norway, NorwaySetermoenVillageView of the main road of the villageSetermoenLocation of the villageShow map of Troms og FinnmarkSetermoenSetermoen (Norway)Show map of NorwayCoordinates: 68°51′39″N 18°20′54″E / 68.8609°N 18.3483°E / 68.8609; 18.3483CountryNorwayRegionNorthern NorwayCountyTroms og FinnmarkDistrictHålogalandMunicipalityBardu MunicipalityArea[1] • Total3.0 km2 (1.2 sq mi)Elevation[2]...

 

Gibraltar Point, Lincolnshire

Nature reserve on Lincolnshire coast, England Gibraltar PointGibraltar Point beach at sunriseOS gridTF560580Coordinates53°05′47″N 0°19′42″E / 53.09641°N 0.32838°E / 53.09641; 0.32838Area437 hectares (1,080 acres)Managed byLincolnshire Wildlife Trust Ramsar WetlandDesignated5 March 1993Reference no.589[1] Gibraltar Point national nature reserve is an area of about 4.3 km2 (1.7 sq mi) on the coast of Lincolnshire, England. The...

Wonorejo, Gondangrejo, Karanganyar

WonorejoDesaKantor Desa WonorejoNegara IndonesiaProvinsiJawa TengahKabupatenKaranganyarKecamatanGondangrejoKode pos57188Kode Kemendagri33.13.13.2001 Luas... km²Jumlah penduduk... jiwaKepadatan... jiwa/km² Untuk kegunaan lain, lihat Wonorejo (disambiguasi). Wonorejo adalah desa di kecamatan Gondangrejo, Karanganyar, Jawa Tengah, Indonesia. Desa Wonorejo dalam waktu dekat akan terkena dampak proyek pembangunan Jalan Tol Solo-Ngawi. Rencananya pada akhir 2008 pembebasan tanah sudah selesa...

 

The Way I Feel (Bill Anderson album)

2005 studio album by Bill AndersonThe Way I FeelStudio album by Bill AndersonReleasedJune 14, 2005 (2005-06-14)GenreCountrycontemporary country[1]Length36:01LabelTWIVarèse SarabandeProducerSabino AllehgriniBill AndersonRex SchnelleMike ToppinsBill Anderson chronology Softly & Tenderly(2004) The Way I Feel(2005) Whisperin' Bluegrass(2007) Singles from The Way I Feel Him and MeReleased: 2005 The Way I Feel is a studio album by American country singer-songwrit...

 

Bajaj Bang Gocir

Artikel ini bukan mengenai Bajaj Bajuri atau Si Bajaj. Bajaj Bang Gocir (BBG)Genre Drama Komedi PembuatMD EntertainmentPemeran Indra Brotolaras Ajun Perwira Angela Gilsha Denira Wiraguna Mat Oli Omo Kucrut Ade Gentar Lutfi Aghizal Marco Panari Darren Rafid Khairan Penggubah lagu temaNicky AstriaLagu pembukaSelamat Pagi Joni — Nicky AstriaLagu penutupSelamat Pagi Joni — Nicky AstriaNegara asalIndonesiaBahasa asliBahasa IndonesiaJmlh. musim1Jmlh. episode7 (daftar episode)ProduksiProduser Dh...

T. Nelson Parker

American politician T. Nelson Parker5th Virginia Commissioner of InsuranceIn officeJuly 1, 1956 – July 1, 1969Preceded byGeorge A. BowlesSucceeded byEverette S. FrancisChair of the Democratic Party of VirginiaIn officeAugust 28, 1952 – December 1, 1952Preceded byWilliam M. TuckSucceeded byThomas H. Blanton60th Mayor of Richmond, VirginiaIn officeJuly 1, 1950 – July 1, 1952Preceded byW. Stirling KingSucceeded byEdward E. Haddock Personal detailsBornThomas Nelso...

 

Jonas Hector

Jonas Hector Hector pada 2018Informasi pribadiNama lengkap Jonas Armin Hector[1]Tanggal lahir 27 Mei 1990 (umur 33)[1]Tempat lahir Saarbrücken, Jerman Barat[2]Tinggi 185 m (606 ft 11 in)[1]Posisi bermain Bek kiriInformasi klubKlub saat ini 1. FC KölnNomor 14Karier junior1998–2009 SV AuersmacherKarier senior*Tahun Tim Tampil (Gol)2009–2010 SV Auersmacher 34 (9)2010–2013 1. FC Köln II 63 (5)2012– 1. FC Köln 175 (7)Tim nasional‡20...

 

Historic Aircraft Restoration Project

Aviation museum in New York, New YorkHistoric Aircraft Restoration ProjectLocation within New YorkEstablished1998 (1998)LocationNew York, New YorkCoordinates40°35′42″N 73°52′59″W / 40.595°N 73.883°W / 40.595; -73.883TypeAviation museumFounderArnie MigliaccioWebsitewww.nps.gov/gate/learn/historyculture/historic-aircraft-at-hangar-b.htm The Historic Aircraft Restoration Project is an aviation museum located in Hangar B at Floyd Bennett Field in New York,...

Monotheismus

Monotheist ist eine Weiterleitung auf diesen Artikel. Zum Album der Metal-Band Celtic Frost siehe Monotheist (Album). Der Begriff Monotheismus (griechisch μόνος mónos „allein“ und θεός theós „Gott“) bezeichnet Religionen bzw. philosophische Lehren, die einen allumfassenden Gott kennen und anerkennen. Damit werden diese in der Religionswissenschaft vom Polytheismus unterschieden, der viele Götter kennt und verehrt. Religionen, die viele Götter kennen, aber einem von diesen...

 

Philippine National Oil Company

Southeast Asian state-owned petroleum enterprise This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article may need to be rewritten to comply with Wikipedia's quality standards. You can help. The talk page may contain suggestions. (September 2019) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsource...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!