检索结果-南通市图书馆

运筹学学报 2002年第1期6卷 75-78页

作者：邓汉元黄元秋湖南师范大学数学系长沙410081

设γM（G）是连通图G=（V,E）的最大亏格,记EM-（G）={e ∈ E（G）G\e连通,且γM（G\e）=γM（G）}.若EM-（G）≠　,则称G是γM（G）-可约的;否则称G是γM（G）-不可约的.本文证明了边的剖分不改变图的最大亏格可约性,点的扩张不改变上... 详细信息

设γM（G）是连通图G=（V,E）的最大亏格,记EM-（G）={e ∈ E（G）G\e连通,且γM（G\e）=γM（G）}.若EM-（G）≠　,则称G是γM（G）-可约的;否则称G是γM（G）-不可约的.本文证明了边的剖分不改变图的最大亏格可约性,点的扩张不改变上可嵌入图的最大亏格可约性;并给出了两类满足EM-（G）=E（G）的非4-边连通图.

关键词：边剖分点扩张最大亏格 Betti亏数可约性连通图拓扑图论

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

关于可平面图的边剖分的若干结果

关于可平面图的边剖分的若干结果

引用

作者：吴玉文山东大学

学位级别：硕士

本文考虑的图若无特殊声明均为简单、无向有限图。对于一个图G=G(V(G)，E(G))，我们用V(G)和E(G)分别表示图的顶点集合和边集合。对任意的v∈V(G)，我们用dG(v)表示顶点v在G中的度数。△(G)和δ(G)分别表示图G的最大度和最小度。对V(G)... 详细信息

本文考虑的图若无特殊声明均为简单、无向有限图。对于一个图G=G(V(G)，E(G))，我们用V(G)和E(G)分别表示图的顶点集合和边集合。对任意的v∈V(G)，我们用dG(v)表示顶点v在G中的度数。△(G)和δ(G)分别表示图G的最大度和最小度。对V(G)的子集S，用G—S表示从G中删去顶点集合S及其关联的边所得到的子图。若S={v}，则令G—v=G—{v}。对E(G)的子集X，用G—X表示从G中删去边集合X所得的子图。若X={e}，则G—{e}简记为G—e。若存在V(G)的两个不交子集X、Y，使得V(G)=X∪Y，且G的所有边均一个端点在X内，另一个端点在Y内，则称G为二部图，记为G=(X，Y，E(G))。若图G可以表示在平面上，并且任两条边仅在其端点处才可能相交，则称G是可平面图。图G的这种平面上的表示法称为G的一个平面嵌入，或称为平面图。对于一个平面图G，我们用F(G)来表示G的面集合。对于一个面f，我们把将f围起来的所有的边所构成的集合称为f的边界，并且称f关联于其边界上的所有的顶点和边。同样地，可以定义f的度dG(f)为f的边界上的边数。若G的两个面f和f有一条公共边e，则称面f和f相邻接于边e。若存在映射φ：E(G)→{1，2，…，k}，对于G中任意两条相邻接的边e和e，满足φ(e)≠φ(e)，则称G是k-边可染色的。这时对于任意的1≤i≤k，φ(i)的边导出子图均是图G的一个匹配。我们把使得图G具有k-边染色的最小正整数k定义为G的边染色数，记作X′(G)。若图的每一个连通分支都是一条路，则称该图为一个线性森林。我们称映射φ∶E(G)→{1，2，…，t}为图G的一个t-线性染色，如果对于任意的1≤α≤t都有，φ(α)的边导出子图是一个线性森林。我们把使图G具有t-线性染色的最小正整数t称为G的线性荫度，记作la(G)。图的染色理论是图论的一个重要分支，是图论研究中最活跃的课题之一。根据一定的规则将一组目标划分为不同的种类，这是数学中的一个基本方法。不同的规则决定着该组中任意一对目标是否在同一个类中。图的染色理论就是研究这类问题的一门理论，它有着相当广泛的应用背景。各种形式的日程表问题，时间表问题以及排序问题，从根本上来说都可以归结为染色问题。对染色理论的研究最早可以追溯至1852年，即著名的“四色猜想”的提出。而图的边染色问题引起人们关注的时间相对较晚。但是，许多研究领域，如地图染色，匹配理论以及拉丁方，都与边染色问题有着紧密的联系。关于边染色的第一篇文章出现在1880年，由P．G．Tait在对“四色猜想”做进一步的研究时，证明出“任一2-边连通，3-正F则的平面简单图是3-边可染色的”与“四色猜想”是等价的。此后，关于边染色问题的研究又有了一些比较重要的结论，如K(o|¨)nig’s Theorem，Shannon’s Theorem以及Vizing’s Theorem。图的边染色中，根据著名的Vizing’s Theorem，可以将简单图分为两类。图的分类问题就是判断一个图G究竟是第一类图，还是第二类图的问题。关于图的分类问题，虽然已有一些相关的结论，但是未解决的部分还有很多。而对于可平面图的边染色的分类问题，Vizing证明出任一△(G)≥8的可平面图G均是第一类图，而△∈{2，3，4，5}的可平面图中存在第二类图。于是Vizing在1968年的时候，提出了著名的可平面图猜想。图G的线性荫度这一概念是由Harary在1970年提出的。接着在1980年，由Akiyama，Exoo和Harary等人给出了关于正则图的线性荫度的猜想;并且在这一猜想的基础上，产生了著名的线性荫度猜想(the Linear Arboricity Conjecture，简称为LAC)。在对线性荫度猜想进行研究时，J．Wu解决了可平面图条件下这个猜想的大部分情况，只余下△7这一种情况仍未解决。我们在本文中主要研究的是可平面图的边染色及线性荫度方面的一些结果。全文共分三章，第一章简单介绍一下图论中的一些基本概念，并给出边染色、线性荫度问题的历史背景和进展状况以及一些已有的相关结论。这一章是后面其他各章节的基础。第二章我们主要讨论可平面图的边染色的一些情况。主要结论为：定理2．1．10．设G是最大度为5的可平面图。若G中不含长度为4的圈，或不含长度为5的圈，则G是第一类图。第三章则讨论了可平面图的线性荫度的一些情况，其主要结论为：定理3．2．1．设G是最大度等于7的可平面图，则la(G)≤4。定理3．3．2．设G是最大度△(G)≥11的可平面图，则la(G)=「(△(G))/2(?)。定理3．3．3．设G是一个最大度△(G)≥7的可平面图，若G中任意两个三角形都没有公共边，则la(G)=「(△(G))/2(?)。

