54422
Páginas: 11 (2534 palabras)
Publicado: 19 de abril de 2015
ALGUNAS PROPIEDADES
TOPOLOGICAS
DE LOS GRAFOS
E.Llorens Fuster
Dspartamento de Mateméticas
RESÜtJEH
Se define, sobre el conjunto soporte de cualquier grcfo,
una colección de topologías, que permiten expresar en sus términos,
ciertas propiedades del grafo, como la estabilidad y la conexión.
INTROOUCCION
Para tratar de expresar, en términos topológicos, ciertas oaracterísticas de las grafos,se define, para cada correspondència P i X — ) X , una colección de topologías sobre X, que re Ple —
jen las propiedades de V , y que salv/o excepciones resulten
ser
no T . A su estudio se dedica la sección 1.
La construcción anterior conduce al estudio de una clase
especial de grafos, pròxima a ios transitivos, que se realiza en 2
reserwàndose la tercera parte al anàlisis de las relacionesentre
la estabilidad interna y externa, la conexión en sus mas usuales
versiones, y la simetria, con las nociones topológicas introduci—
das en 1, independientes del punto de vista adoptado en (?]. Resul
ta existir equivalència entre la conexión dèbil de um grafo
y la
conexión en una de las topologías introducidas.
Toda le terminologia de Teoria de Grafos, se emplea en
el mismo sentido que (l). 1.;
TOPOLOGIAS
UMUJ
CQNSTFIUCCION
Sea
Jlfp.D
( X , r ) un g r a f o c u a l q u i e r a . Dado un elemento x£X,se d e -
f ins!
1^ =
^ V ( x ) £ 2 ^ : ix}
urP(x)cv(x))
Se t i e n e entonces:
1.1.1:
Si
Se%^
y
X
S'tíf'^, entonces
SOS't^^
X
X
1.1.2.: Si
S6|'^
y
S C U , entonces
1«.1.3.: S i
S^feP , entonces
U€
X
%^.
X
xeS.
X
Para cada ordinal p y para cada aplicaciónmultivaluada r* ,
puede definirse una subfamilia de 2^
Jl(p,r}= |U € 2 : U € ^ ^
1.2.;
la familia
para cada xtU} .
TEPRSMA
Para cada ordinal p y cada aplicación multiv/aluada F :X
Jlíp.f) constituye una topologia sobre X.
^X,
La demostración es simple consecuencia de la difinición.
NótesB que €
no constituye un sistema fundamental de enx
^
tormos de x para dichas topologias, pues para ellodebería verificarse
la condición suplementària:
1.2.1.:
Si U6||^ BVtfe'^ tal que V C U y V6 |^ Vx«V.
'x
'x
'
'x
Se ueré posteriormente que no es satisfecha en general.
l.a.i
QBSERVACIDN
No es cierto en general que si (X.P)/ (X.f') entonces
t&CP»^) ^ *^{Pt^')»
Asi para los sencillos grafos de las figuras:
ir^
d
" e
jiCi,r)=ji(i,r')= { íd},íe} , {d,B}
Ello justifica la siguiente:
;.4.!DEFINICIQN
Dos aplicaciones multivocas f-'X
>X f-'X
)X, y por exten
sión los grafos [X,P]y (X,r'), son p-equis/alentes si y solo si Jl(p,r) =
ia(p,r').Escribiremas en tal caso (X,r)~ (X.P').
1.5.:
TEOREMA
^
Un conjunto U C X es Jl(p,P)-abiBrto si y s61o si P (u)CU.
Demostración:
rP(tJ)CU
í ^ V x í U , r ^ ( x ) C U <=» Vx6U, Uí|^ ^-•U.BÍp.r).
1.6.:
Si UcX
COROLARIO
^ ^
es
1.7.; COROLARIO
41.^} C Jí.(k,r) , V k el'.
En adelante, siempre que no sea necesario hacer especial mención
de r ,se escribifa Jl(l,r) s Jl(r).
1.8.; COROLARIO
Jl(p,r) C Jl(k.p,r}
Vk,p£l*.
1.9.; TEOREMA
Para todo vértice x£X, el cierre transitivo P(xj^{x}Ur(x}ur (x)U...
de X, es Jl(p,r)-abierto, VpeI.
Demostración:
Obviamente r^(r(x)) = C^[x)UC^'*' [x} U... C r(x), y elteorema
se sigue de 1.5.
1.10.; TEOREMA
Sea UcX. Si r^{\j)= ^/.entonces U es Jl[p,r)-abierto.
Denostfación;
Es inmediata sin mas que considerar que V (u}= 0CU.
1.11.: TEOREMA
Si •^x^cX es (íi(p,r) abierto, entonces y solo entonoes V (x)= ^
o r^CxJMx].
Demostración;
En efecto, pues por 1.5. T (x)C {x} .
1.12.: TEOREMA
Existen en todo grafo los conjuntos que permiten definir funcioner ordina?-es:
X(0)=^xíX: r(x) = ^ }
X(l)= ixfX; r(x) C X(0)}
X(2)= {XÉX: r(x) C X(l)}
•• •
a si oJ es un ordinal límite
X(a;)= I
)x(o().
En estes condiciones se tiene que, si oi es un ordinal, X(oí) es.
c5l(p»«^]-abierto Vp£l .
Demostración;
Sea oi un ordinal no límite.Es fàcil ver que F (x(o<) )C X(o<-p).
Si a =p , r'^(X(o<))c X(o<-p)=x(o)cx(o(), por lo que X(o<) es (flCp.r)abierto. Si -J^ > p T ^(X(o( )...
TOPOLOGICAS
DE LOS GRAFOS
E.Llorens Fuster
Dspartamento de Mateméticas
RESÜtJEH
Se define, sobre el conjunto soporte de cualquier grcfo,
una colección de topologías, que permiten expresar en sus términos,
ciertas propiedades del grafo, como la estabilidad y la conexión.
INTROOUCCION
Para tratar de expresar, en términos topológicos, ciertas oaracterísticas de las grafos,se define, para cada correspondència P i X — ) X , una colección de topologías sobre X, que re Ple —
jen las propiedades de V , y que salv/o excepciones resulten
ser
no T . A su estudio se dedica la sección 1.
La construcción anterior conduce al estudio de una clase
especial de grafos, pròxima a ios transitivos, que se realiza en 2
reserwàndose la tercera parte al anàlisis de las relacionesentre
la estabilidad interna y externa, la conexión en sus mas usuales
versiones, y la simetria, con las nociones topológicas introduci—
das en 1, independientes del punto de vista adoptado en (?]. Resul
ta existir equivalència entre la conexión dèbil de um grafo
y la
conexión en una de las topologías introducidas.
Toda le terminologia de Teoria de Grafos, se emplea en
el mismo sentido que (l). 1.;
TOPOLOGIAS
UMUJ
CQNSTFIUCCION
Sea
Jlfp.D
( X , r ) un g r a f o c u a l q u i e r a . Dado un elemento x£X,se d e -
f ins!
1^ =
^ V ( x ) £ 2 ^ : ix}
urP(x)cv(x))
Se t i e n e entonces:
1.1.1:
Si
Se%^
y
X
S'tíf'^, entonces
SOS't^^
X
X
1.1.2.: Si
S6|'^
y
S C U , entonces
1«.1.3.: S i
S^feP , entonces
U€
X
%^.
X
xeS.
X
Para cada ordinal p y para cada aplicaciónmultivaluada r* ,
puede definirse una subfamilia de 2^
Jl(p,r}= |U € 2 : U € ^ ^
1.2.;
la familia
para cada xtU} .
TEPRSMA
Para cada ordinal p y cada aplicación multiv/aluada F :X
Jlíp.f) constituye una topologia sobre X.
^X,
La demostración es simple consecuencia de la difinición.
NótesB que €
no constituye un sistema fundamental de enx
^
tormos de x para dichas topologias, pues para ellodebería verificarse
la condición suplementària:
1.2.1.:
Si U6||^ BVtfe'^ tal que V C U y V6 |^ Vx«V.
'x
'x
'
'x
Se ueré posteriormente que no es satisfecha en general.
l.a.i
QBSERVACIDN
No es cierto en general que si (X.P)/ (X.f') entonces
t&CP»^) ^ *^{Pt^')»
Asi para los sencillos grafos de las figuras:
ir^
d
" e
jiCi,r)=ji(i,r')= { íd},íe} , {d,B}
Ello justifica la siguiente:
;.4.!DEFINICIQN
Dos aplicaciones multivocas f-'X
>X f-'X
)X, y por exten
sión los grafos [X,P]y (X,r'), son p-equis/alentes si y solo si Jl(p,r) =
ia(p,r').Escribiremas en tal caso (X,r)~ (X.P').
1.5.:
TEOREMA
^
Un conjunto U C X es Jl(p,P)-abiBrto si y s61o si P (u)CU.
Demostración:
rP(tJ)CU
í ^ V x í U , r ^ ( x ) C U <=» Vx6U, Uí|^ ^-•U.BÍp.r).
1.6.:
Si UcX
COROLARIO
^ ^
es
1.7.; COROLARIO
41.^} C Jí.(k,r) , V k el'.
En adelante, siempre que no sea necesario hacer especial mención
de r ,se escribifa Jl(l,r) s Jl(r).
1.8.; COROLARIO
Jl(p,r) C Jl(k.p,r}
Vk,p£l*.
1.9.; TEOREMA
Para todo vértice x£X, el cierre transitivo P(xj^{x}Ur(x}ur (x)U...
de X, es Jl(p,r)-abierto, VpeI.
Demostración:
Obviamente r^(r(x)) = C^[x)UC^'*' [x} U... C r(x), y elteorema
se sigue de 1.5.
1.10.; TEOREMA
Sea UcX. Si r^{\j)= ^/.entonces U es Jl[p,r)-abierto.
Denostfación;
Es inmediata sin mas que considerar que V (u}= 0CU.
1.11.: TEOREMA
Si •^x^cX es (íi(p,r) abierto, entonces y solo entonoes V (x)= ^
o r^CxJMx].
Demostración;
En efecto, pues por 1.5. T (x)C {x} .
1.12.: TEOREMA
Existen en todo grafo los conjuntos que permiten definir funcioner ordina?-es:
X(0)=^xíX: r(x) = ^ }
X(l)= ixfX; r(x) C X(0)}
X(2)= {XÉX: r(x) C X(l)}
•• •
a si oJ es un ordinal límite
X(a;)= I
)x(o().
En estes condiciones se tiene que, si oi es un ordinal, X(oí) es.
c5l(p»«^]-abierto Vp£l .
Demostración;
Sea oi un ordinal no límite.Es fàcil ver que F (x(o<) )C X(o<-p).
Si a =p , r'^(X(o<))c X(o<-p)=x(o)cx(o(), por lo que X(o<) es (flCp.r)abierto. Si -J^ > p T ^(X(o( )...
Leer documento completo
Regístrate para leer el documento completo.