一个连通无向图有3个5度点、1个4度点、3个2度点，其它都是1度，那么它的顶点个数≤？

设该图有 $n$ 个顶点，则它的边数为 $E=\frac{1}{2}\sum_{i=1}^{n} d_i$，其中 $d_i$ 表示第 $i$ 个顶点的度数。根据握手定理，边数和度数之和相等，即 $\sum_{i=1}^{n} d_i=2E$。

将题目给出的度数代入上式，得到：$$\begin{aligned} \sum_{i=1}^{n} d_i &= 3\times5+1\times4+3\times2+(n-7)\times1 \\ &= 15+4+6+(n-7) \\ &= n+18 \end{aligned}$$

又因为该图是连通的无向图，所以根据欧拉公式有 $E=n-1$。代入上式，得到：$$\begin{aligned} n+18 &= 2E \\ &= 2(n-1) \\ &= 2n-2 \end{aligned}$$

解得 $n=20$。因此，该图的顶点个数不超过 20 个。

相关问题

找到一个p阶简单图，使得最小度为p-3，但是点连通度小于最小度

为了构造这样的图，我们可以从一个$p$个顶点的完全图开始。然后，我们选择一个顶点$v$并将其与所有其他顶点连边，除了相邻的两个顶点$u$和$w$。接着，我们从每个与$v$相邻的顶点中选择$p-3$个顶点，将它们与$u$和$w$连边。最终得到的图具有$p$个顶点和$(p-1)(p-4)/2+1$条边，最小度为$p-3$，但是点连通度为$2$，因为如果$v$被移除，则图不再连通。

设计一个算法，判断无向图G是否连通。若连通返回1，否则返回0。

一个无向图G是连通的，当且仅当从图中任意一个节点出发，都能够到达图中的所有节点。因此我们可以使用深度优先搜索或广度优先搜索来遍历图，判断是否能够访问所有的节点。

以下是使用深度优先搜索的算法：

1. 随机选择一个节点作为起点，将其标记为已访问。

2. 对于该节点的所有未访问过的邻居节点，递归执行步骤1和步骤2，直到访问到所有的节点。

3. 如果访问到的节点数等于图中节点总数，则说明图是连通的；否则，图不连通。

以下是算法的伪代码实现：

function isConnected(G)
    visited = [false, false, ..., false] // 初始化visited数组
    startNode = getRandomNode(G) // 随机选择一个起点
    dfs(startNode, visited, G) // 从起点开始深度优先搜索
    for i = 0 to G.numNodes-1 do // 判断是否所有节点都被访问过
        if not visited[i] then
            return 0 // 存在未访问过的节点，图不连通
    return 1 // 所有节点都被访问过，图连通

function dfs(node, visited, G)
    visited[node] = true // 标记节点为已访问
    for neighbor in G.getNeighbors(node) do // 遍历邻居节点
        if not visited[neighbor] then // 如果邻居节点未被访问过
            dfs(neighbor, visited, G) // 递归访问邻居节点

其中，`getRandomNode(G)` 函数用于随机选择一个起点，`G.numNodes` 表示图中节点的总数，`G.getNeighbors(node)` 返回节点 `node` 的邻居节点列表。