| dbo:abstract
|
- In graph theory, the crossing number cr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown that drawing graphs with few crossings makes it easier for people to understand the drawing. The study of crossing numbers originated in Turán's brick factory problem, in which Pál Turán asked for a factory plan that minimized the number of crossings between tracks connecting brick kilns to storage sites. Mathematically, this problem can be formalized as asking for the crossing number of a complete bipartite graph. The same problem arose independently in sociology at approximately the same time, in connection with the construction of sociograms. Turán's conjectured formula for the crossing numbers of complete bipartite graphs remains unproven, as does an analogous formula for the complete graphs. The crossing number inequality states that, for graphs where the number e of edges is sufficiently larger than the number n of vertices, the crossing number is at least proportional to e3/n2. It has applications in VLSI design and incidence geometry. Without further qualification, the crossing number allows drawings in which the edges may be represented by arbitrary curves. A variation of this concept, the rectilinear crossing number, requires all edges to be straight line segments, and may differ from the crossing number. In particular, the rectilinear crossing number of a complete graph is essentially the same as the minimum number of convex quadrilaterals determined by a set of n points in general position. The problem of determining this number is closely related to the happy ending problem. (en)
- En teoría de grafos, el número de cruce cr(G), también llamado número de cruzamiento, de un grafo G es el menor número de cruces de aristas en un plano del grafo G. Por ejemplo, un grafo es plano si y solo si su número de cruce es cero. El estudio de los números de cruce tuvo su origen en elproblema de la fábrica de ladrillos de Turán, en el cual Pál Turán buscó determinar el número de cruce del grafo bipartito completo Km,n. Sin embargo, el mismo problema de minimizar cruces fue también considerado en sociología aproximadamente al mismo tiempo que Turán, en conexión con la construcción de sociogramas. Sigue siendo de gran importancia en . Sin otra especificación, el número de cruce permite diagramas en los que las aristas pueden ser representadas por curvas arbitrarias; el número de cruce rectilineo requiere que todas las aristas sean segmentos de línea recta, y puede diferir del número de cruce. En particular, el número de cruce rectilineo de un grafo completo es esencialmente el mismo que el número mínimo de cuadriláteros convexos determinados por un conjunto de "n" puntos en posición general, estrechamente relacionado con el problema del final feliz. (es)
- En théorie des graphes, le nombre de croisements cr(G) d'un graphe G est le plus petit nombre d'intersections d'arêtes d'un tracé du graphe G. Par exemple, un graphe est planaire si et seulement si son nombre de croisements est nul. La détermination du nombre de croisements tient une place importante dans le tracé de graphes. Un graphe à but informatif représenté avec peu de croisements facilite la compréhension de celui-ci. L'étude du nombre de croisements trouve son origine dans le , dans lequel Pál Turán a demandé un plan d'usine qui minimiserait le nombre de croisements entre les voies reliant les fours à briques aux sites de stockage. Formellement, ce problème revient à trouver le nombre de croisements d'un graphe biparti complet. Le même problème s'est posé indépendamment en sociologie à peu près au même moment, en relation avec la construction de sociogrammes. La formule conjecturée de Turán pour les nombres de croisements de graphes bipartis complets reste à prouver, tout comme une formule analogue pour les graphes complets. L' (en) indique que, pour les graphes où le nombre e d'arêtes est suffisamment supérieur au nombre n de sommets, le nombre de croisements est au moins proportionnel à e3/n2. Sans autre précision, le nombre de croisements permet des dessins dans lesquels les arêtes peuvent être représentées par des courbes arbitraires. Une variante de ce concept, le nombre de croisements rectilignes, exige que toutes les arêtes soient des segments et est donc supérieur ou égal au nombre de croisements. En particulier, le nombre de croisements rectilignes d'un graphe complet est sensiblement le même que[pas clair] le nombre minimum de quadrilatères convexes déterminé par un ensemble de n points. Le problème de la détermination de ce nombre est étroitement lié au Happy Ending problem. (fr)
- В теорії графів число схрещень cr(G) графа G — це найменше число перетинів ребер плоского зображення графа G. Наприклад, граф є планарним тоді і тільки тоді, коли число його схрещень дорівнює нулю. Математичною відправною точкою вивчення числа схрещень стала задача Турана про цегельну фабрику, поставлена Палом Тураном. У цій задачі потрібно знайти число схрещень повного двочасткового графа Km,n. Однак та ж сама задача поставлена в соціології приблизно в той же самий час у зв'язку з побудовою . Задача дуже важлива для візуалізації графів. Якщо не вказано інше, число схрещень відноситься до зображень графів, у яких ребра зображаються довільними кривими. Число прямолінійних схрещень вказує, що всі ребра є відрізками прямих і може відрізнятися від числа схрещень. Зокрема, число прямолінійних схрещень повного графа дорівнює мінімальному числу опуклих чотирикутників, визначених множиною n точок загального положення, що тісно пов'язано з задачею зі щасливим кінцем. (uk)
- В теории графов число пересечений cr(G) графа G — это наименьшее число пересечений рёбер плоского рисунка графа G. Например, граф является планарным тогда и только тогда, когда его число пересечений равно нулю. Математической отправной точкой изучения числа пересечений стала задача Турана о кирпичной фабрике, поставленная Палом Тураном, в которой требовалось найти число пересечений полного двудольного графа Km,n. Однако та же самая задача поставлена в социологии примерно в то же самое время в связи с построением социограмм. Задача продолжает играть большую роль в визуализации графов. Если не указано другое, число пересечений относится к представлениям графов с помощью любых кривых. Условие прямолинейных пересечений требует, чтобы все рёбра были отрезками прямых, что может изменить ответ. В частности, число прямолинейных пересечений полного графа равно минимальному числу выпуклых четырёхугольников, определённых множеством n точек в общем положении, что тесно связано с задачей со счастливым концом. (ru)
- 在圖論，交叉數是將圖畫在平面上時，邊的交叉點的最小數目。若，則稱為平面圖。在方面，計算圖的交叉數仍是一個重要問題，因為讀者研究發現，畫圖的交叉越少，越有利於讀者理解。 交叉數的研究始於。圖蘭·帕爾想求磚廠中，將每個窯爐各與全部貨倉用路軌連接的最優方案，使路軌的交叉儘可能少。按上述定義，即是問完全二部圖的交叉數。同一問題約莫同時在社會學研究提出，因為事關的繪製。 圖蘭猜想了完全二部圖交叉數的公式，但該公式迄今未獲證，完全圖的交叉數公式亦然。 交叉數不等式斷言，若邊數与頂點數的比值大于某个常数，則交叉數不小于乘以另一个固定的常数。此結論在超大规模集成电路設計與組合幾何方面有應用。 如無特別註明，交叉數允許使用任意曲線來畫邊。另一個相關概念是直線交叉數，其要求僅使用直線段來畫邊，所以未必等於交叉數。更具體說，完全圖的直線交叉數就是平面上處於一般位置的個點所能組成的凸四邊形的最少數目，因為每個凸四邊形的兩條對角線產生一個交叉。直線交叉數問題與幸福結局問題密切相關。 給定一個圖，計算其交叉數是一個NP難問題。 (zh)
|
| rdfs:comment
|
- 在圖論，交叉數是將圖畫在平面上時，邊的交叉點的最小數目。若，則稱為平面圖。在方面，計算圖的交叉數仍是一個重要問題，因為讀者研究發現，畫圖的交叉越少，越有利於讀者理解。 交叉數的研究始於。圖蘭·帕爾想求磚廠中，將每個窯爐各與全部貨倉用路軌連接的最優方案，使路軌的交叉儘可能少。按上述定義，即是問完全二部圖的交叉數。同一問題約莫同時在社會學研究提出，因為事關的繪製。 圖蘭猜想了完全二部圖交叉數的公式，但該公式迄今未獲證，完全圖的交叉數公式亦然。 交叉數不等式斷言，若邊數与頂點數的比值大于某个常数，則交叉數不小于乘以另一个固定的常数。此結論在超大规模集成电路設計與組合幾何方面有應用。 如無特別註明，交叉數允許使用任意曲線來畫邊。另一個相關概念是直線交叉數，其要求僅使用直線段來畫邊，所以未必等於交叉數。更具體說，完全圖的直線交叉數就是平面上處於一般位置的個點所能組成的凸四邊形的最少數目，因為每個凸四邊形的兩條對角線產生一個交叉。直線交叉數問題與幸福結局問題密切相關。 給定一個圖，計算其交叉數是一個NP難問題。 (zh)
- In graph theory, the crossing number cr(G) of a graph G is the lowest number of edge crossings of a plane drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero. Determining the crossing number continues to be of great importance in graph drawing, as user studies have shown that drawing graphs with few crossings makes it easier for people to understand the drawing. (en)
- En teoría de grafos, el número de cruce cr(G), también llamado número de cruzamiento, de un grafo G es el menor número de cruces de aristas en un plano del grafo G. Por ejemplo, un grafo es plano si y solo si su número de cruce es cero. (es)
- En théorie des graphes, le nombre de croisements cr(G) d'un graphe G est le plus petit nombre d'intersections d'arêtes d'un tracé du graphe G. Par exemple, un graphe est planaire si et seulement si son nombre de croisements est nul. La détermination du nombre de croisements tient une place importante dans le tracé de graphes. Un graphe à but informatif représenté avec peu de croisements facilite la compréhension de celui-ci. (fr)
- В теории графов число пересечений cr(G) графа G — это наименьшее число пересечений рёбер плоского рисунка графа G. Например, граф является планарным тогда и только тогда, когда его число пересечений равно нулю. Математической отправной точкой изучения числа пересечений стала задача Турана о кирпичной фабрике, поставленная Палом Тураном, в которой требовалось найти число пересечений полного двудольного графа Km,n. Однако та же самая задача поставлена в социологии примерно в то же самое время в связи с построением социограмм. Задача продолжает играть большую роль в визуализации графов. (ru)
- В теорії графів число схрещень cr(G) графа G — це найменше число перетинів ребер плоского зображення графа G. Наприклад, граф є планарним тоді і тільки тоді, коли число його схрещень дорівнює нулю. Математичною відправною точкою вивчення числа схрещень стала задача Турана про цегельну фабрику, поставлена Палом Тураном. У цій задачі потрібно знайти число схрещень повного двочасткового графа Km,n. Однак та ж сама задача поставлена в соціології приблизно в той же самий час у зв'язку з побудовою . Задача дуже важлива для візуалізації графів. (uk)
|
