基本介紹
- 中文名：距離正則圖
- 外文名：distance-regular graph
- 領域：數學
- 學科：圖論
- 定義：與結合方案有關的圖
- 對象：連通圖
概念,圖論,圖,正則圖,連通圖,
概念
距離正則圖(distance-regular graph)是一類與結合方案有關的圖。設Γ是一個連通圖，有v個頂點，無環邊及重邊。Γ中兩頂點間的距離是連結這兩點的最短路所含的邊數。Γ中任意兩個頂點之間距離的最大值稱為Γ的直徑。若對Γ中距離為k的任意兩個頂點x，y，與x的距離為i且與y的距離為j的頂點z的個數是一個常數Cijk，與x，y的選擇無關，則稱Γ為距離正則圖。直徑為2的距離正則圖稱為強正則圖。
圖論
近年來比較活躍的數學分支之一。圖論是研究各種圖的性質和特徵的一門理論，主要包括圖與子圖、圖的連通性、可平面性、正則圖、樹、著色問題、圖的矩陣以及網路等內容。圖論的發展已有200多年的歷史。早在18世紀中葉就已出現有關圖的文字記載。這時的圖論尚處於萌芽階段，多數問題是圍繞著遊戲而產生的，最有代表性的是著名的哥尼斯堡七橋問題(相當於我國的一筆畫問題)。19世紀中葉到20世紀中葉，圖論問題大量出現，諸如哈密爾頓“繞行世界”問題，關於地圖著色的四色問題以及與之有關聯的圖的可平面性等等。在這個階段，也出現了以圖為工具去解決其他領域中一些問題的成果，例如，凱萊把圖論套用到有機化學中關於同分異構物的計數問題，克希霍夫套用樹研究電網路的分析問題等等。20世紀中葉以後，由於生產管理、軍事、交通運輸、計算機網路等方面提出的實際問題的需要，特別是許多離散性問題的出現，以及由於有了大型超高速計算機，而使大規模問題的求解成為可能，圖論及其套用的研究得到了飛速發展。這個階段的開創性工作是以福特和福克遜建立的網路流理論為代表的。圖論和線性規劃、動態規劃等最佳化理論和方法的相互滲透，促進了組合最最佳化理論和算法的研究以及圖論對實際問題的套用，與此同時也豐富了圖論的內容，使圖論的發展更加充滿活力。
圖
圖論的研究對象。一個圖是一個集合上的一種二元關係。這個集合的元素稱為圖的節點，若兩節點之間有這種確定的二元關係，則稱有一條邊連這兩個節點。一個圖的節點的數目稱為這個圖的階；圖的邊的數目稱為它的度。在文獻中，總是將一般的圖記為G=(V，E)，其中，V=V(G)和E=E(G)分別表示G的節點集和邊集。
若有一條邊連一個圖的某兩個節點，則稱這兩個節點相鄰，並稱這兩個節點為這條邊的端點。若某一節點是某一條邊的端點，則稱這個節點和這條邊關聯。若兩條邊和同一節點關聯，則稱這兩條邊相鄰，兩個端點是同一個節點的邊稱為環。若某條邊的兩個端點不是同一個節點，且只有一條邊連這兩個節點，則稱這條邊為桿。
只有一個節點而沒有邊的圖稱為平凡圖。沒有邊的圖稱為孤立圖。以某兩節點為端點的邊可能不止一條，這時稱連這兩個節點的邊為重邊。既可以有環，也可以有重邊的圖稱為準圖；沒有環而可能有重邊的圖稱為帶重圖；沒有重邊而可能有環的圖稱為帶環圖；既沒有重邊也沒有環的圖稱為簡單圖。若一個圖的階是有限的，則稱這個圖為有限圖，否則稱這個圖為無限圖。每兩個節點都相鄰的簡單圖稱為完全圖。若一個n階圖的節點用1，2，…，n來代表，則稱它為標定圖。若在圖的每一條邊上賦以一個實數或者對於每個節點賦以一個實數，則稱它為賦權圖。
正則圖
正則圖是一類特殊的圖。指所有節點的次都相同的圖。節點的次為k的正則圖稱為k正則圖。一個圖上某一條邊的次是指這個圖上與這條邊有公共端點的邊的數目。所有邊的次都相同的圖稱為邊正則圖。對於一個圖，若存在正整數k，λ，μ，使得下列條件成立，則稱該圖為強正則圖：
1.G是k正則圖。
2.對於圖上任意兩個不同節點v和w，若v和w相鄰，則G上與v和w都相鄰的節點的數目是λ，否則，G上與v和w都相鄰的節點的數目是μ。
3.正則圖是指所有節點的次都是3的圖。每個連通片不是圈就是二階完全圖，即由一條桿組成的圖，稱為一個半正則圖。
連通圖
在圖論中，連通圖基於連通的概念。在一個無向圖G 中，若從頂點vi到頂點vj有路徑相連（當然從vj到vi也一定有路徑），則稱vi和vj是連通的。如果 G 是有向圖，那么連線vi和vj的路徑中所有的邊都必須同向。如果圖中任意兩點都是連通的，那么圖被稱作連通圖。如果此圖是有向圖，則稱為強連通圖（注意：需要雙向都有路徑）。圖的連通性是圖的基本性質。
對一個圖G=(V,E) 中的兩點x和y，若存在交替的頂點和邊的序列：
Γ=(x=v0-e1-v1-e2-...-ek-(vk+1)=y) (在有向圖中要求有向邊vi−(vi+1)屬於E)，則兩點x和y是連通的。Γ是一條x到y的連通路徑，x和y分別是起點和終點。當x=y時，Γ 被稱為迴路。如果通路 Γ 中的邊兩兩不同，則 Γ 是一條簡單通路，否則為一條複雜通路。如果圖G中每兩點間皆連通，則G是連通圖。
強連通圖：有向圖G=(V,E) 中，若對於V中任意兩個不同的頂點x和y，都存在從x到y以及從y到x的路徑，則稱G是強連通圖。相應地有強連通分量的概念。強連通圖只有一個強連通分量，即是其自身；非強連通的有向圖有多個強連分量。
弱連通圖：將有向圖的所有的有向邊替換為無向邊，所得到的圖稱為原圖的基圖。如果一個有向圖的基圖是連通圖，則有向圖是弱連通圖。
初級通路：通路中所有的頂點互不相同。初級通路必為簡單通路，但反之不真。
