In graph theory, an ear of an undirected graph G is a path P where the two endpoints of the path may coincide, but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of P has degree two in G. An ear decomposition of an undirected graph G is a partition of its set of edges into a sequence of ears, such that the one or two endpoints of each ear belong to earlier ears in the sequence and such that the internal vertices of each ear do not belong to any earlier ear. Additionally, in most cases the first ear in the sequence must be a cycle. An open ear decomposition or a proper ear decomposition is an ear decomposition in which the two endpoints of each ear after the first are distinct from each other.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Descomposición en orejas (es)
- Ear decomposition (en)
- Ушная декомпозиция (ru)
- Вушна декомпозиція (uk)
|
| rdfs:comment
| - En teoría de grafos, una oreja de un grafo G es un camino P en el que sus dos extremos pueden coincidir, pero donde no se permite la repetición de aristas o vértices, por lo que todo vértice interno de P tiene grado dos en G. Una descomposición en orejas de un grafo no dirigido G es una partición de su conjunto de aristas en una secuencia en orejas, tal que uno o dos extremos de cada oreja pertenecen a orejas anteriores en la secuencia y tal que los vértices internos de cada oreja no pertenecen a ninguna oreja anterior. Además, en la mayoría de los casos, la primera oreja de la secuencia debe ser un ciclo. Una descomposición en oreja abierta o una descomposición en oreja propia es aquella en la que los dos extremos de cada oreja después de la primera son distintos entre sí. (es)
- In graph theory, an ear of an undirected graph G is a path P where the two endpoints of the path may coincide, but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of P has degree two in G. An ear decomposition of an undirected graph G is a partition of its set of edges into a sequence of ears, such that the one or two endpoints of each ear belong to earlier ears in the sequence and such that the internal vertices of each ear do not belong to any earlier ear. Additionally, in most cases the first ear in the sequence must be a cycle. An open ear decomposition or a proper ear decomposition is an ear decomposition in which the two endpoints of each ear after the first are distinct from each other. (en)
- В теории графов ухо неориентированного графа G — это путь P, у которого две конечные точки могут совпадать, но в противном случае не разрешается повторение вершин или рёбер, так что любая внутренняя точка пути P имеет в пути степень два. Ушная декомпозиция неориентированного графа G — это разбиение множества его рёбер на последовательность ушей, так что конечные точки каждого уха принадлежат ранее выделенным ушам в последовательности, при этом внутренние вершины каждого уха не принадлежат предыдущим ушам. Кроме того, в большинстве случаев первое ухо в последовательности должно быть циклом. Открытая или правильная ушная декомпозиция — это ушная декомпозиция, в которой две конечные точки каждого уха, кроме первого, отличаются. (ru)
- У теорії графів ву́хо неорієнтованого графа G — це шлях P, дві кінцеві точки якого можуть збігатися, але в іншому випадку не дозволяється повторення вершин або ребер, так що будь-яка внутрішня точка шляху P має в шляху степінь два. Вушна́ декомпози́ція неорієнтованого графа G — це розбиття множини його ребер на послідовність вух, так що кінцеві точки кожного вуха належать раніше виділеним вухам послідовності, при цьому внутрішні вершини кожного вуха не належать попереднім вухам. Крім того, в більшості випадків перше вухо в послідовності має бути циклом. Відкри́та або пра́вильна вушна́ декомпози́ція — це вушна декомпозиція, в якій дві кінцеві точки кожного вуха, крім першого, відрізняються. (uk)
|
| foaf:depiction
| |
| dct:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| authorlink
| - László Lovász (en)
- David Eppstein (en)
- Hassler Whitney (en)
- Herbert Robbins (en)
|
| first
| - David (en)
- Herbert (en)
- László (en)
- Hassler (en)
|
| last
| - Robbins (en)
- Whitney (en)
- Lovász (en)
- Eppstein (en)
|
| year
| |
| has abstract
| - In graph theory, an ear of an undirected graph G is a path P where the two endpoints of the path may coincide, but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of P has degree two in G. An ear decomposition of an undirected graph G is a partition of its set of edges into a sequence of ears, such that the one or two endpoints of each ear belong to earlier ears in the sequence and such that the internal vertices of each ear do not belong to any earlier ear. Additionally, in most cases the first ear in the sequence must be a cycle. An open ear decomposition or a proper ear decomposition is an ear decomposition in which the two endpoints of each ear after the first are distinct from each other. Ear decompositions may be used to characterize several important graph classes, and as part of efficient graph algorithms. They may also be generalized from graphs to matroids. (en)
- En teoría de grafos, una oreja de un grafo G es un camino P en el que sus dos extremos pueden coincidir, pero donde no se permite la repetición de aristas o vértices, por lo que todo vértice interno de P tiene grado dos en G. Una descomposición en orejas de un grafo no dirigido G es una partición de su conjunto de aristas en una secuencia en orejas, tal que uno o dos extremos de cada oreja pertenecen a orejas anteriores en la secuencia y tal que los vértices internos de cada oreja no pertenecen a ninguna oreja anterior. Además, en la mayoría de los casos, la primera oreja de la secuencia debe ser un ciclo. Una descomposición en oreja abierta o una descomposición en oreja propia es aquella en la que los dos extremos de cada oreja después de la primera son distintos entre sí. Las descomposiciones en orejas se pueden usar para caracterizar varias clases de grafos importantes y como parte de eficientes. También pueden generalizarse de grafos a matroides. (es)
- В теории графов ухо неориентированного графа G — это путь P, у которого две конечные точки могут совпадать, но в противном случае не разрешается повторение вершин или рёбер, так что любая внутренняя точка пути P имеет в пути степень два. Ушная декомпозиция неориентированного графа G — это разбиение множества его рёбер на последовательность ушей, так что конечные точки каждого уха принадлежат ранее выделенным ушам в последовательности, при этом внутренние вершины каждого уха не принадлежат предыдущим ушам. Кроме того, в большинстве случаев первое ухо в последовательности должно быть циклом. Открытая или правильная ушная декомпозиция — это ушная декомпозиция, в которой две конечные точки каждого уха, кроме первого, отличаются. Ушную декомпозицию можно использовать для описания некоторых важных классов графов, и как часть эффективных . Ушную декомпозицию можно обобщить для матроидов. (ru)
- У теорії графів ву́хо неорієнтованого графа G — це шлях P, дві кінцеві точки якого можуть збігатися, але в іншому випадку не дозволяється повторення вершин або ребер, так що будь-яка внутрішня точка шляху P має в шляху степінь два. Вушна́ декомпози́ція неорієнтованого графа G — це розбиття множини його ребер на послідовність вух, так що кінцеві точки кожного вуха належать раніше виділеним вухам послідовності, при цьому внутрішні вершини кожного вуха не належать попереднім вухам. Крім того, в більшості випадків перше вухо в послідовності має бути циклом. Відкри́та або пра́вильна вушна́ декомпози́ція — це вушна декомпозиція, в якій дві кінцеві точки кожного вуха, крім першого, відрізняються. Вушну декомпозицію можна використати для опису деяких важливих класів графів, і як частину ефективних алгоритмів на графах. Вушну декомпозицію можна узагальнити для матроїдів. (uk)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
