《超立方中匹配的哈密爾頓圈擴張性質》是依託南昌大學，由王凡擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：超立方中匹配的哈密爾頓圈擴張性質
- 項目類別：青年科學基金項目
- 項目負責人：王凡
- 依託單位：南昌大學
項目摘要,結題摘要,
項目摘要
Ruskey 和 Savage 在 1993 年提出了如下問題: 當 n 大於 1 時, n 維超立方的每一個匹配能否擴張成一個哈密爾頓圈? Kreweras 猜想: 當 n 大於 1 時, n 維超立方的每一個完美匹配可以擴張成一個哈密爾頓圈. Fink 證實了 Kreweras 的猜想的正確性. k 元 n 立方是超立方的一種推廣. 申請者在博士期間的工作已經表明 k 元 n 立方的完美匹配不一定能擴張成哈密爾頓圈, 這不同於超立方中完美匹配均可擴的結果. 本項目研究超立方中匹配的哈密爾頓圈擴張性質和 k 元 n 立方中完美匹配的哈密爾頓圈擴張性質. 具體地研究超立方中大小為線性型的匹配與大小為指數型的匹配的哈密爾頓圈擴張問題, 刻畫其中可擴成哈密爾頓圈的匹配需滿足的條件; 討論超立方中是否存在完美匹配擴張成唯一一個哈密爾頓圈; 刻畫 k 元 n 立方中不能擴張成哈密爾頓圈的完美匹配.
結題摘要
Ruskey和Savage在1993年提出了如下問題：當n＞1時，n維超立方的每一個匹配能否擴張成一個哈密爾頓圈？Kreweras猜想：當n＞1時，n維超立方的每一個完美匹配可以擴張成一個哈密爾頓圈。Fink證實了Kreweras的猜想的正確性。項目負責人在與張和平教授的合作下，從小匹配出發，用歸納和構造的方法證實了n維超立方中每一個大小不超過3n-10的匹配都可擴張成一個哈密爾頓圈。但是對其它大部分的匹配，此問題還沒有得到一個完整的解決。k元n立方是超立方的一種推廣，但是我們在研究的過程中發現，k元n立方的完美匹配不一定能擴張成哈密爾頓圈，這不同於超立方中完美匹配均可擴的結果。本項目主要研究超立方中匹配的哈密爾頓圈擴張性質和k元n立方中完美匹配的哈密爾頓圈擴張性質。本項目執行以來，已按計畫取得了多項進展，具體內容如下：(1) 討論了5維超立方中匹配擴張成哈密爾頓圈的問題，證明了5維超立方中的每一個匹配均可擴張成一個哈密爾頓圈。此結論為進一步探討一般的問題打下了基礎。(2) 通過對已知的研究成果的分析總結我們發現“超立方中每一個完美匹配可以擴張成一個哈密爾頓圈”這一性質相當美妙。那么一個自然的問題是：n維超立方中的每一個完美匹配能否擴張成多個哈密爾頓圈？我們運用遞歸構造的方法證明了當n＞3時，n維超立方中的每一個完美匹配至少可擴張成2^{2^{n-4}}個不同的哈密爾頓圈。(3) k元n立方（其中k為偶數）的完美匹配不一定能擴張成哈密爾頓圈，所以一個自然的問題是，k元n立方中的哪些完美匹配可以擴張成哈密爾頓圈？關於此問題，我們得到了如下結果：k元n立方中的每一個由同維邊構成的完美匹配可以擴張成一個哈密爾頓圈。(4) 容錯性是衡量網路穩定性的一項重要指標。通常情形下，我們希望當網路中出現部分故障時仍能保證信息數據的正常傳輸，這就要求網路具有一定的容錯能力。任意給定超立方中的一些故障邊，故障超立方中是否仍然存在無故障哈密爾頓路連線任意兩個不同顏色的點？（註：超立方是二部圖。）關於此問題，我們得到了如下結果：對n≥6，令F是n維超立方Qn中的一個故障邊集滿足|F|≤3n-11。如果Qn-F中每一個點的度都至少為2且Qn-F中至多只有一個2度點，則Qn-F中存在哈密爾頓路連線任意兩個不同顏色的點。
