Kis-Benedek Ágnes Szimmetrikus és periodikus szerkezetek merevsége

¨ tvo ¨ s Lora ´ nd Tudoma ´ nyegyetem Eo ´szettudoma ´ nyi Kar Terme

´ Kis-Benedek Agnes Szimmetrikus ´ es periodikus szerkezetek merevs´ ege Alkalmazott matematikus MSc Oper´aci´okutat´as szakir´any Szakdolgozat

T´emavezet˝o: Jord´an Tibor, tansz´ekvezet˝o egyetemi tan´ar Oper´aci´okutat´asi Tansz´ek

Budapest, 2012

Tartalomjegyz´ek Bevezet˝ o

1

´ 1. Altal´ anos gr´ afmerevs´ egi bevezet˝ o

3

1.1. Alapfogalmak . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2. Gr´afmerevs´eg jellemz´ese d = 2 eset´en . . . . . . . . . . . . . . .

6

2. Henneberg-t´ıpus´ u m˝ uveletek

9

2.1. Szimmetrikus szerkezetek - bevezet˝o . . . . . . . . . . . . . . . .

9

2.2. C3 a s´ıkban . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.1. M˝ uveletek . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2.2. S´ıkbeli szerkezetek alapt´eteleinek anal´ogi´aja . . . . . . . 13 3. Fix r´ acs´ u´ es ”cone” (k´ upos) szerkezetek

22

3.1. A generikus merevs´eghez sz¨ uks´eges kombinatorikus modell . . . 22 3.2. Merevs´egi t´etelek . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3. Algoritmusok . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.3.1. Algoritmus annak eld¨ont´es´ere, hogy ρ(G) trivi´alis-e . . . 30 3.3.2. Ross-gr´af merev komponenseinek meghat´aroz´asa . . . . 31 3.3.3. cone-Laman gr´af merev komponenseinek meghat´aroz´asa

32

Γ = Z/3Z speci´alis eset . . . . . . . . . . . . . . . . . . . 32 Γ = Z/kZ a´ltal´anos eset . . . . . . . . . . . . . . . . . . 33 4. Matroidelm´ eleti megk¨ ozel´ıt´ es

35

4.1. H´anyadosgr´af . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

ii

´ TARTALOMJEGYZEK

iii

4.2. d-periodikus gr´af - merevs´egi bevezet˝o . . . . . . . . . . . . . . 36 4.3. Matroidok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.3.1. Matroidelm´eleti bevezet˝o . . . . . . . . . . . . . . . . . . 38 4.3.2. Matroidok ´es merevs´eg . . . . . . . . . . . . . . . . . . . 39 5. Friss eredm´ enyek

43

5.1. T¨ uk¨orszimmetria . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2. T¨ uk¨orszimmetria ´es Di´eder-csoport . . . . . . . . . . . . . . . . 44 Irodalomjegyz´ ek

45

K¨osz¨onetnyilv´an´ıt´as Ez´ uton szeretn´em megk¨osz¨onni a t´emavezet˝omnek, Jord´an Tibornak az u ´tmutat´asokat ´es hasznos tan´acsokat, valamint hogy seg´ıtett k¨ozelebbr˝ol megismerkedni ezzel a szerte´agaz´o, ´erdekes t´emak¨orrel, ´es rendelkez´esemre bocs´atotta a legfrissebb eredm´enyeket.

iv

Bevezet˝o A szerkezetek merevs´eg´enek vizsg´alata sz´amos k¨ ul¨onb¨oz˝o alkalmaz´asi ter¨ uleten felmer¨ ul˝o probl´ema. Jelen szakdolgozat a periodikus ´es szimmetrikus szerkezetek merevs´eg´et t´argyalja, amelyet szint´en t¨obb val´os ´eletbeli probl´ema motiv´al, u ´gy mint a feh´erj´ek, krist´alyszerkezetek ´es zeolitok vizsg´alata. A feh´erj´ek szerkezet´enek vizsg´alata term´eszetesen nagy jelent˝os´eggel b´ır biok´emiai szempontb´ol.

A feh´erjeszerkezetek reprezent´alhat´ok mechanikus

szerkezetk´ent, k¨ ul¨onb¨oz˝o korl´att´ıpusokat haszn´alva a kovalens k¨ot´es, hidrog´en k¨ot´es, s´ohidak ´es torzi´os sz¨ogek modellez´es´ehez.

A k¨ot´esek ´altal alkotott

h´al´ozat elemz´es´ere, a flexibilis ´es merev r´eszek meghat´aroz´as´ara gr´afelm´eleti technik´akat alkalmaznak. Az algoritmusnak meg kell sz´amolnia a szabads´agi fokokat ebben a h´al´ozatban, ´es azonos´ıtania kell a merev ´es rugalmas r´eszstrukt´ ur´akat a feh´erj´eben, bele´ertve a t´ ulkorl´atozott r´egi´okat, melyekben t¨obb k¨ot´es van, mint az a merevs´eg el´er´es´ehez sz¨ uks´eges, valamint az alulhat´arozott r´egi´okat, melyek nem merevek, azaz k¨ot´es-elfordul´asok lehets´egesek. Az extra korl´atoz´asok sz´ama vagy a megmaradt k¨ot´es-forgat´as szabads´agi fokok sz´ama egy r´eszstrukt´ ur´aban sz´amszer˝ us´ıti a relat´ıv merevs´eget/flexibilit´ast, ´es biztos´ıt egy rugalmass´agi indexet minden k¨ot´esre. Ezt a sz´am´ıt´asi elj´ar´ast el˝osz¨or u ¨vegszer˝ u anyagok anal´ızis´ere haszn´alt´ak. Megk¨ozel´ıt˝oleg egymilli´oszor gyorsabb, mint a molekul´aris dinamikai szimul´aci´o, ´es egyetlen statikus h´aromdimenzi´os strukt´ ura anal´ızisek´ent m´eri a protein f˝o- ´es oldall´ancainak alapvet˝o rugalmass´ag´at. A term´eszetben gyakori a szab´alyoss´ag, szimmetria, ´es a krist´alykapcsolatok is

1

˝ BEVEZETO

2

befoly´asolj´ak a rugalmass´agot. Ezt a feh´erj´ek vizsg´alatakor is figyelembe kell venni. Egy olyan nagyobb molekul´at, amely k´et azonos kisebb molekula o¨sszekapcsol´od´as´aval keletkezik, dimernek nevez¨ unk. A k´et o¨sszekapcsol´od´o molekula energiaminimaliz´al´asi okokb´ol forg´asszimmetrikusan kapcsol´odik, ´es a molekula v´altoz´asai is meg˝orzik a szimmetri´at. A dimerek gyakori alloszterikus feh´erj´ek, mint p´eld´aul a triptof´an represszor, amely a DNS-hez k¨ot˝odve g´atolja a triptof´antermel´est. A triptof´an a 20 standard feh´erjealkot´o aminosav egyike, az alv´ashoz sz¨ uks´eges neurotranszmitterek el˝oanyaga.

1. ´abra. Zeolitok. [24] A forg´asszimmetrikus anyagokon k´ıv¨ ul m´as szab´alyos elrendez˝od´es˝ u anyagok is vannak, mint p´eld´aul a periodikus krist´alyszerkezetek, perovszkit, kvarc, aluminoszilik´atok (pl. ker´amiak´esz´ıt´eshez) ´es zeolitok. A zeolitok krist´alyos mikropor´ozus szerkezetek, melyeket sz´amos ter¨ uleten haszn´alnak, p´eld´aul molekulasz˝ ur˝ok´ent, szagelsz´ıv´okn´al, mos´oszergy´art´asn´al, takarm´anykieg´esz´ıt˝okn´el, u ¨d´ıt˝oitalok adal´ekanyagak´ent, az u ˝rkutat´asban, ´es sz´amos m´as helyen. Manaps´ag a szintetikus zeolitok a legfontosabb kataliz´atorok a petrolk´emiai finom´ıt´okban. Jelent˝os er˝ofesz´ıt´esek ir´anyultak u ´j zeolitok szintetiz´al´as´ara speci´alis p´orusgeometri´aval.[19], [24], [18] ´Igy nem meglep˝o, hogy a merevs´egi k´erd´esk¨or ezen ´aga igen akt´ıv kutat´asi ter¨ uletnek sz´am´ıt.

1. fejezet ´ Altal´ anos gr´ afmerevs´ egi bevezet˝ o A k¨ovetkez˝okben v´egig r´ ud-csukl´o t´ıpus´ u szerkezeteket t´argyalunk. El˝osz¨or bevezetem az alapvet˝o gr´afmerevs´egi fogalmakat, valamint r¨oviden ismertetem az alapvet˝o t´eteleket. A fogalmak tetsz˝oleges d dimenzi´os t´erben ´ertelmezhet˝ok, de a merevs´eg tesztel´ese, illetve el˝oa´ll´ıt´asi t´etelek d > 2 eset´en nem ismertek.

1.1. Alapfogalmak A r´ ud-csukl´o szerkezeteket u ´gy k´epzelhetj¨ uk el, hogy a gr´af ´elei merev rudak, m´ıg a gr´af cs´ ucsai olyan csukl´ok, melyek ment´en a rudak szabadon elfordulhatnak, de term´eszetesen a gr´af a´ltal adott strukt´ ur´at, vagyis a kapcsol´od´ast az ´elek ´es cs´ ucsok k¨oz¨ott v´egig meg kell o˝rizni mozg´as k¨ozben. 1.1.1. Defin´ıci´ o. Legyen G = (V, E) egy gr´af, ´es legyen p : V → Rd a pontok egy elhelyez´ese a d-dimenzi´os t´erben. Az ´eleknek a pontokat ¨osszek¨ot˝o, egym´ast esetleg metsz˝o egyenes szakaszok felelnek meg. Ekkor azt mondjuk, hogy a (G, p) szerkezet a G gr´af egy realiz´aci´oja Rd -ben. 1.1.2. Defin´ıci´ o. A (G, q) szerkezet ekvivalens a (G, p) szerkezettel, ha a 3

´ ´ ´ ´ BEVEZETO ˝ FEJEZET 1. ALTAL ANOS GRAFMEREVS EGI

4

megfelel˝o ´elek hossza a k´et realiz´aci´oban ugyanaz, vagyis minden uv ∈ E-re |p(u) − p(v)| =|q(u) − q(v)| teljes¨ ul. 1.1.3. Defin´ıci´ o. A (G, q) szerkezet kongruens a (G, p) szerkezettel, ha b´armely k´et pont t´avols´aga a k´et realiz´aci´oban ugyanannyi, vagyis |p(u) − p(v)| = |q(u) − q(v)| teljes¨ ul minden u, v ∈ V -re.

1.1. ´abra. A k´et szerkezet ekvivalens, de nem kongruens R2 -ben.

1.1.4. Defin´ıci´ o. A (G, p) szerkezet merev, ha l´etezik  > 0, hogy minden olyan (G, p)-vel ekvivalens (G, q) szerkezetre, ahol ∀u ∈ V -re |p(u) − q(u)| <  teljes¨ ul, arra (G, q) kongruens is (G, p)-vel. 1.1.5. Defin´ıci´ o. (G, p) folytonos mozg´asa (G, q)-ba: olyan Pv (t) f¨ uggv´enyek (v ∈ V , t ∈ [0, 1]), melyekre teljes¨ ulnek a k¨ovetkez˝ok: • ∀v ∈ V -re Pv (0) = p(v), Pv (1) = q(v); • ∀uv ∈ E, ∀t ∈ [0, 1]-re |Pu (t) − Pv (t)| = |Pu (0) − Pv (0)|; • ∀v ∈ V , ∀t ∈ [0, 1]-re Pv (t) folytonos. 1.1.6. T´ etel. [12] (G, p) pontosan akkor merev, ha b´armely folytonos mozg´asa csak vele kongruens szerkezetbe viheti.

´ ´ ´ ´ BEVEZETO ˝ FEJEZET 1. ALTAL ANOS GRAFMEREVS EGI

5

1.1.7. Defin´ıci´ o. (G, p) infinitezim´alis mozg´asa alatt olyan u : V → Rd f¨ uggv´enyt ´ert¨ unk, hogy ∀vi , vj ∈ V -re (u(vi ) − u(vj ))(p(vi ) − p(vj )) = 0 teljes¨ ul. Ez intuit´ıven azt jelenti, hogy a szerkezet pontjainak adunk egy kis kezd˝osebess´eget, ´es ezen ir´anyokkal infinitezim´alisan deform´aljuk az eg´esz szerkezetet. 1.1.8. Defin´ıci´ o. A (G, p) szerkezet merevs´egi m´atrix´at jel¨olje R(G, p). Ez egy |E|×d|V | m´eret˝ u m´atrix, melyben minden ´elhez tartozik egy sor, ´es minden cs´ ucshoz tartozik dimenzi´osz´amnyi oszlop. Az uv ´el sor´at jel¨olje R(G, p)uv , ebben a sorban minden u-t´ol ´es v-t˝ol k¨ ul¨onb¨oz˝o poz´ıci´oban 0, az u-hoz tartoz´o r´eszen p(u) − p(v), a v-hez tartoz´o r´eszen pedig p(v) − p(u) ´all: 

. . . 0 u1 − v1 . . . ud − vd 0 . . . 0 v1 − u1 . . . vd − ud 0 . . .



1.1.9. Megjegyz´ es. Az u pontosan akkor infinitezim´alis mozg´asa (G, p)-nek, ha R(G, p) · u = 0. 1.1.10. Megjegyz´ es. Ha figyelembe vessz¨ uk, hogy R(G, p) magter´eben biztosan szerepelni fognak a trivi´alis mozg´asok (eltol´as ´es forgat´as), a k¨ovetkez˝o
fels˝o becsl´est kapjuk: |V | ≥ d + 2 eset´en rang(R(G, p)) ≤ d|V | − d+1 , m´ıg 2
|V | ≤ d + 2 eset´en rang(R(G, p)) ≤ |V2 | .

1.2. ´abra. Merev, de nem infinitezim´alisan merev R2 -ben.

´ ´ ´ ´ BEVEZETO ˝ FEJEZET 1. ALTAL ANOS GRAFMEREVS EGI

6

1.1.11. Defin´ıci´ o. (G, p) infinitezim´alisan merev, ha rang(R(G, p)) = d|V |−

d+1 vagy rang(R(G, p)) = |V2 | . 2 1.1.12. T´ etel. [20],[12] Ha (G, p) infinitezim´alisan merev, akkor merev. (Ford´ıtva nem felt´etlen¨ ul igaz!) 1.1.13. T´ etel. [20],[12] Ha (G, p) ”kell˝oen ´altal´anos helyzet˝ u”, vagyis generikus (p koordin´at´ainak halmaza algebrailag f¨ uggetlen Q felett), akkor m´ar igaz, hogy (G, p) pontosan akkor infinitezim´alisan merev, ha merev. B´ar egy szerkezet merevs´ege f¨ ugg a realiz´aci´ot´ol, a fenti t´etel k¨ovetkezm´enyek´epp nem csak szerkezetek, de gr´afok merevs´eg´er˝ol is van ´ertelme besz´elni. Egy adott gr´af majdnem minden realiz´aci´oja hasonl´ok´epp viselkedik merevs´egi szempontb´ol. 1.1.14. Defin´ıci´ o. A G gr´af merev, ha l´etezik infinitezim´alisan merev (G, p) realiz´aci´oja.

