關(guān)于判定超歐拉圖的分離結(jié)合法

陳宇龍 張 林 韋美雁 潘學(xué)文

關(guān)于判定超歐拉圖的分離結(jié)合法

陳宇龍 張 林 韋美雁 潘學(xué)文

（湖南科技學(xué)院 電子與信息工程學(xué)院，湖南 永州 425199）

本文基于判定超歐拉圖的收縮法和撕裂法，將兩種方法進(jìn)行了結(jié)合改進(jìn)，提出一種新的超歐拉圖的判定方法——分離結(jié)合法，并進(jìn)行了實例判定。

超歐拉圖；分離結(jié)合法；收縮；分裂

判定一個圖是否是超歐拉圖的方法最早為Catlin在1988年提出的收縮法[2]。收縮法的關(guān)鍵是找到有效的可折疊子圖，但是在實際中對于可折疊子圖的尋找十分不容易。鑒于此，我國的學(xué)者李登信提出次可折疊子圖，即添加邊數(shù)的方法來判定超歐拉圖[3,4]。李霄民提出了撕裂法[5]，即給出圖的頂點的一種變換，變換保持圖的頂點數(shù)不變，但邊數(shù)減少；并且給出變換后的圖與原圖的超歐拉性的關(guān)系，從而通過變換后的圖的超歐拉性導(dǎo)出原圖的超歐拉性。本文考慮將兩種方法進(jìn)行結(jié)合改進(jìn)，提出一種新的超超歐拉圖的判定方法，把圖分離成兩部分，對一部分進(jìn)行收縮，對另一部分進(jìn)行撕裂，得到兩個子圖，然后連接兩個子圖，并引進(jìn)哈密頓圖的概念，實現(xiàn)更加快速地判定超歐拉圖。我們把這種方法稱為分離結(jié)合法。

1 預(yù)備知識

定義2 通過圖（有向圖或無向圖）中所有邊一次且僅一次，行遍所有頂點的回路（通路），叫做歐拉回路（歐拉通路）。具有歐拉回路的圖稱作歐拉圖。

定義3 通過圖中所有頂點一次且僅一次的回路（通路）稱作哈密頓回路（通路）。具有哈密頓回路的圖稱作哈密頓圖。

定義4 超歐拉圖是指具有歐拉生成子圖的圖。如圖1所示，黑邊為其歐拉生成子圖。

圖1 超歐拉圖

2 收縮法與撕裂法的原理

2.1 收縮法原理

收縮法的主要方法是找到一個比原圖簡單的可折疊子圖。通過對收縮后獲得的圖的超歐拉性來引導(dǎo)出原圖的超歐拉性，收縮法的核心在于找出可折疊子圖。收縮法的判定方法及實例在文獻(xiàn)[3]和文獻(xiàn)[4]中有詳細(xì)的介紹，本文不再表述。

2.2 撕裂法原理

撕裂法是給出圖的頂點的一種變換，變換保持圖的頂點數(shù)不變，但邊數(shù)減少；并且給出原圖與變換后的圖的超歐拉性的關(guān)系，從而通過變換后的圖的超歐拉性導(dǎo)出原圖的超歐拉性。撕裂法的判定方法及實例在文獻(xiàn)[5]中有詳細(xì)的介紹，本文不再表述。

3 分離結(jié)合法

收縮法一是在可折疊子圖的判定上要求太過于嚴(yán)格，二是對簡化圖的超歐拉性的判定沒有涉及。而撕裂法可用于簡化圖的超歐拉的判定。本文考慮將兩種方法結(jié)合，提高判定方法的適用性，提出一種新的方法：分離結(jié)合法。

3.1 分離結(jié)合法原理

假設(shè)圖G，K是圖G的一個子圖，把圖K分離成兩部分，結(jié)合文中收縮法和撕裂法，對一部分進(jìn)行收縮，對另一部分進(jìn)行撕裂，得到兩個子圖，然后連接兩個子圖，并引進(jìn)哈密頓圖的概念，實現(xiàn)更加快速地判定超歐拉圖。

3.2 判定方法

證明：利用反證法。

3.3 判定實例

給定案例圖，如圖2，現(xiàn)對其進(jìn)行分離結(jié)合。

將圖分為兩部分，如圖3所示，對左部分圖進(jìn)行撕裂，對右部分圖進(jìn)行收縮，重新連接得到圖4(a)，繼續(xù)撕裂直到任意頂點的度數(shù)不大于3。如圖4(b)所示。

圖2 案例圖

圖3 分解圖

圖4 連接圖

4 結(jié) 論

超歐拉圖的判定是一個比較困難的問題，很多學(xué)者對該問題提出了一些判定方法，較好地解決了該問題。但收縮法的關(guān)鍵在于尋找可折疊子圖，實際上可折疊子圖的判定要求太過于嚴(yán)格，而撕裂法對于復(fù)雜圖的判定太過遲緩。本文通過對這些方法的系統(tǒng)性研究，將收縮法和撕裂法結(jié)合起來提出了分離結(jié)合法，通過實例的判定說明使用分離結(jié)合法能夠更加快速簡便地判斷某些圖是否為超歐拉圖，但對于一些簡單圖，如：矩形網(wǎng)格圖的判定不如撕裂法簡便。所以對于不同的圖選用適合的方法更易進(jìn)行判定是否為超歐拉圖。

[1]F.T.Boesch, C.Suffel, R.Tindell. The spaning subgraph of eulerian graphs[J].J.Graph Theory,1977(1):79-84.

[2]Catlin P A. A reduction method to find spanning Eulerian subgraphs[J]. J.Graph Theory,1988,12(1):29-45.

[3]李登信,王斌,李霄民.關(guān)于判定超歐拉圖的收縮法[J].重慶工商大學(xué)學(xué)報(自然科學(xué)版)2003,20(1):1-4.

[4]李登信,王斌. 超歐拉圖的判定及Catlin-猜想的研究[J].西南師范大學(xué)學(xué)報(自然科學(xué)版)2003(1):6-8.

[5]李霄民.判定超歐拉圖的一個新方法[J].西南大學(xué)學(xué)報(自然科學(xué)版)2007,29(4):41-43

O157.5

A

1673-2219（2021）03-0001-02

2021-01-24

湖南科技學(xué)院應(yīng)用特色學(xué)科建設(shè)項目；湖南省教育廳2020教學(xué)改革項目(項目編號HNJG-2020-0879)。

陳宇龍（2000－），男，湖南長沙人，湖南科技學(xué)院軟件工程專業(yè)2018級學(xué)生。

韋美雁（1974－），女，湖南永州人，碩士，副教授，研究方向為數(shù)據(jù)庫與大數(shù)據(jù)技術(shù)、人工智能。

（責(zé)任編校：文春生）