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 | |