Rendszeroptimalizálás, 25. tétel

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

!! Éldiszjunkt huzalozás, réteg-hozzárendelés, Frank tétele (csak a szükségesség bizonyításával).

Éldiszjunkt huzalozás

Éldiszjunkt huzalozásnak az olyan feladatokat nevezzük, ahol a huzaloknak csak az éldiszjunktságát követelhetjük meg, a csúcsdiszjunktságot nem: két huzal "kikerülheti" egymást X-láb (knock-knee) alakban (lásd alább).

	 |
	 |
	/`
--/	/--
	 ./
	 |
	 |

Réteg-hozzárendelés

A réteg-hozzárendelés egy olyan feladat, melynek bemenete egy éldiszjunkt huzalozás és egy k rétegszám, kimenete pedig egy transzformáció, mely a bemenetet k rétegű csúcsdiszjunkt huzalozássá alakítja át. Speciális esetek a következők:

• k = 2 esete polinom időben megoldható, viszont a válasz általában nem
• k = 3 esete NP-teljes (Lipski)
• k = 4 esete mindig megoldható polinom időben (Brady, Brown)

Frank tétele (csak a szükségesség bizonyításával)

Szoros egyenesnek nevezzük az olyan, a lapot kettévágó e egyeneseket, amelyeknél t(e) = n (vízszintes e esetén) ill. t(e) = w (függőleges e esetén).

Páratlan halmaznak nevezzük azokat a halmazokat, amelyek esetében az olyan rácsélek száma, amelyeknek kilépnek a halmazből (egyik végpontja a halmazon belül, a másik kívül) ill. a halmaz által kettővágótt netek (egyik terminálja a halmazon belül, a másik kívül) számának összege páratlan.

Egy lapot kettévágó e egyenes módosított terhelésének nevezzük a t'(e) = t(e) + p(e) összeget, ahol p(e) az e egyenes paritásterhelése, amely azt mutatja meg, hogy a lap e-től balra eső (e feletti), szoros egyenesek által v + 1 (f + 1) részre osztott felében hány halmaz páratlan.

Frank tétele kimondja, hogy ha egy éldiszjunkt huzalozási problémában minden netnek két terminálja van, a feladat akkor és csak akkor megoldható, ha minden, a lapot kettévágó függőleges e egyenesre t'(e) ≤ w és minden vízszintes e-re T'(e) ≤ h teljesül.

Szükségesség bizonyítása

Veszünk egy függőleges e egyenest, ekkor ettől balra p(e) darab, egymástól piros egyenesekkel elválasztható páratlan halmaz található. Ezek mindegyikéből kilép egy olyan él, amit a huzalozás nem használ. Mivel a piros egyenesek szorosak, rajtuk minden átkelő él használt, így az említett egy-egy élek csak vízszintesek lehetnek, így e-n átlép t(e) felhasznált él (ez a terhelése) valamint p(e) fel nem használt él (páratlan halmazonként egy). Ezek összege pont a módosított terhelés értéke, t'(e), így a lap magasságának legalább ennyinek kell lennie, tehát t'(e) ≤ w szükséges feltétel teljesül.

-- dnet - 2010.05.24.