网论

官方信息技术老师·13 页·深入(追求细节与边界)·0 次浏览·3 天前
图论欧拉回路图着色网络流

网论

理清图论核心定理的证明脉络:看清每一步推理,也看清每一条适用边界

按 空格/→ 演示下一步

1 / 13 页

全部页面点击任意一页,跳回舞台从这页播放

图论欧拉回路图着色网络流

网论

理清图论核心定理的证明脉络:看清每一步推理,也看清每一条适用边界

1第 1 页 · 网论

前言

你手机里的 Wi-Fi 列表、微信好友推荐、大脑神经元放电——背后都是「一堆东西互相连着」的结构。网论,就是把这套结构抽出来、用数学统一描述的学科。

定义
以节点与边的数学语言刻画关系结构,研究其性质与演化
两类对象
现实系统(互联网/社交网)↔ 抽象图模型(图论/随机图)
两个维度
静态结构(度分布/连通性)↔ 动态过程(传播/同步/博弈)
典型应用
社交网络、生物网络、交通网、电力网、信息推荐系统
城市地铁线路图对应 →网论基本模型

站点=节点,线路=边;换乘站对应度大的枢纽节点

2第 2 页 · 前言

网拓扑

北京地铁图你一定看过:线路交错,站点密密麻麻。但你从图里读到的不是地理形状,而是「哪一站能换到哪一站」。网论把这种「只看连接关系、不在乎具体位置」的结构,叫网拓扑。

拓扑抽象
节点画在哪不重要,只保留「谁连谁」这个连接关系本身
节点与边
节点是研究对象(人、基因、站点),边是它们之间的联系
拓扑量
度、路径长度、聚类系数、直径——刻画结构形态的尺子
应用场景
社交关系、生物神经网络、电力/交通网、互联网均在其研究范围
地铁线路图对应 →网拓扑

站点位置无所谓,能不能换乘才是关键——拓扑只关心连通关系

3第 3 页 · 网拓扑

并发论

网络拓扑讲的是节点之间「谁连着谁」的静态形状。但网络真正跑起来时,每个节点都在同时收发、同时计算。这种「多件事同时发生」的规律与机制,就是并发论研究的对象。

并发与并行
并发是逻辑上同时(交错推进),并行是物理上同时(多核多机)
交错与不确定性
行为是所有可能执行路径的集合,而非单一确定路径
同步原语
锁、信号量、消息传递、屏障等,用于约束并发活动
典型应用
分布式系统、网络协议栈、多核调度、数据库事务等
多位厨师共用一个厨房对应 →并发进程共享资源

争灶台=资源竞争,叫号=同步,出菜顺序不定=交错语义

4第 4 页 · 并发论

网逻辑

并发论里我们看到,多节点同时发生的事很难谈先后。网逻辑要回答:没有统一时钟,怎么给分布式事件定义顺序?

因果序
本地顺序加消息传递,定义「a 发生在 b 之前」的偏序关系
逻辑时钟
无需同步物理时钟,给每个事件打上单调递增的逻辑时间戳
偏序而非全序
无因果关系的并发事件不可比,强求全序需额外协议如全序广播
一致性约束
所有节点对因果序的判断必须一致,是分布式系统的逻辑底线
快递签收单对应 →因果序与逻辑时钟

寄出是「自报时刻」,签收是「因果确认」——每环都依赖上一环

5第 5 页 · 网逻辑

信息流网

去医院看病,挂号单、病历、检查报告在医患间流转——每一步携带的不只是"轮到我没"这种状态,而是具体的姓名、症状、数据。网论里专门刻画这种"带内容"的流转的模型,就叫信息流网。

信息令牌
库所里的"东西"不再是无名记号,而是有类型、有取值的具体信息项
守卫与赋值
变迁附带守卫函数与赋值动作:先看输入信息是否满足,再决定产出或改写
数据驱动路由
变迁是否触发、产出哪些输出,由令牌携带的实时内容决定
与控制流分离
信息流管"传什么",控制流管"何时做":实际系统常并存这两类网
办公室公文流转对应 →信息流网

公文就是携带信息的令牌:每经一个部门(变迁)就可能被审阅、批注、改写

6第 6 页 · 信息流网

同步论

上一页讲到信息沿网流动,但工厂里老师傅说「三件齐了再动手」——这种「齐」正是同步论要回答的:并发流如何汇成一步?

同步事件
变迁有多个输入库所,每个都得有托肯才触发,把多条流汇成一步
同步距离 σ
两个变迁触发次数之差的最大值,量化「靠得多紧」
同步关系分级
按距离划分:完全同步、互斥、冲突,刻画变迁间依赖
冲突与边界
多变迁争抢同一托肯时网不能定夺——同步论的外部边界
乐队合奏对应 →网中同步事件

乐手各自演奏(并发流),小节末必须对齐节拍——对齐点即同步事件

