主題
Search

構型


“構型”一詞有時用於描述點的有限集合 p=(p_1,...,p_n)p_i in R^d,其中 R^d 是一個 歐幾里得空間

術語“構型”也用於描述具有以下性質的有限關聯結構 (v_r,b_k) (Gropp 1992)。

1. 有 v 個點和 b 條線。

2. 每條線上有 k 個點,每個點穿過 r 條線。

3. 兩條不同的線最多 相交 一次,並且兩個不同的點最多由一條線連線一次。

條件

 vr=bk
 v>=r(k-1)+1

是構型存在的 必要 條件。對於 k=3,這些條件也是 充分 的,而對於 k=4,情況可能也是如此 (Gropp 1992)。必要條件成立,但不存在 22_5。對於 k=6 和 7,上述條件不是 充分 的,如階數為 6 的仿射射影平面所示 (36_7, 42_6) 和射影平面 (43_7,43_7)

構型是最古老的組合結構之一,由 T. Reye 於 1876 年定義。一個 r-正則圖 可以被視為一個構型 (v_r,b_2),透過將節點與點關聯,並將邊與線關聯。

一個對稱構型 n_k=(n_k,n_k)n 條線和 n 個點組成,排列方式使得 k 條線穿過每個點,並且每條線上有 k 個點。所有對稱 n_3 構型對於 n<=18 都是已知的 (Betten et al. 2000)。7_3, 8_3, 9_3, ... 構型的數量分別為 1, 1, 3, 10, 31, 229, 2036, 21399, 245342, ...,糾正了 von Sterneck 對於 12_3 的錯誤 (OEIS A001403; Sterneck 1894, 1895; Wells 1991, p. 72; Colbourn and Dinitz 1996; Gropp 1997; Hilbert and Cohn-Vossen 1999)。

FanoPlane

法諾平面,其中中心點對應於 無窮遠點,是唯一的 7_3 構型。它可以在階數為 2 的 伽羅瓦域 GF(2) 上實現,但不能在實數或有理數上實現 (Gropp 1997)。不存在使用所有有限距離點的 7_3 構型 (Wells 1986, p. 75)。

Moebius-KantorConfiguration

不存在使用所有有限距離點的 8_3 構型 (Wells 1986, p. 75),但存在一個具有 無窮遠點 的構型 (Kantor 1891)。這被稱為 莫比烏斯-康托爾構型 (Pisanski 和 Randić 2000)。

Configurations9-3

Kantor (1891) 表明存在三個 9_3 構型,其中 帕普斯構型(左圖)是其中之一 (Coxeter 1950; Wells 1986, p. 75)。另外兩個由嵌入的 等邊三角形 組成 (Wells 1991, pp. 159-160)。

DesarguesConfiguration

Kantor (1881) 證明恰好存在 10 個 10_3 構型,其中 德扎格構型(如上圖所示)是其中之一。然而,雖然在論文中沒有明確評論,但 Kantor 的 (10_3)_4 包含一條由兩個方向略有不同的線段組成的線。Schroeter (1889) 隨後證明,這些構型中恰好有一個不能在實平面或有理平面中繪製 (Gropp 1997)。

存在 31 個 11_3 構型 (Gropp 1997),由 Martinetti (1887) 使用遞迴構造方法構建,隨後由 Daublebsky von Sterneck (1895) 在平面上實現,儘管所有構型都可實現的證明直到 Sturmfels 和 White (1990) 的工作才出現。Page 和 Dorwart (1984) 討論了 31 個 11_3 構型 (Wells 1991, p. 63)。

存在 229 個 12_3 構型,其中 228 個已由 Daublebsky von Sterneck (1895) 發現,直到 Gropp (1991) 的工作才找到缺失的一個。12_3 構型之一有時被稱為 考克斯特構型,儘管根據其 Levi 圖(即 諾魯圖)將其稱為 諾魯構型 可能更好。Crapo et al. (1988) 的附錄中出現了所有 11_312_3 構型的實現座標。

考克斯特構型 是一個 28_3 構型,其 Levi 圖福斯特圖 F_(056)C

CremonaRichmondConfig

克雷莫納-里士滿構型(如上圖所示)是 245342 個 15_3 構型之一。

存在一個稱為 考克斯構型(2^(d-1))_d 構型。

下表總結了一些命名構型的 Levi 圖


另請參閱

