图论—图的基本概念和例题

图论--图的基本概念1.图：1.1⽆向图的定义：⼀个⽆向图G是⼀个有序的⼆元组<V,E>，其中V是⼀个⾮空有穷集，称作顶点集，其元素称作顶点或结点。

E是⽆序积V&V的有穷多重⼦集，称作边集，其元素称作⽆向边，简称边。

注意：元素可以重复出现的集合称作多重集合。

某元素重复出现的次数称作该元素的重复度。

例如，在多重集合{a,a,b,b,b,c,d}中，a,b,c,d的重复度分别为2，3，1，1。

从多重集合的⾓度考虑，⽆元素重复出现的集合是各元素重复度均为1的多重集。

1.2有向图的定义：⼀个有向图G是⼀个有序的⼆元组<V,E>，其中V是⼀个⾮空有穷集，称作顶点集，其元素称作顶点或结点。

E是笛卡尔积V✖V的有穷多重⼦集，称作边集，其元素为有向边，简称为边。

通常⽤图形来表⽰⽆向图和有向图：⽤⼩圆圈（或实⼼点）表⽰顶点，⽤顶点之间的连线表⽰⽆向边，⽤带箭头的连线表⽰有向边。

与1.1，1.2有关的⼀些概念和定义：（1）⽆向图和有向图统称为图，但有时也把⽆向图简称作图。

通常⽤G表⽰⽆向图，D表⽰有向图，有时也⽤G泛指图（⽆向的或有向的）。

⽤V(G),E(G)分别表⽰G的顶点集和边集，|V(G)|,|E(G)|分别是G的顶点数和边数，有向图也有类似的符号。

（2）顶点数称作图的阶，n个顶点的图称作n阶图。

（3）⼀条边也没有的图称作零图，n阶零图记作N n。

1阶零图N1称作平凡图。

平凡图只有⼀个顶点，没有边。

（4）在图的定义中规定顶点集V为⾮空集，但在图的运算中可能产⽣顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记作Ø。

（5）当⽤图形表⽰图时，如果给每⼀个顶点和每⼀条边指定⼀个符号（字母或数字，当然字母还可以带下标），则称这样的图为标定图，否则称作⾮标定图。

（6）将有向图的各条有向边改成⽆向边后所得到的⽆向图称作这个有向图的基图。

（7）若两个顶点v i与v j之间有⼀条边连接，则称这两个顶点相邻。

图论导引参考答案图论导引参考答案图论是数学中的一个分支，研究的是图的性质和图之间的关系。

图由节点和边组成，节点表示对象，边表示对象之间的连接关系。

图论在计算机科学、网络分析、社交网络等领域有着广泛的应用。

本文将介绍图论的基本概念和常见算法，并提供一些参考答案来帮助读者更好地理解和应用图论。

一、图的基本概念1.1 有向图和无向图图可以分为有向图和无向图两种类型。

有向图中，边有方向，表示节点之间的单向关系；而无向图中，边没有方向，表示节点之间的双向关系。

1.2 路径和环路径是指图中一系列节点和边的连续序列，路径的长度为路径中边的数量。

如果路径的起点和终点相同，则称之为环。

1.3 连通图和连通分量在无向图中，如果任意两个节点之间都存在路径，则称该图为连通图。

连通图中的极大连通子图称为连通分量。

1.4 强连通图和强连通分量在有向图中，如果任意两个节点之间都存在路径，则称该图为强连通图。

强连通图中的极大强连通子图称为强连通分量。

二、图的存储方式2.1 邻接矩阵邻接矩阵是一种常见的图的存储方式，使用一个二维矩阵来表示图中节点之间的连接关系。

矩阵的行和列分别表示节点，矩阵中的元素表示节点之间是否存在边。

2.2 邻接表邻接表是另一种常见的图的存储方式，使用一个数组和链表的结构来表示图中节点之间的连接关系。

数组中的每个元素表示一个节点，链表中的每个节点表示与该节点相连的边。

