(a, b)-felbontás

A matematika, azon belül a gráfelmélet területén egy irányítatlan gráf (a, b)-felbontása vagy (a, b)-dekompozíciója a gráf éleinek a + 1 halmazra való felbontása oly módon, hogy közülük a darab egy-egy erdőt feszít ki, a maradék pedig egy b maximális fokszámú gráfot. Ha a maradék gráf is erdő, F(a, b)-felbontásról beszélünk.

Egy a arboricitású gráf (a, 0)-felbontható. Minden (a, 0)-felbontásra, illetve (a, 1)-felbontásra igaz, hogy egyben F(a, 0)-felbontás, illetve F(a, 1)-felbontás.

Gráfosztályok

  • Minden síkbarajzolható gráf F(2, 4)-felbontható.[1]
  • Minden síkbarajzolható gráf, melynek girthparamétere legalább :
    • F(2, 0)-felbontható, ha .[2]
    • (1, 4)-felbontható, ha .[3]
    • F(1, 2)-felbontható, ha .[4]
    • F(1, 1)-felbontható, ha ,[5] vagy ha minden köre vagy háromszög, vagy legalább 8 élből áll, melyek nem tartoznak háromszöghöz.[6]
    • (1, 5)-felbontható, ha nem rendelkezik 4 hosszúságú körrel.[7]
  • Minden külsíkgráf F(2, 0)-felbontható[2] és (1, 3)-felbontható.[8]

Fordítás

  • Ez a szócikk részben vagy egészben az (a, b)-decomposition című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

  1. ↑ (Gonçalves 2009), megsejtője (Balogh et al. 2005). (Nash-Williams 1964) eredményeit (Balogh et al. 2005) fejlesztette tovább.
  2. ↑ a b (Nash-Williams 1964)-ből következik.
  3. ↑ (He et al. 2002)
  4. ↑ (Montassier et al. 2012)-ből következik, (He et al. 2002), majd (Kleitman 2008) eredményeit továbbfejlesztve.
  5. ↑ Egymástól függetlenül bizonyította (Wang & Zhang 2011), illetve következik (Montassier et al. 2012)-ből, (He et al. 2002) 11-es girthparaméterre vonatkozó eredményeit továbbfejlesztve, majd (Bassa et al. 2010) 10-es girthre és (Borodin et al. 2008a) 9-es girthre..
  6. ↑ (Borodin et al. 2009b), még ha nem is állítja explicit módon.
  7. ↑ (Borodin et al. 2009a), továbbfejlesztve (He et al. 2002), majd (Borodin et al. 2008b) eredményeit.
  8. ↑ Explicit hivatkozás nélkül (Guan & Zhu 1999) bizonyították.

Hivatkozások kronologikus sorrendben

Read other articles:

Lista över ärkebiskopar i Åbo stift

Detta är en lista över ärkebiskopar i Åbo stift inom den Evangelisk-lutherska kyrkan i Finland.[1][2][3][4] Lista Ärkebiskop ärkebiskop under tiden Jakob Tengström 1817–1832 Erik Gabriel Melartin 1833–1847 Edvard Bergenheim 1850–1884 Torsten Thure Renvall 1884–1898 Gustaf Johansson 1899–1930 Lauri Ingman 1930–1934 Erkki Kaila 1935–1944 Aleksi Lehtonen 1945–1951 Ilmari Salomies 1951–1964 Martti Simojoki 1964–1978 Mikko Juva 1978–1982 John Vikström 1982–1998 Jukk...

 

Allston

For the surname, see Allston (surname). Neighborhood of Boston in Suffolk, Massachusetts, United StatesAllstonNeighborhood of BostonPackard's Corner at the intersection of Commonwealth Avenue and Brighton Avenue in AllstonNicknames: Allston, Rat City, Rock CityCountryUnited StatesStateMassachusettsCountySuffolkNeighborhood ofBostonTime zoneUTC−5 (Eastern)Zip Code02134Area codes617 & 857 Allston is an officially recognized neighborhood within the City of Boston, Massachusetts. It wa...

 

New Parliament House, New Delhi

Seat of the Parliament of India in New Delhi Parliament House, India and Sansad Bhavan redirect here. For Old Parliament House, see Old Parliament House, New Delhi. The Parliament HouseSansad BhavanGeneral informationAddress118, Rafi Marg, New Delhi, DelhiTown or cityNew DelhiCountry IndiaCoordinates28°37′02″N 77°12′36″E / 28.61722°N 77.21000°E / 28.61722; 77.21000Current tenantsParliament of IndiaGroundbreaking1 October 2020Completed28 May 2023Opened1...

Bear Grylls

