對Gallai問題幾種解答形式之間的等價性.pdf

1、分 類 編 號 :密 級 :單 位 代 碼 ：10065學 號 ： 0 920 500 5天 津 師 范 大 學研 究生 學位 論 文論 文 題 目： 對 Gal l ai問題 幾 種 解 答 形 式 之 間的 等 價 性學 生 姓 名： ^? n _ 申請學位級別： 理學碩士申請 專 業(yè) 名 稱 ： 基 礎 數(shù) 學 研 究 方 向 ：泛 函分 析指導 教師 姓 名 ： 李 國 全 專業(yè) 技術(shù) 職 稱 ： 教 授提 交 論文 日期

2、： 2012 年 3 月E q u iva len ce o f sev era la n sw ers to G a llai' s p ro b le mA b s t r a c tIn 196 1 T . G all aip rop osed h ow to cal cu l ate th e m ax i m um num b ers of i n d ep en d ent A -p athsw h i ch

3、 w as sol ved f irstl y by W . M ac ler i n 19 78 .A n altern ati ve an sw er w as gi ven b y L . L ov asz byderi vi n g f rom h i s m atroi d m atchi n g form u l a i n 1980 an d a short p roof w as gi ven b y A . S

4、ch ri jveri n 200 1.T h ose an sw ers are greatl y d i f Feron t ,i n ox p rossi on s.th i s p ap er i s goi n g to sh ow th ei req u iva l en ce.In 2 .1 th ree L em m as are sh ow ed to sim p l i fy th e w h ol e p ro

5、of an d th e eq u i val en ce b etw eenth e M ad er' s an d L ov asz' s versi on i s sh ow ed i n 2 . 2 ,th e eq u i v alen ce b etw een th e L ov asz' s an dSch ri jver' s versi on i s sh ow ed i n 2 .