Revista de Matema´tica: Teor´ıa y Aplicaciones 2001 8(1) : 33–46
cimpa – ucr – ccss issn: 1409-2433
isomorfismo de conjuntos de relaciones*
Mijail Bulat**
Recibido: 16 Noviembre 1999
Abstract
It is recommended to use a solving method for relations sets in order to solve
the isomorphism problem. This method allows to solve the same problem for big size
graphs, homogeneous graphs, graph systems, k-signs logic functions and their systems.
Keywords: graphs isomorphism, graphs systems, equivalence systems, simple substitu-
tion, multiple substitution.
Resumen
Se propone un me´todo de solucio´n del problema del isomorfismo para conjuntos
de relaciones. El me´todo permite resolver el mismo problema para grafos de grandes
taman˜os, grafos homoge´neos, sistemas de grafos, funciones de lo´gicas de k-signos y
sistemas de las mismas.
Palabras clave: isomorfismo de grafos, sistemas de grafos,sistemas de equivalencias, susti-
tucio´n simple,sustitucio´n mu´ltiple.
Mathematics Subject Classification: 05C60, 68R10
1. Introduccio´n
La resolucio´n del problema del isomorfismo de grafos se complica cuando los grafos son
de grandes taman˜os o sus matrices de adyacencias son homoge´neas [1, 3, 5, 6]. En ambos
casos el problema se resuelve ma´s facil presentando los grafos por un conjunto de relaciones
correspondientes a matrices de taman˜os razonables y no homoge´neas.Con tal presentacio´n
aumenta el nu´mero de restricciones que permiten eliminar muchas variantes y con esto
*El art´ıculo fue enviado cuando el autor trabajaba en Universidad Americana, Managua, Nicaragua
**Facultatea de Matematica si Informatica, Universitatea de Stat din Moldova, Str. A Mateevici, 60,
Chisinav, Moldavia. E-Mail: bulat@araximfo.com
33
34 m. bulat
facilita la resolucio´n del problema. En este trabajo se resuelve el problema del isomorfismo
para tales conjuntos y se dan las aplicaciones de e´stos en grafos y en funciones lo´gicas.
Ya que cualquier sistema de grafos o h´ıpergrafos es un conjunto de relaciones, entonces se
puede resolver el problema del isomorfismo para tales sistemas.
2. Sistemas de equivalencias
Dado el conjuntoX = {X1, . . . ,Xn}, dondeX1 = {x11, . . . , xm11} , . . . ,Xn = {x1n, . . . , xmnn}.
Sobre X por medio del conjunto Ω = {ω1, . . . , ωt} esta´n definidas las relaciones RXiXj
RXiXj =
x1j . . . xmjj
x1i
.
.
.
xmii

rij11 . . . r
ij
1mj
.
.
.
rijmi1 . . . r
ij
mimj

