入射位置集
編輯在數學中,入射位置集或入射順序是一種部分有序的集合,代表無向圖的頂點和邊的入射關系。圖G的發生位置集對G中的每個頂點或邊都有一個元素;在這個位置集中,當且僅當x=y或x是一個頂點,y是一條邊,且x是y的一個端點時,存在一個順序關系x≤y。
入射位置集的例子
編輯舉個例子,一個具有奇數元素的人字形擺設或柵欄,具有交替的順序關系a<b>c<d...是一個路徑圖的入射擺設。
入射位置集的屬性
編輯一個非空圖的每一個入射型poset都有兩個高度。它的寬度等于邊的數量加上非循環連接部分的數量。人們特別研究了發生位置集的順序維度,以及它與底層圖的屬性的關系。當且僅當G是一個路徑圖時,連通圖G的發生位置集的順序維數最多為2,當且僅當G最多為平面時,其順序維數最多為3(Schnyder定理)。
然而,其入射位置集的階維為4的圖可能是密集的,并且可能有無界的色度數。每個在n個頂點上的完整圖,以及每個在n個頂點上的圖,都有一個階維為O(loglogn)的入射位置集。如果一個發生位置集具有高維度,那么它一定包含所有小樹的發生位置集的副本,或者作為子序或者作為子序的對偶。
內容由匿名用戶提供,本內容不代表www.gelinmeiz.com立場,內容投訴舉報請聯系www.gelinmeiz.com客服。如若轉載,請注明出處:http://www.gelinmeiz.com/164570/