K国是一个热衷三角形的国度,连人的交往也只喜欢三角原则.他们认为三角关系:即AB相互认识,BC相互认识,CA
相互认识,是简洁高效的.为了巩固三角关系,K国禁止四边关系,五边关系等等的存在.所谓N边关系,是指N个人 A1A2
...An之间仅存在N对认识关系:(A1A2)(A2A3)...(AnA1),而没有其它认识关系.比如四边关系指ABCD四个人 AB,BC,C
D,DA相互认识,而AC,BD不认识.全民比赛时,为了防止做弊,规定任意一对相互认识的人不得在一队,国王相知道,
最少可以分多少支队。
原图:G xx图:G‘
子图:V‘为V的子集 E‘为E的子集
诱导子图:对于V‘ 只要在G中有边 那么在G‘中同样应该有边
最大独立集:最大的一个点的子集使任何两个点不相邻——最大独立集数
最大团:点数最多的团——团数
最小染色:用最少的颜色给点染色使相邻点颜色不同——色数
最小团覆盖:用最少个数的团覆盖所有的点——最小团覆盖数
结论: 团数<=色数 最大独立集数<=最小团覆盖数
弦(Chord):连接环中不相邻的两个点的边
弦图:一个无向图称为弦图,当图中任意长度大于3的环都至少有一个弦
弦图的每一个诱导子图一定是弦图
弦图的判断:
ZJU1015
给定一个无向图,判定它是否为弦图
单纯点:设N(v)为与点v相邻的点的点集 一个点是单纯点当且仅当{v}+N(v)的诱导子图为一个团
引理:任何一个弦图都至少有一个单纯点 不是完全图的弦图至少有两个不相邻的单纯点
原文:https://www.cnblogs.com/Aragaki/p/10053907.html