View of Free sets associated to a finite oriented graph

MA,THEM.{IICA

--

^REVUE D'ÂN¿.I,YSE NUIì4ÉRIQUE

Eî

DE TIIÉORIE DÞ I]"{,PPROXIMÁ'IIÑ

L'ANÂIYSE

_NUMÉRIOUE

ET LA TÏIÉORIE DE

L,APPROXIMATION Torne 10,

¡e L lgLl, pp.5Z_7i '

FREB SETS ASSOCIATED TO A FINITE _ORIENTED

GRAPH

by

nÄnu¡

M,q.Rcu (Bucharest)

58 ^{DÄNUT MARCU} 2

trVe

call

incid.ence

rnøtrix

(see

[5]) of ^the

^{graph G,}

^{thc matrix} Â:

: (^;) :1,2, ...,þ; h:1,2, ...,q, defined

as follows:

L'o: l, if n,: _L

^*(an)

+

L-(ah),

-1, if n¿: _{A-(a,,) + A}

^*(øh),

0,

otherwise.

3 ^{FREE SETS} ¡,SSOCr¡.ie¡ To A FTNITE ORTENTED GRAPH

59

rt

was

in [7]

as

weil that

we have _defined

the notion of

minirnar*

related to a nåouir r.tnrp"".

"rÀr';i ^gx, and, *À-

,nãi"ä that any

nonulr

vector x e

se

is of the form x : f x, ^with x, e lp, minimal

related.

to lf and Vr= X for any i : l,Z,'l

. .,

*.

As to a vector X:É x,b,e

