图论习题+谓词逻辑测验题2.ppt

Powerpoint Templates Page * Powerpoint Templates 图论习题 作业16 3. 求图4-1所示图中结点v1到其他所有结点的最短路径及最短距离，并填表。 步骤 永久结点集P 最近 邻接点 最短距离 D(v2) D(v3) D(v4) D(v5) D(v6) D(v7) D(v8) D(v9) D(v10) D(v11) 1 2 3 4 5 6 7 8 9 10 11 步骤 永久结点集P 最近 邻接点 最短距离 D(v2) D(v3) D(v4) D(v5) D(v6) D(v7) D(v8) D(v9) D(v10) D(v11) 1 2 3 4 5 6 7 8 9 10 11 v1 2 8 1 ∞ 2 ∞ ∞ ∞ ∞ ∞ ∞ 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* v4 1 v1v4v2 v1v4v2v5 V v2 v5 v8 v6 v3 v7 v10 v9 v11 2 3 5 6 7 9 10 11 13 2* v1v4 v1v4v2v5v8 v1v4v2v5v8v6 v1v4v2v5v8v6v3 v1v4v2v5v8v6v3 v7 v1v4v2v5v8v6v3 v7v10 v1v4v2v5v8v6v3 v7v10v9 2* 2* 2* 2* 2* 2* 2* 2* 7* 7* 7* 7* 7* 7 8 8 8 8 3 3* 3* 3* 3* 3* 3* 3* 3* 6* 6* 6* 6* 6* 6* 6 6 9* ∞ ∞ ∞ 5* 11* 10* 13* 9* 9* 9* 9 10 10 10 10 10 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 5 5* 5* 5* 5* 5* 5* 12 12 12 12 12 11 11* 10* 10* 10 13 ∞ ∞ ∞ ∞ 14 14 14 14 14 14 步骤 永久结点集P 最近 邻接点 最短距离 D(v2) D(v3) D(v4) D(v5) D(v6) D(v7) D(v8) D(v9) D(v10) D(v11) 1 2 3 4 5 6 7 8 9 10 11 v1 2 8 1 ∞ 2 ∞ ∞ ∞ ∞ ∞ ∞ 1* 1* 1* 1* 1* 1* 1* 1* 1* 1* v4 1 v1v4v2 v1v4v2v5 V v2 v5 v8 v6 v3 v7 v10 v9 v11 2 3 5 6 7 9 10 11 13 2* v1v4 v1v4v2v5v8 v1v4v2v5v8v6 v1v4v2v5v8v6v3 v1v4v2v5v8v6v3 v7 v1v4v2v5v8v6v3 v7v10 v1v4v2v5v8v6v3 v7v10v9 2* 2* 2* 2* 2* 2* 2* 2* 7* 7* 7* 7* 7* 7 8 8 8 8 3 3* 3* 3* 3* 3* 3* 3* 3* 6* 6* 6* 6* 6* 6* 6 6 9* ∞ ∞ ∞ 5* 11* 10* 13* 9* 9* 9* 9 10 10 10 10 10 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 5 5* 5* 5* 5* 5* 5* 12 12 12 12 12 11 11* 10* 10* 10 13 ∞ ∞ ∞ ∞ 14 14 14 14 14 14 v1到v11的最短距离为13,最短路径为__________________________ 作业16 1.某公司在六个城市C1, C2, …, C6中有分公司，从Ci到Cj的直接航程票价在下述矩阵的(i, j)位置上. (∞表示无直接航线). 该公司想要一张任意两城市之间的票价最便宜的路线表，试做出这样的表格。 作业16 2. 在图4-2中 ⑴ 求邻接矩阵A； ⑵ 求v1到v4长度为4的路的数目； ⑶ 求经过v1长度为3的回路数的数目； ⑷ 求长度小于等于3的路有多少？其中回路有多少条？ 图4-2 作业17——特殊图 4. 饱和烃的分子结构图是一棵树，其中每个碳原子结点的度为4，每个氢原子结点的度为1。证明若该饱和烃含n个碳原子，那么它就相应的含有2n+2个氢原子。 3. (1) 证明含有n个顶点的树中所有顶点度数之和为2n-2. (2)设d1, d2, …, dn是n个正整数；且 。证明存在一棵 结点度数为d1, d2,…, dn的树。 作业15中1. (1)证明非负整数的序列（d1,d2,…,dn） 为某个图的度序