Degeneráltság (gráfelmélet)

Egy 2-degenerált gráf: minden csúcsnak legfeljebb kettő, tőle balra eső szomszédja van, tehát bármely részgráf jobbszélső csúcsának fokszáma legfeljebb kettő lehet. A kettőnél kisebb fokszámú csúcsok ismételt törlésével kapott 2-mag az ábrán színezve látható.

A matematika, azon belül a gráfelmélet területén egy k-degenerált gráf olyan irányítatlan gráf, melynek bármely részgráfjában található legfeljebb k fokszámú csúcs: tehát a részgráf valamely csúcsa a részgráfnak k vagy kevesebb élével érintkezik. Adott gráf degeneráltsága az a legkisebb k érték, melyre a gráf k-degenerált. A gráf degeneráltsága a gráf ritkaságának a mértéke, és konstans faktor távolságra található más gráf-ritkasági mértékektől, például a gráf arboricitásától.

A degeneráltság további megnevezései a k-mag szám (k-core number),[1] szélesség (width)[2] és kapcsoltság (linkage),[3] lényegét tekintve pedig megegyezik a színezési számmal (coloring number)[4] vagy Szekeres–Wilf-számmal (Szekeres and Wilf (1968) után). A k-degenerált gráfokat nevezik k-induktív gráfoknak (k-inductive graphs) is.[5] Egy gráf degeneráltsága lineáris időben számítható a minimális fokszámú csúcsokat ismételten eltávolító algoritmus segítségével.[6] A k-nál kisebb fokszámú csúcsok ismételt eltávolításával kapott összefüggő komponensek a gráf k-magjai, és a gráf degeneráltsága a legnagyobb k érték, amire rendelkezik k-maggal.

Példák

Minden erdő rendelkezik izolált csúccsal (egyetlen éllel sem érintkezik) vagy levél csúccsal (pontosan egy éllel érintkezik); ezért a fák és erdők mind 1-degenerált gráfok.

Minden véges síkbarajzolható gráfnak van 5 vagy kisebb fokszámú csúcsa, ezért minden síkbarajzolható gráf 5-degenerált, és bármely síkbarajzolható gráf degeneráltsága legfeljebb 5. Hasonlóan, a külsíkgráfok degeneráltsága legfeljebb kettő,[7] az Apollóniusz-hálózatoké pedig három.

A véletlen skálafüggetlen hálózatok Barabási–Albert-modelljének[8] jellemzője az m paraméter, ami megadja, hogy a gráfhoz adott minden csúcshoz m korábban hozzáadott csúcs kapcsolódik. Ebből következik, hogy az így kialakított hálózat bármely részgráfjában van legfeljebb m fokszámú csúcs (a részgráfban a gráfhoz legutoljára hozzáadott csúcs), tehát a Barabási–Albert-hálózatok automatikusan m-degeneráltak.

A k-reguláris gráfok degeneráltsága pontosan k. Ennél erősebb állítás is tehető: egy gráf degeneráltsága pontosan akkor egyezik meg a csúcsok maximális fokszámával, ha legalább egy összefüggő komponense a maximális fokszámmal reguláris. Bármely más gráf esetében a degeneráltság kisebb a maximális fokszámnál.[9]

Definíciók és ekvivalenciák

A G gráf (Erdős & Hajnal 1966) által definiált „színezési száma” az a legkisebb κ, amire létezik a G csúcsainak olyan rendezése, hogy minden csúcsnak kevesebb mint κ, a rendezésben előtte álló szomszédja van. Nem tévesztendő össze G kromatikus számával, ami a minimális számú szín, amivel ki lehet színezni a gráfot úgy, hogy nincs két szomszédos, azonos színű csúcs; a színezési számhoz tartozó rendezés ugyan megad egy sorrendet, amivel végre lehet hajtani színezési számnyi színnel a gráf előbb említett módon történő színezését, de ennél általában a kromatikus szám értéke kisebb.