三、常见图算法3.1 深度优先搜索（DFS）深度优先搜索是一种用于遍历图的算法。

从图中的一个节点开始，沿着一条路径一直深入直到无法继续为止，然后回溯到上一个节点，继续深入其他路径。

DFS可以用于判断图的连通性、寻找路径等问题。

3.2 广度优先搜索（BFS）广度优先搜索也是一种用于遍历图的算法。

从图中的一个节点开始，先访问其所有相邻节点，然后再依次访问这些节点的相邻节点，以此类推。

BFS可以用于计算最短路径、寻找连通分量等问题。

3.3 最小生成树算法最小生成树算法用于求解一个连通图的最小生成树，即包含图中所有节点且边的权重之和最小的子图。

图论1．图的基本概念图：由一些点和连接两点间的连线组成图1在这个图中，521,,,v v v 称为这个图的顶点，顶点之间的连线621,,,e e e 称为这个图的边。

通常我们用V 表示一个图中所有顶点的集合，用E 表示一个图中所有边的集合。

于是一个图G 通常被定义为()E V G ,=，在上图中{}521,,,v v v V =，{}621,,,e e e E = 图的阶数：一个图中含有的顶点数。

例如上图中含有5个顶点，故上图称为5阶图 有向边（弧）：如果在图的定义中要求边e 对应的序偶><b a ,是有序的，即前后顺序是不能颠倒的，则称边e 为有向边或弧。

无向边：如果在图的定义中要求边e 对应的序偶><b a ,是无序的，即前后顺序是可以颠倒的，则称边e 为无向边无向图：如果一个图中的每一条边都是无向边，则称这个图为无向图 有向图：如果一个图中的每一条边都是有向边，则称这个图为有向图 如果图的某个顶点和某条边是相联的，则称它们是相关联的顶点的次数：在无向图中把与某个顶点相关联的边数称为该顶点的次数。

环算两次，顶点v 的次数记为()v d在有向图中从顶点v 出去的边数，称为顶点v 的出度，记为()v d +进入顶点v 的边数，称为顶点v 的入度，记为()v d-，()()()v d v dv d -++=定理：一个图中所有的顶点的次数之和等于边数之和的两倍 推论：任何图中奇数次顶点的总数必为偶数例：一次聚会中，认识奇数个人的人数必为偶数 孤立点：次数为0的顶点。

图2 图3多重边：在图中，如果两个顶点之间的边多于一条，那么这几条边就称为多重边。

多重图：含有多重边的图环：如果图中某条边的起点和终点为同一个顶点，那么称这条边为环 简单图：既没有多重边又没有环的图在图中如果顶点i v 和j v 之间至少存在一条边，那么称顶点i v 和j v 是相邻的。

如果边i e 和j e 之间至少有一个共同顶点，则称边i e 和j e 是相邻的子图：设有图()111,E V G =和()221,E V G =，如果21V V ⊆并且21E E ⊆，则称图1G 是图2G 的一个子图生成子图：，如果21V V =并且21E E ⊆，则称图1G 是图2G 的一个生成子图图4图5链：以顶点开始以顶点结束的顶点和边的非空有限交替序列 例如43152v e v e v 就是一条链，而4312v e v v 却不是一条链圈：如果一条链的起点和终点是同一个顶点，则称这条链是一个圈如21152v e v e v路：当一条链中所有边和所有顶点均不相同时就称这条链为路 回路：如果一个圈中的所有边均不向图并且除第一个顶点和最后一个顶点相同外其余顶点都不相同，则称这个圈为回路连通图：如果某个图中的任何两个顶点之间至少存在一条链，则称这个图为连通图在实际的应用中，经常会涉及到图中各个顶点之间的某种联系，例如，在城市公路交通图中，需要说明两个路口之间的路段的长度，这时就需要给图的边赋以某个数值（称为线权）或给顶点赋以某个数值（称为点权），我们把这种赋以了数值的图称为加权图或网络。

