设n阶图G中有m 条边，每个结点的度数不是k的是k+1，若G中有小个k度顶点：Nk+1个k+1度顶点，则NK=

首先，根据握手定理，图G中所有顶点的度数和为2m。因为每个非k度顶点的度数都是k+1，所以有：

N(k+1)(k+1) + Nk(k) = 2m

又因为G中有Nk个k度顶点和N(k+1)个(k+1)度顶点，所以有：

Nk + N(k+1) = n

将上述两个式子代入握手定理得：

N(k+1)(k+1) + Nk(k) = 2m
Nk + N(k+1) = n
=> N(k+1)(k+1) + (n-Nk)(k+1-k) = 2m
=> N(k+1)(k+1) + (n-Nk) = 2m
=> N(k+1)(k+1) + n - Nk = 2m
=> N(k+1)(k+1) - Nk = 2m - n

由于每个顶点的度数都是非负整数，因此有：

Nk >= 0
N(k+1) >= 0

将上述不等式代入上面的式子得：

N(k+1)(k+1) - Nk = 2m - n
=> N(k+1)(k+1) >= 2m - n
=> Nk <= (n - 2m + n/(k+1)) / k

因为Nk是整数，所以有：

Nk <= floor((n - 2m + n/(k+1)) / k)

又因为NK = n - N(k+1)，所以有：

NK = n - N(k+1) = n - (n-Nk) = Nk

综上所述：

NK = Nk <= floor((n - 2m + n/(k+1)) / k)

相关问题

2设口阶圈G中有m 条边，每个结点的度数不是k的是k+1，若G中有小个k度顶点：Nos 个k+1度顶点，则NK=

根据握手定理，对于一个无向图 G，其所有顶点的度数之和等于 2m，其中 m 为边数。设 G 中有 n 个顶点，则有以下方程成立：

n*k + Nos*(k-1) + NK*(k+1) = 2m

又因为 G 中有 NK 个 k 度顶点和 Nos 个 k+1 度顶点，所以 n = NK + Nos，代入上式得：

(NK + Nos)*k + Nos*(k-1) + NK*(k+1) = 2m

化简得：

NK = (2m - k*Nos)/(k+1)

因此，NK 的值为 (2m - k*Nos)/(k+1)。

用团顶点数改进的上界思想解答以下问题： 考虑最大团问题的子集空间树中第i层的一个结点x，i设MinDegree(x)是以结点x为根的子树中所有结点度数的最小值。 设x.u=min{x.cn+n-i+1，MinDegree(x)+1}，依此xu的定义重写算法bbMaxClique

算法bbMaxClique的伪代码如下所示：

bbMaxClique(G):
    bestClique = []
    stack = [(G, [])]
    while stack:
        (graph, clique) = stack.pop()
        if not graph:
            if len(clique) > len(bestClique):
                bestClique = clique
        else:
            # Choose a pivot vertex with maximum degree
            pivot = max(graph, key=lambda v: len(graph[v]))
            for vertex in graph[pivot]:
                # Only consider vertices that have at least as many neighbors as the pivot
                if vertex in graph and len(graph[vertex]) >= len(graph[pivot]):
                    # Update the degree sequence of the remaining vertices
                    neighbors = graph[vertex]
                    graph = {v: neighbors.intersection(graph[v]) for v in graph if v in neighbors}
                    # Add the chosen vertex to the clique and continue searching
                    stack.append((graph, clique + [vertex]))
    return bestClique

我们可以根据上述的思想来改进bbMaxClique算法，具体的改进如下：

1. 在算法的开始，我们定义一个字典`min_degrees`来存储每个结点的MinDegree值。初始时，我们将所有结点的MinDegree值设为0。

2. 在算法的while循环中，在选择中心点时，我们可以选择MinDegree值最大的结点。

3. 选择了中心点后，我们可以按照以下方式更新该结点的x.u值：

   x.u = min(x.cn + n - i + 1, min_degrees[x] + 1)

注意到这里的x.cn是指以x为中心点的团的大小，n是图G的结点数，i是当前子集树的层数。

4. 在算法的内部循环中，我们只考虑MinDegree值大于等于当前结点x.u的结点作为候选点。

   candidates = [v for v in graph if min_degrees[v] >= x.u]

5. 在递归调用算法时，我们需要更新每个子树中结点的MinDegree值。具体地，对于每个子树中的结点v，我们可以按照以下方式更新它的MinDegree值：

   min_degrees[v] = max(min_degrees[v], len(graph[v]) - 1)

注意到这里，我们将v的MinDegree值更新为它的邻居数减1，因为v被选中后，它的邻居都不能再被选中了。

下面是改进后的算法bbMaxClique的伪代码：

def bbMaxClique(G):
    bestClique = []
    stack = [(G, [], {v: 0 for v in G})]
    n = len(G)
    while stack:
        (graph, clique, min_degrees) = stack.pop()
        if not graph:
            if len(clique) > len(bestClique):
                bestClique = clique
        else:
            # Choose a pivot vertex with maximum MinDegree
            pivot = max(graph, key=lambda v: min_degrees[v])
            for vertex in [v for v in graph if min_degrees[v] >= min_degrees[pivot]]:
                # Update the degree sequence of the remaining vertices
                neighbors = graph[vertex]
                graph = {v: neighbors.intersection(graph[v]) for v in graph if v in neighbors}
                # Update the MinDegree of the remaining vertices
                for v in graph:
                    min_degrees[v] = max(min_degrees[v], len(graph[v]) - 1)
                # Update the MinDegree of the chosen vertex
                min_degrees[vertex] = max(min_degrees[vertex], len(neighbors) - 1)
                # Compute xu and add the chosen vertex to the clique
                i = n - len(graph) + len(clique) + 1
                xu = min(len(clique) + len(neighbors) + 1, min_degrees[pivot] + 1, len(graph) + i)
                stack.append((graph, clique + [vertex], min_degrees))
    return bestClique

以上就是用团顶点数改进的上界思想来改进bbMaxClique算法的具体步骤。