A G gráf degeneráltságát (Lick & White 1970) úgy határozta meg, mint a legkisebb k érték, amire G minden feszített részgráfja tartalmaz k vagy annál kevesebb szomszéddal rendelkező csúcsot. A definícióban feszített részgráfok helyett tetszőleges részgráfok is megengedhetők, hiszen a részgráf csúcsai kisebb vagy egyenlő fokszámúak lehetnek, mint ugyanazon csúcshalmaz feszített részgráfjának csúcsai.

A színezési szám és a degeneráltság koncepciója egyenértékű: bármely véges gráf degeneráltsága eggyel kevesebb a színezési számnál.[10] Hiszen, ha egy gráf rendelkezik κ színezési számú rendezéssel, akkor minden H részgráfjában a rendezésben utolsó, H-hoz tartozó csúcsnak legfeljebb κ − 1 H-beli szomszédja van. Megfordítva, ha G k-degenerált, akkor egy k + 1 színezési számú rendezés előállítható egy legfeljebb k csúccsal rendelkező v csúcs ismételt megkeresésével, a v a gráfból eltávolításával, a megmaradt csúcsok rendezésével és a v a rendezés végéhez adásával.

Egy harmadik, ekvivalens megfogalmazás szerint G pontosan akkor k-degenerált (avagy legfeljebb k + 1 a színezési száma), ha G olyan irányított körmentes gráffá orientálható, melynek ki-foka legfeljebb k.[11] Egy ilyen irányítás elérhető, ha minden él irányát úgy választjuk meg, hogy a színezési számhoz tartozó rendezésben korábbi csúcs felé mutasson. Megfordítva, ha adott egy k kifokú irányítás, egy k + 1 színezési számú rendezés előállítható az irányított körmentes gráf topologikus rendezésével.

k-magok

Egy G gráf k-magja olyan maximális összefüggő részgráf, melyben minden csúcs foka legalább k. Ezzel ekvivalens megfogalmazás, hogy a G gráf valamely összefüggő komponense, amit a k-nál alacsonyabb fokszámú csúcsok ismételt törlésével kapunk. Ha a gráfban létezik egy nem üres k-mag, akkor G degeneráltsága nyilvánvalóan legalább k, és G degeneráltsága pontosan egyezik azzal a legnagyobb k-val, amire G-nek van k-magja.

Egy csúcs k-értéke (coreness) , ha beletartozik egy -magba, de nem tartozik bele egyetlen -magba sem.

A k-mag fogalmát ismeretségi hálózatok klaszterezési szerkezetének tanulmányozására[12] és véletlen gráfok evolúciójának leírására vezették be;[13] léteznek alkalmazásai a bioinformatika[1][14] és különböző hálózatok vizuális megjelenítése területén.[15] Alkalmasak gráfok sűrű komponenseinek megkeresésére, gráfok megjelenítésére, klikkek keresésére (mivel egy k-klikk éppen egy k−1-mag).

Algoritmusok

(Matula & Beck 1983) leírja, hogy lehetséges a véges G gráf olyan csúcsrendezését lineáris időben előállítani, ami a rendezés színezési számát optimalizálja; egy bucket típusú („vödör”) elsőbbségi sort (wd) használva, amely ismételten megkeresi és eltávolítja a legalacsonyabb fokszámú csúcsot.

Az algoritmus működése részletesen:

  • Inicializáljuk az L kimeneti listát.
  • A G-beli v csúcsokhoz számítsunk ki egy-egy dv értéket, a v azon szomszédainak számát, melyek még nem találhatók meg L-ben. Kezdetben ezek egyszerűen a csúcsok fokszámai.
  • Inicializálunk egy D tömböt úgy, hogy D[i] tartalmazza azon v csúcsok listáját, melyek még nem találhatók meg L-ben, melyhez dv = i.
  • Inicializáljuk k értékét 0-ra.
  • Ismételjük a következőt n alkalommal:
    • Vizsgáljuk át a tömb elemeit, D[0], D[1], ... amíg el nem érünk egy olyan i-hez, amire D[i] nem üres.
    • Állítsuk k értékét max(k,i)-re
    • Válasszunk ki egy v csúcsot D[i]-ből. Adjuk hozzá v-t az L elejéhez és távolítsuk el D[i]-ből.
    • A v minden olyan w szomszédjához, mely még nem tagja L-nek, vonjunk ki egyet dw-ből és mozgassuk w-t D-nek a dw értékének megfelelő elemébe.