图论问题一． 基本概念1．图的定义：由若干个不同的顶点与连接其中某些顶点的边所组成的图形叫做图。

用G 表示图，用V 表示所有顶点的集合，E 表示所有边的集合，并且记作G=（V ，E ）． 2．同构图：如果两个图G 与G '‘的顶点之间可以建立起一一对应，并且当且仅当G 的顶点v i 与v j 之间有k 条边相连时，G ’的相应顶点j i v v ''与之间也有k 条边相连，就认为G 与G '是相同的，称G 与G '是同构的图． 2．子图：如果对图G E E ,V V )E ,V (G )E ,V (G '⊆'⊆'''='=，则称有与是G 的子图．3．其它有关概念：（1）若在一个图G 中的两个顶点j i v v 与之间有边e 相连，则称点j i v v 与是相邻的，否则就称j i v v 与是不相邻的．（2）如果顶点v 是边e 的一个端点，称点v 与边e 是相邻的．（3）如果顶点本身也有边相连，这样的边称为环．如果连接两个顶点的边可能不止一条，若两个顶点之间有k )2k (≥条边相连，则称这些边为平行边．（4）如果一个图没有环，并且没有平行边，这样的图称为简单图．竞赛中的图论问题涉及到的图一般都是简单图．（5）如果一个简单图中，每两个顶点之间都有一条边，这样的图称为完全图，通常将有n 个顶点的完全图记为n K ．（6）在图G=(V,E)中，顶点个数|V|和边数|E|都是有限的，则称图G 是有限图；如果|V|或|E|是无限的，则称G 为无限图．1v 2v 4v 3v 1v '2v '3'4v '1v ''2v ''3v ''4v ''1G 2G 3G二．例题精选1．设S 为平面上的一个有限点集（含点数不少于5），若其中若干个点涂红色，其余点涂上兰色，又设任何三个同色点不共线，求证：存在一个同色三角形，且它至少有一条边不含另一种颜色． 证明：无穷递降法2．若平面上有997个点，如果两点连成一条线段，且中点涂成红色，证明：平面上至少有1991个红点，试找到正好是1991个红点的特例．证明：设997个点中M 、N 之间的距离最大，以M 、N 为圆心，2MN为半径作圆，如图，设P 为其它995 个点中的任意一个点，则PM 、PN 的中点R 、Q 都在圆M 、 N 内，且这些点个不相同，所以至少有995×2+1=1991个点．特例：在x 轴上横坐标依次为1，2，3，．．．，997的997个点，满足题设条件．3．正六边形被分为24个全等的三角形，在图中的19个结点处写上不同的数，证明：在24个三角形中，至少有7个三角形，其顶点处的三个数是按逆时针方向递增顺序书写的．证明：（１）正六边形的12（2）一个逆三角形有2条逆边，一个顺三角形有1条逆边；（3）除掉正六边形的边，图中有（24×3-12）÷2=30条边，没条边恰好是一个三角形的一条逆向边．综上，设24个三角形中有m 个逆三角形，n 个顺三角形，则有731224≥⇒⎪⎩⎪⎨⎧≥+=+m n m n m ，得证．RRRBBBMNPR QE 逆三角形顺三角形1231234．在正n 边形中，要求其每条边及每条对角线都染上任一种颜色，使得这些线段中任意两条有公共点的染不同颜色，为此，至少需要多少种颜色？的n 需要n 种颜色．当n=3 当n>3时，作正n 设MN 是另外一条边或对角线，若MN//BC ，则将MN 染成与BC 同色；若BC MN //，过A 引直线直线m//MN ，交圆于K ，则弧KN=弧AM ，所以K 也是正n 边形的顶点，即AK 是由A 出发的边或对角线，将MN 染成与AK 同色，所以n 种颜色足够了．5．某次大型活动有2003人参加，已知他们每个人都至少和其中的一个人握过手，证明：必有一个人至少和其中的两个人握过手． 证明：从5个点开始考虑奇数个点即可． 如图6．现有九个人，已知任意三人中总有两个人互相认识，证明：必有四人互相之间都认识． 证明：9个顶点的简单图，利用抽屉原理7．有n 名选手n 21A ,,A ,A 参加数学竞赛，其中有些选手是互相认识的，而且任何两个不相识的选手都恰好有两个共同的熟人，若已知选手21AA 与是互相认识，但他们没有共同的熟人，证明他们的熟人一样多．M NE P Q∙R∙1A 2A 3A 4A 5A KMNA1A 2A )(2A n )(1A n iA jA 1A 2A )(2A n )(1A n iA jA 'jA 'i A证明：的熟人一一对应与21A A8．有n （n>3）个人，他们之间有些人互相认识，有些人互相不认识，而且至少有一个人没有与其他人都认识，问与其他人都认识的人数的最大值是多少？解：作图G ：用n 个点表示这n 个人，当两人认识，则在两相应顶点之间连一线，否则之间不连线．由于至少有一个人与其他人不认识，所以图G 中至少有两点之间没连线，设21A A 与之间没连线，则图G 的边数最多时，G 为21A A K n -，故最大值为n-2．9．次会议有n 名教授n 21A ,A ,A 参加，证明可以将这n 个人分为两组，使得每一个人A i 在另一组中认识的人数不少于他在同一组中认识的人数．证明：用n 个点n A A A ,,,21 表示这n 名教授，并在相互认识的人之间连一条边，且将同一组间的连线染成红色，不同组之间的线染成蓝色．将这n 个点任意分成两组，只有有限种分法．考虑在两组之间的蓝线条数S ，其中必存在一种分法，使S 达到最大值，此时有i A 在两组内引出的边的条数分别为),,2,1,(,n i l l l l i i i i ='≥'，否则，若对i A 有'<i i l l ，将i A 调到另一组，S 增加了i i l l -'条，矛盾，得证．10．有三所中学，每所有学生n 名，每名学生都认识其他两所中学的n+1名学生，证明：从每所中学可以选出一名学生，使选出来的3名学生互相认识．证：用3n 个顶点表示这些学生，三所中学的学生组成的三个顶点集合分别记为A 、B 、C ，设M 和N 是两所不同学校的学生，而且是互相认识的，则在M 与N 之间连一线，得一个简单图．记A 中的元素x 在B 、C 中的相邻元素个数为k 和l ，则k+l =n+1．设k 与l 中大的记作m(x)，让x 跑遍A ，m(x)的最大值记作A m ，同理记C B m m ,分别为集合B 、C 中的所有元素在另两个集合中相邻元素个数的最大值．记m 是A m ，C B m m ,中最大者，不妨设m=A m ，且的顶点相邻的顶点集和中和使得100,B x B A x ∈数为m ，于是C 中与00,11x C z m n x 与设相邻的顶点数为∈≥-+相邻．如果有中中的一个三角形．若是相邻，则与1000010B G z y x z B y ∆∈每一个y 与中相邻与．因此，相邻的顶点数与都不相邻，则A z m n z B z 000-≤的顶点数1)(1+=--+≥m m n n 与m 的最大性矛盾，得证．三．巩固练习1．有n 个药箱，每个药箱里有一种相同的药，每种药恰好在两个药箱里出现，问有多少种药？)1(21-n n 2．18个队进行比赛，每一轮中每一个队与另一个队比赛一场，并且在其他轮比赛中这两个已赛过的队彼此不再比赛，现在比赛已进行完8轮，证明一定有三个队在前8轮比赛中，彼此之间尚未比赛过．3．某次会议有n 名代表出席，已知任意的四名代表中都有一个人与其余的三个人握过手，证明任意的四名代表中必有一个人与其余的n-1名代表都握过手．4．空间１８个点，任三点不共线，它们的两两连线染上红色或兰色，每条线段仅染一色．试证明其中一定存在一个同色的完全四边形．图论问题（二）用图论解决问题躲基本思路：把要考察的对象作为顶点，把对象之间是否具有我们所关注的某种关系作为顶点连边地条件．这样，就可以把一个具体问题化归成图论问题，用图论的理论和方法进行探讨，即使在图论中没有现成定理直接给出问题的解答，也可以（1）借助图论的分析方法拓宽解题思路；（2）把抽象的问题化为直观问题；（3）把复杂的逻辑关系问题化为简明的数量分析问题。

