Tarokkk: /* Éldiszjunkt huzalozás */

2014-01-20T14:54:28Z

Éldiszjunkt huzalozás

← Régebbi változat		A lap 2014. január 20., 16:54-kori változata
14. sor:		14. sor:
	\|		\|
	/`		/`
	--/ /--		---/ /---
	./		./
	\|		\|

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel25}} ==!! Éldiszjunkt huzalozás, réteg-hozzárendelés, Frank tétele (csak a szükségesség bizonyításával).== TOC ==…”

2012-10-22T09:44:09Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel25}} ==!! Éldiszjunkt huzalozás, réteg-hozzárendelés, Frank tétele (csak a szükségesség bizonyításával).== __TOC__ ==…”

Új lap

{{GlobalTemplate|Infoszak|RopiTetel25}}

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

__TOC__

===É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).

<pre>
|
|
/`
--/ /--
./
|
|
</pre>

===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.

-- [[VeresSzentkiralyiAndras|dnet]] - 2010.05.24.

[[Category:Infoszak]]

Rendszeroptimalizálás, 25. tétel - Laptörténet

Tarokkk: /* Éldiszjunkt huzalozás */

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel25}} ==!! Éldiszjunkt huzalozás, réteg-hozzárendelés, Frank tétele (csak a szükségesség bizonyításával).== __TOC__ ==…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel25}} ==!! Éldiszjunkt huzalozás, réteg-hozzárendelés, Frank tétele (csak a szükségesség bizonyításával).== TOC ==…”