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 і більше) має принаймні дві хорди. У графі парності будь-який довгий цикл можна розбити на два шляхи різної парності, жоден з яких не є окремим ребром і необхідна принаймні одна хорда, щоб ці шляхи були породженими шляхами. Тоді після розбиття циклу на два шляхи між кінцевими точками першої хорди необхідна друга хорда, щоб другий шлях не був породженим. Оскільки графи Мейнеля є досконалими графами, графи парності також досконалі. Це точно графи, прямий добуток яких з окремим ребром залишається досконалим графом.

Алгоритми

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

Примітки

  1. Parity graphs [ 2019-07-28 у Wayback Machine.], Information System on Graph Classes and their Inclusions, retrieved 2016-09-25.
  2. Burlet, Uhry, 1984, с. 253–277.
  3. Jansen, 1998, с. 249–260.
  4. Cicerone, Di Stefano, 1997, с. 354–363.

Література

  • Burlet M., Uhry J.-P. Parity graphs // Topics on perfect graphs. — Amsterdam : North-Holland, 1984. — Т. 88. — (North-Holland Math. Stud.) — DOI:10.1016/S0304-0208(08)72939-6.
  • Klaus Jansen. A new characterization for parity graphs and a coloring problem with costs // LATIN'98: theoretical informatics (Campinas, 1998). — Springer, Berlin, 1998. — Т. 1380. — (Lecture Notes in Comput. Sci.) — DOI:10.1007/BFb0054326.
  • Serafino Cicerone, Gabriele Di Stefano. On the equivalence in complexity among basic problems on bipartite and parity graphs // Algorithms and computation (Singapore, 1997). — Springer, Berlin, 1997. — Т. 1350. — (Lecture Notes in Comput. Sci.) — DOI:10.1007/3-540-63890-3_38.

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

Graf parnosti ce graf u yakomu bud yaki dva porodzheni shlyahi mizh dvoma vershinami mayut odnakovu parnist abo obidva mayut neparni dovzhini abo obidva parni Cej klas grafiv pershim pochali vivchati i dali jomu nazvu Barlet ta Uri Graf parnosti unikalnij najmenshij kubichnij sirnikovij graf yakij ne ye ni distancijno uspadkovuvanim ni dvochastkovimPov yazani klasi grafivGrafi parnosti vklyuchayut distancijno uspadkovuvani grafi v yakih bud yaki dva porodzheni shlyahi mizh dvoma vershinami mayut odnakovi dovzhini Do nih nalezhat takozh dvochastkovi grafi yaki mozhna opisati analogichno yak grafi v yakih bud yaki dva shlyahi ne obov yazkovo porodzheni mizh dvoma vershinami mayut odnakovu parnist i reberno doskonali grafi sho uzagalnyuyut dvochastkovi grafi Bud yakij graf parnosti ye grafom Mejnelya tobto grafom u yakomu bud yakij cikl neparnoyi dovzhini dovzhinoyu 5 i bilshe maye prinajmni dvi hordi U grafi parnosti bud yakij dovgij cikl mozhna rozbiti na dva shlyahi riznoyi parnosti zhoden z yakih ne ye okremim rebrom i neobhidna prinajmni odna horda shob ci shlyahi buli porodzhenimi shlyahami Todi pislya rozbittya ciklu na dva shlyahi mizh kincevimi tochkami pershoyi hordi neobhidna druga horda shob drugij shlyah ne buv porodzhenim Oskilki grafi Mejnelya ye doskonalimi grafami grafi parnosti takozh doskonali Ce tochno grafi pryamij dobutok yakih z okremim rebrom zalishayetsya doskonalim grafom AlgoritmiGraf ye grafom parnosti todi j lishe todi koli bud yaka komponenta jogo en ye abo povnim grafom abo dvochastkovim grafom Gruntuyuchis na comu opisi pereviriti chi ye graf grafom parnosti mozhna za linijnij chas Toj samij opis privodit do uzagalnennya deyakih algoritmiv optimizaciyi na grafah iz dvochastkovih grafiv na grafi parnosti Napriklad vikoristovuyuchi rozsheplennya grafa zvazhenu najbilshu nezalezhnu mnozhinu grafa parnosti mozhna znajti za polinomialnij chas PrimitkiParity graphs 2019 07 28 u Wayback Machine Information System on Graph Classes and their Inclusions retrieved 2016 09 25 Burlet Uhry 1984 s 253 277 Jansen 1998 s 249 260 Cicerone Di Stefano 1997 s 354 363 LiteraturaBurlet M Uhry J P Parity graphs Topics on perfect graphs Amsterdam North Holland 1984 T 88 North Holland Math Stud DOI 10 1016 S0304 0208 08 72939 6 Klaus Jansen A new characterization for parity graphs and a coloring problem with costs LATIN 98 theoretical informatics Campinas 1998 Springer Berlin 1998 T 1380 Lecture Notes in Comput Sci DOI 10 1007 BFb0054326 Serafino Cicerone Gabriele Di Stefano On the equivalence in complexity among basic problems on bipartite and parity graphs Algorithms and computation Singapore 1997 Springer Berlin 1997 T 1350 Lecture Notes in Comput Sci DOI 10 1007 3 540 63890 3 38

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