Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel30}} ==!! Minimális generikusan merev rúdszerkezetek, Laman (biz. nélkül), Lovász és Yemini tételei.== TOC ===Minimál…”

2012-10-22T09:44:23Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel30}} ==!! Minimális generikusan merev rúdszerkezetek, Laman (biz. nélkül), Lovász és Yemini tételei.== __TOC__ ===Minimál…”

Új lap

{{GlobalTemplate|Infoszak|RopiTetel30}}

==!! Minimális generikusan merev rúdszerkezetek, Laman (biz. nélkül), Lovász és Yemini tételei.==

__TOC__

===Minimális és generikus merevség===

*Def.*: egy rúdszerzetet gráfja generikusan merev, ha létezik merev megvalósítása. 
*Def.*: egy rúdszerkezet minimálisan merev, ha generikusan merev és bármely élét elhagyva megszűnik merevnek lenni.

===Merevségi problémák és bonyolultságuk===

*Problémák*:
* Pk: G gráf k dimenziós térben generikusan merev-e?
* Pk': G gráf k dimenziós térben minimálisan merev-e?

*Tétel*: ha egy rúdszerkezet gráfja generikusan merev, minden olyan megvalósítása, ahol a csuklók koordinátái algebrailag függetlenek, merev. Az algebrai függetlenség azt jelenti, a számhalmaznak nincs 0 értékű többváltozós, egész együtthatós polinomja. 
*Megj.*: Egy véletlen beágyazás 1 valószínűséggel lesz merev. 
*Schwarz-lemma*: Pk feladatra létezik kis nevezőjű tanú beágyazás, azaz Pk∈NP 

*Tétel (Maxwell, 1960s)*: a minimális merevség szükséges feltétele 2 dimenzióban, hogy e=2p-3 és ∀G'&sube;G feszített részgráfra e'≤2p'-3, azaz ne legyen túlbiztosított részgráf. 
*Tétel (Laman, 1970s eleje)*: a feltételek elégségesek is, azaz P2'∈coNP. 
*Tétel (Lovász, Yemini, 1970s vége)*: G akkor minimálisan merev 2 dimenzióban, ha bármely élének megduplázásával lefedhető két diszjunkt feszítőfával. Matroidokra átfogalmazva: M(G+e)&or;M(G+e)?=U2p-2,2p-2. A 2D minimális merevség kérdését visszavezettük a matroid partíciós problémára, amire ismerünk polinom rendű algoritmust.

*Megj.*: 3 dimenziós térben nem elégséges feltétel az e'≤3p'-6. Ellenpélda a &bdquo;double banana gráf” (ld. a [http://www.libri.hu/hu/images/libri_cover/23960?type=4 Rendszeroptimalizálás könyv borítóján]). A P3' problémáról nem ismert, hogy P-beli-e.

-- [[PallosPeter|Peti]] - 2007.01.03.

[[Category:Infoszak]]

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

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel30}} ==!! Minimális generikusan merev rúdszerkezetek, Laman (biz. nélkül), Lovász és Yemini tételei.== __TOC__ ===Minimál…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel30}} ==!! Minimális generikusan merev rúdszerkezetek, Laman (biz. nélkül), Lovász és Yemini tételei.== TOC ===Minimál…”