关键词：图可平面图边剖分边染色线性荫度

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

图的线性2-荫度

图的线性2-荫度

引用

作者：李元超浙江师范大学

学位级别：硕士

图G的线性k-荫度lak（G）是指最小的正整数m,使得G的边集能被剖分成m个边不交的集合,满足每一个集合是森林,且森林中每一个连通分支都是长度至多为k的路.当取到两个极端情况时,la1（G）显然为图G的边色数;la∞（G）则为图G的线性荫度la... 详细信息

图G的线性k-荫度lak（G）是指最小的正整数m,使得G的边集能被剖分成m个边不交的集合,满足每一个集合是森林,且森林中每一个连通分支都是长度至多为k的路.当取到两个极端情况时,la1（G）显然为图G的边色数;la∞（G）则为图G的线性荫度la（G）.1970年,Harary提出了图的线性荫度这个概念.而后在1980年,Akiyama,Exoo和Harary猜想,对于任何正则图G,有la（G）=「（△（G）+ 1）/2」.因为对于任何图都有la（G）≥「△（G）/21,所以这个猜想等价于著名的线性荫度猜想（LAC）:对任何简单图G,有「△（G）/2」 $ la（G）≤「（△（G）+ 1）/21.在这个猜想的推动下,Habib和Peroche（1982）进一步提出了线性k-荫度的概念,并给出一个关于线性k-荫度的猜想:若G是含有n个顶点的图,且k≥ 2是一个正整数,则本学位论文主要围绕图的线性2-荫度问题展开,探讨了平面图的线性2-荫度,环面图的线性2-荫度以及稀疏图的线性2-荫度问题,分为以下五个部分:第一章介绍了本文用到的定义,符号及专业术语,简述了相关领域的研究现状并呈现了本文的主要研究结果.同时,给出了线性2-荫度的几个性质引理.第二章将证明两个边剖分定理,这在后面几章中证明我们的主要结论至关重要.第三章考虑环面图G的线性2-荫度问题,证明了:（1）la2（G）≤「△（G）+1/2」+7;（2）若 G 不含某个 k-圈,其中 k ∈ {3,4,5},则 la2（G）≤「△（G）+1/2」+4.在第四章中我们研究2-退化图,最大平均度较小时的稀疏图的线性2-荫度.证明了:（1）G 为 2-退化图,则 la2（G）≤「△（G）/2 」 + 2;（2）mad（G）＜4,则 la2（G）≤「△（G）+1/2」+ 4;（3）若 mad（G）＜7/2,则 la2（G）≤「△（G）+1/2」+ 3;（4）mad（G）＜5,则la2（G）≤「△（G）+1/2」+ 10.第五章我们研究最大度较大时的平面图的线性2-荫度问题.证明了若G是△（G）≥ 9 的平面图,则 la2（G）≤ △（G）-1.

关键词：线性2-荫度边剖分平面图环面图最大度

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：