Az algoritmus futásának végén k tartalmazza G degeneráltságát, L pedig a csúcsok a színezési szám szerinti optimális rendezéshez szükséges listáját. A G i-magjai az L prefixumai, melyek azokból a csúcsokból állnak, melyeket azután adtunk L-hez, hogy k először az  i-nél nagyobb vagy egyenlő értéket vett fel.

Az L, dv, D és k változók inicializálása lineáris időben megoldható. Az egyenként eltávolított v csúcsok megtalálásának és a D elemeibe a v szomszédainak beírásának ideje dv adott lépésnél felvett értékével arányos; azonban ezen értékek összege a gráf éleinek számával egyezik meg (minden él a későbbi végpontjával járul hozzá a végösszeghez), ezért a teljes idő mégis lineáris.

Kapcsolata más gráfparaméterekkel

Ha egy G gráfot körmentesen orientálunk k kifokkal, akkor élei szétoszthatók k erdőbe úgy, hogy minden csúcs kifelé irányú éléhez egy erdőt választunk. Így a G arboricitása legfeljebb degeneráltságával egyezik meg. Megfordítva, egy n-csúcsú gráf, ami k erdőbe felosztható, legfeljebb k(n − 1) éllel rendelkezik, ezért van olyan csúcsa, aminek fokszáma legfeljebb 2k− 1 – tehát degeneráltsága kevesebb az arboricitás kétszeresénél. Polinom időben kiszámítható a gráf olyan irányítása is, ami a kifokot minimalizálja, de nem feltétlenül körmentes. Az ilyen irányítású gráf élei hasonló módon szétoszthatók k pszeudoerdőbe, és megfordítva, egy gráf éleinek k pszeudoerdőbe való szétosztásával egy k-kifokú orientációt kapunk (mindig kifok−1 orientációt választva az egyes pszeudoerdőkhöz), ezért az ilyen irányítás minimum kifoka megegyezik a pszeudoarboricitással, ami pedig legfeljebb a degeneráltság értékével egyezhet meg.[16] A gráf vastagsága szintén konstans faktorra található az arboricitástól, így a degeneráltságtól is.[17]

Egy k-degenerált gráf kromatikus száma legfeljebb k + 1; ez a csúcsok számából kiinduló teljes indukcióval egyszerűen belátható, a síkgráfok hatszín-tételével megegyező módon. Mivel a kromatikus szám a maximális elemszámú klikk rendjének felső korlátja, ezért ez utóbbi szintén legfeljebb a degeneráltság plusz egy értéket veheti fel. Egy optimális színezési számú rendezésen mohó színezéssel egy k-degenerált gráf kiszínezhető legfeljebb k + 1 szín használatával.[18]

Egy k-szorosan csúcsösszefüggő gráfnak több mint k csúcsa van, és kevesebb mint k csúcs eltávolítása után minden esetben összefüggő marad; vagy ezzel ekvivalens megfogalmazásban, bármely csúcspárjához található k db, a két csúcsot összekötő csúcsdiszjunkt útvonal. Mivel ezek az utak a csúcspár mindkét tagját diszjunkt éleken kell elhagyják, ezért egy k-szorosan csúcsösszefüggő gráf degeneráltsága legalább k. A k-magokhoz hasonló, de csúcsösszefüggőségen alapuló fogalmakat az ismeretségi hálózatok elméletében strukturális kohézió néven vizsgálják.[19]

