Rendszeroptimalizálás, 30. tétel

A VIK Wikiből
A lap korábbi változatát látod, amilyen Unknown user (vitalap) 2012. október 22., 11: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)

Ez az oldal a korábbi SCH wikiről lett áthozva.

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.