Вершинно k-связный граф

4-связный граф: при удалении любых трёх вершин, он остаётся связным.

В теории графов говорят, что нетривиальный граф G вершинно k-связен (или k-связен), если он имеет больше чем k вершин и после удаления менее чем k любых вершин граф остаётся связным.

Вершинная связность, или просто связность, графа — это наибольшее k, для которого граф k-вершинно-связен.

Альтернативно граф, отличный от полного, имеет связность k, если k является размером наименьшего подмножества вершин, при удалении которого граф становится несвязным[1]. Полные графы исключены из рассмотрения, поскольку их нельзя сделать несвязными путём удаления вершин. Полный граф с n вершинами имеет связность n − 1, как вытекает из первого определения.

Эквивалентное определение — если для любой пары вершин графа можно найти k непересекающихся путей, соединяющих эти вершины — см. теорему Менгера (Diestel 2005, С. 55). Это определение имеет тот же ответ: n − 1 для связности полного графа Kn[1].

1-связный граф называется также связным, 2-связный граф называется двусвязным, 3-связный граф называется, соответственно, трисвязным.

1-скелет[англ.] любого k-мерного выпуклого многогранника образует k-вершинно-связный граф (Теорема Балинского, Balinski, 1961). Частично обратная теорема Штейница утверждает, что любой 3-вершинно-связный планарный граф образует скелет выпуклого многогранника.

См. также

Примечания

  1. ↑ 1 2 Schrijver. Combinatorial Optimization. — Springer.

Литература

  • M. L. Balinski. On the graph structure of convex polyhedra in n-space // Pacific Journal of Mathematics. — Т. 11, вып. 2. — С. 431—434.
  • Reinhard Diestel. Graph Theory. — 3rd. — Berlin, New York: Springer—Verlag, 2005. — ISBN 978-3-540-26183-4.

Read other articles:

Etiopia

Lihat pula: Kekaisaran Ethiopia Republik Demokratik Federal EthiopiaAmharik:የኢትዮጵያ ፌዴራላዊ ዲሞክራሲያዊ ሪፐብሊክ ye-Ītyōṗṗyā Fēdēralāwī Dīmōkrāsīyāwī RīpeblīkAfar:Ityoppiah Federalih Demokrasih UmmunoOromo:Rippabliikii Federaalawaa Dimokraatawaa ItiyoophiyaaSomali:Jamhuuriyadda Dimuqraadiga Federaalka ItoobiyaTigrinya:ናይኢትዮጵያ ፌዴራላዊ ዴሞክራሲያዊ ሪፐብሊክ Nay-Ítiyop'iya Fēdēralawī Dēmokirasīyaw�...

 

Holy Cross Church, Daventry

Church in Northamptonshire, EnglandHoly Cross ChurchHoly Cross Church, Daventry52°15′30″N 1°09′33″W / 52.258264°N 1.159160°W / 52.258264; -1.159160LocationChurch Walk, Daventry, Northamptonshire, NN11 4BLCountryEnglandDenominationChurch of EnglandWebsitewww.holycrosschurchdaventry.org.uk/welcome.htmHistoryStatusActiveArchitectureFunctional statusParish churchHeritage designationGrade I listedYears built1752-1758AdministrationProvinceCanterburyDiocesePeterb...

 

Abjad Samaria

Abjad SamariaJenis aksara Abjad BahasaIbrani Samaria, Aram SamariaPeriode600 SM – sekarangArah penulisanKanan ke kiriAksara terkaitSilsilahHieroglif Mesir[1]Abjad Proto-SinaiAbjad FenisiaAbjad Ibrani KunoAbjad SamariaISO 15924ISO 15924Samr, 123 , ​SamaritanPengkodean UnicodeNama UnicodeSamaritanRentang UnicodeU+0800–U+083F Artikel ini mengandung transkripsi fonetik dalam Alfabet Fonetik Internasional (IPA). Untuk bantuan dalam membaca simbol IPA, lih...

