Azərbaycanca AzərbaycancaDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisItaliana ItalianaҚазақ ҚазақLietuvos LietuvosРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人
Підтримка
www.wikidata.uk-ua.nina.az

k ви роджений граф це неорієнтований граф у якому кожен підграф має вершини зі степенем що не перевищує k Ви родженість

Виродженість (теорія графів)

k-ви́роджений граф — це неорієнтований граф, у якому кожен підграф має вершини зі степенем, що не перевищує k. Ви́родженість графа — це найменше значення k, для якого граф є k-виродженим. Виродженість графа відбиває, наскільки граф розріджений і (з точністю до сталого множника) відбиває інші заходи розрідженості, такі як деревність графа.

image
2-вироджений граф — кожна вершина має не більше двох сусідів зліва, так що найправіша вершина будь-якого підграфа має степінь два і менше. Його 2-ядро, підграф, що залишається після видалення вершин зі степенем, меншим за два, виділено кольором.

Виродженість відома також під назвою k-я́дерне число́, ширина́ і заче́плення, і, по суті, це те саме, що й число́ розфарбовува́ння або число́ Секереша — Ві́лфа. k-вироджені графи називаються також k-індукти́вними гра́фами. Виродженість графа можна обчислити за лінійний час за допомогою алгоритму, що послідовно видаляє вершини з найменшим степенем. Компоненту зв'язності, що залишилася після видалення всіх вершин зі степенем, меншим від k називають k-ядро́м графа, і виродженість графа дорівнює найбільшому значенню k, для якого існує k-ядро.

Приклади

Будь-який ліс або має ізольовану вершину (без суміжних ребер), або листкову вершину (інцидентну рівно одному ребру), так що ліси і дерева є 1-виродженими графами.

Будь-який скінченний планарний граф має вершину степеня 5 або менше, тому будь-який планарний граф є 5-виродженим і виродженість будь-якого планарного графа не перевищує 5. Подібно до цього, виродженість будь-якого зовніпланарного графа не перевищує 2, а виродженість (графів Аполлонія) дорівнює 3.

Модель Барабаші — Альберт генерування випадкових безмасштабних мереж має як параметр число m, таке, що кожна вершина, додана до графа, пов'язана ребрами з m доданих раніше вершин. Звідси випливає, що будь-який підграф мережі, отриманий таким способом, має степінь вершин, не менший від m (це степінь останньої вершини, доданої до графа), так що мережі Барабаші — Альберт автоматично m -вироджені.

Будь-який k-регулярний граф має виродженість рівно k. Строгіше, виродженість графа дорівнює найбільшому степеню вершини тоді й лише тоді, коли принаймні одна з компонент зв'язності графа є регулярною і має степінь самого графа. Для решти графів виродженість строго менша від максимального степеня вершин графа.

Визначення

Число розфарбовування графа G ввели Ердеш і Хайнал як найбільше image, для якого існує впорядкування вершин графа G, за якого кожна вершина має менше image сусідів, що передують вершині в порядку. Слід відрізняти це число від хроматичного числа графа G, найменшого числа кольорів, необхідних для розфарбування вершин, за якого ніякі дві суміжні вершини не пофарбовані в однаковий колір. Упорядкування, що визначає число розфарбовування, дає порядок розфарбовування вершин графа G в число кольорів, що дорівнює числу розфарбовування, але, в загальному випадку, хроматичне число може бути меншим від цього числа.

Лік та Вайт визначили виродженість графа G як найменше число k, для якого будь-який породжений підграф графа G містить вершину з k і менше сусідами. Визначення не зміниться, якщо замість породжених підграфів брати довільні підграфи, оскільки непороджений підграф може мати степені вершин, що не перевищують степенів вершин породженого з тим самим набором вершин підграфа.

Два поняття, число розфарбовування та виродженість, еквівалентні — в будь-якому скінченному графі виродженість на одиницю менша від числа розфарбовування. Якщо граф має упорядкування з числом розфарбовування image, то в кожному підграфі H вершина, що належить H і є останньою в упорядкуванні, має не більше image сусідів у H. З іншого боку, якщо G дорівнює k-виродженості, то впорядкування з числом розфарбовування k + 1 можна отримати послідовним знаходженням вершини v з максимум k сусідами, видаленням вершини v з графа, впорядкуванням решти вершин і додаванням вершини v в кінець порядку.

