هفت پل کونیگسبرگ

نقشه کونیگسبرگ در زمان اویلر، الگوی هفت پل و رودخانه‌های متناظرش را با رنگ آمیزی مشخص کرده‌است.

هفت پل کونیگسبرگ (به انگلیسی: Seven Bridges of Königsberg)، مسئله تاریخی قابل توجهی در ریاضیات است. جواب منفی به آن توسط اویلر در ۱۷۳۶ میلادی،[۱] بنیان نظریه گراف را بنا نهاده و ایده توپولوژی را از پیش ترسیم نمود.[۲]

شهر کونیگسبرگ در پروس (اکنون کالینینگراد در روسیه)، روی هر دو سمت رود پرگل قرار داشت و شامل دو جزیره بزرگ به نام‌های کنیفوف (Kneiphof) و لومس (Lomse) می‌شد، که از طریق هفت پل با هم دیگر و با درگاه‌های شهر متصل بودند. مسئله این بود که آیا گشتی در شهر وجود دارد که از هر پل فقط یک بار عبور کند.

برای این که در مدل‌سازی منطقی مسئله و رسیدن به جواب، ابهامی ایجاد نشود، دو حالت زیر غیرقابل قبول در نظر گرفته می‌شوند:

  1. دسترسی به جزیره یا ساحل زمین اصلی به غیر از عبور از پل‌ها
  2. دسترسی به هرکدام از پل‌ها بدون عبور کامل و گذر کردن از آن‌ها

اویلر اثبات کرد که این مسئله جوابی ندارد. دشواری که با آن روبرو بود، توسعه فن تحلیلی مناسب و آزمون‌هایی بود که به سبب آن‌ها این گزاره را از روش مستحکم ریاضیاتی اثبات نماید.

تحلیه اویلر

اویلر ابتدا به این اشاره کرد که انتخاب مسیر در هر بخش از زمین نامربوط است، و تنها ویژگی مهم مسیر دنباله پل هایی است که از آنها عبور می شود. این به اویلر اجازه داد که مسئله را در قالبی انتزاعی قرار دهد (و بنیان نظریه گراف را بنا نهد): تمام ویژگی های مسیر به جز لیست بخش های زمینی و پل های ارتباطی حذف شدند. در اصطلاحات مدرن، هر توده زمین با یک "رأس" انتزاعی جایگزین می شود، و هر پل با یک ارتباط انتزاعی به نام "یال" جایگزین می شود. هر یال تنها شامل جفت رأسی که ارتباط می دهد است. ثمر ساختار ریاضیاتی نهایی یک گراف است. (برای مشاهده این گراف، به نسخه انگلیسی این صفحه مراجعه کنید.)

با دلیل اینکه تنها اطلاعات ارتباطی اهمیت دارد، ظاهر تصویری یک گراف می تواند به هر طریقی تحریف شود، بدون اینکه خود گراف تغییری کند. تنها وجود (یا عدم وجود) یال بین هر دو جفت از رئوس هائز اهمیت است. به عنوان مثال، اهمیتی ندارد که یال های مستقیم یا منحنی باشند، یا اینکه رأسی در سمت راست یا چپ رأس دیگری قرار گرفته باشد.

پس از آن، اویلر مشاهده کرد که به جز در ابتدا و انتهای گشت، هرگاه از طریق یک یال (یا پل) وارد رأسی می شویم، باید از طریق یالی از آن رأس خارج شویم. به گفته دیگر، در هر گشت در گراف، تعداد بارهایی که وارد رأسی می شویم که در ابتدا یا انتهای گراف قرار ندارد مساوی است با تعداد بارهایی که از آن رأس خارج می شویم. حال، اگر هر یال دقیقاً یک بار طی شود، نتیجه می گیریم که برای هر توده زمین (به جز توده زمین ابتدایی و انتهایی)، تعداد پل هایی که با آن توده زمین در ارتباط هستند باید زوج باشد (نیمی از آنها به سمت آن توده زمین طی می شوند، و نیمه دیگر برای خارج شدن از آن توده زمین استفاده می شوند). اما در مسئله هفت پل کونیگسبرگ، هر چهار توده زمین با تعداد فردی پل در ارتباط هستند: یکی از آنها با پنج پل در ارتباط است، و سه توده زمین دیگر با سه پل در ارتباط هستند. چون حداکثر دو توده زمین می توانند در ابتدا یا انتهای گشت باشند، پیشنهاد گشتی که از هر پل دقیقاً یک بار عبور کند به تناقض منجر می شود.