فامفاكوفيتون (سيرري)

فامفاكوفيتون   تقسيم إداري البلد اليونان  [1] التقسيم الأعلى كيركيني  إحداثيات 41°10′44″N 23°23′38″E / 41.179°N 23.394°E / 41.179; 23.394   السكان التعداد السكاني 1061 (إحصاء السكان) (2011)825 (resident population of Greece) (2021)1178 (resident population of Greece) (2001)1135 (resident population of Greece) (1991)  معلومات ...

 

Maria Lenk Aquatics Centre

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: Maria Lenk Aquatics Centre – news · newspapers · books · scholar · JSTOR (March 2016) (Learn how and when to remove this template message) 22°58′28″S 43°23′16″W / 22.97444°S 43.38778°W / -22.97444; -43.38778 Aerial view of Ma...

 

Stasiun Hayato (Kagoshima)

Stasiun Hayato隼人駅Stasiun Hayato pada Mei 2018LokasiHayato-Chō Mitsugi, Kirishima（鹿児島県霧島市隼人町見次）Prefektur KagoshimaJepangKoordinat31°44′38″N 130°44′23″E / 31.7438°N 130.7397°E / 31.7438; 130.7397Koordinat: 31°44′38″N 130°44′23″E / 31.7438°N 130.7397°E / 31.7438; 130.7397Operator JR KyushuJalur ■ Jalur Utama Nippō ■ Jalur Hisatsu Letak434.7 km dari KokuraJumlah peron1 peron samping + 1...

Stadion Bengaluru (disambiguasi)

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. Stadion Bangalore dapat merujuk ke salah satu dari tiga stadion yang berlokasi di Bengaluru, India: Stadion Bengaluru Stadion Sree Kanteerava, stadion serbaguna Stadion Chinnaswamy, stadion kriket Halaman disambiguasi ini berisi daftar artikel Stadion ...

 

SMA Negeri 1 Tangerang Selatan

SMA Negeri 1 Tangerang SelatanInformasiDidirikan4 Januari 1977JenisNegeriAkreditasiAKepala SekolahLina Nurlina, S.Pd., M.PdJurusan atau peminatanIPA dan IPSRentang kelasX IPA, X IPS, XI IPA, XI IPS, XII IPA, XII IPSKurikulumKurikulum 2013StatusSekolah Standar NasionalAlamatLokasiJl. Pendidikan No. 49, Ciputat, Tangerang Selatan, Banten, IndonesiaTel./Faks.(021) 7401602Situs websman1tangsel.sch.idMotoMotoWe Are Still Number One SMA Negeri 1 Tangerang Selatan, merupakan salah satu Sek...

 

Синелобый амазон

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

Major trauma

For other uses, see Trauma (disambiguation). Injury that could cause prolonged disability or death Medical conditionMajor traumaHealth care providers attending to a person on a stretcher with a gunshot wound to the head; the patient is intubated, and a mechanical ventilator is visible in the backgroundSpecialtyEmergency medicine, trauma surgery Major trauma is any injury that has the potential to cause prolonged disability or death.[1] There are many causes of major trauma, blunt and ...

 

Палеопропитеки

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

 

Richard Fitzalan, 1st Earl of Arundel

English nobleman and soldier Richard FitzAlanEarl of ArundelBorn3 February 1267Died9 March 1302 (aged 35)Resting placeHaughmond Abbey, ShropshireSpouseAlice of SaluzzoChildrenEdmund FitzAlanJohn FitzAlanAlice FitzAlanMargaret FitzAlanEleanor FitzAlanParent(s)John FitzAlan IIIIsabella MortimerFamilyFitzAlan Richard FitzAlan, 1st Earl of Arundel[a] (3 February 1267 – 9 March 1302) was an English nobleman and soldier. Lineage Arms of d'Aubigny, Earls of Arundel, as blazoned in Charles'...

Hell Breaks Loose