图论参考答案图论参考答案图论作为一门数学分支，研究的是图的性质与关系。

图由节点（顶点）和连接节点的边组成，它可以用来解决许多实际问题，如网络规划、社交网络分析等。

本文将从图的基本概念、图的表示方法、图的遍历算法以及图的应用等方面进行探讨。

一、图的基本概念图由节点和边构成，节点表示对象，边表示节点之间的关系。

图可以分为有向图和无向图两种类型。

在有向图中，边有方向，表示从一个节点到另一个节点的箭头；而在无向图中，边没有方向，表示节点之间的双向关系。

图中的节点可以用来表示不同的实体，如人、地点、物品等。

而边则表示节点之间的关系，可以是实体之间的联系、交互或者依赖关系等。

图的度是指与节点相连的边的数量。

在无向图中，节点的度等于与之相连的边的数量；而在有向图中，节点的度分为入度和出度，入度表示指向该节点的边的数量，出度表示从该节点出发的边的数量。

二、图的表示方法图可以使用邻接矩阵和邻接表两种方式进行表示。

邻接矩阵是一个二维数组，其中的元素表示节点之间的关系。

如果节点i和节点j之间有边相连，则邻接矩阵中的第i行第j列的元素为1；否则为0。

邻接矩阵的优点是可以快速判断两个节点之间是否有边相连，但是对于稀疏图来说，会浪费大量的空间。

