传递图表有多大?

对于每个$n$,$n$顶点上最大的传递性降低非循环链接图表是什么?

$e$的边数是多少? $e$如何作为$n$的函数展开? 比$n^2/4$更快?

0
2019-05-13 03:29:34
资源 分享
答案: 2

二分图是最大的。

证据: 假设G是图表,v是顶点。 允许$L(v)$达到路由课程的最高大小,该课程以$v$开头。 允许$L(G)=max_{v\in G} L(v)$。 如果是$L(G)=1$,则图表为二分图。 为了确认,该二分图是最大的,我肯定会确认,对于任何类型的图表$G$,使得$L(G)>1$存在具有相同种类的顶点和边的图表$H$,例如$L(G)>L(H)$。

请记住,任何具有$L(v)=0$的顶点都只有传入链接。 此链接来自顶点w与$L(w)=1$。 我们肯定会在2个动作中做图表$H$。
操作1.使用$L(v)=0$删除所有顶点,并将它们放在一边。 请记住,$L(G)$实际上已被降低。 动作2.添加所有顶点,摆脱动作1.添加边,摆脱动作1,但反转他们的指令。 调用新图表$H$。 请记住,它具有相同种类的顶点和侧面以及$L(H) < L(G)$。

0
2019-05-17 15:07:32
资源

由于可传递降低的图表$G$是非循环的,因此存在等效的无向直接图表$G'$,可以通过忽略侧面的指令来创建。 $G$中的各种边与$G'$中的边的种类一致。

为了使$G$传递降低,一个基本问题是$G'$必须没有任何类型的三角形。

很受欢迎(图兰的/曼特尔定理),$n$顶点上的任何类型的直接无向图表以及大于$n^2/4$的边都有三角形。

另外认识到,具有最大边且没有三角形的$n$顶点上的无向图是完整的二分图$K_{[n/2],[n/2]}$(作为示例检查:http://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA28,锻炼4)

从您的评论中,它类似于您找到的$G$,其等效$G'$是$K_{[n/2],[n/2]}$因此确认了它。

0
2019-05-17 13:33:39
资源