Rendszeroptimalizálás, 30. tétel

A VIK Wikiből
A lap korábbi változatát látod, amilyen (vitalap) 2012. október 22., 10:44-kor történt szerkesztése után volt. (Ú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…”)
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)
Ugrás a navigációhoz Ugrás a kereséshez

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*:
  • 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'⊆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)∨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.

-- Peti - 2007.01.03.