| dbo:abstract
|
- In graph theory, Schnyder's theorem is a characterization of planar graphs in termsof the order dimension of their incidence posets. It is named after Walter Schnyder, who published its proof in . The incidence poset P(G) of an undirected graph G with vertex set V and edge set E is the partially ordered set of height 2 that has V ∪ E as its elements. In this partial order, there is an order relation x < y when x is a vertex, y is an edge, and x is one of the two endpoints of y. The order dimension of a partial order is the smallest number of total orderings whose intersection is the given partial order; such a set of orderings is called a realizer of the partial order.Schnyder's theorem states that a graph G is planar if and only if the order dimension of P(G) is at most three. (en)
- 슈니더의 정리(Schnyder's theorem, -定理)은 그래프 이론의 정리로, 평면 그래프의 특성화를 위한 조건을 제공한다. (ko)
- Теорема Шнайдера — это описание планарных графов в терминах его . Теорема носит имя Вальтера Шнайдера, опубликовавшего её доказательство в 1989 году. Частично упорядоченное множество инцидентных вершин неориентированного графа G со множеством вершин и V и множеством рёбер E — это частично упорядоченное множество высоты 2, которое имеет в качестве элементов. В этом частично упорядоченном множестве имеется отношения порядка , если x является вершиной, y является ребром и x является одним из концов дуги y. Порядковая размерность частично упорядоченного множества — это наименьшее число полных порядков, пересечение которых даёт данное частично упорядоченное множество. Такое множество порядков называется реализатором частично упорядоченного множества. Теорема Шнайдера утверждает, что граф G является планарным тогда и только тогда, когда порядковая размерность не превосходит трёх. (ru)
- Теорема Шнайдера — це опис планарного графа в термінах його . Теорему названо ім'ям Вальтера Шнайдера, який опублікував її доведення 1989 року. Частково впорядкована множина інцидентних вершин неорієнтованого графа з множиною вершин і множиною ребер — це частково впорядкована множина висоти 2, яка має як елементи. У цій частково впорядкованій множині є відношення порядку якщо є вершиною, є ребром і є одним із кінців . Порядкова розмірність частково впорядкованої множини — це найменша кількість повних порядків, перетин яких дає дану частково впорядковану множину. Таку множину порядків називають реалізатором частково впорядкованої множини. Теорема Шнайдера стверджує, що граф є планарним тоді й лише тоді, коли порядкова розмірність не перевищує трьох. (uk)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 5034 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:last
|
- Trotter (en)
- Brightwell (en)
- Ossona de Mendez (en)
|
| dbp:wikiPageUsesTemplate
| |
| dbp:year
|
- 1993 (xsd:integer)
- 1997 (xsd:integer)
- 1999 (xsd:integer)
- 2002 (xsd:integer)
|
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- 슈니더의 정리(Schnyder's theorem, -定理)은 그래프 이론의 정리로, 평면 그래프의 특성화를 위한 조건을 제공한다. (ko)
- In graph theory, Schnyder's theorem is a characterization of planar graphs in termsof the order dimension of their incidence posets. It is named after Walter Schnyder, who published its proof in . The incidence poset P(G) of an undirected graph G with vertex set V and edge set E is the partially ordered set of height 2 that has V ∪ E as its elements. In this partial order, there is an order relation x < y when x is a vertex, y is an edge, and x is one of the two endpoints of y. (en)
- Теорема Шнайдера — це опис планарного графа в термінах його . Теорему названо ім'ям Вальтера Шнайдера, який опублікував її доведення 1989 року. Частково впорядкована множина інцидентних вершин неорієнтованого графа з множиною вершин і множиною ребер — це частково впорядкована множина висоти 2, яка має як елементи. У цій частково впорядкованій множині є відношення порядку якщо є вершиною, є ребром і є одним із кінців . (uk)
- Теорема Шнайдера — это описание планарных графов в терминах его . Теорема носит имя Вальтера Шнайдера, опубликовавшего её доказательство в 1989 году. Частично упорядоченное множество инцидентных вершин неориентированного графа G со множеством вершин и V и множеством рёбер E — это частично упорядоченное множество высоты 2, которое имеет в качестве элементов. В этом частично упорядоченном множестве имеется отношения порядка , если x является вершиной, y является ребром и x является одним из концов дуги y. (ru)
|
| rdfs:label
|
- 슈니더의 정리 (ko)
- Schnyder's theorem (en)
- Теорема Шнайдера (ru)
- Теорема Шнайдера (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
