巧用他山之石，用图论的方法巧解逻辑推理问题（18年3月23日）

家长是孩子最好的老师。

这是奥数君第446天给出奥数题讲解。

今天的题目是关于排列组合问题，

所用知识不超过小学4年级。

题目（5星难度）：

有7名江湖人物在探险，他们每人恰好有4个朋友和2个敌人，但没有3个人是两两都是敌人。请问这7个人可以组成多少个两两都是朋友的三人同盟？

答案：7个。

辅导办法:

将题目写给小朋友，让他自行思考解答，若20分钟还不能解答，由家长进行讲解。

讲解思路：

这道题乍看上去是逻辑推理问题，

但要列表分析时相当复杂。

为此，我们采用图论的方法。

步骤1：

先思考第一个问题，

如何应用图论的方法？

如果将这7个人看作平面上7个点，

将敌对关系看作相邻，

将朋友关系看作不相邻，

将敌对关系相连之后，

这7个点恰好是一个7边形。

步骤2：

再思考第二个问题，

两两都是朋友的三人同盟在图中是什么关系？

这个问题很简单，

就是三个互不相邻的点。

步骤3：

再思考第三个问题，

有多少个三人同盟？

从步骤2知道，

实质就是找三个两两不相邻的点。

可以从图形上看出，

满足条件的3个点共7组：

ACE,ACF,ADF,BDF,BDG,BEG,CEG。