Ha egy gráf favastagsága vagy útszélessége legfeljebb k, akkor egy olyan merev körű gráf részgráfja, melynek egy perfekt eliminációs rendezésében minden csúcsnak legfeljebb k korábbi szomszédja van. Ezért a degeneráltság legfeljebb a favastagság, illetve legfeljebb az útszélesség értékével egyezhet meg. Léteznek azonban korlátos degeneráltságú, de korlátlan favastagságú gráfok, ilyenek például a rácsgráfok.[20]

A (Lee 2017) által bizonyított Burr–Erdős-sejtés összeköti G gráf degeneráltságát a G-hez tartozó Ramsey-számmal, ami a legnagyobb n, amire egy n-csúcsú teljes gráf olyan két színnel történő élszínezésének tartalmaznia kell a G egyszínű kópiáját. A sejtés szerint bármely rögzített k értékre a k-degenerált gráfok Ramsey-száma a csúcsok számával lineárisan nő.[21]

Végtelen gráfok

Bár általában véges gráfok degeneráltságáról és színezési számáról beszélünk, (Erdős & Hajnal 1966) eredeti motivációja a végtelen gráfok területén volt. Egy G végtelen gráf színezési számát a véges gráfokéhoz hasonlóan lehet definiálni: a legkisebb α kardinális szám, melyre létezik G csúcsainak olyan jólrendezése, melyben a csúcsoknak α-nál kevesebb, a rendezésben előttük szereplő szomszédja van. A színezési és kromatikus számok közötti egyenlőtlenség ebben a végtelen esetben is igaznak bizonyult; (Erdős & Hajnal 1966) állítása szerint a cikk megjelentetésének idejében ez már közismert tény volt.

A végtelen hálók véletlen részhalmazainak degeneráltságát bootstrap perkoláció néven vizsgálták.

Jegyzetek

Fordítás

  • Ez a szócikk részben vagy egészben a Degeneracy (graph theory) 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.

További információk

Read other articles:

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 November 2022. Jean-François DavyJean-François Davy (2009)Lahir3 Mei 1945 (umur 78)Paris, PrancisPekerjaanProduser, sutradara, penulis naskah, pemeranTahun aktif1966–kini Jean-François Davy (lahir 3 Mei 1945) adalah seorang produser, sutradara, penuli...

 

AwardUttam Jeevan Raksha PadakRibbon of the medalTypeCivilian Lifesaving awardDescription₹1,50,000 cash award lump-sum monetary allowance[1]CountryIndiaPresented byGovernment of IndiaRibbonRed with blue edges and two thin central green stripesObverseOpen handReverseEmblem of IndiaEstablished30 September 1961PrecedenceNext (higher) Vishisht Seva MedalNext (lower) Wound Medal← Jeevan Raksha Padak, Class II. The Uttam Jeevan Raksha Padak is a civilian lifesaving aw...

 

Halaman ini berisi artikel tentang franchise permainan video. Untuk permainan pertama dalam seri ini, lihat The Idolmaster (permainan video). The IdolmasterAliranPermainan simulasi kehidupan, Permainan ritmePengembangCygamesMetroBandai Namco GamesPenerbitBandai Namco GamesPelantarAndroid, Feature phone (au, NTT DoCoMo, SoftBank), iOS, Namco System 246 (arcade system board), Nintendo DS, PlayStation Portable, PlayStation Vita, PlayStation 3, PlayStation 4, Xbox 360Pelantar pertamaNamco System ...

Административное деление Канады Топонимия Канады — совокупность географических названий, включающая наименования природных и культурных объектов на территории Канады. Структура и состав топонимии страны обусловлены её географическим положением и богатой историе...

 

Duran DuranAsalBirmingham, InggrisGenreNew WavePopRockPop RockNew RomanticTahun aktif1978–sekarangLabelEMI/Capitol RecordsHollywood RecordsEpic RecordsSitus webwww.duranduran.comSitus resmi fanAnggotaSimon Le BonNick RhodesJohn TaylorRoger TaylorMantan anggotaAndy TaylorSterling CampbellWarren CuccurulloStephen DuffyAndy WickettSimon Colley Alan CurtisJeff Thomas Duran Duran (2005) Duran Duran adalah grup musik new wave dan electronic pop rock yang banyak mengandalkan synthesizer pada tiap ...

 

