9. G 是一个非连通无向图,共有 28 条边,则该图至少有( )个顶点。在有 n 个顶点的有向图中,若要使任意两点间可以互相到达,则至少需要( )条弧。
时间: 2024-03-31 22:35:13 浏览: 1251
对于一个非连通无向图 G,若共有28条边,则该图至少有7个顶点。这是因为无向图中的边数可以表示为 n(n-1)/2,其中 n 表示顶点数,将 n 从1开始带入公式,当 n=7 时,边数为28。
对于有 n 个顶点的有向图,若要使任意两点间可以互相到达,则至少需要 n(n-1)条弧。这是因为对于每个顶点,它可以到达除自己以外的所有顶点,因此每个顶点的出度至少为 n-1,而总弧数就是 n(n-1)。注意,这里的“弧”是有方向的边。
阅读全文