关于极大弦图存在性及非完全实例的技术问询
关于极大弦图存在性及非完全实例的技术问询
嘿,最近在琢磨弦图的相关概念,碰到个困惑想请教大家:
先明确下基础定义:
弦图是指所有包含4个及以上顶点的环都含有弦的图——这里的弦是指不属于环本身,但连接环中两个顶点的边。
我不确定学术上有没有极大弦图这个正式概念,所以自己先暂定了一个定义:
一个弦图是极大的,当且仅当在任意一对不相邻的顶点之间添加一条边后,得到的图要么不再是弦图,要么不再是简单图。
按照这个定义,完全图肯定是满足条件的,但我好奇:除了完全图之外,还有没有其他的极大弦图?
另外提个相关术语:有时候我们把不是三角形的导出环叫做「洞(hole)」。换个方式问我的问题就是:是否存在非完全的弦图,使得在它上面添加任意一条边都会产生一个洞?
如果这种非完全的极大弦图不存在的话,是不是意味着从任意一个弦图出发,我们可以不断添加边(同时维持弦图的性质),直到把它补成完全图?
我自己用计算机逐个排查了顶点数≤10的弦图,没找到符合要求的例子,但不确定顶点数更多的情况下会不会有例外。
备注:内容来源于stack exchange,提问作者licheng
相关产品推荐
相关产品推荐