Poorest of the lower class in Naples during the Age of Revolution Lazzari playing cards, 1824 Look up lazzarone in Wiktionary, the free dictionary. In the Age of Revolution, the Lazzaroni (or Lazzari) of Naples were the poorest of the lower class (Italian lazzaroni or lazzari, singular: lazzarone) in the city and Kingdom of Naples (in present-day Italy). Described as street people under a chief, they were often depicted as beggars—which some actually were, while others subsisted partly by s...

Cet article est une ébauche concernant une localité chinoise. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Tàicāng 太仓 Administration Pays Chine Province ou région autonome Jiangsu Préfecture Suzhou Statut administratif Ville-district Code postal 215400[1] Indicatif +86 (0) Démographie 712 069 hab. (2010) Densité 879 hab./km2 Géographie Coordonnées 31° 26′ 52″ n...

 

District in Punjab, IndiaHoshiarpur districtDistrictGraveyard in TodarpurLocation in PunjabCoordinates: 31°35′N 75°59′E / 31.583°N 75.983°E / 31.583; 75.983Country IndiaStatePunjabRegionDoabaHeadquartersHoshiarpur [1]Government • MPSom Parkash(BJP) • MLAPandit Bharma Shankar Jimpa(AAP) • MayorSurinder Shinda (AAP) • Deputy commissionerKomal MittalArea • Total3,365 km2 (1,299 sq&...

 

Disambiguazione – Se stai cercando il torneo disputato tra il 1909 e il 1915 tra i club calcistici dell'Italia meridionale, vedi Coppa Lipton. Copa LiptonSport Calcio TipoNazionali CadenzaAnnuale Partecipanti2 Formulagara unica StoriaFondazione1905 Soppressione1992 Ultimo vincitore Argentina Record vittorie Argentina (17) Trofeo o riconoscimento Modifica dati su Wikidata · Manuale La Copa Lipton (nota anche come Copa de Caridad Lipton) è stato un torneo calcistico disputato tra il 1...

Serie B 1962-1963 Competizione Serie B Sport Calcio Edizione 31ª Organizzatore Lega Nazionale Professionisti Date dal 16 settembre 1962al 16 giugno 1963 Luogo  Italia Partecipanti 20 Formula girone unico Risultati Vincitore Messina(1º titolo) Altre promozioni BariLazio Retrocessioni ComoSambenedetteseLucchese Statistiche Miglior marcatore Cosimo Nocera (24) Cronologia della competizione 1961-1962 1963-1964 Manuale La Serie B 1962-1963 è stata la 31ª edizione del secondo...

 

Not to be confused with Robots (2023 film). 2005 American filmRobotsTheatrical release posterDirected byChris WedgeScreenplay by David Lindsay-Abaire Lowell Ganz Babaloo Mandel Story by Ron Mita Jim McClain David Lindsay-Abaire Produced by Jerry Davis John C. Donkin William Joyce Starring Ewan McGregor Halle Berry Greg Kinnear Mel Brooks Amanda Bynes Drew Carey Robin Williams Edited byJohn CarnochanMusic byJohn PowellProductioncompanies Blue Sky Studios 20th Century Fox Animation Distributed ...

 

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: R-26 missile – news · newspapers · books · scholar · JSTOR (November 2022) (Learn how and when to remove this message) Intercontinental ballistic missile R-26 TypeIntercontinental ballistic missilePlace of origin Soviet UnionProduction histo...

SMA Labschool JakartaInformasiDidirikan1968JenisSwastaAkreditasiANomor Statistik Sekolah302016409191Nomor Pokok Sekolah Nasional20103223Kepala SekolahDr. Suparno, S.Pd, M.M.Jumlah kelasKelas X : 7 Kelas (Kurikulum Merdeka) Kelas XI : 7 Kelas (Kurikulum Merdeka) Kelas XII : 8 Kelas ( 5 IPA, 3 IPS)Jurusan atau peminatanIPA dan IPSRentang kelasX, XI MIPA, XI IPS, XII MIPA, XII IPSKurikulumKurikulum Tingkat Satuan Pendidikan dan Kurikulum 2013AlamatLokasiJl. Pemuda Komple...

 

2016年美國總統選舉 ← 2012 2016年11月8日 2020 → 538個選舉人團席位獲勝需270票民意調查投票率55.7%[1][2] ▲ 0.8 %   获提名人 唐納·川普 希拉莉·克林頓 政党 共和黨 民主党 家鄉州 紐約州 紐約州 竞选搭档 迈克·彭斯 蒂姆·凱恩 选举人票 304[3][4][註 1] 227[5] 胜出州/省 30 + 緬-2 20 + DC 民選得票 62,984,828[6] 65,853,514[6]...

 

Municipality type A in Hebron, Palestinead-DhahiriyaMunicipality type A (City)Arabic transcription(s) • Arabicالظاهرية • Latinal-Dhahiriya (official)az-Zahiriya (unofficial)ad-DhahiriyaLocation of ad-Dhahiriya within PalestineShow map of State of Palestinead-DhahiriyaLocation of ad-Dhahiriya within the West BankShow map of the West BankCoordinates: 31°24′28″N 34°58′20″E / 31.40778°N 34.97222°E / 31.40778; 34.97222Palest...

Riccardo Meggiorini Informasi pribadiTanggal lahir 4 September 1985 (umur 38)Tempat lahir Isola della Scala, ItaliaTinggi 182 m (597 ft 1 in)Posisi bermain PenyerangInformasi klubKlub saat ini ChievoNomor 69Karier junior000?–2004 Bovolone2003–2004 → Internazionale (pinjaman)2004–2005 InternazionaleKarier senior*Tahun Tim Tampil (Gol)2004–2007 Internazionale 1 (0)2005 → Spezia (pinjaman) 10 (0)2005–2006 → Pavia (pinjaman) 12 (0)2006–2007 → Cittadella (p...

 

كشافة أيرلندا الدولة جمهورية أيرلندا  تعديل مصدري - تعديل   كشافة أيرلندا هي المنظمة العالمية الوحيدة لجمعية الكشافة المعترف بها في الحركة الكشفية في جمهورية أيرلندا.[1][2][3] في أيرلندا الشمالية التي تعمل جنبا إلى جنب مع جمعية كشافة المملكة المتحدة. كشافة ا...

 

State museum of Queensland Queensland Museum KurilpaQueensland Museum at South BrisbaneFormer nameQueensland MuseumEstablished20 January 1862; 162 years ago (1862-01-20)LocationSouth BrisbaneCoordinates27°28′24″S 153°01′06″E / 27.473412°S 153.018420°E / -27.473412; 153.018420Collection size1,000,000+Visitors2,000,000+[1]Websitemuseum.qld.gov.au/kurilpa The Queensland Museum Kurilpa is the state museum of Queensland, dedicated to na...

新南向政策簡稱新南向成立時間2016年6月15日創始人蔡英文法律地位特別機構服务地区 中華民國(臺灣) 东南亚国家联盟國家南亞國家 澳大利亞 新西兰官方語言中文首席執行官、政務委員黃志芳、鄧振中机关刊物總統府新南向政策辦公室上級組織經濟部國際貿易局目標促進區域發展交流及合作、提升國家經濟產業格局及多元性網站新南向政策專網 新南向政策...

 

此條目需要补充更多来源。 (2019年7月31日)请协助補充多方面可靠来源以改善这篇条目,无法查证的内容可能會因為异议提出而被移除。致使用者:请搜索一下条目的标题(来源搜索:南齐 — 网页、新闻、书籍、学术、图像),以检查网络上是否存在该主题的更多可靠来源(判定指引)。 齊479年—502年北魏、南齊對峙京城建康国君姓氏蕭君主7• 479-482 高帝蕭道成(...