Bordás bevonat

A gráf élborítója a C élek halmaza úgy, hogy a gráf minden csúcsa legalább egy C élére esik .

A következő ábra két grafikon élfedését mutatja.

A legkisebb élfedés a legkisebb élfedés. A gráf legkisebb élborítójában lévő élek számát élborító számnak nevezzük, és a (Swami könyvében Thulaliramana - ) jelöléssel. A következő ábra a legkisebb élborításokra mutat példákat.

Ne feledje, hogy a jobb oldali gráf borítója nem csak egy élborító, hanem egy megfelelő . Sőt, ez az illesztés tökéletes egyezés – minden csúcspontja pontosan az illesztés egyik élére esik. A tökéletes illeszkedés (ha létezik) mindig a legkisebb élborítás.

A legkisebb éllefedettség megtalálása egy optimalizálási feladat , a fedési feladatok osztályába tartozik, és polinomiális időben megoldható .

Példák

• Ha a gráfban nincsenek izolált csúcsok (azaz 0 fokú csúcsok), akkor az összes él halmaza élborító (de nem feltétlenül a legkisebb!). Ha vannak izolált csúcsok, akkor ebben a gráfban nincs élfedés.
• A teljes kétrészes gráf K m , n élborítószáma max( m , n ).

Tulajdonságok

• A második Gallai-azonosság szerint egy izolált csúcsok nélküli gráfban a legkisebb élfedés és a legnagyobb illeszkedés összes éleinek száma megegyezik a gráf csúcsainak számával.

Algoritmusok

A legkisebb éllefedettséget polinomidőben úgy találhatjuk meg , hogy megtaláljuk a legnagyobb illeszkedést , majd egy mohó algoritmus segítségével éleket adunk hozzá a fennmaradó csúcsok lefedéséhez [1] [2] . A következő ábrán a legnagyobb egyezés piros színnel látható. A fedetlen csúcsok lefedésére hozzáadott további élek kék színnel jelennek meg (a jobb oldali grafikonon a legnagyobb illesztés a tökéletes illeszkedés , amelyben már minden csúcs le van fedve, így nincs szükség további élekre.)

Lásd még

• Csúcsborítási probléma
• A halmazlefedési probléma - az élfedési probléma a halmazlefedési probléma speciális esete - a sokaság elemei csúcsok, és mindegyik részhalmaz pontosan két elemet takar.

Jegyzetek

1. ↑ Garey és Johnson ( Garey, Johnson 1979 ), 79. o., az élborítást és a csúcsfedést használja példaként egy pár hasonló feladatra, amelyek közül az egyik megoldható polinomiális időben, a másik pedig NP-nehéz. Lásd még a 190. oldalon.
2. ↑ Lawler, 2001 , p. 222–223.

Irodalom

• Weisstein, Eric W. Edge Cover  (angolul) a Wolfram MathWorld webhelyén .
• Michael R. Garey, David S. Johnson. Számítógépek és kezelhetetlenség: Útmutató az NP-teljesség elméletéhez . - W. H. Freeman, 1979. - ISBN 0-7167-1045-5 .
• Eugene L. Lawler. Kombinatorikus optimalizálás: hálózatok és matroidok. - Dover Publications, 2001. - ISBN 978-0-486-41453-9 .
• M. Swami, K. Thulasiraman. 9.2 Élfedések // Grafikonok, hálózatok és algoritmusok. - M . : "Mir", 1984. - S. 179-180.