超歐拉圖及相關(guān)問題性質(zhì)研究.pdf

1、歐拉圖是可以從圖中的任意一點(diǎn)出發(fā)，經(jīng)過圖中的每條邊正好一次，最后返回起點(diǎn)的圖。歐拉圖問題是圖論的邊行遍性問題中的一個基本問題。超歐拉圖是存在歐拉生成子圖的圖，也可以定義為含生成閉跡的圖。超歐拉圖問題也是圖論研究中一個非常重要的問題，該問題研究的主要目的在于實(shí)際生產(chǎn)的安排過程中，通過判定某個給定圖是否為歐拉圖，從而決定后續(xù)基于歐拉圖的優(yōu)化算法是否可行。
　　本文主要工作包括：
　　1．回顧了可折疊圖和超歐拉圖的歷史背景、基本概

2、念、發(fā)展現(xiàn)狀，介紹了超歐拉圖的主要研究方向，相關(guān)問題和本課題的研究意義。
　　2．從圖解序列，收縮操作，簡化圖，可折疊圖和歐拉生成子圖的定義、相關(guān)性質(zhì)以及圖與度序列的關(guān)系入手，借鑒判定某個圖的度序列是否可圖解的經(jīng)典方法，對可折疊圖解序列和超歐拉圖解序列逐步深入討論，最后給出判定某個給定的圖解序列是否為可折疊圖解序列或超歐拉圖解序列的充分條件，并給出了相應(yīng)證明。
　　3．對于r≥0，r-超歐拉圖是指在圖G中對于任意的X∈E(G

3、)滿足|X|≤r，G都有歐拉生成子圖H，使得|X|∈E|H|。類似的，可以定義r-歐拉連通圖，強(qiáng)r-歐拉連通圖和r-邊歐拉連通圖。本文分析了使k-邊連通圖必定是r-超歐拉圖的k的最小取值的研究思路，總結(jié)其方法并加以推廣，研究了使k-邊連通圖必定為上述3種歐拉連通圖的k的最小取值，并根據(jù)r的取值范圍不同進(jìn)行劃分，分別確定了k值。
　　4. Catlin提出的用收縮法判定超歐拉圖在理論證明中效果很好，但在判定具體圖時卻不易操作。本文在