Кнезерів граф — це неорієнтований граф, що описує відношення неперетинності -елементних підмножин -елементної множини між собою.
Формальне визначення
Нехай . Тоді кнезерів граф визначається як пара множин вершин і ребер
Часткові випадки
- При кнезерів граф є порожнім графом (без ребер).
- При кнезерів граф являє собою парування. Звичайно, розглядається лише випадок
- При кнезерів граф є повним графом.
- Граф є графом Петерсена.
- Основний інтерес становлять кнезерові графи зі значеннями параметра в проміжку .
Хроматичне число
Кнезерів граф, крім усього іншого, можна використати для ілюстрації часткового випадку непрактичності тривіальних оцінок хроматичного числа графу через клікове число і число незалежності.
Загальні тривіальні оцінки
Числом незалежності називається розмір максимально незалежної множини вершин у графі . Визначення розмальовки означає, що визначає максимальну кількість вершин, яку можна пофарбувати в один колір. Виходячи з деякої модифікації принципу Діріхле, хроматичне число графу можна оцінити як
Аналогічно визначається клікове число як розмір максимальної кліки. Це число дає оцінку
Як правило, перша оцінка краща від другої — а саме, для випадкового графу на вершинах ймовірність того, що прямує до одиниці зі зростанням . З того, що кожній із клік графу можна зіставити незалежну множину графу , можна зробити висновок, що те саме виконується для .
Однак кнезерів граф дає наочну ілюстрацію цілого класу графів, що дискредитують викладені вище оцінки (в загальному випадку, а не для випадкових графів).
Клікове число
Не обмежуючи загальності, припустимо, що входить у кліку як вершина. Тоді, з визначення кліки, жодна інша вершина не повинна містити у своїй підмножині жодного елемента з . При подальшому аналогічному аналізі це очевидним чином дає
Число незалежності
З комбінаторних міркувань очевидно, що . Для побудови незалежної множини такого розміру достатньо зафіксувати одну вершину і перебрати всі -елементні підмножини, що містять її. За визначенням, між будь-якою парою таких множин не буде ребра.
Ердеш, [en] і [en] 1961 року опублікували доведення теореми, що стверджує рівність у викладеній вище оцінці. За словами математиків, вони знайшли доведення ще за кілька десятиліть до цього, але тоді не було сенсу його публікувати, тому що теорема нікого не цікавила. До речі, граф Кнезера в той час ще не був відомий, так що Ердеш, Ко і Радо доводили теорему в елементарному формулюванні максимальної кількості -елементних підмножин -елементної множини, що попарно перетинаються.
Користуючись тривіальною оцінкою, з даного значення числа незалежності можна отримати лише , тобто . Ця оцінка майже не відрізняється від оцінки через клікове число.
Точне значення
Сформульована 1955 року [en] і доведена 1977 року Ласло Ловасом теорема стверджує, що
Побудова оптимальної розмальовки
Для будь-якого пофарбуємо в -й колір кожну підмножину, мінімальним елементом якої є число . Пофарбуємо в колір кожну з підмножин, що містяться у множині . Оскільки в зазначеній множині елемент, то будь-які дві її -елементних підмножини перетинаються, тобто між відповідними вершинами немає ребра. Отже, побудована розмальовка правильна.
Див. також
Джерела
- Науково-популярний фізико-математичний журнал «Квант», 2011 рік, «Гіпотеза Кнезера і топологічний метод у комбінаториці» (А. Райгородський)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Knezeriv graf K G n k displaystyle KG n k ce neoriyentovanij graf sho opisuye vidnoshennya neperetinnosti k displaystyle k elementnih pidmnozhin n displaystyle n elementnoyi mnozhini mizh soboyu Formalne viznachennyaNehaj R n 1 2 n displaystyle R n 1 2 cdots n Todi knezeriv graf K G n k V E displaystyle KG n k V E viznachayetsya yak para mnozhin vershin V S S R n S k displaystyle V S mid S subset R n S k i reber E A B A V B V A B displaystyle E A B mid A in V B in V A cap B varnothing Chastkovi vipadkiPri k gt n 2 displaystyle k gt frac n 2 knezeriv graf ye porozhnim grafom bez reber Pri k n 2 displaystyle k frac n 2 knezeriv graf yavlyaye soboyu paruvannya Zvichajno rozglyadayetsya lishe vipadok n 0 mod 2 displaystyle n equiv 0 pmod 2 Pri k 1 displaystyle k 1 knezeriv graf ye povnim grafom Graf K G 5 2 displaystyle KG 5 2 ye grafom Petersena Osnovnij interes stanovlyat knezerovi grafi zi znachennyami parametra k displaystyle k v promizhku 2 n 2 displaystyle 2 frac n 2 Hromatichne chisloKnezeriv graf krim usogo inshogo mozhna vikoristati dlya ilyustraciyi chastkovogo vipadku nepraktichnosti trivialnih ocinok hromatichnogo chisla grafu cherez klikove chislo i chislo nezalezhnosti Zagalni trivialni ocinki Chislom nezalezhnosti a G displaystyle alpha G nazivayetsya rozmir maksimalno nezalezhnoyi mnozhini vershin u grafi G displaystyle G Viznachennya rozmalovki oznachaye sho a G displaystyle alpha G viznachaye maksimalnu kilkist vershin yaku mozhna pofarbuvati v odin kolir Vihodyachi z deyakoyi modifikaciyi principu Dirihle hromatichne chislo grafu mozhna ociniti yak x G V a G displaystyle chi G geq frac V alpha G Analogichno viznachayetsya klikove chislo w G displaystyle omega G yak rozmir maksimalnoyi kliki Ce chislo daye ocinku x G w G displaystyle chi G geq omega G Yak pravilo persha ocinka krasha vid drugoyi a same dlya vipadkovogo grafu G displaystyle G na n displaystyle n vershinah jmovirnist togo sho a G lt 2 log 2 n displaystyle alpha G lt 2 log 2 n pryamuye do odinici zi zrostannyam n displaystyle n Z togo sho kozhnij iz klik grafu G displaystyle G mozhna zistaviti nezalezhnu mnozhinu grafu G displaystyle not G mozhna zrobiti visnovok sho te same vikonuyetsya dlya w G displaystyle omega G Odnak knezeriv graf daye naochnu ilyustraciyu cilogo klasu grafiv sho diskredituyut vikladeni vishe ocinki v zagalnomu vipadku a ne dlya vipadkovih grafiv Klikove chislo Ne obmezhuyuchi zagalnosti pripustimo sho 1 k displaystyle 1 dots k vhodit u kliku yak vershina Todi z viznachennya kliki zhodna insha vershina ne povinna mistiti u svoyij pidmnozhini zhodnogo elementa z 1 k displaystyle 1 dots k Pri podalshomu analogichnomu analizi ce ochevidnim chinom daye w K G n k n k displaystyle omega KG n k left lfloor frac n k right rfloor Chislo nezalezhnosti Dokladnishe Chislo nezalezhnosti Z kombinatornih mirkuvan ochevidno sho a K G n k n 1 k 1 displaystyle alpha KG n k geq binom n 1 k 1 Dlya pobudovi nezalezhnoyi mnozhini takogo rozmiru dostatno zafiksuvati odnu vershinu i perebrati vsi k displaystyle k elementni pidmnozhini sho mistyat yiyi Za viznachennyam mizh bud yakoyu paroyu takih mnozhin ne bude rebra Erdesh en i en 1961 roku opublikuvali dovedennya teoremi sho stverdzhuye rivnist u vikladenij vishe ocinci Za slovami matematikiv voni znajshli dovedennya she za kilka desyatilit do cogo ale todi ne bulo sensu jogo publikuvati tomu sho teorema nikogo ne cikavila Do rechi graf Knezera v toj chas she ne buv vidomij tak sho Erdesh Ko i Rado dovodili teoremu v elementarnomu formulyuvanni maksimalnoyi kilkosti k displaystyle k elementnih pidmnozhin n displaystyle n elementnoyi mnozhini sho poparno peretinayutsya Koristuyuchis trivialnoyu ocinkoyu z danogo znachennya chisla nezalezhnosti mozhna otrimati lishe x K G n k n k n 1 k 1 n k displaystyle chi KG n k geq frac binom n k binom n 1 k 1 frac n k tobto x K G n k n k displaystyle chi KG n k geq left lceil frac n k right rceil Cya ocinka majzhe ne vidriznyayetsya vid ocinki cherez klikove chislo Tochne znachennya Sformulovana 1955 roku en i dovedena 1977 roku Laslo Lovasom teorema stverdzhuye sho x K G n k n 2 k 2 displaystyle chi KG n k n 2k 2 Pobudova optimalnoyi rozmalovki Dlya bud yakogo j 1 2 n 2 k 1 displaystyle j 1 2 ldots n 2k 1 pofarbuyemo v j displaystyle j j kolir kozhnu pidmnozhinu minimalnim elementom yakoyi ye chislo j displaystyle j Pofarbuyemo v kolir n 2 k 2 displaystyle n 2k 2 kozhnu z pidmnozhin sho mistyatsya u mnozhini n 2 k 2 n 2 k 3 n displaystyle n 2k 2 n 2k 3 ldots n Oskilki v zaznachenij mnozhini 2 k 1 displaystyle 2k 1 element to bud yaki dvi yiyi k displaystyle k elementnih pidmnozhini peretinayutsya tobto mizh vidpovidnimi vershinami nemaye rebra Otzhe pobudovana rozmalovka pravilna Div takozhRozfarbovuvannya grafiv Hromatichne chislo Klika teoriya grafiv Nezalezhna mnozhina teoriya grafiv DzherelaNaukovo populyarnij fiziko matematichnij zhurnal Kvant 2011 rik Gipoteza Knezera i topologichnij metod u kombinatorici A Rajgorodskij