For the 2015 album by Shane Nicholson (singer), see Hell Breaks Loose (album). 2009 promotional single by Eminem featuring Dr. DreHell Breaks LoosePromotional single by Eminem featuring Dr. Drefrom the album Relapse: Refill ReleasedDecember 15, 2009 (digital)[1]Recorded2009GenreHip hopLength4:04LabelShadyAftermathInterscopeSongwriter(s)Marshall MathersAndre YoungMark BatsonDawaun ParkerMike ElizondoProducer(s)Dr. DreMark BatsonEminem chronology Forever (2009) Hell Breaks Loose (2009) ...

 

Constance J. Milstein

American attorney and diplomat Constance MilsteinUnited States Ambassador to Malta IncumbentAssumed office October 27, 2022PresidentJoe BidenPreceded byG. Kathleen Hill Personal detailsNationalityAmericanEducationNew York University (BS)North Carolina Central University (JD) Constance J. Milstein is an American attorney and businesswoman who serves as the United States ambassador to Malta since October 2022. Early life and education Milstein earned her Bachelor of Science from New York Un...

 

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

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

1800 in the United States

U.S.-related events during the year 1800 ← 1799 1798 1797 1800 in the United States → 1801 1802 1803 Decades: 1780s 1790s 1800s 1810s 1820s See also: History of the United States (1789–1849) Timeline of United States history (1790–1819) List of years in the United States 1800 in the United States1800 in U.S. states States Connecticut Delaware Georgia Kentucky Maryland Massachusetts New Hampshire New Jersey New York North Carolina Pennsylvania Rhode Island South Carolina Tennes...

 

Royal National Theatre

Theatre in London, England National TheatreThe National Theatre from Waterloo BridgeNational TheatreLocation within Central LondonFormer namesNational Theatre Company (while based at the Old Vic from 1963)AddressUpper Ground, South BankLondonEnglandCoordinates51°30′26″N 0°06′51″W / 51.5071°N 0.1141°W / 51.5071; -0.1141Public transit Waterloo Waterloo Waterloo EastDesignationGrade II*TypeNational theatreCapacityOlivier Theatre: 1,160 seatsLyttelton Theatre: ...

 

奥林匹克运动会男子击剑奖牌得主列表

奥林匹克运动会男子击剑奖牌得主列表列出在奥林匹克运动会击剑比赛男子项目中获得奖牌的运动员。男子击剑自1896年首届现代奥林匹克运动会举办以来一直是正式奥运项目。[1] 现有项目 花剑个人 届数 金牌 银牌 铜牌 1896 雅典 欧仁-亨利·格拉沃洛特 法国（FRA） 亨利·卡洛 法国（FRA） Periklis Pierrakos-Mavromichalis 希腊（GRE） 1900 巴黎 埃米尔·科斯特 法国...

BBC Radio 2

British national radio station For other stations known as Radio 2, see Radio 2. BBC Radio 2Logo used since 2022London, Salford and CardiffBroadcast areaUnited Kingdom and internationally via BBC SoundsFrequenciesFM: 88.1–90.2 MHzDAB: 12B (BBC National DAB)Freeview: 702Freesat: 702Sky (UK only): 0102Virgin Media: 902Virgin Media Ireland: 908Astra 2E (28.2°E)Intelsat 901 (18°W)RDSBBC R2ProgrammingLanguage(s)EnglishFormatAdult contemporary musicVarious specialist music programmesOwnershipOw...

 

Alexander Conze

German archaeologist (1831-1914) Alexander Conze 1831–1914) Alexander Christian Leopold Conze (10 December 1831 – 19 July 1914) was a German archaeologist, who specialized in ancient Greek art. He was a native of Hanover, and studied at the universities of Göttingen and Berlin. In 1855 he obtained his doctorate at Berlin as a student of Eduard Gerhard. In 1863 he became an associate professor at the University of Halle,[1] and from 1869 to 1877, he served as a professor of archae...