形式化开发方法eri网

软件工程形式化方法

1第5章形式化开发方法(1)2内容安排软件开发的形式化方法形式化开发方法(1)

–Petri网形式化开发方法(2)

–时态逻辑形式化开发方法(3)

–Z方法3软件开发的形式化方法软件开发的形式化方法定义软件开发的形式化方法（formalmethods）是建立在严格数学基础上，具有精确数学语义的开发方法简单地说，凡在系统研究中，应用了数学的方法，都是形式化方法本章所介绍的形式化开发方法是指软件规格说明数学建模、数学验证和数学程序求精4形式化方法与结构化和OO方法区别结构化和OO方法使用了大量的自然语言。自然语言的二义性、不完整和抽象层次的混杂等问题的解决，必然使开发系统的质量不高、成本增加和进度拖长；尤其对安全性或其他质量因素要求极高的软件，任何微小的错误都可能带来灾难性的后果形式化的方法可以帮助软件开发人员开发出更为无二义性、完整的和准确的需求规格说明，进而通过严格的验证发现问题，以达到对软件质量、开发成本和开发进度的有效控制5形式化开发方法发展历史20世纪60年代末形式化方法与非形式化大致同步都是为解决当时出现的“软件危机”提出一般认为是Floyd、Hoare和Manna等在程序正确性证明方面的研究。但由于这些方法受程序规模的限制而未能应用20世纪80年代末在硬件设计领域形式化方法的工业应用结果，又掀起了软件形式化开发方法的学术研究和工业应用的热潮，建立了一些较为成熟的方法和语言如Petri网、statecharts、通信顺序过程、通信系统演算、程序正确性证明、时态逻辑、模型验证、Z语言、VDM及Larch等6目前流行的形式化开发方法形式化规格说明建模形式化验证形式化程序求精7形式化规格说明建模操作类基于状态和转移Petri网、有限状态机和状态图描述类基于数学公理和概念基于逻辑的描述方法：命题线性时态逻辑（PLTL）、一阶线性时态逻辑（FOLTL）、计算树逻辑（CTL）基于代数的描述方法：Z语言、VDM和Larch双重类兼有操作类和描述类两者的特点扩展状态机（ESM）、实时时态逻辑（RTTL）8形式化验证模型验证和定理证明模型验证是对规格说明所建立起来的模型状态空间进行搜索，以确认该系统模型是否具有所期望的某些性质定理证明是以逻辑公式作为系统及其性能的规格说明，其中逻辑由一个具有公理和推理规则的形式化系统给出。进行定理证明的过程就是应用这些公理或推理规则来证明系统是否具有所期望的性质9形式化程序求精形式化程序求精就是将自动推理与形式化规格说明相结合而形成的一门技术研究如何从形式化的规格说明推演出具体的面向计算机的程序代码的全过程基本思想就是用一个抽象程度低和过程性强的程序，去代替一个抽象程度高和过程性弱的程序，并保证它们的功能和性质完全一致形式化程序求精与形式化规格说明和形式化验证三者是紧密联系和相辅相成10形式化开发方法主要问题对软件开发人员（包括管理人员和用户）的数学素质有较高的要求主要是离散数学中的集合、代数结构、数理逻辑等基础内容在软件工程中的具体应用对于原来一些数学背景较差的工程人员要花许多时间去学习和掌握。有的甚至还要克服对数学的畏惧心理在选择和应用形式化开发方法时应注意的问题Bowan和Hinchley提出了“形式化法方法的十条戒律”11

形式化开发方法(1)

Petri网12什么是Petri网Petri网是一种网状结构的系统的描述和分析工具对于具有并发、异步、分布、并行、不确定性或随机性的信息系统，都可以利用这种工具构造出要开发的Petri网模型。然后对其进行分析，即可得到有关系统结构和动态行为方面的信息。根据这些信息就可以对要开发的系统进行评价和改进Petri网的提出由德国C.A.Petri在他的62年博士论文“Communicationwithautomata”中提出当时引起一些欧美科学家的重视。他们在引用这种网状结构模拟和分析并行系统中称它为“PetriNets”。从此以后大家都称它为Petri网13

Petri网介绍的内容

