第 67 讲 图论问题(一)本节主要内容是：把一个具体问题用图形表示出来，利用图形的直观性可能更有利于问题的解决．有关的一些概念：由若干个不同的点及连接其中某些点对的线所组成的图形就称为图．图中的点的集合称为图的点集，记为 V：V＝{v1，v2，…，vn，…}；图中的线的集合称为图的线集(边的集合)，记为 E：E＝{vivj}(vi，vj∈V)．故一个图由其点集 V 和线集 E 所决定，若用 G 表示图，则记为 G＝G(V；E)．含有 n 个点的图称为 n 阶图．在一个图中，如果某点 v 共连了 k 条线，则说此点的“次数”(或“度数”)为 k，记为degv＝k.如果一个 p 阶图的每两个顶点间都连且只连了 1 条线，则称该图为 p 阶完全图，记为Kp．若对每条线确定一个方向(即确定了线的两个端点中一个为“起点”，另一个为“终点”．这时，线是点的“有序对”)，则得到“有向图”；对有向图的一个顶点 v，degv＝k，若 v 是其中 n 条边的起点，m 条边的终点(m＋n＝k)，则称 v 的出次为 n，入次为 m．链：若在一个图 G＝(V；E)中取 n+1 个顶点 v1、v2、…、vn+1，每两个相邻的顶点 vi、vi+1间连有一条边 li,则边 l1,l2,…,ln就称为从 v1到 vn+1的一条链．n 称为链的长度．A 类例题 例 1 ⑴ 证明任意的六人中一定有三个人互相认识或互不认识(约定甲认识乙就意味着乙认识甲)．⑵ K6的边染成红蓝两色，求证：其中必有两个三角形，其三边同色．分析 ⑴ 以点表示人，连红、蓝两色的线分别表示“认识”与“不认识”，问题转化成图的问题．要会把题目的语言转译成图的语言：“三人互相认识”就表示三点间都连红线，“三人互不认识”就表示三点间都连蓝线．⑵ 考虑每个异色三角形的三个角，其中两个角是异色角，而同色三角形的三个角都是同色角．证明 ⑴ 用 6 个点 v1，v2，…，v6表示这 6 个人，如果某两人相互认识，则在表示此二人的点间连一条红线，否则连一条蓝线．于是问题转化为证明此 6 点间一定连出了三边均为红色或蓝色的三角形．在点 v1连出的 5 条线中，由抽屉原理知，必有某色线连有 3 条或 3 条以上．不妨设红线连了至少 3 条．设 v1与 v2、v3、v4连的红线．现考虑点 v2、v3、v4连线的情况，如果此三点间有任两点连的红线，则出现红色三角形(例如 v2v3连红线，则 v1v2v3是红色三角形)，如果这三点间都不连红线，则出现蓝色三角形(v2v3v4是蓝色三角形)．故证．⑵ 考虑 K6共连了 C＝15...
