Ребе́рне покриття́ графа — це множина ребер C, така, що кожна вершина графа інцидентна принаймні одному ребру з C.
На малюнку показано реберне покриття двох графів.
Найме́нше ребе́рне покриття́ — це реберне покриття найменшого розміру. Число ребер у найменшому реберному покритті графа називають число́м ребе́рного покриття́ і позначають (в книзі Свамі, Тхулалірамана — ). На малюнку показано приклади найменших реберних покриттів.
Зауважимо, що покриття правого графа є не тільки реберним покриттям, але й паруванням. Більш того, це парування є досконалим паруванням — у ньому кожна вершина відповідає рівно одному ребру парування. Досконале парування (якщо існує) завжди є найменшим реберним покриттям.
Задача пошуку найменшого реберного покриття є задачею оптимізації, яка належить до класу [en] і може бути розв'язана за поліноміальний час.
Приклад
- Якщо в графі немає ізольованих вершин (тобто вершин степеня 0), то множина всіх ребер є реберним покриттям (але не обов'язково найменшим!). Якщо ізольовані вершини є, реберного покриття в цьому графі не існує.
- Повний двочастковий граф Km,n має число реберного покриття max(m, n).
Властивості
- Згідно з другою тотожністю Галлаї, в графі без ізольованих вершин загальне число ребер у найменшому реберному покритті і найбільшому паруванні дорівнює числу вершин графа.
Алгоритм
Найменше реберне покриття можна знайти за поліноміальний час, знайшовши найбільше парування і додавши за допомогою жадібного алгоритму ребра для покриття решти вершин. На малюнку найбільше парування показано червоним кольором. Додаткові ребра, додані для покриття непокритих вершин, показано синім кольором (у графі праворуч найбільше парування є досконалим паруванням, у якому всі вершини вже покриті, так що немає потреби в додаткових ребрах.)
Див. також
- (Задача про вершинне покриття)
- Задача про покриття множини — задача про реберне покриття є окремим випадком задачі про покриття множини е лементами генеральної сукупності є вершини, а кожна підмножина покриває рівно два елементи.
Примітки
- Гарей і Джонсон (Garey, Johnson, 1979), стор. 79, використовують реберне покриття і вершинне покриття як приклад пари подібних задач, одну з яких можна розв'язати за поліноміальний час, а інша — NP-складна. Див. також стор. 190.
- Lawler, 2001, с. 222–223.
Література
- Weisstein, Eric W. Edge Cover(англ.) на сайті Wolfram MathWorld.
- Michael R. Garey, David S. Johnson. . — W.H. Freeman, 1979. — .
- Eugene L. Lawler. [1] — Dover Publications, 2001. — . з джерела 28 червня 2014
- М. Свами, К. Тхуласираман. 9.2 Рёберные покрытия // Графы, сети и алгоритмы. — М. : Мир, 1984. — С. 179—180.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Rebe rne pokrittya grafa ce mnozhina reber C taka sho kozhna vershina grafa incidentna prinajmni odnomu rebru z C Na malyunku pokazano reberne pokrittya dvoh grafiv Najme nshe rebe rne pokrittya ce reberne pokrittya najmenshogo rozmiru Chislo reber u najmenshomu rebernomu pokritti grafa nazivayut chislo m rebe rnogo pokrittya i poznachayut r G displaystyle rho G v knizi Svami Thulaliramana b1 G displaystyle beta 1 G Na malyunku pokazano prikladi najmenshih rebernih pokrittiv Zauvazhimo sho pokrittya pravogo grafa ye ne tilki rebernim pokrittyam ale j paruvannyam Bilsh togo ce paruvannya ye doskonalim paruvannyam u nomu kozhna vershina vidpovidaye rivno odnomu rebru paruvannya Doskonale paruvannya yaksho isnuye zavzhdi ye najmenshim rebernim pokrittyam Zadacha poshuku najmenshogo rebernogo pokrittya ye zadacheyu optimizaciyi yaka nalezhit do klasu en i mozhe buti rozv yazana za polinomialnij chas Priklad Yaksho v grafi nemaye izolovanih vershin tobto vershin stepenya 0 to mnozhina vsih reber ye rebernim pokrittyam ale ne obov yazkovo najmenshim Yaksho izolovani vershini ye rebernogo pokrittya v comu grafi ne isnuye Povnij dvochastkovij graf Km n maye chislo rebernogo pokrittya max m n VlastivostiZgidno z drugoyu totozhnistyu Gallayi v grafi bez izolovanih vershin zagalne chislo reber u najmenshomu rebernomu pokritti i najbilshomu paruvanni dorivnyuye chislu vershin grafa AlgoritmNajmenshe reberne pokrittya mozhna znajti za polinomialnij chas znajshovshi najbilshe paruvannya i dodavshi za dopomogoyu zhadibnogo algoritmu rebra dlya pokrittya reshti vershin Na malyunku najbilshe paruvannya pokazano chervonim kolorom Dodatkovi rebra dodani dlya pokrittya nepokritih vershin pokazano sinim kolorom u grafi pravoruch najbilshe paruvannya ye doskonalim paruvannyam u yakomu vsi vershini vzhe pokriti tak sho nemaye potrebi v dodatkovih rebrah Div takozhZadacha pro vershinne pokrittya Zadacha pro pokrittya mnozhini zadacha pro reberne pokrittya ye okremim vipadkom zadachi pro pokrittya mnozhini e lementami generalnoyi sukupnosti ye vershini a kozhna pidmnozhina pokrivaye rivno dva elementi PrimitkiGarej i Dzhonson Garey Johnson 1979 stor 79 vikoristovuyut reberne pokrittya i vershinne pokrittya yak priklad pari podibnih zadach odnu z yakih mozhna rozv yazati za polinomialnij chas a insha NP skladna Div takozh stor 190 Lawler 2001 s 222 223 LiteraturaWeisstein Eric W Edge Cover angl na sajti Wolfram MathWorld Michael R Garey David S Johnson W H Freeman 1979 ISBN 0 7167 1045 5 Eugene L Lawler 1 Dover Publications 2001 ISBN 978 0 486 41453 9 z dzherela 28 chervnya 2014 M Svami K Thulasiraman 9 2 Ryobernye pokrytiya Grafy seti i algoritmy M Mir 1984 S 179 180