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

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

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

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

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

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

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

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

1 預(yù)備知識(shí)

定義2 通過(guò)圖（有向圖或無(wú)向圖）中所有邊一次且僅一次，行遍所有頂點(diǎn)的回路（通路），叫做歐拉回路（歐拉通路）。具有歐拉回路的圖稱作歐拉圖。

定義3 通過(guò)圖中所有頂點(diǎn)一次且僅一次的回路（通路）稱作哈密頓回路（通路）。具有哈密頓回路的圖稱作哈密頓圖。

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

圖1 超歐拉圖

2 收縮法與撕裂法的原理

2.1 收縮法原理

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

2.2 撕裂法原理

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

3 分離結(jié)合法

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

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

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

3.2 判定方法

證明：利用反證法。

3.3 判定實(shí)例

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

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

圖2 案例圖

圖3 分解圖

圖4 連接圖

4 結(jié) 論

超歐拉圖的判定是一個(gè)比較困難的問(wèn)題，很多學(xué)者對(duì)該問(wèn)題提出了一些判定方法，較好地解決了該問(wèn)題。但收縮法的關(guān)鍵在于尋找可折疊子圖，實(shí)際上可折疊子圖的判定要求太過(guò)于嚴(yán)格，而撕裂法對(duì)于復(fù)雜圖的判定太過(guò)遲緩。本文通過(guò)對(duì)這些方法的系統(tǒng)性研究，將收縮法和撕裂法結(jié)合起來(lái)提出了分離結(jié)合法，通過(guò)實(shí)例的判定說(shuō)明使用分離結(jié)合法能夠更加快速簡(jiǎn)便地判斷某些圖是否為超歐拉圖，但對(duì)于一些簡(jiǎn)單圖，如：矩形網(wǎng)格圖的判定不如撕裂法簡(jiǎn)便。所以對(duì)于不同的圖選用適合的方法更易進(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é)報(bào)(自然科學(xué)版)2003,20(1):1-4.

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

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

O157.5

A

1673-2219（2021）03-0001-02

2021-01-24

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

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

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

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