圖的最大虧格與三類圖的1-因子數(shù)目.pdf

1、本文主要研究了兩個(gè)問(wèn)題：圖的最大虧格以及三類圖的1-因子計(jì)數(shù).
　　 本文第一部分是關(guān)于圖的最大虧格的綜述.圖的最大虧格問(wèn)題一直以來(lái)都是圖嵌入理論中的一個(gè)重要問(wèn)題，本文綜述了近30年來(lái)關(guān)于圖的最大虧格，以及它與其他不變量之間關(guān)系的重要研究和進(jìn)展，其中包括最大虧格與圖的連通性，圖的直徑，圖的染色數(shù)和圖的2-因子之間的關(guān)系，最大虧格嵌入數(shù)目以及最大虧格與嵌入圖等方面，并就這些方面給出了自己的一些看法.
　　 本文第二部分研究

2、了三類圖的1-因子(又稱為完美匹配)計(jì)數(shù)問(wèn)題.圖的1-因子計(jì)數(shù)問(wèn)題是匹配理論研究中的一個(gè)重要課題.Lovasz和Plummer就曾提出關(guān)于1-因子計(jì)數(shù)的一個(gè)猜想：任意的2-邊連通3-正則圖都有指數(shù)多個(gè)1-因子.另外，1-因子理論在很多領(lǐng)域也有很強(qiáng)的應(yīng)用背景比如物理學(xué)和化學(xué).但是，一般圖的1-因子計(jì)數(shù)問(wèn)題已經(jīng)被證明了是NP-困難的，所以一般考慮一些特殊圖的1-因子計(jì)數(shù).本文用劃分，求和，遞歸的方法分別給出了三類特殊圖(本文稱作L2n，C(