本文選題：路分解 + 競(jìng)賽圖�。� 參考：《新疆大學(xué)》2017年碩士論文

【摘要】：無向圖G的一個(gè)分解就是圖G=(V(G),E(G)的邊不交子圖的集合F使得∪_(F∈F)E(F)=E(G).如果集合F的元素都是路或者圈,那么就稱它是圖G的路分解或者圈分解.另外,如果集合F的元素全部都與一個(gè)圖F同構(gòu),那么我們就稱它是圖G的F分解.Veblen[18]證明了一個(gè)圖存在圈分解當(dāng)且僅當(dāng)圖的所有頂點(diǎn)度數(shù)是偶數(shù).關(guān)于圖的分解的文章有很多,我們可以在文獻(xiàn)[3]中了解有關(guān)圖分解的定義和概念并且看到一些早期的結(jié)果.對(duì)于一個(gè)正整數(shù)k ≥ 2,圖G的Pk分解是指把G的邊集劃分成k-1長(zhǎng)路.分解的概念也可以應(yīng)用到有向圖D中,有向圖D的分解是弧不交子圖的集合.一個(gè)有向圖D的(?)分解是指把它的弧集劃分成k-1長(zhǎng)有向路.特別地,圖D的一個(gè)(?)分解就是把它的弧集劃分成有向2長(zhǎng)路.Thomassen[13-15]研究了當(dāng)k ≥ 4時(shí),圖的Pk分解.然而,有向圖(?)分解的刻畫并不被大家所了解.近期,Diwan[5]首先研究了有向圖的(?)分解.Diwan[5]刻畫了不存在(?)分解的對(duì)稱有向圖.在本文中,我們完整刻畫了存在(?)分解的競(jìng)賽圖和有向二部圖.這樣就解決了Diwan在[5]中所提出的一個(gè)問題.
[Abstract]:One decomposition of an undirected graph G is the set F of the edge disjoint subgraph of a graph G ~ (n) such that F 鈭，

本文編號(hào)：2031603