Вершинне покриття графа — це множина вершин така, що кожне ребро графа (інцидентне) хоча б одній вершині цієї множини. Задача знаходження найменшого вершинного покриття є класичною задачею оптимізації в інформатиці і типовим прикладом NP-складної задачі оптимізації, для якої відомий апроксимаційний алгоритм. Її версія у вигляді проблеми вибору, задача вершинного покриття, була однією з 21 NP-повної задачі Карпа і, отже, класичною NP-повною задачею в теорії складності обчислень.
Задачу найменшого вершинного покриття можна сформулювати як напівцілочисельну задачу лінійного програмування чия є задача найбільшого парування.
Означення
Формально, вершинне покриття неорієнтованого графа це підмножина V′ множини вершин V така, що для кожного ребра (u, v) графа G або u у V′, або v у V′, або обидві вершини. Кажуть, що множина V′ «покриває» ребра G. Наступні зображення показують приклади вершинних покриттів в двох графах (і множина V′ позначена червоним).
Найменше вершинне покриття це покриття з найменшого можливого розміру. Число вершинного покриття це розмір найменшого такого покриття. Наступні зображення показують приклади найменших вершинних покриттів у наведених вище графах.
Приклади
- Множина всіх вершин є вершинним покриттям.
- Вершини з будь-якого найбільшого парування утворюють вершинне покриття.
- Повний двочастковий граф має найменше вершинне покриття розміру .
Властивості
- Множина вершин є вершинним покриттям тоді і тільки тоді, якщо його доповнення є незалежною множиною.
- Тому, кількість вершин у графі дорівнює кількості вершин у його найменшому вершинному покриттю плюс найбільшій незалежній множині.
Обчислювальна задача
Задача найменшого вершинного покриття це задача оптимізації щодо знаходження найменшого вершинного покриття певного графа.
- ПРИМІРНИК: Граф
- ВИХІД: Найменше число таке, що має вершинне покриття розміру .
Якщо задача сформульована як проблема вибору, її називають задача вершинного покриття:
- ПРИМІРНИК: Граф і додатне ціле число .
- ПИТАННЯ: Чи має вершинне покриття розміру не більше
Задача вершинного покриття — це NP-повна задача: вона була серед задач Карпа. В теорії складності обчислень часто використовується як відправна точка для доведення NP-складності.
Формулювання у термінах ЦЛП
Припустимо, що кожна вершина має пов'язану вартість Задачу найменшого зваженого вершинного покриття можна сформулювати як таку цілочисельну програму (ЦЛП).
мінімізувати (мінімізувати підсумкову вартість) за умов для всіх (покрити кожне ребро графа) для всіх . (кожна вершина або належить до вершинного покриття, або ні)
ЦЛП належить до загальнішого класу ЦЛП задач покриття.
Апроксимаційний алгоритм
Незважаючи на те, що ми не знаємо як знайти оптимальне/найменше вершинне покриття у графі за поліноміальний час, ми можемо ефективно знайти вершинне покриття, яке буде близьким до оптимального. Наведемо алгоритм, який повертає вершинне покриття гарантовано не більше ніж вдвічі більше за розміром порівняно з оптимальним покриттям.
НАБЛИЖЕНЕ-ВЕРШИННЕ-ПОКРИТТЯ
|
За умов використання списків суміжності час виконання цього алгоритму
Див. також
Примітки
- Vazirani, 2001, с. 122—123
Джерела
- Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. ISBN .
Посилання
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Vershinne pokrittya grafa ce mnozhina vershin taka sho kozhne rebro grafa incidentne hocha b odnij vershini ciyeyi mnozhini Zadacha znahodzhennya najmenshogo vershinnogo pokrittya ye klasichnoyu zadacheyu optimizaciyi v informatici i tipovim prikladom NP skladnoyi zadachi optimizaciyi dlya yakoyi vidomij aproksimacijnij algoritm Yiyi versiya u viglyadi problemi viboru zadacha vershinnogo pokrittya bula odniyeyu z 21 NP povnoyi zadachi Karpa i otzhe klasichnoyu NP povnoyu zadacheyu v teoriyi skladnosti obchislen Zadachu najmenshogo vershinnogo pokrittya mozhna sformulyuvati yak napivcilochiselnu zadachu linijnogo programuvannya chiya ye zadacha najbilshogo paruvannya OznachennyaFormalno vershinne pokrittya neoriyentovanogo grafa G V E displaystyle G V E ce pidmnozhina V mnozhini vershin V taka sho dlya kozhnogo rebra u v grafa G abo u u V abo v u V abo obidvi vershini Kazhut sho mnozhina V pokrivaye rebra G Nastupni zobrazhennya pokazuyut prikladi vershinnih pokrittiv v dvoh grafah i mnozhina V poznachena chervonim Najmenshe vershinne pokrittya ce pokrittya z najmenshogo mozhlivogo rozmiru Chislo vershinnogo pokrittya t displaystyle tau ce rozmir najmenshogo takogo pokrittya Nastupni zobrazhennya pokazuyut prikladi najmenshih vershinnih pokrittiv u navedenih vishe grafah Prikladi Mnozhina vsih vershin ye vershinnim pokrittyam Vershini z bud yakogo najbilshogo paruvannya utvoryuyut vershinne pokrittya Povnij dvochastkovij graf K m n displaystyle K m n maye najmenshe vershinne pokrittya rozmiru t K m n min m n displaystyle tau K m n min m n Vlastivosti Mnozhina vershin ye vershinnim pokrittyam todi i tilki todi yaksho jogo dopovnennya ye nezalezhnoyu mnozhinoyu Tomu kilkist vershin u grafi dorivnyuye kilkosti vershin u jogo najmenshomu vershinnomu pokrittyu plyus najbilshij nezalezhnij mnozhini Obchislyuvalna zadachaZadacha najmenshogo vershinnogo pokrittya ce zadacha optimizaciyi shodo znahodzhennya najmenshogo vershinnogo pokrittya pevnogo grafa PRIMIRNIK Graf G displaystyle G VIHID Najmenshe chislo k displaystyle k take sho G displaystyle G maye vershinne pokrittya rozmiru k displaystyle k Yaksho zadacha sformulovana yak problema viboru yiyi nazivayut zadacha vershinnogo pokrittya PRIMIRNIK Graf G displaystyle G i dodatne cile chislo k displaystyle k PITANNYa Chi maye G displaystyle G vershinne pokrittya rozmiru ne bilshe k displaystyle k Zadacha vershinnogo pokrittya ce NP povna zadacha vona bula sered zadach Karpa V teoriyi skladnosti obchislen chasto vikoristovuyetsya yak vidpravna tochka dlya dovedennya NP skladnosti Formulyuvannya u terminah CLP Pripustimo sho kozhna vershina maye pov yazanu vartist c v 0 displaystyle c v geq 0 Zadachu najmenshogo zvazhenogo vershinnogo pokrittya mozhna sformulyuvati yak taku cilochiselnu programu CLP minimizuvati v V c v x v displaystyle sum v in V c v x v minimizuvati pidsumkovu vartist za umov x u x v 1 displaystyle x u x v geq 1 dlya vsih u v E displaystyle u v in E pokriti kozhne rebro grafa x v 0 1 displaystyle x v in 0 1 dlya vsih v V displaystyle v in V kozhna vershina abo nalezhit do vershinnogo pokrittya abo ni CLP nalezhit do zagalnishogo klasu CLP zadach pokrittya Aproksimacijnij algoritmDokladnishe Aproksimacijnij algoritm Nezvazhayuchi na te sho mi ne znayemo yak znajti optimalne najmenshe vershinne pokrittya u grafi G displaystyle G za polinomialnij chas mi mozhemo efektivno znajti vershinne pokrittya yake bude blizkim do optimalnogo Navedemo algoritm yakij povertaye vershinne pokrittya garantovano ne bilshe nizh vdvichi bilshe za rozmirom porivnyano z optimalnim pokrittyam NABLIZhENE VERShINNE POKRITTYa G displaystyle G C displaystyle C emptyset E G E displaystyle E G E poki E 0 displaystyle E neq 0 nehaj u v displaystyle u v bude dovilnim rebrom z E displaystyle E C C u v displaystyle C C cup u v vidaliti z E displaystyle E kozhne rebro incidentne do u displaystyle u chi v displaystyle v povernuti C displaystyle C Za umov vikoristannya spiskiv sumizhnosti chas vikonannya cogo algoritmu O V E displaystyle O V E Div takozhZadacha pro pokrittya mnozhini Reberne pokrittyaPrimitkiVazirani 2001 s 122 123DzherelaVazirani Vijay V 2001 Approximation Algorithms Springer Verlag ISBN 3 540 65367 8 PosilannyaWeisstein Eric W Vershinne pokrittya angl na sajti Wolfram MathWorld Weisstein Eric W Najmenshe vershinne pokrittya angl na sajti Wolfram MathWorld Weisstein Eric W Chislo vershinnogo pokrittya angl na sajti Wolfram MathWorld