计算机科学论坛--图论的小问题问问

贴子主题：图论的小问题问问

本主题类别:

昨晚跳了大步,今晚就试图来详细的解一下:
对于题只要证明对于圈C的任意点是2度的(就圈C而言),结论就自然成立了,v的小邻寓构成的圈C与v就是个轮图了

设v为轮图的中心.
(1)先证N(v)中任意点(设为v1)在V(G)-v中至少与一个N(G)-v1中的点是相连通的
假使不然即v1处于一个连通分支上,(v,v1)为G的桥,Deg(R0)>3,矛盾

(2)再证:存在L(v1,v2)=v1.....v2,|L(v1,v2)|>=1,设v2是v1连通的路径最短的一个点.(因此除v1,v2外任何N(v)中的点都不在路径中)C=v1.....v2vv1,则:
(a)不存在N(v)-v1-v2的任意点在C内
(b)不存在V(G)-N(v)-v的任意点
证明(a)
若存在设此点为v3由上知,若存在L(v1,v3)则L(v1,v3)>=2,则有面的次数>=4
若存在L(v2,v3)>=1则在L(v1,v2)并上L(v2,v3)并上v1vv3中必有面次数>=4
所以不含此类点v3
(b)
C是约当曲线,所以该点不能与C外部的点相连,连L(v1,v2)上的任意点都会存在次数>=4的面
所以C内不存在此类点
还能推出L(v1,v2)=v1v2

(3)对于V(G)-v,N(v)中的任意点(设v1)至多与2个N(v)-v1中的点相连通
证:因为对于v1v1只有逆时顺时两个方向连通2个点,如果有>=3的点与它相连通必然有一个圈位于另一个圈内,与(2)中的(a)矛盾.

(4)定义E*={(u1,u2)|u1,u2为N(v)中点且不同},V=N(G)构成的新图G*,(1)说明G*中的点度数都>=1,(3)说明G*中的点都<=2,
若存在一度点由握手知一度点成对出现.设G*中有n个连通分支,每个连通分支必然是一条路径,在时钟方向上任取2个相邻的连通分支,则P1的首与P2尾在时针方向上相邻(由(2)的证明得出)所以一度点是不存在的所以只有2度点