, rij11, . . . , r
ij
mimj ∈ Ω .
Designemos por R el conjunto de estas relaciones. Ana´logamente sobre otro conjun-
to X∗ = {X∗1 , . . . ,X∗n}, donde X∗1 =
{
x∗11, . . . , x∗m11
}
, . . . ,X∗n =
{
x∗1n, . . . , x∗mnn
}
, esta´n
definidas otras relaciones por medio del mismo conjunto Ω . Designemos este conjunto de
relaciones por R∗.
Sea SX,X∗ la sustitucio´n en la primera fila de la cual esta´n los elementos de X y en la
segunda los de X∗ :
SX,X∗ =
(
X1 X2 . . . Xn
X∗k1 X
∗
k2
. . . X∗kn
)
, k1, k2, . . . , kn ∈ {1, . . . , n} (1)
Segu´n esta sustitucio´n componemos las equivalencias
RXiXj
∼= R∗X∗kiX∗kj (2)
∀RXiXj ∈ R,∀R∗Xk∗
i
Xk∗
j
∈ R∗
Llamaremos este conjunto sistema de equivalencias por la sustitucio´n SX,X∗ .
Por ejemplo, si
X = {X1,X2,X3} , X∗ = {X∗1 ,X∗2 ,X∗3} , SX,X∗ =
(
X1 X2 X3
X∗3 X∗1 X∗2
)
,
R = {RX1X3 , RX3X1 , RX2X3} y R∗ =
{
R∗X∗3X∗2 , RX∗1X∗2 , R
∗
X∗2X
∗
3
}
entonces el sistema de equivalencias por esta sustitucio´n es:
RX1X3
∼= R∗X∗3X∗2
RX3X1
∼= R∗X∗2X∗3
RX2X3
∼= R∗X∗1X∗2
isomorfismo de conjuntos de relaciones 35
La solucio´n del sistema (2) se llama un conjunto de n sustituciones
SX1X∗k1
=
(
x11 x21 . . . xm11
x∗11k1 x
∗
12k1
. . . x∗1m1k1
)
SX2X∗k2
=
(
x12 x22 . . . xm22
x∗21k2 x
∗
22k2
. . . x∗2m2k2
)
.....................................
SXnX∗kn
=
(
x1n x2n . . . xmnn
x∗n1kn x
∗
n2kn
. . . x∗nmnkn
)
11 , . . . , nmn ∈ {1, . . . , n}
que satisfacen las equivalencias del sistema.
Si la solucio´n existe, entonces el sistema se llama compatible y en el caso contrario-
incompatible.
Por medio de las sustituciones de la solucio´n un conjunto, por ejemplo R, se transforma
en otro. En este caso escribimos
R(SX1X∗k1 , . . . , SXn,X
∗
kn
) = R∗ (3)
Al conjunto R corresponde un grafo G cuyos ve´rtices son los conjuntos de X. Los pesos
de las aristas son las relaciones respectivas de R .
Este grafo tiene su matriz de adyacencias AG con los elementos aij=
{
1, siRXiXj ∈ R
0, siRXiXj /∈ R
y su matriz APG de los pesos de las aristas.
APG =
X1 · · · Xn
X1
...
Xn
 RX1X1 · · · RX1Xn. . .
RXnX1 · · · RXnXn

Si RXiXj /∈ R, entonces todos los elementos de esta matriz en APG se designan por el
s´ımbolo *. Para m1 = . . . = mn = 1 este grafo se transforma en un grafo habitual con los
ve´rtices x11, . . . , x1n.Los pesos de las aristas son elementos de Ω.
Igualmente al conjunto R∗corresonde un grafo G∗con su matriz de adyacencias AG∗
y con la matriz APG∗de los pesos de las aristas.Si el sistema (1) es compatible entonces
entre X y X∗se establece una correspondencia biun´ıvoca. Para Xi ←→ Xki y Xj ←→ Xkj
debe verificarse la condicio´n
RXiXj
∼= R∗X∗kiX∗kj (4)
Esto significa que G ∼= G∗ y tambie´n R ∼= R∗. Para hallar el conjunto {SX,X∗} de
sustituciones por medio de las cuales se establece la correspondencia biun´ıvoca entre los
elementos de X y X∗ hace falta resolver el problema de equivalencia para las matrices
AG y AG∗ [1]. Es evidente que si {SX,X∗} = ∅ entonces el sistema es incompatible y, por
36 m. bulat
consiguiente, los conjuntos no son isomorfos. Si {SX,X∗} 6= ∅ y ∃SX,X∗ por medio de la
cual el sistema de equivalencias es compatible, entonces R ∼= R∗. Para hallar la solucio´n
del sistema (2) escribimos la matriz APG en la forma desarrollada y designamos sus filas
y columnas respectivamente por y1, . . . , yq y z1, . . . , zq.
APG =
z1 · · · zm1 · · · zp · · · zq
x11 · · · xm11 · · · x1n · · · xmnn
y1 x11
...
...
ym1 xm11
...
...
yp x1n
...
...
yq xmnn

 r
11
11 · · · r111m1
. . .
r11m11 · · · r11m1m1
 · · ·
 r
1n
11 · · · r1n1mn
. . .
r1nm11 · · · r1nm1mn

. . . . . . . . . r
n1
11 · · · rn11m1
. . .
rn1mn1 · · · rn1mnm1
 · · ·
 r
nn
11 · · · rnn1mn
. . .
rnnmn1 · · · rnnmnmn


,
q = m1 + . . . +mn
Igualmente construimos la matriz desarrollada APG∗ . Para esta matriz aplicamos la
sustitucio´n (1) y la designamos por A∗PG∗ . Para las filas y columnas de esta matriz usamos
las mismas designaciones que para las de APG (ver Ejemplo 1). Resolviendo el problema
de equivalencia para APG y A
∗
PG∗ [1], obtendremos la solucio´n del sistema (2). Segu´n (1)
se obtienen las primeras sustituciones:
Sˆ1;Y,Y =
( {y1, . . . , ym1} · · · {yp, . . . , yq}
{y1, .., ym1} · · · {yp, . . . , yq}
)
y Sˆ1;Z,Z=
( {z1, . . . , zm1} · · · {zp, . . . , zq}
{z1, .., zm1} · · · {zp, . . . , zq}
)
(5)
Ya que por yi e ziesta´ designado el mismo elemento del mismo conjunto entonces
yi ←→ yj ⇐⇒ zi ←→ zj (6)
Segu´n [1] para que APG ∼= A∗PG∗ es necesario y suficiente que se cumpla
Lı´mS˜1;Y,Y = SY,Y ∼= SZ,Z = Lı´mS˜1;Z,Z (7)
Para despejar los elementos simples de las sustituciones (5) componemos las matrices
B [1]. En la matriz BY el elemento bklij es igual a la multiplicidad del elemento ωj en la
fila yi de la matriz RXkXl incluida en la matriz APG . En la matriz BZ el elemento b
kl
ij es
igual a la multiplicidad del elmento ωi en la columna zj de la matriz RXkXl incluida en
APG . De la misma manera se construyen las matrices B
∗
Y e B
∗
Z por la matriz A
∗
PG∗ .
isomorfismo de conjuntos de relaciones 37
BZ =
z1 · · · zm1 · · · zp · · · zq
ω1
...
ωt
...
ω1
...
ωt

 b
11
11 · · · b111m1
. . .
b11t1 · · · b11tm1
 · · ·
 b
1n
1p · · · r1n1q
. . .
b1ntp · · · b1ntq

. . . . . . . . . b
n1
11 · · · bn11m1
. . .
bn1t1 · · · bn1tm1
 · · ·
 b
nn
1p · · · bnn1q
. . .
bnntp · · · bnntq


BY =
ω1 · · · ωt · · · ω1 · · · ωt
y1
...
ym1
...
yp
...
yq

 b
11
11 · · · b111t
. . .
b11m11 · · · b11m1t
 · · ·
 b
1n
11 · · · r1n1t
. . .
b1nm11 · · · b1nm1t

. . . . . . . . . b
n1
p1 · · · bn1pt
. . .
bn1q1 · · · bn1qt
 · · ·
 b
nn
p1 · · · bnnpt
. . .
bnnq1 · · · bnnqt


Comparando BY con B∗Y , BZ con B
∗
Z , despejamos elementos simples en las sustitu-
ciones (5) y componemos las sustituciones
Sˆ2;Y,Y =
(
ya1 · · · yar {yb1 , . . . , ybh} · · · {yc1 , . . . , ycs}
ya∗1 · · · ya∗r
{
yb∗1 , . . . , yb∗h
}
· · · {yc∗1 , . . . , yc∗s}
)
(8)
Sˆ2;Z,Z =
(
zd1 · · · zdg {ze1 , . . . , zek} · · · {zf1 , . . . , zfl}
zd∗1 · · · zd∗g
{
ze∗1 , . . . , ze∗k
}
· · ·
{
zf∗1 , . . . , zf∗l
} ) (9)
Designando
{yb1 , . . . , ybh} = M1,y, . . . , {yc1 , . . . , ycs} =Mu,y,
{
yb∗1 , . . . , yb∗h
}
=M∗1y, . . . ,
{
yc∗1 , . . . , yc∗s
}
= M ∗u,y
{ze1 , . . . , zek} = M1,z, . . . , {zf1 , . . . , zfl} = Mv,z,
{
ze∗1 , . . . , ze∗k
}
= M∗1,z, . . . ,
{
zf∗1 , . . . , zf∗l
}
= M∗v,z
obtendremos
S˜2;Y,Y =
(
ya1 · · · yar M1,y · · · Mu,y
ya∗1 · · · ya∗r M∗1,y · · · M∗u,y
)
(10)
S˜2;Z,Z =
(
zd1 · · · zdg M1,z · · · Mv,z
zd∗1 · · · zd∗g M∗1,z · · · Mv,z
)
(11)
Designemos tambien por Ni,y, Nj,z, N∗i,y, N
∗
j,z los conjuntos de los sub´ındices de los
elementos de Mi,y,Mj,z,M∗i,y,M
∗
j,z respectivamente. Segu´n (6) y (7) debe cumplirse la
igualdad
∀i, j |Ni,y ∩Nj,z| =
∣∣N∗i,y ∩N∗j,z∣∣ , (12)
38 m. bulat
i ∈ {1, . . . , u} , j ∈ {1, . . . , v}
Si esta condicio´n no se cumple por lo menos para un par (i, j) entonces la hipo´tesis
segu´n la cual se obtuvieron las sustituciones (10) y (11) es falsa.
Supongamos que (12) se cumplen. En este caso se realizan las correspondencias
∀i, jNi,y ∩Nj,z ←→ N∗i,y ∩N∗j,z (13)
∀i, jNi,y\ (Ni,y ∩Nj,z) ←→ N∗i,y\
(
N∗i,y ∩N∗j,z
)
(14)
∀i, jNj,z\ (Ni,y ∩Nj,z) ←→ N∗j,z\
(
N∗i,y ∩N∗j,z
)
(15)
Por medio de estas correspondencias se transforman los conjuntos M de las susti-
tuciones (10) y (11).Si, por ejemplo, Mi,y = {y1, y3, y4} , Mj,z = {z1, z2, z4} ,M∗i,y =
{y4, y5, y6} , M∗j,z = {z3, z5, z6} ,entonces segu´n (13), (14) y (15) se realizan respectivamente
las correspondencias {1, 4} ←→ {5, 6} , {3} ←→ {4} y {2} ←→ {3} . Estas corresponden-
cias implican las correspondencias {y1, y4} ←→ {y5, y6} , {z1, z4} ←→ {z5, z6} , {y3} ←→
{y4} , {z2} ←→ {z3}. De esta manera se obtienen otros conjuntos M. Los conjuntos M
pueden transformarse tambie´n por medio de los elementos simples. Supongamos que se
cumple (16)
{a1, . . . , ar} 6= {d1, . . . , dg} (16)
Segu´n (6) los elementos de la diferencia sime´trica {a1, . . . , ar}4{d1, . . . , dg} transfor-
man los conjuntosM en los cuales pueden aparecer elementos simples. Formando de nuevo
la diferencia sime´trica efectuamos otras transformaciones. Continuamos el proceso hasta
que se cumpla (17).
∀i∃j Ni,y = Nj,z, N∗i,y = N∗j,z (17)
Otras transformacines de (10) y (11) se efectu´an con las matrices C y D [1] y se
construyen las sucesiones de sustituciones con el cumplimiento de (7).
3. Aplicaciones en grafos
Vamos a ver co´mo se aplican los conjuntos de relaciones en la solucio´n del problema del
isomorfismo para grafos.Esta´n dados dos grafos G y G∗por sus matrices de adyacencias o
por sus matrices de los pesos de las aristas. Designemos las filas y las columnas de ambas
matrices por y1, . . . , yn e z1, . . . , zn respectivamente. Supongamos que segu´n una hipo´tesis
se obtienen las sustituciones (10) y (11).
z1 · · · zn
x1 · · · xn
y1 x1
AG =
...
...
yn xn
 a11 · · · a1n. . .
an1 · · · ann

z1 · · · zn
x∗1 · · · x∗n
y1 x
∗
1
AG∗ =
...
...
yn x
∗
n
 a
∗
11 · · · a∗1n
. . .
a∗n1 · · · a∗nn

Designamos
M1,y = X1, . . . ,Mu,y = Xu,M1,z = Xu+1, . . . ,Mv,z = Xu+v
isomorfismo de conjuntos de relaciones 39
M∗1,y = X
∗
1 , . . . ,M
∗
u,y = X
∗
u,M
∗
1,z = X
∗
u+1, . . . ,M
∗
v,z = X
∗
u+v
Se obtienen los conjuntos X = {X1, . . . ,Xu+v} y X∗ =
{
X∗1 , . . . ,X∗u+v
}
para los cuales
se verifican las correspondecias Xi ←→ X∗i , i = 1, 2, . . . , u+ v. Por eso en este caso
SX,X∗ =
(
X1 X2 . . . Xu∗v
X∗1 X∗2 . . . X∗u+v
)
(18)
Por las matrices AG y AG∗ hallamos las matrices RXiXj y R
∗
X∗i X
∗
j
y componemos los
conjuntos de relaciones R y R∗ (i = 1, . . . , u; j = u + 1, . . . , u + v). A estos conjuntos
corresponden dos grafos bipartidos G1 y G∗1.
Los pesos de las aristas son elementos de R y R∗. Si R ∼= R∗ entonces G1 ∼= G∗1 y
G ∼= G∗. Si los conjuntos no son isomorfos entonces la hipo´tesis segu´n la cual se obtu-
vieron las sustituciones (10) y (11) es falsa y tenemos que verificar otra hipo´tesis. De esta
manera el problema del isomorfismo de dos grafos se reduce al problema del isomorfismo
de dos conjuntos de relaciones. Es conveniente hacer esto cuando los grafos son de grandes
taman˜os o cuando las matrices de adyacencias o de pesos de las aristas son homoge´neas.
La investigacio´n de los grafos de grandes taman˜os se reduce a la investigacio´n de grafos
de taman˜os razonables con unas restricciones adicionales que permiten excluir muchas
variantes. Las matrices homoge´neas se reducen a las no homoge´neas (ver Ejemplo 2).
Un sistema de grafos es un conjunto de relaciones y, por eso, lo expuesto puede aplicarse
en la solucio´n del problema del isomorfismo para tales sistemas (ver Ejemplo 1).
4. Aplicaciones en funciones de lo´gicas de k-signos
La funcio´n f (x1, . . . , xn) de una lo´gica de k−signos (3) se puede considerar como
un conjunto de relaciones. Tal funcio´n puede ser prefijada por los conjuntos M εf (ε =
0, 1, . . . , k−1) del modo siguiente:M εf = {α : f(α) = ε} donde α es un cortejo n−dimensional
de k signos (α1, . . . , , αn), αi ∈ {0, 1, . . . , k − 1}, i = 1, . . . , n. Designemos
X = {x1, . . . , xn}
Y0 = {y10, . . . , yp0} =M0f
Y1 = {y11, . . . , yq1} =M1f
................................
Yk−1 = {y1k−1, . . . , yrk−1} =Mk−1f
M = {X,Y0, Y1, . . . , Yk−1}
R = {RY0X , RY1X , . . . , RYk−1X}
Ω = {0, 1, . . . , k − 1}
Igualmente para otra funcio´n f∗(x1, . . . , xn) hallamos el conjunto R∗. A estos conjuntos
corresponden dos grafos bipartidos G y G∗ con sus matrices de adyacencias AG y AG∗ .
AG =
X Y0 · · · Yk−1
X
Y0
...
Yk−1

0 0 · · · 0
1 0 · · · 0
. . .
1 0 · · · 0
 AG∗ =
X∗ Y ∗0 · · · Y ∗k−1
X∗
Y ∗0
...
Y ∗k−1

0 0 · · · 0
1 0 · · · 0
. . .
1 0 · · · 0

40 m. bulat
Para que las funciones sean isomorfas es necesario que se realicen las correspondencias
X ←→ X∗, Y0 ←→ Y ∗o , Y1 ←→ Y ∗1 , . . . , Yk−1 ←→ Y ∗k−1
Es decir
SM,M∗ =
(
X Y0 Y1 · · · Yk−1
X∗ Y ∗0 Y ∗1 · · · Y ∗k−1
)
El sistema de equivalencias por esta sustitucio´n es
RY0X
∼= R ∗Y ∗0 X∗
RY1X
∼= R ∗Y ∗1 X∗
.......................
RYk−1X
∼= R ∗Y ∗k−1X∗
(19)
Es evidente que en este sistema deben verificarse las condiciones
X = X∗, |Y0| = |Y ∗0 | , |Y1| = |Y ∗1 | , . . . , |Yk−1| =
∣∣Y ∗k−1∣∣ (20)
Para hallar la solucio´n del sistema (19) componemos las matrices APG y APG∗ .
APG =
X
Y0
Y1
...
Yk−1

RY0X
RY1X
...
RYk−1X
 APG∗ =
X
Y ∗0
Y ∗1
...
Y ∗k−1

R∗Y ∗0 X
R∗Y ∗1 X
...
R∗Y ∗k−1X

Pasemos a la forma desarrollada y investiguemos las matrices en la equivalencia. Si
e´stas son equivalentes entonces las funciones son isomorfas.
5. Ejemplos
Ejemplo 1 Investigar en el isomorfismo los sistemas de grafos prefijados por
R = {RX1X1,RX2X2 , RX3X3 , RX1X2 , RX2X3 , RX3X1} ,
R∗ =
{
R∗X∗1X∗1 , R
∗
X∗2X
∗
2
, R∗X∗3X∗3 , R
∗
X2X∗1
, R∗X∗1X∗3 , R
∗
X∗3X
∗
2
}
,
X1 = {x11, x21, x31, x41} ,X2 = {x12, x22, x32, x42} ,X3 = {x13, x23, x33, x43} ,
X∗1 = {x∗11, x∗21, x∗31, x∗41} ,X∗2 = {x∗12, x∗22, x∗32, x∗42} ,X∗3 = {x∗13, x∗23, x∗33, x∗43} ,
X = {X1,X2,X3} ,X∗ = {X∗1 ,X∗2 ,X∗3} ,
Ω = {0, 1} ,
isomorfismo de conjuntos de relaciones 41
RX1X1 =
x11x21x31x41
x11
x21
x31
x41

0 1 1 0
1 0 0 1
0 1 0 1
1 0 1 0
 , RX2X2 =
x12x22x32x42
x12
x22
x32
x42

0 0 1 1
1 0 0 1
1 1 0 0
0 1 1 0
 ,
RX3X3 =
x13x23x33x43
x13
x23
x33
x43

0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
 , RX1X2 =
x12x22x32x42
x11
x21
x31
x41

1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
 ,
RX2X3 =
x13x23x33x43
x12
x22
x32
x42

0 1 1 0
1 0 0 0
0 0 1 1
0 1 0 1
 , RX3X1 =
x11x21x31x41
x13
x23
x33
x43

0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
 ,
R∗X∗1X∗1 =
x∗11x
∗
21x
∗
31x
∗
41
x∗11
x∗21
x∗31
x∗41

0 1 0 1
0 0 1 1
1 1 0 0
1 0 1 0
 , R∗X∗2X∗2 =
x∗12x
∗
22x
∗
32x
∗
42
x∗12
x∗22
x∗32
x∗42

0 1 1 0
1 0 0 1
0 1 0 1
1 0 1 0
 ,
R∗X3X∗3 =
x∗13x∗23x∗33x∗43
x∗13
x∗23
x∗33
x∗43

0 0 1 1
0 0 1 1
1 1 0 0
1 1 0 0
 , R∗X∗2X∗1 =
x∗11x∗21x∗31x∗41
x∗12
x∗22
x∗32
x∗42

1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1
 ,
R∗X∗1X∗3 =
x∗13x∗23x∗33x∗43
x∗11
x∗21
x∗31
x∗41

0 1 0 1
0 0 1 1
1 0 0 0
0 1 1 0
 , R∗X3X∗2 =
x∗12x∗22x∗32x∗42
x∗13
x∗23
x∗33
x∗43

0 1 1 0
0 1 1 0
1 0 0 1
1 0 0 1
 .
Solucio´n. Construimos las matrices de adyacencias AG y AG∗ .
AG =
X1X2X3
X1
X2
X3
 1 1 00 1 1
1 0 1
 AG∗ =
X∗1X∗2X∗3
X∗1
X∗2
X∗3
 1 0 11 1 0
0 1 1

Por medio de las matrices C [1] hallamos que AG ∼= AG∗ . El conjunto {SX,X∗} contiene
tres sustituciones:
a)
(
X1 X2 X3
X∗2 X
∗
1 X
∗
3
)
b)
(
X1 X2 X3
X∗1 X
∗
3 X
∗
2
)
c)
(
X1 X2 X3
X∗3 X
∗
2 X
∗
1
)
42 m. bulat
Construimos los sistemas de equivalencias por cada una de estas sustituciones
a)

