网论
理清图论核心定理的证明脉络:看清每一步推理,也看清每一条适用边界
按 空格/→ 演示下一步
全部页面点击任意一页,跳回舞台从这页播放
网论
理清图论核心定理的证明脉络:看清每一步推理,也看清每一条适用边界
前言
你手机里的 Wi-Fi 列表、微信好友推荐、大脑神经元放电——背后都是「一堆东西互相连着」的结构。网论,就是把这套结构抽出来、用数学统一描述的学科。
站点=节点,线路=边;换乘站对应度大的枢纽节点
网拓扑
北京地铁图你一定看过:线路交错,站点密密麻麻。但你从图里读到的不是地理形状,而是「哪一站能换到哪一站」。网论把这种「只看连接关系、不在乎具体位置」的结构,叫网拓扑。
站点位置无所谓,能不能换乘才是关键——拓扑只关心连通关系
并发论
网络拓扑讲的是节点之间「谁连着谁」的静态形状。但网络真正跑起来时,每个节点都在同时收发、同时计算。这种「多件事同时发生」的规律与机制,就是并发论研究的对象。
争灶台=资源竞争,叫号=同步,出菜顺序不定=交错语义
网逻辑
并发论里我们看到,多节点同时发生的事很难谈先后。网逻辑要回答:没有统一时钟,怎么给分布式事件定义顺序?
寄出是「自报时刻」,签收是「因果确认」——每环都依赖上一环
信息流网
去医院看病,挂号单、病历、检查报告在医患间流转——每一步携带的不只是"轮到我没"这种状态,而是具体的姓名、症状、数据。网论里专门刻画这种"带内容"的流转的模型,就叫信息流网。
公文就是携带信息的令牌:每经一个部门(变迁)就可能被审阅、批注、改写
同步论
上一页讲到信息沿网流动,但工厂里老师傅说「三件齐了再动手」——这种「齐」正是同步论要回答的:并发流如何汇成一步?
乐手各自演奏(并发流),小节末必须对齐节拍——对齐点即同步事件
同步论-合同实例
两个部门合作:市场部承诺'下单三天内发货',生产部承诺'收到订单后生产'——这些承诺就是合同。把它们画成具体的网,让计算机验证真能做到,就叫合同实例。
甲乙双方的承诺条款对应义务与保证;图纸落地施工对应抽象合同实例化为具体网
同步论-婚礼教堂实例
上一节合同实例里,新郎新娘按顺序交接文件,那是顺序协作。这节换成婚礼现场——两位新人从两个方向同时赶往教堂,牧师要等他们「都到齐」才能主持仪式。这正是同步论最经典的形态。
牧师=transition,两路 token=两位新人,必须同时就位才一次 firing
同步论 同步器
上页讲了同步论关注「如何让分散的变迁协同行动」,本页落到具体工具——同步器。它就像音乐里的节拍器,把不同声部对齐到共同的拍点上。
所有队员都到齐才迈步,对应所有前置变迁都引发才触发后继动作
建模方法论
前面同步器只抓住“双方如何配合”;建模时还要回答:谁在何种条件下行动、动作怎样改变状态,以及系统边界。
货架是库所,叉车动作是变迁,托盘货物是令牌;传送路线和检查规则对应结构与约束。
本节要点
- ✓网图统一承载拓扑结构与动态行为
- ✓并发是局部使能与全局约束的张力
- ✓同步即多类资源在共享节点交汇
- ✓信息流与物流可在同一网中同构建模
- ✓建模是场景—网—分析—简化的迭代
课后思考
先合上屏幕,用三分钟独立想清楚每个问题;再看参考答案,对照你的思路找差距。
参考答案信息流网里信息流动需要占用信道或注意力等资源,原本「因果无关」的事件可能因争夺同一资源而不能交换。结构上的并发仍存在,但「无关」的判定要加入资源约束。
参考答案合同双方需在「挂号成功」与「叫号接诊」两个事件上同步。无协调者时,双方各自独立运行会出现患者已挂号但医生未收到叫号的脱节,对应合同实例中的冲突模式。
参考答案难点在「非确定性」与「概率性」的本质区别——网论只刻画「哪些事件可能发生」,不刻画「以多大可能发生」。需要引入概率变迁即随机 Petri 网,是扩展而非直接套用。