Video在线视频

下面我来介绍有向网

叫做directed net

一个有向网呢是一个三元组

有三部分组成S T或F

大家注意在这里是个分号

这个分号的意思是什么呢

这个F是用S或T定义出来的

它不是独立的

一个三元组我们给它起个名字叫做N

所以这个N呢是一个有向网

这个有向网要满足一定的条件才行

不是说随便三个东西就能叫做有向网

首先S或T加起来

一定要至少有一个元素

它不能是个空集

说我这个空集里面

我这有个网那不行

至少得有一个元素

另外S或T它没有公共元素

所以这是两类不同的元素

F就是用S或T构造出来的

它可以沟通S或T

也可以T到S这是笛卡尔积

S×T或T×S是不同的

但是不能够S×S T×T

所以这是两种关系

一个是从S到T一个是从T到S

另外底下这一行

dom(F)和cod(F)加起来

一定要等于S或T

dom是什么呢

是这个F的定义语

cod是它的支语

两个加起来不能有孤立元素

所以要么S要么在T里面

要么在dom里面 要么在cod里面

要么在两个里面都有

但是不能孤立元素

所以我们这个叫做没有孤立元素

这是dom跟cod的定义

我就不多说了

另外请大家思考一个问题

像这样的一个定义

是不是形式化的定义呢

往往大家都会把这

当做一个形式化的定义

但是这个不是

这是一个半形式化的定义

为什么 因为这里面有自然语言

自然语言你就是把它换成英文

一个中国字没有

它也是半形式化的

那么什么是形式化的呢

形式化的定义是这样的

我们定义了一个谓词

一个三元谓词这个三元谓词

要符合下面这个条件

用这四个来定义它

一个叫做S ∪ T ≠空 S ∩ T =空

另外就是这两个公式

刚才我们看到过的

这是什么意思呢

如果这四个布尔表达式都成真的话

因为这都是 ∧ 联系在一起

那么这个谓词呢就成真

如果其中只要有一个不成真

那么这个就不是一个成真的谓词

那么这个三元组呢

就不是一个有向网

这个形式化的定义有什么好处呢

就是它完全没有自然语言

完全是数据化的

我们举个例子

比方说S有四个元素c x q d

大家一看可能有点眼花

怎么这个乱七八糟的这么些字母

其实我一说你就明白了

c呢是春天 这x呢是夏天

q呢是秋天 这个d呢是冬天

咱们的拼音第一个字母

然后这个T呢就是四个季节的变化

所以从c从春到夏 从夏到秋

从秋到冬 从冬又到春

然后这个联系呢

一会我们看图就更清楚了

所以这三元组就构成一个网

我们叫做N1第一个网

好 有向网呢

我们为什么叫它一个网

因为它画出来

它有一个图形表示

画出来会像一张网的样子

首先这个S元素呢

我们一般是用一个圆圈表示

这个T元素呢用一个方框表示

然后F呢是用一个箭头表示

这个S元素呢英文叫做place

这个中文呢我给它翻译成叫做库所

下面我会解释为什么叫库所

它是一个类似于仓库的地方

它储存同类的东西

但是它没有固定的位置

所以不能

有人把它翻译成地址那不对的

然后transition呢是个变迁

变迁是变化

变化呢我们Petri网的变化呢

包括了质变和量变在内

所以叫做变迁 不是迁移

有人把它翻译成迁移

迁移只是移动搬家了这个不是

既有质变还有量变

F呢是流关系

就是资源在我们这个网上的流动

咱们看一个网

这就是刚才我说的

春夏秋冬的变化

这是春夏秋冬

然后有四个变化的元素四个变迁

从春到夏 从夏到秋

从秋到冬等等

所以这就是一个网

看看是不是有点像个网了

我这个网站只有一个眼

一个网眼

这是第二个例子这个例子呢

就更像一个网了

也像一张棋盘了

刚才我们不是说

有向网像个棋盘吗

