密集圖
在數學中，一個密集的圖是一個圖形，其中邊緣數接近最大邊數（每對頂點都通過一個邊連接）。相反的圖形只有幾個邊，是稀疏圖。構成密集圖或稀疏圖的區別是不確定的，通常以“大致等於”的陳述表示。因此，定義密度的方式通常取決於問題的上下文。
簡單圖的圖密度定義為邊數|的比例。 E |關於最大可能的邊緣。
對於無方向的簡單圖，圖密度為：
對於有針對性的簡單圖，最大可能的邊緣是無向圖的兩倍（因為有兩個方向到邊緣），因此密度為：
其中e是邊緣的數量， v是圖中的頂點數。無向圖的最大邊數為
對於增加尺寸的圖形家庭，如果
上密度
上密度是從有限圖到無限圖的上面定義的圖密度概念的擴展。直觀地，無限圖具有任意較大的有限子圖，任何密度都小於其上部密度，並且沒有密度大於其上部密度的任意有限的子圖。形式上，圖G的上部密度是值α的最大值，因此，具有密度α的G的有限亞圖具有界數的頂點。可以使用ERDőS -STONDER定理表明，上部密度僅能是1或超級比率0， 1 / 2、2 / 3、3 / 4、4 / 5 ， … n / n + 1 （請參閱，例如，diestel，第5版，第189頁）。
稀疏的圖形
Lee＆Streinu（2008）和Streinu＆Theran（2009）將圖定義為（ k ， l ） -sparse，如果每個n位具有n個頂點的每個非空的子圖最多都具有kn -l邊緣，以及（k， l） - 如果是（ k ， l ） -為（ k ， l ） -sparse，具有kn -l邊緣。因此，樹正好是（1,1） - 圖形，森林正好是（1,1） -sparse圖，而具有樹木的圖形恰好是（ k ， k ） -sparse圖。偽索恰好是（1,0） -sparse圖，而在剛性理論中產生的Laman圖正是（2,3） - –圖形圖。
其他未出於其稀疏性特徵的圖形家庭也可以通過這種方式描述。例如，任何具有N頂點的平面圖最多具有3 n - 6個邊緣（除了少於3個頂點的圖），並且平面圖的任何子圖都是平面的事實，同時均表示平面圖（3 ，6） -sparse 。但是，並非每個（3,6） -sparse圖是平面。同樣，外平面圖為（2,3） -sparse和平面兩分圖為（2,4） -sparse。
Streinu和Theran表明，當K和L為整數並且0≤l <2 k時，可以在多項式時間內進行測試（ K ， L ） -Sparsity。
對於圖族， K和L的存在的存在使得家族中的圖（ k ， l ） -sparse等同於具有有界變性或具有界限的家族中的圖形。更確切地說，這是從納什·威廉姆斯（Nash -Williams，1964）的結果中得出的，最多是A的圖形恰好是（ a ， a ） -sparse圖。同樣，大多數d的變性圖是
稀疏和密集的圖形類
Nešet松和Ossona de Mendez（2010）認為，稀疏/密度二分法必須考慮無限的圖形類別而不是單個圖形實例。他們將某個地方的圖形類定義為存在閾值t的圖形類別，以使每個完整的圖在類中圖中顯示為t -subdivision。相反，如果不存在這樣的閾值，則班級無處可聞。在Nešet松和Ossona de Mendez（2012）中討論了無處濃密與密集二分法的特性。
具有有界變性且無處濃密圖的圖形類別都包含在Biclique-for-for-fir graphs中，圖形家族將某些完整的兩分圖表排除為子圖（ Telle＆Villanger 2012 ）。