RX1X1
∼= R∗X∗2X∗2
RX2X2
∼= R∗X∗1X∗1
RX3X3
∼= R∗X∗3X∗3
RX1X2
∼= R∗X∗2X∗1
RX2X3
∼= R∗X∗1X∗3
RX3X1
∼= R∗X∗3X∗2
b)

RX1X1
∼= R∗X∗1X∗1
RX2X2
∼= R∗X∗3X∗3
RX3X3
∼= R∗X∗2X∗2
RX1X2
∼= R∗X∗1X∗3
RX2X3
∼= R∗X∗3X∗2
RX3X1
∼= R∗X∗2X∗1
c)

RX1X1
∼= R∗X∗3X∗3
RX2X2
∼= R∗X∗2X∗2
RX3X3
∼= R∗X∗1X∗1
RX1X2
∼= R∗X∗3X∗2
RX2X3
∼= R∗X∗2X∗1
RX3X1
∼= R∗X∗1X∗3
Resolvemos el sistema a). Construimos las matrices APG y A
∗
PG∗ .
APG =
z1 z2 z3 z4 z5 z6 z7 z8 z9 z10 z11 z12
x11 x21 x31 x41 x12 x22 x32 x42 x13 x23 x33 x43
y1
y2
y3
y4
x11
x21
x31
x41
y5
y6
y7
y8
x12
x22
x32
x42
y9
y10
y11
y12
x13
x23
x33
x43