你看看是不是像个棋盘

这是第二个网 你看三个元素

红的是S元素库所

这个黑的方框是变迁

然后呢箭头

代表了这个资源的流动

好我们来分析一下这些表达方法

我们现在有半形式化的定义

形式化的定义 还有图形表示

半形式化的定义呢

是叫做Friendly是友好的

因为大家读起来比较容易懂

而形式化的定义呢

是用来做自动化处理的

所以你要在计算机上开发一个程序

用这个形式化定义呢容易处理

不需要自然语言理解了

那么图形表示呢直观

人跟人交流起来比较容易

而且你不需要给它起名字了

这个方法呢有这三种

各有各的好处

现在我问一个问题

这个图这是它的图形表示

这个呢是它的半形式化的表示

就是一个三元组

你看两个元素 一个元素 两个元素

两个S元素 一个T元素 两个箭头

这个是它的图形表示吗

那么初学的时候可能会

在这些问题上有点纠结

其实无所谓

这个就是它的图形表示

只不过呢这里写了个P1

这是用了个S1

在同构意义上来讲

这个网跟它是一样的

什么叫同构 一一对应

所以S1对应P1 S2对应P2

P对应这个T 就完全一样了

下面一个问题这是一个有向网吗

有两个s元素 两个t元素 两个箭头

这是一个吗

回答是是 也不是

因为我们的定义里面呢

没有说它一定是连通的连着的

所以你可以把它

看成是一个有向网

你也可以把它看成两个

如果你把它看成一个是两部分

这两部根本没有联系

你何必把它放在一起研究呢

所以这个是一个也对两个也对

看你的应用需要什么

好 下面我们看

刚才我讲的就是连通性

这个Petri网里面呢

有向网里面没有定义

它是连通还是不连通

这个呢是叫做弱连通

就是从任何一个元素

到另外一个元素都能够连上

为什么叫弱连通呢

你去掉一个箭头它就连不上了

这叫弱连通

这个呢是强连通

因为你去掉一个箭头

它还是连着的

底下这个呢 连通吗

不连通了

因为这两个没有没有弧连着是不是

思考一下啊

我们把有向网的定义说了

它的三种表示说了现在我问大家

这个有向网允许这种结构吗

允许这种结构吗

这两个应该是说没有问题

它是允许的

但是这个呢

这个在按照有向网的定义是不允许的

两个就是x y它只能出现一次

在这个集合里面

在f它是一个集合

集合里面只能出现一次

所以这个呢是不允许的

这种叫做不单纯的结构

这种呢叫做不简单的结构

因为它这两个Y1 Y2

完全一样没有区别

所以叫不简单的

这个呢是有这种环 自环

这个呢叫做不单纯的

我们定义一些符号一些术语

然后方便我们下面用

我们把X S或T把它做成一个集合

这是有向网的所有元素的集合

x跟y呢是两个节点

T元素也好S元素也好

什么叫做x这个节点的前集呢

就是有一个箭头从y指到x

那么所有这些y组成的集合

就是x的前集

用这x的左上角有一个点表示

这个是它的后集

箭头从x出发指向的那些节点

叫做x的后集

咱们用x后面一点来表示

好 刚才我已经提到了单纯性

这个非单纯性 简单 非简单

那么单纯网简单网呢

就可以定义出来了

刚才我说了不允许这个重复弧

下面一个问题我又问大家

有向网一定是有限的吗

能不能包含无穷多个元素呢

这个要求在我们的

定义里面是没有的

所以一个有向网

可以有 有限多个元素

也可以有无穷多个元素

甚至于是不可数的无穷多个元素

那么如果这里有限多个元素呢

我们叫它有限网

如果它有无穷多个元素呢

叫做无限网

有限网是

什么时候我们能够发现

用得着有限网

凡是人造的系统都是有限网

因为人创造不出无穷的东西来

你数都数不过来

还有我们观察自然

我们只观察了自然界的一部分

