Rendszeroptimalizálás, 30. 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

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

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*:
• P_k: G gráf k dimenziós térben generikusan merev-e?
• P_k': 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*: P_k feladatra létezik kis nevezőjű tanú beágyazás, azaz P_k∈NP
  

• Tétel (Maxwell, 1960s)*: a minimális merevség szükséges feltétele 2 dimenzióban, hogy e=2p-3 és ∀G'⊆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 P₂'∈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)∨M(G+e)?=U_2p-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 „double banana gráf” (ld. a Rendszeroptimalizálás könyv borítóján). A P₃' problémáról nem ismert, hogy P-beli-e.

-- Peti - 2007.01.03.