图论杂项问题

数学竞赛中的图论问题2-6数学竞赛中的图论问题（P ．221）⼀、基本思想引例欧拉7桥问题把所考察的对象作为顶点（v ），把对象之间是否具有我们所关⼼的某种关系作为了连线的的条件（e ），这样，就可以把⼀个具体问题抽象为图的研究．在解数学竞赛题中的好处：（1）把抽象的问题转化为直观的问题；（2）把复杂的逻辑关系转化为简明的数量关系．⼆、基本内容有图、顶点、边、简单图、完全图、连通图、树、⼆分图、竞赛图等14个定义，12条定理：定义１设集合{}12(),,,p V G v v v =≠?，{}12(),,,q E G e e e =是()V G 中某些元素对的⽆序集合，则称()()(),G V G E G 为图，⼜称()V G 为图G 的顶点集合，其元素叫做顶点；称()E G 图G 的边集合，其元素叫做边．若(),u v V G∈，边e 是⽆序顶点对(),u v ，则记e uv vu ==，且称u 与v 是边e 的端点，e 与顶点,u v 关联，也说顶点u 与v 邻接（或相邻）．有公共端点的边12,e e 称为邻边，也说12,e e 邻接．例如顶点：()V G =｛⼩王，⼩李，⼩张，⼩赵，⼩陈，⼩刘｝，边：1e =｛⼩王，⼩李｝，2e =｛⼩李，⼩赵｝，3e =｛⼩陈，⼩刘｝， 12,e e 相邻.定义2 图G 中所含顶点的数⽬称为图的阶数，记为V （也⽤G 来表⽰）；⼜⽤E 表⽰图G 的边数（也⽤G 来表⽰）．通常⽤(),G p q 表⽰p 个顶点，q 条边的图G ；若,p q 都是有限数的图称为有限图，否则称为⽆限图．如果对于图(),G V E 与()''',G V E ，有'',V V E E ??，则称'G 是G 的⼦图．定义 3 两顶点间⾄多连⼀条边且每边的两个端点相异的图称为简单图；图中任何两个顶点都邻接的简单图称为完全图，p 阶完全图记为.p K定理1 p K 的边数为()12p p E -=．定义４图G 中与顶点u 关联的边数称为顶点u 的度，记为()d u ．如果u 的度数是奇数，则称u 为奇顶点；如果u 的度数是偶数，则称u 为偶顶点．定理２任何⼀个图的总度数等于边数的2倍，()2u Vd u E ∈=∑．推论任何图中奇顶点的个数是偶数．定义５图G 中点边交错的⾮空有限序列011231k k k u e u e u u e u -叫做以0,k u u 为端点的途径．若途径中所有的i e 都不相同，则叫做0k u u -链；若链中所有的i u 都不相同则叫做0k u u -通路，k 称为通路的长；若0,k u u 重合，则叫做回路或圈．k 为奇（偶）数的回路称为奇（偶）回路．定义６经过图G 中每条边的链称为欧拉链，两端重合的欧拉链称为欧拉环游图（欧拉回路），有欧拉环游的图称为欧拉图（简称E 图）直观的说，欧拉图就是从⼀个顶点出发⽽每边通过⼀次⼜能回到出发顶点的图（⼀笔画）．定理3 连通图G 为欧拉图的充要条件是G 中没有奇顶点．推论如果连通图G 有2k 个奇顶点，那么图G 可以⽤k 笔画成．定义７包含图G 每⼀个顶点的通路称为哈密尔顿通路，有哈密尔顿通路的图称为哈密尔顿图．定理4 设G 是⼀个p 阶简单图()3p ≥，若G 中任意两个顶点,u v 的度数满⾜()()d u d vp +≥，则G 是哈密尔顿图．定义８连通⽽⽆回路的图称为树，树上度数为1的顶点称为叶（悬挂点）．定理5 如果树T 的顶点数不⼩于2，那么树T 上⾄少有两个叶．定理6 设图G有p个顶点，q条边，则下列说法彼此等价：（1）G是树；（2）G的任意两个顶点间有且仅有⼀条通路；（3）G连通，且1=-；q p（4）G⽆回路，且1=-；q p（5）G⽆回路，但连接任何两个⾮邻接顶点,u v所得新图，有且仅有⼀个回路；（6）G连通，但舍弃任何⼀条边后便不连通．定义9 图()G V E的顶点集V若能分成两个⾮空⼦集12,V V，,使得任何边e的⼀个端点属于V，另⼀个端点属于2V，则G为1⼆分图．定理7 图G为⼆分图的充要条件是G不含奇回路．定义10 设图()G V E为简单图，M是E的⼀个⾮空⼦集，,若M中任何两边都不相邻，则称M为图G的⼀个匹配（⼜称对集）．若M边之端点包括G中⼀切顶点，则称M为G的⼀个完备匹配．M中每⼀边的两个端点称为相配．定义11 在图的边上⽤箭头标注出⽅向就得到⼀个有向图，称为定向．完全图的⼀个定向称为竞赛图．定理8 每个竞赛图都有单向哈密尔顿通路．定义12 若⼀个图G可以画在平⾯上，使得任何两条边都不在⾮顶点处相交，则称图G为平⾯图．图的边所包围的⼀个区域，其内部既不包含图的顶点，也不包含图的边，这样的区域为图G 的⼀个⾯．为了⽅便，把平⾯图G 的外部⽆限区域也作为⼀个⾯，称为外部⾯，其他⾯则称为图G 的内部⾯．定理9 设G 是⼀个简单连通平⾯图，()(),V G p E G q==，⾯数为f （包括外部⾯），则2p q f -+=．定理10 ⼀个连通的平⾯简单图G ，若有v 个顶点()3,v e ≥条边，则36e v ≤-．定义13 ⽤红蓝两种颜⾊对完全图p K 的边任意染⾊，使每条边都染上某⼀种颜⾊，若总会出现红⾊边m K 或蓝⾊边n K 时，则记p 的最⼩值为(),r m n ，称(),r m n 为关于,m n 的拉姆赛数．定理11 ()()()()()3,36,3,49,3,514,3,618,3,723,r r r r r ===== ()3,936,r =()4,418.r =定义14 ⽤n 种颜⾊对完全图p K 的边任意染⾊，使每条边都染上某⼀种颜⾊，若总会出现同⾊三⾓时，则记p 的最⼩值为()3,3,,3n r 个，简记为n r ，称n r 为拉塞姆数．定理12 设12,,,n S S S 是集合{}1,2,,n r 的任意分划，则存在⼀个,1n i i r ≤≤，使i S 中有⽅程x y z +=的根．三、主要⽅法不是图论知识的直接套⽤，⽽是图论基本思想的常识应⽤．构造法、反证法数学归纳法抽屉原理染⾊⽅法极端原理四、例题选讲例1-1 有5个课外活动⼩组，每2个⼩组⾥有⼀个相同的同学，每个同学恰好在两个⼩组⾥出现，问这5个⼩组⾥共有多少个同学？解把⼩组对应为点，“每2个⼩组⾥有⼀个相同的同学”就连⼀条线，每两点都有连线；⼜由于“每个同学恰好在两个⼩组⾥出现”，故每两点都连且只连⼀条线，得5阶完全图，图中变的条数就是同学个数，得10个同学.例1-2 有n 个药箱，每两个药箱⾥有⼀种相同的药，每种药恰好在两个药箱⾥出现，问共有多少种药？解把药箱对应为点，“两个药箱⾥有1种相同的药”就连⼀条线，每两点都有连线；⼜由于“每种药恰好在两个药箱⾥出现”，故每两点都连且只连⼀条线，得（n 阶完全图）2n N C ．例2 证明：在任何⼀群⼈中，与奇数个⼈互相握⼿（互相认识）的⼈有偶数个．证明记这群⼈为n 个点，“互相握⼿”就在对应的两点连⼀条线，共有e 条，每个⼈认识的⼈数为点的“度数”，记为12,,,n d d d ，则 122n d d d e +++=，2i i d d e +=∑∑奇偶，2i i de d =-∑∑奇偶为偶数 id ∑奇是偶数个奇数之和．例3-1 (1947，匈⽛，例2-4-1）证明：在任意6个⼈中，总可以找到3个⼈互相认识，或互相不认识，并且这种情况⾄少出现2个．例3-2 （1976，波兰）平⾯上有6个点，任何3点都是⼀个不等边三⾓形的顶点，则这些三⾓形有⼀个的最短边⼜是另⼀个三⾓形的最长边．提要：把每个三⾓形的最短边染成红⾊，存在红⾊三⾓形，红⾊三⾓形的最长边为所求．例4 在边⼆染⾊的K 5中没有单⾊三⾓形的充要条件是它可分解为⼀红⼀蓝两个圈，每个圈恰由5条边组成．证明充分性是显然的．考虑必要性，在K 5中每点恰引出4条线段，如果从其中某点A 1能引出三条同⾊线段A 1A 1，A 1A 3，A 1A 4，记为同红，则考虑△A 2A 3A 4，若当中有红边i j A A （24i j ≤≤≤），则存在红⾊三⾓形1i j A A A 是同蓝⾊三⾓形，均⽆与单⾊三⾓形⽭盾．所以，从每点引出的四条线段中恰有两条红⾊两条蓝⾊，整个图中恰有5条红边、5条蓝边．现只看红边，它们组成⼀个每点度数都是2的偶图，可以构成⼀个或⼏个圈，但是每个圈⾄少有3条边，故5条红边只能构成⼀个圈，同理5条蓝边也构成⼀个圈．例 5 求最⼩正整数n ，使在任何n 个⽆理数中，总有3个数，其中每两数之和都仍为⽆理数．解取4个⽆理数，显然不满⾜要求，故5n ≥．设,,,,a b c d e 是5个⽆理数，视它们为5个点，若两数之和为有理数，则在相应两点间连⼀条红边，否则连⼀条蓝边．这就得到⼀个⼆染⾊5k ．只须证图中有蓝⾊三⾓形，分两步：（1）⽆红⾊三⾓形．若不然，顶点所对应的3个数中，两两之和均为有理数，不妨设,,a b b c c a +++都是有理数，有1[()()()]2a ab bc c a =+-+++ 但⽆理数≠有理数，故5k 中⽆红⾊三⾓形．（2）有同⾊三⾓形，若不然，由上例知，5k 中有⼀个红圈，顶点所对应的5个数中，两两之和均为有理数，设,,,,a b b c c d d e e a +++++为有理数，则1[()()()()()]2a ab bc cd de e a =+-+++-+++ 但⽆理数≠有理数，故5k 中⽆5条边组成的红圈，从⽽有同⾊三⾓形．这时，同⾊三⾓形必为蓝⾊三⾓形，其顶点所对应的3个⽆理数，两两之和仍为⽆理数．综上所述，最⼩的正整数5n =.例6-1 某⾜球邀请赛有,,,A B C D 4个城市参加，每市派出红黄两⽀球队，根据⽐赛规则，每两之间球队⾄多赛⼀场，并且同⼀城市的两⽀球队之间不进⾏⽐赛.⽐赛若⼲天后进⾏统计，发现除A 市红队外，其他各队⽐赛过的场次各不相同.问A 市黄队赛过多少场.（找黄队，求c 场次）解因为“同⼀城市的两⽀球队之间不进⾏⽐赛”，所以每⼀个球队最多赛6场；有因为“除A 市红队外，其他各队⽐赛过的场次各不相同”，所以，其他各队赛过的场次分别为0，1，2，3，4，5，6共7种情况.⽤12345678,,,,,,,A A A A A A A A 表⽰8⽀球队，两队之间进⾏了⽐赛就连1条边，其中1234567,,,,,,A A A A A A A 分别赛了6，5，4，3，2，2，1，0场.由于1A 赛了6场，应有6条引线，记为121314151617,,,,,A A A A A A A A A A A A ，由于1A 与8A 没有引线，故1A ，8A 属于同⼀城市.同理， 27,A A 属于同⼀城市， 36,A A 属于同⼀城市，45,A A 属于同⼀城市.45,A A 属于同⼀城市且都赛过3场，由于“除A 市红队外，其他各队⽐赛过的场次各不相同”，所以45,A A 就是A 市的两⽀球队，得A 市黄队赛过3场.例6-2 李明夫妇最近参加了⼀次集会，同时出席的还有三对夫妻．⼀见⾯，⼤家互相握⼿，当然夫妻之间不握⼿，也没有⼈与同⼀个⼈握两次从⼿．握⼿完毕后，李明统计了包括妻⼦在内的7个⼈握⼿的次数，发现恰好数字发互不相同．请问．李明的妻⼦握了⼏次⼿?例6-3 （P.225例2-115）作业：1 习题2-6第12．习题2-6第11题（P．235）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

图论在计算机科学、电子工程、物理学等领域有着广泛的应用。

下面是一些图论习题的解答，希望对读者有所帮助。

1. 问题：给定一个无向图G，求图中的最大连通子图的节点数。

解答：最大连通子图的节点数等于图中的连通分量个数。

连通分量是指在图中，任意两个节点之间存在路径相连。

我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，统计连通分量的个数。

2. 问题：给定一个有向图G，判断是否存在从节点A到节点B的路径。

解答：我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，查找从节点A到节点B的路径。

如果能够找到一条路径，则存在从节点A到节点B的路径；否则，不存在。

3. 问题：给定一个有向图G，判断是否存在环。

解答：我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，同时记录遍历过程中的访问状态。

如果在搜索过程中遇到已经访问过的节点，则存在环；否则，不存在。

4. 问题：给定一个加权无向图G，求图中的最小生成树。

解答：最小生成树是指在无向图中，选择一部分边，使得这些边连接了图中的所有节点，并且总权重最小。

我们可以使用Prim算法或Kruskal算法来求解最小生成树。

5. 问题：给定一个有向图G，求图中的拓扑排序。

解答：拓扑排序是指将有向图中的节点线性排序，使得对于任意一条有向边(u, v)，节点u在排序中出现在节点v之前。

我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，同时记录节点的访问顺序，得到拓扑排序。

6. 问题：给定一个加权有向图G和两个节点A、B，求从节点A到节点B的最短路径。

解答：我们可以使用Dijkstra算法或Bellman-Ford算法来求解从节点A到节点B的最短路径。

这些算法会根据边的权重来计算最短路径。

数据结构——图选择题整理1.设完全图Kn,有n个结点(n≥2),m条边，当()时，K,中存在欧拉回路。

A.m为奇数B.n为偶数C.n为奇数D.m为偶数解析:答案C完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。

n 个端点的完全图有n个端点以及n(n-1)/2条边，因此完全图Kn的每个结点的度都为n-1，所以若存在欧拉回路则n-1必为偶数。

n必为奇数。

选C。

2、若从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）A、强连通图B、连通图C、有回路D、一棵树解析：选B对于A，强连通图的概念是在有向图中的。

对于B，连通图证明任意两个顶点之间一定能够相连，因此一定可以到达。

对于C，有环图不一定是连通图不一定任意两个顶点均能到达。

对于D，树是可以，但是不是树也可以，题目中说的太肯定了，不能选，比如下图就不是树，但可以完成题目中要求的功能。

2、对于一个有n个顶点的图：若是连通无向图，其边的个数至少为（）；若是强连通有向图，其边的个数至少为（）A、n-1,nB、n-1,n(n-1)C、n,nD、n,n(n-1)解析：选A对于连通无向图，至少需要n-1条边。

对于强连通有向图，只要能形成一个大环就可以从任意一点到另一点。

3、设有无向图G=(V,E)和G'=(V',E')，若G’是G的生成树，则下列不正确的是（）a.G'为G的连通分量b.G'为G的无环子图c.G'为G的极小连通子图且V'=VA、a和bB、只有cC、b和cD、只有a解析：选D极大连通子图简称连通分量，生成树是极小连通子图。

故a不对，c对。

生成树无环，故b对4.带权有向图G用邻接矩阵存储，则vi的入度等于邻接矩阵中（）A、第i行非∞的元素个数B、第i列非∞的元素个数C、第i行非∞且非0的元素个数D、第i列非∞且非0的元素个数解析：选D带权有向图的邻接矩阵中，非0和∞的数字表示两点间边的权值。

第一章习题1. 对任何简单图G ，(1) 证明：(1)()2G υυε−≤；(2)(1)()2G υυε−=当且仅当G K ν≅。

2. 证明：(1),()m n K mn ε=；(2) 若G 是完全二部图，则2()4G υε≤。

3. 图G 有21条边，12个3度顶点，其余顶点的度均为2，求图G 的阶数。

4. 证明：任何简单图必有至少两个顶点具有相等的度。

5. 设G 是简单图，求G 的所有不同的生成子图的个数（包括G 本身和空图）。

6. 证明：任何图中，奇度顶点的个数总是偶数（包括0）。

并由此证明：在任一次聚会上握过奇数次手的人必为偶数个。

7. 证明或反证：如果u 和v 是图G 中仅有的具有奇数度的顶点，则G 包含一条u , v 路。

8. 证明：若4υ≥且1+=νε，则存在)(G V v ∈使得3)(≥v d 。

由此证明： n 个球队比赛（4n ≥），已赛完n +1场，则必定有一个球队已参加过至少3场比赛。

9. 在一个运动联盟中，将所有运动队组织成两个赛区，每个赛区有13个队，能否恰当安排比赛使得每个队在其所在赛区中进行9场比赛而与另一个赛区中的运动队进行4场比赛？10. 在平面上有n 个点12{,,,}n S x x x =⋅⋅⋅，其中任两个点之间的距离至少是1。

证明在这n 个点中，距离为1 的点对数不超过3n 。

11. 某次会议有n 人参加，其中有些人互相认识，但每两个互相认识的人，都没有共同的熟人，每两个互不认识的人都恰好有两个共同的熟人。

证明每一个参加者都有同样数目的熟人。

12. 在一个化学实验室里，有n 个药箱，其中每两个不同的药箱恰有一种相同的化学品，而且每种化学品恰好在两个药箱中出现，问：（1）每个药箱有几种化学品？（2）这n 个药箱中共有几种不同的化学品？13. 在一次舞会中，A 、B 两国留学生各(2)n n >人，A 国每个学生都与B 国一些(不是所有)学生跳过舞，B 国每个学生至少与A 国一个学生跳过舞。

《图论及其应用》大作业指导老师郝荣霞知行1503 徐鹏宇 152912002.1.9证明：若G是森林且恰有2k个奇点，则在G中有k条边不重的路P1,P2......P K,使得E(G)=E(P1) E(P2) ...... E(P K)。

证明：对奇点数k使用数学归纳法。

①当k=1时，G是森林，且有且只有2个奇点⇒G只能为一颗树，且G的所有奇度顶点为两个1度顶点⇒G是一条路⇒满足题设②假设当k=t时，结论成立。

接下来考虑k=t + 1时的情况。

在G中一个分支中取两个叶子点u与v，令P是连接该两个顶点的唯一路。

由于P上除u，v以外的点均被P经过两次，即G-P后除u，v以外的点奇偶性不变。

⇒则G–P是有2t个奇度顶点的森林⇒由归纳假设知，G–P可以分解为t条边不重合的路之并，即E(G-P)=E(P1) E(P2) ...... E(P t)。

⇒则G可分解为t+1条边不重合的路之并，即E(G)=E(P1) E(P2) ...... E(P t) E(P)。

⇒即证。

2.4.4证明：若e 是K n 的边，则τ（K n -e ）=（n-2）n n-3证明：由定理2.9：τ（K n ）=n n-2由于τ（K n -e ）=τ（K n ）-τ（含有e 的生成树棵树）现在需要求含有e 的生成树棵树，τ（含有e 的生成树棵树）=)1(21n 1-n 2-n n n ）（=2n n-3τ（K n -e ）=τ（K n ）-τ（含有e 的生成树棵树）=（n-2）n n-33.2.4证明：不是块的连通图至少有两个块，其中每个恰有一个割点。

证明：设G 为不是块的连通图，由于G 连通且不是块⇒G 有割点①当G 只有1个割点v 时，延割点分开，G1，G2内无割点，且连通，由块的定义知⇒G1,G2是块，且分别含一个割点v 。

②当G 含有2个及2个以上割点时，取相距距离最远的两个割点u 和v ，此时分G 为三部分G1,G2,G3。

常见问题：1、图论的历史图论以图为研究对象的数学分支。

图论中的图指的是一些点以及连接这些点的线的总体。

通常用点代表事物，用连接两点的线代表事物间的关系。

图论则是研究事物对象在上述表示法中具有的特征与性质的学科。

在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观。

例如，国家用点表示，有外交关系的国家用线连接代表这两个国家的点，于是世界各国之间的外交关系就被一个图形描述出来了。

另外我们常用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC中各元件电路导线连接关系等等。

事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟。

由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要。

由此经数学抽象产生了图的概念。

研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容。

图论的产生和发展经历了二百多年的历史，大体上可分为三个阶段：第一阶段是从1736年到19世纪中叶。

当时的图论问题是盛行的迷宫问题和游戏问题。

最有代表性的工作是著名数学家L.Euler于1736年解决的哥尼斯堡七桥问题(Konigsberg Seven Bridges Problem)。

东普鲁士的哥尼斯堡城(现今是俄罗斯的加里宁格勒，在波罗的海南岸）位于普雷格尔(Pregel)河的两岸，河中有一个岛，于是城市被河的分支和岛分成了四个部分，各部分通过7座桥彼此相通。

如同德国其他城市的居民一样，该城的居民喜欢在星期日绕城散步。

于是产生了这样一个问题：从四部分陆地任一块出发，按什么样的路线能做到每座桥经过一次且仅一次返回出发点。

这就是有名的哥尼斯堡七桥问题。

哥尼斯堡七桥问题看起来不复杂，因此立刻吸引所有人的注意，但是实际上很难解决。

瑞士数学家(Leonhard Euler)在1736年发表的“哥尼斯堡七桥问题”的文章中解决了这个问题。

二、应用题题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，)(xN G≥[n/2]；（2）对V的任一个子集S，只要S＝[n/2]，S中有两个顶点相邻或V-S中有两个顶点相邻。

需要证明G中有三个顶点两两相邻。

反证，若G中不存在三个两两相邻的顶点。

在G中取两个相邻的顶点x1和y1,记N G(x1)＝{y1,y2,……,y t}和N G(y1)={x1,x2,……,x k},则N G(x1)和N G(y1)不相交，并且N G(x1)（N G(y1)）中没有相邻的顶点对。

情况一；n=2r：此时[n/2]＝r，由（1）和上述假设，t=k=r且N G(y1)＝V-N G(x1)，但N G(x1)中没有相邻的顶点对，由（2），N G(y1)中有相邻的顶点对，矛盾。

情况二；n=2r+1: 此时[n /2]＝r ，由于N G (x 1)和N G (y 1)不相交，t ≥r,k ≥r,所以r+1≥t,r+1≥k 。

若t=r+1,则k=r ，即N G (y 1)=r ，N G (x 1)＝V-N G (y 1)，由（2），N G (x 1)或N G (y 1)中有相邻的顶点对，矛盾。

故k ≠r+1，同理t ≠r+1。

所以t=r,k=r 。

记w ∈V- N G (x 1) ∪N G (y 1),由（2），w 分别与N G (x 1)和N G (y 1)中一个顶点相邻，设wx i0∈E, wy j0∈E 。

若x i0y j0∈E ，则w ，x i0, y j0两两相邻，矛盾。