Лемма Кёнига о бесконечном пути

Статья Кёнига 1927 года

Лемма Кёнига о бесконечном пути — теорема, которая даёт достаточное условие на существование бесконечного пути в графе. Эта теорема играет важную роль как пример в конструктивной математике и теории доказательств.

Доказана Денешем Кёнигом в 1927 году[1].

Формулировка

Пусть — бесконечный, но локально конечный (то есть каждая его вершина имеет конечную степень) связный граф. Тогда содержит бесконечный простой путь, то есть путь без повторяющихся вершин, который начинается в одной вершине и продолжается бесконечно долго.

Замечания

  • Полезным частным случаем этого утверждения является то, что каждое бесконечное дерево содержит вершину бесконечной степени или бесконечный простой путь.

Примечания

  1. ↑ Kőnig, D. (1927), "Über eine Schlussweise aus dem Endlichen ins Unendliche", Acta Sci. Math. (Szeged) (3(2-3)): 121–130.

Read other articles:

Sonic Advance 2

Sonic Advance 2[a] adalah gim video platform gulir samping tahun 2002 dikembangkan oleh Dimps untuk Game Boy Advance.Ini adalah angsuran dalam seri Sonic the Hedgehog dan sekuel Sonic Advance 2001.Ceritanya mengikuti Sonic saat ia berangkat untuk menyelematkan teman-temannya dan mengambil Chaos Emeralds tujuh ajaib dari antagonis seri Doctor Eggman. Gameplay terdiri dari pemain yang menyelesaikan berbagai berbagai level sebagai salah satu dari lima karakter, masing-masing dengan atri...

 

Atherion maccullochi

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Januari 2023. Atherion maccullochi TaksonomiKerajaanAnimaliaFilumChordataKelasActinopteriOrdoAtheriniformesFamiliAtherinidaeGenusAtherionSpesiesAtherion maccullochi Jordan dan Hubbs, 1919 lbs Atherion maccullochi adalah sebuah spesies ikan dari keluarga Atherionidae...

 

Thioproperazine

Typical antipsychotic medication ThioproperazineClinical dataTrade namesMajeptilATC codeN05AB08 (WHO) Legal statusLegal status BR: Class C1 (Other controlled substances)[1] Identifiers IUPAC name N,N-dimethyl-10-[3-(4-methylpiperazin-1-yl)propyl]-10H-phenothiazine-2-carboxamide CAS Number316-81-4PubChem CID9429DrugBankDB01622ChemSpider9058UNIIYJ050AQ56XKEGGD08585ChEBICHEBI:59120ChEMBLChEMBL609109CompTox Dashboard (EPA)DTXSID1023655 ECHA InfoCard100.005.695 Chemical and ...

List of public art in the London Borough of Southwark

This list is incomplete; you can help by adding missing items. (January 2022) Stuart Williamson's statue of John Keats (2007), Guy's Hospital Map all coordinates using OpenStreetMap Download coordinates as: KML GPX (all coordinates) GPX (primary coordinates) GPX (secondary coordinates) This is a list of public art in the London Borough of Southwark. Bankside Main article: Bankside Image Title / subject Location andcoordinates Date Artist / designer Architect / other Type Desig...

 

Alexandra Palace

Cet article est une ébauche concernant Londres. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Alexandra PalacePrésentationType Lieu pour des événements (d), centre communautaire, installation sportive, studio de télévision, théâtreFondation 1875Architecte Owen JonesOuverture 1873, 1875Propriétaire Haringey London Borough Council (en)Patrimonialité Monument classé de Grade II (en) (1996)Site web...

 

Will.i.am

Pour les articles homonymes, voir Adams et William Adams. Pour le label, voir Will.i.am Music Group. will.i.am will.i.am au John F. Kennedy Center for the Performing Arts à Washington, D.C. en 2018.Informations générales Surnom Zuper Blahq Nom de naissance William James Adams Junior Naissance 15 mars 1975 (49 ans)Los Angeles, États-Unis Activité principale Rappeur, chanteur, disc jockey, producteur, compositeur, acteur Genre musical Hip-hop, dance, pop, funk Instruments Piano, synt...

Gonaïves

Gonaïves GonayivKomuneJulukan: La Cité de l'IndépendanceKota KemerdekaanKoordinat: 19°26′44″N 72°41′18″W / 19.44556°N 72.68833°W / 19.44556; -72.68833Koordinat: 19°26′44″N 72°41′18″W / 19.44556°N 72.68833°W / 19.44556; -72.68833Country HaitiDepartemenArtiboniteArondisemenGonaïvesPemerintahan • Wali kotaNeil LatortureKetinggian6 m (20 ft)Populasi (2011) • Komune300,000 �...

 

Hubble Ultra-Deep Field

Deep-field space image The original NASA release, containing about 10,000 galaxies of various ages, sizes, shapes, and colors. The smallest, reddest ones are some of the most distant galaxies to have been imaged by an optical telescope, probably existing shortly after the Big Bang. Hubble Deep UV (HDUV) Legacy Survey; 15k galaxies, released August 16, 2018ABYSS WFC3/IR Hubble Ultra Deep Field; released January 24, 2019 The Hubble Ultra-Deep Field (HUDF) is a deep-field image of a small region...

 

Азиатский барсук

Азиатский барсук Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:СинапсидыКласс:Мле�...

末沙布