Третє еквівалентне визначення k-виродженості графа G (або що число розфарбовування не перевищує k + 1) — граф k-вироджений тоді й лише тоді, коли ребра графа G можна зорієнтувати з утворенням спрямованого ациклічного графа з напівстепенем виходу, що не перевищує k. Таку орієнтацію можна отримати орієнтуванням кожного ребра в бік ранішої з двох вершин ребра в упорядкуванні. З іншого боку, якщо задано орієнтацію з напівстепенем виходу k, упорядкування з числом розфарбовування k + 1 можна отримати як топлогічне впорядкування орієнтованого ациклічного графа.

k-Ядра

k-Ядро графа G — це найбільший зв'язний підграф графа G, в якому всі вершини мають степінь принаймні k. Еквівалентно, це одна зі зв'язних компонент підграфа G, утвореного послідовним видаленням усіх вершин зі степенем, меншим від k. Якщо існує непорожнє k-ядро, ясно, що G має виродженість, не меншу від k, а виродженість графа G — це найбільше число k, для якого G має k-ядро.

Вершина image має ядерність image якщо вершина належить image-ядру, але не належить image-ядру.

Поняття k-ядра введено для вивчення групування в соціальних мережах та для опису розгортання випадкових графів. Поняття також перенесено в біоінформатику та візуалізацію мереж.

Алгоритми

Як описують Матула і Бек, можна знайти за лінійний час упорядкування вершин у скінченному графі G, що оптимізує число розфарбовування упорядкування, якщо для знаходження та видалення вершин найменшого степеня використовувати [en]. Виродженість тоді — це найбільший степінь будь-якої вершини на момент її видалення.

Детальніше, алгоритм працює так:

  • Створюємо список виведення L.
  • Для кожної вершини v графа G обчислюємо число dv — число сусідів вершини v, що ще не містяться в L. Спочатку ці числа просто рівні степеням вершин.
  • Створюємо масив D, в якому D[i] містить список вершин v, які не входять до списку L, для яких dv = i.
  • (Присвоюємо) k значення 0.
  • Повторюємо n разів:
    • переглядаємо елементи масиву D [0], D [1], …, доки знайдемо i, якого D[i] не порожнє;
    • присвоюємо k більше з двох значень (k,i);
    • вибираємо вершину v з D[i]. Додаємо v на початок черги L і видаляємо її з D[i].
    • Для кожної вершини w, яка сусідня v і не міститься в L, віднімаємо одиницю від dw і переносимо w в елемент масиву D, який відповідає новому значенню dw.

При завершенні алгоритму k містить виродженість графа G, а список L містить вершини в оптимальному порядку для числа розфарбовування. У графі G i-ядра — це підсписки списку L, що складаються з вершин, доданих до L після того, як k вперше набуло значення, більшого або рівного i.

Ініціалізувати змінні L, dv, D і k можна легко за лінійний час. Знаходження чергової вершини, що видаляється, і перерахунок елементів D, що містять сусідів вершини v, займає час, пропорційний значенню dv на цьому кроці, але сума таких значень дорівнює числу ребер графа, так що загальний час лінійний.

Зв'язок з іншими параметрами графа

Якщо граф G є орієнтованим ациклічним з напівстепенем виходу k, його дуги можна розбити на k лісів вибором одного лісу для кожної вихідної дуги кожної вершини. Отже, деревність графа G не перевищує його виродженості. З іншого боку, граф із n вершинами, який можна розбити на k лісів, має не більше k(n − 1) ребер, а тому має вершини зі степенем, що не перевищує 2k − 1. Тобто виродженість удвічі менша від деревності графа. Також за поліноміальний час можна обчислити орієнтацію графа, що мінімізує степінь напіввиходу, але не мусить бути ациклічною. Ребра графа з такою орієнтацією можна розбити тим самим способом на k псевдолісів. І навпаки, будь-яке розбиття ребер графа на k псевдолісів приводить до орієнтації з найбільшим напівстепенем виходу k (вибором орієнтації з напівстепенем виходу 1 для кожного псевдолісу), так що найменший напівстепінь виходу такої орієнтації є псевдодеревністю, яка, знову ж, не перевищує виродженості. Товщина також (з точністю до сталого множника) пропорційна деревності, так що те саме істинне й для виродженості.