示例-四季系统ΣPetri网的定义Petri网的基本原理-静态结构Petri网的基本原理-动态特征建模实例特性分析Petri网的特性分析方法改进Petri网及其应用时间网和随机网从Petri网到程序结构的转换14示例：四季系统Σ一年有四季，四季气候的变化该Σ系统可以由图形表示15系统Σ的Pe克tr屋i网图撞形表浮示16系统Σ的Pe灾tr战i网数做学表补示Σ=（P，T；F，M0）P=鬼{p改1,算p迹2,开p抹3,划p疼4}T=很{t穴1,萌t谱2,卖t恳3,隆t钳4}F=漏{（p1检,首t1）,（t1灾,烟p2）,（p2补,辈t2）,（t2信,异p3）,（p3输,泼t3）,（t3镰,习p4）,（p4惕,准t4）,（t4债,吐p1）}M0=（0,贴0秋,疤0,退1）17Pe录tr丘i网描陈述系悼统Σ的特怕点从四姜季系粪统Σ中，沿可以灯看出看这种宵利用废事物嘴的因菠果关饰系对层系统率进行晋网状姐结构东的描锐述，胳有以蝇下特佳点自然没有湿任何盗不必渴要的带人为坡控制途，完盘全反段映了贵现实按世界绿的真狮实情贝况局部零确定勾原理因为雨事件跑或转滚移的哨发生匹和结洒果都扫由局扛部状罪态决缸定既有饺系统衡静态炕结构种，又街有动绍态行圣为方然面的从信息既有请图形烂工具璃，又细有数澡学工底具图形捐工具慎和数姥学工渐具完聪全等维价图形勾工具疏直观砖、形难象、叼易懂侮、易怎学；逼数学伴工具蕉严谨净，既喉便于姑计算仪，又舱便于昂验证18Pe与tr秘i网的租基本哪原理碍：静杀态结研构任何膝系统梁都有摆两类涂元素樱组成裤：表晶示状歪态的桌元素午和表加示状弹态变包化的惕元素Pe阔tr摔i网位置南（pl义ac毯e）：槽状态转移志（tr愿an微si终ti熟on）：邪改变莲状态两者构之间忙的依品赖关敌系用业弧（返箭头梨）表钻示19Pe消tr去i网的锯基本具成分浙（1）20Pe隆tr骑i网的振基本基成分六（2）其中享：P=（p1,p2,,早…,债pm）是N的有般穷位咐置集演合,T=（t1,,t2,,…楼,tn）是N的有旅穷转班移集信合,F是由N中一及个P元素泊和一个个T元素抚组成俯的有聪序偶剥的集蜂合，F称为谦流关蹈系。（P×或T）和（T×真P）中的甲“×”为笛商卡尔巴乘积颠。DO川M（F）=｛x｜y：（x,听y）F｝，CO型D（F）=｛x︱y：（y，xF｝分别融为F所含夫的有栋偶序旱偶的苹第一须个元锅素组随成的职集合膀和第露二个悉元素都组成丙的集泻合。21Pe凡tr注i网的曲基本监成分哗（3）由上可以重说明N=（P,秤T；F）是倘位置居集合P和转陪移集雹合T构造Pe掀tr软i网的敏两个植基本糠成分,P与T两者氏间的肠流关顿系F是从率它们隶构造收出来晶的。顺所以练在P、T之后奖的F用分下号“帮；”皮隔开阀来P∪T≠说明千网中狸至少宅要有眉一个元素,P∩T=说明P和T为两挨类不棵同的绵元素,两者输不能碗有交F（P×富T）∪（T×限P）说蜜明一窗个P元素职代表须一个杰资源,其流苏动由F关系列规定敬。所杀以,转移T只能爽与位归置有辜直接篮的流所关系,不是搏从P→率T,就是桐从T衰→P。而不肯参与业任何造转移举的资案源为东孤立条的P,不引祸起资螺源流拼动的准转移鲁为孤盯立的T。所以DO宇M（F）∪CO到D（F）=P∪T说明蜂网中讯不能当有孤贞立的妈元素P或T22前集农、后责集、雾子网设舱，仅令*x={y|（y,烘x）∈F},磁x*备={y|（x,搁y）∈F}*x被称拨为x的前迫集或著输入长集。x*被称蔑为x的后转集或侵输出读集。在N1=（P1,T1;F1）和N2=（P2,T2;F2）中，如果,执,且,则称N1是N2的子赚网。23纯网在N=（P,泊T；F）中,如果挠对似有x∈P∪T,都有*x∩x*另=,则称N为纯贱网（pu且re垂n讲et）纯网墨中无较公共难前后沉集（帝环）24简单局网如果愈对所昼有x,缺y∈P∪T,都有驻（*x=际*云y）躬∧（x*脆=y怀*）x=斜y,则称N为简置单网贫（si乌mp租le耕n刮et）简单回网中半无相壳同的踢前后范集25Pe她tr院i网的酷基本晋原理茧：动筛态特茫征（1）Pe撕tr道i网作骡为系亡统的隔建模屡工具,除具馒有上杆述描狠述的范静态贤结构她外,还应粉包括须位置含的容崖量和同转移祝发生脱对位剖置容斤量的烦影响沟信息翁。有驴限容佛量可且用大秩于零家的整兼数表绝示,转移望发生弱对位毒置中咸标记无数的童影响晴用孤西上的颗整数婚表示韵。于迎是,具有宾动态杆特征储的Pe葱tr锅i网可院表示祥为六扩元组衬：26Pe子tr剖i网的攀基本训原理炊：动丙态特嘉征（2）Pe找tr隐i网的页六元啄组：其中萍：（P,袄T；F）含疮义同扒前K：P→唉N＋∪｛｝是位刊置上孔的容饥量函日数,N＋=｛0,睬1,军2,债3,款…｝,若K（p）=,表示溉位置秒中的邻容量个为无昨穷W：F晴→N＋是孤歉集合纯上的增孤函牌数M：P潮→N0是Pe月tr定i网∑夏的标宴识（ma横rk轧in怎g）。M0为初隶始标御识,N0=｛0,时1,桥2,雪3,济…｝,p∈P,必须叨满足M（p）≤K（p）在Pe链tr岔i网的奸图形讯表示饭中,M（p）不此是用律数字,而是冰用实案圆点朋表示椅。每滩个实腐圆点存为一帝个标饮记,同一腥个位骗置中库的诸仇多标搂记代驴表同纯一类乓完全脏等价却的个搞体。敲弧（x,布y）上短的W值标乳注在算孤（x,松y）上27转移妄发生呀规则归（1）Pe先tr纽奉i网的统动态率行为品是通批过转湿移发突生引班起标啦识改奖变来辛体现丘的转移莲可发谨生的抽条件剖和发晌生规术则转移t可发构生的糠条件若在川标识M下,p1,仁p1∈*tM（p1）≥（p1,t）,且p2,膊p2∈t*M（p2）+W（t,舒p2）≤K（p2）+W（t,宜p2）库≤K（p2）,此时骆称t在M下可墙发生,记为M[t位>转移t发生访的结牛果若t在M下可森发生,就可址以发森生,发生亏后将M变成别新标脖识M’,出视博方出胶记为M〔t＞M’或M茎→M鸡’,并称M’为M的后导继标醋识对p∈P,兔M’（p）=M（p）－W（p,忠t）当p∈*顿t－t廊*=M（p）＋W（t,设p）当p∈t富*－榆*t=M（p）栗－W（p,翠t）＋W（t,街p）当p∈*落t∩t凡*=M（p）当p∈t攻*∪*绣t28转移督发生泪规则静（2）注意一个尖没有犹任何辟输入双位置这的转故移叫杜源转兔移,一个题源转椒移的检可发德生是俭无条册件的品。一折个源捞转移责的发洪生只艺会产铸生标瞧记,而不违消耗冒任何方标记一个敲没有巨任何臣输出朴位置坚的转晕移叫饲潭转扔移,一个节潭转照移的保发生辆将消球耗标底记,而不柔产生斤任何欠标记29示例垂：转测移发布生规费则以本坛例来说滋明网赚论中虏的转普移发扭生规猎则，赖以及赢网论嗽中的姨冲突训（co今nf染li松ct）、例并发晨（co支nc逗ur个re稠nt）和甜碰撞储（co咸nt苹ac爪t）现撒象有时聋，一筐个Pe籍tr却i网中材同时至存在滚并发痕和冲碗突，茅而且衔并发帜的发僚生会达引起筑冲突算的消昼失或冬出现邻。网案论中胶称这杠种现替象为疑混惑步（co亚nf俭us牵io月n）30并发汗和冲体突概脖念的顿完整盒描述并发设M为Pe扛tr竿i网Σ的一弱个标劝识，阴若存匪在t1和t2使得M[t1>和M[t2>，并满子足私，悉且港则称t1和t2在M下并予发冲突设M为Pe容tr警i网Σ的一掌个标挖识，铸若存恳在t1和t2使得M[t1>和M[t2>，并满崖足融，且戒则倚称t1和t2在M下冲科突31网系杏统分锡类根据Pe沾tr租i网系珍统中壳容量龙函数K和权越函数W的不侮同可原分为繁三种撕情况K≡1，W≡1为基招本网虏（el垒em本en答ta淹ryne由t,抵EN）系乱统这种垂网系恼统位蕉置p中，倘只有佛‘有蛙标记何’和膜‘无丹标记共’两筒种状巴态。虚习惯哥上把四这种姨网称夫为条因件/转移怕网系夺统K≡，W≡1为P/T（pl柴ac误e/母tr米an丝式si壤ti斗on）网K和W为任拉意函乘效孟为P/T系统P/光T网和P/妙T系统波中都册是物没质资睬源，纤它们榜与EN系统初有本圆质的财不同主。所指以，EN系统进又叫偶做条狼件/事件俯网系汇统。P/腹T网和P/然T系统嘴也有各区别寇。K（p）（附位置哲容量砌）是显其能竿容纳艳此类漂资源赔的能象力，讽也称毕空间状资源亏。而W（p,促t）和W（t,燃p）分号别是库转移t发生扰时释崇放和向占用锦此类形空间淡资源凭的数趋量。P/T网的骗位置p容量筛足够粒大，割所以熊不会觉发生穷碰撞论。而P/T系统气，如觉果位很置p容量洪有限钟，且扩不进桃行技个术处跃理，票则有睡可能阀发生钳碰撞32Pe吉tr若i网转挡移发雪生规舱则的辈简化对Pe挂tr乒i网简包化的古原因准是为片了对Pe类tr纽奉i网进士行理趣论上精研究佛的方览便通过钱上面批讨论仔可以识看出起，对葱于简胳单的Pe锁tr筛i网，砌由于K和W已无摊任何央限制城作用鼠。所馅以，戴一般茄把这岸种Pe升tr鹿i网系帜统记悬为：风∑=（N,诱M）=（P,充T;禾F,铁M）。魂这种Pe烦tr伏i网系岸统的库转移纲发生线规则舍，可膨以简宁化为偶：若M﹝t＞，当且使仅当p∈p，M（p）摧≥1，t发生撑后，M﹝t＞M’M’（p）=M（p）－1当p*t－t*=M（p）＋1当p∈t乒*－慌*t=M（p）扣其它网论母可以雷证明平，经扛过适蜜当加卫技术伏处理眯，都杏可以食把K、W任意闹的P/沫T网或P/墙T系统店改造孟为K≡,W≡1的Pe为tr贵i网M’（p）=M（p）－1当p厚∈*逝t－t率*=M（p）＋1当p嗽∈t扩*－民*t=M（p）卧其它33建模课实例坦：有任限状纳态机34建模秧实例粮：并伸行活帅动35建模肚实例诞：数巩据流戏计算36建模傍实例惩：通盾信协俘议37建模缎实例卡：同芽步控集制38建模王实例浸：生特产者/消费横者系袭统（1）39建模菠实例紫：生闲产者/消费携者系银统（2）抑制举弧40建模震实例兔：形指式语烤言41建模雄实例捧：机拌械加刊工（1）42建模斯实例匆：机伏械加匀工（2）43建模边实例摄：机斧械加暑工（3）44建模隆实例狭：机以械加榴工（4）45建模想实例洪：机企械加是工（5）46特性指分析Pr确et蔽ri网的狮特性渴主要勒包括可达恶性（Re亦ac供ha究bi娘li虹ty）有界禽性（Bo公un晌de录dn涌es抽s）活性偿（Li避ve宰ne递ss）可逆精性（Re熔ve称rs捐ib挥il税it誓y）可覆小盖性仰（Co茅ve兄ra磁bi侄li究ty）持久挎性（Pe夹rs虑is冬te贝nc塘e）同步贡距离鞭（Sy夜nc移hr口on秧ic派D痕is福ta感nc兼e）公平脖性（Fa扬ir轻ne窝ss）47特性罪分析-可达翁性对Pe顶tr御i网（N，M0），史如果妄存在秃一个浑从M0到Mn的发睛生序饭列，制则称叙标识Mn是从M0可达兆的。匠发生意序列骆表示催为σ=M0t1M1t2M2t3M3…tnMn，或简化衬为σ=t1t2…tn。可用M0〔σ＞Mn表示卸三者哲间的浩关系法。在Pe兄tr您i网（N,驳M）中季所有骂从标弊识M0可达辛的标吉识集央合，登可表桥示为R（N，M0）或甩个简旗化为R（M0）。从M0出发星的所哥有可进能发全生序察列的偷集合卖，可昏表示陕为L（N,找M0）或持简化嫌为L（M0）。这样,P疫et俱ri网的亏可达雄性问丸题就惕转换臣为对联于Pe柱tr哗i网（N,踪蝶M）和延给定古标识M0,寻找燥是存乳在M0R（M0）可达提性是龙研究奖任何熄系统报动态忌特性游而与船基础48特性朝分析-有界闪性对Pe捆tr碑i网（N,袄M），哑若存阳在一月个非碌负整净数K，使得M0的任蓬何一退个可拥达标众识的后每个引位置写中的救标记纹数都轻不超堆过K，即对兽每个怀标识M∈R（M0）和章每个东位置p,显M（p）照≤K均成旷立，花则称Pe清tr炎i网（N,世M0）为K有界睛，或归简称反有界若Pe复tr馋i网（N,市M0）为1有界采，则慢称此Pe土tr斯i网为抗安全疏的。乒这种阅网的通每一篇个位墓置要突么有设一个素标记风，要吉么没甜有标贺记通常商用Pe驼tr姿i网中允的位疮置表草示实惧际系毅统中求存储岗数据勺的缓易冲区含和寄与存器呼。通妥过分泰析网烛的有各界性熔或安舟全性死，就桌可以但考察喂实际弯系统建中缓奴冲区谜或寄遥存器达是否麻会溢笋出49特性占分析-活性一个Pe铺tr坚i网（N,龙M）被丧称为刑活的活或称M0是网N的一喉个活火标识醒，仅背当从M0可达思的任兔一标理识出指发都做可以泄通过牢执行滚某一刑转移长序列系而最移终发爆生任赢一转怜移。努这意答味着誓，无宪论选知择什魄么样汤的发烤生序质列，蹈一个店活的Pe陆tr柏i网都刚可以蚂保证复无死松锁操槐作。扶活性堪是许鹿多系翻统的耍理想沿特性朋。但础这是晓不现互实现瞎的，渡也是掠不必歌要的对于Pe降tr蹈i网（N，M0）中川的一傍个转磁移t，实际先上可雾能属届于以站下情蜓况：L0级活第（死侵的）泻：仅巡寿当t在L（M0）中未任何司发生稍序列恳中都挤无法抽发生L1级活抄（可轰能能扫发生躺）：隙仅当t在L（M0）中换的一届些发史生序蒙列中征至少命可发悲生一奔次L2级活悄：已哥知任临一正饿整数k，仅当t在L（M0）中脾的一看些发是生序屑列至在少可枯发生k次L3级活恋：仅咽当t在L（M0）中摄的一谢些发猎生序跨列中景可以绪无限说制的苦发生L4级活纷（活潮的）谣：仅域当t在R（M0）中霞的每千个标寇识是L1活的50特性连分析-可逆曲性一个Pe糟tr熄i网（N,丛M0）称钉为可鸡逆的资，仅典当对R（M0）中杨每个垦标识M,M0都是里从M可达琴的。磁因此饮，一超个可救逆网首可以看返回延到初互始标垮识或悬初始块状态蜂。在廊很多赞名小陈应用够中只霜要求乐系统院回到纠某个捷特定话状态姻而无调需回麦到初倘始状张声在雾态我散们称程这个滚特定尾状态锋为主佛（ho合me）状批态即彼对于R（M0）的催每个疼标识M,主状胆态M’都是燥可达缩慧的有界斜性、询活性速和可都逆性绪是三弊种相荒互独苍立的侦特性51特性遵分析-可覆企盖性一个Pe迎tr魄i网（N,调M0）中陡一个棉标识M称做袜可覆共盖的哭，仅昏当在R（M0）中敌存在腐一个亚标识M’，使得抛对网虎中的毛每个气位置M’（p）锦≥M（p）成谦立可覆绝盖性袖与L1活（简潜在孩的可包发生净性）费紧密贱相关抵。设M是转湾移t发生欣所必贷需的调最小草标识全。那考么，妨当且杏仅当M是不颂可覆袄盖的担，t是死河的（姻非L1活）瘦。也们就是离说，t是L1活，趟当且纪仅当M是可脉覆盖畜的52特性男分析-持久膝性一个Pe荐tr的i网（N,董M0）称佳为持味久的鞋，仅公当对驻于任师意两扇个可仁发生副转移皆，其缺中一怎个转横移的全发生金不会撕使另筑一个丑转移淡不发澡生。供就是候说，皮持久省网中梦的一盯个转旺移一王旦可窄发生占，将德保持萍这种痕可发艰生性艰直至斤它发班生为宜止所有造位置相都只岛有一绝条输球入孤喂和一叨条输未出弧浩的Pe修tr宽i网（丽标识它图）腰具有树持久哈性53特性罗分析-同步惹距离同步铃距离价是条幻玉件/事件短系统碎中两嫌个事件莫间相摔互独拼立程苗度紧矮密相常关的一种化量度侨。我输们用来定握义Pe热tr米i网（N,捡M0）中宵两个絮转移t1和t2间的钉同步裂距离俱。其秧中是起忠始于R（M0）朋中的横任何却标识M的一猴个发黄生序之列，骂（ti）是毛转移ti（I=弃1,格2,盛…）在真中发椒生的弄次数里。右图硬们仍赢所示Pe斯tr效i网中d12=1离,d34=1馅,d13=∞同步睛有不苍同的闷形式涌（见鹿例1~例5）54同步先形式迫（1）它们蚕共同撕执行券一个半任务部，只栋有p1、p2中的描标记尝同时辞到达希时才知能同临步55同步察形式纷（2）这是棉一个根顺序面系统案，t1,t2为同净步。慰但它粥们交举替发唤生，t1与t2的关坏系为1﹕猴156同步标形式寸（3）这是末一个隶并发谈系统蕉，t1、t2发生裕的关康系也叮为1︰戒1。但张它们岂不是叶交替枪发生腰，而妇可同豆时发扁生，蛛也可铁一先利一后勒发生57同步诸形式拳（4）本例中，t2不能同先发究生，用只有t1可以抄发生央。这诞也就省是说涌，只住有t1发生宰后，t2才能颂发生惊。这闯时，吃仍只梦有t1能够嫂发生勺。即t1第二抬次发律生后裤，t2才能切发生后。由叮此可迎见t1与t2也为音顺序孙关系学，但悬它们享的关抛系为2﹕池158同步史形式茶（5）本例中，t1与t2的关但系为1︰论∞或∞︰1，这族就等振于无潮同步默可言59同步胆距离克刻画捉事件呀间的修同步港关系d12=∞两组笨事件菌不同魂步，采即异第步d12<∞两组凤事件蹄以d12为距资离相截互同浙步d12=0两组足事件挂在时闹间和右空间捡上一舟起发也生，叮网论抄中将锻它们挽当做披一个植事件d12=1两组管事件晚必须纤交替劳发生60特性区分析-公平资性两种魄基本训公平简性有界选公平歉性对于互两个缝转移叨，若哗不发妙生其组中一股个转毯移另腰一个说转移堤可以窗发生所的最睛大次棒数是伪有界俯的，套则称菜两个胀转移冤为有朴界-公平豪（或β-公平渣）关眼系。隔若Pe围tr躲i网（N,漏M0）中芽每对州转移旗都是β-公平鱼关系耽，则哑外该僻网为β-公平洗网无条本件（环全局畏）公像平性对于黑一个移发生故序列梁，津若它百为有尖限的首或网考中每升个转膏移在嘱中无心限次壁出现酷，则荒称寄为无户条件落（全冰局）糕公平友的。搅若督从R（M0）中某另个M开始填的每蓬个发叹生序古列嫁都是僚无条剩公平挎的，坟则称Pe烧tr脾i网（N,药M0）为锄无条买件公酬平网两种勿类型车公平庆性之侨间的响关系每个β-公平汗网都虫是无邪条件敲公平舰网每鞠个有余界的站无条宏件公墓平网分都是β-公平历网61Pe搏tr抗i网的陪特性牢分析运方法分层殃或化胡简可覆上盖性嚷（可榆达性厅）树不变耐量、怨关联疾矩阵洒和状钳态方蛾程62Pe印tr吨i网的动分层Pe粱tr益i网分恭层的涂方法自顶倾向下弯（一勺个子扩网替牢代一教个结润点）自底阳向上辫（一划个结淡点替晃代一蒙个子暑网）结点葛的选时择一般先以转熔移t为结匠点，铲也可垮以位涨置p为结裂点子网番结构臂的限樱制这是泥由于Pe传tr弹i网的增异步律并发齐性质排决定妖的解决阔的方摘法有刊：基修于基画本网浆和高渴级网迅的，惜有基筋于网匠的静雅态结只构和厅动态术行为块的，精也有透基于惭形式南化和亏非形累式化辜的，腰还有漏基于爱网的包静态针结构此的图董论观谱点的63示例便：Pe年tr驴i网的价分层冶概念与DF折D分层摇相似简。Pe舱tr冰i网分层待时，著以作曾为分鄙层的碧结点亡。不欲仅要魂保证兼父子抖层的I/浩O一致肾，还呢要保可证它额们的硬性质贿不变率（因亦为Pe醉tr制i网主杠要用慌于并棕发系情统的清特性掏分析继）64示例蔬：基该于网穿的静黄态结茧构的阵图论军观点图中p1和p2分别匪为子岩网G’的输桥入门暂和输丸出门页。t1和t2则分奸别分基子网G”的输陵入门龄和输瓶出门庭。G’是一讨个位悲置子帮网，G”是一万个转腾移子葡网。闸同时阿，它有们的碧输入幅度（冲输入胃孤的捕数目酱）和菜输出裕度（妥输出察弧的娇数目绍）均王为1。有迟了这绸些概自念就滑可以终定义支出如彻下化拼简子幸网的驻条件炒：1，构零成一滩条只议有一恢个输入门书和一理个输肺出门更的直鸡接路经2，输萍入门绞的输叶入度姿和输出门鸣的输及出度腐分别苹为1只有发这样利，才凡能保皂证原已网的特无性（违如活含性、胸有界铲性等微）不变65Pe帖tr巩i网的悼化简与分层逗一样尖，是福一种罩处理雕复杂燃问题宰的方见法化简炸的基衬本原续则在保掉持所蒙有要倚求的港性质傲不变遵的情疑况下灯，将踩多个忠不同顶位置退或转字移抽秩象为洞单个想位置吵和转化移化简吹的方像法折叠耳（将猛结点键多的巩基本霜网转秆换为璃结点督少的蚀高级汁网）删减逃（将错冗余祖或等陷价例愉位置端或转拔移删绿除或昨合并困）66Pe模tr吧i网的假化简沸：折接叠-着色袖网这种抬方法异是用层颜色雁把标无记分签开示例67Pe喇tr寒i网的水化简屋：折虏叠-谓词/转移俘网这种旗方法她与着喝色网字不同授，它哲用字嫩符串绳来表膏示标柔记。困然后凭，把所转移四与谓泰词（拆刻画逮标记屋的性声质）滔联系畅起来店，用识来控阵制转贝移是如否可慎发生示例68高级魄网到煮基本捷网高级爬网也旬可以秧展开复为基学本网示例69Pe甚tr述i网的笔化简皱：删非减设（N,思M）和以（N’宏,M武’）分恢别为友化简龙前后讨的网阔，运提用以阵下化用简规因则，蔑当且侍仅当村（N,续M）是考活的记、安两全的宋和有递界的斜，则静（N’周,M滑’）是规活的啦、安奋全的涝和有逢界的串行生位置章的合载并串行宵转移臂的合赖并并行饶位置所的合偶并并行唯转移似的合阳并自循幸环位设置的流消除自循肆环转紫移的棍消除70串行穿位置碧和转险移的宫合并71并行发位置寇和转斜移的秒合并72自循环还位置蜡和转腔移的前消除73删减炮的示例从图名（a）发蚕生t2,移去p1中标印记,合并t1和t2为t12,合并t3和t4为t34,从而宅得出电图（b）所晋示的Pe产tr低i网。埋从图录（b）中蚀消去锹自循两环转款移t12和自反循环树位置p3,又可奔得以炸得出火图（c）所忌示的Pe辱tr响i网。类所有沫这三谈个网赤都是砍有界的,非活母的和困安全的,并且鞋都是搬不可逆的74可覆盖萄性（附可达倍性）贺树可覆矩盖性峰或可蜂达性嘉树用前标识勤树来钩实现标识未树的耀实现利用维一个草给定行的Pe炎tr驴i网（N,炮M0），从M0开始侍可以米得数啊量与饮可发规生转预移一各样多扮的许粪多“宏新的需”标仍识。坏从各店个新奴的标舰识可妨以再字到达拌更多灭的标申识。琴可用古标识锣树表弃示以撞上过涝程，犯以初王始标反识M0作树研根，蚕可由M0到达渔的标香识作居树的泼后继讯结点逗。每倡条连飞接结闯点的尸弧表图示一甚个转辜移的彩发生乖，它镰将一什个标撤识变泰换到关另一叛个标中识标识斗树中浙的特崭殊符捐号如果Pe珍tr摆i网无匆界，城则所令构造久的标陷识树租将生汇长为芹无限暑。如燃果Pe撤tr市i网有艇界，聚所构墓造制盟标识抓树也念可能微为无映限。艰另为暑了保向持标馅识树咸的有爆限，蹈我们元引入饶一个保特殊迁符号，可以庭把它羡想像哨为“敲无限捷”。具有蝴这样劲的性价质：对每窃个整帅数n：＞n，缴±n拿=钱，雕≥谈75可覆祥盖性傅（可准达性再）树久的构室造过货程1.把初薯始标吉识M0当作布根，贫并加渐上“新谈的”标志勒；2.当具冠有“新的”标志明的标膏识存介在时忘，重易复以损下步洞骤：（1）选典择一辜个“新美的”标识M；（2）如常果M与从口根到M路径坊上的姿一个叔标识璃相同震，则败对M加上“老贵的”标志欲，然拾后转介向另仗一个“新的”标识远；（3）如裤果M中没咬有转拘移可别以启飞动，摔对M加上“死的”标志械；为（4）当M中存弱在有影效的昂转移萌时，对M的每跟个转耽移t做以缘瑞下各菠步：a，从M发生t的结难果获钩得标抽识M’b，若M（p）=，则M’（p）=摔c，在从凝根到M的路径苍上，铲如果瓶存在窜一个芦标识M”，使得棋每个举位置p存在M’（p）M’松’（p）,并且M’M’秩’,即M”是可患覆盖俊的。谢那么规，对歪其中店满足M’（p）>M’偷’（p）彻的每白个位题置p，用重卖置M’（p）d.引入M’作为河树的沈一个类结点藏，从M向M’画用t标注搅的弧挥，并厦对M’加上“新右的”标志鼠。76从Pe瓜tr室i网获蓝得可取覆盖沫性树77使用收可覆贵盖性畏树可掉研究Pe贴tr惧i网的新特性虫（1）对于欠一个Pe路tr乏i网（N,艰M0），缝且因壮此R（M0）是通隶过使闷用可迟覆盖开性树店可以洪研究付以下膏特性一个形网（N,碗M0）是有嘴界的脾，且因旷此R（M0）是有蝴限的鸡，当且勇仅当不会排出现滑在可亡覆盖船性树累中的询任一农结点衡标注流中一个肿网（N,冻M0）是安芹全的亲，当扛且仅铺当只浙有“0”和“1”出现雪在可巨覆盖游性树膝的结挎点标因注中一个荷转移t是死橡的，先当且寨仅当t不出怕现在栽可覆托盖性枝树的龟任一士弧的锄标注建中如果M从M0可达密，则督存在避一个谦标注M’的结有点，动使得MM’78使用建可覆题盖性台树可阶研究Pe对tr辞i网的扔特性挖（2）对于废一个泻有界今的Pe催tr谅i网，悦其可惯覆盖醉性树丑被称心为可辫达性敲树。猜这是介因为祥它包耐括所摄有可暴能到塘达的红标识垒。在组这种倾情况顺下，拜前面哲计讨攀论的和所有拳行为剧特性漫的分赴析问夺题都娃可以久通过暂可达喜性树款来解绿决，貌这是羞一种枯穷举穗法但在嘴通常由情况慌下，蹦由于近使用你符号会使一些逃信息足丢失民，所遭以可认达性什和活遥性问溪题不乘可能员单单如利用案可覆诊盖性题树方慨法来拒解决誉。我膨们可奏看下梦页所承示的涝两个营不同役的Pe旁tr泉i网，昏它们宋有相侵同的绝可覆章盖性镇树。环但其炭中一亦个是蛛活的Pe闷tr滑i网，清而另听一个梦不是辩活的峡，因恭为该今网在主发生t1、t2和t3以后姿再也录没有叼可发关生的注转移79使用鲜可覆挡盖性衡树可缺研究Pe艘tr合i网的才特性涛（3）两个精不同逝的Pe拢tr吹i网一个劝活的Pe衰tr较i网师一个骂不活躁的Pe软tr次i网80使用闯可覆诊盖性蜘树可舰研究Pe缺tr逼i网的姿特性析（4）相同澡的可约覆盖泪性树81使用坝可覆猫盖性孤树可排研究Pe周tr逝i网的示特性舌（5）不同验的可症达状辛态一个邻活的Pe首tr治i网虫一藏个不指活的Pe斧tr梁i网82不变病量、温关联妨矩阵恋和状罗态方粒程这一部球分介芝绍的楼是完贪全用汽代数边计算搜来对奥网系仓统进判行分透析。前边湿介绍五的可斩达集幻玉都是遗从网蚁的整庙体行盏为来戏刻画桌的。送这里亚讲不职变量窗，整认体中步有许边多不施变量制，这串是局既部行猾为。不变毯量用售关联川矩阵振定义再，它以给出绍了系屑统的秃结构窃。根据橡关联士矩阵坑与网球存在蒜的一交一对穷应关揪系推是出状评态方嫩程。最后铁就可成用关只联矩阿阵和宪状态侍方程荡计算夕出网踪蝶的不贪变量宋和网语的各施种特合性。83不变教量（in阀va深ri练an更t）网系永统中有S-不变冷量和T-不变耍量如果咳网系浅统中翅有一肆些位妥置，湿其中屋包含转的资犯源（孙标记浩）的土总和歌在任翼何可欺达标凶识情消况下骨均为膨常数草，即奥系统带不论患发生渴什么徒事件惊，这丧些位找置中线的标鹿记总抛数不往变，匀则这蜻些位露置就桐是系逮统的报一个S-不变土量。壤也就样是说驱，S-不变磨量代汁表着房诚网系澡统中席若干谊个资夸源的甚流动刃范围如果归网系昌统中辛有一伶些转饿移，删它们尿的发钻生会驰使它译们的剥标识朽恢复息到它卷们的萄开始羽状态魄，则晴这些模转移则就是猫系统阳的一厚个T-不变镰量84不变乔量-示例1S-不变刻量和T-不变群量一跑般采怕用向狮量表酱示，铸即以请位置送元素浇为序枪标的痛列向命量表诵示S-不变查量，桌以转除移元刺素为马序标呼的列饭向量搭表示T-不变刺量本网污系统融的不蛋变量助为：S-不变琴量T-不变馆量85不变奥量-示例2本网系统字的不愚变量丑：86不变傅量-示例3本网系统筋的不搬变量诊：87关联唐矩阵（In喘ci挑de教nc悉e异Ma铃tr哪ix）（1）正如裳网系咬统的样标识乏可以裕表示么为一巾个向帜量一辽样，抛网结芦构也溜可以川用一侍个矩蹲阵来百表示洲。设Σ=（N,留M0）,其中N=（P,娇T;F）是一贴个纯膀网，锣其中P={p1,p2,…规,pm}，T={t1,t2,…盾,tn}用S-元素帜作为较序标疯的列亦向量V：PZ称为Σ的S-向量叼，Z为正刺负数锤集合仆。其锁中，Z=｛…－2,－1,见0,馒1,督2,高…｝为正宁负数朱集合用T-元素胀作为螺序标六的列刮向量U：TZ称为Σ的T-向量用P×T作为置序标缘瑞的矩愚阵C：P×TZ称为Σ的关罪联矩武阵其关修联矩傅阵元坝素C（pi,tj）=W（tj,pi）－W（pi,tj）88关联读矩阵拿（2）C（pi,tj）=W（tj,pi）－W（pi,tj）也可写成：﹝Cij﹞m×蚂n=﹝Cij＋﹞m×堵n－﹝Cij－﹞m×闻n其中Cij＋就是肆从转泽移j到它晕的输腥出位主置I的弧姿的权盼，Cij－是抗秃持转移轨的输望入伍网卜位浸置I到转伍移j的弧怒的权芽。从科转移霉规则耍很容朵易看胀出，Cij－、Cij＋和Cij分别帐表示漂当转亲移j一旦示发生萍，位塔置i中标舞记取梢走、毁增加畅和改案变的廊数量脸。当（tj,pi）∈F其他当（pi,tj）∈F其他89关联并矩阵铅（3）关联以矩阵妥一般绢表示征形式其中Cij表一下票示取饶走、筒增加典后产毙生的泡变化脊数。溪此关皆联矩浮阵给表出了塞系统家∑的疲结构90状态螺方程如果N=（P,晌T;F）是纯吼网，欣则C与N存在愚一一净对应蓝关系利。在奖此，楼我们妇用m维列盖向量弓来表断示标肾识M，即M=﹝M（p1）,M（p2）,肆…,M（pm）﹞T。这样武，M﹝tj＞的充疯分必误要条键件为势：i∈｛1,芹2,夺…的m｝：Cij－≤M（i）或写角成：C*j－≤M其中C*j－表示险矩阵Cij－的第j列。如果M1﹝tj＞M2，则有M2=M1+C*j。若M0﹝σ＞M，就可包以推季出状怠态方虑程为矛：M=M0+C·疫U其中C·等U是矩阵刚乘法候，σ是∑猎的转砌移序渴列，U是∑的T-向量越表示故，它很以tj为序标的分量源值为tj在σ中出柄现的组次数喘，即U（tj）=#（tj/该σ），M0是∑的初纹始标写识的S-向量寇表示申，由σ导出地的可卧达标负识M也表从示为S-向量除形式语。91用关联冶矩阵放和状够态方膏程求员不变罪量设I是∑认的S-不变峰量，M∈﹝M0＞，则IT·M=IT·M0设σ是从M0到M的转饭移序词列：M0﹝σ＞M，于是M0+CT·U=M，其中U是对婚应于σ的T-向量物，对陷所有tj∈T，U（tj）是tj在σ中出末现的彩次数肝。两纽奉边同垂时乘由以IT，则得IT·M0一+IT·CT·U=IT·M92状态衣方程密在可捡达性材分析倦中的腊应用理（1）状态脖方程M=M0+CT·U为部分躲解决估可达嚼性问炕题提乖供了匹一个董依据刻。若Md从M0可达裹则方事程CT·U=Md－M0=△M必然低存在酒一个摆非负晨整数狱解Ux，该解喜即为乱发生驾的计捏数向免量。赛若无凤这样缓的解付，Md就不继非从M0到达怨。示例193状态佛方程万在可雅达性伞分析航中的学应用缴（2）示例1（续拜）在所扩示的Pe愉tr靠i网中令：在状拐态M0下转位移t3是可像发生辩的。备设M1是发爬生t3所得侄的标卖识，瓜则有94状态碰方程雁在可课达性介分析留中的湾应用蓝（3）示例1（续蜓）发生仰序列σ=t3t2t3t2t1表示积成发脉生计邪数向凡量（1,啄2,里2），σ发生矿后产料生的珠新标卷识为95状态渠方程申在可滩达性伍分析恢中的毕应用虎（4）示例1（续铃）考察竹标识碗，它眠可以息从标粪识M0到达炊方程星为有一赶个解U=（0,值4,税5），捷它对我应于易发生秘序列σ=t3t2t3t2t3t2t3t2t396状态菜方程满在可甘达性酸分析滴中的喇应用柄（5）再考隐察后枕标识缘瑞，因裙方程无解倚，所软以标鄙识引为不捧可达酸标识97状态最方程竹在可岭达性乳分析拘中的违应用盲（6）注意绒，状蒸态方菌程有婚解只黎是可垦达性垒的必导要条煌件，终而不功是充狮分条从件。败这是铃由于座缺少△M初始必标识鸭信息战导致龄的示例2考察育所示鲁的Pe唇tr拜i网98状态蓄方程纠在可撑达性遥分析术中的嫂应用纹（7）示例2（续阻）在所闻示的Pe挤tr肠i网中方程99状态毕方程妥在可琴达性册分析苦中的排应用碗（8）示例2（续侍）有一板个解U=。这个创解对匹应的侄两个笋可能准发生醋序列且为t1t2或t2t1，然而转这两宽个序践列都航不是塌可发质生序纽奉列。爽因为咐在M0下，t1、t2都不曲可能影发生鸦。这妹里若取梨初始绑标识心为则为挪可达桃的，循且对能应于废发生惹计数并向量甚的发处生序核列为t1t210厚0关联陈矩阵螺和状菌态方夸程在钢其他就特性棒方面迟的应伸用（1）结构腊有界位性N=（P,仅T；F）称踏为结饥构有众界，监是指椅对任际何初草始标币识M0，（N,刚M0）都手是有蜜界的纽奉。可觉以证应明，各网N结构春有界峰的充象分必她要条螺件是停存在m维正蓄整数码向量V，使得CT·V≤0守恒遥性如果睛存在P上的厦一个只正整纪数函片数V，使得奔对任句何初也始标距识M0和任漆何M∈R（M0），∑M（i）V（i）为塑一固逐定值容，则雕称N为守计恒的费。可叼以证窄明，密网N守恒姑的充街分必蓝要条镰件是打存在m维正姥整数劳向量V，使得CT·V=0可重复沫性如果闹在存忌在初搏始标万识M0，在格（N,壮M0）中炼存在眯无限民转移限序列σ，使得M0﹝σ＞，而且搬每个仇转移tj都在σ中出稻现无言限多呈次，趟则称嫌网N为可叨重复滋的。抄可以缸证明没，网N可充觉分必睡要条笑件是去存在n维正悦整数排向量U，使得C忆·钟U≥010壮1关联蔽矩阵自和状渡态方结程在矮其他扮特性火方面犹的应陵用（2）相容击性如果锤存在缎初始冠标识M0，在誓（N,小M0）中讨存在赖无限桥转移煮序列σ，使得M0﹝σ＞M0，而且tj∈T，#（tj/σ）桶≥1，则称崭网N为可浩相容谨的。葛可以输证明宇，网N为相践容的横充分摧必要赞条件截是存牢在n维正竟整数塞向量U，使得C端·朵U粗=0结构置公平瓦性如果治对任关何初棉始标砌识M0，在（N,颜M0）中技都是劳公平应网，待则称芦网N为公激平网揭。可以羊证明曾，网N为公皂平网晨的充眼分必尊要条蹄件是版对任梢意n维非柄负整插数向著量U：C仗·拳U≥0i∈｛1,俱2,祸…舞,m｝：U（i）＞0，而且喘若有U1和U2满足C狼·竹U1≥0和C蔑·勒U2≥0，则U1和U2线性住相关10半2关联业矩阵盾和状怒态方窑程在墨其他炉特性教方面编的应燃用（3）示例本例咏所示屿的网殿（N,M0），行它的稍位置测集S和转挣移集T各有4个元务素，率流关艇系如闲图所荒示，夕初始鼻标识M0=﹝胞1,绸0,食0,田0﹞。对这桂样的扫网（N,M0），括可以反写出叮它的毅关联紫矩阵卸和状肾态方伐程10团3关联涌矩阵挡和状雨态方茶程在闪其他酒特性销方面拉的应沸用（4）由于M0≥C*2－，所以t2可以掌发生章。设M0﹝t2＞M1，则如没σ=t2t1t2t1t2t4在M0可以贿发生克，记M0[σ＞M2，则田可计算赛出M2为10忌4关联苏矩阵蒸和状永态方特程在惊其他超特性恋方面垮的应管用（5）本例阀容易拥证明详，存姿在U1=使得CU1=0。所以驱网N是相林容的陡，也吼是可山重复的。鼓但不稻存在饼四维苍正整皇数向耍量V，使得CTV≤0。所以投网N不是发结构必有界虽的对于横任意茫非负娇整数kV=k都满今足CTV=0。何所盏以k是N的一聪个S-不变量博，从胀而｛S1,S2,S4｝是N的S-不变糟量的央支集珍。同理尊，N的T-不变原量额周广都扶有k的形篇式，陡也即尼转移吉集T本身府是N的T-不变齐量的众支集由于殖存在U2=，使得CU2=，而U2中含马有零恰分量稻。所孙以N不是公平10戒5改进Pe隔tr吩i网及逐其应役用什么便是改多进Pe稀tr阁i网改进Pe孝tr置i网指穗的是虎谓词/转移森网和妻着色灰网。池它们分由基赠本网振改进络而来居，故改称它紧们为膀改进Pe伐tr服i网。范有的甜称它晴们为妹变形魄网，肉还有卫的称浩它们段为高雪级网既然功有了械上面鸦讨论坦的基遮本网搁，为姐什么议还要恨高级织网这是田因为袜在实来际应税用中兄，一驾个稍巾复杂孤的网狮系统牙就会旷使用稿大量谦的位胖置和臂转移渔，由赖此引怀起状晶态组贡合爆伙炸问瞎题，节使Pe示tr岸i网难决以理蓝解和运分析乒。有某人甚颂至认律为在秤状态乌（可劫达集婶）组孩合爆呜炸这隔一基菌本问阔题未帅获解塞决或衬有可丢能避眠免之漆前，Pe锤tr勿i网建滥模不魄可能侄出现蛙实质仪性的偿成功认或突削破。肆所以而还要叶介绍历高级睁网。高级惠网系耳统如着何构幕造高级绝网系亿统如洒何构访造，声一般脏都从价应用荒的问毒题的P/菜T网系默统模涛型着胁手，老经折僻叠而胀成。匆所以翁，我耕们就复应该恭先弄泡清什汇么是P/架T网系逗统的男折叠澡，然塞后介惰绍折尿叠的补高级金网系见统的没定义什么扫是折灾叠折叠饶就是腾采用贤抽象脂的方衬法，脚把具斜有同筑类逻辩辑功乏能制稠的位鸽置和栋转移哑进行亚合并狂，这箭样就葱可以寻大大雹减少由位置给和转死移的月数量里，将冲结点透多的P/时T网系细统转财换为倍结点谣较少晓的高名级网漏系统10滤6谓词/转移派网谓词/转移疤网（Pr贸ed猴ic锤at购e/救Tr弊an知si害ti割on碍n痒et额s,吃P异r/属T网）Pr缺/T网的竹转移保发生抄条件泪和引辣起的杆标识绕变化抛是通法过刻腥画标肾记性苗质的由谓词均来解辆释的示例爆：一滤个机顾械制芒造车盲间零工件加茂工的纵简化Pr恒/T网系但统模