0 1 1 0
1 0 0 1
0 1 0 1
1 0 1 0


1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1


∗ ∗ ∗ ∗
∗ ∗ ∗ ∗
∗ ∗ ∗ ∗
∗ ∗ ∗ ∗


∗ ∗ ∗ ∗
∗ ∗ ∗ ∗
∗ ∗ ∗ ∗
∗ ∗ ∗ ∗


0 0 1 1
1 0 0 1
1 1 0 0
0 1 1 0


0 1 1 0
1 0 0 0
0 0 1 1
0 1 0 1


0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0


∗ ∗ ∗ ∗
∗ ∗ ∗ ∗
∗ ∗ ∗ ∗
∗ ∗ ∗ ∗


0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0


APG∗ =
z1 z2 z3 z4 z5 z6 z7 z8 z9 z10 z11 z12
x∗12 x
∗
22 x
∗
32 x
∗
42 x
∗
11 x
∗
21 x
∗
31 x
∗
41 x
∗
13 x
∗
23 x
∗
33 x
∗
43
y1
y2
y3
y4
x∗12
x∗22
x∗32
x∗42
y5
y6
y7
y8
x∗11
x∗21
x∗31
x∗41
y9
y10
y11
y12
x∗13
x∗23
x∗33
x∗43


0 1 1 0
1 0 0 1
0 1 0 1
1 0 1 0