考克斯構型, 考克斯特構型, 克雷莫納-里士滿構型, 丹澤爾構型, 德扎格構型, 德斯米克構型, 雙六, 等邊三角形, 歐幾里得空間, 法諾平面, 框架, 圖條, 格林鮑姆-裡格比構型, Levi 圖, 莫比烏斯-康托爾構型, 果園種植問題, 普通線圖, 定向擬陣, 帕普斯六邊形定理, 射影平面, 正則圖, 雷耶構型, 剛性圖, 張拉整體, 超立方體

使用 探索

參考文獻

Betten, A; Brinkmann, G.; 和 Pisanski, T "Counting Symmetric Configurations v_3." Disc. Appl. Math. 99, 331-338, 2000.Bokowski, J. 和 Sturmfels, B. Computational Synthetic Geometry. Berlin: Springer-Verlag, p. 41, 1988.Colbourn, C. J. 和 Dinitz, J. H. (Eds.). CRC Handbook of Combinatorial Designs. Boca Raton, FL: CRC Press, p. 255, 1996.Coxeter, H. S. M. "Self-Dual Configurations and Regular Graphs." Bull. Amer. Math. Soc. 56, 413-455, 1950.Crapo, H.; Havel, T.; Sturmfels, B.; Whiteley, W.; 和 White, N. "Symbolic Computations in Geometry." IMA Preprint No. 389. University of Minnesota, 1988.Daublebsky von Sterneck, R. "Die Configuration 11_3." Monatshefte f. Math. Phys. 5, 325-331, 1894.Daublebsky von Sterneck, R. "Die Configurationen 12_3." Monatshefte f. Math. Phys. 6, 223-255, 1895.Gropp, H. "Configurations and the Tutte Conjecture." Ars. Combin. A 29, 171-177, 1990a.Gropp, H. "On the History of Configurations." Conference San Sebastien (Spain). Sept. 1990b.Gropp, H. "Configurations and Steiner systems S(2,4,25) II--Trojan Configurations n_3." In Combinatorics '88, Research and Lecture Notes in Mathematics (Ed. A. Barlotti et al. ) Rende, Italy: Mediterranean Press, pp. 425-435, 1991.Gropp, H. "Enumeration of Regular Graphs 100 Years Ago." Discrete Math. 101, 73-85, 1992.Gropp, H. "Non-Symmetric Configurations with Deficiencies 1 and 2." Combinatorics '90. Recent Trends and Applications. Proceedings of the International Conference Held in Gaeta, May 20-27, 1990 (Ed. A. Barlotti, A. Bichera, P. V. Ceccherini, 和 G. Tallini). Amsterdam, Netherlands: North-Holland, pp. 227-239, 1992.Gropp, H. "Configurations and Their Realization." Discr. Math. 174, 137-151, 1997.Grünbaum, B. Configurations of Points and Lines. Providence, RI: Amer. Math. Soc., 2009.Hilbert, D. 和 Cohn-Vossen, S. Geometry and the Imagination. New York: Chelsea, 1999.Kantor, S. "Die Configurationen (3,3)_10." Sitzungsber. Akad. Wiss. Wien Math.-Natur. Kl, 84, 1291-1314, 1881.Martinetti, V. "Sulle configurazioni piane mu_3." Ann. Mat. Pura Appl. 15, 1-26, 1887.Page, W. 和 Dorwart, H. L. "Numerical Patterns and Geometrical Configurations." Math. Mag. 57, 82-92, 1984.Pisanski, T. 和 Randić, M. "Bridges between Geometry and Graph Theory." In Geometry at Work: A Collection of Papers Showing Applications of Geometry (Ed. C. A. Gorini). Washington, DC: Math. Assoc. Amer., pp. 174-194, 2000.Schroeter, H. "Üner die Bildungsweise und geometrische Konstruction der Konfigurationen 10_3.. Nachr. Ges. Wiss. Göttingen, 193-236, 1889.Sloane, N. J. A. Sequence A001403 in "The On-Line Encyclopedia of Integer Sequences."Sturmfels, B. 和 White, N. "All 11_3 and 12_3 Configurations are Rational." Aeq. Math. 39, 254-260, 1990.Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England: Penguin Books, p. 75, 1986.Wells, D. The Penguin Dictionary of Curious and Interesting Geometry. London: Penguin, pp. 63 和 159-160, 1991.

請引用為

Weisstein, Eric W. “構型。” 來自 --一個 資源。 https://mathworld.tw/Configuration.html

主題分類