| 单词 | 图的度序列 |
| 释义 | 【图的度序列】 拼译：degree seguences of graphs 图论研究的一个基本领域。给定一个n阶简单图G，其顶点v1，v2，…，vn的度依次为d1，d2，…，dn，d1≥d2≥…≥dn，π=(d1，d2，…，dn)，即是图G的度序列。若它是某个图的度序列，一个非增的非负整数序列π=(d1，d2，…，dn)是可图的(graphic)，由于同构的图具有相同的度序列，而度序列相同的图未必同构，因此度序列是图同构的不变量，但不是全系不变量。所以一个图的度序列的代数性质必然部分地反映这个图的图论性质，其反映程度是度序列研究的基本课题。度序列的研究主要围绕下面两个基本问题进行：(1)刻划可图序列；(2)对给定的图论性质P，刻划蕴含P(Potentially-P)可图序列和强迫P(forcibly-P)可图序列。 1957年Gale与Ryser率先给出可图序列的刻划，从而揭开研究度序列的序幕。至今已发表400多篇论文。关于可图序列的刻划，至今已发现7个判准和1个算法，即：Gale-Ryser判准(1973)、Erdös-Gallai判准(1960)、Fulkerson-Hoffman-MeAndrew判准(1965)、Grtinbaum判准(1969)、Berge判准(1973)、Bollobás判准(1978)和Ruch-GutmanHässelbalth(1979，1984)以及Kleitman-Wang算法(1973)。应该说，在以往数十年里，可图序列的刻划已经彻底解决。但一些基本性工作尚有待进一步研究。1991年Sierksma和Hoogeveen用循环论证法证明，可图度列的7个判准是等价的。1992年J．S．Li进一步证明，上述7个判准实质上只有两个，即GaleRyser判准，Erdös-Gallai判准，Fulkerson-HoffmanMcAdrew判准，Berge判准和Ruch-Gutman-Hǎssebath判准是同一件事物的不同表述形式，而Grünbaum判准与Bollobás判准则是另一件事物的两种表达形式。J．S．Li研究了n维可图序列集合Gn的整体性。易知Gn在序列间优超关系下成为偏序集。J．S．Li刻划了偏序集Gn中的极大元。1991年Favaron，Mahéo和Saclé证明，可图序列π的剩余R(π)(Residue)是偏序集Gn上一个Schur凸函数。最早研究蕴含P和强迫P可图序列的是Edmonds。1964年，他给出了蕴含k边连通可图序列的刻划。此后，蕴含P和强迫P可图序列的研究便得到蓬勃发展。其主要研究方法是：(1)利用判定可图序列的Kleitman-Wang算法，即所谓Laying off技巧。(2)利用Edmonds在刻划蕴含k边连通可图序列时所使用的Interchange技巧及其变形。所谓Interchange技巧是指：设G是可图序列π的一个实现，若G含有边xy，uv，不含边xu，yv，则G′=G－xy－uv+xu+yv也是π的一个实现。从图G到G′的变换是保持可图序列不变的一种变换，它称为对π进行一次Interchange；Laying off技巧是指：设π=(d1，d2，…，dn)是非增的非负整数序列，从π中去掉第k项dk，并将余下的dk个最大的项各减去1，得到序列π′。从π到π′的过程称为从π lay off dk。1973年，Wang和Kleitman用Laying off技巧给出蕴含k连通可图序列的刻划，并且给出Edmonds上述结论的新证明。关于强迫k连通可图序列，1969年Bondy给出一个充分条件。当k=1时，1991年Choudum给出一个充分条件。但强迫k连通和强迫k边连通可图序列的刻划问题仍未解决。具有Hamilton圈的图称为Hamilton图。刻划强迫Hamilton可图序列的问题是Nash-William于1966年提出的。1976年Bondy和Murty将它收入到他们的名著《Graph Theory with Applications》，列为当时图论中50个未解决问题之一。它一直是人们关注的一个热点。到目前为止，所有的研究都集中在充分条件上。主要方法则是运用Bondy和Chvátal引进的k闭包概念。给定正整数k，对图G中任意两个度之和至少为k的不相邻顶点都连一条边，直到不能再连为止，得到的图Ck(G)即是G的k闭包。Bondy和Chvátal证明，n阶图G为Hamilton的充要条件是，n闭包Cn(G)为Hamilton的。在Bondy-Chvátal方法基础上，Zhu和Tian给出了可图序列为强迫Hamilton的一个充分条件。这是迄今为止所得到的最好的充分条件。1988年P．Ц．Tышкeвич，А．А．ЧepHяк和Ж．А．ЧepHяк称Zhu和Tian所用的方法为Bondy-Chvátal-Zhu-Tian方法。但是NashWilliam 20多年前提出的刻划强迫Hamilton可图序列的问题仍未解决。至于蕴含Hamilton可图序列的刻划问题，Rao已经解决。刻划蕴含可平面和强迫可平面可图序列的问题一直为人们所关注。由Euler公式可知，可平面图G的度序列π=(d1，d2，…，dn)应满足d1+d2+…+dn≤6(n－2)。满足这一条件的可图序列π称为Euler序列，其中等式成立的Euler序列称为极大的。另外，一个可图序列π=(d1，d2，…，dn)称为k序列，若d1－dn=k。1971年，Owens首先研究蕴含可平面可图序列的刻划问题。他证明，除(47)和(514)外，每个Euler零序列都是蕴含可平面的，这里π=(47)表示π是由7个4组成的。随后Schmeichel和Hakimi证明，除(510，4)，(512，4)，(6，512)，(6，514)外，每个Euler 1序列都是蕴含可平面的。他们还证明，除(45，2)，(511，3)，(6h－7，47)，h＞7，(53，33)，(71，512)以及未定情形(513，3)，(7，517)外，每个非极大Euler 2序列都是蕴含可平面的。他们也研究了极大Euler 2序列，留下未定情形：(7h+1，62－h，513+h)，(73+2h，6，515+2h)，(75+2h，517+2h)，h=0，1。他们提出如下猜想：(513，3)，(7，517)和(73，517)，(7h+1，62－h，513+h)，h=0，1，2和(75+2h，517+2h)，h=0，1都不是蕴含可平面的，而上述其他未定序列都是蕴含可平面的。Ruscitti，Fanelli研究了上面遗留的序列，Mao研究了序列(75+2h，517+2h)，h=0，1和(73，517)，证明它们不是蕴含可平面的，从而宣告Schmeichel-hakimi猜想的解决，然而刻划蕴含可平面可图序列的问题并未解决。至于强迫可平面可图序列的刻划问题，Rao已经解决。与无向图情形相比，有向图情形的可图序列的研究进展较为缓慢。最令人注目的是1960年Fulkerson给出了非负整数偶序列π=［(r1，s1)，(r2，s2)，…，(rn，sn)］为有向可图序列的判准，从而解决了可图序列的刻划问题。其次是1965年Beineke和Harary给出了蕴含强连通有向可图序列的刻划。自然要考虑的是蕴含k强连通有向可图序列的刻划问题。1979年Chaiken，Kleitman和S．Y．R．Li考虑了这一问题，得到了有向可图序列为蕴含2强连通的一个充分条件。他们的结论离蕴含2强连通有向可图序列的刻划相去甚远。至于蕴含k强连通有向可图序列的刻划问题，则难度更大。而刻划强迫k强连通有向可图序列的问题，至今仍未解决。李炯生等和Bagga与Beineke曾对特殊有向图类(如竞赛图、多部竞赛图)得到一些结论，例如李炯生等给出了蕴含k强连通和强迫k强连通得分向量的刻划。根据Rao，ышкeвич、Чepняк以及李炯生的综述文章，可以预期，图的度序列的研究将围绕以下几个问题进一步展开：(1)深入研究偏序集Gn的整体性质，考虑偏序集Gn上哪些计数函数是Schur凸的，哪些是Schur凹的。(2)深入研究蕴含P和强迫P(有向)可图序列的刻划问题，特别是强迫k连通可图序列、强迫Hamilton可图序列和强迫可平面可图序列的刻划以及蕴含k强连通有向可图序列的刻划等。这些问题的解决，无疑将是度序列研究的突破性进展。【参考文献】：1 Rao S B. Combinatorics and Graph Theory, Proceedings. Calcutta 1980,Berlin,Springer-Verlag,1981,415～4402 Zhu Y, Tian F, J. Combinatorial Theory,Ser. B,1983, 35 (3):247～2553 A.K BEPHET KA ,1987,6:12～19; 1988;2:1～12;1988;5:1～84 Mao J Z. Kexue Tongbao (English Ed),1987,32(2):145～ 1465 FavaronO,MahéoM,Sacle J-F. J Graph Theory,1991,15 (1):39～646 Sierksma G ,Hoogeveen H,J. Graph Theory,1991,15(2): 222～2317 Choudum S A. Discrete Mathematics, 1991, 96 (3): 175 ～ 181(中国科技大学博士生导师李炯生撰) |
| 随便看 |
科学参考收录了7804条科技类词条，基本涵盖了常见科技类参考文献及英语词汇的翻译，是科学学习和研究的有利工具。