邻接表是一种链表的形式，其中每个节点都有一个指针指向与之相连的节点。

邻接表的优点是可以有效地节省空间，适用于稀疏图。

但是在判断两个节点之间是否有边相连时，需要遍历链表，效率较低。

三、图的遍历算法图的遍历算法是指以某个节点为起点，按照一定的规则依次访问图中的所有节点。

深度优先搜索（DFS）是一种常用的图遍历算法。

它的思想是从起始节点开始，沿着一条路径一直访问到最后一个节点，然后回溯到上一个节点，继续访问其他路径。

DFS可以用递归或者栈来实现。

广度优先搜索（BFS）是另一种常用的图遍历算法。

它的思想是从起始节点开始，先访问所有与起始节点直接相连的节点，然后再依次访问与这些节点相连的节点。

图论及应用习题答案图论及应用习题答案图论是数学中的一个分支，研究的是图的性质和图之间的关系。

图论在现实生活中有着广泛的应用，涵盖了许多领域，如计算机科学、通信网络、社交网络等。

本文将为读者提供一些关于图论及应用的习题答案，帮助读者更好地理解和应用图论知识。

1. 图的基本概念题目：下面哪个不是图的基本概念？A. 顶点B. 边C. 路径D. 线段答案：D. 线段。

图的基本概念包括顶点、边和路径。

线段是指两个点之间的连线，而在图论中，我们使用边来表示两个顶点之间的关系。

2. 图的表示方法题目：以下哪个不是图的表示方法？A. 邻接矩阵B. 邻接表C. 边列表D. 二叉树答案：D. 二叉树。

图的表示方法包括邻接矩阵、邻接表和边列表。

二叉树是一种特殊的树结构，与图的表示方法无关。

3. 图的遍历算法题目：以下哪个不是图的遍历算法？A. 深度优先搜索B. 广度优先搜索C. 迪杰斯特拉算法D. 克鲁斯卡尔算法答案：D. 克鲁斯卡尔算法。