σ(t1,t2)=max{#t1#t2}\sigma(t_1, t_2) = \max\{|\#t_1 - \#t_2|\}
7第 7 页 · 同步论

同步论-合同实例

两个部门合作:市场部承诺'下单三天内发货',生产部承诺'收到订单后生产'——这些承诺就是合同。把它们画成具体的网,让计算机验证真能做到,就叫合同实例。

合同三要素
义务、假设与保证构成一份完整合同
实例化
把抽象合同落地为具体Petri网
实现关系
实例的每条执行路径都要兑现合同承诺
多级精化
抽象合同可逐级细化到具体实例
工程项目合同对应 →合同与实例

甲乙双方的承诺条款对应义务与保证;图纸落地施工对应抽象合同实例化为具体网

IC    L(C)L(I)I \models C \iff L(C) \subseteq L(I)
8第 8 页 · 同步论-合同实例

同步论-婚礼教堂实例

上一节合同实例里,新郎新娘按顺序交接文件,那是顺序协作。这节换成婚礼现场——两位新人从两个方向同时赶往教堂,牧师要等他们「都到齐」才能主持仪式。这正是同步论最经典的形态。

双向独立进程
新郎、新娘各自从不同路径走向教堂,两个进程互不依赖
AND-同步转移
ceremony 转移的每个输入库所都必须有 token 才可触发
原子触发
一次 firing 同时消费两路 token,要么都到、要么都不发生
同步是并发的对偶
并发=路上各走各的;同步=等到齐再一起迈出下一步
婚礼现场两人到齐才开席对应 →多入弧 transition 的同步触发

牧师=transition,两路 token=两位新人,必须同时就位才一次 firing

M[tpt:M(p)1M[t\rangle \Leftrightarrow \forall p \in {}^\bullet t\,{:}\,M(p) \geq 1
9第 9 页 · 同步论-婚礼教堂实例

同步论 同步器

上页讲了同步论关注「如何让分散的变迁协同行动」,本页落到具体工具——同步器。它就像音乐里的节拍器,把不同声部对齐到共同的拍点上。

定义与角色
同步器是网论里实现协同引发的一类标准子网,可作为「积木」插入主子网
三种基本类型
AND 同步、OR 同步、仲裁同步,分别对应全齐才发、任一即发、互斥选择
构造机制
依靠测试弧读而不耗,或抑制弧在条件不具备时才允许引发
性质保持边界
同步器自身有界且安全,但与无死锁主子网组合后,性质需另行验证
集合点等齐人再出发对应 →AND 同步器

所有队员都到齐才迈步,对应所有前置变迁都引发才触发后继动作

10第 10 页 · 同步论 同步器

建模方法论

前面同步器只抓住“双方如何配合”;建模时还要回答:谁在何种条件下行动、动作怎样改变状态,以及系统边界。

模型边界
先确定对象、环境与观察尺度,区分系统内外。
要素映射
把状态或条件表示为库所,把事件或动作表示为变迁;资源用令牌或容量表达。
关系约束
用有向流连接库所与变迁,表达依赖和输入输出;必要时加入守卫、容量和优先级。
执行规则
规定初始标识、使能条件和触发后的状态更新,模型才能重演并接受分析。
验证应用
检查可达性、死锁、活性等性质,并将模型用于合同、婚礼和并发任务。
仓库分拣对应 →网模型

货架是库所,叉车动作是变迁,托盘货物是令牌;传送路线和检查规则对应结构与约束。

MtM=MI(t)+O(t)\mathbf{M} \xrightarrow{t} \mathbf{M}' = \mathbf{M} - I(t) + O(t)
11第 11 页 · 建模方法论

本节要点

  • 网图统一承载拓扑结构与动态行为
  • 并发是局部使能与全局约束的张力
  • 同步即多类资源在共享节点交汇
  • 信息流与物流可在同一网中同构建模
  • 建模是场景—网—分析—简化的迭代
延伸主题:不变量与活性分析时间网与着色 Petri 网层级网与模块化建模
12第 12 页 · 本节要点

课后思考

先合上屏幕,用三分钟独立想清楚每个问题;再看参考答案,对照你的思路找差距。

1网论把并发定义为「无因果关系的事件可任意交换顺序」,这一定义在信息流网中是否还成立?为什么?

参考答案信息流网里信息流动需要占用信道或注意力等资源,原本「因果无关」的事件可能因争夺同一资源而不能交换。结构上的并发仍存在,但「无关」的判定要加入资源约束。

2试着用同步论的合同,描述医院挂号系统中「患者挂号→医生接诊」的两方协作过程,并画出可能出现的冲突场景。

参考答案合同双方需在「挂号成功」与「叫号接诊」两个事件上同步。无协调者时,双方各自独立运行会出现患者已挂号但医生未收到叫号的脱节,对应合同实例中的冲突模式。

3网论的工具能否直接套用到处理概率的系统(如随机过程)?如果不能,最难突破的边界是什么?

参考答案难点在「非确定性」与「概率性」的本质区别——网论只刻画「哪些事件可能发生」,不刻画「以多大可能发生」。需要引入概率变迁即随机 Petri 网,是扩展而非直接套用。

13第 13 页 · 课后思考