Многодольный граф

k-дольный граф — граф, множество вершин которого можно разбить на k независимых множеств (долей). Эквивалентно, это граф, который можно раскрасить с помощью k цветов так, что концы любого выбранного ребра будут окрашены в разные цвета. При k = 2 k-дольный граф называется двудольным^[1].

Распознавание двудольных графов может быть выполнено за полиномиальное время, но для любого k > 2 задача определения, является ли данный неокрашенный граф k-дольным, становится NP-полной^[2]. Впрочем, в некоторых приложениях теории графов k-дольный граф может быть задан на входе уже раскрашенным; это может случиться, когда множества вершин графа соответствуют разным типам объектов. Например, фолксономии математически моделировались трёхдольными графами, в которых три множества вершин соответствуют пользователям системы, ресурсам, которые подлежат пометке тегами, и собственно тегам^[3]

Полный k-дольный граф — это k-дольный граф, такой, что любые две вершины, входящие в разные доли, смежны^[1]. Полный k-дольный граф может быть описан нотацией

K_{v_{1},v_{2},\ldots ,v_{k}},

где $v_{1},v_{2},\ldots ,v_{k}$ — числа вершин в долях графа. Например, $K_{2,2,2}$ — полный трёхдольный граф правильного октаэдра, состоящий из трёх независимых множеств, каждое из которых включает в себя две противоположные вершины октаэдра. Полный многодольный граф — это граф, который является полным k-дольным для некоторого k^[4].

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

Примечания

↑ ¹ ² Лекции по теории графов, 1990, с. 11.
↑ Computers and Intractability, 1979.
↑ Hotho, Andreas; Jäschke, Robert; Schmitz, Christoph; Stumme, Gerd (2006), "FolkRank : A Ranking Algorithm for Folksonomies", LWA 2006: Lernen - Wissensentdeckung - Adaptivität, Hildesheim, October 9th-11th 2006, pp. 111—114
↑ Chromatic Graph Theory, 2008, p. 41.

Литература

В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. Лекции по теории графов. — М.: Наука, Физматлит, 1990. — 384 с. — ISBN 5-02-013992-0.
Gary Chartrand, Ping Zhang. Chromatic Graph Theory. — CRC Press, 2008. — ISBN 9781584888017.
Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. — W. H. Freeman, 1979. — ISBN 0-7167-1045-5.

Read other articles:

Gereja Mathias Budapest

Gereja Mathias Beautiful view of Gereja Mathias Gereja Mathias (Hongaria: Mátyás-templomcode: hu is deprecated ) adalah sebuah gereja yang terletak di kota Budapest, Hungaria. Menurut tradisi gereja, awalnya dibangun dalam gaya Romawi di 1015, meskipun tidak ada peninggalan arkeologis ada. Bangunan saat ini dibangun di akhir kemerahan gaya Gotik di paruh kedua abad ke-14 dan secara luas dikembalikan pada akhir abad ke-19. Ini adalah gereja terbesar kedua pada abad pertengahan Buda dan gerej...

