新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 计算机科学论坛 → 计算机理论与工程 → 『 计算机考研交流 』 → 图论的小问题问问 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 8561 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 图论的小问题问问 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     Logician 帅哥哟，离线，有人找我吗？天蝎座1984-10-28
      
      
      威望：9
      头衔：逻辑爱好者
      等级：研三(收到IBM CRL的Offer了)(版主)
      文章：1219
      积分：10357
      门派：IEEE.ORG.CN
      注册：2005/3/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Logician发送一个短消息 把Logician加入好友 查看Logician的个人资料 搜索Logician在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给Logician  访问Logician的主页 引用回复这个贴子 回复这个贴子 查看Logician的博客第11楼
    发贴心情 

    我相信“极大平面图必是轮图的并”（这个命题似乎等价于“对每个顶点的v，存在一个圈C，使得C的顶点恰为v的所有邻顶”），但这个证明………
    似乎太不完整了……
    你的证明不能保证所有的极大平面图都可以这样构造出来（因为不一定要按你说的方式添新边）。

    ----------------------------------------------
    Three passions, simple but overwhelmingly strong, 
    have governed my life: the longing for love, the
    search for knowledge, and unbearable pity for the
    suffering of mankind.
                                - Bertrand Russell

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/23 14:41:00
     
     zsmjlu 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(C++考了100分!)
      文章：52
      积分：307
      门派：IEEE.ORG.CN
      注册：2006/5/31

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给zsmjlu发送一个短消息 把zsmjlu加入好友 查看zsmjlu的个人资料 搜索zsmjlu在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看zsmjlu的博客第12楼
    发贴心情 
    我是这么想的，但确实找不到更好的方法，不过这个不是什么大问题吧``

    没必要在这里纠缠.....

    ----------------------------------------------
    用怀疑的目光看这个世界得一切``````

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/23 14:45:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第13楼
    发贴心情 
    以下是引用Logician在2006-8-22 23:02:00的发言：
    （1）不知道。@_@
    （2）3-正则图怎么不可能是2-边连通的？首先，3-正则图不一定是就是3-边连通的（下面有两个反例）。其次，即使是3-边连通的，根据定义，3-边连通的图自然也是2-边连通的和1-边连通的（注意，证明2-边连通就是证明删除1条边后还连通就可以了，并不要求证明“边连通度为2”）。

    我们知道，K_4是3-边连通的3-正则图。两个K_4的并是不连通的3-正则图。
    而下面两个3-正则图的边连通度分别是2和1：

       * ── *
      / \    / \   
    *   *  *   *
      \ /    \ /
       * ── *

    ┌ * - * ─ * - * ┐
    │ |   |    |   | │
    │ * - *    *   * │
    │  \ /      \ /  │
    └─ *        * ─┘

    总之，我们从正则性得不出太多关于边连通度的结论。

    （3）对偶图 + 鸽巢原理。就是证明“简单图中必有两个度数相同的顶点”。



    彻底明白了，谢谢！

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/23 19:14:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第14楼
    发贴心情 
    以下是引用zsmjlu在2006-8-22 23:09:00的发言：

    1,可以自己画一个轮图看一下,与中心相邻的点所在的圈长=d(v)
    2,对课本定义理解不透,k-边连通是指最小边连通度>=k ,即可(我理解) ,3-正则图最少删除2条边后连同分支才可>=2,故为2-边连通,没错!!!!



    懂了，谢谢！
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/23 19:16:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第15楼
    发贴心情 
    以下是引用yourwk在2006-8-22 23:37:00的发言：
    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不是连通图，G*也是连通图）

    由于G是2-边连通的简单平面图，所以G中无桥，所以G*中无环。
    由于G中每两个面的边界至多有一条公共边，所以G*中无平行边。
    所以G*是简单的连通平面图。

    设G*上有n个顶点，这n个顶点的度数只能是1至n-1，根据鸽巢原理，至少有2个
    顶点的度数相同。


    多谢！

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/23 19:23:00
     
     yourwk 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(猛啃高等数学)
      文章：5
      积分：134
      门派：XML.ORG.CN
      注册：2006/5/25

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给yourwk发送一个短消息 把yourwk加入好友 查看yourwk的个人资料 搜索yourwk在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看yourwk的博客第16楼
    发贴心情 
    昨晚跳了大步,今晚就试图来详细的解一下:
    对于题只要证明对于圈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度点

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/23 22:43:00
     
     yangling_1985 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(研究MFC有点眉目了!)
      文章：63
      积分：507
      门派：XML.ORG.CN
      注册：2006/4/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给yangling_1985发送一个短消息 把yangling_1985加入好友 查看yangling_1985的个人资料 搜索yangling_1985在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看yangling_1985的博客第17楼
    发贴心情 
    我觉得是不是可以借助定理11.4的思路。极大平面图每个面的度数都为3。对G中任意一顶点v,v在外部面R0或是在内部面Ri 上。
    （1）若v在R0 上，则v与内部面上另外两点a,b相邻。由n>3及G的每个内部面的次数均为3可以得R0中必存在另一点c与v相邻。所以，d(v)>=3.
    (2) 若v在Ri上。令G'=G-v,由于与v关联的边均不是外部面上的边，则G'中必定存在一个圈C，使v在C中，且任意u属于C，均和u在G中相邻（否则出现面大于3的内部面）。所以d(v)为C的长度。又由条件，则有d(v)>=3.
    不是严格的证明，只是说明一下我的想法。请大家指教。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/24 17:00:00
     
     yourwk 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(猛啃高等数学)
      文章：5
      积分：134
      门派：XML.ORG.CN
      注册：2006/5/25

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给yourwk发送一个短消息 把yourwk加入好友 查看yourwk的个人资料 搜索yourwk在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看yourwk的博客第18楼
    发贴心情 
    yangling的证明也是越了很大的步骤,实际上:"则G'中必定存在一个圈C，使v在C中，且任意u属于C，均和u在G中相邻"是你的结论,原因就是"否则出现面大于3的内部面".其他的说明都没有意义.与证明的题目无关.按照书上的证明同样的,他说"G'中必定存在一个圈C"这句话就需要证明,画出来的图也是特别巧的一个圈(刚好满足需要).
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/8/24 21:54:00
     
     栖憧 帅哥哟，离线，有人找我吗？处女座1986-9-13
      
      
      等级：大二(研究汇编)
      文章：27
      积分：219
      门派：XML.ORG.CN
      注册：2007/2/6

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给栖憧发送一个短消息 把栖憧加入好友 查看栖憧的个人资料 搜索栖憧在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看栖憧的博客第19楼
    发贴心情 
    假设d（v）=x，则c是由x个顶点构成的一个圈，显然其长度为x=的（v）
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/10/14 21:52:00
     
     zhongyuan17 帅哥哟，离线，有人找我吗？
      
      
      等级：大一(猛啃高等数学)
      文章：19
      积分：137
      门派：XML.ORG.CN
      注册：2007/8/12

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给zhongyuan17发送一个短消息 把zhongyuan17加入好友 查看zhongyuan17的个人资料 搜索zhongyuan17在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看zhongyuan17的博客第20楼
    发贴心情 
    以下是引用Logician在2006-8-23 0:25:00的发言：
    [quote]以下是引用zsmjlu在2006-8-22 23:09:00的发言：
      1,可以自己画一个轮图看一下,与中心相邻的点所在的圈长=d(v)
    [/quote]
    问题是，怎么证明任何顶点v和它的邻顶正好构成一个轮图呢？
    也就是说，怎么证明存在一个圈C，它的顶点恰为（既不多也不少）v的所有邻顶呢？



    必然是轮图.
    考虑与v相关的两条相邻的边,这两条边必在同一面上
    而这一个面的度为3.所以这两条边分别关联的另两个点之间必有边
    这样就是轮图了
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2007/10/15 10:09:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 计算机考研交流 』 的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/6/15 22:24:16

    本主题贴数20，分页： [1] [2]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 109.375ms