*【例4】（渡河问题）这是一个古老的趣味数学问题，在世界不同国家与民族中有着不同的表述形式。今设一人携带狼、羊、菜，须从一条小河的此岸渡往对岸。河边仅有一条小船，容量为2。当人不在场时，狼要吃羊、羊要吃菜。问：应怎样渡河，才能使大家安全到达对岸，且小船在河上的来回次数最少。(船上必须要有人)*【解】记M代表人、W代表狼、S代表羊、V代表菜。以河的此岸为考察基点，则开始状态为MWSV，结束状态为Φ。共有16种状态：MWSV、MWS、MWV、MSV、WSV、MW、MS、MV、WS、WV、SV、M、W、S、V、Φ。其中，有6种不允许出现，即：WSV、MW、MV、WS、SV、M。于是，可能的状态仅有10种。*以每个状态作为顶点，构造相应的图（如图5-8所示），其中，边的连接原则为：若状态甲经一次渡河可变为乙，则连一条边。从而，渡河问题就归结为求MWSV→Φ的最短路。(船上必须要有人)（算法形式化方面的内容）图5-8MWSVMWSMWVMSVMSWVWSVΦ**第五章图论与网络优化*子图定义：如果V1?V2,E1?E2称G1是G2的子图；设G1=[V1,E1],G2=[V2,E2]（1）部分子图：如果V1=V2,E1?E2称G1是G2的部分子图；（2）真子图：如果V1?V2,E1?E2称G1是G2的真子图；(3)生成子图：V1?V2，E1={［vi,vj］｜vi,vj∈V1}?E2，则G1称为G2中由V1生成的子图，记作G1=G(V1)，简称为G1是G2的生成子图(4)支撑子图：V1=V2，E1?E2，且保持G2原有的连通性，则G1称为G2的支撑子图。四.子图*G1G3是G1的真子图G2是G1的部分子图但是否是G1的生成子图？G5是否是G1的生成子图？G4是G1的支撑子图，*五、图的矩阵表示定义：则p×q阶矩阵[mij]称为G的关联矩阵。例：求下图的关联矩阵。e1e2e3e4e5e6e7v11110000v20102100v31010010v40000111v500000011.关联矩阵v1v5v4v3v2e2e6e3e5e4e1e7*2.邻接矩阵则p×p阶矩阵[uij]称为G的邻接矩阵。例：求下图的邻接矩阵。定义v1v2v3v4v5v101200v211010v320010v401101v500010v6v1v5v4v3v2e12e34e13e24e22e13e45*将一个图的结构表示为矩阵形式具有唯一性，并可以方便地为计算机提供代数形式的数据输入。一般而言，对于边数较少的稀疏图来说，采用关联矩阵可以占用相对少的计算机内存；对于边数较多的稠密图来说，则采用邻接矩阵更为节省。*§5-3树及其优化问题一、树及其性质在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。例5.3已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。*如果用六个点v1…v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。v6v3v4v2v5v1*v6v3v4v2v5v1表示任意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。下图是一个不含圈的连通图，代表了一个电话线网。*定义6：一个无圈的连通图叫做树。树一般记为T．作为树定义还可以有以下几种表述：(1)T连通且无圈或回路；(2)T无圈且有n－1条边（如果有n个结点）；(3)T连通有n－1条边；(4)T无回路，但不相邻的两个结点之间联以一边，恰得一个圈；(5)T连通，但去掉T的任意一条边，T就不连通了；（亦即，在点集合相同的图中，树是含边数最少的连通图。）(6)T的任意两个结点之间恰有一条初等链．*下面介绍树