Mufassar

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. Mufassar (dalam bahasa Arab berarti dijelaskan) menurut istilah ushul fikih mengarah kepada suatu lafal atau kalimat yang menunjukkan suatu hukum dengan dalalah, yakni petunjuk yang jelas, tanpa menerima kemungkinan penakwilan dan pertakhsisan (pengkhu...

Kota bawah tanah Derinkuyu

Sebuah lorong di kota bawah tanah Derinkuyu Kota bawah tanah Derinkuyu (Turkish: Derinkuyu Yeraltı Şehricode: tr is deprecated , arti: sumur dalam)[1] adalah suatu kota bawah tanah kuno yang bertingkat-tingkat, tepatnya di Subprovinsi Derinkuyu, Provinsi Nevşehir, Turki. Dengan kedalaman hingga 54 m (177 kaki) di bawah permukaan tanah,[2] kota tersebut dapat menampung hingga sekitar 20.000 orang beserta hewan ternak dan bahan makanan mereka.[3] Ini adalah kota bawah...

Bahrain Kasuba

H.Bahrain KasubaS.Pd., M.Pd. Bupati Halmahera Selatan ke-2Masa jabatan23 Mei 2016 – 23 Mei 2021PresidenJoko WidodoGubernurAbdul Ghani KasubaWakilIswan Hasjim PendahuluMuhammad KasubaHelmi Surya Botutihe (Plh.)PenggantiPetahana Informasi pribadiLahir29 Januari 1967 (umur 57)Bibinoi, Bacan Timur Tengah, Halmahera Selatan, Maluku Utara, IndonesiaKebangsaanIndonesiaPartai politikPKS (2003–2018)PKPI (2018–2023)PDI-P (2023–Sekarang)Suami/istriNurlaila Muhamad (istri kedua)...

Honfleur

For other uses, see Honfleur (disambiguation). Not to be confused with nearby Harfleur. This article's tone or style may not reflect the encyclopedic tone used on Wikipedia. See Wikipedia's guide to writing better articles for suggestions. (November 2014) (Learn how and when to remove this template message) Commune in Normandy, FranceHonfleurCommuneHonfleur harbour Coat of armsLocation of Honfleur HonfleurShow map of FranceHonfleurShow map of NormandyCoordinates: 49°25′10″N 0°13′57″...

Girls' Generation Complete Video Collection

2012 video by Girls' GenerationGirls' Generation Complete Video CollectionVideo by Girls' GenerationReleasedSeptember 26, 2012Recorded2007 – 2012GenreK-pop, pop, dance-pop, teen pop, bubblegum pop, J-Pop, electropopLength163 min. and 6 sec. LanguageKorean, English, JapaneseLabelS.M. Entertainment, Nayutawave RecordsGirls' Generation chronology The 1st Japan Tour DVD(2011) Girls' Generation Complete Video Collection(2012) Girls' Generation Tour DVD(2012) Girls' Generation Complete Vi...

Arkadiusz Milik

Polish footballer (born 1994) Arkadiusz Milik Milik with Marseille in 2021Personal informationFull name Arkadiusz Krystian Milik[1]Date of birth (1994-02-28) 28 February 1994 (age 30)[1]Place of birth Tychy, PolandHeight 1.86 m (6 ft 1 in)[1]Position(s) StrikerTeam informationCurrent team JuventusNumber 14Youth career2000–2010 Rozwój KatowiceSenior career*Years Team Apps (Gls)2010–2011 Rozwój Katowice 10 (4)2011–2013 Górnik Zabrze 38 (11)20...

Provincia della Slesia

Provincia della Slesia Provincia della Slesia - Localizzazione Dati amministrativiNome completoProvincia della Slesia Nome ufficialeProvinz Schlesien CapitaleBreslavia PoliticaNascita1815 CausaGuerre di Slesia Fine1919 CausaScorporo e successiva annessione alla Polonia Territorio e popolazioneMassima estensione40.318 km² nel 1905 Popolazione4.935.823 nel 1905 Evoluzione storicaPreceduto da Monarchia asburgica Succeduto da Bassa Slesia Alta Slesia Modifica dati su Wikidata · Manuale La ...

Hurricane Harvey

Category 4 Atlantic hurricane in 2017 For other storms of the same name, see List of storms named Harvey. Hurricane Harvey Harvey near peak intensity prior to landfall in southern Texas on August 25Meteorological historyFormedAugust 17, 2017 (2017-08-17)ExtratropicalSeptember 1, 2017 (2017-09-01)DissipatedSeptember 2, 2017 (2017-09-02)Category 4 major hurricane1-minute sustained (SSHWS/NWS)Highest winds130 mph (215 km/h)Lowest&#...

Jacques Lacan

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Le ton de cet article ou de cette section est trop élogieux, voire hagiographique (février 2024). Modifiez l'article pour adopter un ton neutre ou discutez-en. Pour les articles homonymes, voir Lacan. Pour le germaniste, voir Jacques Lacant. Jacques LacanJacques Lacan.FonctionPrésidentSociété psychanalytique de ParisBiographieNaissance 13 avril 19013e arrondissement de ParisDécès 9 septembre 1981 (à 80...

Sepak bola di Spanyol

Parade tim nasional Spanyol sedang merayakan keberhasilan menjadi juara di Piala Dunia FIFA 2010. Di Spanyol sepak bola adalah olahraga paling populer. Federasi Sepak Bola Kerajaan Spanyol (bahasa Spanyol: Real Federación Española de Fútbol) atau yang biasa singkat dengan RFEF adalah badan nasional pengendali sepak bola di Spanyol yang mengatur La Liga, Copa del Rey dan tim nasional sepak bola Spanyol. Sepak bola modern diperkenalkan ke Spanyol pada akhir abad ke-19 oleh gabungan antar...

约翰斯顿环礁

此條目可参照英語維基百科相應條目来扩充。 (2021年5月6日)若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。约翰斯顿环礁Kalama Atoll 美國本土外小島嶼 Johnston Atoll 旗幟颂歌：《星條旗》The Star-Spangled Banner約翰斯頓環礁�...

هنود

هنودمعلومات عامةنسبة التسمية الهند التعداد الكليالتعداد قرابة 1.21 مليار[1][2]تعداد الهند عام 2011ق. 1.32 مليار[3]تقديرات عام 2017ق. 30.8 مليون[4]مناطق الوجود المميزةبلد الأصل الهند البلد الهند الهند نيبال 4,000,000[5] الولايات المتحدة 3,982,398[6] الإمار...

周處除三害 (電影)

周處除三害The Pig, The Snake and The Pigeon正式版海報基本资料导演黃精甫监制李烈黃江豐動作指導洪昰顥编剧黃精甫主演阮經天袁富華陳以文王淨李李仁謝瓊煖配乐盧律銘林孝親林思妤保卜摄影王金城剪辑黃精甫林雍益制片商一種態度電影股份有限公司片长134分鐘产地臺灣语言國語粵語台語上映及发行上映日期 2023年10月6日 (2023-10-06)（台灣） 2023年11月2日 (2023-11-02)（香�...

Miss Grand International 2020

Miss Grand International 2020Abena Appiah, Miss Grand International 2020.Tanggal27 Maret 2021Tempat Show DC Hall, Bangkok, ThailandPembawa acaraMatthew DeanePeserta63Finalis/Semifinalis20DebutKrimeaTidak tampilArmeniaAustraliaCuracaoEstoniaGuadeloupeHaitiLebanonLatviaMakauReunionRumaniaUkrainaTampil kembaliArgentinaFinlandiaInggrisIranJamaikaKambojaKenyaKosovoKoreaLaosSkotlandiaSri LankaUruguayPemenangAbena Appiah( Amerika Serikat)Kostum Nasional Terbaik Ivana Ba...

City of Glenorchy

Local government area in Tasmania, AustraliaGlenorchy City CouncilTasmaniaMap showing the Glenorchy local government area.Coordinates42°50′20″S 147°13′11″E / 42.839°S 147.2198°E / -42.839; 147.2198Population50,411 (2021)[1] • Density416.28/km2 (1,078.1/sq mi)Established1 January 1864[2]Area121.1 km2 (46.8 sq mi)MayorSue Hickey (acting)Council seatGlenorchyRegionHobart northern suburbsCountyBuckinghamState ele...

Foča

Not to be confused with Foča-Ustikolina. Town and municipality in Republika SrpskaFoča ФочаTown and municipality Coat of armsLocation of Foča within Bosnia and HerzegovinaCoordinates: 43°30′23″N 18°46′29″E / 43.50639°N 18.77472°E / 43.50639; 18.77472Country Bosnia and HerzegovinaEntity Republika SrpskaGeographical regionPodrinjeGovernment • Municipal mayorMilan Vukadinović (SNSD) • Municipality1,134.58 km2...

Palestinian Nicaraguan

Ethnic group Palestinian NicaraguanPalestino-nicaragüenseفلسطينيو نيكاراغوا Total populationunknownRegions with significant populationsManagua, Granada, MasayaLanguagesSpanish, Palestinian ArabicReligionChristianity, Sunni Islam, Shia IslamRelated ethnic groupsArab Nicaraguan Palestinian Nicaraguans (Spanish: palestino-nicaragüense) (Arabic: فلسطينيو نيكاراغوا) are Nicaraguans of Palestinian ancestry who were born in or have immigrated to Nicaragua. They ar...

Aram Khachaturian

Aram KhachaturianKhachaturian di Belanda pada tahun 1971Lahir6 Juni [K.J.: 24 Mei] 1903Tiflis, Kekaisaran Rusia (sekarang Tbilisi, Georgia)Meninggal1 Mei 1978(1978-05-01) (umur 74)Moskow, RSFS Rusia, Uni SovietMakamKomitas Pantheon, Yerevan, ArmeniaWarga negaraArmeniaAlmamaterGnessin Musical Institute, Moscow ConservatoryTahun aktif1926–1978ZamanMusik Klasik abad ke-20Partai politikPartai Komunis Uni Soviet (sejak 1943)Suami/istriNina Makarova (k. 1933; w. 1976)Anak2PenghargaanFu...

نسبة الرفع إلى السحب

الرفع والسحب هما مكونان من إجمالي القوة الديناميكية الهوائية التي تعمل على طائرة أو طائرة. في الديناميكا الهوائية، نسبةالرفع إلى السحب (lift-to-drag ratio) أو نسبة إل/دي أ(L/D ratio) هي الرفع الناتجة عن جسم ديناميكي هوائي مثل مُنساب هوائي (aerofoil) أو طائرة، مقسومًا على السحب الديناميكي ال�...