1.2. Gr´afmerevs´eg jellemz´ese d = 2 eset´en A s´ıkban ismert a merev gr´afok jellemz´ese, l´etezik r´ajuk el˝o´all´ıt´asi t´etel, valamint hat´ekony algoritmus a merevs´eg tesztel´es´ere. A jellemz´eshez sz¨ uks´eg van a f¨ uggetlens´eg fogalm´anak bevezet´es´ere. 1.2.1. Defin´ıci´ o. A (G, p) szerkezet f¨ uggetlen, ha R(G, p) sorai line´arisan f¨ uggetlenek. 1.2.2. Defin´ıci´ o. A G = (V, E) gr´af f¨ uggetlen, ha l´etezik f¨ uggetlen realiz´aci´oja. 1.2.3. Megjegyz´ es. Ha G = (V, E) f¨ uggetlen, akkor |E| ≤ 2|V | − 3. (Ez az R(G, p) rangj´ara vonatkoz´o fels˝o becsl´es d = 2 esetben.) G pontosan akkor merev, ha l´etezik benne 2|V | − 3 ´elsz´am´ u f¨ uggetlen r´eszgr´af. Ez egy ritka tan´ u a merevs´egre.

´ ´ ´ ´ BEVEZETO ˝ FEJEZET 1. ALTAL ANOS GRAFMEREVS EGI

7

1.2.4. Defin´ıci´ o. G = (V, E) ritka, ha ∀X ⊆ V , |X| ≥ 2-re i(X) ≤ 2|X| − 3, ahol i(X) jel¨oli a fesz´ıtett ´elek sz´am´at. 1.2.5. Lemma. Ha G = (V, E) f¨ uggetlen, akkor ritka. A merev gr´afok jellemz´es´ehez sz¨ uks´eg¨ unk lesz k´et kiterjeszt´esi m˝ uveletre a gr´afon. 1.2.6. Defin´ıci´ o. A m´asodfok´ u kiterjeszt´es jelentse azt, hogy egy u ´j cs´ ucsot vesz¨ unk a gr´afhoz, ´es ¨osszek¨otj¨ uk k´et r´egi cs´ uccsal. A harmadfok´ u kiterjeszt´es pedig jelentse azt, hogy egy u ´j cs´ ucsot vesz¨ unk a gr´afhoz, v´alasztunk a r´egi cs´ ucsok k¨oz¨ ul k´et olyat, amelyek k¨ozt vezet ´el, ezt az ´elt t¨or¨olj¨ uk, majd az u ´j cs´ ucsot ¨osszek¨otj¨ uk ezzel a k´et r´egi cs´ uccsal, ´es m´eg egy harmadikkal. 1.2.7. Lemma. Legyen adott a G gr´af ´es annak egy p realiz´aci´oja a s´ıkon. Ha a m´asodfok´ u kiterjeszt´esben szerepl˝o h´arom cs´ ucs nincs egy egyenesen, akkor a m˝ uvelet meg˝orzi a f¨ uggetlens´eget. Ha a harmadfok´ u kiterjeszt´esben szerepl˝o h´arom r´egi cs´ ucs nem kolline´aris, valamint az u ´j cs´ ucs rajta van a t¨or¨olt ´el v´egpontjainak egyenes´en, ez a m˝ uvelet is meg˝orzi a f¨ uggetlens´eget.

1.3. a´bra. M´asod-, illetve harmadfok´ u kiterjeszt´es. (A harmadfok´ u kiterjeszt´es nem az eml´ıtett merevs´eget meg˝orz˝o m´odon szerepel az ´abr´an.)

1.2.8. Lemma. Ha a G gr´af ritka, |V (G)| ≥ 3, elv´egezhet˝o a m´asod- vagy a harmadfok´ u kiterjeszt´es inverz m˝ uvelete a ritkas´ag meg˝orz´ese mellett.

´ ´ ´ ´ BEVEZETO ˝ FEJEZET 1. ALTAL ANOS GRAFMEREVS EGI

8

1.2.9. T´ etel. (Laman-t´etel) [14] G ritka ⇐⇒ G f¨ uggetlen. 1.2.10. T´ etel. (Henneberg-f´ele el˝o´all´ıt´asi t´etel) [3] G pontosan akkor minim´alisan merev (m´as sz´oval izosztatikus), ha megkaphat´o egyetlen ´elb˝ol m´asod´es harmadfok´ u kiterjeszt´esekkel. 1.2.11. Defin´ıci´ o. Az X = (X1 , . . . , Xt ), Xi ⊆ V , |Xi | ≥ 2 halmaz egy fed´ese G = (V, E)-nek, ha ∪ti=1 E(Xi ) = E. A fed´es ´ert´eke pedig V al(X ) = Pt i=1 (2|Xi | − 3). A k¨ovetkez˝o t´etel ad egy Co-NP jellemz´est. 1.2.12. T´ etel. Lov´asz-Yemini t´etel [13] A f¨ uggetlen ´elhalmazok m´erete ´es a fed´esek ´ert´eke k¨oz¨ott a k¨ovetkez˝o egyenl˝os´eg teljes¨ ul: max {F : F ⊆ E ritka} = min {V al(X ) : X fed´es}. 1.2.13. Megjegyz´ es. El´eg u ´n. v´ekony fed´esekre minimaliz´alni, vagyis amelyekre teljes¨ ul az |Xi ∩ Xj | ≤ 1 egyenl˝otlens´eg. A merevs´eg tesztel´es´ere, illetve maxim´alis ritka halmaz sz´am´ıt´as´ara l´etezik O(n2 ) fut´asidej˝ u algoritmus, mely a fut´as sor´an v´egig fenntart egy optim´alis fed´est. 1.2.14. Defin´ıci´ o. Egy G gr´af 3Fa2 part´ıci´oja azt jelenti, hogy az ´elhalmazt h´arom ´eldiszjunkt f´ara part´ıcion´aljuk, melyekre teljes¨ ul az, hogy a gr´af minden pontj´at pontosan k´et darab fa tartalmazza. Egy 3Fa2 part´ıci´ot megfelel˝onek (proper) nevez¨ unk, ha a diszjunkt f´aknak nincsenek nemtrivi´alis r´eszf´ai, melyek ugyanazt a cs´ ucshalmazt fesz´ıtik. 1.2.15. T´ etel. (Crapo t´etele) [15] Egy G gr´af pontosan akkor generikusan izosztatikus, ha van megfelel˝o (proper) 3Fa2 part´ıci´oja. -

2. fejezet Henneberg-t´ıpus´ u m˝ uveletek ´ Erdekes k´erd´es, hogy szimmetrikus szerkezetek ´es nem felt´etlen¨ ul szimmetrikus mozg´asok eset´en megfogalmazhat´ok-e a kor´abbi s´ıkbeli t´etelekkel anal´og ´all´ıt´asok. Ebben a fejezetben a 2π/3-sz¨og˝ u forgat´as eset´et t´argyalom.

2.1. Szimmetrikus szerkezetek - bevezet˝o 2.1.1. Defin´ıci´ o. A (G, p) d-dimenzi´os szerkezet szimmetria oper´aci´oja olyan x izometri´aja a t´ernek, hogy valamely α ∈ Aut(G) eset´en ∀v ∈ V -re x(p(v)) = p(α(v)) teljes¨ ul. Ezek csopotj´at a kompoz´ıci´ora n´ezve a (G, p) szerkezet pont csoportj´anak nevezz¨ uk. Jel¨olje C3 a 2π/3-as forgat´ast, C3 pedig a csoportj´at. Adott S d-dimenzi´os szimmetriacsoport ´es adott G gr´af eset´en R(G,S) jelenti G azon d-dimenzi´os realiz´aci´oit, ahol S (nem felt´etlen¨ ul val´odi) r´eszcsoportja a gr´af pont csoportj´anak. M´ask´epp megfogalmazva R(G,S) tartalmaz minden (G, p) realiz´acio´t, amihez l´etezik Φ : S → Aut(G) lek´epez´es, hogy (*) ∀v ∈ V (G) ´es ∀x ∈ S eset´en

x(p(v)) = p(Φ(x)(v)).

A fenti o¨sszef¨ ugg´est kiel´eg´ıt˝o szerkezetet Φ-t´ıpus´ unak nevezz¨ uk, ´es a Φ-t´ıpus´ u R(G,S) -beli realiz´aci´ok halmaz´at R(G,S,Φ) -vel jel¨olj¨ uk. 9

´ MUVELETEK ˝ FEJEZET 2. HENNEBERG-T´IPUSU

10

2.1. a´bra. Izosztatikus szerkezetek a s´ıkon C3 pont csoporttal. Az els˝o szerkezet a h´aromsz¨og prizma gr´af egy realiz´aci´oja R(G,C3 ,Φ) -ben, ahol Φ(C3 ) = (v1 v2 v3 )(v4 v5 v/ ). A m´asodik szerkezet a K3,3 gr´af egy realiz´aci´oja R(G,C3 ,Ψ) , ahol Ψ(C3 ) = (v1 v2 v3 )(v4 v5 v6 ).

2.1.2. Defin´ıci´ o. Tekints¨ uk a G = (V, E) gr´af ponthalmaz´an a Kn = (V, E 0 ) teljes gr´afot, tov´abb´a az S szimmetriacsoportot a Φ : S → Aut(G) lek´epez´essel. A (G, p) ∈ R(G,S,Φ) szerkezet (S, Φ)-generikus, ha R(Kn , p) tetsz˝oleges r´eszm´atrix´anak determin´ana akkor ´es csak akkor 0, ha minden olyan p0 -re 0, ami kiel´eg´ıti (*)-t. Intuit´ıven ez azt jelenti, hogy egy ilyen realiz´aci´o az Sv = {Φ(x)(v)|x ∈ S} szimmetria orbitok reprezent´ansainak elhelyez´ese generikus poz´ıci´okba. (A t¨obbi cs´ ucs helyzete ebb˝ol m´ar egy´ertelm˝ u.) 2.1.3. Defin´ıci´ o. Adott a G gr´af, S szimetriacsoport, illetve a hozz´a tartoz´o Φ : S → Aut(G) lek´epez´es. G-t (S, Φ)-generikusan infinitezim´alisan merevnek (f¨ uggetlennek, izosztatikusnak) nevezz¨ uk, ha G minden realiz´aci´oja, ami (S, Φ)-generikus, infinitezim´alisan merev (f¨ uggetlen, izosztatikus). 2.1.4. T´ etel. [10] Legyen G egy gr´af, S szimmetriacsoport, Φ : S → Aut(G) lek´epez´es olyan, hogy R(G,S,Φ) 6= ∅. Ekkor a k¨ovetkez˝ok ekvivalensek: • ∃ infinitezim´alisan merev (f¨ uggetlen, izosztatikus) (G, p) ∈ R(G,S,Φ) szerkezet; • G minden (S, Φ)-generikus realiz´ac´oja infinitezim´alisan merev (f¨ uggetlen, izosztatikus).

´ MUVELETEK ˝ FEJEZET 2. HENNEBERG-T´IPUSU

11

2.2. C3 a s´ıkban A tov´abbiakban tekints¨ uk az orig´o k¨oz´eppont´ u, 2π/3 sz¨og˝ u forgat´ast a s´ıkban.

2.2.1. M˝uveletek 2.2.1. Defin´ıci´ o. Adott a G gr´af, valamint a Φ : C3 → Aut(G) lek´epez´es, ´es (G, p) ∈ R(G,C3 ,Φ) . A (v, p(v)) csukl´ot C3 fix´alja Φ-re n´ezve, ha Φ(C3 )(v) = v. A fix´alt csukl´ok sz´ama (G, p)-ben jΦ (C3 ). 2.2.2. Megjegyz´ es. Ha (v, p(v)) (G, p) ∈ R(G,C3 ,Φ) -beli csukl´ot C3 fix´alja Φ-re n´ezve, akkor C3 (p(v)) = p(Φ(C3 )(v)) = p(v), azaz v a C3 forgat´as k¨oz´eppontj´aban fekszik. 2.2.3. T´ etel. [2] Adott a G gr´af, Φ : C3 → Aut(G) homomorfizmus, (G, p) egy izosztatikus szerkezet R(G,C3 ,Φ) -ben, tov´abb´a a p(v) pontok fesz´ıts´ek ki R2 -et. Ekkor G teljes´ıti a Laman-felt´eteleket ´es jΦ (C3 ) = 0. A t´etel bizony´ıt´asa a szimmetrikus Maxwell-egyenl˝os´egb˝ol olvashat´o ki. B˝ovebben l´asd: [2]. 2.2.4. Defin´ıci´ o. [23] Adott G gr´af, v1 , v2 ∈ V (G), v1 6= v2 , C3 = {Id, C3 , C32 } a s´ıkban, Φ : C3 → Aut(G) homomorfizmus. Vegy¨ unk h´arom u ´j u1 , u2 , u3 pontot, valamint a k¨ovetkez˝o ´eleket: u1 v1 , u1 v2 , u2 Φ(C3 )(v1 ), u2 Φ(C3 )(v2 ), u3 Φ(C32 )(v1 ), u3 Φ(C32 )(v2 ). Ezt a m˝ uveletet (C3 , Φ) ponthozz´aad´asnak nevezz¨ uk. 2.2.5. Defin´ıci´ o. [23] Adott a G gr´af, v1 , v2 , v3 ∈ V (G) p´aronk´ent k¨ ul¨onb¨oz˝ok, v1 v2 ∈ E(G), C3 = {Id, C3 , C32 } a s´ıkban, Φ : C3 → Aut(G) homomorfizmus, ´es v1 , v2 nem lehetnek fixek Φ(C3 )-ra n´ezve. Vegy¨ unk h´arom u ´j u1 , u2 , u3 pontot, t¨or¨olj¨ uk a v1 v2 , Φ(C3 )(v1 v2 ), Φ(C32 )(v1 v2 ) ´eleket, valamint h´ uzzuk be a k¨ovetkez˝o u ´j ´eleket: u1 vi , u2 Φ(C3 )(vi ), u3 Φ(C32 )(vi ), ahol i = 1, . . . , 3. Ezt a m˝ uveletet (C3 , Φ) ´elfeloszt´asnak nevezz¨ uk.

´ MUVELETEK ˝ FEJEZET 2. HENNEBERG-T´IPUSU

12

2.2.6. Defin´ıci´ o. [23] Adott a G gr´af, v0 ∈ V (G), C3 = {Id, C3 , C32 } a s´ıkban, Φ : C3 → Aut(G) homomorfizmus, v0 nem fix Φ(C3 )-ra n´ezve. Vegy¨ unk h´arom u ´j u1 , u2 , u3 pontot, valamint a k¨ovetkez˝o u ´j ´eleket: u1 u2 , u2 u3 , u3 u2 , u1 v0 , u2 Φ(C3 )(v0 ), u3 Φ(C32 )(v0 ). Ezt a m˝ uveletet (C3 , Φ) h´aromsz¨og-kiterjeszt´esnek nevezz¨ uk. 2.2.7. Megjegyz´ es. A fenti h´arom m˝ uvelet mindegyike v´egrehajthat´o m´asod´es harmadfok´ u kiterjeszt´esek sorozatak´ent is, teh´at meg˝orzik a Laman-tulajdons´agot. A ponthozz´aad´as j´ol l´athat´oan h´arom darab m´asodfok´ u kiterjeszt´es szimmetrikusan elv´egezve. Az ´elfeloszt´as h´arom darab harmadfok´ u kiterjeszt´es szimmetrikusan elv´egezve. A h´aromsz¨og-kiterjeszt´eshez u ´gy juthatunk el, ha el˝osz¨or u1 -et m´asodok´ u kiterjeszt´essel hozz´akapcsoljuk v1 -hez ´es v2 -h¨oz. Ezut´an u2 -t harmadfok´ u kiterjeszt´essel kapcsoljuk u1 -hez, v2 -h¨oz ´es v3 -hoz az u1 v2 ´el t¨orl´es´evel, v´eg¨ ul u3 -at szint´en harmadfok´ u kiterjeszt´essel hozz´akapcsoljuk u1 hez, u2 -h¨oz ´es v3 -hoz az u2 v3 ´el t¨orl´es´evel.

