二、应用题
题0：（1996年全国数学联赛）
有n（n?6）个人聚会，已知每个人至少认识其中的[n/2]个人，而对任意的[n/2]个人，或者其中有两个人相互认识，或者余下的n-[n/2]个人中有两个人相互认识。证明这n个人中必有3个人互相认识。
注：[n/2]表示不超过n/2的最大整数。
证明 将n个人用n个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G。由条件可知，G是具有n个顶点的简单图，并且有
（1）对每个顶点x，
NG(x)?[n/2]；
（2）对V的任一个子集S，只要S＝[n/2]，S中有两个顶点相邻或V-S中有
两个顶点相邻。
需要证明G中有三个顶点两两相邻。
反证，若G中不存在三个两两相邻的顶点。在G中取两个相邻的顶点x1和y1,记NG(x1)＝{y1,y2,……,yt}和NG(y1)={x1,x2,……,xk},则NG(x1)和NG(y1)不相交，并且NG(x1)（NG(y1)）中没有相邻的顶点对。
情况一；n=2r：此时[n/2]＝r，由（1）和上述假设，t=k=r且NG(y1)＝V-NG(x1)，但NG(x1)中没有相邻的顶点对，由（2），NG(y1)中有相邻的顶点对，矛盾。
情况二；n=2r+1: 此时[n/2]＝r，由于NG(x1)和NG(y1)不相交，t?r,k?r,所以r+1?t,r+1?k。若t=r+1,则k=r，即NG(y1)=r，NG(x1)＝V-NG(y1)，由（2），NG(x1)或NG(y1)中有相邻的顶点对，矛盾。故k≠r+1，同理t≠r+1。所以t=r,k=r。记w?V- NG(x1) ∪NG(y1),由（2），w分别与NG(x1)和NG(y1)中一个顶点相邻，设wxi0?E, wyj0?E。若xi0yj0?E，则w，xi0, yj0两两相邻，矛盾。若xi0yj0?E，则与xi0相邻的顶点只能是(NG(x1)-{yj0})∪{w},与yj0相邻的顶点只能是(NG(y1)-{xj0})∪{w}。但与w相邻的点至少是3，故NG(x1)∪NG(y1)中存在一个不同于xi0和yj0顶点z与w相邻，不妨设z?NG(x1)，则z，w，xi0两两相邻，矛盾。
题1：已知图的结点集V={a,b,c,d}以及图G和图D的边集合分别为：
E(G)={(a,a), (a,b), (b,c), (a,c)}
E(D)={
试作图G和图D，写出各结点的度数，回答图G、图D是简单图还是多重图？ 解：
a ? ?d a? ?d
b? ?c b? ?c 图G 图D 例2图
图G中：deg(a)=4，deg(b)=2，deg(c)=2，deg(d)=0
图D中：deg(a)=3，deg(b)=2，deg(c)=4，deg(d)=1 图D是简单图． 其中 deg(a)=2, deg(a)=1, deg(b)=0, deg(b)=2, deg(c)=3, deg(c)=1, deg(d)=1. 题2：设简单连通无向图G有12条边，G中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3．求G中有多少个结点． 试作一个满足该条件的简单无向图． 解：设图G有x个结点，有握手定理 2?1+2?2+3?4+3?（x?2?2?3）＝12?2
3x?24?21?18?27
+
-
+
-
+
--
x＝9
图G有9个结点． 例 3图
图见例3图．（图不唯一）
题3：设简单连通无向图G有9条边，G中有4个3度结点，2个1度结点，其余结点度数为2．求G中有多少个结点．
题4 无向完全图K3，K4，及3个结点的有向完全图.
K3 K4 3个结点的有向完全图
题5：两个图同构有下列必要条件：
（1） 结点数相同； （2） 边数相同；
（3） 度数相同的结点数相同.
但它们不是两个图同构的充分条件，下图中(a)和(b)满足上述三个条件，但这两个图并不同构.
(a) (b)
到目前为止，判断两个图同构，只能根据定义，还没有其它简单而有效的方法.
题6：三名商人各带一随从乘船过河，一只小船只能容纳2人，由他们自己划行。随从们密约，在河的任一案，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大权掌握在商人手中，商人们怎样安排每次乘船方案才能安全渡河？
解：用图论模型求解如下：
? 每个状态有三个因素：此岸构成，彼岸构成，船所在。 ? ?
此岸a1 b1，a1为商人个数，b1为随从个数，a1≥b1，a1,b1=0,1,2,3，或a1=0,b1=0,1,2,3。 彼岸a2 b2，a2为商人个数，b2为随从个数，a2≥b2，a2,b2=0,1,2,3，或a2=0,b2=0,1,2,3。
? 注：a1+a2=b1+b2=3；0表示船在此岸，1表示在彼岸。
可行状态有：33|00|0，32|01|0，31|02|0，22|11|0，11|22|0，03|30|0，02|31|0，01|32|0， 32|01|1，31|02|1，30|03|1，22|11|1，11|22|1，02|31|1，01|32|1，00|33|1。
33|00|0 32|01|0 31|02|0 22|11|0 11|22|0 03|30|0 02|31|0 32|01|1 31|02|1 30|03|1 22|11|1 11|22|1 02|31|1 01|32|1 00|33|1
01|32|0
根据上图，求从33|00|0到00|33|1的路径，可得解如下：
33|00|0--31|02|1--32|01|0--30|03|1--31|02|0--11|22|1-22|11|0--02|31|1--03|30|0--01|32|1--02|31|0--00|33|1。 或：
33|00|0--31|02|1--32|01|0--30|03|1--31|02|0--11|22|1-22|11|0--02|31|1--03|30|0--01|32|1--11|22|0--00|33|1。 或：
33|00|0--22|11|1--32|01|0--30|03|1--31|02|0--11|22|1-22|11|0--02|31|1--03|30|0--01|32|1--11|22|0--00|33|1。
题7 在平面上有n个点S＝{x1,x2,……,xn}，其中任两个点之间的距离至少是1，证明在这n个点中距离为1的点对数不超过3n。 证明 首先建立一个图G＝（V，E），其中V就取S中的n个顶点，V中两个点有边相连当且仅当两点之间的距离恰好是1。则所得图G是一个简单图，S中距离为1的点对数就是G的边数。因此我们只需证明m(G)?3n。
我们考虑G中每个顶点的度，可以证明：deg(xi)?6,i=1,2, ……,n。
让xi是G中的任一个顶点，且与xi相邻的顶点为y1,y2,……,yk，则y1,y2,……,yk分布在以xi为圆心的单位圆周上。所以k= deg(xi)?6 ,i=1,2, ……,n。 由握手定理得
n2m(G)=?d(vi)?6n
i?1 故m(G)?3n。
题8 n个点由若干线段连接着。已知每一点与另外任何一点都有道路相连通。而任何两点都没有两种不同的道路。证明：线段总数为n-1。
证明 构造图G：将问题中给定的n个点作为顶点，线段作为边。根据给定的条件，所得图G是含有n个顶点的简单图，每一对顶点之间有且只有一条路连接，因此G是连通图，并且没有回路（否则，该回路上两个不同的顶点之间有两条不同的路），所以图G是一棵树。
题9：设无向图G有12条边，已知G中度数为3的节点个数为6个，其余结点的度数均小于3，问G中至少有多少顶点？
解：由定理可知，图中所有节点的度数之和应为边数的2倍，即12 x 2 =24，却掉度数为3的6个结点的总度数18，还剩6度，又由于其余结点的度数小于3，故度数只能是0，1，2，若其余结点的度数均为2，则至少需3个结点，故图G中至少有9个结点。
题10：若图G是不连通的，则G的补图G是连通的。
证明：设G=（V，E）不连通，则设其连通分支为G1，G2，…Gs，其相应的节点集为V1，V2，…Vs，任取G中的两个节点u，v∈V，
1）、若u，v分属于G中不同的连通分支，则(u,v)∈G，因此u，v在G中连通。 2）、若u，v分属于G中同一个连通分支，则从另一连通分支中任取一结点w，则(u,w)∈G，(v,w)∈G，于是在G中存在一条道路uwv，使得u，v连通。
综上所述可知，对于G中任意2个结点，u，v总有路相连，故G是连通的。
题11：当且仅当G的一条边e不包含在G的回路中，e才是G的割边（桥）。
证明：必要性：设e是连通图G的割边，e关联的两个结点为u和v。若e包含在G的一个回路中，则除边e =（u，v）外还有一条以u，v为端点的道路，故删去边e后，G仍是连通的，这与e是割边矛盾。
充分性：若e不包含在G的任一回路中，那么连接节点u和v只有边e，而不会有其他连接u和v的路，因为若连接u和v还有不同于边e的路，此路与边e就组成一个包含e的
相关推荐：
loading