43
And as
Recski
Technical Uni e si y Budapes
Depa men
o
Ma hema ics
Budapes , S oczek
u.
2-4
H-1111, Hunga y
Pa
I
o
his pape was published
in
S uc u al
Topology,
numbe
12.
La pa ie
I
de ce a icle a
B b
publibe dans
le
numB o
12
de la
e ue
Topologie s uc u ale.
F ench ansla ion:
T aduc ion ancaise
:
Jean-Luc Raymond
"11111"
'llll~l'~
ONE-STORY BUILDINM AS
TENSEGRIN FRAMEWORKS CHARPENTES
DE
TENSEGRl E
PART11
*
PARTIEII
*
DES
EDIFICES
D'UN ETAGE COMME
ABSIHACT
The minimum numbe o diagonal cables o makeaone-s o y build-
ing in ini esimally igid was de e mined in Pa
I.
The cha ac e iza-
ion o he minimum sys ems is now gi en in wo special cases:
I he unde lying g aph
is
no a ee, and i all he cables a e pa allel.
.ill.
1.
INTRODUCTION
Conside a 1-s o y building on a squa e g id, wi h he e ical ba s
ixed o he ea h ia join s. I each
o
he ou ex e nal e ical wall
con ains a diagonal, he ou co ne s o he oom become ixed.
Hence ques ions ela ed o he in ini esimal igidi y o one-s o y
buildings a e educed [2]
o
hose ela ed
o
he in ini esimal igidi y
o 2-dimensional squa e g ids whe e he co ne s a e pinned down.
Suppose a i s ha he co ne s o he g id a e
no
pinned down. I
such a g id has
k
ows and
e
columns hen
k+P-1
is he minimum
numbe o diagonal ods
o
igidi y he g id, and a sys em o
k+e-l
odsisapp op ia e i andonly i heco esponding subg aph
o he comple e bipa i e g aph
Kk,(
is a ee [2]. In wha ollows, he
wo subse s o he e ex se o
Kk,(
will be deno ed by
A
and
B
wi h
lAl=
k
and
IBl=
e.
Dans la pa ie
I,
on a ai de e mine le nomb e minimal de cilbles
diagonauxpou end e in ini esimalemen igide un edi ice d'un e age.
On donne main enan la ca ac e isa ion des sys emes minimaux
dans deuxcas speciaux
:
celui
ou
le g aphe sous-jacen n'es pas un
a b e,
e
celui
00
ous les cAbles son pa alleles.
.# i.
1.
INTRODUCTION
Conside ons un edi ice d'un e age cons ui su une g ille ca ee, ses
ba es e icales e an ixees au
sol
a
I'aide de join s. Si chacun des
qua e mu s e icaux ex e ieu s con ien une diagonale, les qua e
coins du oi son alo s ixes. Les ques ions ela i es
a
la igidi e
in ini esimale des edi ices d'un e age se eduisen donc
a
celles liees
a
la igidi e in ini esimale des g illes ca ees bidimensionnelles don
les coins son ixes au plan [2].
Supposons
ou
d'abo d que les coins de la g ille ne son
pas
ixes
au plan.
Si
une elle g ille possede
k
lignes
e
e
colonnes, alo s
k+ -l
es le nomb e minimal de igesdiagonales necessai es pou
igidi ie la g ille, e un sys eme de
k+ -l
iges es app op ie si e
seulemen si le sous-g aphe co espondan du g aphe bipa i co n-
ple
Kk,[
es un a b e [2]. Dans ce qui sui , les deux sous-ensembles
44
I we apply diagonal cables a he han ods hen connec edness o
he co esponding di ec ed subg aph is eplaced by s ong connec -
edness, and he minimum numbe becomes 2,max(k,e), see
[I,
Theo em 10,151.
I he co ne s o he g id
a e
pinned down, he minimum numbe o
necessa y diagonal ods educes
o
k+ -2 [2] and such a sys em
is app op ia e i and only i he co esponding subg aph is an asym-
me ic 2-componen o es [4]. Recall ha a 2-componen o es
wi h e ex se s
V,,
V,
o he componen s is called asymme ic i
I
Y.n
BI
.
I
(n
A
1.
Finally, i we use diagonal cables, he necessa y
minimum was p o ed
o
be
i
k=e=l
i k=e=2
i"
k+ -1 o he wise
[3]. Howe e , he p oblem o cha ac e izing all minimal in ini esi-
mally igid sys ems (i
k,
2 and
k+
2
5) seems o be open. Fo
example, he eade may
y
o
guess, which o he wo sys ems on
Figu e
4
below is in ini esimally igid. We a e going o p o e he
ollowing
wo
pa ial esul s.
Theo em
1:
Conside asys emo
k+e-l
diagonal cablesin he
kx
squa eg id
whe e he co ne s a e pinned down. Suppose he co esponding
subg aph is no a ee. Then he sys em o cables makes he g id in i-
ni esimally igid i and only i
k-e
=+1 and he co esponding sub-
g aph is
a
di ec ed ci cui wi h 2.min
(k,C)
e ices (see
Figu e
2).
Theo em
2:
Conside asys emo
k+e-l
diagonalcablesin he kx squa eg id
whe e he co ne s a e pinned down, and suppose ha all he diago-
nals a e pa allel (i.e. he o ien a ion o e e y edge is he same, say
om
A
owa ds
B).
Then he sys em makes he g id in ini esimally
igid i and only i
lN(%)I
>
.I%/
holds o e e y p ope subse %o
de I'ensemble des somme s de
Kk,?
se on designes pa
A
e
B
ou
IA~
=
k
e
=
e.
Si on applique des cables diagonaux en lieu e place des iges,
la connexi e du sous-g aphe o ien e co espondan es alo s em-
placee pa une connexi e o e, e le nomb e minimal de ien
2*max(k, ), oi
[l,
heo eme 10.151.
Si lescoins de la g ille son ixesau plan,
le
nomb e minimal de iges
diagonales necessai es es edui
a
k+e-
2 [2], e un el sys eme es
app op ie si e seulemen si
le
sous-g aphe co espondan es une
o & asy ne iquea2 composan esconnexes
[4].
Rappelonsqu'une
o &
a
2 composan es connexes don les ensembles de somme s
son
V,
e
V,es di easyme iquesiI(nBi#-/
.Iy,nA(.
IIaB b
demon e, en in, que si on u ilise des cables diagonaux,
le
nomb e
minimal necessai e es
sik=e=l
sik=e=2
F
k+ -l
au emen
[3]. Tou e ois, le p obleme de laca ac e isa ion de ous les sys emes
in ini esimalemen igides minimaux (si
k,e
2
2 e
k+
2
5) semble
Q e ou e . Pa exemple,
le
lec eu peu en e de de ine lequel des
deux sys emes de la
igu e
4
es in ini esi nalemen igide. Voici
deux esul a s pa iels don on donne a les demons a ions.
Thdo eme
1
Conside ons un sys eme de
k+e-l
cables diagonaux dans la g ille
ca ee
kxe
don les coins son ixes au plan. Si le sous-g aphe
co espondan n'es pas un a b e, alo s
le
sys eme de cables end
la g ille in ini esimalemen igide si
e
seulemen si
k-e=+l
e le
sous-g aphe co espondan es un ci cui o ien e su 2.min
(k, )
somme s ( oi la
igu e
2).
45
FIGURE
1
FIGURE
4
:(-==A
4
A
FIGURE
2
sa
1234
0
123
FIGURE
3
3
4m
lU
723
1234
&
12345
OM
46
A,
whe e
N(X)
deno es he se o hose e ices o
B
which a e
adjacen
o
a leas one e ex o
X.
2.
PROOF OF
THEOREM
1
Following he no a ion o
[3]
le
x,,
x2,
..
.,
xk
deno e he ho izon al
ansla ions o he ows and
y,, y2,
. .
.,
y,
he e ical ansla ions o
he columns. Fixing he ou co ne s o he g id means
(1) x,+x2+
...+
x,=O and
y,+y,+
...+ye=
0
[2],andadi ec ededge(i,j)
meansx,2$. Hence he di ec ed ci cui
wi h e ices, say, (x,,
y,,
x,,
y2,
...
,
xk,
yk)
means ha all he
2k
quan i ies a e equal.
Thus
x,
=
y,
=
0
o
i
=
1,
2,
.I
.,
k
by
(1)
and
yk+,
=
0
also ollows.
We mus show ha his is he only possibili y o a minimum sys em
o cables, i he co esponding subg aph G is no a ee. Since we
ha ek+e e icesand henumbe o edgesin
Gisk+C-l,i Gis
no a ee, i has
c
>1 connec ed componen s.
A i s we p o e ha hesys emcanno
bein ini esimally igidi
c>
2.
Recall ha he di ec ed edges wi hin a componen imply ela ions
among x,’s and
4’s
o ha componen only. Hence he mos one can
expec is ha all hese quan i ies a e equal o a common alue
z,
wi hin a componen G,o G. Then we s ill ha e cquan i ies zl, z,,
.
.
.,
z,
and only wo u he equa ions, namely (1). Hence he
z,’s
can be
chosen
so
ha a leas one o hem is di e en om ze o.
Thus
c=2
and one o he componen s, say G,, con ains no ci cui .
Hence i has a sou ce
s
(wi h indeg ee ze o) and a sink
(wi h
ou deg ee ze o).
Lemma
1
I a sou ce
s
and a sink
a e dis inc and hey a e in he same e ex
se
A
hen he sys em canno be igid.
ThBo Bme
2
Conside ons un sys eme de
k+C-1
cables diagonaux dans la g ille
ca ee
kxC
don les coins son ixes au plan, e supposons que
ou es les diagonales soien pa alleles (c’es -&di e que I’o ien a ion
de ou es les a e es es la meme, disons de
A
e s
B).
Alo s le
sys eme end la g ille in ini esimalemen igide si e seulemen si
IN(X)I
>
-
1x1
es alide pou ou sous-ensemble p op e Xde
A,
oh
N(X)
designe I’ensemble des somme s de
B
qui son adjacen s
A
au moins un somme de
X
2.
DEMONS^
TION
DU
THEOREME
1
Selon la no a ion u ilise dans
[3],
soien
x,,
x2,
. .
,,
xk les ansla ions
ho izon ales des lignes, e
y,,
y,,
.
.
.,
ye
les ansla ions e icales
des colonnes. Fixe les qua e coins de la g ille signi ie
(1) x,+x2+
...
+x,=O
e
y1+y2+
...
+y,=O
[2],
e unea e eo ien ee
(ill)
signi iex,>$. L’exis ence d’un ci cui
o ien 6 de somme s, disons, (x,,
y,,
x,,
y2,
.
. .
,
x,,
y,)
signi ie donc
que ou es les
2k
quan i es son egales. Ainsi
xi
=
yi
=
0
pou
i
=
1,
2,
. .
.,
k
pa
(1)
e
yk+,
=
0
s’ensui egalemen .
On
doi demon e que c’es la seule possibili e pou un sys kme
minimal de cables, si le sous-g aphe co espondan G n’es pas un
a b e. Puisqu’on a
k+C
somme s e que
le
nomb e d’a b es de G es
k
+
C
-
1, si G n’es pas un a b e,
il
possbde
c
>
1
composan es
connexes.
Dans un p emie emps, on demon e que le sys eme ne peu & e
in ini esimalemen igide si
c
>2.
II
au se appele que les a e es
o ien ees
a
I’in e ieu d’une composan e n’impliquen des ela ions
qu’en e les
xi
e les
,
de ce e composan e. Le mieux qu’on puisse
espe e es donc que ou es ces quan i es soien egales
a
une aleu
commune
z,
a I’in e ieu d’une composan e
Gi
de
G.
I1
nous es e
alo s enco e
c
quan i es z,, z2,
. .
.,
z,e seulemen deux equa ions,
47
P oo
Simply pu
x,
=
+I,
x,
=
-1
and ze o o e e ywhe e else,
o
ob ain
a de o ma ion (see
Figu e
1).
Suppose a i s ha
G,
has a single e ex
s=
only, in one o he
e ex se s, say in
A.
Then
G,
can ha e nei he sinks no sou ces in
A,
bylemma1,andi
V(G,)nB
hasasink, i canno ha eany sou ce,
o he same eason. Hence he only ci cui Co
G,mus
be di ec ed
wi h
V(C)
n
A
=
V(G,)
n
A
and all
he
poin s in
D=
B-
V(C)
mus
hen be sinks.
I
D=0,
we ob ained case (ii) o Theo em
1,
see
Figu e2.
O he wise
assign a nega i e alue
u
o e e y
xi,
,
o
C,
assign
-u
a
I
V(
C)
n
A
I
o
s
and
-u
-
1
V(C)
n
BI
/ID/
o
he poin s o
0,
o
ob ain a de o ma-
ion, see
Figu e
3.
Now
suppose ha
G1
has se e al e ices and
SEA
and
~
B.
Le
a=
1
V(G,)
n
A
1-1,
b=
I
V(G,)
n
Bl -1
and
c=
k-
a-1
,
d=
-b-
1.
We pu
xi=yi=
u2
o e e y poin in
G,,
q=yi=
u,
o e e y poin
excep
s
and
in
G1,
and
x,
=
u,
+
E,
y
=
u,
-
6.
Then all he in-
equali iesde e mined by hecablesa e me i ~,620and he ollow-
ing sys em o equa ions gi en by
(1)
is sa is ied:
(a+l)x
+
cy
=
-E
This
is
uniquely sol able o any
~,6
i
I
;;;
,
I
#O.
I he de e minan
anishes hen i is also sol able wi h
E
=
6
=
0.
(b
+
1
)x
+
dy
=
6
3.
PROOF
OF
THEOREM2
a.
Necessi y
Suppose ha
lN(X)l
I
.IXI
o some
XC
A
(X#
0;
X+
A).
We
cons uc a de o ma ion as ollows. Le
Y=
A-X.
Assign
xi=-lY
o he poin s in Xand
q=(XI
o he poin s in
K
In he o he e ex
se assign
yi=-lYl
o he poin s in
N(X)
and
yi=c
o he poin s in
celles de
(1).
Les
zi
peu en donc Q e choisis de elle so e qu’au
moins I’un d’en e eux soi di e en de ze o.
Ainsi,
c=2
e I’une des composan es, disons
G,,
ne
con ien aucun
ci cui .
II
possede donc une sou ce
s
(de deg k in k ieu ze o) e un
pui s
(de deg e ex e ieu ze o).
Lemme
1
Si une sou ces e un pui s
son dis inc s e qu’ils appa iennen au
meme ensemble desomme s
A,
alo s
le
sys eme ne peu e e igide.
Demons a ion
II
s’agi simplemen de ai e en so e que
x,
=
+1,
x,=
-1
e ze o
pa ou ailleu s, e on ob ien une de o ma ion ( oi
igu e
1).
Supposons
ou
d’abo d que
G,
ne possede qu’un seul somme
s
=
,
dans I’un des ensembles de somme s, disons dans
A.
Alo s
G,
peu n’a oi ni pui s, ni sou ce dans
A,
pa
le
Lemme
1,
e si
V( G,)
n
B
possede un pui s, il ne peu a oi aucune sou ce, pou la
meme aison. Le seul ci cui
C
de
G,
doi donc e e o ien e
OD
V(C)nA= V(G,)nA
e ouslespoin sappa enan d
D=B-V(C)
doi en alo s & e des pui s.
Si
D=
0,
on ob ien le cas (ii) du heo eme
1,
oi
igu e 2.
Au e-
men , on assigne une aleu nega i e
u
a
ous
les
xi,
,
de
C,
on
assigne-u.IV(C)nAl
as
e -u.IV(C)nBI/lDl auxpoin sde
D,
pou ob eni une de o ma ion, oi
igu e
3.
Supposons main enan que
G,
possede plusieu s somme s e
SEA
e
~
B.
Soien
a=
/V(G,)
n
A1
-
1,
b
=
IV(Gl)
n
BI
-
1
e
c=k-a-I,
d=e-b-l.
On
poseq=yi=u,pou ou poin deG2,
q=yi=u,
pou ou poin deG,sau se
,e x,=u,+~,y,=u,-6.
Tou es les inegali es dk e minees pa les cables son alo s e i iees
siE,610e
lesys kmed’equa ionssui an donnk
pa
(1)
es sa is ai :
(a+l)x+cy=-E
(b
+
1
)x
+
dy
=
6

B-N(X).
In o de
o
mee
(1)
we need
IN(X)l.
lY1=
IB-l (X)l-
c
which gi es
The condi ions
xi>
,
implied by he cables a e clea ly me
i
iE
A,
j
E
I (X).
The case
ie
X,
jE
B-I (X)
is impossible by he de ini ion o
N(X).
Hence only he case
iE
Y,
j.
B-N(X).
is
le ,
i.e.
we ha e o
p o e
CI
1x1.
Howe e , by
(2)
i is jus equi alen
o
IN(%)
2
.l%i.
b.
Su iciency
We ex end ou g aph
G
in o a la ge g aph
Go
as ollows. Le
us
conside
C
copies A,, A,,
. .
.,
A, o
A
and
k
copies
B,,
B,,
.
.
.,
B,
o
B.
The unions
A,
=
A,
u..
.
u
A and
B,
=
6,
u..
.
u
B,
o hese se s
de ine he bipa i ion o he e ex se o
Go
and he
i h
e ex
x;o
a
subse
A,
is adjacen o he
jih
e ex
&+'
o a subse
Bq
in
Go
i and
only
i
x,
is adjacen
o
4
in
G.
Bo h subse s A,and
6,
ha e ca dinali y
C.
k,
hence
Go
has a pe ec
ma ching i and only i
IN(X)I
2
1x1
o e e y
X
A,
[5].
Fo any
subse
X
o A, we de ine he in e se image
/(X)
o i as a subse o
A
so
ha
xi€
/(X)
i and only i
xp~X
o some
p.
Clea ly,
l/(X)l>
1x1
/
e
o any
X
Conside now an a bi a y subse
X
o A,. Obse e ha
IN(X)I
=
k.
IN(/(X))I
by hede ini iono
Go.
On heo he hand,
IN(/(%))l> i/(%)l
by he condi ion. Hence
IIV(X)~
=
k+ (/(x))l>
e.
I/(x)l
z
1x1,
hus
Go
hasa pe ec ma ching
M=((5,,
8,);
=1,2,
...,
k.C).
Each edge o
M
implies an inequali y
,,
I
5,
;
each quan i y $a ises
C
imes and each
,
a ises
k
imes in his se o inequali ies. Hence
he equali y
On ou e a une solu ion unique pou ou
&, i
si
I
;;;
;I
#
0.
Si
le
de e minan s'annule,
le
sys eme possede alo s aussi une solu ion
pou
E
=
6
=
0.
3.
DEMONSTRATlol
DU
WEOREME
2
a.
Necessi d
SupposonsqueIIV(X)II~IXl
pou
unce ainXcA(X# ZI;X#A).
On peu cons ui e une de o ma ion de la aqon sui an e. Soi
Y=
A-X. Posons
x,=
-1Y
pou les poin s de Xe
x,=IXl
pou les
poin s de
Y.
Dans I'au e ensemble de somme s, posons
y,
=
-1YI
pou les poin s de
N(X)
e
y,
=
c
pou les poin s appa enan
a
B-N(X).
Pou que les equa ions de
(1)
soien sa is ai es, il au que
IN(X)I
0
/YI
=
/B-N(X)(
-
c,
ce qui donne
Les condi ions
x,
z
y,
amenees pa les ciibles son clai emen e i-
iees si
ie
A,
j.
N(X).
Le cas
ie
X,
je
B-N(X)
es impossible pa
de ini ion de
I(%).
II
ne es e donc que
le
cas
iE
Y,
j.
B-N(X).
On
a donc
a
demon e que
CI
1x1.
Tou e ois, on oi pa
(2)
que c'es
equi alen
a
IN(%)I
I
-
1x1.
b.
Su isance
On e end
le
g aphe
G
en un plus g and g aphe,
Go,
de la aqon
sui an e. Conside ons
e
copies
A,,
A,,
.
.
.,
A,
de
A
e
k
copies
B,,
B,,
.
.
.,
B,
de
B.
Les eunions
A,
=
A,
u..
.
u
A, e
B,
=
8,
u..
.
u
B,
de ces ensembles de e minen une bipa i ion de I'ensemble de
somme s de
Go
e
le
i-e ne somme
x,p
d'un sous-ensemble
A,
es
adjacen au j-ieme somme JQd'un sous-ensemble
BQ
dans
Go
si e
seulemen si
x,
es adjacen
a
J
dans
G.
Les deux sous-ensembles A, e
B,
e an de ca dinali e
C.
k,
Go
pos-
sede un couplage pa ai si e seulemen si
1N(X)12
1x1
pou ou
Xc_
A,
[5].
Pou
ou
sous-ensemble
X
de
A,,
on de ini son image
49
P
k
o=k.&
I
e.Cx,=o
I
.1
/
.1
can hold only i each o he abo e inequali ies
y,,
I
5,
a e in ac
equali ies.
Lemma
2
I
IN(X)I>#IXI
holds o e e yp ope subse Xo
A hen hedele ion
o any one edge o
G
leads
o
an asymme ic 2-componen o es .
P oo
Le
e=
(x,
y)
be an a bi a y edge and le
G,, G2
be he componen s
o
G
-
e,
wi h espec i e e ex se s
V,,
V,.
Should
Iy
n
BI
=
-IynA/hold, hechoiceX= V,nAi x~V; o X= V,nAi
XEV,,
leads
o
a con adic ion.
In o de o inish he p oo , conside hose edges o
G
only whe e
equali y holds. I he esul ing subg aph
F
is he whole g aph
G
hen
he sys em is in ini esimally igid and he p oo is comple e. O he -
wise Fis a o es wi h se e al componen s
6,
F2,
. . .
and he sys em
is
in ini esimally non- igid. We show ha his is impossible.
Le
IV(F;)
n
A1
and
IV(F;)
n
BI
be deno ed by
k,
and
el,
espec i ely.
I
kl
=
.
el
o e e y
i,
we ob ain a con adic ion by Lemma
2.
O he wise he e exis s a subsc ip
i
so
ha
k,
>
.
el
holds. Then he
choice
X= V(F;)
nA
leads
o
a con adic ion.
4.
EXAMPLES AND REMARKS
a. In o de
o
illus a e Theo em
2,
conside he wo amewo ks o
Figu e
4.
The i s one is in ini esimally igid, he second one is
no . One can see his di e ence by le ing
X
be he subse o med
by he i s i e ows. Then
N(X)
is o he ca dinali y
13
in he i s
case and
12
in he second one, and
12
<y<
13.
b. The end o he p oo o Theo em
2
(Lemma
2
and he las
wo
in e se
I(%)
comme un sous-ensemble de
A
el que
xl
E
/(X)
si e
seulemen si X~EX pou un ce ain
p.
De aqon B iden e,
I/(X)l
2
1x1
/
e
pou ou
X.
Conside ons main enan un sous-ensemble a bi ai e
X
de
A,.
On
no e que
IN(X)l
=
k.
IN(/(X))I
pa de ini ion de
Go.
D'au e pa ,
lN(/(X))l>
j.
l/(X)l
pa la condi ion. Donc
IN(x)~
=
~.IN(I(X))~
>
e.
II(X)~
2
1x1
;
ainsi
Go
possede un couplage pa ai
M={(5,,
x,);
=l,
2,
. .
.,
k4.
Chaque a e e de
M
implique une inegali e
,,
I
x,,
;
chaque quan i e
5
su ien
e
ois e chaque
,
su ien
k
ois dans ce ensemble
d'inegali es. Donc, I'egali e
k
O=k.C ,
I
"&=O
I
.1
/
.1
ne ien que si chacune des inegali es ,
I
x,,
son
en
ai desegali es.
emme
2
Si I'inegali e
IN(X)l
>
.
1x1
es e i iee pou ou sous-ensemble
p op e
X
de
A,
alo s la supp ession d'une a e e quelconque de
G
mene
a
une o & asyme ique
a
2
composan es.
D6mons a ion
Soi
e=
(x,
y)
une a e e a bi ai e, e soien
G,
e
G2
lescomposan es
de
G-e,
don les ensembles de somme s son espec i emen
V,
e
V,.
Si I'egali e
I
I(
n
Bl
=
-
1
(
n
A1
e ai sa is ai e,
le
choix de
X
=
V,nAsixE V,,oudeX=
V,nA
sixEV,, mene ai aunecon adic ion.
Dans
le
bu de e mine la demons a ion, conside ons seulemen
lesa e es de
G
pou lesquelles I'egali ees e i iee. Si le sous-g aphe
esul an Fes le g aphe en ie
G,
alo s
le
sys bme es in ini esima-
lemen igide
e
la demons a ion es comple ee. Au emen ,
F
es
une o & ayan plusieu s composan es
6,
2,
.
.
.
e
le
sys eme es
pa ag aphs) can
besigni ican lysho ened.
By a heo em o He yei
[6] e e y edge is con ained in a pe ec ma ching i he Hall-
condi ion holds wi h s ic inequali y o e e y p ope subse o
A
(see also P oblem 7.7 in
[8]).
Then he connec i i y o
G
imme-
dia ely implies in ini esimal igidi y.
c.
The e a e plen y o e icien algo i hms
o
check whe he a bipa -
i e g aph has a pe ec ma ching, see [7] o example. Hence he
condi ion o Theo em
2
can easily be checked.
d. The p ope y desc ibed in Lemma 2 ( he dele ion o any one edge
eo
G
leads o an asymme ic 2-componen o es ) is necessa y
o he in ini esimal igidi ye en
i
hecablesa e no pa allel. E en
i all he cables o
G-e
a e eplaced by ods, he e a e wo ypes
o de o ma ions and one o hem is a de o ma ion o ou o iginal
sys em (see
Figu e
5).
FIGURE
5
123
12
456
w
34
Case
x,
+
y,
Cas
ou
x3
+
y,
Case
y,
+
x,
Cas
OD
~3
+
x,
in ini esimalemen lexible. On a mon e que c'e ai impossible.
Soi
lV(5)nAl
e
IV(5)nBl
ep esen es pa k, e
e,,
espec i emen .
Si
k,
=
.
e,
pou ou
i,
on ob ien une con adic ion pa le lemme
2. Au emen ,
il
exis e un indice
i
el que
k,
>
a
el.
Le choix de
X=
V(F;)nA
amene alo s une con adic ion.
4.
EXEMPES
ET
REMARQUES
a. A in d'illus e
le
heo eme 2, conside ons les deuxs uc u es de
la
igu e
4.
La p emie e es in ini esimalemen igide, la seconde
ne I'es pas. On peu oi
ce e
di e ence en designan pa
X
le
sous-ensemble cons i ue des cinq p emie es lignes.
l(X)
es
alo s de ca dinali e 13 dans le p emie cas e 12 dans
le
second,
e 12
<?<
13.
b. La in de lademons a ion du heo eme
2
(le lemme
2
e les deux
de nie s pa ag aphes) peu d e signi ica i emen kcou ee. Se-
Ion un heo eme de He yei [6], ou e a d e es con enue dans un
couplage pa ai si la condi ion de Hall es e i iee a ec des in&
gali es s ic es pou ou sous-ensemble p op e de
A
( oi aussi
le p obleme 7.7 dans
[€I]).
La connexi e de
G
implique alo s
immedia emen la igidi e in ini esimale.
c.
II
exis e un g and nomb e d'algo i hmes e icaces pou e i ie si
un g aphe bipa i possede un couplage pa ai , oi [7] pa exem-
ple. Ainsi, la condi ion du heo eme 2 es acilemen e i iable.
d. La p op ie e dec i e dans
le
lemme 2 (la supp ession d'une a d e
quelconque
e
de
G
mene
A
une o & asyme ique
a
2 compo-
san es) es necessai e
a
la igidi e in ini esimale, mdme si les
cAbles ne son pas ous pa alleles. Mdme lo sque ous les cPbles
de
G-
e
son emplaces pa des iges, il exis e deux ypes de
de o ma ions e I'un d'eux es une de o ma ion du sys eme o i-
ginal ( oi
igu e
5).
51
e.
A
de o ma ion is called elemen a y i he e exis s a bipa i ion
XuY o
A
and a cons an
c
such ha
x,
=
c.lYl
o
icX
and
x,=-c.lXl o
ieY,
and a simila condi ion holds o he
y,’s
as
well. (Tha is, only
wo
dis inc alues a ise among he x,’s and
also
wo
among he
XIS.)
The de o ma ions, illus a ed on
Fig-
u es3and5a eelemen a y.A
byp oduc o hep oo o Theo em
2
is ha i he
k+e-l
cables a e all pa allel hen he sys em is
ei he in ini esimally igid o possesses elemen a y de o ma ions.
Figu e
6
shows a sys em which is in ini esimally non- igid (see
Figu e7)
bu
hasnoelemen a yde o ma ions(asi can
beshown
by a s aigh o wa d calcula ion).
Acknowledgemen
This wo k was pa ially suppo ed by he Ins i u e u Ope a ions
Resea ch and by he Alexande - on-Humbold S i ung (Bonn,
FRG).
.11111.
e.
Une de o ma ion es di e elemen ai e s’il exis e une bipa i ion
XuY
de
A
e une cons an e
c
elles que
x,=c.lYI
pou iEXe
x,=-c.lXl pou
ieY
e elles que des condi ions similai es soien
e i iees pou lesy, aussi. (C’es -a-di eque lesx, nep ennen que
deux aleu s dis inc es, de meme que les
y,
.)
Les de o ma ions
illus ees aux
igu es
3
e
5
son elkmen ai es. La p eu e du
heo eme
2
amene
le
esul a secondai e sui an
:
si les
k+e-l
cables son ous pa all6les, alo s,
ou
bien le sys eme es in ini e-
simalemen igide,
ou
bien il possede des de o ma ions elemen-
ai es. La
igu e
6
mon e un sys kme qui es in ini esimalemen
lexible ( oi
igu e
7)
mais ne possede pas de de o ma ions
Blemen ai es (comme
on
peu le mon e pa un calcul di ec ).
Reme ciemen s
Ce e eche che a e e ealisee en pa ie g ace a des sub en ions de
I’lns i u e u Ope a ions Resea ch e de
I’Alexande - on-Humbold
S i ung (Bonn,
RFA).
.11111.
FIGURE
6
FIGURE
7