2.2. ´abra. Ponthozz´aad´as, ´elfeloszt´as ´es h´aromsz¨og-kiterjeszt´es.

2.2.8. Defin´ıci´ o. [23] Adott a G gr´af, C3 = {Id, C3 , C32 } a s´ıkban, Φ : C3 → Aut(G) homomorfizmus. A G gr´afnak egy (C3 , Φ) 3Fa2 part´ıci´oja olyan speci´alis {E(T0 ), E(T1 ), E(T2 )} 3Fa2 part´ıci´o, melyben ∀i ∈ {1, 2, 3}-ra megk¨ovetelj¨ uk, hogy Φ(C3 )(Ti ) = Ti+1 teljes¨ ulj¨on modulo 3. (Ez egy 3Fa2 part´ıci´o faforgat´asi tulajdons´aggal.)

´ MUVELETEK ˝ FEJEZET 2. HENNEBERG-T´IPUSU

13

2.2.2. S´ıkbeli szerkezetek alapt´eteleinek anal´ogi´aja 2.2.9. T´ etel. [7] Legyen G egy izosztatikus gr´af a s´ıkban, ´es legyen v egy harmadfok´ u cs´ ucsa, melynek szomsz´edai: w1 , w2 , w3 . Ekkor a v t¨orl´es´evel keletkez˝o gr´afban ki lehet v´alasztani w1 , w2 ´es w3 k¨oz¨ ul k´et olyat, hogy k¨oz´ej¨ uk beh´ uzva egy ´elt az u ´j G0 gr´af is izosztatikus legyen. A k¨ovetkez˝o defin´ıci´o a´ltal´anos´ıtja a szerkezet fogalm´at. 2.2.10. Defin´ıci´ o. Legyen G egy gr´af, V (G) = {v1 , . . . , vn }. Egy R2 -beli keret egy olyan (G, p, q) h´armas, melyre p : V (G) → R2 , q : E(G) → R2 \ {0} lek´epez´esek olyanok, hogy minden vi vj ∈ E(G)-re l´etezik λij ∈ R2 , melyre p(vi ) − p(v − j) = λij q(vi vj ). (λij = 0 is lehets´eges.) 2.2.11. Defin´ıci´ o. A (G, p, q) keret a´ltal´anos´ıtott merevs´egi m´atrixa R2 -ben a k¨ovetkez˝o: 

.. .



   R(G, p, q) =  0 . . . 0 q(v v ) 0 . . . 0 −q(v v ) 0 . . . 0 i j i j   .. . 2.2.12. Defin´ıci´ o. Azt mondjuk, hogy a (G, p, q) keret f¨ uggetlen, ha R(G, p, q) sorai line´arisan f¨ uggetlenek. 2.2.13. Megjegyz´ es. Ha a (G, p, q) keret f¨ uggetlen ´es vi vj ∈ E(G) eset´en p(vi ) 6= p(vj ), akkor a (G, p) szerkezet is f¨ uggetlen. 2.2.14. T´ etel. [23] Legyen G egy legal´abb h´arom pont´ u gr´af, C3 = {Id, C3 , C32 } a s´ıkban, Φ : C3 → Aut(G) homomorfizmus. A k¨ovetkez˝ok ekvivalensek: • (A)

R(G,C3 ,Φ) 6= ∅ ´es G (C3 , Φ)-generikusan izosztatikus;

• (B)

|E(G)| = 2|V (G)|−3, i(X) ≤ 2|X|−3 minden X ⊆ V (G), |X| ≥ 2

eset´en, tov´abb´a jΦ(C3 ) = 0;

´ MUVELETEK ˝ FEJEZET 2. HENNEBERG-T´IPUSU • (C)

14

∃(K3 , Φ0 ) = (G0 , Φ0 ), (G1 , Φ1 ), . . . , () = (G, Φ) konstrukci´osorozat,

amelyre Gi+1 a fent defini´alt h´arom m˝ uvelet valamelyik´evel kaphat´o meg Gi -b˝ol, Φi+1 |V (Gi ) = Φi , tov´abb´a Φi+1 (C3 )|u1 ,u2 ,u3 = (u1 u2 u3 ), ahol a h´arom u ´j pontot u1 , u2 , u3 jel¨oli; • (D)

G-nek van egy megfelel˝o (proper) (C3 , Φ) 3Fa2 part´ıci´oja.

