本节书摘来自异步社区《趣题学算法》一书中的第1章1.4节图的性质，作者徐子珊,更多章节内容可以访问云栖社区“异步社区”公众号查看。
1.4 图的性质
有的计数问题所涉及的事物间存在着某种关系，这样的问题往往可以表示成一个图（graph）：问题中的每个事物视为一个顶点，两个顶点之间如果存在这关系，就在这两个顶点之间做一条称为边的弧。形式化描述为由问题中的各事物构成的集合，记为顶点集v={v1,v2,…,vn}，边集e={(vi, vj)| vi, vj ∈v且vi和vj具有关系}。
例如，图1-3将五个人adward、john、philips、robin和smith之间的朋友关系表示成了一个图。其中，adward与robin和smith是朋友，john与philips和robin是朋友，philips与john、robin和smith是朋友，smith与adward、philips和robin是朋友，robin与其他所有人都是朋友。
图g记为。数学家们对图的研究已经有了百年的历史，有很多很好用的性质能帮助我们轻松地解决计数问题。例如，图论中有一个著名的“握手”定理。
定义1-1
设g=为一无向图，vv，称v作为边的端点次数之和为v的度数，简称为度，记为d(v)。
对图中所有顶点的度数有如下所述的结论。
定理1-1（握手定理）
设g=为任意无向图，v={v1,v2,…,vn}，|e|=m，则
sumnolimits_{i=1}^{n}{d({{v}_{i}})=2m}
即所有顶点的度数之和为边数的2倍。
证 g中每条边（包括环）均有两个端点，所以在计算g中各顶点度数之和时，每条边均提供2度，当然，m条边，共提供2m度。
握手定理说明，图中各顶点的度数之和必为偶数。
问题描述
百度之星总决赛既是一群编程大牛一决高下的赛场，也是圈内众多网友难得的联欢，在为期一周的聚会中，总少不了各种有趣的游戏。
某年的总决赛聚会中，一个有趣的游戏是这样的：
游戏由robin主持，一共有n个人参加（包括主持人），robin让每个人说出自己在现场认识的人数（如果a认识b，则默认b也认识a），在收到所有选手报出的数据后，他来判断是否有人说谎。robin说，如果他能判断正确，希望每位选手都能在毕业后来百度工作。
为了帮robin留住这些天才，现在请您帮他出出主意吧。
特别说明：
1．每个人都认识robin。
2．认识的人中不包括自己。
输入
输入数据包含多组测试用例，每组测试用例有2行，首先一行是一个整数n (1
n为0的时候结束输入。
输出
请根据每组输入数据，帮助主持人robin进行判断：如果确定有人说谎，请输出“lie absolutely”；否则，请输出“maybe truth”。
每组数据的输出占一行。
输入样例
输出样例
解题思路
（1）数据的输入与输出
根据题面中对输入文件格式的描述，文件中有若干个测试案例，每个案例的数据以表示人数的整数n开头，然后有n-1个整数表示除主持人以外的每个人所报告的相识人数。对案例判断其中是否有人说谎，根据计算结果输出一行“maybe truth”（无人说谎）或“lie absolutely”（有人说谎）。n=0是输入结束的标志。
其中，第9行调用过程party-game(a)判断n个人中是否有人说谎，是解决一个案例的关键。
（2）处理一个案例的算法过程
在一个案例中，把两个人相互认识看成一种关系，n个人之间的认识关系将可表示成一个无向图g=。其中，顶点集v={v1,v2,…,vn}表示这n个人，边集e中元素表示两个人之间的认识关系。
利用握手定理，我们将问题中的每一个案例的所有人所报的认识的人数（包括主持人报的n−1）相加，考察和数的奇偶性，若为奇数，则肯定有人撒谎。等价地，设置一个计数器count（初始为0），检测每个人（包括主持人）所报的认识的人数，若是奇数则count增加1，根据count的奇偶性进行判断。伪代码过程表示为如下：
算法1-11 利用握手定理判断晚会中是否有客人说谎的过程
对一个案例而言，假定包括主持人在内，晚会上有n个人，则第3～5行的for循环将重复n次。所以算法对一个案例的运行时间是Θ(n)。
解决本问题的算法的c++实现代码存储于文件夹laboratory/party game中，读者可打开文件partygame.cpp研读，并试运行之。