Выпуклый подграф

В этом графе треугольник 1-2-5 выпуклый, но путь 2-3-4 выпуклым не является, поскольку он не включает один из двух кратчайших путей из 2 в 4.

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

Выпуклые подграфы играют важную роль в теории неполных кубов[англ.] и медианных графов. В частности, в медианных графах выпуклые подграфы имеют свойство Хэлли[англ.] — если элементы семейства выпуклых подграфов попарно пересекаются, то и всё семейство имеет непустое пересечение.

Ссылки

  • H.-J. Bandelt, V. Chepoi. Surveys on Discrete and Computational Geometry: Twenty Years Later / Jacob E. Goodman, János Pach, R. Pollack. — Providence, RI: AMS, 2008. — Т. 453. — С. 49–86..
  • Wilfried Imrich, Sandi Klavžar. A convexity lemma and expansion procedures for bipartite graphs // European Journal of Combinatorics. — Т. 19, вып. 6. — P. 677–686. — doi:10.1006/eujc.1998.0229..

Read other articles:

Aikoku Kōshinkyoku

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 Oktober 2022. Aikoku Kōshinkyoku Bermasalah memainkan berkas ini? Lihat bantuan media. Aikoku Kōshinkyoku (愛国行進曲code: ja is deprecated ) adalah mars Jepang yang disusun oleh Tōkichi Setoguchi dengan lirik oleh Yukio Morikawa. Lagu ini dirilis pada bulan...

 

 

Daftar stasiun televisi di Kalimantan Tengah

Penyuntingan Artikel oleh pengguna baru atau anonim untuk saat ini tidak diizinkan.Lihat kebijakan pelindungan dan log pelindungan untuk informasi selengkapnya. Jika Anda tidak dapat menyunting Artikel ini dan Anda ingin melakukannya, Anda dapat memohon permintaan penyuntingan, diskusikan perubahan yang ingin dilakukan di halaman pembicaraan, memohon untuk melepaskan pelindungan, masuk, atau buatlah sebuah akun. Artikel ini membutuhkan rujukan tambahan agar kualitasnya dapat dipastikan. Mohon...

 

 

Santa Clara River Trail

Bicycle/walking path in Santa Clarita, California The Santa Clara River Trail is a paved bicycle and walking path in the city of Santa Clarita, California. The path is currently approximately 8 miles (13 km) in length and generally runs in an east–west direction and closely follows the path of the Santa Clara River and Soledad Canyon Road between the communities of Canyon Country and Valencia through Saugus. A north-south fork connects to the community of Newhall. The trail is generall...

Immanuel Velikovsky

