简单有向图中诱导圈的最大个数

Question

给定一个简单的有向图G=(V，E)，诱导圈是一个圈，其中没有一个环的两个顶点有一个不存在于圈中的边。

(无弦圈是至少有4个顶点的诱导圈)。

我的问题是，一个简单有向图的最大诱导圈数是多少？

我已经浏览过很多网页了。然而，我无法找到这个具体问题的答案。

Answer 1

如果图是有向的，这就意味着没有一个圈可以两次包含相同的边。

如果这个图很简单(假设你真的是指一个简单图)，那就意味着没有“循环”边开始和结束在同一个顶点，并且任何一对不同的顶点最多在它们之间有一个边。

从这些假设，我们可以很容易地表明，任何电路(诱导或其他)必须包含至少三个顶点和至少三个边。一个有一个顶点的电路必须使用一个循环边；一个有两个顶点的电路必须重用一个单一的边，或者在相同的两个顶点之间有两个边；等等。

现在，给定任何两个不同的电路(诱导或其他)，这两个电路不能共享所有三个顶点。如果是这样的话，它们要么是相同的电路，要么在同一对顶点之间又会有两个不同的边缘。根据本质上相同的逻辑，任何两个不同的电路都不能共享多个边。

结果表明，对于任意图G(V，E)，图G(V，E)不能有多于V-2电路，也不能多于(E1)/2电路。

现在，我可以通过一个简单的例子证明这个上界不仅是一个界，而且是一个最大值。设G包含顶点A和B，边X从A到B，目前有0圈，2个顶点和1个边。现在添加一个顶点C1，加上从B到C1的边Y1和从C1到A的另一个边Z1，现在我们有一个圈(很明显是诱导的)，3个顶点和3个边。同样地，添加顶点C2和边Y2和Z2，使我们有2个诱导圈，4个顶点和5个边。继续这个模式，通过归纳法，当我们添加CN，YN和ZN时，我们将有N个诱导圈，2+N顶点和1+2N边。这意味着N=V-2和N=(E-1)/2，这是我们的理论上界.

因此，图G(V，E)中诱导电路/圈的最大数目是V-2和(E-1)/2的最小值。