1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1


∗ ∗ ∗ ∗
∗ ∗ ∗ ∗
∗ ∗ ∗ ∗
∗ ∗ ∗ ∗


∗ ∗ ∗ ∗
∗ ∗ ∗ ∗
∗ ∗ ∗ ∗
∗ ∗ ∗ ∗


0 1 0 1
0 0 1 1
1 1 0 0
1 0 1 0


0 1 0 1
0 0 1 1
1 0 0 0
0 1 1 0


0 1 1 0
0 1 1 0
1 0 0 1
1 0 0 1


∗ ∗ ∗ ∗
∗ ∗ ∗ ∗
∗ ∗ ∗ ∗
∗ ∗ ∗ ∗


0 0 1 1
0 0 1 1
1 1 0 0
1 1 0 0


Al investigar las matrices sobre equivalencia por medio de las matrices B y C hallamos
las sustituciones
SY,Y =
(
y1 y2 y3 y4 y5 y6 y7 y8 y9 y10 y11 y12
y4 y3 y1 y2 y5 y7 y8 y6 y9 y12 y10 y11
)
isomorfismo de conjuntos de relaciones 43
SZ,Z =
(
z1 z2 z3 z4 z5 z6 z7 z8 z9 z10 z11 z12
z4 z3 z1 z2 z5 z7 z8 z6 z9 z12 z10 z11
)
La condicio´n (7 ) se cumple. Por lo tanto APG ∼= A∗PG∗ ,el sistema a) es compatible y
los sistemas de grafos son isomorfos y no es necesario resolver los sistemas b) y c). De las
sustituciones obtenidas resulta la solucio´n del sistema a):
SX1X∗2 =
(
x11 x21 x31 x41
x∗42 x∗32 x∗12 x∗22
)
, SX2X∗1 =
(
x12 x22 x32 x42
x∗41 x∗31 x∗11 x∗21
)
,
SX3X∗3 =
(
x13 x23 x33 x43
x∗43 x∗33 x∗13 x∗23
)
Por medio de estas sustituciones un sistema de grafos se transforma en otro.
Ejemplo 2 Investigar en el isomorfismo los grafos G y G∗ prefijados por las matrices AG
y AG∗ de los pesos de las aristas:
AG =
z1 z2 z3 z4 z5 z6 z7 z8 z9
x1 x2 x3 x4 x5 x6 x7 x8 x9
y1 x1
y2 x2
y3 x3
y4 x4
y5 x5
y6 x6
y7 x7
y8 x8
y9 x9

