离散数学问题。（1.2.3.4.5.5）为各个点的度，它能画出图吗

1
可以画出图，因为度数之和是偶数，但是不是简单图。
2
不是简单图的原因。假设图是简单图，题目中有两个度为5的顶点，每个度为5的顶点都与其他5个顶点相连，剩下的4个非度为5的顶点，每个顶点度数必然大于2，与题目中存在度为1的顶点矛盾。可以画出图，但是不是简单图，是带有自回路或者重边的图。

9阶无向图的每个顶点的度数为5或6，至少有6个5度顶点。

解：本题利用了握手定理进行求解。

因为6个n阶无向图边数为n(n-1)/2

又根据握手定理:n(n-1)/22=结点数

根据题意可以算的结点数为72

然后假设度数为5的结点数为1，那么度数为6的结点数不为整数，则1舍去；依次类推，度数为5的结点数之少6个 。

扩展资料：

握手定理的推算与应用：

1、顶点的度数

设G=<V，E>为一无向图，v∈V，称v作为边的端点次数之和为v的度数，简称为度，记做 dG(v)，在不发生混淆时，简记为d(v)。设D=<V，E>为有向图，v∈V，称v作为边的始点次数之和为v的出度，记做(v)，简记作d+(v)。

称v作为边的终点次数之和为v的入度，记做(v)，简记作d-(v)，称d+(v)+d-(v)为v的度数，记做d(v)。

2、握手定理

设G=<V,E>为任意无向图，V={v1,v2,…,vn}，|E|=m，则所有顶点的度数和=2m、

证 G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，当然，m条边，共提供2m度。

定理142(握手定理) 设D=<V,E>为任意有向图，V={v1,v2,…,vn}，|E|=m，

则所有顶点的度数和=2m，且出度=入度=m。

参考资料来源：百度百科-握手定理

一、求出这个图的补图　 （1）输入无向图的各边所关联的顶点对，确定每个顶点度，以及图的最大度数和最小度数，求出这个图的补图。
（2）输入有向图的各边所关联的顶点对，确定每个顶点的出度和入度。
二、　编写一个程序，要求于无向图和有向图都能做到：输入图的邻接矩阵和正整数n，求长度为n的链和圈。
三、模拟判断一个程序中是否存在递归的函数，若存在，如何消除递归。
四、输入图的边，确定这是否为连通图。
（1）若不是连通图，则确定连通分图的个数；
（2）若是连通图，判断是否存在割边和割点，若存在各是什么？
五、输入一个多重图各边关联的顶点对。
（1） 判断它是否存在欧拉圈，若存在，则求出一个欧拉圈；
（2）若不存在，则判断是否存在一个欧拉链，若存在则求之。
六、输入一个简单图的边列表。
（1）确定是否存在哈密尔顿圈，若存在求该哈密尔顿圈；
（2）若不存在，判断是否存在哈密尔顿链，若存在则求之。
七、自选一个算法求货郎担问题。
八、给定带权连通简单图的边及权列表，输入图中两个顶点，求两点是否可达？若可达距离为多少？并输出这条最短的链。
提示：
可以使用Dijkstra算法——迪杰斯特拉算法）
九、给定无向图的边列表，对该图进行着色，求着色数。
十、输入一个加权无向简单图的边及权列表，求最小生成树，以及这棵最小生成树的权。
十一、输入一段文章，全部用小写字母，求各字母的哈夫曼编码。
十二、要给n个人分配m个资源，输入每个人可以获得的资源情况，求最大匹配，
要求所有资源在满足尽可能多的人获得的情况下，全部分配出去。

---