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

Покриття верши н ци клами або просто покриття ци клами графа G це набір циклів які є підграфами графа G і містять усі ве

Покриття вершин циклами

Покриття вершин циклами

Покриття́ верши́н ци́клами (або просто покриття́ ци́клами) графа G — це набір циклів, які є підграфами графа G і містять усі вершини G.

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

Якщо цикли покриття не мають спільних ребер, покриття називають реберно неперетинним або просто покриттям циклами, що не перетинаються.

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

Властивості та застосування

Перманент

Перманент (0,1)-матриці дорівнює числу покриттів вершинно неперетинними циклами орієнтованого графа з цією матрицею суміжності. Цей факт використовують у спрощеному доведенні того, що обчислення перманента [en].

Покриття циклами, що не перетинаються

Задачі пошуку вершинно неперетинних і реберно неперетинних покриттів циклами з найменшим числом циклів є NP-повними. Задачі не належать до класу складності APX. Варіанти для орграфів також належать до APX.

Див. також

Примітки

  1. David Eppstein. Partition a graph into node-disjoint cycles.
  2. Tutte W. T. A short proof of the factor theorem for finite graphs // . — 1954. — Т. 6. — С. 347–352. — DOI:10.4153/CJM-1954-033-3..
  3. http://www.cs.cmu.edu/~avrim/451f13/recitation/rec1016.txt [ 2018-04-27 у Wayback Machine.] (problem 1)
  4. Garey M. R., Johnson D. S. Computers and intractability. — New York : W.H. Freeman and Company, 1979. — .
  5. Amir Ben-Dor, Shai Halevi. Zero-one permanent is #P-complete, a simpler proof // Proceedings of the 2nd Israel Symposium on the Theory and Computing Systems. — 1993. — С. 108-117.
  6. G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. — 1999. — С. 378, 379. — ., у книзі цитується Sartaj Sahni, Teofilo F. Gonzalez. P-complete approximation problems // . — 1976. — Т. 23, вип. 3. — С. 555–565. — DOI:10.1145/321958.321975.

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

Pokrittya vershi n ci klami abo prosto pokrittya ci klami grafa G ce nabir cikliv yaki ye pidgrafami grafa G i mistyat usi vershini G Yaksho pokrivalni cikli ne mayut spilnih vershin pokrittya nazivayut vershinno neperetinnim abo inodi prosto pokrittyam ciklami sho ne peretinayutsya U comu vipadku nabir cikliv utvoryuye kistyakovij pidgraf grafa G Pokrittya ciklami sho ne peretinayutsya neoriyentovanogo grafa yaksho take isnuye mozhna znajti za polinomialnij chas peretvorivshi zadachu v zadachu poshuku doskonalogo paruvannya v bilshomu grafi Yaksho cikli pokrittya ne mayut spilnih reber pokrittya nazivayut reberno neperetinnim abo prosto pokrittyam ciklami sho ne peretinayutsya Analogichni viznachennya v terminah oriyentovanih cikliv isnuyut dlya orgrafiv Poshuk pokrittya ciklami oriyentovanogo grafa sho vershinno ne peretinayutsya mozhna zdijsniti za polinomialnij chas shlyahom analogichnogo zvedennya do doskonalogo paruvannya Prote dodannya umovi sho kozhen cikl povinen mati dovzhinu prinajmni 3 robit zadachu NP skladnoyu Vlastivosti ta zastosuvannyaPermanent Permanent 0 1 matrici dorivnyuye chislu pokrittiv vershinno neperetinnimi ciklami oriyentovanogo grafa z ciyeyu matriceyu sumizhnosti Cej fakt vikoristovuyut u sproshenomu dovedenni togo sho obchislennya permanenta en Pokrittya ciklami sho ne peretinayutsya Zadachi poshuku vershinno neperetinnih i reberno neperetinnih pokrittiv ciklami z najmenshim chislom cikliv ye NP povnimi Zadachi ne nalezhat do klasu skladnosti APX Varianti dlya orgrafiv takozh nalezhat do APX Div takozhPokrittya reber ciklamiPrimitkiDavid Eppstein Partition a graph into node disjoint cycles Tutte W T A short proof of the factor theorem for finite graphs 1954 T 6 S 347 352 DOI 10 4153 CJM 1954 033 3 http www cs cmu edu avrim 451f13 recitation rec1016 txt 2018 04 27 u Wayback Machine problem 1 Garey M R Johnson D S Computers and intractability New York W H Freeman and Company 1979 ISBN 0 7167 1044 7 Amir Ben Dor Shai Halevi Zero one permanent is P complete a simpler proof Proceedings of the 2nd Israel Symposium on the Theory and Computing Systems 1993 S 108 117 G Ausiello P Crescenzi G Gambosi V Kann A Marchetti Spaccamela M Protasi Complexity and Approximation Combinatorial Optimization Problems and Their Approximability Properties 1999 S 378 379 ISBN 3 540 65431 3 u knizi cituyetsya Sartaj Sahni Teofilo F Gonzalez P complete approximation problems 1976 T 23 vip 3 S 555 565 DOI 10 1145 321958 321975

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