大门|大门-CS-2014-（第1组）|问题62-yiteyi-C++库

d1>=d2>=d1的有序n元组（d1，d2，…，dn）⋯ >= 如果存在一个简单的无向图，其中n个顶点的度数分别为d1、d2、…、dn，则称为图。以下哪个6元组不是图形？ （A） (1, 1, 1, 1, 1, 1) （B） (2, 2, 2, 2, 2, 2) （C） (3, 3, 3, 1, 0, 0) （D） (3, 2, 1, 1, 1, 0) 答复: （C） 说明： 给定的度集（3,3,3,1,0,0）不可能生成所需的图。使用这个6元组，形成的图将是一个不相交的无向图，其中图的两个顶点不应连接到图的任何其他顶点（即，两个顶点的度都为0）。对于剩下的4个顶点，图需要满足度（3，3，3，1）。

null

让我们借助图表的逻辑结构来了解这一点：

假设顶点标记为其程度应分别为<3,3,3,1,0,0>。

图片[1]-大门|大门-CS-2014-（第1组）|问题62-yiteyi-C++库

现在E和F不应该连接到图中的任何顶点。A、B、C和D的度数应分别为<3、3、3、1>。现在，为了满足A、B和C的要求，节点D将永远无法将其度设为1。它的学位也将变成3。如上图所示。

因此，元组<3,3,3,1,0,0>不是图形。

这个问题的小测验

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章