擬可分圖(quasi-separable graph)是一類特殊的圖。圖論是研究各種圖的性質和特徵的一門理論，主要包括圖與子圖、圖的連通性、可平面性、正則圖、樹、著色問題、圖的矩陣以及網路等內容。圖的定義是隨著圖論的發展而逐步推廣的。最初圖被直觀描述為：所謂圖就是一些點和連線點的邊所構成的圖形。
基本介紹
- 中文名：擬可分圖
- 外文名：quasi-separable graph
- 領域：數學
- 學科：圖論
- 性質：一類特殊的圖
- 定義：具有某種可分離性的圖
概念,圖論,圖,子圖,完全圖,
概念
擬可分圖是一類特殊的圖。它是具有某種可分離性的圖。若圖G中存在一個頂點子集K，K的導出子圖為一完全圖，且去掉這個子集K後的圖變為不連通的，則稱圖G為擬可分圖。當|K|=0或1時，分別為不連通圖或可分圖。
圖論
近年來比較活躍的數學分支之一。圖論是研究各種圖的性質和特徵的一門理論，主要包括圖與子圖、圖的連通性、可平面性、正則圖、樹、著色問題、圖的矩陣以及網路等內容。圖論的發展已有200多年的歷史。早在18世紀中葉就已出現有關圖的文字記載。這時的圖論尚處於萌芽階段，多數問題是圍繞著遊戲而產生的，最有代表性的是著名的哥尼斯堡七橋問題(相當於我國的一筆畫問題)。19世紀中葉到20世紀中葉，圖論問題大量出現，諸如哈密爾頓“繞行世界”問題，關於地圖著色的四色問題以及與之有關聯的圖的可平面性等等。在這個階段，也出現了以圖為工具去解決其他領域中一些問題的成果，例如，凱萊把圖論套用到有機化學中關於同分異構物的計數問題，克希霍夫套用樹研究電網路的分析問題等等。20世紀中葉以後，由於生產管理、軍事、交通運輸、計算機網路等方面提出的實際問題的需要，特別是許多離散性問題的出現，以及由於有了大型超高速計算機，而使大規模問題的求解成為可能，圖論及其套用的研究得到了飛速發展。這個階段的開創性工作是以福特和福克遜建立的網路流理論為代表的。圖論和線性規劃、動態規劃等最佳化理論和方法的相互滲透，促進了組合最最佳化理論和算法的研究以及圖論對實際問題的套用，與此同時也豐富了圖論的內容，使圖論的發展更加充滿活力。
圖
圖的定義是隨著圖論的發展而逐步推廣的。最初圖被直觀描述為：所謂圖就是一些點和連線點的邊所構成的圖形。以後將此描述嚴格定義為：
定義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的極大子圖。在所有極大子圖中，邊數最多的那個稱為最大子圖。
完全圖
在圖論的數學領域，完全圖是一個簡單的無向圖，其中每對不同的頂點之間都恰連有一條邊相連。完整的有向圖又是一個有向圖，其中每對不同的頂點通過一對唯一的邊緣（每個方向一個）連線。n個端點的完全圖有n個端點以及n(n − 1) / 2條邊，以Kn表示。它是(k − 1)-正則圖。所有完全圖都是它本身的團（clique）。
圖形理論本身以萊昂哈德歐拉於1736年在Königsberg七橋的工作開始。 然而，完全圖的繪圖，其頂點放置在正多邊形的點上，已經在13世紀中出現。這樣的繪畫有時被稱為神秘玫瑰。
在圖論的數學領域，完全圖是一個簡單的無向圖，其中每對不同的頂點之間都恰連有一條邊相連。完整的有向圖又是一個有向圖，其中每對不同的頂點通過一對唯一的邊緣（每個方向一個）連線。n個端點的完全圖有n個端點以及n(n − 1) / 2條邊，以Kn表示。它是(k − 1)-正則圖。所有完全圖都是它本身的團（clique）。
圖形理論本身以萊昂哈德歐拉於1736年在Königsberg七橋的工作開始。 然而，完全圖的繪圖，其頂點放置在正多邊形的點上，已經在13世紀中出現。這樣的繪畫有時被稱為神秘玫瑰。