k-Вироджений граф має хроматичне число, що не перевищує k + 1. Це можна показати простою індукцією за кількістю вершин, так само, як при доведенні теореми про шість фарб для планарних графів. Оскільки хроматичне число є верхньою межею порядку найбільшої кліки, цей порядок не перевищує виродженості плюс одиниця. Скориставшись алгоритмом жадібного розфарбування для порядку з оптимальним числом розфарбовування, можна розфарбувати k-вироджений граф, використавши не більше k + 1 кольору.

Вершинно k-зв'язний граф — це граф, який не можна розбити на кілька компонентів, видаливши менше k вершин, або, еквівалентно, це граф, у якому кожну пару вершин можна з'єднати k шляхами, що не мають спільних вершин. Оскільки ціх шляхи повинні виходити з цих двох вершин через різні ребра, вершинно k-зв'язний граф повинен мати виродженість принаймні k. Близьке до k-ядер поняття, яке ґрунтується на зв'язності вершин, вивчається в теорії соціальних мереж під назвою [en].

Якщо деревна ширина або (шляхова ширина) графа не перевищує k, то він є підграфом хордального графа, що має досконалий порядок виключення, за якого кожна вершина має не більше k попередніх сусідів. Таким чином, виродженість не перевищує деревної ширини та колійної ширини. Однак існують графи з обмеженою виродженістю та необмеженою деревною шириною, як, наприклад, решітки.

Гіпотеза Ердеша — Бура стосується зв'язку виродженості графа G і числа Рамсея графа G, найбільшого n, для якого будь-яке двоколірне розфарбування ребер повного графа з n вершинами повинне містити монохромну копію графа G. Конкретно, гіпотеза стверджує, що для будь-якого фіксованого значення k число Рамсея k-вироджених графів зростає лінійно від числа вершин графів. Гіпотезу довів Лі.

Нескінченні графи

Хоча поняття виродженості та числа розфарбовування часто застосовують у контексті скінченних графів, початковою метою Ердеша та Хайнала була теорія нескінченних графів. Число розфарбовування для нескінченного графа G можна визначити аналогічно визначенню для скінченних графів як найменше кардинальне число α, для якого існує впорядкування вершин графа G, що є цілком упорядкованим, у якому кожна вершина має менше α сусідів серед попередніх вершин в упорядкуванні. Нерівність між числом розфарбовування та хроматичним числом виконується і для нескінченного випадку. Ердеш і Хайнал стверджували це, і на час публікації їхньої роботи факт був добре відомим.

Виродження випадкових підмножин нескінченних ґраток вивчається під назвою [en].

Примітки

  1. Altaf-Ul-Amin, Nishikata, Koma, Miyasato и др., 2003.
  2. Wuchty, Almaas, 2005.
  3. Bader, Hogue, 2003.
  4. Freuder, 1982.
  5. Kirousis, Thilikos, 1996.
  6. Erdős, Hajnal, 1966.
  7. Irani, 1994.
  8. Matula, Beck, 1983.
  9. Lick, White, 1970.
  10. Barabási, Albert, 1999.
  11. Єнсен і Тофт (Jensen, Toft, 2011), с. 78: «Легко бачити, що col(G) = Δ(G) + 1 тоді й лише тоді, коли G має Δ(G)-регулярну компоненту». В позначеннях Єнсена і Тофта col(G) дорівнює виродженню + 1, а Δ(G) дорівнює найбільшому степеню вершини.
  12. Matula, 1968.
  13. Lick, White, 1970, с. 1084 Proposition 1.
  14. Chrobak, Eppstein, 1991.
  15. Seidman, 1983.
  16. Bollobás, 1984.
  17. Łuczak, 1991.
  18. Dorogovtsev, Goltsev, Mendes, 2006.
  19. Gaertler, Patrignani, 2004.
  20. Alvarez-Hamelin, Dall'Asta, Barrat, Vespignani, 2005.
  21. Gabow, Westermann, 1992.
  22. Venkateswaran, 2004.
  23. Asahiro, Miyano, Ono, Zenmyo, 2006.
  24. Kowalik, 2006.
  25. Dean, Hutchinson, Scheinerman, 1991.
  26. Szekeres, Wilf, 1968.
  27. Moody, White, 2003.
  28. Robertson, Seymour, 1984.
  29. Burr, Erdős, 1975.
  30. Lee, 2017.