图的遍历算法包括深度优先搜索和广度优先搜索，用于遍历图中的所有顶点。

迪杰斯特拉算法是用于求解最短路径的算法，与图的遍历算法有所不同。

4. 最小生成树题目：以下哪个算法不是用于求解最小生成树？A. 克鲁斯卡尔算法B. 普里姆算法C. 弗洛伊德算法D. 公交车换乘算法答案：D. 公交车换乘算法。

最小生成树是指包含图中所有顶点的一棵树，使得树的边的权重之和最小。

克鲁斯卡尔算法和普里姆算法是常用的求解最小生成树的算法，而弗洛伊德算法是用于求解最短路径的算法，与最小生成树问题有所不同。

5. 图的应用题目：以下哪个不是图的应用？A. 社交网络分析B. 路径规划C. 图像处理D. 数字逻辑电路设计答案：D. 数字逻辑电路设计。

图的应用广泛存在于社交网络分析、路径规划和图像处理等领域。

数字逻辑电路设计虽然也涉及到图的概念，但与图的应用有所不同。

总结：图论是一门重要的数学分支，具有广泛的应用价值。

通过本文提供的习题答案，读者可以更好地理解和应用图论知识。

图论及应用参考答案图论及应用参考答案图论是数学中的一个重要分支，研究的是图的性质和图之间的关系。

图由节点（顶点）和边组成，节点代表对象，边代表对象之间的关系。

图论不仅在数学中有广泛的应用，也在计算机科学、物理学、生物学等领域中发挥着重要的作用。

本文将介绍图论的基本概念和一些应用。

一、图论的基本概念1. 图的类型图分为有向图和无向图。

有向图中的边有方向，表示节点之间的单向关系；无向图中的边没有方向，表示节点之间的双向关系。

2. 图的表示方法图可以用邻接矩阵或邻接表来表示。

邻接矩阵是一个二维数组，其中的元素表示节点之间是否有边相连；邻接表是一个链表数组，数组中的每个元素对应一个节点，链表中存储了该节点相邻的节点。

3. 图的性质图的性质包括节点的度、连通性和路径等。

节点的度是指与该节点相连的边的数量；连通性指的是图中任意两个节点之间是否存在路径；路径是指由边连接的节点序列。

二、图论在计算机科学中的应用1. 最短路径算法最短路径算法是图论中的经典问题之一，它用于计算图中两个节点之间的最短路径。

著名的最短路径算法有迪杰斯特拉算法和弗洛伊德算法。

这些算法在网络路由、地图导航等领域中有广泛的应用。

2. 最小生成树算法最小生成树算法用于找到一个连通图的最小生成树，即包含所有节点且边的权重之和最小的子图。

普里姆算法和克鲁斯卡尔算法是常用的最小生成树算法。

这些算法在电力网络规划、通信网络设计等领域中有重要的应用。

3. 图的着色问题图的着色问题是指给定一个图，将每个节点着上不同的颜色，使得相邻节点之间的颜色不同。

这个问题在地图着色、任务调度等方面有实际应用。

三、图论在物理学中的应用1. 粒子物理学在粒子物理学中，图论被用来描述和分析粒子之间的相互作用。

图论模型可以帮助研究粒子的衰变、散射等过程，为理解物质的基本结构提供了重要的工具。

2. 统计物理学图论在统计物理学中也有应用。

例如，渗透模型中的图可以用来研究流体在多孔介质中的渗透性质，为石油勘探、水资源管理等提供了理论基础。

图论问题一． 基本概念1．图的定义：由若干个不同的顶点与连接其中某些顶点的边所组成的图形叫做图。