像四季那么它是一个有限网

那么无限网呢就是

描述的是无始无终的自然变化

比方说还有理论研究像图灵机

它是个无限的东西

这个呢是另外一种网

刚才我们讲的那个网呢

是表现了它的出现的规律

就是春夏秋冬周而复始

这个呢是我们做的记录

比方说16年的春天

然后到了16年的夏天

到了16年的秋天 到了16年冬天

然后到17年 前面是15年

那么这个呢

叫做一个特殊的有向网

叫做出现网

我们把出现的现象记录下来

这个呢叫做出现网

这也是我们要用到的

一种特殊的网

有了这么多的定义以后

我跟大家讲

基础概念定义的金律

就是你要想定义一个基础概念

一定要记住这句话

在你的定义里面

没有必要包含的

就有必要不包含

这个是从哪儿来的呢

这是我从官场定律里头

吸取来的精髓

做官的有一个官场定律

叫做什么没有必要决定的

就有必要不决定

咱们这呢是

没有必要包含的 就有必要不包含

你看我们这个有向网的定义里面

没有包含连通性

单纯性 简单性 有限性

因为无 所以我们就可以把这些性质

根据我们的需要加进去

所以我说叫做因为无所以有

如果你一开始就把它放在定义里面

那你以后就去不掉了

你要想着灵活的组合组合不了了

所以呢按照那个

定义基础固定的金律

我们就有这样的收获

因为我这里面只包含必要的东西

所以其它的

我就可以根据需要来随时增加

这样呢我们的基础概念很简洁

可以灵活的引进新的东西

比方说有一个自由选择网

这个我不说 自由选择网

如果你有兴趣你可以去查查文献

这种网呢 我觉得是人为造出来的

跟实际有点脱节 所以我不介绍了

好 刚才我说因为无所以有是吧

我们现在来从无到有

有向网分类比方说简单网

我就说两个元素

如果它的前集相等

它的后集相等

它就是统一的元素

这叫简单网没有不同的

就是两个元素结构上完全一样

但是是两个元素

没有 这叫简单网

单纯网如果没有

这个前集和后集一个自环

这就叫单纯网

连通网那么它的

如果把那个箭头的方向忘掉

变成一个图

那么它就是一个连通图

那么有限网就是

S元素和T元素加起来

它的个数是有限的小于无穷

然后我们可以引进新的东西

有两个有向网

我把它关联起来

这两个都是有向网

这两个有向网我们说是对偶的

什么意思呢

就是一个的S元素

是另一个的T元素

一个T元素

是另一个的S元素箭头不变

这两个网叫做对偶的

这个对偶概念呢

在BPM叫做工作流网里面

起很大的作用

另外叫互逆的

这个S元素T元素是一样的

但是箭头呢倒过来了

在这个网里面是从a到b

从那个另外一个网呢从b到a

这就叫做逆网 互逆的两个网

比方说举个例子

这个网或这个网

S元素变成了T元素

T元素变成了S元素

所以这两个网是互相对偶的

箭头没有变

这个你看这个箭头是这

这个箭头倒过来了

这个箭头是这样的

这个箭头倒过来了

所以这两个网呢就是互逆的

这个是两个概念

好 咱们在图形表示 在多说一点

比方说这两个 是同一个网吗

这个S1在这

这个S1画在后面去了

这个S2在前面 这个S2在后面

这两个网图形看上去是一样的

名字也是一样的

这两个网是一个网吗

当然是一个网对不对

只是我画的不一样

这是为什么刚才我说

我们那个叫库所

不叫位置为什么呀

这个位置根本跟这个网没关系

你画在哪里都行

你这样曲里拐弯的画

它也还是同一个网

像我们这样画成弯曲的

它仍然是这同一个网

它的定义的三元组是完全一样的

都是这个网

就是两个S元素

一个T元素两个箭头

它都是这同一个

有向网的这个图形表示

所以这个位置不重要