Σ Σ Σ ∆ ∆ ∆ Φ Φ Φ
Φ Σ Σ Σ ∆ ∆ ∆ Φ Φ
Φ Φ Σ Σ Σ ∆ ∆ ∆ Φ
Φ ∆ Φ Σ Σ Σ Φ ∆ ∆
∆ Φ Φ ∆ Σ Σ Σ Φ ∆
∆ Φ Φ Φ ∆ Σ Σ Σ ∆
∆ ∆ ∆ Φ Φ Φ Σ Σ Σ
Σ ∆ ∆ ∆ Φ Φ Φ Σ Σ
Σ Σ ∆ Φ Φ Φ ∆ ∆ Σ

AG∗ =
z1 z2 z3 z4 z5 z6 z7 z8 z9
x1 x2 x3 x4 x5 x6 x7 x8 x9
y1 x1
y2 x2
y3 x3
y4 x4
y5 x5
y6 x6
y7 x7
y8 x8
y9 x9

Σ Φ ∆ Φ Σ ∆ Σ Φ ∆
∆ Σ Φ Σ ∆ Φ ∆ Φ Σ
∆ Σ Σ Σ Φ Φ ∆ Φ ∆
Σ Φ Φ Σ ∆ Φ ∆ ∆ Σ
Φ ∆ ∆ ∆ Σ Σ Φ Σ Φ
Φ Σ Σ ∆ ∆ Σ Φ ∆ Φ
∆ Φ ∆ Φ Σ ∆ Σ Σ Φ
Φ ∆ Σ ∆ Φ Σ Φ Σ ∆
Σ ∆ Φ Φ Φ ∆ Σ ∆ Σ