Література

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Дата публікації:
k vi rodzhenij graf ce neoriyentovanij graf u yakomu kozhen pidgraf maye vershini zi stepenem sho ne perevishuye k Vi rodzhenist grafa ce najmenshe znachennya k dlya yakogo graf ye k virodzhenim Virodzhenist grafa vidbivaye naskilki graf rozridzhenij i z tochnistyu do stalogo mnozhnika vidbivaye inshi zahodi rozridzhenosti taki yak derevnist grafa 2 virodzhenij graf kozhna vershina maye ne bilshe dvoh susidiv zliva tak sho najpravisha vershina bud yakogo pidgrafa maye stepin dva i menshe Jogo 2 yadro pidgraf sho zalishayetsya pislya vidalennya vershin zi stepenem menshim za dva vidileno kolorom Virodzhenist vidoma takozh pid nazvoyu k ya derne chislo shirina i zache plennya i po suti ce te same sho j chislo rozfarbovuva nnya abo chislo Sekeresha Vi lfa k virodzheni grafi nazivayutsya takozh k indukti vnimi gra fami Virodzhenist grafa mozhna obchisliti za linijnij chas za dopomogoyu algoritmu sho poslidovno vidalyaye vershini z najmenshim stepenem Komponentu zv yaznosti sho zalishilasya pislya vidalennya vsih vershin zi stepenem menshim vid k nazivayut k yadro m grafa i virodzhenist grafa dorivnyuye najbilshomu znachennyu k dlya yakogo isnuye k yadro PrikladiBud yakij lis abo maye izolovanu vershinu bez sumizhnih reber abo listkovu vershinu incidentnu rivno odnomu rebru tak sho lisi i dereva ye 1 virodzhenimi grafami Bud yakij skinchennij planarnij graf maye vershinu stepenya 5 abo menshe tomu bud yakij planarnij graf ye 5 virodzhenim i virodzhenist bud yakogo planarnogo grafa ne perevishuye 5 Podibno do cogo virodzhenist bud yakogo zovniplanarnogo grafa ne perevishuye 2 a virodzhenist grafiv Apolloniya dorivnyuye 3 Model Barabashi Albert generuvannya vipadkovih bezmasshtabnih merezh maye yak parametr chislo m take sho kozhna vershina dodana do grafa pov yazana rebrami z m dodanih ranishe vershin Zvidsi viplivaye sho bud yakij pidgraf merezhi otrimanij takim sposobom maye stepin vershin ne menshij vid m ce stepin ostannoyi vershini dodanoyi do grafa tak sho merezhi Barabashi Albert avtomatichno m virodzheni Bud yakij k regulyarnij graf maye virodzhenist rivno k Strogishe virodzhenist grafa dorivnyuye najbilshomu stepenyu vershini todi j lishe todi koli prinajmni odna z komponent zv yaznosti grafa ye regulyarnoyu i maye stepin samogo grafa Dlya reshti grafiv virodzhenist strogo mensha vid maksimalnogo stepenya vershin grafa ViznachennyaChislo rozfarbovuvannya grafa G vveli Erdesh i Hajnal yak najbilshe k displaystyle kappa dlya yakogo isnuye vporyadkuvannya vershin grafa G za yakogo kozhna vershina maye menshe k displaystyle kappa susidiv sho pereduyut vershini v poryadku Slid vidriznyati ce chislo vid hromatichnogo chisla grafa G najmenshogo chisla koloriv neobhidnih dlya rozfarbuvannya vershin za yakogo niyaki dvi sumizhni vershini ne pofarbovani v odnakovij kolir Uporyadkuvannya sho viznachaye chislo rozfarbovuvannya daye poryadok rozfarbovuvannya vershin grafa G v chislo koloriv sho dorivnyuye chislu rozfarbovuvannya ale v zagalnomu vipadku hromatichne chislo mozhe buti menshim vid cogo chisla Lik ta Vajt viznachili virodzhenist grafa G yak najmenshe chislo k dlya yakogo bud yakij porodzhenij pidgraf grafa G mistit vershinu z k i menshe susidami Viznachennya ne zminitsya yaksho zamist porodzhenih pidgrafiv brati dovilni pidgrafi oskilki neporodzhenij pidgraf mozhe mati stepeni vershin sho ne perevishuyut stepeniv vershin porodzhenogo z tim samim naborom vershin pidgrafa Dva ponyattya chislo rozfarbovuvannya ta virodzhenist ekvivalentni v bud yakomu skinchennomu grafi virodzhenist na odinicyu mensha vid chisla rozfarbovuvannya Yaksho graf maye uporyadkuvannya z chislom rozfarbovuvannya k displaystyle kappa to v kozhnomu pidgrafi H vershina sho nalezhit H i ye ostannoyu v uporyadkuvanni maye ne bilshe k 1 displaystyle kappa 1 susidiv u H Z inshogo boku yaksho G dorivnyuye k virodzhenosti to vporyadkuvannya z chislom rozfarbovuvannya k 1 mozhna otrimati poslidovnim znahodzhennyam vershini v z maksimum k susidami vidalennyam vershini v z grafa vporyadkuvannyam reshti vershin i dodavannyam vershini v v kinec poryadku Tretye ekvivalentne viznachennya k virodzhenosti grafa G abo sho chislo rozfarbovuvannya ne perevishuye k 1 graf k virodzhenij todi j lishe todi koli rebra grafa G mozhna zoriyentuvati z utvorennyam spryamovanogo aciklichnogo grafa z napivstepenem vihodu sho ne perevishuye k Taku oriyentaciyu mozhna otrimati oriyentuvannyam kozhnogo rebra v bik ranishoyi z dvoh vershin rebra v uporyadkuvanni Z inshogo boku yaksho zadano oriyentaciyu z napivstepenem vihodu k uporyadkuvannya z chislom rozfarbovuvannya k 1 mozhna otrimati yak toplogichne vporyadkuvannya oriyentovanogo aciklichnogo grafa k Yadrak Yadro grafa G ce najbilshij zv yaznij pidgraf grafa G v yakomu vsi vershini mayut stepin prinajmni k Ekvivalentno ce odna zi zv yaznih komponent pidgrafa G utvorenogo poslidovnim vidalennyam usih vershin zi stepenem menshim vid k Yaksho isnuye neporozhnye k yadro yasno sho G maye virodzhenist ne menshu vid k a virodzhenist grafa G ce najbilshe chislo k dlya yakogo G maye k yadro Vershina u displaystyle u maye yadernist c displaystyle c yaksho vershina nalezhit c displaystyle c yadru ale ne nalezhit c 1 displaystyle c 1 yadru Ponyattya k yadra vvedeno dlya vivchennya grupuvannya v socialnih merezhah ta dlya opisu rozgortannya vipadkovih grafiv Ponyattya takozh pereneseno v bioinformatiku ta vizualizaciyu merezh AlgoritmiYak opisuyut Matula i Bek mozhna znajti za linijnij chas uporyadkuvannya vershin u skinchennomu grafi G sho optimizuye chislo rozfarbovuvannya uporyadkuvannya yaksho dlya znahodzhennya ta vidalennya vershin najmenshogo stepenya vikoristovuvati en Virodzhenist todi ce najbilshij stepin bud yakoyi vershini na moment yiyi vidalennya Detalnishe algoritm pracyuye tak Stvoryuyemo spisok vivedennya L Dlya kozhnoyi vershini v grafa G obchislyuyemo chislo dv chislo susidiv vershini v sho she ne mistyatsya v L Spochatku ci chisla prosto rivni stepenyam vershin Stvoryuyemo masiv D v yakomu D i mistit spisok vershin v yaki ne vhodyat do spisku L dlya yakih dv i Prisvoyuyemo k znachennya 0 Povtoryuyemo n raziv pereglyadayemo elementi masivu D 0 D 1 doki znajdemo i yakogo D i ne porozhnye prisvoyuyemo k bilshe z dvoh znachen k i vibirayemo vershinu v z D i Dodayemo v na pochatok chergi L i vidalyayemo yiyi z D i Dlya kozhnoyi vershini w yaka susidnya v i ne mistitsya v L vidnimayemo odinicyu vid dw i perenosimo w v element masivu D yakij vidpovidaye novomu znachennyu dw Pri zavershenni algoritmu k mistit virodzhenist grafa G a spisok L mistit vershini v optimalnomu poryadku dlya chisla rozfarbovuvannya U grafi G i yadra ce pidspiski spisku L sho skladayutsya z vershin dodanih do L pislya togo yak k vpershe nabulo znachennya bilshogo abo rivnogo i Inicializuvati zminni L dv D i k mozhna legko za linijnij chas Znahodzhennya chergovoyi vershini sho vidalyayetsya i pererahunok elementiv D sho mistyat susidiv vershini v zajmaye chas proporcijnij znachennyu dv na comu kroci ale suma takih znachen dorivnyuye chislu reber grafa tak sho zagalnij chas linijnij Zv yazok z inshimi parametrami grafaYaksho graf G ye oriyentovanim aciklichnim z napivstepenem vihodu k jogo dugi mozhna rozbiti na k lisiv viborom odnogo lisu dlya kozhnoyi vihidnoyi dugi kozhnoyi vershini Otzhe derevnist grafa G ne perevishuye jogo virodzhenosti Z inshogo boku graf iz n vershinami yakij mozhna rozbiti na k lisiv maye ne bilshe k n 1 reber a tomu maye vershini zi stepenem sho ne perevishuye 2k 1 Tobto virodzhenist udvichi mensha vid derevnosti grafa Takozh za polinomialnij chas mozhna obchisliti oriyentaciyu grafa sho minimizuye stepin napivvihodu ale ne musit buti aciklichnoyu Rebra grafa z takoyu oriyentaciyeyu mozhna rozbiti tim samim sposobom na k psevdolisiv I navpaki bud yake rozbittya reber grafa na k psevdolisiv privodit do oriyentaciyi z najbilshim napivstepenem vihodu k viborom oriyentaciyi z napivstepenem vihodu 1 dlya kozhnogo psevdolisu tak sho najmenshij napivstepin vihodu takoyi oriyentaciyi ye psevdoderevnistyu yaka znovu zh ne perevishuye virodzhenosti Tovshina takozh z tochnistyu do stalogo mnozhnika proporcijna derevnosti tak sho te same istinne j dlya virodzhenosti k Virodzhenij graf maye hromatichne chislo sho ne perevishuye k 1 Ce mozhna pokazati prostoyu indukciyeyu za kilkistyu vershin tak samo yak pri dovedenni teoremi pro shist farb dlya planarnih grafiv Oskilki hromatichne chislo ye verhnoyu mezheyu poryadku najbilshoyi kliki cej poryadok ne perevishuye virodzhenosti plyus odinicya Skoristavshis algoritmom zhadibnogo rozfarbuvannya dlya poryadku z optimalnim chislom rozfarbovuvannya mozhna rozfarbuvati k virodzhenij graf vikoristavshi ne bilshe k 1 koloru Vershinno k zv yaznij graf ce graf yakij ne mozhna rozbiti na kilka komponentiv vidalivshi menshe k vershin abo ekvivalentno ce graf u yakomu kozhnu paru vershin mozhna z yednati k shlyahami sho ne mayut spilnih vershin Oskilki cih shlyahi povinni vihoditi z cih dvoh vershin cherez rizni rebra vershinno k zv yaznij graf povinen mati virodzhenist prinajmni k Blizke do k yader ponyattya yake gruntuyetsya na zv yaznosti vershin vivchayetsya v teoriyi socialnih merezh pid nazvoyu en Yaksho derevna shirina abo shlyahova shirina grafa ne perevishuye k to vin ye pidgrafom hordalnogo grafa sho maye doskonalij poryadok viklyuchennya za yakogo kozhna vershina maye ne bilshe k poperednih susidiv Takim chinom virodzhenist ne perevishuye derevnoyi shirini ta kolijnoyi shirini Odnak isnuyut grafi z obmezhenoyu virodzhenistyu ta neobmezhenoyu derevnoyu shirinoyu yak napriklad reshitki Gipoteza Erdesha Bura stosuyetsya zv yazku virodzhenosti grafa G i chisla Ramseya grafa G najbilshogo n dlya yakogo bud yake dvokolirne rozfarbuvannya reber povnogo grafa z n vershinami povinne mistiti monohromnu kopiyu grafa G Konkretno gipoteza stverdzhuye sho dlya bud yakogo fiksovanogo znachennya k chislo Ramseya k virodzhenih grafiv zrostaye linijno vid chisla vershin grafiv Gipotezu doviv Li Neskinchenni grafiHocha ponyattya virodzhenosti ta chisla rozfarbovuvannya chasto zastosovuyut u konteksti skinchennih grafiv pochatkovoyu metoyu Erdesha ta Hajnala bula teoriya neskinchennih grafiv Chislo rozfarbovuvannya dlya neskinchennogo grafa G mozhna viznachiti analogichno viznachennyu dlya skinchennih grafiv yak najmenshe kardinalne chislo a dlya yakogo isnuye vporyadkuvannya vershin grafa G sho ye cilkom uporyadkovanim u yakomu kozhna vershina maye menshe a susidiv sered poperednih vershin v uporyadkuvanni Nerivnist mizh chislom rozfarbovuvannya ta hromatichnim chislom vikonuyetsya i dlya neskinchennogo vipadku Erdesh i Hajnal stverdzhuvali ce i na chas publikaciyi yihnoyi roboti fakt buv dobre vidomim Virodzhennya vipadkovih pidmnozhin neskinchennih gratok vivchayetsya pid nazvoyu en PrimitkiAltaf Ul Amin Nishikata Koma Miyasato i dr 2003 Wuchty Almaas 2005 Bader Hogue 2003 Freuder 1982 Kirousis Thilikos 1996 Erdos Hajnal 1966 Irani 1994 Matula Beck 1983 Lick White 1970 Barabasi Albert 1999 Yensen i Toft Jensen Toft 2011 s 78 Legko bachiti sho col G D G 1 todi j lishe todi koli G maye D G regulyarnu komponentu V poznachennyah Yensena i Tofta col G dorivnyuye virodzhennyu 1 a D G dorivnyuye najbilshomu stepenyu vershini Matula 1968 Lick White 1970 s 1084 Proposition 1 Chrobak Eppstein 1991 Seidman 1983 Bollobas 1984 Luczak 1991 Dorogovtsev Goltsev Mendes 2006 Gaertler Patrignani 2004 Alvarez Hamelin Dall Asta Barrat Vespignani 2005 Gabow Westermann 1992 Venkateswaran 2004 Asahiro Miyano Ono Zenmyo 2006 Kowalik 2006 Dean Hutchinson Scheinerman 1991 Szekeres Wilf 1968 Moody White 2003 Robertson Seymour 1984 Burr Erdos 1975 Lee 2017 LiteraturaAltaf Ul Amin M Nishikata K Koma T Miyasato T Shinbo Y Arifuzzaman M Wada C Maeda M Oshima T Prediction of protein functions based on k cores of protein protein interaction networks and amino acid sequences Genome Informatics 2003 T 14 S 498 499 Alvarez Hamelin Jose Ignacio Dall Asta Luca Barrat Alain Vespignani Alessandro k core decomposition a tool for the visualization of large scale networks 2005 arXiv cs 0504107 Asahiro Yuichi Miyano Eiji Ono Hirotaka Zenmyo Kouhei Graph orientation algorithms to minimize the maximum outdegree CATS 06 Proceedings of the 12th Computing The Australasian Theory Symposium Darlinghurst Australia Australia Australian Computer Society Inc 2006 S 11 20 ISBN 1 920682 33 3 Bader Gary D Hogue Christopher W V An automated method for finding molecular complexes in large protein interaction networks 2003 T 4 vip 1 DOI 10 1186 1471 2105 4 2 PMID 12525261 Barabasi Albert Laszlo Albert Reka Emergence of scaling in random networks Science 1999 T 286 vip 5439 S 509 512 DOI 10 1126 science 286 5439 509 PMID 10521342 z dzherela 17 kvitnya 2012 Bollobas Bela The evolution of sparse graphs Graph Theory and Combinatorics Proc Cambridge Combinatorial Conf in honor of Paul Erdos Academic Press 1984 S 35 57 Burr Stefan A Erdos Paul On the magnitude of generalized Ramsey numbers for graphs Infinite and finite sets Colloq Keszthely 1973 dedicated to P Erdos on his 60th birthday Vol 1 Amsterdam North Holland 1975 T 10 S 214 240 Colloq Math Soc Janos Bolyai Chrobak Marek Eppstein David Planar orientations with low out degree and compaction of adjacency matrices 1991 T 86 vip 2 S 243 266 DOI 10 1016 0304 3975 91 90020 3 Dean Alice M Hutchinson Joan P Scheinerman Edward R On the thickness and arboricity of a graph 1991 T 52 vip 1 S 147 151 Series B DOI 10 1016 0095 8956 91 90100 X Dorogovtsev S N Goltsev A V Mendes J F F k core organization of complex networks Physical Review Letters 2006 T 96 vip 4 S 040601 arXiv cond mat 0509102 DOI 10 1103 PhysRevLett 96 040601 PMID 16486798 Erdos Paul Hajnal Andras On chromatic number of graphs and set systems Acta Mathematica Hungarica 1966 T 17 vip 1 2 S 61 99 DOI 10 1007 BF02020444 Freuder Eugene C A sufficient condition for backtrack free search 1982 T 29 vip 1 S 24 32 DOI 10 1145 322290 322292 Gabow H N Westermann H H Forests frames and games algorithms for matroid sums and applications 1992 T 7 vip 1 S 465 497 DOI 10 1007 BF01758774 Gaertler Marco Patrignani Maurizio Dynamic analysis of the autonomous system graph Proc 2nd International Workshop on Inter Domain Performance and Simulation IPS 2004 2004 S 13 24 Irani Sandy Coloring inductive graphs on line 1994 T 11 vip 1 S 53 72 DOI 10 1007 BF01294263 Jensen Tommy R Toft Bjarne Graph Coloring Problems John Wiley amp Sons 2011 T 39 Wiley Series in Discrete Mathematics and Optimization ISBN 9781118030745 Kirousis L M Thilikos D M The linkage of a graph 1996 T 25 vip 3 S 626 647 DOI 10 1137 S0097539793255709 Kowalik Lukasz Approximation scheme for lowest outdegree orientation and graph density measures Proceedings of the 17th International Symposium on Algorithms and Computation ISAAC 2006 Springer Verlag 2006 T 4288 S 557 566 DOI 10 1007 11940128 56 Lee Choongbum Ramsey numbers of degenerate graphs Annals of Mathematics 2017 T 185 vip 3 S 791 829 arXiv 1505 04773 DOI 10 4007 annals 2017 185 3 2 Lick Don R White Arthur T k degenerate graphs 1970 T 22 S 1082 1096 DOI 10 4153 CJM 1970 125 1 Luczak Tomasz Size and connectivity of the k core of a random graph 1991 T 91 vip 1 S 61 68 DOI 10 1016 0012 365X 91 90162 U Matula D W A min max theorem for graphs with application to graph coloring SIAM 1968 National Meeting 1968 T 10 vip 4 S 481 482 DOI 10 1137 1010115 Matula D W Beck L L Smallest last ordering and clustering and graph coloring algorithms 1983 T 30 vip 3 S 417 427 DOI 10 1145 2402 322385 Moody James White Douglas R Structural cohesion and embeddedness a hierarchical conception of social groups 2003 T 68 vip 1 S 1 25 DOI 10 2307 3088904 Robertson Neil Seymour Paul Graph minors III Planar tree width 1984 T 36 vip 1 S 49 64 DOI 10 1016 0095 8956 84 90013 3 Seidman Stephen B Network structure and minimum degree 1983 T 5 vip 3 S 269 287 DOI 10 1016 0378 8733 83 90028 X Szekeres George Wilf Herbert S An inequality for the chromatic number of a graph 1968 T 4 S 1 3 DOI 10 1016 S0021 9800 68 80081 X Venkateswaran V Minimizing maximum indegree 2004 T 143 vip 1 3 S 374 378 DOI 10 1016 j dam 2003 07 007 Wuchty S Almaas E Peeling the yeast protein network 2005 T 5 vip 2 S 444 449 DOI 10 1002 pmic 200400962 PMID 15627958
Топ