Nyíri Gábor, 2015. május 25., 12:34-n

2015-05-25T12:34:24Z

← Régebbi változat		A lap 2015. május 25., 14:34-kori változata
12. sor:		12. sor:
	Először egy speciális esetet bizonyítunk be, melyben minden netnek pontosan egy északi és egy déli terminálja van. A huzalozás során a következő sorrendben kötjük be a neteket:		Először egy speciális esetet bizonyítunk be, melyben minden netnek pontosan egy északi és egy déli terminálja van. A huzalozás során a következő sorrendben kötjük be a neteket:

	1 ÉK-DNy típusú netek (/ alak): déli terminálok x koordinátája szerinti növekvő sorrendben, így nem metszik egymást		* ÉK-DNy típusú netek (/ alak): déli terminálok x koordinátája szerinti növekvő sorrendben, így nem metszik egymást
	1 egyenes bekötések (\| alak): sorrent érdektelen, nem metszhetik egymást		* egyenes bekötések (\| alak): sorrent érdektelen, nem metszhetik egymást
	1 ÉNy-DK típusú netek (\ alak): északi terminálok x koordinátája szerinti növekvő sorrendben		* ÉNy-DK típusú netek (\ alak): északi terminálok x koordinátája szerinti növekvő sorrendben

	Végül az általános esetet visszavezetjük a speciálisra oly módon, hogy amennyiben valamelyik oldal (északi, déli, vagy mindkettő) nem felel meg a fenti speciális esetnek, a megfelelő terminálokat a [[RopiTetel23\|23. tételben]] említett Gallai-féle algoritmussal egysoros huzalozásként kezelve összekötjük, majd netenként "kivezetünk" egy függőleges huzalt, így már alkalmazható a speciális esetre kidolgozott algoritmus.		Végül az általános esetet visszavezetjük a speciálisra oly módon, hogy amennyiben valamelyik oldal (északi, déli, vagy mindkettő) nem felel meg a fenti speciális esetnek, a megfelelő terminálokat a [[RopiTetel23\|23. tételben]] említett Gallai-féle algoritmussal egysoros huzalozásként kezelve összekötjük, majd netenként "kivezetünk" egy függőleges huzalt, így már alkalmazható a speciális esetre kidolgozott algoritmus.

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel24}} ==!! Csatornahuzalozás a kétrétegű, megszorítás nélküli modellben. Switchbox-huzalozás, alsó becslés a rétegek sz…”

2012-10-22T09:44:07Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel24}} ==!! Csatornahuzalozás a kétrétegű, megszorítás nélküli modellben. Switchbox-huzalozás, alsó becslés a rétegek sz…”

Új lap

{{GlobalTemplate|Infoszak|RopiTetel24}}

==!! Csatornahuzalozás a kétrétegű, megszorítás nélküli modellben. Switchbox-huzalozás, alsó becslés a rétegek számára, felső becslés (biz. nélkül).==

__TOC__

===Csatornahuzalozás a kétrétegű, megszorítás nélküli modellben===

Csatornahuzalozásnak az olyan feladatokat nevezzük, ahol a terminálok a lap két szemközti szélén helyezkednek el. Minden ilyen feladat megoldható kétrétegű áramköri lapon, megszorítás nélküli modellben alkalmas (nem feltétlenül optimális) szélességben, ilyen megoldást lineáris időben találhatunk.

Először egy speciális esetet bizonyítunk be, melyben minden netnek pontosan egy északi és egy déli terminálja van. A huzalozás során a következő sorrendben kötjük be a neteket:

1 ÉK-DNy típusú netek (/ alak): déli terminálok x koordinátája szerinti növekvő sorrendben, így nem metszik egymást
1 egyenes bekötések (| alak): sorrent érdektelen, nem metszhetik egymást
1 ÉNy-DK típusú netek (\ alak): északi terminálok x koordinátája szerinti növekvő sorrendben

Végül az általános esetet visszavezetjük a speciálisra oly módon, hogy amennyiben valamelyik oldal (északi, déli, vagy mindkettő) nem felel meg a fenti speciális esetnek, a megfelelő terminálokat a [[RopiTetel23|23. tételben]] említett Gallai-féle algoritmussal egysoros huzalozásként kezelve összekötjük, majd netenként "kivezetünk" egy függőleges huzalt, így már alkalmazható a speciális esetre kidolgozott algoritmus.

===Switchbox-huzalozás, alsó becslés a rétegek számára, felső becslés===

Switchbox-huzalozásnak az olyan feladatokat nevezzük, ahol a terminálok a lap mind a négy oldalán elhelyezkedhetnek. Erre az esetre Hambrusch tétele kimondja, hogy tetszőleges k számhoz található olyan feladat, amely nem oldható meg k rétegen még a megszorítás nélküli modellben sem.

TODO: bizonyítás

====Alső és felső becslés a rétegek számára====

<math>\lceil m \rceil + 1 \leq k \leq 2\lceil m \rceil + 4</math>
ahol m = max(n / w, w / n), n és w pedig a lap magassága ill. szélessége

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

[[Category:Infoszak]]

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

Nyíri Gábor, 2015. május 25., 12:34-n

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel24}} ==!! Csatornahuzalozás a kétrétegű, megszorítás nélküli modellben. Switchbox-huzalozás, alsó becslés a rétegek sz…”