Bear GryllsPertemuan Bear Grylls dengan kelompok pramuka, Oktober 2012LahirEdward Michael Grylls07 Juni 1974 (umur 49)Donaghadee, Irlandia UtaraTempat tinggal Sebua Tongkang ditambatkan oleh Jembatan Battersea di Sungai Thames, Inggris[1] Saint Tudwal's Island West, Abersoch di Llŷn Peninsula, Wales Utara[2] Almamater Eton College Birkbeck, Universitas London Pekerjaan Chief Scout Petualang Penulis Motivator Pembawa acara Suami/istriShara Cannings KnightAnakJesse, Marma...

 

Nanny McPhee and the Big Bang

2010 British filmNanny McPhee and the Big BangUK theatrical release posterDirected bySusanna WhiteWritten byEmma ThompsonBased onNurse Matildaby Christianna BrandProduced byTim BevanEric FellnerLindsay DoranStarring Emma Thompson Maggie Gyllenhaal Rhys Ifans Maggie Smith CinematographyMike EleyEdited bySim Evan-JonesMusic byJames Newton HowardProductioncompanies StudioCanal Relativity Media Working Title Films Three Strange Angels Distributed byUniversal Pictures (North America and Internati...

 

B

  此條目介紹的是拉丁字母中的第2个字母。关于其他用法，请见「B (消歧义)」。   提示：此条目页的主题不是希腊字母Β、西里尔字母В、Б、Ъ、Ь或德语字母ẞ、ß。 BB b(见下)用法書寫系統拉丁字母英文字母ISO基本拉丁字母（英语：ISO basic Latin alphabet）类型全音素文字相关所属語言拉丁语读音方法 [b][p][ɓ](适应变体)Unicode编码U+0042, U+0062字母顺位2数值 2歷史發...

Saint-Yorre (eau minérale)

Pour les articles homonymes, voir Saint-Yorre. Saint-Yorre SNC Neptune Distribution Création 7 juillet 1993 : immatriculation de la société Forme juridique Société en nom collectif Siège social Saint-Yorre France Direction Sebastien Boie (depuis le 11 septembre 2010) Actionnaires Succession de Pierre Papillaud Activité Autres intermédiaires du commerce en denrées, boissons et tabac (code 4617B) Sociétés sœurs Eaux Minérales de Chambon la Forêt Roxane Saint Amand Finan...

 

Nyhavn 9

Nyhavn 9The house seen from the other side of the canalGeneral informationLocationCopenhagen, DenmarkCoordinates55°40′50.76″N 12°35′19.4″E / 55.6807667°N 12.588722°E / 55.6807667; 12.588722Completed1681 Nyhavn 9 is a historic townhouse overlooking the Nyhavn Canal in central Copenhagen, Denmark. It dates back to the 17th century and is one of few buildings along the canal that was not heightened in the 19th century. The building was listed on the Danish Reg...

 

1985–86 Notre Dame Fighting Irish men's basketball team

American college basketball season 1985–86 Notre Dame Fighting Irish men's basketballNCAA tournamentConferenceIndependentRankingCoachesNo. 11APNo. 10Record23–6Head coachDigger Phelps (15th season)Home arenaAthletic & Convocation CenterSeasons← 1984–851986–87 → 1985–86 NCAA Division I men's basketball independents standings vte Conf Overall Team W   L   PCT W   L   PCT No. 10 Notre Dame - – -   – 23 –...

The Madness of Crowds: Gender, Race and Identity

2019 book by Douglas Murray The Madness of Crowds: Gender, Race and Identity First editionAuthorDouglas MurrayLanguageEnglishSubjectsPolitics, race, LGBT, feminismPublisherBloomsbury PublishingPublication date17 September 2019Media typePrint (Hardcover and Paperback)Pages288ISBN978-1-63557-998-7 The Madness of Crowds: Gender, Race and Identity is a 2019 book by conservative British journalist and political commentator Douglas Murray. It was published in September 2019. The book attracted...

 

British literature

Literature from the United Kingdom For an overview of all English-language literature, see English literature. British literature is literature from the United Kingdom of Great Britain and Northern Ireland, the Isle of Man, and the Channel Islands. This article covers British literature in the English language. Anglo-Saxon (Old English) literature is included, and there is some discussion of Latin and Anglo-Norman literature, where literature in these languages relate to the early development...

 

El reino (película)

El reino Parte del equipo artístico, de izquierda a derecha: Mariela Besuievsky (productora), Álex de Pablo (director de fotografía), Mercedes Gamero (productora), Isabel Peña (guionista), Rodrigo Sorogoyen (director y guionista), Olivier Arson (músico) y Alberto del Campo (montador).Ficha técnicaDirección Rodrigo SorogoyenGuion Rodrigo Sorogoyen Isabel PeñaFotografía Álex de PabloProtagonistas Antonio de la TorreJosep María PouBárbara LennieNacho FresnedaAna Wagener Ver todos los...

الإباضية

إباضية الإباضية الدين الإسلام المؤسس عبد الله بن إباض التميمي - جابر بن زيد[1] مَنشأ شبه الجزيرة العربية العقائد الدينية القريبة الخوارج عدد المعتنقين 2.7 مليون[2] - 7 ملايين [3] الامتداد  عُمان  الجزائر (وادي ميزاب)  ليبيا (نفوسة)  تونس (جربة) (زنجبار) تعديل ...

 

History of the Grand Canyon area

Foot of Toroweap Looking East by William H. Holmes (1882). Artwork such as this was used to popularize the Grand Canyon area. The known human history of the Grand Canyon area stretches back 10,500 years, when the first evidence of human presence in the area is found. Native Americans have inhabited the Grand Canyon and the area now covered by Grand Canyon National Park for at least the last 4,000 of those years. Ancestral Pueblo peoples, first as the Basketmaker culture and later as the more...

 

Celtic Christianity

Christianity in the Celtic language–speaking world during the early Middle Ages A Celtic Cross in Knock, Ireland Celtic Christianity[a] is a form of Christianity that was common, or held to be common, across the Celtic-speaking world during the Early Middle Ages.[1] Some writers have described a distinct Celtic Church uniting the Celtic peoples and distinguishing them from adherents of the Roman Church, while others classify Celtic Christianity as a set of distinctive practi...

بيت نصيف

21°29′2″N 39°11′16″E / 21.48389°N 39.18778°E / 21.48389; 39.18778 بيت نصيفبيت نصيفمعلومات عامةنوع المبنى بيتالمكان جدة، منطقة مكة المكرمةالبلد  السعوديةمعلومات أخرىالإحداثيات 21°29′02″N 39°11′16″E / 21.4839°N 39.1878°E / 21.4839; 39.1878 تعديل - تعديل مصدري - تعديل ويكي بيانات بيت نصيف�...

 

Neville Godwin

Neville GodwinNazionalità Sudafrica Altezza173 cm Peso73 kg Tennis Termine carriera2003 Carriera Singolare1 Vittorie/sconfitte 36-56 Titoli vinti 1 Miglior ranking 90º (31 marzo 1997) Risultati nei tornei del Grande Slam  Australian Open 3T (1997)  Roland Garros 1T (1997)  Wimbledon 4T (1996)  US Open 2T (1996) Doppio1 Vittorie/sconfitte 64-74 Titoli vinti 0 Miglior ranking 57º (21 agosto 2000) Risultati nei tornei del Grande Slam  Australian Open 2T (1998) &#...

 

Hōjō Masako

Hōjō MasakoHōjō Masako oleh Kikuchi Yōsai (菊池 容斎) Midaidokoro Informasi pribadiLahir1156Meninggal16 Agustus 1225(1225-08-16) (umur 69)Suami/istriMinamoto no YoritomoHubunganHōjō Yoshitoki (saudara) Kujō Yoritsune (ipar cucu)AnakMinamoto no YoriieMinamoto no SanetomoOrang tuaHōjō TokimasaPekerjaanBiarawati Buddha, politisiSunting kotak info • L • B Hōjō Masako (北条 政子) (1157-1225) merupakan seorang politikus sekaligus istri dari syogun pertama Jepa...

Drip Harder

2018 mixtape by Lil Baby and GunnaDrip HarderMixtape by Lil Baby and GunnaReleasedOctober 5, 2018 (2018-10-05)Recorded2018Genre Hip hop trap Length38:47LabelYSLQuality ControlMotownCapitolProducerTurbo (also exec.)B RackzFrank DukesJetJune JamesLosoMattazik MuzikQuay GlobalSidepceTay KeithTaz TaylorWheezyLil Baby chronology Harder Than Ever(2018) Drip Harder(2018) Street Gossip(2018) Gunna chronology Drip Season 3(2018) Drip Harder(2018) Drip or Drown 2(2019) Singles fr...

 

Colonia Fara

Colonia Gustavo FaraLocalizzazioneStato Italia RegioneLiguria LocalitàChiavari Coordinate44°19′13.84″N 9°18′36.66″E44°19′13.84″N, 9°18′36.66″E Informazioni generaliCondizioniIn uso Costruzione1935-36 Inaugurazione28 giugno 1938 Stilefuturismo UsoCivile, turistico Piani11 RealizzazioneArchitettoCamillo Nardi GrecoLorenzo Castello AppaltatorePartito Nazionale Fascista ProprietarioFara Srl CommittentePartito Nazionale Fascista Modifica dati su Wikidata · Manuale L...