Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Граф Мейнеля це граф у якому будь який непарний цикл довжини п ять і більше має принаймні дві хорди тобто два ребра що з

Граф Мейнеля

Граф Мейнеля

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

image
У графі Мейнеля будь-який довгий непарний цикл (такий як чорний 5-цикл, показаний тут) повинен мати принаймні дві хорди (зелені)

Графи Мейнеля названо ім'ям (відомого також за гіпотезою Мейнеля), який 1976 року довів, що вони є досконалими графами задовго до доведення сильної теореми про досконалі графи, яка повністю описує досконалі графи. Той самий результат незалежно виявили Маркосян і Карапетян.

Досконалість

Графи Мейнеля є підкласом досконалих графів. Будь-який породжений підграф графа Мейнеля є іншим графом Мейнеля і в будь-якому графі Мейнеля розмір найбільшої кліки дорівнює найменшому числу кольорів, необхідних для розфарбовування графа. Таким чином, графи Мейнеля задовольняють визначенню досконалих графів, що в будь-якому породженому підграфі число клік дорівнює хроматичному числу.

Графи Мейнеля називають також дуже сильно досконалими графами, оскільки (як припустив Мейнель і довів Хланг) їх можна описати властивістю, яка узагальнює визначення властивості строго досконалих графів — у будь-якому породженому підграфі графа Мейнеля будь-яка вершина належить незалежній множині, котра перетинається з будь-якою максимальною клікою.

Пов'язані класи графів

Графи Мейнеля містять хордальні графи, графи парності та їх підкласи, інтервальні графи, дистанційно-успадковувані графи, двочасткові графи та реберно-досконалі графи.

image
Будиночок є досконалим графом, але не є графом Мейнеля

