在反馈节点集上求布尔网络的不动点及其应用

摘要

布尔网络是自然和人造的非线性动态网络的一种紧凑模型，近年来，对于有关布尔网络的研究受到了人们的广泛关注.布尔网络是一个有向图，但是与一般图的的区别是:布尔网络中节点的状态变量取值只能是“0”或“1”，关于布尔网络的相关计算都是在二元布尔代数上进行的.需要注意的是这里的“0”和“1”不再是单纯的数字，而是符号.形式逻辑中命题的“真”和“假”，开关网络中出现的有电与无电，高压与低压，导通与截止等，都可以视为二元布尔代数中两个元素“1”和“0”的现实模型.由于现实生活中的网络模型并不总是强连通的，当这些网络不特殊的时候，我们希望用更少的条件来找到它们的不动点.
　　本文主要研究了一类布尔网络，首先根据有向图中节点的等价关系，把布尔网络分成了若干个极大强连通子网，并为子网进行编号；基于子网的反馈节点集，给出了为每个子网构造对应新子网的算法，这些新子网也合成了新网络；由此，证明了原布尔网络的不动点与新布尔网络的不动点相同.然后，通过新增加的反馈节点集中节点的树形函数，给出了求解布尔网络不动点的一个充分必要条件，即:在新构造网络的基础上，通过移动网络中的弧，使其变为非循环网络，按照节点的拓扑排序，给出了为新增加的反馈节点集中节点构造树形函数的算法；在此基础上，利用状态变量和节点的树形函数所满足的方程，给出了确定不动点的必要条件以及条件加强下的求解不动点的充分条件.从而用更少的方程和更少的条件给出了求解布尔网络不动点的充要条件.

目录

声明

摘要

引言

第一章 预备知识

1．1 有向图

1．2 布尔代数

1．3 布尔网络

1．4 反馈节点集

第二章 通过新布尔网络确定原网络的不动点

2．1 构造新网络的算法

2．2 算法分析和具体的例子

2．3 新网络与原网络不动点之间的关系

第三章 确定布尔网络不动点的充要条件

3．1 构造树形函数的算法

3．2 在反馈节点集上给出确定不动点的充要条件

3．3 数值例子

结论

参考文献

后记