文档介绍：Bollobas和Scott证明了如果一个赋权有向图每个顶点的出赋权度至少为1,那么它包含一条有向路权值至少为1。
我们描述了在上述条件下不含权重超过1的有向路的极图的形式。
演讲结构
符号和术语
问题背景
结论和证明思路
问题的延伸
符号和术语
一个图G被称为赋权图,如果G的每条边e对应一个非负实数w(e),这一非负实数称为e的权。
对于G的一个子图H,定义H的权为
符号和术语
对于G的子图H和顶点v,定义v在H中的赋权度为
简记为。
符号和术语
一个非赋权图可以看作是一个每条边的赋权都为1的赋权图。因此,对于每一顶点v,w(v)=d(v),此外,它的子图的权等于其边数。
符号和术语
一条(x,y)-路是连接顶点x和y的一条路。
一条z-路是以z作为其一个端点的一条路。
符号和术语
一个有向图D被称为赋权有向图,如果D的每条弧a对应一个非负实数w(a),这一非负实数称为a的权。
对于D的一个子图H,定义H的权为
符号和术语
对于D的子图H和顶点v,定义v在H中的出赋权度和入赋权度分别为
和简记为和。
符号和术语
一条有向(x,y)-路是由x到y的一条有向路。
问题背景
Dirac证明了若一个图G的最小度为d,则G包含一条路长度至少为d。
Bondy和Fan将这个结论推广到赋权图中,并且给出了不含重路的相应的极图的形式: