以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  离散,两条平行边构成的通路、环是回路吗  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=66595)


--  作者:cpkug
--  发布时间:8/30/2008 4:16:00 PM

--  离散,两条平行边构成的通路、环是回路吗
离散大本, P119   7.2  通路与回路

定义 7.18 设G为无向标定图,G中顶点与边的交替序列Γ = vi0 - ej1 - vi1 - ej2 -... - ejl - vil称为顶点vi0到顶点vil的通路,其中vir-1,vir为ejr的端点,r=1,2,...,l,vi0,vil分别称为Γ的始点和终点,Γ中边数l称为Γ的长度。若vi0=vil,则称通路Γ为回路。

由上面定义,可以认为两条平行边构成的通路、环是回路,且是简单回路,也是初级回路。

大家怎么看?


[此贴子已经被作者于2008-8-30 22:27:40编辑过]

--  作者:fgffggfg
--  发布时间:8/30/2008 5:07:00 PM

--  
简单回路——边各异,初级回路——点各异(除始点终点)边各异,
这样看,两条平行边能构成简单回路、初级回路,2k(k>1)条平行边能构成简单回路,不能构成初级回路。
大家看这样有问题没?


[此贴子已经被作者于2008-8-31 12:54:57编辑过]

--  作者:karry_2008
--  发布时间:8/30/2008 9:40:00 PM

--  
为什么平行边不是呢?我觉得LZ说的对呢?
QQ:535677899

--  作者:cpkug
--  发布时间:8/30/2008 10:32:00 PM

--  
一条平行边所对应的边肯定不构成回路,因为如果成立的话,那任何边都能构成回路了;

多条平行边肯定能构成回路;

两条平行边可以构成回路、简单回路、初级回路。

以上是本人观点!


--  作者:jason_00
--  发布时间:8/30/2008 10:34:00 PM

--  
汗,平行边怎么可能是简单回路,更不可能是初级回路---
--  作者:cpkug
--  发布时间:8/30/2008 11:02:00 PM

--  
以下是引用jason_00在2008-8-30 22:34:00的发言:
汗,平行边怎么可能是简单回路,更不可能是初级回路---

平行边,从字面上理解,只是一条边,因而不构成回路;

但认为多条平行边能构成回路;

如果超过两条平行边,则构成可以构成简单回路(边各异),但不能构成初级回路(点不各异,);

如果是两条平行边,则可以构成简单回路、初级回路,因为顶点各异,边也各异;

不知这样推理对不?


[此贴子已经被作者于2008-8-31 19:42:12编辑过]

--  作者:jason_00
--  发布时间:8/30/2008 11:13:00 PM

--  
看来你还要对一些概念多加理解---
--  作者:Logician
--  发布时间:9/3/2008 2:59:00 PM

--  
我想,对于无向图,你的结论是对的
如果是有向图,平行边就不构成回路了

在无向图中,一条边也能构成(复杂)回路。即,若e=(u,v),则u e v e u也是回路。

不过话说回来,貌似大家一般关心的是简单图中的简单或初级回路的
所以上述细节的讨论貌似没有太多意义

呵呵~~

以下是引用cpkug在2008-8-30 22:32:00的发言:
一条平行边所对应的边肯定不构成回路,因为如果成立的话,那任何边都能构成回路了;

多条平行边肯定能构成回路;

两条平行边可以构成回路、简单回路、初级回路。

以上是本人观点!




--  作者:cpkug
--  发布时间:9/3/2008 10:17:00 PM

--  
以下是引用fgffggfg在2008-8-30 17:07:00的发言:
简单回路——边各异,初级回路——点各异(除始点终点)边各异,
这样看,两条平行边能构成简单回路、初级回路,2k(k>1)条平行边能构成简单回路,不能构成初级回路。
大家看这样有问题没?


以下是引用Logician在2008-9-3 14:59:00的发言:
我想,对于无向图,你的结论是对的
如果是有向图,平行边就不构成回路了



下面总结如下(以下结论,不考虑复杂回路,并且所指的边是一定要全部遍历到的):
1. 环是回路,且是简单回路,也是初级回路;

2. 在无向图中,两条平行边可以构成简单回路、初级回路;2k(k>1)条平行边能构成简单回路,不能构成初级回路;2k + 1(k>1)条平行边不能构成简单回路、初级回路;

3. 在有向图中,任何条数的平行边不能构成回路;



--  作者:xujianyong
--  发布时间:9/5/2008 10:19:00 PM

--  
logican 果然牛逼,讲的如此清晰
--  作者:jason_00
--  发布时间:9/5/2008 10:54:00 PM

--  
唉---,讨论平行边和环是否是简单回路或圈没什么意义---
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
62.500ms