尊敬的拿督斯里莫哈末·沙布Mohamad bin Sabu国会议员2018年9月24日末沙布在五角大楼与美国国防部长詹姆斯·马蒂斯会面农业及食品工业部部长现任就任日期2022年12月3日君主最高元首苏丹阿都拉最高元首苏丹依布拉欣·依斯迈首相安华·依布拉欣副职陈泓缣（2022年至2023年）亚瑟古律（2023年至今）前任羅納建迪国防部长任期2018年5月21日—2020年2月24日君主最高元首端姑莫哈末五世...

 

2020年夏季奧林匹克運動會波蘭代表團

2020年夏季奥林匹克运动会波兰代表團波兰国旗IOC編碼POLNOC波蘭奧林匹克委員會網站olimpijski.pl（英文）（波兰文）2020年夏季奥林匹克运动会（東京）2021年7月23日至8月8日（受2019冠状病毒病疫情影响推迟，但仍保留原定名称）運動員206參賽項目24个大项旗手开幕式：帕维尔·科热尼奥夫斯基（游泳）和马娅·沃什乔夫斯卡（自行车）[1]闭幕式：卡罗利娜·纳亚（皮划艇）&#...

 

Fort Scratchley

Museum and former coastal defence site in Newcastle, New South Wales Fort ScratchleyNewcastle East, New South Wales Fort Scratchley (on hilltop) viewed from Nobbys BeachFort Scratchley in 2011.Fort ScratchleyCoordinates32°55′40″S 151°47′26″E / 32.92768°S 151.79045°E / -32.92768; 151.79045TypeCoastal defence installationHeight30 m (98 ft)Site informationOwnerNewcastle City CouncilControlled byAustraliaOpen tothe publicWednesday - Mon...

Roberto Simón

Questa voce sull'argomento cestisti cubani è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Roberto Simón Nazionalità  Cuba Altezza 193 cm Pallacanestro Ruolo Guardia Termine carriera 1999 CarrieraSquadre di club 1998-1999Orientales SantiagoNazionale 1980-1995 Cuba Il simbolo → indica un trasferimento in prestito.   Modifica dati su Wikidata · Manuale Roberto Simón Salomón (Guantá...

 

أحمد إبراهيم (لاعب كرة قدم بحريني)

  لمعانٍ أخرى، طالع أحمد إبراهيم (توضيح). أحمد إبراهيم معلومات شخصية مركز اللعب الدفاع الجنسية البحرين  معلومات النادي النادي الحالي النجمة المسيرة الاحترافية1 سنوات فريق م. (هـ.) 1 عدد مرات الظهور مع الأندية وعدد الأهداف تحسب للدوري المحلي فقط وهو محدث في 13 أغسطس 20...

 

Paulina Robot

Eva Paulina Robot (16 April 1938 – 5 Oktober 2000) adalah seorang aktris berkebangsaan Indonesia yang aktif pada tahun 1950-an. Ia merupakan putri dari aktris Mien Sondakh. Paulina RobotPaulina pada tahun 1955LahirEva Paulina Robot(1938-04-16)16 April 1938Meninggal5 Oktober 2000(2000-10-05) (umur 62)KebangsaanIndonesiaPekerjaanAktrisTahun aktif1953–1957Orang tuaMien Sondakh (ibu) Filmografi Paulina, Titien Sumarni, A. Thys, dan Mien Sondakh dalam film Putri Solo (1...

Haugean movement

Christian Pietistic movement in Norway Haugianere Adolph Tidemand (1852) Hans Nielsen Hauge ca. 1800 The Haugean movement or Haugeanism (Norwegian: haugianere) was a Pietistic state church reform movement intended to bring new life and vitality into the Church of Norway, which had been often characterized by formalism and lethargy. The movement emphasized personal diligence, enterprise and frugality.[1][2] Background The Haugean movement took its name from the lay evangelist H...

 

الدوري التركي الممتاز 1966-67

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (نوفمبر 2019) الدوري التركي الممتاز 1966-67 تفاصيل الموسم الدوري التركي الممتاز  النسخة 9  البلد تركيا  المنظم اتح�...

 

حرة القفيف

حرة القفيف الموقع  السعودية - المدينة المنورة النوع حرة (جغرافيا) تعديل مصدري - تعديل   حَرّة القُفيف هي حَرّة تقع في السعودية، ضمن نطاق منطقة المدينة المنورة الواقعة غرب السعودية. تبلغ مساحة الحَرّة 650 كم2،[1] ويقع بها «حزم صُماخ» الذي يرتفع نحو 1065 م.[2] انظر أيضا�...

Vicepresident

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2019-08) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan. Vicepresident, i vissa republiker titel för den person som har till uppgift att fullgöra en presidents uppgift då denne är förhindrad att fullgöra sina plikter. I många länder finns ingen särskild vicepresident....

 

WVOP

Radio station in Vidalia, GeorgiaWVOPVidalia, GeorgiaFrequency970 kHzBrandingNews Talk 970ProgrammingFormatNews/TalkAffiliationsABC Radio, Jones Radio NetworkOwnershipOwnerDennis Jones(RadioJones, LLC)Sister stationsWTCQWYUMTechnical information[1]Licensing authorityFCCFacility ID70116ClassDPower4,000 watts day60 watts nightTransmitter coordinates32°13′12.00″N 82°26′7.00″W / 32.2200000°N 82.4352778°W / 32.2200000; -82.4352778Translator(s)105.3 ...