^u)(,

we may say it ^js

elementøry _as

äinotTur,t; *

,'L." " ^{minimal related to}

^{1ße and-}

^{x, =} {-1,0, l}

^ror

fn ilTl

^rve

particularized 9t to VLq,Rl _and lf to Ker ¡

^orland

rmV,

we

provedihat

any

nonrril'o""tor'i ='K";A"i, ^{äi tn" form} : ':

å *,", with

ø.,

e [! - ^{{0} and X,}

elementary related

to Ker 7\,

^and.

any nonull

vector

y e fm V is of the form y :i,p,p, _with

g,

=R_{0}

(2.2).

spaces.

¡Er¡r'rrroN 3.r. r,et us

consider %,

as a

space

of finite

dimensions

andEitsbases.Asets

= ^&, s,;Øi;said io b;,rr;; îåråî"¿ to a

nonult

#'fåï _-lJtul: ^{ir anJoniv} ií iã'^äì"'v nonud x ₌

^x,

with s(x) c

e R e m a r

k 3'1'^one" can presently notice that if ß is free

and

ecß, e+Ø thenerslree.

l. If

incl_usion

^g c of _úl

setsi

ls frec

zøith reløtetl.

tiis--pr"prrty^.îa*o,o= to

Ker

7\

^ønd.

møximat ,\î,

^then,(as que Xth)

e _Ker [,

elementøry, so that yrot

:,

6o

+ È

^{'*y, ;"',}

witk xlt ^e _{-1,0, t}. ^oo'ï

Proof.

If a" e g\8,

then, having

in

view

the maximality of ï,

the set s.

lJ

{a")

is

iro _longèr

it"ã t"r"t"lä _{5", a ; that}

_means

_that

_{there is}

x - ^Ker'Ä, x a o*.øtr.ã(ð-;; U-{i¡^fs,) ^-" *'-'

Taking

into

account. (2.2),

it

means that

X :io",X, *ith - ^{{0}, X,}

elementary

in Ker ¿\

^anð.

X,tr X for

all

i:1,2,

I

we

shall denote

by vp., Rl,

(see [17'l) the set of

the

linear forms

x with

4

as bases and R as value range (we denote by

rl

the field of the real num-

c

bers),

X :D,xoø',

_h:1

_{x*= R,}

_where

!a, ^{is the vector with all}

^tine

^xo:e,

except lor xr: -l-1 and

0u

the vector with all t]¡e xo:Q.

Similarly,

we

define

the vector

speace

z[*, R]

as consisting

in

^al1

the

vectors of

the form Z :Dz¡/t¡,

þ

_{z¡e R,}

_lvhere 0¿¿

is the

vector

rvith all z¡:0

^anð.

¡:l

!n,

^_rs

^the vector xcept for z¡: 11

practically, Z[ú1,

R] is

Ra and

To the

above

d the

following applications

will

be attached (see

l17l) : _{Rl, V:V} [;, ^RJ

^--+

^T/ls.,Iì]

^defi-

ned

by _A(X) :

Ð(Ð,"r.r

^.%¿,

v(z):å(å^r ^{,,) .oo,}

^where

i:

qþ

X : _Ð

xn&p

e _Vlg,,Rl

and.

Z :Dzrn¡€ Z[:ìÌ, R].

þ:t i:1

Out of the definitio's of the functions 7\ ^and V,

^results

the

fact

Þq

that ¡

^(oo)

:Ðnr"o, lè:1,2, ...,q

anð,

y(n,) : Dnïoo,i:7,2,...,þ

which

means

that I ^arrd V ^{are two}

hornomorphisms betrveen

v[9,fl]

and' V

t

^,

^R].

They have as

a matrix for

linear transfornration,

the

inci- dence

matrix of the

graph G

: {

,

&),

aud according

to _[lS] it

^means

that dim Vle,Ilrl:

dirn

Ker I f

^(dinr

Im[

=- dim

Im¡) or:

- q:

dinr

Ker ¡ f

frank

(^)

_{=r dim}

Ln V]

^(2.1),

where

I(er ¡ : {X e _{[jt, R]lV(X)} :

0u.] and.

Im V :

_{V(V [e¿,}

_R])

t17 l).

ector

space

of the finite

dimensions

and It the values

range,

and,

sub- reord.er

relation ,,E",

^whef

e X É Y

d s-(X) - ß-(Y), with &*(X) :

"

^{I xo}

10l¡, ^8(X) : ß*(X) _{U ß-(X),}

andX: D

_i:l ^{x,boe %,.} only if X ^* a vector is nonull, x e ,. c æ, is,saicr _"rg to be min,irnq,r relatecr to a nonurl subspace r,f of Ø, if ancl

""aùr-"oy'"ï"ä ^{w,-'w¡th s)(y)} cs(X), we,trave o, 4 ^1p.

4¡€ Iì -

., %.

60 DÃNIJT MARCU

But if X.=X, then, 4(Xr) . s(X) and

acco¡d.ing

to the

relation 3.1. we have

û.(X,) g C U

{øo},

which

means

that

Xn,

being

elernentary,

is of the form X¡:

^{xÍl a¡}

* Ð ^{x!) an, with x!)} - {-

^1,

^0, 1}

^and

4d*

xft ₌ {-1, ^l}.

fi x[ót:O, then, g(X,) c {, i.e. í is not free

related'

to Ker 7\;

contradiction rvith the

^above hypothesis.

ff there exists io = {1,2, ...,nt}, so that x["]: l, ^then

^{we take}

NtÊl

:

Xa,.

But, iÎ xYl: - I for all i : ^{1,2, ..}

^.,

^{rn, we}

consid,er the vectors

X; : -Xr, i:1,2, ^{...,vtt, which} are obviously

elementary

in Ker 7\

^(see

^(1.21) irr _[17]) ^and for which g6;) _{ç s U {an}}

_{Lor every}

i:1,2, ...,m.

O1 course,

there

exists now

io u _{1,2, ...,rn} ^lor

which

x¡Íiol

- ^{1 and}

^we

^{take Xtn} :

Xi".

So, it exists

Xtht

-

^øo

^{1-'L xltao,}

elementary

in Ker ¡. ¿s¡

^us

n o-&

prove now

that f,trl

is unique. To

this

purpose

let

us consider

X ^{e Ker} A,

elementary,

with e(ft) ₌ ï _l)

_{øo}

of the form Î :

^an

*Di,o".

Since Ker

7\ ^{is a linear}

^subspace,

^{there result.} tl" îj=Jt that

fr.

- -

^{XÍht belongs}

^{to Ker A, which}

^means

^that

_oo*l

| ^(i. -

^{*|f;t) øo}

^{e KeÍ A.}

As ø(.Ë

- ^{Xrh\ c} s

^{and. E. is free related.}

to Ker

_¿\,

it

rneans

that X =

^XVI

(Q.E.D.).

Let us

consid.er

Þ: lg\.&l

^and

^{let us}

^re-mark

^{the set 4}

^as

^follow:

A,: _{Vy

Vn,..

.,

^V

o, ^Ur, Ur,

^{. .}

.,U;} :

{c¿t, Ø2, . .

.,

^øo}, where

Zo=g\9, a.: 1,2, ...,h,, and Ug. ff, I : ^{l, 2, ...,nt', witlt} * :

^q

-Ã.

Rem ark

^3.2.

Having in view the

theorem

3,1, it

means

that

for

I ^FREB SBTS.ASSoCIATBD TO A ^pfNrTB oRTBNTED CRApfÍ 6t

.Proof

. r,et x

be a vector

of Ker 7\.

^According

to the

r,vay re-marked.

the set

ú[,

it

means

that X: É

_e-t

^frnVn*

_0:r

^f.*rUo,withxn,rBeR, ø:

:1,2, _{... h;} g: 1,2, ...,rn,

using the

courponents

of the vector x we

define

the

vector

ø'

X-ft:ÐxøUr_.

_xoxrt

\- ;

¿-J 0==r

h

xs

- \

ø:l

^x"xf;l

4

lrÀ1*

X: D

_d'-l

^xoXtøt:

_e:t

D xnVnlD Ð"."å'

_{c=r Flr}

,, lo h,-

uu:Ðxsus_

ÐÐxnxftur:

hn

¿-l 0:l

ÐÐ

U

vecto¡ for which

rve have :

u ø. ^(3.2)

r.Xi: 0s, it

results

ihat 0e is nul1 vector of

the

any

d.=

{1,2,...,h}, ^the¡e

^exists

^{an uniqus} f,tcJ:Voi

mentary

in Ker 4 with xf) e {-1,0,

^1}.

Dr)Fr\.rrTroN 3.2.

Let lX,bealinearspaceoverR

and.

(Xr,Xr, ...,Xn)

a vector

system

of

9[. \Me

call the system (Xr,Xr, ...,X*) ø

systerne

of

generøting uectors

of

_"X,,

iÎ any vector X ^e

^%,

can be

expressed, as ^a

linear

combination

of

these vectors

i X:f,rr*, 'r'ith z, ^eF., X¡ e

_"X,,

'i:1,2,...,h.

Tr¡EOIìÐM

3.2. The

Uectors

Xtrtx\2t,...,xtal,

ma,h,e

uþ a

^{systern oJ}

generating aectors

of

tke sþøce

Ker [.

. ^But, 6 - h ⁼ I*r A ^{and taking} into

account

the relation

(S.2)

it

means

that

8"(X

- ^,ï) ₌ ^{Ur,

^(Jr,

..l,Ur}: s.

Since g.

is a

free set related

to Ker A, it

^results

^that X _ i :

^O*.

b

So,

X: _D xdXtut.

(eIì).D.).

a:1

DEFTNTTToN

3.3. L"t ^{gj be} a lirrear

space

over lì, ancl (Xr, Xr,

. . .

..., X"> a vector

systern

of fi. Thc systeln (Xr, Xr, ...,

Xu)

is

lineetr incleþendent

if

for any

null

linear cornbirration

f

r¡:0, ,i:1,2, ...,n,

r,vhere ,.¡

€ R

andi:l space 9[.

DgrrrNrl.roN 3.4.

l..t

^gl.

be a linear

space

ovcr R

and.

(Xr, Xr,

. . .

..., Xn) a vector

system

of fr.

^,I.he system

(Xr, Xr, ..., X,> is a

^bases

of the

space g[

if and only if (Xr, Xr, ...,

Xu>

"orrrtit.rt", ^{a linear}

^inde_

pendent systern

of

generating vectors

of the

space ^g[.

THDOnltrÙr S.S. 'fhe _uectors

XItl,

Xtz),

..., Xút

reþ.resent

ø linear

ind,c_

þend.ent system

in

tke sþøce Ker

[.

,n

L'rå"'uB,

^ele-

p:1

62

Proof

. I.el ^rtf,ttt I

^rrXtzt

¡

nation

of the

vectots Xttl,

Xl2t,

- . .

we

obtain'

^l

8, : _r1V1*

,r.*ltt

Ut I

^rrxf,ttUr

l- I

^rrl/

, )- ,r*Í') U, ¡

rrxf,"t(I, -1-

-¡ r"V¡lrtxr tu,¡rr*fiU" +

^.

: rrVl I ^rrV, + ... ¡

^r-¡V

¡ I

h

Y ¡xlt

(f ,,*:i'\u,J-...*

\Fr

^I

DÀNUT l"fARCU

'.. I r¡Xh:8s ^{a null linear}

^combi-

,

Xtu. Having in

view

the

remark 3.2'

+

_'\tlLDt'

r.*t!u- +

+

tþiilrfl'

r.*!t(l- ⁺

l,/¡ I

x

Z ^{FREìI SurS} ASSOCTATED To A FTNITE ORTENTED GRAPH

6J

/¿, we can say

that the

dimension of the subspace Ker

7\ is

^equar

to

E, i,e.

space

Ker

_A

,

^u'hich

is

made

up of the vectors

XUl, Xt2l, . .

.,

^{yrat. ,Ihese}

vectors are uniquely

determined related.

to the

set

E s _{rl flgl} : _tn :

A), which

is

_{maximal (as compared}

_{to the}

_{inclu_}

sion

of

sets) rvith

_ Practically, th

_bases

for

Ker

¡ ^{is to find.} a

set

iå,i;'lï ;Tli:"i :

^r,

2,, u,o,,o*lä*'3,1lx*:*{ ^{j ä*"} :;':

RemarkS.T.I,et's

_co'sid.er

{ ^cû., free related to _fm !

^and

maximal

with this

propertv.

Bv

means ot

ã tn"oiÀ; ;;bgr"s to

the theo_

rerrr

e

_frn 3.1,

V,

\\¡e elerncntary, can pro\¡e

so that that if

^{&n '"}

e o.'.. g,

then there

is

an unique \ztÀJ e

\tt\ ^'-,¿o ₊

_uooü

_D

),'"!tao,

with ljale {-1,0,

^1}.

ft

_¡eLr.a¡

:i and

re-marking

the set d so that g: _{{Wr,Wz, ...}

...,W;, Tr, Tr, ..,, T';j :

_{ør, &2,

. .,

eo},WB

e

úI...

g,

_p

: 1,2, ...,s

and

1, ^e î, æ:1,2, ..,,/, with z:

q

_

_{s, we}

_{obtai' the}

_{vector unique}

systerr <Ytlt,Y,t2),...,Y1"r¡ \¡ith ^yr0l - ^We+ É y:ot.f", u,ith

^{,,1pt u}

= {-1,0,

_l},.-P

:1,2,...,.s. This vecto, ,y{"L: can be

proved.,

by

a

reasouing similar to

that

rrade iu the theorenr.

g.z.

_a:rcl

8.3. to

constitrrte

a

basis

for the

space

fm !

^and.,

thus,

dirn

Im V -: _s.

_1a.2.¡.

'Iakirrg into

account

the relations

(8.6), (8.7)

and

_1Z.t¡

we get: q:

:

À

+

^s and considering the

fact

that m

:

q

- ^{n und,i\} q-

s,

it res'lts that m:

^S- ând

r :

/t. and, thus,

&.

: _{W1,1(r,

_.

_.,,1A¡, Tr, Tr, .. ., T¡}

:'{Vr, _Vr, ...,Vu,Ur.,Ur,...,U;}:

_{or,a¿,

_...,aq}.

₍₃₈₎

.

R e rn a

r k

3.8.

practically speaki'g, the d.eterrninatio' fo a

^basis

fol the

subspace

frn !,

^{goes down}

upon the

discorrery

of a

set

î c

^ê1,

I¡ee

related to rrr V anã iriaxirnal

"iit' tt, ¡;.;"r,n

^Ãccording

^{to it,}

the

construction

of the

vectors

yrtl, ylzl,

_{. . .,y1,,1}

uniquply

determined as

compared

to &, is i'rediate if

^.,r,e har¡e

i' mi.d the

remàrk S.7.

6

-f /¡ U;:

1

5-

_lJ1

jt U

D

^{I ¡X-U U (3 3)}

Denoted

by

^co¡

:þr,*:tt, i - ^1,2, " ',1n,

^ttn'd'

^taking i.to

^{account the}

relation (3.3) .té ãbt"itt: ^0* : 1'rVrl rrl/r¡ "' ^{+ r¡Vn} I ^orUr f I

^clr(J, _-nu-t,

+ .. -i tt;U-'

^(3.4)

{lt/r, I/r, ..., Vi, Ur, Ur, ..., (l-} -- {o', &2,

^'

', ao): &,

^anð

having in 'rild ^{that t"} ii a

bases o1

Vlt,Iìl it

^means

^that

^{the system}

-¿i:,:/r,

...,v k,(Jr,tJr, ...,u¡) ^{is lineàr} itrclepe.dent and from

(3'4) r

¡e

have

: /t: 1'z --

r

h or :

^cù¿

=

- (ù* 0'

^(3'5)

Thtrs, iÎ rrXttt I

r"Xtzt

+

^.

^.

1-

rlxtht - ^{gs, theu, having} in

view

(3.5) ,

it

^lneatìs

^that

^{the vectors}

^X[ll,

^{.YL2 l,}

...,

Xthl

rriakc up

a linear inde-

pcrrdcrt

^systcrn

in Kcr A ^(Q.Il.ll.)

R ^e nr a

r k

3.3.

I{avirrg iu mincl tirc

theorems 3.3,

3.2, and

taking irrto

ì".o""t ^the

definitiorr"3.4,

it ne¿'s

^{th¿it th.e}

vectors

Xltt,

Xlzl, ..

'

. .

.,

^Xtt¡)

form up a

bases

of the

slrace

I(er !'

r)ttr¡rNrTroN

3.5 A liuear

space

I is

considcred'

to

^harre

^the

^d'inteto'

si,on

n

iT:

a)

there exists

in this

space

a

system

with n linear

ind.epeud.ent vec-

tors

^('rt'

is a nonull

^{integer) and}

b) every vector

^system

of tr which

contains rnore

than ø

r¡ector ^1s

not liircar

iúd.ependent,

better to

say

it is

I'ineør d.eþen'dent.

R e m

ar k 3.4.'we can also add the fact that the

dimension

of

^a

space

*

reprezents

the

rnaximal number

of linear

ind'ependent ltectors of

this

sp:Lce.

R e rn a

r k.

3.5.

Flaving in

^ÛiintL

^the

^rernark

^3.3.

^and

^{the fact that}

if

^{a linear spoce}

"dmits a bisis rvjth

^r¿ vectors,

theu it

has

the

dimension

64 ^{DÄNUT M1\RCU}

I

R ^e m ^a

r k

3.9. F'rom

the

above rneutioned.

thns

r¡'e

notice that if I ^c t is free

related.

to Ker ¡

^and.

^maximal with this property,

then,

lïl:m: ^dimlmy : rauk (Â),

and.

if I ^c

^Û,

is free related to Im

_Ç

and rnaximal with this property, then ï : h:

^d.im

Ker ¡.

T,DMMA 3.1.

If ^& c

& _{is free} velated' fo

Ker L,

^{tken there exists}

{ã-&,

free

rel,ated,lo

Ker ¡

^{a.ncl møxirnal}

^uith,

^tkís þroþerty, ^so thøt ã"

- ^{ã.

Proof

. I,et õ c & be

free related.

to Ker [. ff ^{õ is}

nr.aximal, then we

take Oã,: *

^and.

the

theorem

is

proved.

ff õ is not

maximal,

then there

exists

at

least

an arc ¿ e 4\ õ

so

that

ã,

U {¿} to

be

further on

free related.

to Ker [

^.

Since

ã c &

^and. & is

finite, it

means

that there

exists

a finite

num-

berof arcs,bethem &:{or,,&í,,...,or,},ã -g\ã, ^{so that ã,¿A}

to be

free related

to Ker ¡ ^{and for any ø €} 4\(ã _{U A), the} set õ

_[J

U g _{U {ø}}

_has

_{no longer} this property. In this

case,

if we take ï 6 : : ã ¿ ^4, it

results

that e¿ is

free related

to Ker

_¿\

,

^maximal

^with

^this

property and õ ç rA.

^(Q.E.D.)

T,EMMA 3.2.

If ã - Aisfree related,toI:nV,

^tkem tkereexists

{6 cü,

free ^reløted to

Im V

^ønd. rnaxirnø|.

witk

this þroþerty, ^so

tlmt

á.

- {".

*,

^{Proof. Analogous}

^{to the proof of the}

^{lemma 3.1.}

-

_{R e m a}

_{r k}

_3.10.

_{Taking into}

_account

_{to the} remark 3.9.

ancl lemma

3.1, it

immedijLtly

results that if

ã"

-

^A,

^{is free}

^related.

to l(er 4

^and

l&l :

m, then-4 is free related

to l(er ¡

^and.

maximal with this

property.

Sirnilarly,

iÎ

^&,

^c

€[

is

free

relatet to Im _Ç and l&l : h, then,

according

to the

lemma

3.2

and.

the remark

3.9,

it

results

that the set 4 ^is

^free

related.

to Im I

^and.

^{maximal with this property.}

Accord.irrg

to the

^rela-

tron (2.1) we have also

got

i

Q

:

h

t ^m.

^(3.9)

I'HEoRENT 3.6.

If { ^c

^A.

is free

^related'

to ^l(er I

and' m,øxirnal

uitk tkis

l>roþerty, tken

á'...g-

i,s

free

^related,

to lm V

^ønd, ffia'xírnal

witk

^tlt'is

þroþerty.

Proof.

Having in nind the remark

3.9,

it

meaüs

that l9l : tn

^and

thus l&\E.l : ^å

^(see

the relation

^(3.9)).

I,et

us prove now

that the

set

S\g is

free related.

to Im V. ^Wit¡

this

purpose-,

let

us consider

Y e Im V, arbitrary,

so

that e(Y) c 4"..1'

h

Tf

g(Y) &\g it

rneans

thatY : Dy*V,, with./, ^{e R,}

^a

: 1,2, .'.,

^h'

Taking into

account

the inn", pråãlct within the lirrear

space Z _14,,!.1 (see

¡iZ1)

and using

the

results

ïbtined. within the paragr"ptt + in-

[17],

9 ^{FREE SETS} ASSoCTATED To A FINTTE oRTENTED GRAPH

65

we ç get: *

_[XtdrlY,]

:0, for all lþ

¹

^qL:1,2, _..., h. But, 0: _[Xtc]ly] :

:lr"+ _D *f) uglÐr, V"f:o*for

all d

:1,2, _{.. .,å}

_{and thus}

y _ _0e.

This fact

leads

's ^{to the}

cónclusion

that the set

úI

... í is

free related

to Im [. ' \-

Consequcntly

wl

have

t

'....8_.free.related

to Im I

^and

ld...e.l : þ;

und.er such circumstances, according

to the t"*árk

^g.10,

_tÌr"

_{theorem is}

proved.

TrrrionrM 3.7.

If ï

_{_=}

&

^,is

_free

reløted

to Im !

^{ønd. møxiytøl}

uith tkis

þroþerty, then

g' _-

_&-

_{is free}

_rclated.

_{lo Ker} ¡

^{ønd. maxinrøl}

with

this þroþcrty.

lroof. ^Similar to the proof of the

theorem _3.6.

Remark

'.il. ^îhe

^theorems

^s.6

^anð,

s.7 ailãw us to

assert

that

the sets

S

and

&

make

up

a

parti

rling to the remark 3.7 we ^havË

: {Wr,W2,...,W;} ^and a':

got_{Vr, R e m

ar k

3.12.

Taking

into 3.11

we may

assert

that the

mo

Ker 4

'úe automatically _{have a base} having determined a bases for

fm I

TrrEoRrJDr

3.8. Let &t c

&. b reløtèd. to

Im l,

^{so tkøt}

d, f) ^ü,

{ ^{c 8-fre9}

^relq'ted

^to

^Ker

6

^{ønd, møximat}

uith this

_þroþerty and.

{ ^{c. g}

free

^reløted.

to rm |

^{øød møximal} wi,th this

þroþrity,'ii'mú

d:r-=-g:oria

&zc8'

lroof .

^T,et

us

suppose that _&,

e ^g,

= g.

_According

_{to the}

_lemma

3.r there

exists ss.,

ê-& free

relatèd-

to Ke; a ;"áää""i-"ñtùïht,

property

_so

that

,9, c:

ïgr, and

according

to the

lemma 3.2

there

_exists

Ù

*, ₌ ^{& free relatet} to rm y

and. maximar

with this property so that

tLq<-äJo.

But,

according

to the

remark S.11,

lve have ï*, lJî*,: A.

anð,

ï*,À {*,:Ø; _which obviously leads us to ï",: ä,

^rd,"

ïr,:

&r, where,

taki'g ^g - c\

^and

g:

_.nz,

_the

_theorem

_is

_proved..

_fet

us suppose now

that &rU &, ç-úl and let A": _{{dr:e.,, ...,} e;,}: & _ (&r[J ilr)

tre.

U

{oo,)

is

free

related to Ker Ã,

^o,

mV.

now,

against

all

reson,

that

A..

I

^I

anð,

t,, _{U {d,,}} is not free

_relaieã

under

such circumstances (see

the definition 3.1) there

exists

x

^e

e

Ker

A, x _*Øs

and

y =rm v, ^y ier,-iá"tlài'aikl

='*,"ü'iu,j,

5 - L analysc numérique et la théoríe de l,approximation ,Iome _10, nr. 1, 1981

66 DÃNUT MARCU 10

A(Y)

= &rl) {ã,,}, where X : %¡d.¡,J-1,

xoao

and Y : lidr,+ T,

^ysos,

oo-&t ^og.&¡

with

x¿,

* ⁰

^and. !¿,

*

^0.

Having in

vierv

the inner product of Vlt",Rl

^(see

_[17]) and

using the results obtained

in

the paragraph

4 from _{[17], we}

obtain

: [XlY] :

0,

which leads us

to

⁰

: _txlYl : %i,d¿,*,Po:*"r0,,o,, *

oD ^{yrtesl: x;!;,*O.}

We get thus a contradiction, and. therefore, either

^g1

U

{ø¿,}

Is

free

related to Ker A, ^{or S,} U {dt,} is free

related.

to Irn !. ^We

^shall

^put

gl't : _s, l)

{et,}

if sl _U

_{ã¡,}

is

free related,

to Ker 4 ^{and g't't: erl){ã,,}}

iÎ ^g, _U

_{ø¡,}

is

free related

to Im

V.

By a similar

reasoning we

can show that _{ú[lr U}

_{ã¡"}

is

free related.

to Ker ¡ ^or

^&f,tt

l)

{a,"}

is free

related.

to Im V, sirnilarly building

^up

one of the sets

^g,l't

:

ú[ftr

U

{a¡"}

or &['] : s['t _U

_{ao^}.

Going on just this way, we obtain the sets

&.ltt anð,

ø[8)

wítln

f, g =

{0,

1,2, ...,r},

^e.tot

:

&r, &Lo)

: &", for which elfr i. free

related

to Ker A,

^eütt

^{is free}

^related.

to fm V,

^g,[r]

)

^g.Y)

=Ø, ^gy) ¿ ^af) :

a,

&r - ^&trt

^{anð. &.,}

₌ ^{g;t); so} \¡e find the

hypothesis

of the first part

of

the

demonstration, where

tealing {: øln

and.

&: g.[r], the

theorem ^is proved.

R e m a

r k

3.12.

The theorem

3.8 represents

an extension of

the theorems

3.6 and 3.7. Practically it's a

stronger representation

of

^these

two

theorems.

4. On the

free sets relatcil

to Ker A. Within this

^paragraph we shall

give a

theorem

who

characterizes

the free

sets related.

to the

subspace

Ker ¡.

DÐFrNrl'roN 4.1.

We call

cycle

of length z

(see

[17]) a

secluence of

r + |

^{nod.es (nio, ni,, !t¡,, . . .,}

^{Øìr) and} a

sequence

of z arcs with

sign '("rø0,, Ez&h,,

...,

^eranr) where

ei:

1

or -1,

^so

^{that for}

^each

j :1,2, ...,r

we have:

I

A*(an,), if

^e¡

: l,

_I

L-

^(ø,,,),

if e¡:

^1,

tuii-r:

\

^x-i.øoo),

if

e¡

: - l, and n'¡: ^{\ A *(oi¡),iI}

^e¡

: _-1.

W'e d.enote

a

cycle

by a

ln¿"1, and.

its

set

of

arcs

by

t(oln¿"f).

THÞoREM 4.1.

Let ^g c &,

^S

+ Ø be. The set I

^'is

_free

^{rel.ated. to}

Ker ¡ ,

,í,f a.nd, onl,y

if

there

is

no cycl,e

alnl

so th,øt

t(<llnl -

^S.

Proof.

I'et S c

9,, S

*Øbe, freerelated.to l(er¡ and let

us prove

that

there

is no

cycle

alnl ^with

^€[

(aln]) c

A.

We

suppose against

all

reason

that there exists a

cycle

alnl

^wrtb

€I(o:ln))

:

_{ûn,, a.þ,,

...,

an,}

9 ^S.

^According

to the

lemma 3.1.

from

_[17!,

f

the

vector

X : -t

e¡a,p.

is nonull in Ker 4,

^and.

^as

^e.(X)

:

ú(<,¡lnl)

c

9,

it

^means

that I

j:t

is not

free related

to I{er [ ; ^{which is}

contrad.ictory to

1l ^FREE sETs

^ssocrATED To _¡\ FrNì.TE

',ìTENTED cRAr¡r{

the

above

-

^stated 6z rs no _cycle <,.,1n1

wit

to Kcr A.

^Against

Ker

A

^{which leads}

with CllX) c

ç

According (2.2) the

vector X is of the form X : Ð ^aqX,,

^{witþ ct e}

e f{ - ^{{0} a'd} ¡f,. "t"mentary iu

5*o, lod x,Afl'ni::u, ;:;,;,

..

.¡ /tL. Because

l,

is elernerrtary

in

f,c.r A.,..thg_o,

u"lo,áirr* to

the theorem

s'B rrom

_Lt7

L ^jt i,

^'

"¡iìl'ì"ivj ""'^'¡n1 ì,¡i,. aILî"üï _tro,,

ah", . . ., ø,,,.}

so

that

X _¿

: ic2)"1rt. Ilut

since

Ì, _E X and

e_t(X)

c f,

then

t(Xn¡

^{c. g}

and, thris, therå.exists a cycle aln-l with.e@fu1) ç.f ; ^which is

con_

tradictory to the

abovc

_-;t"i"ä'riypottr"ris.

' ^5'

^{Gn the}

^froc

sefs ¡'erared ú"

ù ^V. Within this

pa.ragraph we _shall

fi::,;i'.n'"o",",'":*:"å',.:f il;'î'""î;f ',.ff ï::rff !TTi"*-"iir,"g,"pi' i,,duliä'f'yä?:: ]' ^r'et _"i'r' c&¡,

^;r1*

t'.Ø. w"

"uir

^section

^{(see rrTj\}

ä;i,åi;fi ^jT,;f ',î-i:i"':;,]i{,":l!::,"*,,;;:!îfi¿",i:i_1*

a).

A ^*(øn¡ e

ÐL*,

and

_A

-(ar¡) =

^ÐI

\

^пo,

if

e¡

: _l, b) _A-(at¡) €

¡rì>ß

and A *(oi¡) =

^п\g¿*,

if e¡: ^_1,

the set

&.'F

:

{a.¡,,,Øh,,

...,.øn,} beei'g maximal

_(related

to the

inclusion

of sets) with this

property.

iÍ .,:;':';',ì'l, ,!ry',,i:'Ì,_î,,*'"f {fo,i, _*{ris¿r ^r

^zs

^rree

^{retøtcd. ro}

^{rm v,} ,a^rlíZ!;,lï"Fri"r*, ,rr*,#f"ai,""r,"lntù ^{to r,n V}

^and

^{ret us}

^prove

Against all

reson

we

suppose

that there

_exists

a section

E

:

{"ruo,,

Ez(trk",

.'.,

e,at,Ì

with g'k

_{{ãi,, oo",}

_{..., a4}}

s s. ;";;rÀì* ,, the

theo_

rem

2.1 from fl7l, ^the vector O:Zre¡ø¡,is _{nonull in fm V,}

and

since q,(y)

:

&)o

c E it

^T"-ul, that f io'ìot

free related

to _fm V; ^which

is

contradictory

Reciprocally,

to the let

us

above-_

suppose

ãt"r"j, ttaithere

hypothesis.

_is no ;ection

_{E with.}

t* -E

and

_Against let us pïove that I ir'ir". r"*rli"u to rm

_V.

all

rea

which r""*a. .," io

il :åä::i:i::":Til"åi: ï'=Ti ;'î::i ;þîi Ë

6B ^{DÄNUT MARCU} 72 13

\ü'e deJine nro)

_

d.i

FnEE SETS âSSOCTATED TO A FINTTE ORIENTED GRÀP,H ì.

69

According

to

(2.2), the vector

Y is'of

the forrn

Y: Ð ^{p,Y, with} 9; = ^R - - ^{0}

^and

^Y,

elementary

iu Im Ç

^and.

V,=V for all i : 1,2,

.

..,

^ñ..

If Y, is

elernentary

in Im _Ç, thetr,

accord.ing

to the

theorem 2.4

from f17], ^{there exists} a section E:{srah,,Ezãh,,...,ur¡dn,.} so tlnatYr:

: + D _j:r

x ^e¡a.¡..

^Flrt

^{since Y,}

^E

^{ts and}

^{8.(Y) cß, then}

^A.(Vr¡

- $

^{and, thus,}

there

exists

a

section E

rvith g(V,): _&*

c-

9; which is contradictory

to

the

above

-

^stated hypothesis.

DnrlrNrlroN 5.2.

We call chøin ,,vitt^ the length r

(see

[17])

^from

the

node

ntotlnenodem

asequence o1

r! l

^nodes

(nq,ni,,...,n¿,)

^and'

a

sequence

of r

arcs

with

sign (eg.¡,,, e2a,¡,,

...,

e,&pr), where lû¿o:

tt, /t'¡,:

: rn, ei: 1 or -1,

^so

^{that for}

^every

j:1,2, ...,r

^{we have:}

Particularly, a

single nod.e (and

an empty

seçluence

of

arcs) is regar- d.ed as a chain

with the length

zero

from the

nod.

to

itself.

We

denote

a chain frotn n to m by ^(ln,rnl and its set of

arcs of arcs

by A.ftln,m)).

DDrrrNrrroN 5.3.

Two

nodes

n

and,

nr

are mutuøl'ly connected' (see [16]) and we denote this

by

^'/t,

-

^i,n,

^if

^{and only}

^if

^{there exists}

^{yln, m).}

^Evidently,

,,-" ^{ts an}

equivalence

on

^tl/-

^and

^ind.uces

a partition in the

clases ^:)Ir,

flr,

.

.., fl[",

calleð. connected, comþonents (see [16]).

l'rrDoREl\{ 5.2.

Let I

^c:

^g, I + Ø be,

ønd &Lr,

ür,

. .

.,

^Sí(

",

^{tlte connec-}

ted. comþoncnts

of

thc graþh

G:

<ÐL, g.>.

IÍ

tke set

I _{is free}

^reløted

^to

^tke

subsþøci

Im V,

^îhen,

for-all, ie _{1,2, ...,s}

^ønd

_for

^{øny '}t,!t'L}

^ë

^{ÐLr, tkere}

ex,ists

ø

chøin

yln, ml

zøitk ,9(yln,

m)) c ^g \

^g.

Proof.

I,et I c ^g, I *Ø

^{be free related.}

^to Im V,'io = {1,2, ...,s}

arbitrary

fixed

and. n, ln

e

,tI;". W-e denote AV øtÏt _t the set of all

the

chains

from the

node

n to the

node

m. Evidently,

^ø[],)-¡

is not empty

^because n,

rn e

&L¿o.

Againit all

reson

.ffe

_suppose

that for any \ln, rnl = ^ø[iL¡

^{we have}

not A.(yln,ml) ç g\ 9, which

leads

to the

existence

of an arc (at

^least

one)

ø e _&.for

_which

_ø = &(^(ln,ml)

arLd.a.

€ _9.

_-Let us consid.er

yoln,ftl

such

a chain, €I(\oln,m)) :

_{o[?t,

o[l], ..., oll'] its set of arcs

^ar-.ð, {ø1n",'-.,

oro?,

...,o|otj ^q .9(yoln,rnl) the set of arcs for which

^n[:.].

=

&(yoln,rnl)

''1, '¿u' "ti

anð. a[ol t'tt

= ^9, i:7,2, ^...,',,.

ø[ot),

iÎ

efgr

: l,

olî), O

e{or

: - 1 ^{and we}

^consider

^the

^vector

f,,

a*(

A-(

Z : _Dnf,t,

T _vector

_which

_{obviously belongs}

_to

Z[&t,

R].

Having in _{view the}

construction

of

n[on] anð,

Â

we have :

v(z) :

" ^(å *['l): t, ^,@r,,¡ :

_j:l

_É (f ^nî'*r)

:Àq',.ï: Ð"';'"r:;

^(s1)

Putting Y : É "lit ' .ï)we have,

according

to (5.1), y _{e rm}

_V,

Y *

^0s",

^e\Y) c F and

subsequently,

g is not free relatcd to Inr [;

which is contradictory to the

above_stated hypothesis.

Therefo¡e,

if

s is free rerated to the

Jm V, ^the.,

^there exists

yfrø,mle

= ^{ø[l]^t,}

^so

that €rkln,rnl) ç s \ ^{s. (e.E.n¡}

6. Matrix

assoeiafcd

to the

free sets.

I,et rls

consid.er

{

^c_ &.

a

free set related

to Ker ¿ ^and

^rnaximai

*itf, tti, präp*ro'äccording to

the theorem 3.6,

the

set g'

- ^{g '}

& is frec _related

to rm ! ^a'd

^rnaximal rvith

this

property.

, -Accordi'g to the

theorenr 3.7 ard.

thc

rerrrarr< 3.8,

if

^&-

is

free rerated

to fm V and naxirnal with this piop"rt1,, then,

rve carr

co¡struct

_the vectors Because

Ytt),ytzl, the

vcctors

...,yt,;t, ytgt, which forrn

_p

_=- l,

2,

a

basis

for the

subspace

frn

\7.

"....,0i

^belong

Io ^yl&, Rl,

thcy may be rvritten _{as a} linear

combi'atiå,,

ór

l¡å. "";to;;"r,,;r, ^.., &q,w'ich

means _{. . .,}

_{q (matrix} that there _{with tn} exists

_rows

a matrix e:

(gu,),

q-: i, ;',':..,,¡n; t:1,2,

and. q .oiirrrrr,À¡

iã irr"t

,nl"-îurr" ,

YtPr

:

Ënu, o,,

_Ê

: _{l, 2,}

. . .,

rn

(6

l) Having in vielv

the_

way the

vectors ytß1, p

: L,2, ..., Ø, have

been

construct

_(see

remark

3.7)

we

cao assert

the fact that

dlBr

e {_ ^{1,0, l},}

tor all

₉

: 1,2, ...,*; í: t,Z, ..-.,q.

considering another paft (g',

a,¡

of free maximal sets rerated.

to

KerT\

and rmV resoectiysly, *e obtain anothe¡ b;q;- ?;,;

^p

: l, 2, ...,tñ,

lätä:

^{subspaËe rm V-}

^{ior which}

^nve

tå.,r",

u""ording

to id rl oiotu:*r

^{'^:;:}

I

I

l

I

i

70 DÃNUT MARCU 14

r.Di\rx,r 6.1.

Ij Q

ønd'

dl

are

tuo

møtrices a.ssaciøted

to

tke þqß¿s l/fØl _, P

:

1,

2, ...,fn,

then, tkere exists a. .squ&re ma.tr'ix

T,

so tka.t

õ - ^lQ

det (l) : *1. -

Proof

.

^'Writing

/tßl

^¿5

a

combination

of the

vectors ^ytOl

,

^{we obtain :}

yrsr:Ét*)zrrr,

p

:1,2,...,t/1,

^(6.2)

Y:I

where

I :

(1r,") _P

: 1,2, ...,lli, ^(:1,2, ^{...,1/i is a}

^square

^{matrix with}

elements

i" _{-1,

^{0, 1}.}

Now, writiug Ytßì as a

combination

of the

vectors

yt0l

_we

_obtain:

15 ^{FREE SETS} ASSOCIATED TO A FINITE ORIENTED GRAPFI

77

irøt

ønd.

where ¡:

(I'r")

y: 1,2, ...,1ñ; u.: ^l, to l. ^{From (6.2) and (6.3) we obtain:}

,n

irsr -

_1:1

^{5^ r," (å} fl,"r*,) å(åu'" t1"Jyr"r,

^(6.4)-

Proof

. I,et us

suppose

that the set

{o,,, o,", , ^. ., ø,_}

is free

related

to Ker ¡

^and. .maximal

with this

proper,ty. According

tä tne

remarks 3.7

and 3.8

r've

can construct a

basËs fro_rn

tþe

subspãce

il'v, ;;t"g th;

set

4'\..{ãt,,at,,...,at^}, _{who is}

free related

to fm'V and rnaxirn"i*itf, ';

is property.

r,ei

us äor.sid",

õ tn" matrix

associated.

to this

bases,accor- ding

to

^th-e. procedure described

at thc

bcgining

of this

paragraph.

.

^According

^to,thc

lcmma 6.1.

it

cxists"

u íqu"r" -Jt.i*-r io ^that:

õ : ro and. det (t) : +1.

^(6.6)

Because

t) = lO, ^then,

^rve can write :

.

õr^,,,,...,,n¡t

=

^det

^(f)

^Ðp,,,,,.

..,,it.

^(6.7)

Buï,

-havi'g in rnind the way the natrix õ hr.

been defined we may assert

that:

to.

¹¹

s+i.

ol

_s"

:

i r, if g: i, I: 1'2,'",

nt'

which

rneans

that

(developing accord.ing

the

diagonal line)

õrn,,^,,..,r_1

: fl.

^(6.g)

F'rom (6.6),

(6.7) and (6.8) we obtain:

Ðu,,t,,...,r_¡:

fl. ^{(e.E.D). I,et}

us srlppose now

that

the set _{o,,, o,,, . .

.,

a.r

} i,

,roä free related

to l(er I

and maxirrral with this property, rn"t"'ti'ot implies that

there exists

X: D ^{*,, n,,= Ker} 4, ^nonúll,

^so

that

(see

the

rcnarr_

4.2 from

_[17])

[X¡Vr9l] :0, _{for all}

p

: 1,2, ...,/n. (6.9), Rewriting (6.9)

r,ve obtain:

lil l. j ,tL ill

0: _lxlvrrjrr :

lÐ x',e',1Ðnn

',]-Ðx¡

dùst,:D.cùp,,x, _,

v

^{'( \1}/-t^î,

l",Yt"l, y:

lg"

l"nYt"ì

DD

*fl

1,2,

. . .,

ûfi,

^(6.3)

2,

. .

,,

ln

; is a ^matrix

^similar

Becatrse

the

vector5

lft9l, I : ^1,2, ...,wi are linear

ind.epend.ent, then, accord.ing

to

(6.4)

we must

have ^:

É"u'r'":80,:{f ^il I:"'

^(6.s)

y:l

10,

if _þ * _".

F'rom (6.5)

we have: 1-Jclet

[(80")

f3:1,2,...,1ñ; s.:1,2,...,rn1 : :

d.et

(ll) :

^det

^(l)

^d.et

^{(l), which}

^does

not

rnean

anything

else

but that det (l)

^and.

det ([') are concurently equal to 1 or - ^1.

Consequently,

det (l) : ¡tl.

^(Q.Iì.D.)

Rervritirrg

the relation

(6.2) rvc obtain

, fõ,u,o,: ^?tsl : Élurltvl:

'ui | (r

t:t f-*

: å t- _(Ð ^a,, o,): å ^(å

^rB"

^o,,)

^ø,, rvhich teads

to õs, :

å ^{re, oy}

^,

i.e. õ: to.

^(g.E.D.)

We

^d.enotê

by

Øy,,t,...,r*l

u

subdeterrninant

of the rnatrix f), a

sub- dcterrninant made

up with the tn rows of Q and the

columns t1, t2, . . ^,

...,t;ofÇ1.

rl*rnc,r.rì.t

61. If

^the _{set {o,,,} ^o,,,

..., q*) is _free'

rela.ted' to

Ker L

^and'

maximø|, aith' this þroþerty,

then,

Сt,,t,,....,t,)

: !1,

^ønd'

iÍ

_{o,,, ^atr",

..., e,;)

isnotfreerelated,toKerT\ øndmaximal'wi,tktkisþroþerty,tlren,Ø¡t,,t",...,r¡):0'

the relation (6.l0)

represerrts a h

with

ut, urrl<n'orvn'quäntitcs (the

But, as not all the

unknown

that the

vector

X is

nonull)

it

^rnea

ad.mits

a nonull solution fáct that

det _f(OB¿-)

9: ^{l, 2,} ...,m;

i,

:1,2, ...,nil:

^Ð[,,1,,. _{..,r_t}

: 0. (e.n.n.¡.

Re

m:ar'.,k 6.1.

rf

(g,

a¡ is a'pair of free

sets,

naximal

rerated. to Ker

I ^{a'd rir.} y

respectiv"iy,

ir,""iãocording-tã-iii" i"î"rr. 8.6

we can

þ:r,2,.

^{7lL (6.10)}

72 ^{DÄNUT MARCU} 16

constfuct

the

vectors ^XLq),

d.: I,2,...,

^{À which}

fofm a

bases

for

Ker¿1

and we rnay

associated

to it ^the _{matrix 9*} : _{ff)ir) -"} :1,2, ...,h;

t:1,2, ^... q; sirnilar to the rnatrix Q. ^Denoting by

Ð1,,,,r...,,nt

^ subd.etelninant

of O*

(subdeterminant

mlde.up-with

_\he.

h

rows

of

O*

ã"ã-tfr"

^columns

^tl,

^{tz, . .}

^', ta of

C)x) we"

obtain, by a similar

resouing

to

that prcviously

expounded,

the following

theorenr ;

rii'olc¡;tul ^6.2' IÍ

^{tke set} {o,,, o,,, ' '

',

^q

h} is frtc

^rtlale

^{d lo ¡rr V}

^ønd

ma.ximal,

uitk ^this

þroþerty, th'en Ðþ,,4....,t

nt: !1,

^a'nd

^iÍ

^{{o,,, a¡", . .}

^{., a'r}}

rna.ximøl

uith this _þroþcñy,

then,

<gL,

g> _with

"-Y¿

:

{nr, rrz, ns, ,/&4, ?t5,

(nr,

rcr.),

ds:

^{(tu2, ns),}

&¿:

(ns,ns),

tua, /11),

ar:

^(m",

nn), ør:

^{(nu, nn)}

et ï : {or:

^Ur,,

^{&u: Ur,}

^flz

: U, Ker 7\

^and

^{maximal with this}

^pro-

A4:

Vs, &e

:

V¿,

A,s:

V6,

erc:I,/ß)

I with this

^property.

is

those obtained

paper and

_[16]

iu - tl8l _[1] - ^[13].

^{representMore}

a theory in the

þarticulør ^{case ult'en}

d

_{tke grøþk}

_U6l - ^[B] _is

_not ^we _necessøry ^{consid,er aud} _connected.^d.eve-

ecome nat:ulral conseçluences

of

lvhat

"i; Tl"i,:i'"ii"r* å?,'i :ii ^åî1,1

y iÎ I is a

sþønning tree

of G.

(see

[l] - ^[13]).

Sirnilarly,

a

set_8.

is to Im!

^and

maximal with this

^property,

iÎ

^{anð' onlv}

^if

^&

^is a

otree-of

G'

(see

tll -

^t13l)'

Moreãve-r, Ker

7\

^is

the

^sþøce

of_c1t V t!"

^sþøcc

of

^{cocycles. (see}

tll - ^[tá1).

^rndeed.,

^from

^116]

a

results:

dirnl(er L:q-þ1-s,

where ^.s

is the

nrrmber

of

connected components

of G,

Hence

dirnKerA:ulGl,

rvhere

_Så. v[G] is the

cyclonr'øtic^number:f

G'

þee. [5]).'"

-

^.

"""*¿ins to

^remarks

3.6 and 3.9 we

obtaiu

: if t

^is

_frec

^{related to}

fãt n

^and' "rnøxirnal

uith

tk'is þroþerty, ^tken

l8l : rank

(Â) ;

if a

is free ^related.

to Imv

ønd ma.xintøl

uith

this þroþerty, ^tken

lgl :

v[G].

17 ^{FREE SETS} ASSOCIATED TO A FINITE ORIENTED GR,ÀPI{

7s

But, if

G

is

connected, e,g., s

: l, then,

accofding

with _[16], it

results ^:

lsl:þ-r,

e.g.,

Similarly,

E.

is a

spanning

if

^G

is tree

connected, then

of G.

(see

tll - ^ilgl).

lal :u[G] :q-þ+1,

e tll -

^[13]).

t16l - ^{[18] and this}

^paper,

if

G

tree is free

and.

maximal

related

ue.

(see exemple

7). Similarly for

^a

graph G

is not connected..

^ecessary

^a

^general

^theory

^{when the}

,

^{9. ,opened, problem.}

^A

^research

co'cerning the rink

between _{the free} sels (introduced

in this

paper) and

the

ind,eþendent systems

from

matróids theory.

I{EIlERENCBS

tll

^A

[2] ^B [3] ^lr

rderrne - Ehrenf est, T., De Bru jin, N. I.incar graþh.s. Siruon SLcvin pB, lg5l. G., Circuits and, tt,ees in ^oyicntcd ott, _Iì..,_l[ayberry, J. p., Matrices aød lrecs. Ecorrornic Activity Analysis, New

York,,Wiley, 1954.

[Z] ? " ^rrr_b_i t, J. J., ^On trecs rsf conncctcrl graþhs. L¿tvion Mailr. flearbook, lg65.

!9] ^G " ^{u I} d, R. 1,., Gra,þhs ctn.tl. Vector Sþales.- J. Mailr., phys., JtÌ, 1958.

[9] Gniller'in, E.4,, Introdtt.ctory Cîrcuit ihrory. _3rom" Wley & Sons, I'c., New

York, 1953.

[10] Kirchhof f, G., _{mgen., auf uelche m.ø.n l¡ci} d,erlJnter- sucltung der ^y" Strome geÍuhyt uird,. .Lnnalen det Physik un<l

[l] Ptecival. \\¡., I

rz¿¿s. proceecìi'gs or trre nrstitute o, ,r..rlrl'#oß:rr:lr"K::'i"{rrTi,''íKä|n*t [2] ^{s e cl I a c e} k, _J., I;ûúte. graþhs anrt their sþattning rrccs. Õ?r.pir-ir"pèstovani mate-

matiky, 1967.

[13] ^{S e s h} rr, S., l{ e e r], M. l\., I'ittear graþhs ønd el¿clrical nelaorhs. I{eatling, Adclison- Wcsley, lg6l.

[14] Arglriri _gicir,ã rioard (vot. l). Editura Dj<tacticá çi ^pedago- lll] ^{S_. e a n g} á, çi pedagogicä, Bucurcçti, 1920.

[16] M a r c n, l). ie ^Catcõlu's oj the Nu*nber oJ Can_

necte _{,¿8, /¿. Sturìii} çi ô.ercetãri Mateiratice,

2, 1976.

L4 t5 t6

ll l

ll

B B

I

I

74 DÄNI-TT MARCU' 18 DÍATIIEMATICA

_

REVUE D'ANAI,YSE NUMERIQUTI

ET DE TI{EORTE DE I,'APPROXIMATION

L'ANALYSE

NUMÉRIQTIE

ET LA TTIÉORM DE

L'APPROXIMATION TOME

10,

I¡o

l, lg8t, pp. 25_29

[17] ^{M a r c} u, D., Considerations Concerning Certain Vector Sþacas Associatcrl to the Orienteil Finite Graþhs. Stuclii çi Cercetäri Maternatice, È{1, 4, 1976.

flB] Marcu, I)., On Certøin Vcctor Sþaoes Assoaiaterl to lhe Oricnled Finite Grøphs, Analele Univcrsitäfii ,,AI/. I. Cuza" clin lagi, 25, 1, 1979.

Ræeived l. XII. 1980

Faculty of Malhemøtics

U nia er sily of B uohør e s t

Acatlemiei 14 r

70109 Bucharest, Ronrauia

SUFFICIENT CONDITIONS OF UNIVALENCY FOR COMPI,.EX FUNCTIONS IN THE CI,ASS

C,

by

PDTRU 1'. MOCANU (Cluj-Napoca)

1' Introductigl Tn"

follorving. sufTicient condition

for

univalency _of

an analvtic

T''IEoREùI

fu'ctio' A. IÍ D in is a

convex

a

conuex d.omaiø

äomairr is in well

the

r."i*"

comþrex

_l2l, pùne _t4j:-

t,'ønd,

lii:"'

if f ^is

^{an ønøIytic} function

in D

suck

that '- --- -""'Ì

(1) _Re/'(z) ¡ 0, _for

^a.tt

^{z e}

D, then

f ^is

^uniuølent

in

D.

'Ihis result

was generalized

in [l] and [S]

^{as follows:}

I] If

_{_{}

_is. in ø

domøin

D

^ønd.

if there

exists øn

*n

n g which

is t

and conuex

in D

(i.e. g(D)

i, ; ¿;;";;

do

th&t

(2) ¡¡qlll ¡ 9, _for øtt

z

e

_D,

e'(:) then

f ^is

uniuq,lent

in

D.

conditions

of

univalency

similar

to

the

class C1. These conditions yield.

ism in the

complex plane.

L:,

_Ltons

^we _u:

^say _r(e ^that'.;he

_{/ anda} function/0"r.;î.;r"""r:::1 _{: Imf} ,::rr";: r:::

of the real varíables

r

and

1i ^hau.

^continuous

{irst order pärtial derir,.iív"s il b.