一個圖G的邊圖是指由G這樣得到的圖：節點集為G的邊集，兩節點有一條邊相連若且唯若它們所對應的邊在G中相鄰。常用L(G)表示G的邊圖。圖L(G)的邊圖稱為G的2疊邊圖，常記為L2(G)。
基本介紹
- 中文名：邊圖
- 領域：數學
- 學科：圖論
- 性質：圖
- 表示：L(G)
概念,交鄰圖,圖,圖論,
概念
一個圖G的邊圖是指由G這樣得到的圖：節點集為G的邊集，兩節點有一條邊相連若且唯若它們所對應的邊在G中相鄰。常用L(G)表示G的邊圖。圖L(G)的邊圖稱為G的2疊邊圖，常記為L2(G)。類似地，G的k疊邊圖就是指G的(k-1)疊邊圖的邊圖，常記為Lk(G)。一個圖G的團圖是指這樣的圖：以G的每個團作為節點，兩節點有一條邊相連若且唯若它們所對應的團有公共節點。G的團圖常記為cl(G)。cl(G)也稱為G的1疊團圖。G的(k-1)疊團圖的團圖稱為G的k疊團圖，常記為cl(G)，k≥2。一個圖G的塊圖是指這樣的圖：以G的每個塊作為節點，兩節點有一條邊相連若且唯若它們所對應的塊有公共節點。G的塊圖常記為B(G)。一個圖G的割點圖是指這樣的圖；以G的每一個割點作為節點，兩節點有一條邊相連若且唯若它們所對應的割點在同一塊中。G的割點圖常記為C(G)。一個圖G的塊-割點圖是指這樣的圖：以G的所有塊和所有割點組成的集合為節點集，兩節點有一條邊相連，若且唯若它們對應於一個塊和一個割點，並且這個塊含這個割點.G的塊-割點圖常記為BC(G)。一個圖G的k冪圖(k≥1)是指這樣的圖：以G的節點集為節點集，兩節點有一條邊相連，若且唯若它們對應於G的節點在G上的距離最多為k。G的k冪圖常記為G。當然，G的1冪圖就是G本身。
交鄰圖
交鄰圖是一類特殊的圖。它是由一個子集族產生的圖。設F={S1，S2，…，Sp}是由一個有限集S的p個不同的非空子集S1，S2，…，Sp組成的族.以F為節點集，節點Si和Sj有邊相連當Si∩Sj≠ ∅(i≠j)，這樣所得的圖稱為F的交鄰圖，常記為Ω(F)。以數軸上的一些區間作為節點，兩節點有一條邊相連若且唯若它們所對應的區間的交非空，這樣所得的圖稱為區間圖。區間圖還有兩種有意義的推廣。一種叫盒圖：節點集為n維立方體的集合，兩節點相鄰若且唯若它們對應的兩個立方體相交.另一種叫樹路圖：節點集為一樹上的一些路組成的集合，兩節點相鄰若且唯若它們對應的兩條路有公共部分(包括有公共端點).若將節點代表平面上一個圓的不包括二端點的弦，兩節點相鄰若且唯若它們相應的弦有一個公共點，稱這樣的圖為圓圖。
圖
圖論的研究對象。一個圖是一個集合上的一種二元關係。這個集合的元素稱為圖的節點，若兩節點之間有這種確定的二元關係，則稱有一條邊連這兩個節點。一個圖的節點的數目稱為這個圖的階;圖的邊的數目稱為它的度。在文獻中，總是將一般的圖記為G=(V，E)，其中，V=V(G)和E=E(G)分別表示G的節點集和邊集。
若有一條邊連一個圖的某兩個節點，則稱這兩個節點相鄰，並稱這兩個節點為這條邊的端點。若某一節點是某一條邊的端點，則稱這個節點和這條邊關聯。若兩條邊和同一節點關聯，則稱這兩條邊相鄰，兩個端點是同一個節點的邊稱為環。若某條邊的兩個端點不是同一個節點，且只有一條邊連這兩個節點，則稱這條邊為桿。
圖論
近年來比較活躍的數學分支之一。圖論是研究各種圖的性質和特徵的一門理論，主要包括圖與子圖、圖的連通性、可平面性、正則圖、樹、著色問題、圖的矩陣以及網路等內容。圖論的發展已有200多年的歷史。早在18世紀中葉就已出現有關圖的文字記載。這時的圖論尚處於萌芽階段，多數問題是圍繞著遊戲而產生的，最有代表性的是著名的哥尼斯堡七橋問題(相當於我國的一筆畫問題)。19世紀中葉到20世紀中葉，圖論問題大量出現，諸如哈密爾頓“繞行世界”問題，關於地圖著色的四色問題以及與之有關聯的圖的可平面性等等。在這個階段，也出現了以圖為工具去解決其他領域中一些問題的成果，例如，凱萊把圖論套用到有機化學中關於同分異構物的計數問題，克希霍夫套用樹研究電網路的分析問題等等。20世紀中葉以後，由於生產管理、軍事、交通運輸、計算機網路等方面提出的實際問題的需要，特別是許多離散性問題的出現，以及由於有了大型超高速計算機，而使大規模問題的求解成為可能，圖論及其套用的研究得到了飛速發展。這個階段的開創性工作是以福特和福克遜建立的網路流理論為代表的。圖論和線性規劃、動態規劃等最佳化理論和方法的相互滲透，促進了組合最最佳化理論和算法的研究以及圖論對實際問題的套用，與此同時也豐富了圖論的內容，使圖論的發展更加充滿活力。
