自补图理论及其应用 - 中国高校教材图书网
|
书名： |
自补图理论及其应用
|
| ISBN： | 7-5606-0801-9 |
条码： | |
| 作者： |
许进
相关图书
|
装订： | 0 |
| 印次： | 1-1 |
开本： | 0 |
| 定价： |
￥25.00
折扣价：￥23.75
折扣：0.95
节省了1.25元
|
字数： |
386千字
|
| 出版社： |
西安电子科技大学出版社 |
页数： |
|
| 发行编号： | 107200 |
每包册数： |
|
| 出版日期： |
1999-12-01 |
|
|
| 内容简介： |
本书是国际上第一部关于自补图理论及其应用的学术专著。全书共分9章，系统地研究了自补图的基本性质与基本理论：涉及自补图的基本性质；自补图与有向自补图的计数；自补图的分解与构造技术；自补图中的路与圈；正则与强正则自补图理论；2重自补图理论；偶自补图理论；自补度序列图理论。在应用方面，探讨了强正则自补图在对角线型的Ramsey数问题研究上的应用，还讨论了自补图在图与其补图色多项式研究中的应用。
本书从ABC出发，采用循序渐进的写作方法，把读者逐步引入自补图研究的最前沿。该书第1章给出了图论中的一些必要的内容，使得不具有图论知识的读者也可以顺利阅读全书。本书的每一章后均附有尚待解决的公开问题或猜想，供那些有兴趣进一步研究的读者参考。
本书可供数学、计算机科学、电路与系统、智能科学以及有关工程技术人员使用，也可作为大学本科生和研究生学习的教材和参考书。
|
| 作者简介： |
|
|
| 章节目录： |
第1章 图的基本知识
1.1 图的定义与分类
1.2 图的同构
1.3 图的库与库序列
1.4 子图及其运算
1.5 路、圈、图的连通性，补图与自补图
1.6 匹配、独立等，覆盖与Ramsey数
1.7 图的三种矩阵
1.8 群与图的自同构群
1.9 尚待解决的困难或猜想
习题
参考文献
第2章 自补图的基本理论
2.1 引子
2.2 自补图置换
2.3 可自补库序列
2.4 自补图中的三角形
2.5 自补图的直径
2.6 自补图的同构群
2.7 自补图的谱
2.8 自补图的色性
2.9 尚待解决的困难问题
习题
参考文献
第3章 自补图的解解与构造
3.1 引言
3.2 自补图的分解
3.3 4n阶自补图的构造
3.4 (4n+1)阶自补图的构造
3.5 尚待解决的问题
习题
参考文献
第4章 自补图的计数理论
4.1 计数的基本理论
4.2 p阶自补图与p阶有向自补图的数目
4.3 素数阶顶点可传有向、无向自补图的计数
4.4 标定自补图计数问题的讨论
4.5 公开问题
习题
参考文献
第5章 自补图中的路与圈
5.1 圈与Hamilton圈的基础知识
5.2 自补图中的路
5.3 自补图中的圈
5.4 自补图的Hamilton性
5.5 尚待解决的问题
习题
参考文献
第6章 正则与强正则自补图
6.1 正则与强正则自补图
6.2 正则与强正则自补图的基本性质
6.3 强正则自补图的自补置换
6.4 阶数≤49的强正则自补图的完全计数
6.5 Kozting三个公开问题的解
6.6 强正则自补图与Ramsey数
6.7 尚待解决的困难问题或猜想
习题
参考文献
第7章 有向、无向偶自补图
7.1 偶自补图的基本理论
7.2 可偶自补库序列
7.3 偶自补图的计数问题
7.4 偶自补图的构造
7.5 有向偶图的数目
7.6 有向偶自补图的计数
7.7 尚待解决的问题
习题
参考文献
第8章 2重自补图与有向自补图
8.1 基本概念
8.2 可2重自补序列
8.3 计数理论
8.4 2重自补图的构造
8.6 顶点数小于或等于5的全部有向自补图
8.7 尚待解决的问题与猜想
习题
参考文献
第9章 自补图与图的色多项式
9.1 图的色多项式
9.2 自补图序列图
9.3 图与它的补图的色多项式
9.4 尚待解决的困难与猜想
习题
参考文献
|
| 精彩片段： |
|
|
| 书 评： |
当我在1984年攻读硕士学位期间，学习由李慰萱教授所译Harary的《图论》一书时，发现其中第二章的习题2.17(“画出有8个顶点的所有4个自补图”)有问题，因为我构造出了多个8个顶点的6个自补图。于是，我通过查阅Read在1963年的文章得知：8个顶点共有10个自补图!并通过一种自补图的分解方法很快把这8个顶点的自补图全部构造出来。由此，我对自补图产生了浓厚的兴趣。1984年至今已经有15年多了，在这15年当中，我几乎每年都完成关于自补图方面的几篇学术论文。正因为对自补图的浓厚兴趣，使得我在自己的硕士学位论文(《论自补度序列图及自补图的构造》)以及我的理学博士学位论文(《图的自补性与色性》)中均对自补图进行了较为深入的研究。本书就是在我的上述两篇学位论文的基础上产生的。
一个图若与它的补图同构，则称这个图为自补图。自补图是有趣而重要的一类图。目前业已发现，自补图在对角线型的Ramsey数方面的研究、关于图的Shannon容量的研究、图与它的补图的色多项式相互之间关系方面的研究、强完美图(strongperfectgraph)猜想以及图的同构测试问题等的研究有其重要的应用，因而，越来越多地受到图论学者的关注。
自补图的研究始于本世纪60年代初，它几乎同时由三位著名的图论专家Ringel,Sacha和Read各自独立地进行了研究。随后有许多著名的图论专家展开对自补图的研究，如Rao,Clapham,Mathon等。到目前为止，关于自补图理论及其应用的研究已经取得了丰富的结果，并且有许多优美的结果与独特的方法。基于此因，我们撰写了这本关于自补图理论及其应用的学术专著。在这本书中，我们几乎对关于自补图理论方面的所有重要的结果都给予了较为详细的论述。
本书是国际上第一部关于自补图理论及其应用的学术专著。全书共分9章，系统地研究了自补图的基本性质与基本理论：诸如自补图的度序列特征与实现算法；自补图的直径特征；自补图与有向自补图的计数；自补图的分解与构造技术；自补图中的路与圈，特别是关于自补图的Hamilton性的刻划；正则与强正则自补图的计数与构造；引入2重自补图类，较系统地研究了2重自补图的基本性质与基本理论，并将其应用于有向自补图的研究之中；通过发现自补图的一种分解方法，引入了偶自补图的概念，指出了偶自补图是自补图中一类关键的、核心的生成子图，进而对偶自补图的基本特征与基本性质进行了较为详细的研究；引入一类自补图类更广泛的图——自补度序列图并对其基本特征与基本性质进行了研究。在应用方面，主要有两个方面的内容：一是强正则自补图在对角线型Ramsey数问题研究上的探讨，特别是提出了Ramsey数R(5,5)=46的猜想；另一个是自补图在图与其补图色多项式研究中的应用，成功地应用自补图方法解决了Akiyama和Harary在这一领域所提出的猜想。
由于Laszlolovasz在1979年的突破性的工作(Laszlolovasz.OntheShannoncapacityofagraph.IEEETrans.OnIT,1979,25(1):1-7)，使得关于图的Shannon容量的研究陡然“热”了起来。然而，关于图的Shannon的研究还是非常困难的，目前仅能对极少数的图类可求出它们的Shannon容量。而对一般图的Shannon容量的计算是困难的，甚至对一些极其简单的图也是如此。应用自补图对图的Shannon容量的研究是Laszlolovasz在1979年所给出的。但这仅仅是一个开始，还没有实质性的工作。我们试图应用自补图对图的Shannon容量作进一步的研究，已经有一些好的进展，但还不够成熟，故在本书中尚未讨论。另外，关于自补图在强完美图猜想以及图的同构测试问题的应用也未列入。这也是我感到很遗憾的不足之处。
本书在完成过程中得到了国内外许多同行的关心与帮助。首先要感谢的是我的硕士导师、西北工业大学的王自果教授，我的博士导师、北京理工大学的王朝瑞教授和新加坡国立大学(NationalUniversityofSingapore)数学系教授KohK.M.博士。是王自果教授教给我图论，引导我研究自补图理论，是王朝瑞教授使得我的自补图理论的研究更加深入。
1994年KohK.M.教授邀请我去新加坡国立大学访问讲学，并作了关于《SelfComplementaryGraphs:TheoryandApplication》的学术报告。在访问期间，KohK.M.教授就这本书的编写大纲及内容进行了多次磋商(其中包括我1997～1998年在新加坡国立大学作计算机系的ResearchFellow期间)，并给我提供了许多关于自补图方面的资料以及他本人的学术论文，在此表示衷心的感谢。
在本书
|
| 其 它： |
|
|
|
中国大学出版社协会 |
首页 |
宏观指导 |
出版社天地 |
图书代办站 |
教材图书信息 |
教材图书评论 |
在线订购 |
教材征订
