因子覆蓋圖(factor covered graph)是一類特殊的圖。指每一條邊都在同一種因子之中的圖。若圖中的每一條邊都包含在某個1因子之中，則稱G為1因子覆蓋圖。G的節點v稱為完全覆蓋點，若v的每條與之關聯的邊均有G的一個1因子包含它。
基本介紹
- 中文名：因子覆蓋圖
- 外文名：factor covered graph
- 領域：數學
- 學科：圖論
- 性質：每一條邊都在同一因子
- 相關圖：覆蓋圖、部圖
概念,圖,子圖,部圖,圖論,覆蓋圖,
概念
因子覆蓋圖(factor covered graph)是一類特殊的圖。指每一條邊都在同一種因子之中的圖。若圖中的每一條邊都包含在某個1因子之中，則稱G為1因子覆蓋圖。G的節點v稱為完全覆蓋點，若v的每條與之關聯的邊均有G的一個1因子包含它。
圖
圖的定義是隨著圖論的發展而逐步推廣的。最初圖被直觀描述為：所謂圖就是一些點和連線點的邊所構成的圖形。以後將此描述嚴格定義為：
定義1 給定非空集合V，E是V的若干二元子集做成的集合，則G=(V，E)稱為一個圖。V中每一元素叫做圖G的結點，E中每一元素(即V中某個二元子集) {a，b}稱為圖G中連線結點a和b的邊，結點a和b稱為鄰接的。
這樣定義的圖現在稱為簡單圖，因為在這些圖中每兩個點最多只能有一條邊連線，且任何結點到自身沒有邊連線。隨著生產實踐的發展，更廣泛的一類圖被引入。
定義2 V為一個非空集合，E為任意集合，ᵠ為E到V中無序偶對集合上的函式，則G=(V，E，ᵠ)稱為一個圖。V中的元素稱為圖G的結點。對任何e∈E，若ᵠ(e)={a，b}，則e稱為圖G中連結a，b兩點的邊。
顯然，這樣定義的圖兩結點間可以有不止一條邊，且結點到自身也可以有邊連線。若兩結點間有不止一條邊連線，則這些邊稱為平行邊。對應於簡單圖，具有平行邊的圖有時也稱為多重圖。
後來，圖的定義又得到進一步的推廣，引入所謂方向的概念，即給每一條邊賦予一個方向。
定義3 V為非空集合，E為任意集合，ᵠ為E到V×V的函式，則G=(V，E，ᵠ)稱為一個圖。對任意e∈E，若ᵠ(e)= (a，b)，則e稱為圖G中從a到b的有向邊，a稱為e的始點，b稱為e的終點。
隨著圖論的發展，由實際問題抽象出來的圖中結點和邊上往往都帶有信息，因此又引入賦數圖的概念。所謂賦數圖是一個三重組 (V，E，g)或四重組(V，E，f，g)，其中V是結點集合，E是邊的集合，f是定義在V上的函式，g是定義在E上的函式。對任何υ∈V，e∈E，f(υ)，g(e)分別稱為點υ和邊e上的數。
子圖
圖論的基本概念之一。指節點集和邊集分別是某一圖的節點集的子集和邊集的子集的圖。若這個節點子集或邊子集是真子集，則稱這個子圖為真子圖。若圖G的每一個節點也是它的子圖H的節點，則稱H是G的支撐子圖。設S是V(G)的子集，以S為節點集，以G的所有那些兩端點都在S內的邊組成邊集，所得到的G的子圖稱為S在G中的導出子圖，或更確切地，節點導出子圖。設B是E(G)的子集，由G的所有與B內至少有一條邊關聯的節點組成節點集，以B為邊集，所得到的G的子圖稱為B在G中的邊導出子圖。對於某種性質P，若一個圖的具有P的子圖不是任何具有P的子圖的真子圖，則稱它為具有P的極大子圖。在所有極大子圖中，邊數最多的那個稱為最大子圖。
部圖
一類特殊的圖。即一個圖的節點集可分成若干個子集，使得每一條邊的兩端點不在同一子集內。若一個圖的節點集能分成k個兩兩不交的非空子集，使得這個圖的每一條邊的兩端點不在同一個子集內，則稱這個圖為k部圖。若k=2，則稱這種k部圖為二部圖；若k=3，則稱這種k部圖為三部圖。若在一個k部圖中，任一節點與其他部的所有節點都相鄰，則稱它為完全k部圖。
圖論
近年來比較活躍的數學分支之一。圖論是研究各種圖的性質和特徵的一門理論，主要包括圖與子圖、圖的連通性、可平面性、正則圖、樹、著色問題、圖的矩陣以及網路等內容。圖論的發展已有200多年的歷史。早在18世紀中葉就已出現有關圖的文字記載。這時的圖論尚處於萌芽階段，多數問題是圍繞著遊戲而產生的，最有代表性的是著名的哥尼斯堡七橋問題(相當於我國的一筆畫問題)。19世紀中葉到20世紀中葉，圖論問題大量出現，諸如哈密爾頓“繞行世界”問題，關於地圖著色的四色問題以及與之有關聯的圖的可平面性等等。在這個階段，也出現了以圖為工具去解決其他領域中一些問題的成果，例如，凱萊把圖論套用到有機化學中關於同分異構物的計數問題，克希霍夫套用樹研究電網路的分析問題等等。20世紀中葉以後，由於生產管理、軍事、交通運輸、計算機網路等方面提出的實際問題的需要，特別是許多離散性問題的出現，以及由於有了大型超高速計算機，而使大規模問題的求解成為可能，圖論及其套用的研究得到了飛速發展。這個階段的開創性工作是以福特和福克遜建立的網路流理論為代表的。圖論和線性規劃、動態規劃等最佳化理論和方法的相互滲透，促進了組合最最佳化理論和算法的研究以及圖論對實際問題的套用，與此同時也豐富了圖論的內容，使圖論的發展更加充滿活力。
覆蓋圖
覆蓋圖是一類重要的圖。它是從一個圖派生的圖。對圖G的每一條邊(u，v)給出兩個側[u，v)(即含u而不含v)和[v，u)(即含v而不含u)。記S(G)為G的所有邊的兩側組成的集合。對於群Γ，G上的一個Γ鏈是從S(G)到Γ的一個函式φ，對G的所有側[u，v)，滿足：φ[u，v)=(φ[v，u))。
對給定的圖G的Γ鏈φ，G的覆蓋圖G~：其頂點集為Γ×V(G)；兩頂點(a，v)，(b，u)相鄰若且唯若[v，u)∈S(G)且b=aφ[v，u)。例如，Γ={0，1}，G=K3，即3階的完全圖。G~如下圖所示。在K3中邊旁之兩數字給出φ的值。
