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

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

本主题类别:

1.关于书上的这个证明中说到是某个圈,这个某是特指(即与v相邻的所有点构成的一个圈)下面在证明一下这个圈必定存在,假设存在对于v1,v2(为是与v相邻的任两点)(v1,v2)不属于E(G).这就是说极大平面图有大于圈长为3的面存在,矛盾,所以(V1,V2)肯定属于E(G)因为任意就知道这个圈是存在的

2.边连通度>=K就说图是K连通的,并不是你想的边连通度=2,比如说该题连通度=5.图是1边连通的也是2边连通的也是3边连通的...要证明它是2边连通的只要证明删除任一条边还是连通的即可

3.答案
13,设G是2-边连通的简单平面图，且每两个面的边界至多有一条公共边，证明G中至少有
两个面的次数相同。
证明做G的对偶图G*，只要证明G*上至少有2个顶点的度数相同即可。

G是连通图，显然G*也是连通图。

设G*上有n个顶点，这n个顶点的度数只能是1至n-1，根据鸽巢原理，至少有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号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	62.500ms