ارجاعات

  1. Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". Comment. Acad. Sci. U. Petrop 8, 128–40.
  2. Shields, Rob (December 2012). "Cultural Topology: The Seven Bridges of Königsburg 1736". Theory, Culture & Society. 29 (4–5): 43–57. doi:10.1177/0263276412451161. Shields provides a discussion of the social significance of Euler's engagement with this popular problem and its significance as an example of (proto-)topological understanding applied to everyday life.

پیوند به بیرون

Read other articles:

Chinese hammer thrower In this Chinese name, the family name is Zhang. Zhang WenxiuZhang Wenxiu after winning silver medal at Rio 2016Personal informationNationalityChineseBorn (1986-03-22) 22 March 1986 (age 37)Liaoning, ChinaHeight1.82 m (5 ft 11+1⁄2 in)Weight113 kg (249 lb)SportCountry ChinaSportAthleticsEvent(s)Hammer throwAchievements and titlesPersonal best(s)77.33 m (2014) Medal record Women's athletics Representing  China Olympic Games 200...

 

Ferrara Cona Ospedalestazione ferroviariaLocalizzazioneStato Italia LocalitàFerrara, località Cona Coordinate44°48′07.97″N 11°41′45.59″E / 44.802214°N 11.695997°E44.802214; 11.695997Coordinate: 44°48′07.97″N 11°41′45.59″E / 44.802214°N 11.695997°E44.802214; 11.695997 Lineeferrovia Ferrara-Codigoro StoriaStato attualein uso Attivazione2012 CaratteristicheTipofermata Binari1 GestoriFerrovie Emilia Romagna OperatoriTrenitalia Tper (1...

 

1995 single by Everclear Santa MonicaSingle by Everclearfrom the album Sparkle and Fade B-sideHeroin Girl (live)ReleasedDecember 5, 1995 (radio)GenreGrunge[1]Length3:11LabelCapitolSongwriter(s)Art AlexakisGreg EklundCraig MontoyaProducer(s)Art AlexakisEverclear singles chronology Heroin Girl (1995) Santa Monica (1995) Heartspark Dollarsign (1996) Music videoSanta Monica on YouTube Santa Monica (subtitled Watch the World Die in Europe) is a song by American rock band Everclear, from th...

Ronnie Platt Información personalNacimiento 24 de febrero de 1960 (63 años)Chicago, Illinois, Estados UnidosNacionalidad EstadounidenseInformación profesionalOcupación Músico, PianistaAños activo 80's - presenteGénero RockRock ProgresivoInstrumentos Voz, tecladosArtistas relacionados KansasMiembro de KansasYezda Urfa [editar datos en Wikidata] Ronnie Platt (nacido el 24 de febrero de 1960) es el cantante actual de la banda de rock Kansas. Se unió a la banda en 2014, a t...

 

Erdbeben in der Provence 1909 Erdbeben in der Provence 1909 (Frankreich) Datum 11. Juni 1909 Uhrzeit 21 Uhr 15 Minuten Magnitude 6,2 ML Tiefe 6 km Epizentrum 43° 42′ 0″ N, 5° 24′ 0″ O43.75.4-6000Koordinaten: 43° 42′ 0″ N, 5° 24′ 0″ O Land Frankreich (France métropolitaine) Tsunami nein Tote 46 Verletzte 250 Sachschaden 2000 Gebäude zerstört, 2,2 Milliarden Francs Das Erdbeben in der Provence (auch: Be...

 

Sorex ornatus Охоронний статус Найменший ризик (МСОП 3.1) Біологічна класифікація Царство: Тварини (Animalia) Тип: Хордові (Chordata) Клада: Синапсиди (Synapsida) Клас: Ссавці (Mammalia) Ряд: Комахоїдні (Eulipotyphla) Родина: Мідицеві (Soricidae) Рід: Мідиця (Sorex) Вид: S. ornatus Біноміальна назва Sorex ornatusMerriam, 1895 S...

Japanese footballer Seiya Baba 馬場 晴也 Baba playing for Japan U19 in 2019Personal informationDate of birth (2001-10-24) 24 October 2001 (age 22)Place of birth Chiba, JapanHeight 1.80 m (5 ft 11 in)Position(s) Centre-backTeam informationCurrent team Hokkaido Consadole SapporoNumber 3Youth career Refino2017–2019 Tokyo VerdySenior career*Years Team Apps (Gls)2020–2022 Tokyo Verdy 47 (0)2023– Hokkaido Consadole Sapporo 0 (0)International career‡2016–2018 Japan ...

 

Giovanni Battista VenturiLahir(1746-03-15)15 Maret 1746BibbianoMeninggal24 April 1822(1822-04-24) (umur 76)Reggio Emilia Halaman artikel ini diterjemahkan, sebagian atau seluruhnya, dari halaman di (Tolong cantumkan kode bahasa Wiki sumber terjemahan) yang berjudul (Tolong cantumkan nama artikel sumber terjemahan). Lihat pula [{{localurle:{{{1}}}:|oldid=&action=history}} sejarah suntingan halaman aslinya] untuk melihat daftar penulisnya. Giovanni Battista Venturi (lahir 15 Maret 1746...

 

2019 video game 2019 video gameJust Dance 2020Developer(s)Ubisoft ParisUbisoft PuneUbisoft ShanghaiUbisoft BordeauxPublisher(s)UbisoftSeriesJust DanceEngineUbiArt FrameworkPlatform(s)WiiNintendo SwitchPlayStation 4Xbox OneStadiaReleaseWW: November 5, 2019JP: March 12, 2020CHN: December 24, 2020Genre(s)MusicMode(s)Single-playermultiplayer Just Dance 2020 is a 2019 dance rhythm game developed and published by Ubisoft. It was unveiled on June 10, 2019, during its E3 press conference as the eleve...

Ethnic Kashmiris who practice Islam and are native to the Kashmir Valley Kashmiri MuslimsLanguagesKashmiri, UrduReligionIslam (Sunni majority) (Shia minority)Related ethnic groupsKashmiris, Kashmiri Hindus Kashmiri Muslims are ethnic Kashmiris who practice Islam and are native to the Kashmir Valley in Indian-administered Kashmir.[1][2] The majority of Kashmiri Muslims are Sunni.[3] They refer to themselves as Koshur in their mother language.[4][5][6...

 

Railway station in Pune, Maharashtra, India Loni railway stationIndian Railways stationGeneral informationLocationPune–Solapur Highway, RajBagh, Loni Kalbhor, PuneIndiaCoordinates18°29′27″N 74°01′16″E / 18.4908°N 74.0211°E / 18.4908; 74.0211Elevation539.00 metres (1,768.37 ft)Owned byIndian RailwaysLine(s)Mumbai Dadar–Solapur lineMumbai–Chennai linePlatforms2Tracks4ConnectionsAuto standConstructionParkingNoBicycle facilitiesNoOther informationSta...

 

1995 film by S. A. Chandrasekhar DevaPosterDirected byS. A. ChandrasekharStory byShoba ChandrasekharProduced byB. VimalStarringVijaySwathiCinematographySelva. REdited byP. R. Gautham RajMusic byDevaProductioncompanyB. V. CombinesDistributed byXB Film CreatorsRelease date 17 February 1995 (1995-02-17) Running time140 minutesCountryIndiaLanguageTamil Deva is a 1995 Indian Tamil-language romantic action film directed by S. A. Chandrasekhar and produced by B. Vimal. The film stars ...

4th episode of the 5th season of Star Trek: The Next Generation Silicon AvatarStar Trek: The Next Generation episodeEpisode no.Season 5Episode 4Directed byCliff BoleStory byLawrence V. ConleyTeleplay byJeri TaylorFeatured musicJay ChattawayProduction code204Original air dateOctober 14, 1991 (1991-10-14)Guest appearances Ellen Geer - Kila Marr Susan Diol - Carmen Davila Episode chronology ← PreviousEnsign Ro Next →Disaster Star Trek: The Next Generation (seaso...

 

Marina and tourist precinct in Western Australia Restaurants and promenade Boat pens. Beach and waterslides of The Great Escape visible in the background in 2015, prior to demolition. Hillarys Boat Harbour is a marina and tourist precinct located in Hillarys, north of Perth, Western Australia and on the Indian Ocean. History Hillarys Boat Harbour was the first such major marina in the north metropolitan region of Perth. Construction of the new Harbour commenced in September 1985.[1] P...

 

北山一郎 北山 一郎(きたやま いちろう、1872年4月10日(明治5年3月3日[1]) - 1949年(昭和24年)2月12日[2])は、日本の政治家、実業家。衆議院議員、青森市長。 経歴 青森県津軽郡浅瀬石村(現黒石市)で北山長作の長男として生まれる[3][4]。南津軽郡中学校を経て、1897年、東京専門学校政治科(現早稲田大学政治経済学部)を卒業[2][3 ...

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: Juho Suomalainen – news · newspapers · books · scholar · JSTOR (January 2019) Finnish politician Juho Suomalainen Juho Suomalainen (15 October 1868, in Vesanto – 16 April 1941) was a Finnish politician. He was a Member of the Parliament of Finland f...

 

Questa voce sull'argomento centri abitati del Lancashire è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Burnleyparrocchia civileBurnley – Veduta LocalizzazioneStato Regno Unito    Inghilterra RegioneNord Ovest Contea Lancashire DistrettoBurnley TerritorioCoordinate53°47′N 2°15′W / 53.783333°N 2.25°W53.783333; -2.25 (Burnley)Coordinate: 53°47′N 2°15′W / 53.783333°N 2.25°W...

 

Russian singer (1934–2012) In this name that follows Eastern Slavic naming conventions, the patronymic is Anatolyevich and the family name is Khil. Eduard KhilЭдуард Анатольевич ХильKhil receiving a 4th class Order For Merit to the Fatherland in 2009BornEduard Anatolyevich Khil(1934-09-04)4 September 1934Smolensk, Western Oblast, Russian SFSR, Soviet UnionDied4 June 2012(2012-06-04) (aged 77)Saint Petersburg, RussiaResting placeSmolensky Cemetery, Saint Petersb...

Label applied to certain updates of old games for the Nintendo 3DS It has been suggested that this article should be split into articles titled 3D Classics (Nintendo) and 3D Classics (Sega), because the two topics covered on this page are unrelated. (discuss) (April 2022) Some of this article's listed sources may not be reliable. Please help this article by looking for better, more reliable sources. Unreliable citations may be challenged or deleted. (October 2023) (Learn how and when to remov...

 

Untuk kota bernama sama, lihat Kota Sambas.Untuk Kesultanan, lihat Kesultanan Sambas. Kabupaten Sambasكابوڤاتين سمباس三發縣Sānfā xiànKabupaten LambangMotto: Sambas BerkemajuanPetaKabupaten Sambasكابوڤاتين سمباس三發縣Sānfā xiànPetaTampilkan peta KalimantanKabupaten Sambasكابوڤاتين سمباس三發縣Sānfā xiànKabupaten Sambasكابوڤاتين سمباس三發縣Sānfā xiàn (Indonesia)Tampilkan peta IndonesiaKoordinat: 1°25...

 

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