*树形目录（最近20个回帖）	顶端
主题：图论的小问题问问(702字) － Supremgoooo，2006年8月22日
回复：假设d（v）=x，则c是由x个顶点构成的一个圈，显然其长度为x=的（v）..(63字) －栖憧，2007年10月14日
回复： yangling的证明也是越了很大的步骤,实际上:"则G'中必定存在一个圈C，使v在C中，且任意u..(294字) － yourwk，2006年8月24日
回复：我觉得是不是可以借助定理11.4的思路。极大平面图每个面的度数都为3。对G中任意一顶点v,v在外部..(484字) － yangling_1985，2006年8月24日
回复：昨晚跳了大步,今晚就试图来详细的解一下:对于题只要证明对于圈C的任意点是2度的(就圈C而言),结..(1280字) － yourwk，2006年8月23日
回复：我是这么想的，但确实找不到更好的方法，不过这个不是什么大问题吧``没必要在这里纠缠.......(89字) － zsmjlu，2006年8月23日
回复：我上午想了一下,关于极大平面图必是轮图的并,大家看这样对不对若不是则存在如下情形，(图中的一部分..(788字) － zsmjlu，2006年8月23日
回复：我相信“极大平面图必是轮图的并”（这个命题似乎等价于“对每个顶点的v，存在一个圈C，使得C的顶点恰..(242字) － Logician，2006年8月23日
回复： 1.关于书上的这个证明中说到是某个圈,这个某是特指(即与v相邻的所有点构成的一个圈)下面在证明一下..(724字) － yourwk，2006年8月22日
回复： [quote][b]以下是引用[i]yourwk在2006-8-22 23:37:00[/i]的发..(1018字) － Supremgoooo，2006年8月23日
回复： [quote][b]以下是引用[i]yourwk在2006-8-22 23:37:00[/i]的发..(406字) － Logician，2006年8月23日
回复： logican 确实思路比较多,佩服`````(32字) － zsmjlu，2006年8月22日
回复： [quote][b]以下是引用[i]Supremgoooo在2006-8-22 21:19:00[..(399字) － zsmjlu，2006年8月22日
回复： [quote][b]以下是引用[i]zsmjlu在2006-8-22 23:09:00[/i]的发..(277字) － Supremgoooo，2006年8月23日
回复： [quote][b]以下是引用[i]zsmjlu在2006-8-22 23:09:00[/i]的发..(269字) － Logician，2006年8月23日
回复： [quote][b]以下是引用[i]Logician在2006-8-23 0:25:00[/i]的..(489字) － zhongyuan17，2007年10月15日
回复： [/quote] 问题是，怎么证明任何顶点v和它的邻顶正好构成一个轮图呢？也就是说，怎么..(248字) － zsmjlu，2006年8月23日
回复：（1）不知道。@_@（2）3-正则图怎么不可能是2-边连通的？首先，3-正则图不一定是就是3-边..(694字) － Logician，2006年8月22日
回复： [quote][b]以下是引用[i]Logician在2006-8-22 23:02:00[/i]..(813字) － Supremgoooo，2006年8月23日
回复：你把问题说全吧,我现在手边没书.:)不好意思~(49字) － carroty，2006年8月22日

*树形目录（最近20个回帖）

顶端

主题：

图论的小问题问问(702字) － Supremgoooo，2006年8月22日

回复：

假设d（v）=x，则c是由x个顶点构成的一个圈，显然其长度为x=的（v）..(63字) －栖憧，2007年10月14日

回复：

yangling的证明也是越了很大的步骤,实际上:"则G'中必定存在一个圈C，使v在C中，且任意u..(294字) － yourwk，2006年8月24日

回复：

我觉得是不是可以借助定理11.4的思路。极大平面图每个面的度数都为3。对G中任意一顶点v,v在外部..(484字) － yangling_1985，2006年8月24日

回复：

昨晚跳了大步,今晚就试图来详细的解一下:对于题只要证明对于圈C的任意点是2度的(就圈C而言),结..(1280字) － yourwk，2006年8月23日

回复：

我是这么想的，但确实找不到更好的方法，不过这个不是什么大问题吧``没必要在这里纠缠.......(89字) － zsmjlu，2006年8月23日

回复：

我上午想了一下,关于极大平面图必是轮图的并,大家看这样对不对若不是则存在如下情形，(图中的一部分..(788字) － zsmjlu，2006年8月23日

回复：

我相信“极大平面图必是轮图的并”（这个命题似乎等价于“对每个顶点的v，存在一个圈C，使得C的顶点恰..(242字) － Logician，2006年8月23日

回复：

1.关于书上的这个证明中说到是某个圈,这个某是特指(即与v相邻的所有点构成的一个圈)下面在证明一下..(724字) － yourwk，2006年8月22日

回复：

[quote][b]以下是引用[i]yourwk在2006-8-22 23:37:00[/i]的发..(1018字) － Supremgoooo，2006年8月23日

回复：

[quote][b]以下是引用[i]yourwk在2006-8-22 23:37:00[/i]的发..(406字) － Logician，2006年8月23日

回复：

logican 确实思路比较多,佩服`````(32字) － zsmjlu，2006年8月22日

回复：

[quote][b]以下是引用[i]Supremgoooo在2006-8-22 21:19:00[..(399字) － zsmjlu，2006年8月22日

回复：

[quote][b]以下是引用[i]zsmjlu在2006-8-22 23:09:00[/i]的发..(277字) － Supremgoooo，2006年8月23日

回复：

[quote][b]以下是引用[i]zsmjlu在2006-8-22 23:09:00[/i]的发..(269字) － Logician，2006年8月23日

回复：

[quote][b]以下是引用[i]Logician在2006-8-23 0:25:00[/i]的..(489字) － zhongyuan17，2007年10月15日

回复：

[/quote] 问题是，怎么证明任何顶点v和它的邻顶正好构成一个轮图呢？也就是说，怎么..(248字) － zsmjlu，2006年8月23日

回复：

（1）不知道。@_@（2）3-正则图怎么不可能是2-边连通的？首先，3-正则图不一定是就是3-边..(694字) － Logician，2006年8月22日

回复：

[quote][b]以下是引用[i]Logician在2006-8-22 23:02:00[/i]..(813字) － Supremgoooo，2006年8月23日

回复：

你把问题说全吧,我现在手边没书.:)不好意思~(49字) － carroty，2006年8月22日


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	66.406ms