注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

P对NP的世界

Polynomial时间和指数时间的比赛

 
 
 

日志

 
 

ear decomposition  

2009-12-20 23:18:25|  分类: 图论中NP问题 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
来自其他文章资料

Definition. An ear of a graph G is a path with end vertices in common with G.
  这实际上类似 一个Cycle,但是有两点属于另外一个图G
     An ear decomposition of G is a partition of the edge set of G  into a cycle C and paths P1 , . . . , Pk such that Pi has only its endvertices on C ∪ P1 ∪ . . . ∪ Pi?1 for each i = 1, . . . , k.

ear分解类似我在EMPG中的argument Cycle(3-edge-connectivity )情况。

 Lemma 1. ( [3]) A graph is 2-vertex connected if and only if it has an ear decomposition.
等价描述
. If a graph G is 2-connected, then G can be obtained from a cycle by successively adding ears.

Proof. We provide an algorithm which contstructs G by successively adding ears to a cycle in G.
If G is not a cycle, then let G be the current graph. We construct ears to add to G by choosing
an edge e = uv with v ∈ V (G ) but u ∈\ V (G ). Let Q be the shortest path in G ? v from u to some
                                     
vertex in G . Then Q together with e is an ear, which we add to G . Continue this process until
we obtain G.

Definition 2. We denote an edge contraction by G/e. We denote strong edge contraction by
G//e, where e is first contracted then multiple edges are replaced by a single edge.

Lemma 2. For every 3-connected graph G of order at least 5, there exists an edge e such that
G//e is still 3-connected.

Theorem 2.  If G is a 3-connected graph distinct from a wheel, then G contains an edge e such
that either G ? e or G/e is 3-connected.

Argument cycle 可以描述为 a cycle without  any chords, or [C] induces a simple cycle

[3] Douglas B. West, Introduction to graph theory, Prentice-Hall, New Jersey, 1996.
  评论这张
 
阅读(400)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017