Solucio´n. Ω = {Σ,Φ,∆} . Los grafos son homoge´neos. Por eso desde el principio las
matrices B no sirven para despejar los elementos simples. Designamos por y1, . . . , y9 las
filas y por z1, . . . , z9 las columnas de las matrices. Las primeras sustituciones mu´ltiples
son:
S˜1;Y,Y =
( {y1, y2, y3, y4, y5, y6, y7, y8, y9}
{y1, y2, y3, y4, y5, y6, y7, y8, y9}
)
S˜1;Z,Z =
( {z1, z2, z3, z4, z5, z6, z7, z8, z9}
{z1, z2, z3, z4, z5, z6, z7, z8, z9}
)
44 m. bulat
Sea y1 ←→ y1. Entonces segu´n (4) z1 ←→ z1. Construimos la tabla T1 de las matrices
C (la parte de arriba).
G y2y3y4y5y6y7y8y9 z2z3z4z5z6z7z8z9 G
∗ y2y3y4y5y6y7y8y9 z2z3z4z5z6z7z8z9
y1 ΣΣ∆∆∆ΦΦΦ y1 Φ∆ΦΣ∆ΣΦ∆
z1 ΦΦΦ∆∆∆ΣΣ z1 ∆∆ΣΦΦ∆ΦΣ
G y2y3y4y5y6y7y8y9 z2z3z4z5z6z7z8z9 G
∗ y1y3y4y5y6y7y8y9 z1z3z4z5z6z7z8z9
y1 ΣΣ∆∆∆ΦΦΦ y2 ∆ΦΣ∆Φ∆ΦΣ
z1 ΦΦΦ∆∆∆ΣΣ z2 ΦΣΦ∆ΣΦ∆∆
G y2y3y4y5y6y7y8y9 z2z3z4z5z6z7z8z9 G
∗ y1y2y4y5y6y7y8y9 z1z2z4z5z6z7z8z9
y1 ΣΣ∆∆∆ΦΦΦ y3 ∆ΣΣΦΦ∆Φ∆
z1 ΦΦΦ∆∆∆ΣΣ z3 ∆ΦΦ∆Σ∆ΣΦ
T1
De esta tabla se obtienen las sustituciones
Sˆ2;Y,Y =
(
y1 {y2, y3, y4} {y5, y6, y7} {y8, y9}
y1 {y5, y6, y8} {y2, y3, y7} {y4, y9}
)
y
Sˆ2;Z,Z =
(
z1 {z4, z5, z6} {z7, z8, z9} {z2, z3}
z1 {z3, z6, z9} {z2, z4, z8} {z5, z7}
)
Observamos que |{2, 3, 4} ∩ {7, 8, 9}| 6= |{5, 6, 8} ∩ {2, 4, 8}|. Es decir la condicio´n (12)
no se cumple. Por eso z1 ←→ z1 e y1 ←→ y1 no existen. Ana´logamente hallamos que
tampoco existen z1 ←→ z2 e y1 ←→ y2. Examinemos las correspondencias z1 ←→ z3 e
y1 ←→ y3. De T1 (la parte de abajo) resulta que
Sˆ4;Y,Y =
(
y1 {y2, y3, y4} {y5, y6, y7} {y8, y9}
y3 {y2, y4, y9} {y1, y5, y7} {y6, y8}
)
y
Sˆ4;Z,Z =
(
z1 {z4, z5, z6} {z7, z8, z9} {z2, z3}
z3 {z1, z7, z9} {z5, z6, z8} {z2, z4}
)
Para estas sustituciones la condicio´n (12) se cumple. Aplicando (13), (14) y (15) se
obtiene:
Sˆ4;Y,Y =
(
y1 y4 y7 {y2, y3} {y5, y6} {y8, y9}
y3 y9 y5 {y2, y4} {y1, y7} {y6, y8}
)
y
Sˆ4;Z,Z =
(
z1 z4 z7 {z2, z3} {z5, z6} {z8, z9}
z3 z9 z5 {z2, z4} {z1, z7} {z6, z8}
)
Las condiciones (20) se cumplen. Construimos las matrices de los pesos y las matrices B.
APG1 =
z2 z3 z5 z6 z8 z9
y2
y3
y5
y6
y8
y9