Bizony´ıt´as: (A) ⇒ (B): A 2.2.3 t´etel ´eppen ezt mondja ki. (B) ⇒ (C) Ez az ir´any teljes indukci´ot haszn´alva esetvizsg´alattal vezethet˝o le, felhaszn´alva a gr´af (hagyom´anyos ´ertelemben vett) Henneberg-fel´ep´ıt´es´ere vonatkoz´o ismereteket. A Φ : C3 → Aut(G) l´etez´ese ´es jΦ(C3 ) = 0 miatt |V (G)| ≡ 0 modulo 3. A legkisebb ilyen gr´af a K3 , amelyhez nemtrivi´alis Φ tartozik. Az alapeset teh´at k´esz. Tegy¨ uk fel, hogy n pontig tudjuk, hogy igaz az a´ll´ıt´as, ´es tekints¨ unk egy |(V (G)| = n + 3 pont´ u gr´afot. Ha ennek a gr´afnak van v m´asodfok´ u pontja, akkor m´ar csak az kell, ul¨onb¨oz˝o m´asodfok´ u) pontok k¨ozt hogy v, Φ(C3 )(v) ´es Φ(C32 )(v) (egym´ast´ol k¨ nem vezet ´el. Ha vΦ(C3 )(v) ∈ E(G), akkor a szimmetria miatt ez a h´arom pont egy h´aromsz¨oget alkot, mely nem kapcsol´odik a gr´af t¨obbi r´esz´ehez, teh´at G nem lehet Laman-tulajdons´ag´ u: |E(G − {v, Φ(C3 )(v), Φ(C32 )(v)})| = |E(G)| − 3 = 2|V (G)| − 6 = 2|V (G − {v, Φ(C3 )(v), Φ(C32 )(v)})|. Teh´at a v, Φ(C3 )(v), Φ(C32 )(v) pontok olyanok, hogy az ˝o t¨orl´es¨ uk ut´an keletkez˝o gr´afban a Laman-felt´etel meg˝orz˝odik, az indukci´o miatt l´etezik a t´etelbeli konstrukci´osorozat, ´es o˝k a ponthozz´aad´as m˝ uvelettel adhat´ok a gr´afhoz a sorozat utols´o elemek´ent. Ha a G gr´afnak nincs m´asodfok´ u pontja, akkor a Laman-felt´etel garant´alja, hogy van harmadfok´ u pontja, jel¨olje ezt ism´et v. N´egy esetet kell megk¨ ul¨onb¨oztetn¨ unk v, Φ(C3 )(v), Φ(C32 )(v) elhelyezked´es´et tekintve:

´ MUVELETEK ˝ FEJEZET 2. HENNEBERG-T´IPUSU

15

• (1) nem vezet k¨ozt¨ uk ´el, de mindh´arman ugyanazzal a h´arom ponttal szomsz´edosak; • (2) nem vezet k¨ozt¨ uk ´el, de b´armely kett˝onek van k¨oz¨os szomsz´edja; • (3) nem vezet k¨ozt¨ uk ´el, ´es szomsz´edjaik is k¨ ul¨onb¨oz˝oek; • (4) vΦ(C3 )(v) ∈ E(G) (ekkor harmadik szomsz´edaik k¨ ul¨onb¨oz˝oek, mivel nincs a forgat´as ´altal fix´alt pont).

2.3. ´abra.

N´egy k¨ ul¨onb¨oz˝o eset a harmadfok´ u pont elforgatottjainak ´es

szomsz´edainak kapcsolat´ara. Az (1) esetben a 2.2.9 T´etel miatt v leemelhet˝o oly m´odon, hogy szomsz´edai k¨oz¨ ul kett˝ot ´ellel k¨ot¨ unk ¨ossze, ´es v-t t¨or¨olj¨ uk (a harmadfok´ u kiterjeszt´es Henneberg-m˝ uvelet inverzek´ent), valamint ugyanezt v´egrehajthatjuk sorban uk, Φ(C3 )(v)-re ´es Φ(C32 )(v)-re is, vagyis a szomsz´edait p´aronk´ent o¨sszek¨otj¨ m´ıg v-t ´es k´epeit t¨or¨olj¨ uk. Ekkor a Laman-felt´etel meg˝orz˝odik. Indukci´oval erre a gr´afra l´etezik a k´ıv´ant konstrukci´osorozat, ´es befejez˝o l´ep´esk´ent m´eg egy ´elfeloszt´asra lesz sz¨ uks´eg¨ unk, hogy visszakapjuk G-t. A (2) ´es (3) esetben a 2.2.9 T´etel miatt szintj´en leemelhet˝o v oly m´odon, hogy szomsz´edai k¨oz¨ ul kett˝ot o¨sszek¨ot¨ unk, legyenek ezek v1 ´es v2 . v elforgatottjaival ugyanezt megtessz¨ uk (de ott nem felt´etlen¨ ul a szimmetrikus szomsz´edok k¨oz´e ker¨ ul ´el). ´Igy a G0 gr´afhoz jutunk. H ⊆ G0 −{v1 , v2 } r´eszgr´afra igaz lesz a k¨ovetkez˝o: |E(H)| ≤ 2|V (H)|−4. S˝ot, ha G0 jel¨oli a G gr´afb´ol v ´es elforgatottjai t¨orl´es´evel kapott gr´afot, minden H ⊆ G0 -re, ahol v1 , v2 ∈ H, ugyanez igaz.

´ MUVELETEK ˝ FEJEZET 2. HENNEBERG-T´IPUSU

16

Illetve mivel G0 invari´ans a forgat´asra, minden olyan H r´eszgr´afra is teljes¨ ul az o¨sszef¨ ugg´es, amely tartalmazza Φ(C3 )(v1 )-t ´es Φ(C3 )(v2 )-t, vagy Φ(C3 )2 (v1 )t ´es Φ(C3 )2 (v2 )-t. Ki fog der¨ ulni, hogy {v1 , v2 }, {Φ(C3 )(v1 ), Φ(C3 )(v2 )} ´es {Φ(C3 )2 (v1 ), Φ(C3 )2 (v2 )} diszjunkt p´arok. Tegy¨ uk fel, hogy {v1 , v2 } = {Φ(C3 )(v1 ), Φ(C3 )(v2 )}. Ekkor v1 = Φ(C3 )(v2 ) ´es v2 = Φ(C3 )(v1 ), amib˝ol k¨ovetkezik, hogy v2 = Φ(C3 )(v1 ) = Φ(C3 )2 (v2 ), de ez ellentmond annak, hogy nincs a forgat´as a´ltal fix´alt pont. A t¨obbire ugyan´ıgy. Defini´aljuk a k¨ovetkez˝o gr´afot: G = G0 + {{v1 , v2 }, {Φ(C3 )(v1 ), Φ(C3 )(v2 )}, {Φ(C3 )2 (v1 ), Φ(C3 )2 (v2 )}}. Ez kiel´eg´ıti a Laman-felt´eteleket. |E(G)| = |E(G0 )| + 3 = |E(G)| − 6 = 2|V (G)| − 9 = 2|V (G)| − 3 r¨ogt¨on ad´odik. Tegy¨ uk fel, hogy l´etezik H ⊆ G0 , v1 , v2 , Φ(C3 )(v1 ), Φ(C3 )(v2 ) ∈ V (H) ´es |E(H)| = 2|V (H)| − 4. Φ(C3 )(H)-t ´es Φ(C3 )(H)-t is tekinthetj¨ uk, hasonl´o tulajdons´agokkal. Legyen H 0 = H ∪ Φ(C3 )(H). Ekkor |E(H 0 )| = |E(H)| + |E(Φ(C3 )(H))| − |E(H ∩ Φ(C3 )(H))| ≥ 2|V (H)| − 4 + 2|V (Φ(C3 )(H)| − 4 − (2|V (H ∩ Φ(C3 )(H))| − 4) = 2|V (H 0 )| − 4, mert H ∩ Φ(C3 )(H) r´eszgr´afja G0 -nek, ´es tartalmazza Φ(C3 )(v1 )-t ´es Φ(C3 )(v2 )-t. H 0 szint´en tartalmazza o˝ket, ez´ert |E(H 0 )| = 2|V (H 0 )| − 4. Hasonl´o igaz H 00 = H 0 ∩ Φ(C3 )2 (H)ra, |E(H 00 )| = 2|V (H 00 )| − 4, r´aad´asul H 00 invari´ans a forgat´asra ´es nincs fix pontja, vagyis ´eleinek ´es cs´ ucsainak sz´ama 3-mal oszthat´o. Ez ellentmond |E(H 00 )| = 2|V (H 00 )| − 4-nek. Teh´at minden H ⊆ G0 -re, ahol v1 , v2 , Φ(C3 )(v1 ), Φ(C3 )(v2 ), arra |E(H)| ≤ 2|V (H)| − 5 teljes¨ ul. (A forgat´assal kapott a´l´ıt´asok igazak G0 invarianci´aja miatt.) M´ar csak azt kell megmutatni, hogy ez sem teljes¨ ulhet egyenl˝os´eggel, ha H m´eg Φ(C3 )2 (v1 ), Φ(C3 )2 (v2 )-t is tartalmazza. Indirekt tegy¨ uk fel, hogy l´etezik H, ami egyenl˝os´eggel teljes´ıti. Akkor H elforgatottjaira ugyanez igaz. Legyen H 0 = H ∪ Φ(C3 )(H). Ekkor |E(H 0 )| = |E(H)| + |(EΦ(C3 )(H)| − |E(H ∩Φ(C3 )(H)| ≥ 2|V (H)|−5+2|V (Φ(C3 )(H)|−5−(2|V (H ∩Φ(C3 )(H))|− 5) = 2|V (H 0 )| − 5, mivel H ∩ Φ(C3 )(H) is r´eszgr´afja G0 -nek, ´es tartalmazza v1 , v2 -t ´es Φ(C3 )(v2 ), Φ(C3 )(v2 )-t. ´Igy |E(H 0 )| = 2|V (H 0 )| − 5. Hasonl´o igaz

´ MUVELETEK ˝ FEJEZET 2. HENNEBERG-T´IPUSU

17

H 00 = H 0 ∪ Φ(C3 )(H)-ra. Csakhogy H 00 invari´ans a forgat´asra, nincs fix pontja, ´es ´ıgy pontjainak ´es ´eleinek sz´ama 3-mal oszthat´o, ami ellentmond a kapott egyenl˝os´egnek. Teh´at G teljes´ıti a Laman-felt´eteleket, ´es ´ıgy az indukci´os felt´etel felhaszn´alva, valamint egy ´elfeloszt´ast v´egrehajtva k´eszen vagyunk. A (4) esetben v-t ´es k´epeit t¨or¨olve Laman-gr´afhoz jutunk, amelynek az indukci´o szerint l´etezik megfelel˝o konstrukci´osorozata, ´ıgy utols´o l´ep´esk´ent elv´egezhetj¨ uk a h´aromsz¨og-kiterjeszt´es m˝ uvelet´et. (C) ⇒ (D): Ism´et pontsz´am szerinti indukci´ot alkalmazunk. K3 eset´en a h´arom fa a h´arom k¨ ul¨onb¨oz˝o ´elb˝ol a´ll. R´aad´asul ha egy ´el a T1 f´aban van, elforgatottja legyen a T2 f´aban, m´ıg annak elforgatottja a T3 f´aban. Ezt a faforgat´asi tulajdons´agot v´egig meg˝orizz¨ uk. (Ha egy u ´j ´elr˝ol eld¨ontj¨ uk, hogy a Ti f´ahoz kapcsol´odjon, mert valamely v´egpontj´aba m´ar vezet Ti -beli ´el, akkor az elforgatottj´aba sz¨ uks´egk´epp vezet Ti+1 -beli, teh´at ez a tulajdons´ag nem ker¨ ul ¨ossze¨ utk¨oz´esbe azzal, hogy f´akat ´ep´ıt¨ unk, vagyis o¨sszef¨ ugg˝o r´eszgr´afokat.) Tegy¨ uk fel, hogy n pontig igaz az ´all´ıt´as, ´es l´assuk be V (G) = n+3-ra. A konstrukci´osorozat G-t megel˝oz˝o elem´et jel¨olje G0 . K¨ ul¨on esetekk´ent vizsg´aljuk, hogy G el˝o´all´ıt´as´ahoz mi volt az utols´o m˝ uvelet. Ha az utols´o m˝ uvelet ponthozz´aad´as, egy u ´j pont ´eleit u ´gy rakhatjuk be k´et k¨ ul¨onb¨oz˝o f´aba, hogy megn´ezz¨ uk a k´et szomsz´edj´at, ´es mivel mindketten k´et-k´et f´aban vannak benne, ki tudunk v´alasztani k´et k¨ ul¨onb¨oz˝o f´at az u ´j pont ´eleinek sz´am´ara. Ha az egyik u ´j pont ´elein´el d¨ont¨ott¨ unk, elforgatottjainak tudunk u ´gy v´alasztani, hogy fennmaradjon a fenti faforgat´asi tulajdons´ag. Ha az utols´o m˝ uvelet ´elfeloszt´as, akkor egy u ´j pont h´arom ´el´et kell k´et k¨ ul¨onb¨oz˝o f´aba beosztani. Az u ´j pont h´arom szomsz´edja k¨oz¨ ul kett˝o G0 -ben szomsz´edos volt, de a k¨ozt¨ uk l´ev˝o ´elt a m˝ uvelet sor´an t¨or¨olt¨ uk. Az u ´j pont ezen k´et r´egi ponthoz kapcsol´od´o ´ele teh´at megkaphatja a t¨or¨olt ´el t´ıpus´at. Az u ´j pont harmadik ´el´ehez k´et lehets´eges fat´ıpus tartozhat, ezek k¨oz¨ ul az egyiket m´eg biztos nem haszn´altuk el, teh´at tudunk v´alasztani minden ´elhez

´ MUVELETEK ˝ FEJEZET 2. HENNEBERG-T´IPUSU

18

megfelel˝o f´at. Az u ´j pont elforgatottjainak v´alasszuk u ´gy a c´ımk´ez´es´et, hogy fennmaradjon a faforgat´asi tulajdons´ag. Ha az utols´o m˝ uvelet h´aromsz¨og-kiterjeszt´es volt, mindh´arom u ´j pont egy-egy r´egi ponthoz kapcsol´odik, ´es itt kihaszn´aljuk, hogy v´egig fenntartottuk a faforgat´asi tulajdons´agot. Ugyanis emiatt ha az egyik u ´j ´es az egyik G0 -beli pontot o¨sszek¨ot˝o ´el t´ıpusa Ti lett, az elforgatottja Ti+1 -beli, annak az elforgatottja pedig Ti+2 -beli lesz (modulo 3 sz´amolva). Ezek ut´an vegy¨ unk egy olyan ´elet, mely k´et u ´j pont k¨ozt vezet. Ennek az ´elnek a t´ıpus´at a v´egpontjaihoz kapcsol´od´o k´et ´el t´ıpus´at´ol f¨ ugg˝oen szabadon megv´alaszthatjuk, ´es a faforgat´as szab´alyainak megfelel˝oen a t¨obbi m´ar ad´odik. Vagyis G-nek is l´etezik (C3 , Φ) 3Fa2 part´ıci´oja. (D) ⇒ (A): Crapo eredeti eredm´eny´ere Tay adott egy bizony´ıt´ast, amelyhez hasonl´o megk¨ozel´ıt´es haszn´alhat´o ennek az ir´anynak a bel´at´as´ara. Tegy¨ uk fel, hogy {T0 , T1 , T2 } egy megfelel˝o (C3 , Φ) 3Fa2 part´ıci´o. A 2.1.4 alapj´an elegend˝o tal´alni egy (G, p) ∈ R(G,C3 ,Φ) -t, ami izosztatikus. Mivel az ´elhalmaz h´arom fa uni´oja, |E(G)| = 2|V (G)| − 3. ´Igy el´eg olyan p realiz´aci´ot tal´alni, amelyre (G, p) ∈ R(G,C3 ,Φ) f¨ uggetlen. Legyen a0 = (0, 0), a1 = (1, 0) ´es a2 = ( 21 ,

√

3 ). 2

Jel¨olje Vi azon pontok

halmaz´at, melyek nincsenek benne Ti -ben. Ekkor (G, p, q) legyen a k¨ovetkez˝o: p(v) =  ai , ha v ∈ Vi ; √ 3 1  a − a = (− , ) , ha e ∈ E(T0 )  1 2 2√  2 q(e) = a0 − a2 = (− 21 , − 23 ) , ha e ∈ E(T1 )    a − a = (1, 0) , ha e ∈ E(T2 ) 1 0 A hozz´a tartoz´o R(G, p, q)-t m´odos´ıtsuk u ´gy, hogy felcser´elj¨ uk az oszlopait: a p´aratlanadik oszlopokat vessz¨ uk el˝ore egym´as ut´an (sorrendj¨ uket nem m´odos´ıtva), majd a p´arosadik oszlopokat (sorrendj¨ uket szint´en nem m´odos´ıtva). Ezut´an ha sz¨ uks´eges, cser´elj¨ uk fel a sorokat is u ´gy, hogy el˝osz¨or a T0 beli ´elek, azt´an a T1 -beli ´elek, azt´an pedig a T3 -beli ´elek sorai k¨ovetkezzenek. Ezek a m˝ uveletek nem befoly´asolj´ak a sorok ¨osszef¨ ugg˝os´eg´et, ´ıgy el´eg a kapott R0 (G, p, q) m´atrix sorainak f¨ uggetlens´eg´et bel´atni R(G, p, q) sorainak f¨ ugget-

´ MUVELETEK ˝ FEJEZET 2. HENNEBERG-T´IPUSU

19

lens´eg´ehez. Jel¨olje az e ´elhez tartoz´o sort Fe .



− 12

                1   

√

√

3 2

1 2

.. .

− 12

− √

1 2

− 12

.. .

−

−1

0

P

e∈E(G)

... .. .

3 2

3 2

.. .

√

0 .. .

−

√

−

−1

Indirekt tegy¨ uk fel, hogy

√

3 2

3 2

1 2

.. . 1

√

1 2

− 12

.. .



3 2

3 2

√

3 2

0 .. .

                  

0 αe Fe = 0, u ´gy hogy αe 6= 0 valamely

e ∈ E(G)-re. Tegy¨ uk fel, hogy αe 6= 0 valamely e ∈ T2 -re. Mivel T2 fa, ∃vs ∈ V (T2 ), P amelyre e∈E(T2 ) = C 6= 0. A 3Fa2 part´ıci´o tulajdons´agai miatt vs -nek benne kell lennie valamelyik m´asik f´aban is, tegy¨ uk fel, hogy ez T1 . Ekkor ∀e ∈ T0 -ra P (Fe )s = 0, (Fe )|V (G)|+s = 0. Az indirekt feltev´es miatt e∈E(T1 ) αe (Fe )s = P −C. Ekkor viszont a m´atrix speci´alis alakja miatt e∈E(T1 ) αe (Fe )|V (G)|+s = √ P at ebben az esetben ellentmond´asra e∈E(G) αe (Fe )|V (G)|+s = − 3C 6= 0. Teh´ jutunk, vagyis minden e ∈ E(T2 )-re αe = 0. T¨or¨olhetj¨ uk a T2 -nek megfelel˝o sorokat R0 (G, p, q)-b˝ol, ´es el´eg a marad´ekr´ol bel´atni a f¨ uggetlens´eget.

Ez

megtehet˝o a m´atrix alkalmas b´azistranszform´aci´oja ut´an a fentihez hasonl´o ´erveket alkalmazva. A k¨ovetkez˝o teend˝o (G, p, q) pontjainak szimmetrikus sz´eth´ uz´asa. Tegy¨ uk fel, hogy |Vi | ≥ 2. Mivel {T0 , T1 , T2 } egy megfelel˝o part´ıci´o, < V0 > ∩Ti nem o¨sszef¨ ugg˝o valamely i ∈ {1, 2}-re. Tegy¨ uk fel, hogy i = 2-re nem o¨sszef¨ ugg˝o, ekkor az elforgatottjaik, azaz < V1 > ∩T0 ´es < V2 > ∩T1 szint´en nem lesznek o¨sszef¨ ugg˝oek. Legyen A a < V0 > ∩T2 egy o¨sszef¨ ugg˝o komponens´enek cs´ ucshalmaza. Legyen t ∈ R, pt : V (G) → R2 , qt : E(G) → R2 a k¨ovetkez˝o:

´ MUVELETEK ˝ FEJEZET 2. HENNEBERG-T´IPUSU

20

 √ 3 1  (− t, − t) , ha v ∈ A  2 2    (1 + t, 0) , ha v ∈ Φ(C3 )(A) √ pt (v) = 3 1  ( 2 (1 − t), 2 (1 + t)) , ha v ∈ Φ(C3 )2 (A)     p(v) , k¨ ul¨onben.  √  (1 + 12 t, 23 t) , ha e ∈ EA,V1 \Φ(C3 )(A)   √    (1 + 3 t, 3 t) , ha e ∈ EA,Φ(C3 )(A)  2 2  √   3 1  , ha e ∈ EΦ(C3 )(A),V2 \Φ(C3 )2 (A)   (− 2 − t, 2√) 3 3 1 qt (e) = , ha e ∈ EΦ(C3 )(A),Φ(C3 )2 (A) (− 2 − 2 t, 2 (1 + t))  √    (− 21 (1 − t), − 23 (1 + t)) , ha e ∈ EΦ(C3 )2 (A),V0 \A   √ √   3 1  (− , − − 3t , ha e ∈ EΦ(C3 )2 (A),A  2 2    q(e) , k¨ ul¨onben. , ahol EX,Y jelenti az X ´es Y k¨oztes ´eleinek sz´am´at valamely X, Y ⊆ V (G) diszjunkt halmazokra. Ekkor (G, p, q) = (G, p0 , q0 ). Ha t0 -t v´altoz´onak tekintj¨ uk, a (G, pt0 , qt0 ) pontosan akkor line´arisan ¨osszef¨ ugg˝o (R[t0 ] f¨ol¨ott), ha minden |E(G)|×|E(G)|s r´eszm´atrix detemin´ansa azonosan 0. Ezek t0 -ben polinomi´alisak, ´ıgy azon t0 -k halmaza, amelyekre R(G, pt0 , qt0 ) sorai nem line´arisan f¨ uggetlenek, egy F variet´ast alkotnak, amelynek komplementere ha nem¨ ures, s˝ ur˝ u ny´ılt halmaz. Mivel t = 0 ∈ / F , majdnem minden t-re a m´atrix sorai line´arisan f¨ uggetlenek lesznek, azaz l´etezik t0 6= 0, amire (G, pt0 , qt0 ) keret f¨ uggetlen. Az elj´ar´ast folytatva eljutunk egy olyan (G, p, q) kerethez, amelyben minden uv ∈ E(G)re p(u) 6= p(v). ´Igy a 2.2.13 miatt (G, p) egy f¨ uggetlen szerkezet R(G,C ,Φ) -ben. 3

Vagyis a t´etelt bel´attuk.  2.2.15. Megjegyz´ es. Az el˝oz˝o t´etelhez hasonl´o eredm´enyek ismertek C∈ -re, ami a π-sz¨og˝ u forgat´as csoportja, valamint CS -re, ami a t¨ ukr¨oz´es csoportja. Sejt´es, hogy C2v -re ´es C3v -re is levezethet˝o ilyen t´ıpus´ u t´etel, de komplik´altabb m´odon. [22] Schulze eredm´enyei olyan szempontb´ol gyeng´ebbek, mint a periodikus eset hasonl´o eredm´enyei, hogy csak izosztatikus szerkezetekr˝ol sz´ol, viszont olyan szempontb´ol er˝osebbek, hogy ezek olyan szerkezetekr˝ol is inform´aci´ot

´ MUVELETEK ˝ FEJEZET 2. HENNEBERG-T´IPUSU

21

adnak, amikt˝ol nem k¨ovetelj¨ uk meg a szimmetri´at, csak ´epp mell´ekesen szimmetrikusak.

3. fejezet Fix r´ acs´ u´ es ”cone” (k´ upos) szerkezetek Ebben a fejezetben olyan R2 -beli speci´alis gr´afok merevs´eg´enek tesztel´es´ere adunk algoritmusokat, melyekhez szimmetri´ara, illetve periodikuss´agra vonatkoz´o extra felt´etelek is tartoznak.

3.1. A generikus merevs´eghez sz¨uks´eges kombinatorikus modell A szerkezet speci´alis strukt´ ur´aja miatt nem az eg´esz szerkezetet, hanem az u ´n. sz´ınezett gr´afot vizsg´aljuk a fejezet sor´an. 3.1.1. Defin´ıci´ o. Legyen G = (V, E) egy v´eges ir´any´ıtott multigr´af, tov´abb´a legyen adva egy hozz´a tartoz´o γ = (γij )ij∈E , γij ∈ Γ csoport. A (G, γ) p´art sz´ınezett gr´afnak nevezz¨ uk. Egy adott periodikus vagy szimmetrikus szerkezethez tartoz´o sz´ınezett gr´afot u ´gy konstru´alhatunk meg, hogy a pont-orbitokat ¨osszeh´ uzzuk pontokk´a, az ´el-orbitokat ¨osszeh´ uzzuk ´elekk´e, tov´abb´a a pont-orbitok ´es ´el-orbitok incidenci´aj´at megtartva az ´eleket tetsz˝oleges m´odon megir´any´ıtjuk. Ez egy v´eges gr´afreprezent´aci´oj´at adja a pont-orbitoknak ´es ´el-orbitoknak. Egy ij ∈ E 22

´ U ´ ES ´ ”CONE” (KUPOS) ´ FEJEZET 3. FIX RACS SZERKEZETEK

23

´elhez tartozzon egy c´ımke vagy sz´ın, amit u ´gy kapunk meg, hogy felemelj¨ uk az ij ´elt az eredeti gr´af egyetlen olyan ij ´el´ev´e, melynek t¨ove egy i-hez tartoz´o kiv´alasztott i reprezent´anselem. Ekkor az ij ´el feje γij j, ahol j a j v´alasztott reprezent´anseleme. Ez a γij lesz az ij ´el sz´ıne. Ez a gr´af az egyes orbitokr´ol egy-egy cs´ ucsot tartalmaz, ´es a c´ımk´ezett ´elek mutatj´ak a teljes szerkezet strukt´ ur´aj´at. Ennek a fogalomnak a bevezet´es´et az a t´eny indokolja, hogy a gr´afhoz kapcsol´od´o extra periodicit´asi/szimmetria felt´etelek miatt bizonyos cs´ ucsok k´enytelenek egy¨ utt mozogni.

3.1. ´abra. Periodikus szerkezet ´es egy hozz´a tartoz´o sz´ınezett gr´af.

3.1.2. Megjegyz´ es. Fix r´acs´ u periodikus szerkezetre Γ = Z2 ; m´ıg k ≥ 2 eg´esz ”cone” (k´ upos) gr´afra Γ = Z/kZ. 3.1.3. Defin´ıci´ o. Azokat a mozg´asokat tekintj¨ uk megengedett folytonos mozg´asoknak, amelyek meg˝orzik a cs´ ucs-´el kapcsolatokon ´es a rudak hossz´an k´ıv¨ ul az adott periodicit´asi, ill. szimmetria felt´eteleket is. 3.1.4. Defin´ıci´ o. Egy fix r´acs´ u szerkezet merev, ha az egyetlen megengedett mozg´as az eltol´as; m´ıg egy k´ upszerkezetet akkor h´ıvunk merevnek, ha az egyetlen megengedett mozg´as a k¨oz´eppont k¨or¨ uli forgat´as. 3.1.5. Defin´ıci´ o. Egy szimmetrikus/periodikus szerkezet minim´alisan merev, ha merev, de b´armely ´el-orbit r´ udjainak elt´avol´ıt´asa ut´an m´ar nem az.

´ U ´ ES ´ ”CONE” (KUPOS) ´ FEJEZET 3. FIX RACS SZERKEZETEK

24

3.2. Merevs´egi t´etelek A k¨ovetkez˝okben az ilyen t´ıpus´ u gr´afok merevs´eg´enek vizsg´alat´ahoz sz¨ uks´eges defin´ıci´ok ´es t´etelek szerepelnek. A tov´abbiakban jel¨olje n a pontok, m pedig az ´elek sz´am´at a gr´afban. 3.2.1. Defin´ıci´ o. Legyen a G ciklikus ter´eb˝ol Γ-ba k´epez˝o ρ f¨ uggv´eny a k¨ovetP P kez˝o: ρ(C) = ij∈C,el˝ore-´el γij − ij∈C,h´atra-´el γij , ahol C fix bej´ar´as´ u k¨or G-ben. 3.2.2. Defin´ıci´ o. ρ(G0 ) jel¨oli G0 Γ-k´ep´et, amit trivi´alisnak nevezz¨ uk, ha minden G0 ´altal fesz´ıtett C k¨or ρ(C) k´epe az identit´as. K¨ ul¨onben nemtrivi´alis. Jel¨olje n a G gr´af cs´ ucsainak, m pedig az ´eleinek sz´am´at. 3.2.3. T´ etel. [8] Egy generikus fix r´acsos szerkezet a hozz´arendelt (G, γ) sz´ınezett gr´affal minim´alisan merev ⇐⇒ (1) m = 2n − 2; (2) ∀ G0 nem¨ ures r´eszgr´afra, amelynek pontsz´ama n0 , ´elsz´ama m0 , ´es trivi´alis a Z2 -k´epe, teljes¨ ul a k¨ovetkez˝o: m0 ≤ 2n0 − 3; (3) ∀ G0 nem¨ ures r´eszgr´afra, amelynek pontsz´ama n0 , ´elsz´ama m0 , ´es nemtrivi´alis a Z2 -k´epe, teljes¨ ul a k¨ovetkez˝o: m0 ≤ 2n0 − 2. Azokat a gr´afokat, melyek teljes´ıtik a t´etelben szerepl˝o h´arom felt´etelt, Ross-gr´afoknak h´ıvjuk. Ha csak a (2) ´es (3) felt´etelek teljes¨ ulnek, a gr´af Rossritka. 3.2.4. Defin´ıci´ o. A 3.2.3 alapj´an a maxim´alisan merev r´eszszerkezet ´altal´anos fix r´acs´ u szerkezetben megfelel azon G-beli maxim´alis r´eszgr´afnak, ahol m0 = 2n0 − 2. Ezeket nevezz¨ uk (G, γ) merev komponenseinek. 3.2.5. T´ etel. [9] Egy generikus ”cone” (k´ upos) szerkezet a hozz´arendelt sz´ınezett gr´affal minim´alisan merev ⇐⇒ (1) m = 2n − 1;

´ U ´ ES ´ ”CONE” (KUPOS) ´ FEJEZET 3. FIX RACS SZERKEZETEK

25

(2) ∀ G0 nem¨ ures r´eszgr´afra, amelynek pontsz´ama n0 , ´elsz´ama m0 , ´es trivi´alis a Z/kZ-k´epe, teljes¨ ul a k¨ovetkez˝o: m0 ≤ 2n0 − 3; (3) ∀ G0 nem¨ ures r´eszgr´afra, amelynek pontsz´ama n0 , ´elsz´ama m0 , ´es nemtrivi´alis a Z/kZ-k´epe, teljes¨ ul a k¨ovetkez˝o: m0 ≤ 2n0 − 1. Az ilyen gr´afokat nevezz¨ uk cone-Laman-gr´afoknak. (A Ross-gr´afokkal anal´og m´odon, csak ´epp 2n0 − 2 helyett 2n0 − 1-gyel.) A Ross- ´es cone-Laman gr´afok matroidcsal´adok. [9] 3.2.6. Lemma. [8] Legyen (G, γ) egy sz´ınezett gr´af. ρ(G) trivi´alis ⇔ G minden T fesz´ıt˝o erd˝oj´ere ρ trivi´alis minden T ´altal induk´alt alapk¨orre. K¨ovetkezzenek a (k, l)-ritkas´aggal kapcsolatos alapfogalmak. ([16]) Ezek a (k, l)-ritkas´agi fogalmak a megfelel˝o matroid alapfogalmainak felelnek meg, ez indokolja az elnevez´eseket is. 3.2.7. Defin´ıci´ o. A (k, l)-ritkas´ag azt jelenti, hogy m0 ≤ kn0 − l teljes¨ ul minden r´eszgr´afra. Ha m = kn − l, a gr´af (k, l)-gr´af. 3.2.8. Defin´ıci´ o. A (k,l)-k¨or olyan gr´af, ami nem (k, l)-ritka, de b´armely ´el´et elhagyva m´ar az. Ezek mindig (k, l − 1)-gr´afok, ´es a megfelel˝o matroid k¨oreit alkotj´ak. 3.2.9. Defin´ıci´ o. A G gr´af (k, l)-b´azisa alatt olyan maxim´alis G0 r´eszgr´afot ´ert¨ unk, amely (k, l)-ritka. A defin´ıci´o megfelel a matroid b´azis fogalm´anak. 3.2.10. Defin´ıci´ o. Ha a G0 gr´af (k, l)-b´azis, ij ∈ E(G) − E(G0 ), akkor a 0(k, l)-alapk¨or ij-re ´es G0 -re az egyetlen (k, l)-k¨or G0 + ij-ben. 3.2.11. Megjegyz´ es. Egy gr´af ”(2, 3)-” tulajdons´ag´ u ⇔ Laman-gr´af. A k´es˝obbi algoritmusokhoz felhaszn´aljuk a ”pebble game”-et, amely egy egyszer˝ u ´es eleg´ans kombinatorikus m´odszer, csup´an a gr´af ir´any´ıt´as´anak megfelel˝o v´altoztat´as´at haszn´alja. A (k,l)-”pebble game” seg´ıts´eg´evel O(1) id˝o ellen˝orizni, hogy egy ij ´el fesz´ıtett-e valamely (k, l)-komponensben. O(n2 ) id˝o friss´ıteni a komponenseket, ha egy G + ij (k, l)-ritka. Tov´abb´a O(n) id˝o sz¨ uks´eges adott (k, l)-ritka gr´afra alapk¨or sz´am´ıt´as´ahoz.

´ U ´ ES ´ ”CONE” (KUPOS) ´ FEJEZET 3. FIX RACS SZERKEZETEK

26

3.2.12. Defin´ıci´ o. (Legkisebb k¨oz¨os ˝os f´aban) Legyen T r-gy¨oker˝ u fa, i, j ∈ V (T ). Ekkor i ´es j legkisebb k¨oz¨os ˝ose T -ben az a cs´ ucs, ahol az egy´ertelm˝ u i → r-´ ut ´es a j → r-´ ut el˝osz¨or tal´alkoznak. Ez O(n) el˝oprocessz´al´as ut´an O(1) id˝oben sz´am´ıthat´o. (B˝ovebben: [4].) 3.2.13. Lemma. [21] Legyen G egy gr´af, ´es tegy¨ uk fel, hogy a Laman-k¨or¨ok G-ben ´eldiszjunktak. Ekkor minden G-beli Laman-b´azisra ugyanaz az alapk¨or, ´es minden Laman-k¨or G-ben egy alapk¨or. Bizony´ıt´as: Legyen G egy Laman-b´azisa L. A matroidtulajdons´ag miatt minden Laman-k¨or egy´ uttal Laman-alapk¨or L-re, vagy el˝oa´ll k¨or elimin´aci´os l´ep´esekkel. Az ´eldiszjunkts´agra vonatkoz´o feltev´es miatt a m´asodik eset nem fordulhat el˝o, teh´at az a´ll´ıt´as igaz, mivel L-t tetsz˝olegesen v´alasztottuk.  3.2.14. Lemma. [21] Legyen (G, γ) egy sz´ınezett gr´af, ´es tegy¨ uk fel, hogy G egy (2, 2)-gr´af. (G, γ) Ross gr´af ⇔ G-ben minden L Laman-b´azisra a Lamank¨or minden ij ∈ E − E(L)-re nemtrivi´alis Z2 -k´eppel rendelkezik. Bizony´ıt´as: (G, γ) legyen a felt´eteleknek megfelel˝o. Figyelj¨ uk meg, hogy minden G-beli G0 (2, 2)-blokknak tartalmaznia kell Laman-k¨ort, ugyanis egy G0 -beli Laman-b´azis nem tartalmazhatja az o¨sszes ´elt, mert t´ ul sok van. De ha b´armely G0 (2, 2)-blokknak trivi´alis a Z2 -k´epe, akkor a r´eszgr´afjainak is az, aminek tartalmaznia kell Laman-k¨ort. Emiatt (G, γ) pontosan akkor Rossgr´af, ha minden Laman-k¨ornek nemtrivi´alis a Z2 -k´epe. M´eg azt kell bel´atnunk, hogy minden Laman-k¨or helyett el´eg csak a Laman-alapk¨or¨okre megk¨oveteln¨ unk a nemtrivialit´ast. A Laman-k¨or¨ok (2, 2)blokkok G-ben, ´es nem tartalmazhatnak kisebb (2, 2)-blokkokat. Mivel G (2, 2)-gr´af, ´ıgy a G-beli (2, 2)-blokkok k¨oz¨ ul b´armely kett˝ore igaz az, hogy vagy ´eldiszjunktak, vagy (2, 2)-blokkban metszik egym´ast. Ebb˝ol k¨ovetkezik, hogy a Laman-k¨or¨ok, amik nem tartalmaznak kisebb (2, 2)-blokkot, ´eldiszjunktak, vagyis a 3.2.13 alapj´an az a´ll´ıt´as igaz. 

´ U ´ ES ´ ”CONE” (KUPOS) ´ FEJEZET 3. FIX RACS SZERKEZETEK

27

3.2.15. Lemma. [21] Legyen (G, γ) egy sz´ınezett gr´af Γ = Z/kZ csoporttal, ´es tegy¨ uk fel, hogy G (2, 2)-k¨or. (G, γ) pontosan akkor cone-Laman gr´af, ha b´armely ´elt elt´avol´ıtva G-b˝ol Ross-gr´afot kapunk. Bizony´ıt´as: Ha l´etezik olyan ´el, melynek t¨orl´ese ut´an nem Ross-gr´afot kapunk, akkor ez a gr´af tartalmaz trivi´alis k´ep˝ u r´eszgr´afot, amely nem Lamanritka. Mivel ez az eredeti G gr´afnak is r´eszgr´afja, G nem lehet cone-Laman. Teh´at az ´all´ıt´as balr´ol jobbra ir´anya igaz. Legyen G0 egy (2,2)-blokk G-ben. Mivel G (2,2)-k¨or, G 6= G0 . Legyen ij ∈ E(G) − E(G0 ), ekkor a felt´etel miatt G − ij Ross-gr´af, teh´at G0 -nek nemtrivi´alis a Γ-k´epe. Mivel G0 tetsz˝oleges volt, az a´ll´ıt´as m´asik ir´anya is igaz.  3.2.16. Lemma. [21] Legyen G egy (2, 1)-gr´af. Ekkor a (2, 2)-k¨or¨ok G-ben ´eldiszjunktak. 3.2.17. Lemma. [21] Legyen G egy (2, 1)-gr´af, G0 pedig Laman-k¨or G-ben. Ekkor G0 -t vagy tartalmazza egy (2, 2)-k¨or vagy G0 Laman-alapk¨or. Bizony´ıt´as: Legyen L egy tetsz˝oleges Laman-b´azis. Terjessz¨ uk ki egy R (2,2)-b´aziss´a. Ha G0 ´eldiszjunkt minden (2,2)-k¨ort˝ol, akkor r´esze R-nek. Minden Laman-k¨or alapk¨or L-re n´ezve, teh´at ekkor G0 Laman-alapk¨or. Tegy¨ uk fel, hogy G0 metsz egy G00 (2,2)-k¨ort, a metszet¨ uket jel¨olje G∩ , az uni´ojukat G∪ . Mivel G0 (2,2)-gr´af, a k¨ovetkez˝ot kapjuk: 2|V (G∩ )| − 2 ≥ |E(G∩ )| = 2|V (G0 )| − 2 + 2|V (G00 )| − 1 − |E(G∪ )| ≥ 2|V (G0 )| − 2 + 2|V (G00 )| − 1 − 2|V (G∪ )| + 1 = 2|V (G∩ )| − 2. Mivel minden megfelel˝o G0 gr´af Laman-ritka, G0 ∩ G00 = G0 -t kapjuk, twh´at G0 egy (2,2)-k¨or.  3.2.18. Lemma. [21] Legyen (G, γ) egy sz´ınezett gr´af. (G, γ) cone-Laman gr´af ⇔ (1) G egy (2, 1)-gr´af; (2) minden G-beli R (2, 2)-b´azisra az ij ∈ E(G) − E(R) ´ellel kapott G0 alapk¨or b´armely ´el´et elt´avol´ıtva Ross-gr´afot kapunk; (3) minden L Laman-b´azisra G-ben a Laman-alapk¨or Γ-k´epe nemtrivi´alis.

´ U ´ ES ´ ”CONE” (KUPOS) ´ FEJEZET 3. FIX RACS SZERKEZETEK

28

Bizony´ıt´as: El´eg bel´atni, hogy minden Laman-k¨or Γ-k´epe nemtrivi´alis. A 3.2.17 alapj´an k´et t´ıpus van: amelyek nem metszenek m´as Laman-k¨ort, teh´at Laman-alapk¨or¨ok valamely Laman-b´azisra, illetve amelyek (2, 2)-k¨or¨ok r´eszgr´afjai, ezek pedig ´eldiszjunktak a 3.2.16 miatt. Ezek ut´an a 3.2.15 lemm´ab´ol megkapjuk a k´ıv´ant ´all´ıt´ast.  A k¨ovetkez˝o lemm´akhoz sz¨ uks´eg¨ unk lesz egy G-hez tartoz´o G ir´any´ıtatlan ´gy kapjuk G-b˝ol, hogy minden cs´ ucsot h´arom gr´af defini´al´as´ara. A G gr´afot u p´eld´anyban vesz¨ unk fel, ´es az ij ir´any´ıtott, γ sz´ın˝ u ´elnek megfelel˝oen beh´ uzunk az u ´j gr´afban h´arom u ´j ´elt: ik jk+γ (k = 0, 1, 2) modulo 3 sz´amolva. Ehhez tartozik egy π : G → G term´eszetes fed˝olek´epez´es, ami ik -t i-be, ik jk+γ -t ij-be viszi. A fed˝olek´epez´es defin´ıci´o szerint olyan folytonos lek´epez´es, amelyre v´eve a k´ept´er egy elem´et, annak l´etezik olyan ny´ılt k¨ornyezete, amelynek o˝sk´epe el˝oa´ll p´aronk´ent diszjunkt ny´ılt halmazok uni´ojak´ent u ´gy, hogy π minden ilyen ny´ılt halmazt homeomorf m´odon k´epez le. Ez szeml´eletesen azt jelenti, hogy a G gr´afot r´atekerj¨ uk G-re. A π −1 az i f¨ol¨otti ”fiber”, vagyis i o˝sk´epeinek halmaza. 3.2.19. Lemma. [21] Legyen (G, γ) Z/3Z-sz´ınezett gr´af, G0 ⊆ G. Ekkor ha G0 Z/3Z-k´epe trivi´alis, akkor π −1 (G0 ) megegyezik a G0 h´arom diszjunkt p´eld´any´aval. Ha G0 Z/3Z-k´epe nemtrivi´alis, akkor π −1 (G0 ) ¨osszef¨ ugg˝o. 3.2.20. Lemma. [21] (G, γ) Z/3Z-sz´ınezett gr´af. Ha G Laman-ritka, akkor (G, γ) cone-Laman-ritka. Bizony´ıt´as: A bizony´ıt´as kontrapozit´ıv m´odon t¨ort´enik, tegy¨ uk fel, hogy (G, γ) nem cone-Laman-ritka. Legyen G0 ⊆ G, ekkor k´et esetet kell megk¨ ul¨onb¨oztetni. El˝osz¨or tegy¨ uk fel, hogy G0 k´epe trivi´alis ´es m0 ≥ 2n0 − 2. A 3.2.19 miatt π −1 (G0 ) h´arom diszjunkt m´asolata G0 -nek, de ekkor ellentmond´ast kapunk, mert ekkor G nem lesz Laman-ritka. A m´asodik eset az, hogy G0 k´epe nemtrivi´alis ´es m0 ≥ 2n0 . A 3.2.19 miatt π −1 (G0 ) o¨sszef¨ ugg˝o ´es megegyezik a G0 orbitjaival, ´ıgy 3n0 pontja ´es legal´abb

´ U ´ ES ´ ”CONE” (KUPOS) ´ FEJEZET 3. FIX RACS SZERKEZETEK

29

6n0 ´ele van, ami szint´en ellentmond´asra vezet.  3.2.21. Lemma. [21] Legyen (G, γ) egy Z/3Z-sz´ınezett gr´af. Ha a G nem Laman-ritka, akkor (G, γ) nem cone-Laman-ritka. Bizony´ıt´as: A bizony´ıt´as ism´et kontrapozit´ıv m´odon t¨ort´enik. Tegy¨ uk 0

fel, hogy G nem Laman-ritka. Ekkor tartalmaz egy G Laman-k¨ort, legyen O az orbitja. Ism´et k´et esetet k¨ ul¨onb¨oztet¨ unk meg. 0

El˝osz¨or tegy¨ uk fel, hogy O h´arom p´eld´any´ u m´asolata G -nek. Ekkor π(O) 0

is egy m´asolata G -nek trivi´alis k´eppel, ami megs´erti a cone-Laman-ritkas´agot, teh´at ebben az esetben az ´all´ıt´as igaz. 0

A m´asik eset az, hogy O o¨sszef¨ ugg˝o, ´ıgy ∀γ ∈ {0, 1, 2}-re αγ (G ) ´es 0

0

ures. Legyen A = G ∩ α1 (G ). Minden p´aronk´enti αγ+1 (G ) metszete nem¨ 0

0

0

metszet izomorf A-val. Legyen B = G ∩ α1 (G ) ∩ α2 (G ). Ekkor |E(O)| = 0 0 3|E(G )|−3|E(A)|+|E(B)|. Mivel G Laman-k¨or, A ´es B is Laman-ritk´ak. ´Igy a fenti egyenl˝os´eg jobb oldala akkor minim´alis nem¨ ures A ´es B eset´en, ha A ´es B (2,3)-szorosak. Emiatt O-nak k´etszer annyi ´ele van, mint pontja. A 3.2.19 lemma miatt π(O) k´epe nemtrivi´alis, teh´at megs´erti a cone-Laman-ritkas´agot, vagyis az ´all´ıt´as igaz.  3.2.22. Lemma. [21] Legyen (G, γ) egy Z/3Z-sz´ınezett gr´af. G0 ⊆ G egy cone-Laman merev komponens ⇔ π −1 (G0 ) egy szimmetrikus (2,3)-komponense G-nek. Bizony´ıt´as: K¨ovetkezik a 3.2.20 ´es 3.2.21 lemm´akb´ol.  3.2.23. Lemma. [21] Legyen (G, γ) egy sz´ınezett gr´af, Γ = Z/3Z. (G, γ) cone-Laman ⇔ G Laman-gr´af. S˝ot, (G, γ) merev komponensei megfelelnek G merev komponenseinek. Bizony´ıt´as: K¨ovetkezik a 3.2.20, 3.2.21 ´es 3.2.22 lemm´akb´ol.  Tegy¨ uk fel, hogy G o¨sszef¨ ugg˝o, T fesz´ıt˝ofa r gy¨ok´errel. Pi jel¨oli az r-b˝ol i-be vezet˝o utat T -ben.

´ U ´ ES ´ ”CONE” (KUPOS) ´ FEJEZET 3. FIX RACS SZERKEZETEK

30

3.2.24. Defin´ıci´ o. (ρ Γ-k´epe) A ρ Γ-k´ep´et jel¨olje σij , amit defini´aljunk a k¨ovetkez˝ok´epp. El˝osz¨or sz´am´ıtsuk ki az r gy¨ok´erponthoz tartoz´o ´ert´ekeket: P P σri = jk∈Pi ,elore−el γjk − jk∈Pi ,hatra−el γjk . Ezut´an megadhatjuk a t¨obbi pontp´arhoz tartoz´o ´ert´ekeket: legyen σij = σri − σrj , ha j ∈ Pi . Ha σji -t m´ar defini´altuk, σij = −σji . 3.2.25. Lemma. Legyen (G, γ) ¨osszef¨ ugg˝o sz´ınezett gr´af, T gy¨okeres fesz´ıt˝ofa, ij ∈ E(G) − E(T ), ´es legyen i ´es j legkisebb k¨oz¨os ˝ose a f´aban x. Ha C az ij-vel vett alapk¨or T -re, ρ(C) = σxi + γij − σjx . 3.2.26. Lemma. Legyen (G, γ) ¨osszef¨ ugg˝o. L´etezik O(n + m) algoritmus annak eld¨ont´es´ere, hogy ρ(G) Γ-k´epe trivi´alis-e.

3.3. Algoritmusok Az elm´eleti h´att´er ut´an k¨ovetkezzenek a f˝o k´erd´eseket megold´o algoritmusok. ([21]) H´arom f˝o probl´em´at szeretn´enk algoritmikusan kezelni: a merevs´eg tesztel´es´et, nem merev gr´af maxim´alis merev r´eszgr´afj´anak meghat´aroz´as´at, valamint egy gr´af maxim´alis r´eszgr´afj´anak keres´es´et adott f¨ uggetlen hosszkorl´atoknak megfelel˝oen.

3.3.1. Algoritmus annak eld¨ont´es´ere, hogy ρ(G) trivi´alis-e A k¨ovetkez˝o algoritmus seg´ıts´eg´evel ellen˝orizhetj¨ uk, hogy ρ(G) trivi´alis-e. Input: (G, γ). L´ep´esek: • T gy¨okeres fesz´ıt˝o fa keres´ese. • σri kisz´am´ıt´asa ∀ i ∈ V (G)-re.

´ U ´ ES ´ ”CONE” (KUPOS) ´ FEJEZET 3. FIX RACS SZERKEZETEK

31

• ∀ij ∈ E(T )-re T -beli alapk¨or k´ep´enek sz´am´ıt´asa.

Output: Ha l´etezik alapk¨or, amelynek k´epe nemtrivi´alis, akkor ρ(G) nem trivi´alis. K¨ ul¨onben ρ(G) trivi´alis. Az algoritmus helyess´ege k¨ovetkezik a 3.2.6 lemm´ab´ol, hiszen az algoritmus ´epp egy fesz´ıt˝ofa alapk¨oreit vizsg´alja meg. Fut´asid˝o: A fesz´ıt˝o fa keres´ese O(m) id˝ot vesz ig´enybe. σri kisz´am´ıt´asa O(n) id˝o alatt t¨ort´enik. Az alapk¨or k´ep´enek sz´am´ıt´asa O(n + m) id˝oben t¨ort´enik, mert ennyi id˝ot vesz ig´enybe a fabeli legkisebb k¨oz¨os o˝s¨ok meghat´aroz´asa, ut´ana pedig k¨or¨onk´ent O(1) id˝o sz¨ uks´eges. Teh´at o¨sszesen O(n + m) id˝o alatt ´er v´eget az algoritmus.

3.3.2. Ross-gr´af merev komponenseinek meghat´aroz´asa A k¨ovetkez˝o algoritmus seg´ıts´eg´evel meghat´arozhatjuk egy Ross-gr´af merev komponenseit. Input: (G, γ). Algoritmus: A ”pebble game”-et fogjuk haszn´alni (2,2)- ´es (2,3)-ritka gr´afokra p´arhuzamosan. Kezd´esk´ent inicializ´aljuk egyenk´ent a (2,2)- ´es (2,3)-komponenseket. Ezut´an ∀ij ∈ E(G)-re: • Ha ij-t fesz´ıti egy (2,2)-komponens a (2,2)-ritka gr´afban, eldobjuk ij-t, ´es a k¨ovetkez˝o ´ellel folytatjuk. • Ha nem fesz´ıti egyik (2,3)-komponens sem, adjuk hozz´a az ´altalunk ´ep´ıtett (2,2)- ´es (2,3)-ritka gr´afokhoz is, ´es friss´ıts¨ uk a komponenseket. • K¨ ul¨onben haszn´aljuk a (2,3)-”pebble game”-et a legkisebb G0 (2,3)-blokk azonos´ıt´as´ara, ami ij-t fesz´ıti. Hozz´aadjuk G0 -h¨oz ij-t ´es kisz´am´ıtjuk a

´ U ´ ES ´ ”CONE” (KUPOS) ´ FEJEZET 3. FIX RACS SZERKEZETEK

32

Z2 -k´ep´et. Ha trivi´alis, eldobjuk ij-t, ´es a k¨ovetkez˝o ´ellel folytatjuk. • Ha nemtrivi´alis, ij-t a (2,2)-ritka gr´afhoz adjuk ´es friss´ıtj¨ uk a komponenseit. Az outputot a (2,2)-ritka gr´af (2,2)-komponensei adj´ak. A matroidtulajdons´ag garant´alja, hogy a moh´o megk¨ozel´ıt´es j´o eredm´enyt ad. Defin´ıci´o szerint egy Ross-gr´af merev komponensei pontosan a (2,2)komponensek. Az els˝o l´ep´es biztos´ıtja, hogy egy (2,2)-ritka gr´afot tartunk fent, a m´asodik ´es harmadik l´ep´es helyess´eg´et a 3.2.14 lemm´ab´ol l´atjuk, mivel u ´j (2,2)-blokkok l´etrej¨ottekor az sz¨ uks´eges, hogy nemtrivi´alis Z2 -k´eppel rendelkezzenek. Az utols´o l´ep´es pedig biztos´ıtja, hogy minden l´ep´esben friss´ıts¨ uk a merev komponenseket. Fut´asid˝o: Az els˝o kett˝o, valamint az utols´o l´ep´es o¨sszesen O(n2 ) id˝ot vesz ig´enybe az algoritmus fut´asa sor´an. A harmadik l´ep´es O(n) id˝obe telik, ´es mivel Θ(m) iter´aci´oban hajtjuk v´egre, v´eg¨ ul egy O(nm)-es, fut´asid˝ot kapunk, vagyis az algoritmus O(n3 ) fut´asidej˝ u. 3.3.1. Megjegyz´ es. Ha csak azt akarjuk eld¨onteni, hogy a gr´af merev-e, le´allhatunk az els˝o olyan ´eln´el, amit el kell dobnunk. Emiatt, mivel O(n) ´el¨ unk van, a fut´asid˝o O(n2 ) lesz.

3.3.3. cone-Laman gr´af merev komponenseinek meghat´aroz´asa Γ = Z/3Z speci´alis eset A k¨ovetkez˝o algoritmusok seg´ıts´eg´evel meghat´arozhatjuk egy cone-Laman gr´af merev komponenseit. El˝osz¨or n´ezz¨ uk azt a speci´alis esetet, amikor Γ = Z/3Z. Input: (G, γ).

´ U ´ ES ´ ”CONE” (KUPOS) ´ FEJEZET 3. FIX RACS SZERKEZETEK

33

• A kor´abban eml´ıtett G megkonstru´al´asa. • (2,3)-”pebble game” haszn´alat´aval G merev komponenseinek meghat´aroz´asa. Output: A G szimmetrikus merev komponenseinek megfelel˝o G-beli r´eszgr´af. Az algoritmus helyess´ege a 3.2.23 lemm´ab´ol azonnal k¨ovetkezik. A fut´asid˝o O(n2 ).

Γ = Z/kZ ´altal´anos eset Most tekints¨ uk az ´altal´anos esetet, vagyis legyen Γ = Z/kZ. Input: (G, γ) ´es k. Output: a (2,1)-komponensek az a´ltalunk ´ep´ıtett (2,1)-ritka gr´afban. Algoritmus: Kezd´enek (2,1)-, (2,2)- ´es (2,3)-”pebble game”. Azt´an ∀ ij ∈ E(G)-re: • Ha ij-t fesz´ıti egy (2,1)-komponens a (2,1)-ritka gr´afban, eldobjuk ij-t, ´es a k¨ovetkez˝o ´ellel folytatjuk. • Ha ij-t nem fesz´ıti egyik (2,3)-komponens sem, ij-t hozz´aadjuk mindh´arom ritka gr´afhoz, amit ´ep´ıt¨ unk, majd friss´ıtj¨ uk a komponenseket, ´es a k¨ovetkez˝o ´ellel folytatjuk. • Ha ij-t nem fesz´ıti egyik (2,2)-komponens sem, ellen˝orizz¨ uk, hogy a Laman-alapk¨ornek a (2,3)-ritka gr´afban nemtrivi´alis-e a Z/kZ-k´epe. Ha nem, eldobjuk ij-t. K¨ ul¨onben ij-t hozz´aadjuk a (2,1)- ´es (2,2)-ritka gr´afokhoz ´es friss´ıtj¨ uk a komponenseket. • K¨ ul¨onben ij-t nem fesz´ıti egy (2,1)-komponens sem. Megkeress¨ uk azt a G0 minim´alis (2,2)-blokkot, ami fesz´ıti ij-t, ´es ellen˝orizz¨ uk, hogy G0 + ij

´ U ´ ES ´ ”CONE” (KUPOS) ´ FEJEZET 3. FIX RACS SZERKEZETEK

34

Ross-gr´aff´a v´alik-e b´armely ´el elt´avol´ıt´asa ut´an. Ha igen, ij-t hozz´aadjuk a (2,1)-gr´afhoz. K¨ ul¨onben eldobjuk.

A helyess´eg bizony´ıt´asa a Ross-gr´af eset´ehez hasonl´oan t¨ort´enik a 3.2.18 lemma alapj´an. Fut´asid˝o: Minden iter´aci´o O(n3 ) id˝ot vesz ig´enybe, ´ıgy az algoritmus fut´asideje O(n5 ) lesz.

4. fejezet Matroidelm´ eleti megk¨ ozel´ıt´ es Ez a fejezet m´as szemsz¨ogb˝ol vizsg´alja a merevs´egi k´erd´esk¨ort, el˝ot´erbe ker¨ ul a merevs´eg m¨og¨ott megh´ uz´od´o matroidstrukt´ ura. Malestein ´es Theran adott egy t´etelt generikus periodikus szerkezetek minim´alis merevs´eg´er˝ol ([8]), melynek egy Shin-ichi Tanigaw´at´ol sz´armaz´o r¨ovidebb, matroidelm´eleti bizony´ıt´as´at ismertetem ebben a fejezetben ([1]).

4.1. H´anyadosgr´af Az al´abbi fejezetben a h´anyadosgr´affal foglalkozunk, amely megfelel az el˝oz˝o fejezet sz´ınezett gr´af fogalm´anak. 4.1.1. Defin´ıci´ o. [8] Egy d-periodikus gr´af alatt olyan (G, Γ) p´art ´ert¨ unk, ahol G = (V, E) egyszer˝ u v´egtelen gr´af, minden pont foka v´eges, Γ ⊂ Aut(G) ´ pedig a d-rang´ u automorfizmusok egy szabad Abel-csoportja fixpont n´elk¨ ul, v´eges sok pont-orbittal (´es k¨ovetkez´esk´epp v´eges sok ´el-orbittal). Γ a periodicit´asi csoportja vagy periodicit´asi r´acsa G-nek. 4.1.2. Defin´ıci´ o. [8] Ekkor a G/Γ = (V /Γ, E/Γ) h´anyadosgr´af az el˝oz˝o fejezetben m´ar ismertetett sz´ınezett gr´affal azonos. Legyen φ : G → G/Γ fed˝o lek´epez´es ´es ρ : H1 (G/Γ) → Γ sz¨ urjekt´ıv homeomorfizmus φ-hez, ahol H1 (G/Γ) a G/Γ els˝o homol´ogia csoportja eg´esz 35

´ ¨ ´ITES ´ FEJEZET 4. MATROIDELMELETI MEGKOZEL

36

egy¨ utthat´okkal (amely azonos´ıthat´o a G/Γ ciklikus t´errel). Minden inform´aci´o a fed˝o lek´epez´esr˝ol (´es fed˝o t´err˝ol) elk´odolhat´o G/Γ-ba v reprezent´al´o cs´ ucs fix´al´as´aval minden [v] p´aly´ar´ol. 4.1.3. Defin´ıci´ o. Egy digr´afot Γ-gain gr´afnak (el´er´esi gr´afnak) h´ıvunk, ha minden [e] ¨ossze van kapcsolva egy γ[e] elemmel a Γ csoportb´ol, u ´gy hogy ∀[e]re γ[e] = −γ[e] teljes¨ ul, ahol [e] jel¨oli [e] megford´ıtottj´at. 4.1.4. Megjegyz´ es. G/Γ gain-gr´af. 4.1.5. Megjegyz´ es.

Q

[e]∈C

γ[e] f¨ uggetlen a reprezent´al´o cs´ ucsok v´alaszt´as´at´ol

minden G/Γ-beli C k¨orre.

4.2. d-periodikus gr´af - merevs´egi bevezet˝o Jel¨olje τ (Rd ) a d-dimenzi´os euklideszi t´er eltol´ascsoportj´at. 4.2.1. Defin´ıci´ o. Egy d-periodikus (G, Γ) gr´af elhelyez´ese Rd -ben egy olyan p : V → Rd ´es π : Γ → τ (Rd ) f¨ uggv´enyp´ar, ahol p injekt´ıv lek´epez´es, amely minden cs´ ucshoz egy pontot rendel, π injekt´ıv homomorfizmusa Γ-nak, tov´abb´a p ´es π kiel´eg´ıti a periodicit´ast: ∀v ∈ V -re ´es ∀γ ∈ Γ-ra teljes¨ ul p(γv) = π(γ)(p(v)). Az ´ıgy kapott r´ ud-csukl´o szerkezet: (G, Γ, p, π). 4.2.2. Defin´ıci´ o. Egy elhelyez´es l : E → R s´ ulyokat induk´al a gr´afon: legyen l(uv) = p(u) ´es p(v) t´avols´aga. 4.2.3. Defin´ıci´ o. (G, Γ) realiz´aci´oja l s´ ulyokkal egy olyan (p, π) elhelyez´es, ami l-t induk´alja, azaz a k¨ovetkez˝o rendszer megold´asa a periodikuss´ag mellett: ∀e = uv ∈ E-re

< p(v) − p(u), p(v) − p(u) >= l(e)2 .

Az egyszer˝ us´eg kedv´e´ert γ1 , . . . , γd b´azist v´alasztva megfeleltetj¨ uk Γ-t d

Z -vel. Minden γ ∈ Γ egy´ertelm˝ uen kifejezhet˝o a k¨ovetkez˝ok´eppen: γ = Pd k k 1 d d k=1 cγ γk , ahol cγ ∈ Z. Legyen cγ = (cγ , . . . , cγ ) ∈ Z .

´ ¨ ´ITES ´ FEJEZET 4. MATROIDELMELETI MEGKOZEL

37

Minden π-nek megfeleltethet˝o egy d × d-es M ∈ GL(d) m´atrix µ1 , . . . , µd oszlopvektorokkal a k¨ovetkez˝o ¨osszef¨ ugg´es alapj´an: Pd P π(γ) = k=1 ckγ π(γk ) = dk=1 ckγ µk = M cγ . Teh´at a periodicit´as miatt p egy´ertelm˝ uen meghat´arozott, ha minden cs´ ucsp´aly´ar´ol v´alasztunk egy reprezent´al´o cs´ ucsot, ´es megadjuk a hozz´a tartoz´o pontot. ´Igy minden cs´ ucsp´aly´ara az elhelyez´esek tere azonos´ıthat´o (Rd )V /Γ × GL(d)-vel. A realiz´aci´os teret le´ır´o egyenletek rendszere a k¨ovetkez˝o: < p(γ[e] v) − p(u), p(γ[e] v) − p(u) >= l(e)2 , [e] = [u][v] ∈ E/Γ. Mivel p(γ[e] v) = p(v) + π(γ[e] ) = p(v) + M ce , ahol ce = cγ[e] , ez kifejezhet˝o az al´abbi m´odon: (∗) < p(v) + M ce − p(v), p(v) + M ce − p(u) >= l(e)2 , [e] = [u][v] ∈ E/Γ. 4.2.4. Defin´ıci´ o. A (G, Γ) l s´ ulyok melletti R realiz´aci´os tere a fenti egyenl˝os´eget kiel´eg´ıt˝o elhelyez´esek altere. 4.2.5. Defin´ıci´ o. R/E(d) defini´alja a C konfigur´aci´os teret, amely az E(d) euklideszi t´er kv´ociens tere. 4.2.6. Defin´ıci´ o. Egy periodikus szerkezetet merevnek mondunk, ha az elhelyez´ese izol´alt pont C-ben. 4.2.7. Defin´ıci´ o. A (G, Γ; p, π) periodikus szerkezet infinitezim´alis mozg´asainak tere R ´erint˝otere (p, π)-ben. Feltessz¨ uk, hogy (p, π) sima, ´ıgy differenci´al´as ut´an a k¨ovetkez˝ot kapjuk: < p(v) + M ce − p(u), p(v) ˙ + M˙ ce − p(u) ˙ >= 0, [e] = [u][v] ∈ E/Γ-ra. 4.2.8. Defin´ıci´ o. Ha p˙ kib˝ov´ıthet˝o Rd egy infinitezim´alis izometri´aj´av´a, p-t ˙ trivi´alisnak nevezz¨ uk. 4.2.9. Defin´ıci´ o. A szerkezet infinitezim´alisan merev, ha minden lehets´eges infinitezim´alis mozg´as trivi´alis.

´ ¨ ´ITES ´ FEJEZET 4. MATROIDELMELETI MEGKOZEL

38

4.2.10. Defin´ıci´ o. Az R merevs´egi m´atrix egy |E/Γ| × (d|V /Γ| + d2 )-m´atrix, amely a (∗)-hoz tartozik. 4.2.11. T´ etel. [1] (G, Γ, ; p, π) infinitezim´alisan merev ⇔ R rangja d|V /Γ| +
d2 − d+1 . 2 4.2.12. Defin´ıci´ o. Az R(G, Γ) generikus d-merevs´egi matroid a merevs´egi m´atrix sormatroidja generikus elhelyez´es mellett.

4.3. Matroidok 4.3.1. Matroidelm´eleti bevezet˝o 4.3.1. Defin´ıci´ o. Egy µ : 2E → Z f¨ uggv´enyt polimatroid f¨ uggv´enynek nevez¨ unk, ha µ(∅) = 0, µ nemcs¨okken˝o, tov´abb´a szubmodul´aris, azaz teljes¨ ul r´a a k¨ovetkez˝o egyenl˝otlens´eg: µ(X) + µ(Y ) ≥ µ(X ∩ Y )µ(X ∪ Y ). (E, µ)-t polimatroidnak h´ıvjuk. µ induk´al E-n egy matroidot, melyben azon F ⊆ E-k lesznek f¨ uggetlenek, amelyeknek minden F 0 r´eszhalmaz´ara µ(F 0 ) ≥ |F 0 | teljes¨ ul. Legyen µ ˆ(F ) = max{

P

e∈F

x(e)|x : F → R, ∀F 0 6= ∅

P

e∈F 0

x(e) ≤

0

µ(F )}. Ez nemcs¨okken˝o szubmodul´aris f¨ uggv´eny, ´es a´t´ırhat´o a k¨ovetkez˝ok´epp: P µ(F ) = min{ 1≤i≤k f (Fi )|{F1 , . . . , Fk } part´ıci´oja F − nek}. (E, µ ˆ) egy PM(µ) polimatroidot induk´al. Vezess¨ uk be a line´arisan reprezent´alhat´o polimatroidok fogalm´at. Legyen E v´eges halmaz, valamint tartozzon minden e ∈ E-hez egy Ae ∈ Rd line´aris alt´er. Vezess¨ uk be a dim : 2E → Z f¨ uggv´enyt a k¨ovetkez˝ok´eppen: dim(F ) = dim{Ae |e ∈ F }. 4.3.2. Megjegyz´ es. (E, dim) egy polimatroidot alkot.

´ ¨ ´ITES ´ FEJEZET 4. MATROIDELMELETI MEGKOZEL

39

4.3.3. Defin´ıci´ o. Ha (E, µ) polimatroid izomorf (E, dim) polimatroiddal valamely {Ae }-re, akkor az egy line´aris polimatroid. 4.3.4. Megjegyz´ es. Line´aris polimatroidok ¨osszege is line´aris polimatroid. 4.3.5. Defin´ıci´ o. Legyen A az Rd line´aris altereinek egy v´eges halmaza. Korl´atozzuk A-t egy H generikus hipers´ıkra (H = {x ∈ Rd | < a, x >= 0} valamely a ∈ Rd -re, ahol a koordin´at´ai algebrailag f¨ uggetlenek Q f¨ol¨ott). Ezt a m˝ uveletet Dilworth-csonkol´asnak nevezz¨ uk. 4.3.6. T´ etel. [13] A legyen Rd line´aris altereinek egy csal´adja, H pedig egy generikus hipers´ık Rd -ben. P Ekkor dim{A ∩ H|A ∈ A} = min{ ki=1 (dim{A|A ∈ Ai } − 1}, ahol a minimumot A minden {A1 , . . . , Ak } part´ıci´oj´an n´ezz¨ uk.

4.3.2. Matroidok ´es merevs´eg Tekints¨ uk a d-periodikus G gr´afot fed˝o transzform´aci´os Γ csoporttal, ´es a kapcsol´od´o ρ : H1 (G/Γ) → Γ lek´epez´essel. L´attuk, hogy Γ megfeleltethet˝o Zd -vel. Minden F j E-t azonos´ıtsuk F j E/Γ-val, amely az F a´ltal induk´alt G/Γbeli r´eszgr´af. Ekkor tekinthetj¨ uk H1 (F ) → H1 (G/Γ) → Γ-t, egybef˝ uz´es´et a befoglal´asnak ´es φ-nek. Jel¨olje dF a H1 (F ) k´ep´enek rangj´at Γ-ban. Tekints¨ uk a g(F ) = nF − ωF , g : 2E /Γ → Z f¨ uggv´enyt, ahol nF jel¨oli az F -beli pontorbitok sz´am´at, ´es ωF jel¨oli az F -beli o¨sszef¨ ugg˝o komponensek sz´am´at. Ez a G/Γ grafikus matroidj´anak rangf¨ uggv´enye. Vezess¨ uk be a k¨ovetkez˝o f¨ uggv´enyt: f (F ) = nF − ωF + dF , f : 2E/Γ → Z. Ez nemcs¨okken˝o, szubmodul´aris f¨ uggv´eny, tov´abb´a ∀e ∈ E/Γ-ra f (e) ≤ 1, ´ıgy induk´al egy M(f ) = (E, f ) matroidot. Bevezethet¨ unk egy m´asik G 0 matroidot is E/Γ-n, amely line´aris, ´es minden [e] ∈ E/Γ-t egy (n + d)-dimenzi´os vektor reprezent´al, amelynek els˝o n ´ert´eke a reprezent´al´o cs´ ucsokkal, utols´o d ´ert´eke pedig Γ b´azis´aval van megfeleltetve. Az uv ´elhez tartoz´o sorban a v-nek megfelel˝o poz´ıci´oban 1, u-nak megfelel˝o poz´ıci´oban -1, a t¨obbi cs´ ucs hely´en 0, γi -nek megfelel˝o poz´ıci´oban pedig ci (e) ´all. Az ezen vektorokb´ol a´ll´o, G-t reprezent´al´o m´atrixot jel¨olje R:

´ ¨ ´ITES ´ FEJEZET 4. MATROIDELMELETI MEGKOZEL

40

Ruv = (0, . . . , 0, 1, 0, . . . , 0, −1, 0, . . . , 0, c1 (e), . . . , cd (e)). 4.3.7. Lemma. A k¨ovetkez˝ok ekvivalensek G/Γ = (V /Γ, E/Γ)-ra: b´armely F j E/Γ-ra • (a) F f¨ uggetlen M(f )-ben; • (b) B´armely maxim´alis F 0 erd˝ore F -ben {ρ(C(F 0 , e)) ∈ Zd |e ∈ F − F 0 } line´arisan f¨ uggetlen Rd -ben; • (c) F f¨ uggetlen G 0 -ben. Bizony´ıt´as: (a) ⇒ (b): Ha (b) nem lenne igaz, akkor |F − F 0 | > dF valamely F 0 erd˝ore. Mivel |F | = |F 0 | + |F − F 0 | > (nF − ωF ) + df , ellentmond´asra jutunk, hiszen a felt´etel szerint |F | = f (F ) = nF − ωF + df -nek kellene teljes¨ ulnie. (b) ⇒ (c): Minden e ∈ F \F 0 -re vegy¨ uk az RF -beli sorokat ´es o¨sszegezz¨ uk. (Ahol RF jel¨oli az R F -nek megfelel˝o r´esz´et.) Az ´ıgy kapott vektorban az els˝o |V | koordin´ata nulla, m´ıg az utols´o d koordin´ata ρ(C(F 0 , e)).

Ez enek megfelel˝o sort cser´elj¨ uk le ezzel a vektorral minden e ∈ F \F -re. ´Igy 0

R megv´altozott, ´es blokkonk´ent vizsg´alhat´o. A bal fels˝o blokk F incidencia m´atrixa, ami pontosan akkor sor-f¨ uggetlen, ha F egy erd˝o. A bal k¨oz´eps˝o blokk nulla. A jobb k¨oz´eps˝o blokk tartalmazza ρ(C(F 0 , e))-t minden e ∈ F \F 0 -re, ´es ez a blokk a felt´etel szerint f¨ uggetlen. Teh´at az a´ll´ıt´as igaz. (c) ⇒ (a): Vegy¨ unk egy nem¨ ures I ⊆ F halmazt, ´es tekints¨ uk a hozz´a tartoz´o sorok r´eszm´atrix´at. A m´atrix magj´anak dimenzi´oja legal´abb (n−nF )+ (ωF + (d − dF ), ez´ert |I| ≤ n + d − [(n − nF ) + ωF + (d − dF )] = nF − ωF + dF megtartja az RF sor-f¨ uggetlens´eg´et.  ´Igy M(f ) line´aris polymatroid, amelyben minden e ∈ E/Γ megfelel egy egydimenzi´os vektort´ernek, ahol a vektorok a kor´abban eml´ıtett Re vektor αe szeresei: Ae = {(0, . . . , 0, αe , 0, . . . , 0, −αe , 0, . . . , 0, c1 (e)αe , . . . , cd (e)αe )|αe ∈ R}.

´ ¨ ´ITES ´ FEJEZET 4. MATROIDELMELETI MEGKOZEL

41

Tekints¨ uk a k´etdimenzi´os szerkezeteket: 4.3.8. Defin´ıci´ o. (G, Γ) minim´alisan merev, ha merev, de b´armely ´el-orbitj´at elhagyva m´ar nem az. 4.3.9. T´ etel. [8] (G, Γ) 2-periodikus gr´afra R(G, Γ) = M(2f − 1). Azaz (G, Γ) generikusan minim´alisan merev ⇐⇒ h´anyadosgr´afj´ara teljes¨ ulnek a k¨ovetkez˝ok: m = 2n + 1 ´es minden F j E/Γ-ra |F | ≤ 2(nF − ωF + dF ) − 1. Bizony´ıt´as: Tekints¨ uk a PM(2f ) = (E, 2f ) polimatroidot. PM(f ) = M(f ) = (E, f )-nek van {Ae } line´aris reprezent´aci´oja, ´es ´ıgy PM(2f )-nek is van, m´egpedig Ae ⊕ Ae ⊆ (R)2n+4 . Cser´elj¨ uk fel a koordin´at´ak sorrendj´et, f´es¨ ulj¨ uk ¨ossze o˝ket: az els˝o vektor i-edik koordin´at´aja ut´an a m´asodik Ae vektor i-edik koordin´at´aja k¨ovetkezzen. Vegy¨ unk egy generikus (p, π) elhelyez´est, ´es defini´aljuk a H ⊆ R2n+4 hipers´ıkot a k¨ovetkez˝ok´epp: H = {(x1 , y1 , . . . , xn , yn , z1 , w1 , z2 , w2 )|

P

[i]∈V /Γ

< p(i), (−yi , xi ) > +

P

1≤i≤d

<

µi , (−wi , zi ) >= 0}. Figyelj¨ uk meg, hogy (Ae ⊕ Ae ) ∩ H egy egydimenzi´os line´aris t´er. Teh´at R(G, Γ) megkaphat´o PM(2f )-b˝ol Dilworth-csonkol´assal. Azt kapjuk 4.3.6 felhaszn´al´as´aval, hogy: dim{(Ae ⊕ Ae ) ∩ H | e ∈ E/Γ} = P min{ i (dim{Ae ⊕ Ae | e ∈ Fi } − 1) | {F1 , . . . , Fk } part´ıci´oja F -nek} = P min{ i (2 dim{Ae | e ∈ Fi } − 1) | {F1 , . . . , Fk } part´ıci´oja F -nek} = P min{ i (2f (Fi ) − 1) | {F1 , . . . , Fk } part´ıci´oja F -nek}, ami F rangja PM(2f − 1)-ben. ´Igy R(G, Γ) = PM(2f − 1). Mivel b´armely e-re 2f (e) − 1 ≤ 1, PM(2f − 1) val´oban martoid, ´es R(G, Γ) = M(2f − 1).  A periodikus szerkezeteket u ´gy is meg lehet k¨ozel´ıteni, mint a h´anyadosgr´af elhelyez´es´et egy t´oruszon. Az el˝oz˝o fejezetben l´attunk eredm´enyeket fix t´orusz eset´ere [21], ebben a fejezetben pedig teljesen v´altoztathat´o t´oruszra

´ ¨ ´ITES ´ FEJEZET 4. MATROIDELMELETI MEGKOZEL

42

[8]. Azonban az is ´ertelmes k´erd´es, hogy mi a helyzet, ha a t´orusz r´eszlegesen v´altoztathat´o. Ezt az atomi mozg´asok id˝obeli sk´al´az´asa motiv´alja. Ha a t´orusz x-ir´anyba v´altoztathat´o, akkor l´etezik egy Henneberg-t´ıpus´ u karakteriz´aci´o. 4.3.10. T´ etel. [17] Egy sz´ınezett gr´af generikusan minim´alisan merev r´eszben v´altoztathat´o t´oruszon ⇔ el˝o´all´ıthat´o egyetlen hurok´elb˝ol gain-meg˝orz˝o Henneberg-m˝ uveletekkel.

5. fejezet Friss eredm´ enyek Az al´abbiakban szerepel n´eh´any u ´j o¨sszef¨ ugg´es, amely a 2. fejezetben ismertetett eredm´enyek ´es a h´anyadosgr´af kapcsolat´ar´ol sz´ol.

5.1. T¨uk¨orszimmetria 5.1.1. T´ etel. [22] Legyen (GS , p) t¨ uk¨orszimmetrikus generikus szerkezet. Ekkor (GS , p) pontosan akkor minim´alisan merev, ha GS (2, 3)-kritikus, nincs fix pontja, ´es pontosan egy fix ´ele van. A fix ´el felt´etel ´es a h´anyadosgr´af kapcsolata k¨ovetkezik. Jel¨olje GS a t¨ uk¨orszimmetrikus gr´afot, G pedig a h´anyadosgr´afj´at. Ha GS -nek egy fix ´ele van, akkor |VS | = 2|V | ´es |ES | = 2|E| − 1. ´ ıt´ 5.1.2. All´ as. [11] Ha GS (2,3)-kritikus ´es egy fix ´ele van, akkor G (2,1)kritikus, egy hurok´ele van, ´es teljes¨ ul ∀X ⊆ E identit´ashalmazra, hogy |X| ≤ 2|V (X)| − 3. Az ´all´ıt´as megford´ıt´asa nem igaz. ´ ıt´ 5.1.3. All´ as. [11] G (2,1)-kritikus, egy hurok´ele van, ´es teljes¨ ul ∀X ⊆ E identit´ashalmazra, hogy |X| ≤ 2|V (X)| − 3 ⇔ |E| = 2|V | − 3, G (2,2)-ritka, de ha X ⊆ E minden orbitb´ol legfeljebb egy pontot fed, akkor |X| ≤ 2|V (X)| − 3. 43

´ FEJEZET 5. FRISS EREDMENYEK

44

5.1. ´abra. P´elda arra, mikor az 5.1.2 ´all´ıt´as m´asodik fele teljes¨ ul, de az els˝o nem.

5.2. T¨uk¨orszimmetria ´es Di´eder-csoport A szimmetrikus Henneberg-m˝ uveletek sor´an az eredeti merevs´egi m´atrix ´es az orbitm´atrix rangja is meg˝orz˝odik, ´ıgy Schulze eredm´enyei ´atdolgozhat´ok a gain-gr´afok nyelv´ere. A k¨ovetkez˝o eredm´enyek err˝ol sz´olnak: Defini´alhat´o a CS t¨ ukr¨oszimmetri´ara ´es a h-hoz tartoz´o Dh Di´eder-csoportra egy ritkas´agfogalom, hasonl´oan a 3. fejezet Ross-ritkas´ag ´es coneLaman-ritkas´ag fogalm´ahoz. Tov´abb´a ebb˝ol egy ´elsz´amra vonatkoz´o felt´etellel kaphat´o a CS -szoros, illetve Dh gr´af, hasonl´oan a 3. fejezet Ross-gr´af ´es coneLaman-gr´af fogalm´ahoz. A CS -szoros, illetve Dh gr´afokra l´etezik Hennebergt´ıpus´ u karakteriz´aci´o. [6] 5.2.1. T´ etel. [6] (G, Φ) egy CS -szimmetrikus merev szerkezet h´anyadosgr´afja ⇔ (G, Φ)-nek van CS -szoros r´eszgr´afja. 5.2.2. T´ etel. [6] (G, Φ) egy Dh -szimmetrikus merev szerkezet h´anyadosgr´afja ⇔ (G, Φ)-nek van Dh -szoros r´eszgr´afja.

Irodalomjegyz´ek [1] Shin-ichi Tanigawa, A Note on the Generic Rigidity of Periodic Frameworks, (k´ezirat), (2011). [2] B. Schulze, Combinatorial and geometric rigidity with symmetry constraints, Ph.D. thesis, York University, Toronto, Canada, (2009). [3] L. Henneberg, Die Grapische Statik der starren Systeme, Leipzig, (1911). [4] D. Harel, R. E. Tarjan, Fast algorithms for finding nearest common ancestors, SIAM J. Comput., 13:338-355, (1984). [5] E. Ross, B. Schulze, W. Whiteley, Finite motions from periodic frameworks with added symmetry, International Journal of Solids and Structures 48, 1711-1729, (2011). [6] T. Jord´an, V. E. Kaszanitzky, Shin-ichi Tanigawa, Gain-Sparsity and Symmetric Rigidity in the Plane, k´ezirat, (2012). [7] T.-S. Tay, W. Whiteley, Generating isostatic frameworks, Topol. Struct. 11, 21-69, (1985). [8] J. Malestein, L. Theran, Generic combinatorial rigidity of periodic frameworks, arXiv:1008.1837v3, (2010). [9] J. Malestein, L. Theran, Generic rigidity of frameworks with orientationpreserving crystallographic symmetry, arXiv:1108.2518v2, (2012).

45

´ IRODALOMJEGYZEK

46

[10] B. Schulze, Injective and non-injective realizations with symmetry, Contributions to Discrete Mathematics, Volume 5, Number 1, 59-89, (2009). [11] Kaszanitzky Vikt´oria, k´ezirat, (2012). [12] B. Jackson, Notes on the Rigidity of Graphs, Levico Conference Notes, 22-26 October (2007). [13] L. Lov´asz, Y. Yemini, On generic rigidity in the plane, SIAM Journal on Algebraic and Discrete Methods, 3:91–98, (1982). [14] G. Laman, On graphs and rigidity of plane skeletal structures, J. Engineering Math. 4, 331-340, (1970). [15] H. Crapo, On the generic rigidity of plane frameworks, Inst. Nat. Rech. en Informatique et Automatique (INRIA), No. 1278, (1990). [16] A. Lee, I. Streinu, Pebble game algorithms and sparse graphs, Discrete Math., 308(8):1425-1437, (2008). [17] A. Nixon, E. Ross, Periodic Rigidity on a Variable Torus Using Inductive Constructions, arXiv:1204.1349, (2012). [18] Schulze, A. Sljoka, W. Whiteley, Protein Flexibility of Dimers: Do Symmetric Motions Play a Role in Allosteric Interactions?, AIP Conference Proceedings of AMMCS, (2011). [19] D. J. Jacobs, A. J. Rader, L. A. Kuhn, M. F. Thorpe, Protein Flexibility Predictions Using Graph Theory, PROTEINS: Structure, Function, and Genetics 44:150–165, (2001). [20] B. Roth, Rigid and flexible frameworks, Amer. Math. Monthly 88 (1981), no. 1, 6–21. [21] M. Berardi, B. Heeringa, J. Malestein, L. Theran, Rigid components in fixed-lattice and cone frameworks, Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, Toronto, Ontario, Canada, August 10-12, (2011).

´ IRODALOMJEGYZEK

47

[22] B. Schulze, Symmetric Laman theorems for the groups C2 and CS , The electronic journal of combinatorics, 17, (2010). [23] B. Schulze, Symmetric Versions of Laman’s Theorem, Discrete and Computational Geometry (2009), arXiv:0907:1958. [24] A. Sartbaeva, S. A. Wells, M. M. J. Treacy, M. F. Thorpe, The flexibility window in zeolites, Nature Materials 5, 962 - 965, (2006). [25] R. Conelly, P. W. Fowler, S. D. Guest, B. Schulze, W. J. Whiteley, When is a symmetric pin-joined framework isostatic?, Int. J. Solids Struct. 46, 762-773, (2009).

NYILATKOZAT

Név: Kis-Benedek Ágnes ELTE Természettudományi Kar, szak: Alkalmazott matematikus Msc ETR azonosító: KIAPACT.ELTE Szakdolgozat címe: Szimmetrikus és periodikus szerkezetek merevsége

A szakdolgozat szerzőjeként fegyelmi felelősségem tudatában kijelentem, hogy a dolgozatom önálló munkám eredménye, saját szellemi termékem, abban a hivatkozások és idézések standard szabályait következetesen alkalmaztam, mások által írt részeket a megfelelő idézés nélkül nem használtam fel.

Budapest, 2012.05.30.

_______________________________ a hallgató aláírása