Хоча графи Мейнеля утворюють дуже загальний підклас графів, вони не включають усіх досконалих графів. Наприклад, будиночок (п'ятикутник з однією хордою) досконалий, але графом Мейнеля не є.

Алгоритми та складність

Графи Мейнеля можна розпізнати за поліноміальний час та деякі задачі оптимізації на графах, зокрема, розфарбовування графів, які NP-складні для довільних графів, можна розв'язати за поліноміальний час для графів Мейнеля.

Примітки

  1. Meyniel graphs [ 2019-07-28 у Wayback Machine.], Information System on Graph Classes and their Inclusions, retrieved 2016-09-25.
  2. Meyniel, 1976, с. 339–342.
  3. Маркосян, Карапетян, 1976, с. 292–296.
  4. Hoàng, 1987, с. 302–312.
  5. Burlet, Fonlupt, 1984, с. 225–252.
  6. Hertz, 1990, с. 231–240.
  7. Roussel, Rusu, 2001, с. 107–123.

Література

  • Meyniel H. On the perfect graph conjecture // . — 1976. — Т. 16, вип. 4. — С. 339–342. — DOI:10.1016/S0012-365X(76)80008-8.
  • С. Маркосян, И. Карапетян. О совершенных графах // ДАН Арм. ССР. — 1976. — Т. LXIII, вип. 5.
  • Hoàng C. T. On a conjecture of Meyniel // . — 1987. — Т. 42, вип. 3. — С. 302–312. — (Series B). — DOI:10.1016/0095-8956(87)90047-5.
  • Burlet M., Fonlupt J. Polynomial algorithm to recognize a Meyniel graph // Topics on perfect graphs. — North-Holland, Amsterdam, 1984. — Т. 88. — С. 225–252. — (North-Holland Math. Stud.) — DOI:10.1016/S0304-0208(08)72938-4.
  • Hertz A. A fast algorithm for coloring Meyniel graphs // . — 1990. — Т. 50, вип. 2. — С. 231–240. — (Series B). — DOI:10.1016/0095-8956(90)90078-E.
  • Roussel F., Rusu I. An O(n2) algorithm to color Meyniel graphs // . — 2001. — Т. 235, вип. 1—3. — С. 107–123. — DOI:10.1016/S0012-365X(00)00264-8.

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

Graf Mejnelya ce graf u yakomu bud yakij neparnij cikl dovzhini p yat i bilshe maye prinajmni dvi hordi tobto dva rebra sho z yednuyut nesusidni vershini ciklu Hordi mozhut buti takimi sho ne peretinayutsya yak na malyunku a mozhut i peretinatisya U grafi Mejnelya bud yakij dovgij neparnij cikl takij yak chornij 5 cikl pokazanij tut povinen mati prinajmni dvi hordi zeleni Grafi Mejnelya nazvano im yam vidomogo takozh za gipotezoyu Mejnelya yakij 1976 roku doviv sho voni ye doskonalimi grafami zadovgo do dovedennya silnoyi teoremi pro doskonali grafi yaka povnistyu opisuye doskonali grafi Toj samij rezultat nezalezhno viyavili Markosyan i Karapetyan DoskonalistGrafi Mejnelya ye pidklasom doskonalih grafiv Bud yakij porodzhenij pidgraf grafa Mejnelya ye inshim grafom Mejnelya i v bud yakomu grafi Mejnelya rozmir najbilshoyi kliki dorivnyuye najmenshomu chislu koloriv neobhidnih dlya rozfarbovuvannya grafa Takim chinom grafi Mejnelya zadovolnyayut viznachennyu doskonalih grafiv sho v bud yakomu porodzhenomu pidgrafi chislo klik dorivnyuye hromatichnomu chislu Grafi Mejnelya nazivayut takozh duzhe silno doskonalimi grafami oskilki yak pripustiv Mejnel i doviv Hlang yih mozhna opisati vlastivistyu yaka uzagalnyuye viznachennya vlastivosti strogo doskonalih grafiv u bud yakomu porodzhenomu pidgrafi grafa Mejnelya bud yaka vershina nalezhit nezalezhnij mnozhini kotra peretinayetsya z bud yakoyu maksimalnoyu klikoyu Pov yazani klasi grafivGrafi Mejnelya mistyat hordalni grafi grafi parnosti ta yih pidklasi intervalni grafi distancijno uspadkovuvani grafi dvochastkovi grafi ta reberno doskonali grafi Budinochok ye doskonalim grafom ale ne ye grafom Mejnelya Hocha grafi Mejnelya utvoryuyut duzhe zagalnij pidklas grafiv voni ne vklyuchayut usih doskonalih grafiv Napriklad budinochok p yatikutnik z odniyeyu hordoyu doskonalij ale grafom Mejnelya ne ye Algoritmi ta skladnistGrafi Mejnelya mozhna rozpiznati za polinomialnij chas ta deyaki zadachi optimizaciyi na grafah zokrema rozfarbovuvannya grafiv yaki NP skladni dlya dovilnih grafiv mozhna rozv yazati za polinomialnij chas dlya grafiv Mejnelya PrimitkiMeyniel graphs 2019 07 28 u Wayback Machine Information System on Graph Classes and their Inclusions retrieved 2016 09 25 Meyniel 1976 s 339 342 Markosyan Karapetyan 1976 s 292 296 Hoang 1987 s 302 312 Burlet Fonlupt 1984 s 225 252 Hertz 1990 s 231 240 Roussel Rusu 2001 s 107 123 LiteraturaMeyniel H On the perfect graph conjecture 1976 T 16 vip 4 S 339 342 DOI 10 1016 S0012 365X 76 80008 8 S Markosyan I Karapetyan O sovershennyh grafah DAN Arm SSR 1976 T LXIII vip 5 Hoang C T On a conjecture of Meyniel 1987 T 42 vip 3 S 302 312 Series B DOI 10 1016 0095 8956 87 90047 5 Burlet M Fonlupt J Polynomial algorithm to recognize a Meyniel graph Topics on perfect graphs North Holland Amsterdam 1984 T 88 S 225 252 North Holland Math Stud DOI 10 1016 S0304 0208 08 72938 4 Hertz A A fast algorithm for coloring Meyniel graphs 1990 T 50 vip 2 S 231 240 Series B DOI 10 1016 0095 8956 90 90078 E Roussel F Rusu I An O n2 algorithm to color Meyniel graphs 2001 T 235 vip 1 3 S 107 123 DOI 10 1016 S0012 365X 00 00264 8

Дата публікації:
Топ