用G 表示图，用V 表示所有顶点的集合，E 表示所有边的集合，并且记作G=（V ，E ）． 2．同构图：如果两个图G 与G '‘的顶点之间可以建立起一一对应，并且当且仅当G 的顶点v i 与v j 之间有k 条边相连时，G ’的相应顶点j i v v ''与之间也有k 条边相连，就认为G 与G '是相同的，称G 与G '是同构的图． 2．子图：如果对图G E E ,V V )E ,V (G )E ,V (G '⊆'⊆'''='=，则称有与是G 的子图． 3．其它有关概念：（1）若在一个图G 中的两个顶点j i v v 与之间有边e 相连，则称点j i v v 与是相邻的，否则就称j i v v 与是不相邻的．（2）如果顶点v 是边e 的一个端点，称点v 与边e 是相邻的．（3）如果顶点本身也有边相连，这样的边称为环．如果连接两个顶点的边可能不止一条，若两个顶点之间有k )2k (≥条边相连，则称这些边为平行边．（4）如果一个图没有环，并且没有平行边，这样的图称为简单图．竞赛中的图论问题涉及到的图一般都是简单图．（5）如果一个简单图中，每两个顶点之间都有一条边，这样的图称为完全图，通常将有n 个顶点的完全图记为n K ．（6）在图G=(V ,E)中，顶点个数|V|和边数|E|都是有限的，则称图G 是有限图；如果|V|或|E|是无限的，则称G 为无限图．1v 2v 4v 3v 1v '2v 3'4v '1v ''2v ''3v ''4v ''1G 2G 3G二．例题精选1．设S 为平面上的一个有限点集（含点数不少于5），若其中若干个点涂红色，其余点涂上兰色，又设任何三个同色点不共线，求证：存在一个同色三角形，且它至少有一条边不含另一种颜色． 证明：无穷递降法2．若平面上有997个点，如果两点连成一条线段，且中点涂成红色，证明：平面上至少有1991个红点，试找到正好是1991个红点的特例．证明：设997个点中M 、N 之间的距离最大，以M 、N 为圆心，2MN为半径作圆，如图，设P 为其它995 个点中的任意一个点，则PM 、 PN 的中点R 、Q 都在圆M 、 N 内，且这些点个不相同，所以至少有995×2+1=1991个点．特例：在x 轴上横坐标依次为1，2，3，．．．，997的997个点，满足题设条件．3．正六边形被分为24个全等的三角形，在图中的19个结点处写上不同的数，证明：在24个三角形中，至少有7个三角形，其顶点处的三个数是按逆时针方向递增顺序书写的．证明：（１）正六边形的12（2）一个逆三角形有2条逆边，一个顺三角形有1条逆边；（3）除掉正六边形的边，图中有（24×3-12）÷2=30条边，没条边恰好是一个三角形的一条逆向边．综上，设24个三角形中有m 个逆三角形，n 个顺三角形，则有731224≥⇒⎪⎩⎪⎨⎧≥+=+m n m n m ，得证． RRRBBBMNPR QE 逆三角形顺三角形1231234．在正n 边形中，要求其每条边及每条对角线都染上任一种颜色，使得这些线段中任意两条有公共点的染不同颜色，为此，至少需要多少种颜色？的n 需要n 种颜色．当n=3 当n>3时，作正n 设MN 是另外一条边或对角线，若MN//BC ，则将MN 染成与BC 同色；若BC MN //，过A 引直线直线m//MN ，交圆于K ，则弧KN=弧AM ，所以K 也是正n 边形的顶点，即AK 是由A 出发的边或对角线，将MN 染成与AK 同色，所以n 种颜色足够了．5．某次大型活动有2003人参加，已知他们每个人都至少和其中的一个人握过手，证明：必有一个人至少和其中的两个人握过手． 证明：从5个点开始考虑奇数个点即可． 如图6．现有九个人，已知任意三人中总有两个人互相认识，证明：必有四人互相之间都认识． 证明：9个顶点的简单图，利用抽屉原理7．有n 名选手n 21A ,,A ,A 参加数学竞赛，其中有些选手是互相认识的，而且任何两个不相识的选手都恰好有两个共同的熟人，若已知选手21AA 与是互相认识，但他们没有共同的熟人，证明他们的熟人一样多．M NEP Q∙R∙1A 2A 3A 4A 5A KMNA1A 2A )(2A n )(1A n iA jA 1A 2A )(2A n )(1A n iA jA 'jA 'i A证明：的熟人一一对应与21A A8．有n （n>3）个人，他们之间有些人互相认识，有些人互相不认识，而且至少有一个人没有与其他人都认识，问与其他人都认识的人数的最大值是多少？解：作图G ：用n 个点表示这n 个人，当两人认识，则在两相应顶点之间连一线，否则之间不连线．由于至少有一个人与其他人不认识，所以图G 中至少有两点之间没连线，设21A A 与之间没连线，则图G 的边数最多时，G 为21A A K n -，故最大值为n-2．9．次会议有n 名教授n 21A ,A ,A 参加，证明可以将这n 个人分为两组，使得每一个人A i 在另一组中认识的人数不少于他在同一组中认识的人数．证明：用n 个点n A A A ,,,21 表示这n 名教授，并在相互认识的人之间连一条边，且将同一组间的连线染成红色，不同组之间的线染成蓝色．将这n 个点任意分成两组，只有有限种分法．考虑在两组之间的蓝线条数S ，其中必存在一种分法，使S 达到最大值，此时有i A 在两组内引出的边的条数分别为),,2,1,(,n i l l l l i i i i ='≥'，否则，若对i A 有'<i i l l ，将i A 调到另一组，S 增加了i i l l -'条，矛盾，得证．10．有三所中学，每所有学生n 名，每名学生都认识其他两所中学的n+1名学生，证明：从每所中学可以选出一名学生，使选出来的3名学生互相认识．证：用3n 个顶点表示这些学生，三所中学的学生组成的三个顶点集合分别记为A 、B 、C ，设M 和N 是两所不同学校的学生，而且是互相认识的，则在M 与N 之间连一线，得一个简单图．记A 中的元素x 在B 、C 中的相邻元素个数为k 和l ，则k+l =n+1．设k 与l 中大的记作m(x)，让x 跑遍A ，m(x)的最大值记作A m ，同理记C B m m ,分别为集合B 、C 中的所有元素在另两个集合中相邻元素个数的最大值．记m 是A m ，C B m m ,中最大者，不妨设m=A m ，且的顶点相邻的顶点集和中和使得100,B x B A x ∈数为m ，于是C 中与000,11x C z m n x 与设相邻的顶点数为∈≥-+相邻．如果有中中的一个三角形．若是相邻，则与1000010B G z y x z B y ∆∈每一个y 与中相邻与．因此，相邻的顶点数与都不相邻，则A z m n z B z 000-≤的顶点数1)(1+=--+≥m m n n 与m 的最大性矛盾，得证．三．巩固练习1．有n 个药箱，每个药箱里有一种相同的药，每种药恰好在两个药箱里出现，问有多少种药？)1(21-n n 2．18个队进行比赛，每一轮中每一个队与另一个队比赛一场，并且在其他轮比赛中这两个已赛过的队彼此不再比赛，现在比赛已进行完8轮，证明一定有三个队在前8轮比赛中，彼此之间尚未比赛过．3．某次会议有n 名代表出席，已知任意的四名代表中都有一个人与其余的三个人握过手，证明任意的四名代表中必有一个人与其余的n-1名代表都握过手．4．空间１８个点，任三点不共线，它们的两两连线染上红色或兰色，每条线段仅染一色．试证明其中一定存在一个同色的完全四边形．图论问题（二）用图论解决问题躲基本思路：把要考察的对象作为顶点，把对象之间是否具有我们所关注的某种关系作为顶点连边地条件．这样，就可以把一个具体问题化归成图论问题，用图论的理论和方法进行探讨，即使在图论中没有现成定理直接给出问题的解答，也可以（1）借助图论的分析方法拓宽解题思路；（2）把抽象的问题化为直观问题；（3）把复杂的逻辑关系问题化为简明的数量分析问题。