| dbo:abstract
|
- In the mathematics of graph drawing, the crossing number inequality or crossing lemma gives a lower bound on the minimum number of crossings of a given graph, as a function of the number of edges and vertices of the graph. It 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 combinatorial geometry,and was discovered independently by Ajtai, Chvátal, Newborn, and Szemerédiand by Leighton. (en)
- Неравенство числа пересечений или лемма о пересечениях даёт нижнюю грань минимального числа пересечений данного графа как функцию от числа рёбер и вершин графа. Лемма утверждает, что для графов, у которых число рёбер e достаточно велико по сравнению с числом вершин n, число пересечений по меньшей мере пропорционально e3/n2. Неравенство имеет приложения при разработке СБИС и в комбинаторной геометрии. Неравенство открыли Аитаи, Хватал, Ньюборн и Семереди и, независимо, Лейтон. (ru)
- 交叉數不等式是數學的圖論分支中的一条不等式，給出了一幅图画在平面上时交叉數的下界；这一结论又名交叉数引理。給定一幅圖，該下界可由其邊數和頂點數計算出。不等式斷言，若邊數与頂點數的比值大于某个常数，則交叉數不小于乘以另一个固定的常数。 交叉數不等式在超大规模集成电路設計與組合幾何方面有應用。其由、、、塞邁雷迪·安德烈四人以及分別獨立發現。 (zh)
- Нерівність числа схрещень або лема про схрещення дає нижню межу мінімальної кількості схрещень даного графа як функцію від числа ребер і вершин графа. Лема стверджує, що для графів, у яких число ребер e досить велике, порівняно з числом вершин n, число схрещень принаймні пропорційне e3/n2 Нерівність застосовують при розробці надвеликих інтегральних схем (НВІС) та в комбінаторній геометрії. Нерівність відкрили Айтай, Хватал, Ньюборн та Семереді і, незалежно, Лейтон. (uk)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 10792 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- In the mathematics of graph drawing, the crossing number inequality or crossing lemma gives a lower bound on the minimum number of crossings of a given graph, as a function of the number of edges and vertices of the graph. It 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 combinatorial geometry,and was discovered independently by Ajtai, Chvátal, Newborn, and Szemerédiand by Leighton. (en)
- Неравенство числа пересечений или лемма о пересечениях даёт нижнюю грань минимального числа пересечений данного графа как функцию от числа рёбер и вершин графа. Лемма утверждает, что для графов, у которых число рёбер e достаточно велико по сравнению с числом вершин n, число пересечений по меньшей мере пропорционально e3/n2. Неравенство имеет приложения при разработке СБИС и в комбинаторной геометрии. Неравенство открыли Аитаи, Хватал, Ньюборн и Семереди и, независимо, Лейтон. (ru)
- 交叉數不等式是數學的圖論分支中的一条不等式，給出了一幅图画在平面上时交叉數的下界；这一结论又名交叉数引理。給定一幅圖，該下界可由其邊數和頂點數計算出。不等式斷言，若邊數与頂點數的比值大于某个常数，則交叉數不小于乘以另一个固定的常数。 交叉數不等式在超大规模集成电路設計與組合幾何方面有應用。其由、、、塞邁雷迪·安德烈四人以及分別獨立發現。 (zh)
- Нерівність числа схрещень або лема про схрещення дає нижню межу мінімальної кількості схрещень даного графа як функцію від числа ребер і вершин графа. Лема стверджує, що для графів, у яких число ребер e досить велике, порівняно з числом вершин n, число схрещень принаймні пропорційне e3/n2 Нерівність застосовують при розробці надвеликих інтегральних схем (НВІС) та в комбінаторній геометрії. Нерівність відкрили Айтай, Хватал, Ньюборн та Семереді і, незалежно, Лейтон. (uk)
|
| rdfs:label
|
- Crossing number inequality (en)
- Неравенство числа пересечений (ru)
- Нерівність числа схрещень (uk)
- 交叉數不等式 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is foaf:primaryTopic
of | |
