One-S o y Buildings as Tenseg i y F amewo ks
by
N.
Chak a a y,
G.
Holman,
S.
McGuinness and A. Recski
Rbum6
Topologie s uc u ale
#12, 1986
Des kli ices d’un 6 age comme cha pen es de enseg i 6
Bolke e C apo [l] on ou ni une solu ion ma o‘idale au p obkme du con e en-
emen d’un edi ice d’un age. Un des objec i s de la p sen e no e es de sume
leu s esul a s en u ilisan seulemen la h o ie des g aphes. his, la
2e
pa ie
p sen e des sul a s analogues pou des cha pen es de ens g i sp ciales
(oh
les
a e es de
la
g ille ca e son enco e des iges, mais les diagonales son des cables).
Comme
il
allai s’y a end e, il su i a d’u ilise des g aphes o ien s, bien que
I’ ude des cha pen es de ens g i , en g n al, puisse n cessi e le ecou s aux
ma oides o ien es.
Ad esses des au eu s:
N. Chak a a y, G. Holman e
S.
McGuinness:
Depa men o Combina o ics
&
Op imiza ion, Uni e si y o Wa e loo
Wa e loo, On a io, Canada N21. 3G1
A. Recski:
School o Ope a ions Resea ch
&
Indus ial Enginee ing, Co nell Uni e si y
I haca, New Yo k 14853, U.S.A.
Ma h. Ins i u e,
1..
Eo os Uni e si y, H- 1088 Budapes , Hong ie
en cong de:
Une pa ie de ce e eche che a ai e alo s que I’au eu ai p o esseu in i e
A
I’Uni e si y o Wa e loo.
Abs ac
S uc u al Topology
#12, 1986
Bolke
&
C apo
[l]
ga e a ma oidal solu ion o decide how o b ace
a
one-s o y
building. One o he aims o he p esen no e is o summa ize hei esul s using
g aph heo y only. Then, in Pa
2,
we p esen analogous esul s o special
enseg i y amewo ks (whe e he edges o he squa e g id a e s ill ods bu he
diagonals a e cables). As one can expec , di ec ed g aphs will be equi ed only,
al hough he s udy o enseg i y amewo ks, in gene al, migh need o ien ed
ma oids.
Add esses
o
he au ho s:
N. Chak a a y, G. Holman and
S.
McGuinness:
Depa men o Combina o ics
&
Op imiza ion, uni e si y o Wa e loo
Wa e loo, On a io, Canada N2L 3G1
A, Recski:
School o Ope a ions Resea ch
&
Indus ial Enginee ing, Co nell Uni e si y
I haca, New Yo k 14853, U.S.A.
Ma h. Ins i u e,
I..
Eo os Uni e si y, H-1088 Budapes , Hunga y
on lea e om:
Pa o his esea ch was done while he au ho was a isi ingp o esso a he Uni e si y o
Wa e loo.
12
Topologie
s n c u ale
#12,
1986
abc
a
1
2
Figu e
1
l e
pa ie
Figu e
2
Figu e
3
Pa
1
Soi une g ille ca e elle qu'8 la Figu e
1.
La cha pen e cons i u e de ba es e de join s
co espondan e es un mecanisme e peu le demeu e meme ap s I'addi ion de quelques
en e oises diagonales, comme c'es le cas lo sque des en e oises son ajou kes aux
posi ions
a2, bl
e
c2,
el que mon C
B
la Figu e
2.
Thh 8me
1
[
11
Soi
G,
un
g aphe bipa i ayan
la
bipa i ion
V(G)
=A
u
B,
ou
les somme s
A e
B
co esponden espec i emen aux lignes e aux colonnes de la g ille ca ke, e
o i
les
a B es co esponden aux en e oises diagonales.
Pa exemple, la Figu e
3
mon e G pou le
cas du sys me de la Figu e
2.
La
cha pen e cons i uke de ba es e de join s es igide si e
seulemen si
e
g aphe
G
co espondan es connexe.
Ape qu
de
la dbmons a ion. N'impo e quelle d o ma ion peu e compl emen
d c i e pa les ansla ions ho izon ales
xl x2,
...
des lignes e pa les ansla ions e icales
y,, yb,
...
des colonnes, el qu'illus
B
la
Figu e
4.
Un ca kco espondan
B
la
ie
ligne e
B
la
je
colonne de la g ille conse e a sa o me si e seulemen si
xi
=
yj,
comme
y,
=
x2
B
la
Figu e
4.
1.e
sys me en ie es igide si e seulemen si
x,
=
x2
=
...
=
y,
=
yb
=
...
L.es
en e oises diagonales ga an issen ceci si e seulemen si le g aphe G es connexe.
Co ollai e
2
II au au moins k
+
I
-
1
en e oises diagonalespou igidijie uneg ille ca ke
de k
x
I.
Un
ensemble dexac emen k
+I
-
1
en e oises su i si e seulemen si
G
es
un
a b e
pa iel.
Co ollai e
3
Soi
un
g oupe den e oises qui p odui
WI
sys 2me igide. Une en e oise
donnPe es
c i ique
(c'es -c -di e que sa supp ession
c ke
un
mkcanisme) si e seulemen si
la
supp ession
de
I'a B e co espondan e dans le g aphe le disjoin .
Ces dnoncCs son de simples cons quences des obse a ions p cCden es. Pa exemple, les
deux sys mes de la Figu e
5
son igides e en e men six en e oises diagonales, mais
seulemen le p emie sis e
B
la pe e d'une seule des memb u es.
I,e p incipal ksul a de
[I]
a ai aux &i ices d'un C age.
I1
es acile de cons a e qu'une
en e oise diagonale dans un mu e ical empeche les d o ma ions li es
B
un mou emen
Flgu e
5
Fi s ly, le us conside a squa e g id, as
in
Figu e
1.
The co esponding ba and join
amewo k is a mechanism and may emain
so
e en a e he addi ion o some diagonal
b aces, as is he case when b aces a e added a posi ions
a2, bl
and
c2,
as shown in Figu e
2.
Theo em
1
[I]
Le
G
be a bipa i eg aph wi h bipa i ion
V(G)
=A
u
B,
whe e he e ices
o
A and
B
co espond o he ows and o he columns o he squa e g id, espec i ely, and
edges co espond o diagonal b aces.
Fo example, Figu e
3
shows Gin case
o
he sys em
o
Figu e
2.
The ba and join amewo k is igid
i
and only
i
he co esponding g aph
G
is
connec ed.
Ske ch
o
Roo .
Any de o ma ion can ully
be
desc ibed by he ho izon al ansla ions
x,, x2,
...
o
he ows and by he e ical ansla ions
y,, yb,
...
o he columns, as illus a ed
in Figu e
4.
Asqua e,
co esponding o he
i h
ow andj h column o he g id, will main ain
i s shape i and
only
i
xi
=
y.
like
y,
=
x2
in Figu e
4.
The ull sys em is igid i and only i
x,
=
x2
=
,..
=
y,
=
yb
=
...
&e diagonal b aces insu e his i and only i he g aph G is
connec ed.
Co olla y
2
A leas
k
+
I
-
1
diagonal b aces a e equi ed o make a k
x
I
squa e g id igid.
A se o exac ly k
+
1
-
1
b aces is app op ia e
i
and
only
i
G
is
a
spanning ee.
Co olla y
3
Suppose a gi en collec ion
o
b aces yielak a igid sys em. A gi en b ace is
c i ical
(i.e. i s emo al leads o
a
mechanism)
i
and only
i
he co esponding edge
in
he
g aph is a sepa a ing edge.
These s a emen s a e simple consequences o he abo e obse a ions. Fo example, bo h
sys ems
o
Figu e
5
a e igid and con ain six diagonal b aces, bu only he i s one is
esis an o he ailu e o single membe s.
The main esul s
o
[l]
e e o one-s o y buildings. One can easily see ha a diagonal
b ace in a e ical wall p e en s hose de o ma ions o which he wall mo es along i sel .
S uc u al
Topology
#12,
1986
13
Figu e
1
Figu e
6
Figu e
10
Figu e
8
w
Figu e
9
14
Topoiogie s uc u aie
#12,
1986
du mu dans son plan. Donc deux de ces en e oises
x,
y
dans des mu s e icaux qui se
c oisen immobilisen la d oi e d’in e sec ion en en ie (Figu e
6).
Donc, si chacun des mu s e icaux ex e nes en e me une en e oise (Figu e
7),
alo s le
p oblhe de de e mine lequel de deux edi ices d’un e age es igide se Cdui au sui an :
laquelle des deux g illes ca es de la Figu e
8
es igide si leu s coins son ixis au plan? De
ou e e idence, si une elle g ille es non igide, elle n’a que des mou emen s in ini esimaux
comme
A
la Figu e
10.
Un ensemble de
k
+
I
-
1
en e oises
ou
plus, qui d e mine
un
g aphe connexe, se ai
ce ainemen su isan selon le heo he 1, mais
il
n’es pas necessai e. Des ensembles bien
choisis de
k
+
I
-
2
en e oises su i on aussi.
Thb &me
4
[2]
Soi une o P de deux composan es di e minkepa un ensemble de k
+I
-
2
en e oises, Ies classes de bipa i ion des deux composan es
GI
e
G2
i an espec i emen de
ca dinali ik, e
I,.
e
k,
e
I,.
(Donc k
=
k,
+
k2 e
I
=
I,
+
I,.)
L’ensemble den e oisesp odui
un sys ime igide si e seulemen si
k/I,
z
k2/12
z
k/l.
Pa exemple, pou lep emie sys hede la Figu e
8,
oh
k
=
4,
I=
6,
k,
=
k2
=
2,
I,
=
I,
=
3,
les
ois appo s son iden iques. Pou le second sys kme
oh
k
=
4,
I=
6,
kl
=
k2
=
2,
I,
=
2,
I,
=
4,
les ois appo s son di k en s (Figu e
9).
Ape qu de la demons a ion.
[
13
Lo sque les qua e coins de la g ille ca e son ix s, il
s’ensui que:
(1)
x, +x2+
...
+xk
=O
e
y,
+y2+
,..
+y,=O
Donc, en plus des
k
+
I
-
2
equa ions de la o me
xi
=
xi,
auxquelles co esponden les
en e oises,
les
equa ions de
(I)
son disponibles.
Suppposons que
k,/Il
=
k2/12,
e considk ons s pa men
GI
e
G,.
Si
un
x
ou
un
y
appa ien
GI,
no ons
c,
la aleu co espondan e; sinon no ons-la
c,.
Les Cqua ions de
o me
xi
=
yjson au oma iquemen sa is ai es. De plus, si
k,c,
+
k2c2
=
I,cl
+
12c2
=
0
e
cI
z
0
ou
c2
z
0,
alo s la solu ion de
(1)
es non i iale, c’es -&-di e qu’une de o ma ion es
ob enue.
D’au e pa , considi ons le sys he d’iqua ions
S,
cons i u des Cqua ions de
(1)
e des
k
+
1
-
2
equa ions de o me
xi
=
yj
d’un sous-sys be
(2).
Si
S
a une solu ion non i iale,
alo s les ec eu s des lignes de la ma ice de coe icien s
M
de
S
son IinCai emen
d pendan s. Considi ons une elle combinaison lineai e non i iale des ec eu s des
lignes. Soien
A
e
p,
les coe icien s des lignes co espondan
a
(1).
Quels que soien les
au es coe icien s,
il
s’ensui que
Ak
=
-PI,
puisque chaque ligne de
(2)
a exac emen deux
en Ces non nulles, une pou x e une pou y. Lo sque la meme discussion es CpC Ce pou
les blocs de
M,
qui co esponden aux deux composan es
GI
e
G,,
il s’ensui que
kl/Il
=
k2A2
=
k/I.
Hence wo such b aces
x,
y
in in e sec ing e ical walls ix he whole line o in e sec ion
(Figu e
6).
Thus,
i each ex e nal e ical wall con ains a b ace (Figu e
7)
hen he p oblem o
de e mining, which o he wo one-s o y buildings is igid, educes
o
he ollowing: Which
o he wo squa e g ids
o
Figu e
8
is igid i hei co ne s a e ixed o he plane? Ob iously,
i such a g id is non- igid, i has in ini esimal mo ions only, as in Figu e
10.
A se o
k
+
I
-
1
o mo e b aces, de e mining a connec ed g aph, would ce ainly be
su icien by Theo em 1, bu is no necessa y. App op ia e se s o
k
+
I
-
2
b aces will
also do:
Theo em
4
[2]
Le 's
se
o
k
+
I
-
2
b aces de e mine a 2-componen o es . Le he
bipa i ion-classes o he wo componen s
GI
and
C2
be o ca dinali y k, andl,, andk, and
1,.
espec i ely. (Hence k
=
k,
+
k2 and
I
=
I,
+
12)
The se o b aces leads
o
a igidsys em i and
onIy i k,/Il
z
k2/12
z
k/I.
Fo example, in he i s sys em o Figu e
8,
whe e
k
=
4,
I
=
6,
k,
=
k2
=
2,
I,
=
1,
=
3,
he
h ee a ios a e he same. Fo he second sys em whe e
k
=
4,
I
=
6,
k,
=
k2
=
2,
I,
=
2,
I,
=
4,
he h ee a ios a e all di e en (Figu e
9).
Ske ch
o
P oo .
Obse e
[
13
ha ixing he ou co ne s o he squa e g id means ha
(1)
x,+x,+
...+
xk=O
and
y,+y,+ ...+y,
=O
Thus,
in addi ion o he
k
+
I
-
2
equa ions o he o m
xi =xi,
e lec ed by he b aces, we
ha e he equa ions o
(1).
Suppose
kl/Il
=
k2/12.
Conside
G,
and
G,
sepa a ely. I an
x
o
y
belongs o
GI,
le i s
co esponding alue be
c,,
o he wise le i be
c2.
The equa ions o o m
xi
=
yj
a e
au oma icallysa is ied. Fu he mo e,i k,c,
+
k2c2 =l,c,
+
12c2
=Oandc,
zOo c,
zO hen
we ha e a non i ial solu ion o
(I),
i.e. a de o ma ion is ob ained.
On he o he hand, conside he sys em
S
o equa ions, consis ing o he equa ions o
(1)
and he
k
+
I
-
2
equa ions o o m
xi
=
yj
o
a
subsys em
(2).
I
S
has a non i ial solu ion
hen he ow ec o s o he coe icien ma ix Mo
S
a e linea ly dependen . Conside such
a non i ial linea combina ion o he ow ec o s and le
A
and
p
be he coe icien s o he
ows, co esponding
o
(1). No ma e wha he o he coe icien s a e, we ob ain
Ak
=
-PI,
since each ow o
(2)
has exac ly wo nonze o en ies, one o an
x
and one o a
y.
Repea ing he same a gumen o he blocks o
M,
co esponding o he wo componen s
GI
and
G2,
yields
kl/ll
=
k2A2
=
k/I.
2e
pa ie
S uc u al
Topology
U12,
1986
15
Pa
2
La sui e de ce e no e o mule les analogues des hio nes
1
e
4
pou les g illes ca 6es
a ec clbles diagonaux.
D’abo d,
il
es
ii
no e que dans le cas des clbles, leu di ec ion es impo an e.
I1
se a
dCmon 6 que la p emik e cha pen e de ensCg i 6 de la
Figu e
11
es igide (les iges e les
clbles son ep ksen s espec i emen pa des lignes pleines e poin ill es) alo s que la
seconde cha pen e ne l’es C idemmen pas
(Figu e
12).
Pa conskquen le mod le e a appel
a
des g aphes o ien is.
I1
au se appele que les
lignes e les colonnes de la g ille co esponden espec i emen aux ensembles de poin s
du
bas
e
du hau
du g aphe bipa i
(Figu e
3).
Pou les deux cha pen es de la
Figu e
11,
une
a e e se a o ien ke
e s le hau
si le clble co espondan es en posi ion
sud-oues /no d-es ,
e
e s le
bas
s’il es en posi ion
no d-oues /sud-es
(Figu e
13).
I1 au aussi se appele qu’un g aphe o ien 6 es di
o emen connexe
si pou ou e pai e
de somme s
u,
il exis e un chemin o ien 6 de
u
e s
e un au e de
e s
u.
Thh he
5
[3]
Une cha pen e de ensig i i es igide si e seulemen si le g aphe o ien &
co espondan es o emen connexe.
Dkmons a ion.
Assignons
xi
un signe posi i si les a es ho izon ales du hau des
ca ks de la ligne
i
se d6placen e s la gauche (pa appo aux a C es du bas), e un signe
nega i au emen . De
la
mCme acon, assignons un signe posi i
a
yj
si les a e es du ca 6
d oi des cads de la colonnej se dkplacen e s le hau (pa appo aux a es du ca 6
gauche), e nega i au emen . Alo s un clble en aine une inkqua ion xi
z
yj
s’il
y
a une
a e e o ien & de
i
e s
j,
e
xi
I
y,
si l’a e e es o ien 6e de
j
e s
i.
S’il
y
a dans le g aphe un chemin o ien 6 P,,allan du somme
u
au somme
,
alo s ou es
les inCgali Cs, qui co esponden aux a e es de
Pu ,
on la meme di ec ion. S’il es possible
de ou e un au e chemin
P,,
allan de
a
u,
alo s ou es les in gali ks se ans o men en
Cgali Cs. Pa exemple,
il
decouledes chemins o ien is
(1,
b,
2)e (2,
a,
1)du p emie g aphe
de la
Figu e
13
que x,
2
yb
5
x2
2
yo
2
x,.
Donc la o e connexi 6 du g aphe o ien 6
implique la igidi 6 de la cha pen e.
ab
ab
In he es o his no e we o mula e he analogues o Theo ems
1
and
4
o squa e g ids
wi h diagonal cables.
Fi s o all obse e ha in case
o
cables, hei di ec ion is o impo ance.
We
shall see ha .
he
i s
enseg i y amewo k o
Figu e
11
is igid ( ods and cables a e deno ed by
con inuous and do ed lines, espec i ely) while he second amewo k
is
ob iously no
(Figu e
12).
Hence we shall use di ec ed g aphs in ou model. Recall ha ows and columns o he
g id co esponded o he
lowe
and
uppe
poin se s o he bipa i e g aph, espec i ely
(Figu e
3).
Le us o ien and edge
up
i he co esponding cable has a
Sou hwes -No heas
posi ion and
down
i i is in a
No hwes -Sou heas
posi ion
(Figu e
13)
o he wo
amewo ks o
Figu e
11.
Recall ha a di ec ed g aph is called
s ongly
connec ed
i o any wo e ices
u,
he e
exis s a di ec ed pa h om
u
o
and ano he om
o
u.
Theo em
5
[3]
The enseg i y amewo k is igid i and only
i
he co esponding di ec ed
g aph is s ongly connec ed.
P oo .
Le
us
assign a posi i e sign o
xi
i he uppe ho izon al edges o he squa es o
ow
i
mo e o he le ( ela i e o he lowe edges), and a nega i e sign o he wise. Simila ly,
le
yj
be posi i e i he igh hand side edges o he squa es o column
j
mo e upwa ds
( ela i e o he le hand side edges) and nega i e o he wise. Then a cable means an
inequali y xizyji he e is an edge di ec ed om
i
ojand xi
5
yji he edge
is
di ec ed om
j
o
i.
I he e is a di ec ed pa h
P,,,
in
ou
g aph om e ex
u
o e ex
hen all he inequali ies,
co esponding o he edges o P,,,, ha e he same di ec ion.
I
ano he pa h
P,,
om
o
u
can also be ound hen all he inequali ies a e me by equali y. Fo example, he di ec ed
pa hs(l,b,2)and(2,a, 1)in
he i s g apho Figu e13meansx,zybzx,zy,zx,.
Hence
he s ong connec edness o he di ec ed g aph implies igidi y o he amewo k.
MI4
12
12
Figu e
11
Figu e
12
Flgu e
13

16
Topologie
si uc u ale
#12,
1986
Si le g aphe o ien 6 n’es pas o emen connexe, alo s I’ensemble des somme s du g aphe
peu S e decompose en deux pa ies elles que ou es les a e es soien o ien es de la
seconde pa ie e s la p emi e. Assignons une pe i e (mais Cgale) aleu aux a iables xe
y
co espondan aux somme s de la p emii e pa ie, e une plus g ande aleu commune
au es e.
Cecid e mineuned o ma ionde
lacha pen e. Pa exemple,~,
=
yo<o<x2 =yb,
oh
xI
=
-x2
e
yo
=
-yb
d c i la de o ma ion mon ee a la
Figu e
12.
Ceci co espond
?i
la
decomposi ion
{
1,
a}
u
{2,
b}.
I he di ec ed g aph is no s ongly connec ed hen he e ex se o he g aph can be
decomposed in o wo pa s
so
ha e e y edge is o ien ed om he second pa owa ds he
i s pa . Assign smalle (bu equal) alues o he
x
and
y
a iables, co esponding o
e ices o he i s pa and a g ea e common alue o he es . This de e mines a
de o ma ion o he amewo k. Fo example,
xI
=
yo
<
0
<
x2
=
yb,
whe e
xI
=
-x2
and
yo
=
-yb
desc ibes he de o ma ion shown on
Figu e
12.
This co esponds o he decompo-
si ion
(1,
a)
u
{2,
b).
Co ollai e
6
[3]
I1
au au moins
2 max(k,
)
cables diagonaux pou igidi e une g ille
Ca ie de
k
x
1.
Dhons a ion.
Supposons que I’ensemble de poin s
du bas
comp e
a
=
max(k,
I)
somme s e que celui
du hau
comp e
b
=
min(k,
I)
somme s. Pa sui e de la o e connexi e,
chaque poin
du
bas
doi comp e une a e e o ien e qui ien e s lui e au moins une a e e
o ien ee qui s’ loigne de
hi.
Puisque le g aphe es bipa i,
il
ne peu exis e deuxpoin s
du
bas
adjacen s. Pa cons quen ces
2a
a k es son ou es di k en es. La
Figu e
14
mon e
que ce e limi e es ne e, c’es -&di e que ce nomb e de cables es oujou s su isan .
Rema que.
L,es en e oises diagonales, sans & e des cables, peu en aussi e e plus
iables en ac ion qu’en comp ession. Pa consequen , si deux en e oises diagonales
pe pendiculai es son u ilis es au lieu d’une seule dans ce ains ca s, alo s
il
au
2(k
+
I-
1)
en e oises selon le co ollai e 2, soi p esque deux ois I’op imum donn pa le
co ollai e
6.
Finalemen , consid ons un edi ice d’un &age de aille k
x
I.
Supposons que les qua e
mu s e icaux ex e nes soien igides (g ace a une ige
ou
deux clbles chacun).
I1
su i
alo s de p end e en consid a ion une g ille ec angulai e de k
x
I
don les qua e coins
son ixes au plan. Combien au -il de cables diagonauxpou en elimine les mou emen s
in ini simaux?
Thb he
7
[4]
Soi
k,
I?
2
e
k
+
12
5.
Alo s il au au moins
k
+
I
-
1
c ibles diagonaux
pou igidpe le sys ime.
Dhons a ion.
Si un ensemble de cables igidi ie un sys he, la subs i u ion de iges
A
ces cables ne peu pas d ui e la igidi e. Pa consequen , d’ap is le h o ime
4,
moins de
k
+I-
2clbles ne peu en su i e. De la meme aqon, s’il exis ai un sys ime ayan k
+I-
2
cables, le g aphe
G
co espondan de ai & e une o &
a
deux composan es
oh
kl/ll
#
k2/12 (c . hko ime
4
pou la no a ion). L.es deux composan es
GI
e
G2
de
G
on
chacune au moins une sou ce e au moins un pui s.
Si une des classes de bipa i ion de
G
en e me
a
la ois une sou ce
s
e un pui s
,
alo s
assignons une aleu de
+I
As,
de
-1
A
e de
0
A
ous les au es somme s. Ceci d e mine
une de o ma ion de la cha pen e.
Co olla y
6
[3]
A
leas
2 max(k,
)
diagonal cables a e equi ed
o
make a
k
x
I
squa e
g id igid,
P oo .
Suppose ha he
lowe
poin se has
a
=
max(k,
I)
e ices and he
uppe
one has
b
=
min(k,
I)
e ices. E e y
lowe
poin mus ha e an edge o ien ed owa ds i and a leas
one edge o ien ed away om i , by he s ong connec i i y. Since he g aph is bipa i e, no
wo
lowe
poin s can be adjacen . Hence hese
2a
edges a e all di e en .
Figu e
14
shows
ha his bound is sha p, i.e. ha his numbe o cables is always enough.
Rema k.
Diagonal b aces (no cables) may also be mo e eliable unde ension han
unde comp ession. The e o e i one applies wo pe pendicula diagonal b aces, a he
han jus one o hem, in some squa es hen 2(k
+
I
-
1)
b aces would be needed by
Co olla y
2;
nea ly wice as many as he op imum, gi en by Co olla y
6.
Finally, le
us
conside a k
x
I-sized one-s o y building. Suppose ha he ou ex e nal
e ical walls a e igid (by using one od o wo cables in each). We need only conside
a
k
x
I
ec angula g id wi h all he ou co ne s ixed o he plane. How many diagonal
cables can p e en i s in ini esimal mo ions?
Theo em
I
[4]
Le
k,
I?
2
and
k
+
12
5.
Then a leas
k
+I
-
1
diagonal cables a e equi ed
o
make he sys em igid.
P oo .
I a se o cables makes a sys em igid, changing he cables o ods canno des oy
igidi y. Hence less han k
+
I
-
2 cables canno be enough, by Theo em
4.
Simila ly, i
he e we e a sys em wi h k
+
I
-
2 cables, he co esponding g aph
G
should be a
2-componen o es wi h k,/ll
#
k2/12 (see he no a ion
in
Theo em
4).
Bo h componen s
GI
and
G2
o
G
ha e a leas one sou ce and a leas one sink each.
I one o he bipa i ion classes o
G
con ains bo h a sou ces and a sink
hen assign he
alues
+
1
o
s,
-
1
o
I
and
0
o all he o he e ices. This de e mines a de o ma ion o he
amewo k.
S uc u al Topology
#I2,
I986
17
Si
ou es les sou ces son dans
la
classe de bipa i ion
A
e ous les pui s dans
B,
alo s soi
s
unesou cede GI e soi unpui sde G2.
Assignonsune aleu dex-~~Pse dexA ousles
au essomme sde Gl;puisdey-yoP e deyP ouslesau essomme sde G2. Cesys kme
sa is ai aux inkgali b si
xo
>
0
e
yo
<
0,
e sa is ai aussi
P
(1)
si
se b i ie. hisque la ma ice es non singulih e,
il
es possible de ou e des aleu s
con enables
pou
x
e
y
si
xo
e
yo
son ixks. Pa conskquen une dk o ma ion de la
cha pen e es ob enue.
Finalemen ,
il
au dkmon e que
k
+
I
-
1
cables peu en igidi ie un sys bme. Soi
k
I
I.
Considk ons le g aphe de la
Figu e
15,
c'es -Pdi e le sys kme mon C
P
la
Figu e
16.
Supposons que
les
quan i ks
xl, x2,
...,
xk;
yI,
y,,
..,,
yl
sa is on
P
k
I
i=
1
j=
1
X
xi=O
e
P
yj=O
e
xisyl
pou
1
cisk-
~;y,
5xk;e xk~y,pou 2Ij~ .
Amoinsqu'elIesnesoien ou esnulles,le
seul cas possible es que
xi
5
yI
<
0
<
xk
5
yj
(pou ou
1
5
i
5
k
-
1
e
2
5
j
5
I).
Pa
conskquen
k k-
I
i=
I
i=
I
0
=
x
xi
=
xk
+
P
xi
5
xk
+
(k
-
1)yl
=
xk
yI
+
(k
-
2)yl
Donc,
si
k
2
3,
alo s de
k
k
I
xk+yl+(k-2)yl<xk+yl
+
y.c
z
yjs
X
y'=o
j=3
J-pl
j=I
J
il
dkoule une con adic ion.
Si
k
=
2
e
I
>
2,
alo s de
I
j=
I
Xk
+
+
(k
-
2)yl
=
X2
+
I
+
y2
<
yj
=
0
il
dkcoule enco e une con adic ion.
I all he sou ces a e in he bipa i ion classA and all he sinks in
B
hen le
s
be a sou ce o
GI and
be
a
sink o G1. Assign he alues
x -xo
os and
x
o e e y o he e ex o GI; hen
y
-yo
o
and
y
o e e y o he e ex o G2. This sys em sa is ies he ineql ali ies i
xo
>
0
and
yo
<
0,
and
also
sa is ies
(1)
i
holds. Since he ma ix is nonsingula , we can ind sui able alues o
x
and
y
i
xo
and
yo
a e ixed. Hence we ob ain a de o ma ion o he amewo k.
Finally we ha e o p o e ha
k
+
I
-
1
cables can lead o a
igid
sys em. Le
k
5
I
and
conside he g aph o
Figu e
15,
i.e. he sys em shown on
Figu e
16.
Suppose ha he
quan i ies
xI, x2,
..-,
xk;
yI,
y2,
...,
yl
sa is y
k
I
i=
1
j=
I
P
xi=O
and
X
yj=O
and
xiiyl
o
Isilk-
l;y,
~xk;andxk~y~ o
21js .
Unlessallo hema eze o, heonlypossible
case is
xi
5
yI
<
0
<
xk
syj
( o e e y
1
I
i
I
k
-
1
and
2
S~I
I).
Hence
k
k-
I
0
=
z
xi
=
xk
xi
I
xk
(k
-
1)yl
=
xk
+
yI
+
(k
-
2)yI
i=l
i=
1
Thus, i
k
2
3
hen
k kI
x&
YI
+
(k
-
2)yl
<
xk
+
YI
+j53
yj
sj51
uj
';. i
yj
=
leads o
a
con adic ion. I
k
=
2
and
I
>
2
hen
I
j=
1
Xk
+
(k
-
2)yl
5
X2
Iyl
+y,
C
)'j
=
0
again a con adic ion.
Y,
Y2
Y3 Y4
Yl
x1
x2
x3
xk-l
xk
Figu e
14
Figu e
IS
18
Topologie
s uc u ale
#12,
1986
Rema que. Ce e de nie e k ape dkmon e que ce e cons uc ion n’es pas alide pou
k
=
I
=
2 (Figu e
17).
Rema k. This las s ep
shows
ha he cons uc ion ails o
k
=
I
=
2 (Figu e
17).
Figu e
17
Rb b ences
-
Re e ences
[l] E.D. Bolke
&
H. C apo,
“How
o B ace a One-S o y Building?”, En i onmen and
Planning B, 4 (1977) 125-152.
[2] H. C apo, “Mo e on he B acing o One-S o y Buildings”, En i onmen and Plan-
ning B, 4 (1977) 153-156.
[3] A. Recski,
Ma oid Theo y and
i s
Applica ions,
Sp inge Ve lag, Be lin and AkadC-
miai Kiadb, Budapes , o appea .
[4]
N.
Chak a a y,
G.
Holman
&
S.
McGuinness, p ojec s epo shappo s de p oje s,
Uni e si y
o
Wa e loo, 1984.