Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大家使用,禁止任何单位和个人用作其它商业用途! -Andy Xia 2)在非连通无向图,共28条边,则至少有几个顶点?(9) 3)所有顶点的入度之和等于所有顶点出度之和的几倍?(1) 4)n个顶点的连通图至少有n-1条边。 5)用邻接矩阵表示n个顶点的无向图,至少有2(n-1)个非零元素。 6)n个顶点的有向强连通图至少有n条边 7)n个有向强连通图,最多有n(n-1)条弧,至少有n条弧 8)有n个顶点的无向图中,边数等于邻接矩阵非零元素个数之和的一半。( right) 在一个无向图中,所有顶点的度之和等于边数的2倍( right) 具有n个顶点的无向图最多有n(n-1)n2度( right) n个顶点的无向图,有小于(n-1)条边,则是非连通图,多于(n-1)条边,则一定有 回路( right) 有(n-1)条边的图肯定都是生成树。( wrong 9)如图 的 画出强连通分量,邻接表,你邻接表。并指出每个顶点的出度,入度 10)如图对称邻接矩阵 画出最小生成树。 11)重点题:如图Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia 2）在非连通无向图，共 28 条边，则至少有几个顶点？（9） 3）所有顶点的入度之和等于所有顶点出度之和的几倍？（1） 4）n 个顶点的连通图至少有 n-1 条边。 5）用邻接矩阵表示 n 个顶点的无向图，至少有 2（n-1）个非零元素。 6）n 个顶点的有向强连通图至少有 n 条边。 7）n 个有向强连通图，最多有 n（n-1）条弧，至少有 n 条弧。 8）有 n 个顶点的无向图中，边数等于邻接矩阵非零元素个数之和的一半。（right） 在一个无向图中，所有顶点的度之和等于边数的 2 倍（right） 具有 n 个顶点的无向图最多有 n（n-1）/2 度（right） n 个顶点的无向图，有小于（n-1）条边，则是非连通图，多于（n-1）条边，则一定有 回路（right） 有（n-1）条边的图肯定都是生成树。（wrong） 9）如图： ○v1 ○v2 ○v5 ○v4 ○v3 画出强连通分量，邻接表，你邻接表。并指出每个顶点的出度，入度。 10）如图对称邻接矩阵： ∞ 17 ∞ ∞ 20 22 ∞ 6 7 ∞ 12 ∞ 11 ∞ ∞ ∞ 19 15 ∞ 34 ∞ 画出最小生成树。 11）重点题：如图