Immanuel VelikovskyImmanuel Velikovsky (pada konferensi American Association for the Advancement of Science tahun 1974 di San FranciscoLahir(1895-06-10)10 Juni 1895Vitebsk, Russian Empire (sekarang Belarus)Meninggal17 November 1979(1979-11-17) (umur 84)Princeton, New Jersey Immanuel Velikovsky (bahasa Rusia: Иммануи́л Велико́вский) (10 June [K.J.: 29 May] 1895 – 17 November 1979) adalah seorang psikiater dan sarjana berkebangsaan Yahudi-Rusia, ter...

 

 

Official Opposition (India)

Second-largest party in the upper or lower house This article is part of a series on the Politics of India Constitution and law Constitution of India Fundamental Rights, Directive Principles and Fundamental Duties of India Human rights Judicial review Taxation Uniform Civil Code Basic structure doctrine Amendment Law of India Indian criminal law Bharatiya Nyaya Sanhita Bharatiya Nagarik Suraksha Sanhita Bharatiya Sakshya Adhiniyam Code of Civil Procedure (India) Government President of India ...

 

 

Castrovillari Calcio

ASD Castrovillari CalcioCalcio Rossoneri, Lupi del Pollino Segni distintiviUniformi di gara Casa Trasferta Colori sociali Nero, rosso SimboliLupo InnoInno del Castrovillari Dati societariCittàCastrovillari Nazione Italia ConfederazioneUEFA Federazione FIGC CampionatoSerie D Fondazione1921 Rifondazione2003Presidente Nicola Mazzuca Allenatore Davide Boncore StadioStadio Mimmo Rende(2 800 posti) Sito webwww.castrovillaricalcio.it PalmarèsSi invita a seguire il modello di voce L'A.S.D...

Bintuni Bay

For the Indonesian regency, see Teluk Bintuni Regency. Bintuni BayTeluk Bintuni (Indonesian)Bintuni BayBintuni Bay as shown relative to Western New GuineaLocationNew GuineaCoordinates02°20′S 133°25′E / 2.333°S 133.417°E / -2.333; 133.417Primary outflowsBerau GulfBasin countries IndonesiaBintuni Bay Nature ReserveTeluk Bintuni Nature ReserveIUCN category Ia (strict nature reserve)[1]Area1,248.51 km2 (482.05 sq mi)Designation...

 

 

Diocese of Armagh (Church of Ireland)

Anglican diocese of the Church of Ireland Further information on the Anglican and Roman Catholic dioceses of Armagh jointly: Archbishop of Armagh This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: Diocese of Armagh Church of Ireland – news · newspapers · books · scholar · JSTOR (May 2008) (Learn how and when to remove this message) Diocese of Arma...

 

 

Andre Nickatina

Andre Nickatina Información personalNacimiento 11 de marzo de 1970 (54 años)San Francisco (Estados Unidos) Nacionalidad EstadounidenseEducaciónEducado en Galileo Academy of Science and Technology Información profesionalOcupación Rapero Años activo desde 1992Seudónimo Andre Nickatina Género Hip hop Instrumento Voz Discográfica In a Minute Records Sitio web www.andrenickatina.com/home [editar datos en Wikidata] Andre Nickatina (también conocido como Dre Dog) es un rapero del...

内华达州

内華達州 美國联邦州State of Nevada 州旗州徽綽號：產銀之州、起戰之州地图中高亮部分为内華達州坐标：35°N－42°N, 114°W－120°W国家 美國建州前內華達领地加入聯邦1864年10月31日（第36个加入联邦）首府卡森城最大城市拉斯维加斯政府 • 州长（英语：List of Governors of {{{Name}}}]]） • 副州长（英语：List of lieutenant governors of {{{Name}}}]]）喬·隆巴爾多（R斯塔...

 

 

Bâtiment ravitailleur de forces

Bâtiment ravitailleur de forces[1] Le tête de série Jacques Chevallier Caractéristiques techniques Type Navire ravitailleur Longueur 194 m Maître-bau 27,6 m Tirant d'eau 9 m Déplacement 16 000 tonnes À pleine charge 31 000 tonnes, 13 000 m3 de carburant (10 800 t)[2] Propulsion Propulsion diesel-électrique composée de 4 moteurs diesel MAN Diesel SE [3]: 2 moteurs MAN 12V32/44CR (2 × 7 200 kW) 2 moteurs MAN 8L32/44CR (2 × 4 800 kW) montés su...

 

 

February 1918

Month in 1918 1918 January February March April May June July August September October November December << February 1918 >> Su Mo Tu We Th Fr Sa 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 Signing of the Peace Treaty of Brest-Litovsk, ending the fighting between Ukraine and the Central Powers. Swedish, German and Soviet soldiers together during a lull in the Invasion of Åland off Finland. The following events occurred in February 1918: Fri...

Caterina di Pomerania-Wolgast

Questa voce o sezione sugli argomenti sovrani e nobili tedeschi non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento. Questa voce sull'argomento nobili tedeschi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Eucario Rodione presenta Der Rosengarten a Caterina Caterina d...

 

 

داريو فرانكو

