You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

关于极大弦图存在性及非完全实例的技术问询

关于极大弦图存在性及非完全实例的技术问询

嘿,最近在琢磨弦图的相关概念,碰到个困惑想请教大家:

先明确下基础定义:

弦图是指所有包含4个及以上顶点的环都含有弦的图——这里的弦是指不属于环本身,但连接环中两个顶点的边。

我不确定学术上有没有极大弦图这个正式概念,所以自己先暂定了一个定义:

一个弦图是极大的,当且仅当在任意一对不相邻的顶点之间添加一条边后,得到的图要么不再是弦图,要么不再是简单图。

按照这个定义,完全图肯定是满足条件的,但我好奇:除了完全图之外,还有没有其他的极大弦图?

另外提个相关术语:有时候我们把不是三角形的导出环叫做「洞(hole)」。换个方式问我的问题就是:是否存在非完全的弦图,使得在它上面添加任意一条边都会产生一个洞?

如果这种非完全的极大弦图不存在的话,是不是意味着从任意一个弦图出发,我们可以不断添加边(同时维持弦图的性质),直到把它补成完全图?

我自己用计算机逐个排查了顶点数≤10的弦图,没找到符合要求的例子,但不确定顶点数更多的情况下会不会有例外。

备注:内容来源于stack exchange,提问作者licheng

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.04.22 09:03:06