交叉數（圖理論）
在圖理論中，圖G的交叉數Cr（ g ）是圖G的平面圖的最低邊交叉數。例如，當且僅當其交叉數為零時，圖是平面。在圖形圖中，確定交叉數仍然非常重要，因為用戶研究表明，劃線圖形很少，使人們更容易理解圖紙。
對交叉數字的研究起源於Turán的磚廠問題，其中PálTurán要求制定一項工廠計劃，以最大程度地減少將磚窯連接到存儲地點的軌道之間的穿越數量。從數學上講，這個問題可以正式化，因為它要求完整的兩部分圖的交叉數。與社會圖的構建有關，大約同時在社會學中獨立出現了同樣的問題。 Turán對於完整兩部分圖的交叉數字的猜想公式尚未得到證實，與完整圖的類似公式也未經證實。
交叉數字不等式指出，對於邊緣數E的圖，足夠大於頂點的數字n ，交叉數至少與E 3 / N 2成正比。它在VLSI設計和發病率幾何形狀中具有應用。
沒有進一步的資格，交叉數允許用任意曲線表示邊緣的圖紙。該概念的變體，即直線交叉數，所有邊緣都需要直線段，並且可能與交叉數不同。特別是，完整圖的直線交叉數基本上與由一組N點一組中的N點確定的最小凸四側數量相同。確定這個數字的問題與幸福的結局問題密切相關。
定義
為了定義交叉數的目的，無向圖的繪製是從圖形的頂點到平面中的分離點的映射，以及從圖的邊緣到連接兩個端點的曲線的曲線。不應將頂點映射到它不是端點的邊緣上，並且每當兩個邊緣具有相交的曲線（除了在共享端點外）時，它們的交叉點應形成一組有限的合適橫梁，其中兩條曲線是橫向的。對於每個交叉點，每對交叉點分別計數一個交叉點。然後，圖形的交叉數是圖紙中交叉數的所有圖紙的最小值。
一些作者在圖形的定義中添加了更多約束，例如，每對邊緣最多都有一個相交點（共享端點或交叉）。對於上面定義的交叉數，這些約束沒有區別，因為交叉最小圖形不能具有多個相交點的邊緣。如果兩個帶有共享端點交叉的邊緣，則可以在交叉點本地更改圖形，使繪圖的其餘部分保持不變，以產生一個不同的圖紙，而較少的橫梁。同樣，如果兩個邊緣越過兩次或多次，則可以在兩個交叉點進行本地更改圖形，以使兩個較少的橫梁進行不同的圖形。但是，這些約束與交叉數的變體定義有關，例如，這些定義僅計算越過越過的邊緣的數量而不是交叉數。
特別案例
截至2015年4月，交叉數字以很少的圖表家庭而聞名。特別是，除了一些初始情況外，儘管在下限上已經有一些進展，但完整圖，兩分的完整圖和周期產物的交叉數量仍然未知。
完整的兩分圖
在第二次世界大戰期間，匈牙利數學家PálTurán被迫在一家磚廠工作，將貨車裝載從窯爐推到儲藏地點。工廠從每個窯爐到每個存儲地點都有軌道，貨車很難在軌道互相交叉的地方推動，而Turán被帶到那裡問他的磚工廠問題：窯爐，儲物網站和軌道如何如何被安排以最大程度地減少交叉的總數？從數學上講，窯爐和儲存地點可以正式化為完整的兩部分圖的頂點，其軌道為邊緣。可以將工廠佈局表示為該圖的圖形，因此問題變成了：完整的兩部分圖的繪圖中可能的交叉數量是多少？
Kazimierz Zarankiewicz試圖解決Turán的磚工廠問題；他的證明包含一個錯誤，但他確立了有效的上限
對於完整的兩分圖K m的交叉數。該界限已被認為是所有完整的兩部分圖的最佳交叉數。
完整的圖形和圖形著色
確定完整圖的交叉數的問題首先是由安東尼·希爾（Anthony Hill）提出的，並於1960年出現。希爾和他的合作者約翰·歐內斯特（John Ernest）是兩位對數學著迷的建築主義藝術家。他們不僅提出了這個問題，還為這個交叉數字起了一個猜想的公式，理查德·K·蓋伊（Richard K.）於1960年發表。
十字路口。該公式給出1、3、9、18、36、60、100、150的值， p = 5，...，12 ;參見整數序列的在線百科全書中的序列A000241 。猜想是沒有更好的圖形，因此該公式為完整圖提供了最佳的交叉數。托馬斯·薩蒂（Thomas L. Saaty）於1964年對同一猜想進行了獨立的表述。
Saaty進一步驗證了該公式給出了P≤10的最佳交叉數，Pan和Richter表明它對P = 11，12也是最佳的。
由邁克爾·奧伯森（Michael O. Albertson）於2007年制定的艾伯森（Albertson）猜想指出，在所有色數n的圖形中，完整的圖k n具有最小的交叉數。也就是說，如果完整圖的交叉數的猜想公式是正確的，則每個n個奇異圖的交叉數至少等於同一公式。現在已知艾伯遜猜想以N≤16持有。
立方圖
具有1-8和11的最小立方圖是已知的（ OEI中的序列A110507 ）。最小的1跨立方圖是完整的兩分圖K 3,3 ，具有6個頂點。最小的2跨立方圖是Petersen圖，具有10個頂點。最小的3串立方圖是Heawood圖，具有14個頂點。最小的4跨立方圖是Möbius-Kantor圖，具有16個頂點。最小的5橫尺圖是Pappus圖，具有18個頂點。最小的6個跨立方圖是Desargues圖，具有20個頂點。眾所周知，四個具有22個頂點的7個7個立方圖中都沒有。最小的8個跨立方圖包括Nauru圖和McGee圖或（3,7） -籠子圖，帶有24個頂點。最小的11個跨立方圖包括帶有28個頂點的Coxeter圖。
在2009年，Pegg和Exoo的猜想是，具有交叉數字13的最小立方體圖是Tutte-Coxeter圖，而最小的Cubic圖170是Tutte 12-Cage 。
連接到二分寬度
2/3分配寬度
複雜性和近似值
通常，確定圖的交叉數很難。加里（Garey ）和約翰遜（Johnson）在1983年表明，這是一個NP困難的問題。實際上，即使僅限於立方圖和接近平面圖（去除單個邊緣後，將變成平面的圖形），該問題仍然是NP-HARD。對於真實的存在理論，確定直線交叉數的緊密相關問題是完整的。
在正面，有有效的算法來確定交叉數是否小於固定常數k 。換句話說，問題是固定參數可處理的。對於較大的k ，例如k = |仍然很難。 V |/2 。還有有效的近似算法用於近似
交叉數字不等式
對於具有N頂點和E邊的無方向的簡單圖G ，使E > 7 n至少始終是
邊緣，頂點和交叉數之間的這種關係是由Ajtai ， Chvátal ，Newborn和Szemerédi獨立發現的，以及Leighton。它被稱為交叉數不等式或交叉引理。
常數29是迄今為止最著名的，並且是由於Ackerman造成的。常數7可以降低至4 ，但以較差的64常數代替29 。
Leighton在研究交叉數字中的動機是用於在理論計算機科學中進行VLSI設計的應用。後來，Székely也意識到這種不平等得出了非常簡單的證據，證明了一些重要定理的入射幾何形狀，例如Beck的定理和Szemerédi -Trotter定理，而Tamal Dey則用它證明了在幾何k - sets上的上限。
變化
如果需要將邊緣繪製為直線段，而不是任意曲線，則有些圖需要更多的橫差。直線交叉數定義為此類圖的最小交叉數。它總是至少與交叉數一樣大，並且對於某些圖形而言大。眾所周知，通常，直線交叉數不能受交叉數的函數的界定。 K 5至K 12的直線交叉數為1、3、9、19、36、62、102、153 ，（ A014540 ）和高達k 27的值， k 28需要7233或7234橫梁。直線交叉編號項目收集了進一步的值。
如果可以在每個邊緣繪製最多的K交叉點，則具有本地交叉數k ，但不要更少。每個邊緣最多可以用K交叉點繪製的圖也稱為K-平面。
交叉數的其他變體包括成對的交叉數（在任何圖紙中交叉的邊緣對的最小邊數）和奇數交叉數（在任何圖紙中越過奇數次數的邊的邊數）。奇數交叉數最多等於成對交叉數，最多等於交叉數。但是，通過Hanani -Tutte定理，每當這些數字之一為零時，它們都是。 Schaefer（ 2014，2018 ）調查了許多這樣的變體。