داريو فرانكو معلومات شخصية الميلاد 17 يناير 1969 (العمر 55 سنة) الطول 1.89 م (6 قدم 2 1⁄2 بوصة) مركز اللعب مدافع الجنسية الأرجنتين  معلومات النادي النادي الحالي سان لويس دي كويلوتا (مدرب) مسيرة الشباب سنوات فريق نيولز أولد بويز المسيرة الاحترافية1 سنوات فريق م. (هـ.) 1987...

 

 

فرط تنسج بطانة الرحم

Endometrial hyperplasia صورة مجهرية showing simple endometrial hyperplasia, where the gland-to-stroma ratio is preserved but the glands have an irregular shape and/or are dilated. خزعة بطانية رحمية. صبغة الهيماتوكسيلين واليوزين.صورة مجهرية showing simple endometrial hyperplasia, where the gland-to-stroma ratio is preserved but the glands have an irregular shape and/or are dilated. خزعة بطانية رحمية. صبغة الهي...

Beibu Gulf Economic Rim

The Beibu Gulf Economic Rim[1] or Beibu Economic Belt (simplified Chinese: 环北部湾经济圈; traditional Chinese: 環北部灣經濟圈; pinyin: Huán Běi bù wān jīng jì quān) also known as Gulf of Tonkin Economic Belt in (Vietnamese: Vành đai kinh tế vịnh Bắc Bộ) defines the economic region or rim surrounding around China's southwestern coastal region and cities around the Gulf of Tonkin. The region is part of Chinese government's Go West strategy, to...

 

 

Gjirokastër County

County of Albania County in AlbaniaGjirokastër County Qarku i Gjirokastrës (Albanian)CountyThermal Baths near Përmet EmblemCoordinates: 40°10′N 20°10′E / 40.167°N 20.167°E / 40.167; 20.167Country AlbaniaSeatGjirokastërSubdivisions7 municipalities, 268 towns and villagesGovernment • Council chairmanDino Selimi[1]Area • Total2,884 km2 (1,114 sq mi)Population (2021[2]) • Total58,...

 

 

El Cristo (Panama)

El CristocomuneLocalizzazioneStato Panama ProvinciaChiriquí DistrettoTolé TerritorioCoordinate8°19′22.08″N 81°36′02.88″W8°19′22.08″N, 81°36′02.88″W (El Cristo) Superficie31,3 km² Abitanti1 500[1] (2010) Densità47,92 ab./km² Altre informazioniFuso orarioUTC-5 CartografiaEl Cristo Modifica dati su Wikidata · Manuale El Cristo è un comune (corregimiento) della Repubblica di Panama situato nel distretto di Tolé, provincia di Chiriquí. Si ...

Remember Me

Remember MePoster filmSutradaraAllen CoulterProduserNicholas OsborneTrevor EngelsonErik FeigDitulis olehWill FettersPemeranRobert PattinsonEmilie de RavinChris CooperLena OlinPierce BrosnanTate EllingtonRuby JerinsPenata musikMarcelo ZarvosSinematograferJonathan FreemanPenyuntingAndrew MondsheinPerusahaanproduksiUnderground FilmsDistributorSummit EntertainmentTanggal rilis 12 Maret 2010 (2010-03-12) Durasi108 menitNegara Amerika SerikatBahasaBahasa InggrisAnggaran$16 juta[...

 

 

Maria Isabel of Braganza

Queen of Spain from 1816 to 1818 Maria Isabel of BraganzaBernardo López y Piquer, depicting Maria Isabel in front of Prado (1829)Queen consort of SpainTenure29 September 1816 – 26 December 1818Born19 May 1797Palace of Queluz, PortugalDied26 December 1818(1818-12-26) (aged 21)Royal Palace of Aranjuez, Aranjuez, SpainBurialEl EscorialSpouse Ferdinand VII of Spain ​ ​(m. 1816)​IssueDetailInfanta María Luisa IsabelInfanta María Luisa IsabelNamesMaria I...