[
Σ Σ
Φ Σ
] [
∆ ∆
Σ ∆
] [
Φ Φ
∆ Φ
]
[
Φ Φ
Φ Φ
] [
Σ Σ
∆ Σ
] [
Φ ∆
Σ ∆
]
[
∆ ∆
Σ ∆
] [
Φ Φ
Φ Φ
] [
Σ Σ
∆ Σ
]

isomorfismo de conjuntos de relaciones 45
APG∗1
=
z2 z4 z1 z7 z6 z8
y2
y4
y1
y7
y6
y8

[
Σ Σ
Φ Σ
] [
∆ ∆
Σ ∆
] [
Φ Φ
Φ ∆
]
[
Φ Φ
Φ Φ
] [
Σ Σ
∆ Σ
] [
∆ Φ
∆ Σ
]
[
Σ ∆
∆ ∆
] [
Φ Φ
Φ Φ
] [
Σ ∆
Σ Σ
]

BY =
Σ Φ ∆ Σ Φ ∆ Σ Φ ∆
y2
y3
y5
y6
y8
y9

[
2 0 0
1 1 0
] [
0 0 2
1 0 1
] [
0 2 0
0 1 1
]
[
0 2 0
0 2 0
] [
2 0 0
1 0 1
] [
0 1 1
1 0 1
]
[
0 0 2
1 0 1
] [
0 2 0
0 2 0
] [
2 0 0
1 0 1
]

B∗Y =
Σ Φ ∆ Σ Φ ∆ Σ Φ ∆
y2
y4
y1
y7
y6
y8

[
2 0 0
1 1 0
] [
0 0 2
1 0 1
] [
0 2 0
0 1 1
]
[
0 2 0
0 2 0
] [
2 0 0
1 0 1
] [
0 1 1
1 0 1
]
[
1 0 1
0 0 2
] [
0 2 0
0 2 0
] [
1 0 1
2 0 0
]

BZ =
z2 z3 z5 z6 z8 z9
Σ
Φ
∆
Σ
Φ
∆
Σ
Φ
∆

 1 21 0
0 0
  1 00 0
1 2
  0 01 2
1 0
 0 02 2
0 0
  1 20 0
1 0
  1 01 0
0 2
 1 00 0
1 2
  0 02 2
0 0
  1 20 0
1 0


B∗Z =
z2 z4 z1 z7 z6 z8
Σ
Φ
∆
Σ
Φ
∆
Σ
Φ
∆

 1 21 0
0 0
  1 00 0
1 2
  0 02 1
0 1
 0 02 2
0 0
  1 20 0
1 0
  0 10 1
2 0
 1 00 0
1 2
  0 02 2
0 0
  2 10 0
0 1


De Sˆ4;Y,Y e Sˆ4;Z,Z y de las matrices B resultan las sustituciones simples:
SZ,Z =
(
z1 z2 z3 z4 z5 z6 z7 z8 z9
z3 z2 z4 z9 z1 z7 z5 z8 z6
)
SY,Y =
(
y1 y2 y3 y4 y5 y6 y7 y8 y9
y3 y2 y4 y9 y1 y7 y5 y8 y6
)
46 m. bulat
Hemos obtenido dos sucesiones convergentes [1] para las cuales se cumple (7). Por con-
siguente G1 ∼= G∗1 y G ∼= G∗.
6. Conclusio´n
Lo expuesto se puede aplicar:
1. En sistemas algebraicos [3, 4],
2. En la solucio´n del problema del isomorfismo:
a) para grafos y hipergrafos de grandes taman˜os [3, 6],
b) para sistemas de grafos y hipergrafos,
c) para grafos homoge´neos [5, 6],
d) para funciones lo´gicas y sistemas de ellas [2].
Ser´ıa bueno aplicar matrices multidimensionales en la resolucio´n de sistemas de equi-
valencias. En este dominio todav´ıa faltan investigaciones.
Referencias
[1] Bulat, M. (1998) “Isomorfismo de grafos y de funciones lo´gicas con algunas aplica-
ciones”, Revista de Matema´tica: Teor´ıa y Aplicaciones 5(2): 87–112.
[2] Bulat M.S.; Goryuk I.V. (1978) S´ıntesis de Estructuras Lo´gicas Instituto Polite´cnico
de Kishinev. (En ruso).
[3] Gorba´tov, V.A. (1988) Fundamentos de la Matema´tica Discreta. Editorial MIR, Moscu.
[4] Ma´ltsev, A.I. (1970) Sistemas Algebraicos. Editorial NAUKA, Moscu (en ruso).
[5] Skliar, O.; Lascaris, T.; Medina, V. (1994) “Enfoque compartimental para la solucio´n
del problema del isomorfismo de grafos”, in: G. Mora (Ed.) II Encuentro Centroame-
ricano de Investigadores en Matema´ticas, I parte, Sede de Occidente UCR: 113–131.
[6] Zykov, A.A. (1987) Fundamentos de la Teor´ıa de los Grafos. Editorial NAUKA,
Moscu´ (en ruso).