Ear decomposition (original) (raw)
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í.
| Property | Value |
|---|---|
| dbo: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) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Ear_decomposition.png?width=300 |
| dbo:wikiPageExternalLink | https://books.google.com/books%3Fid=unEloQ_sYmkC&pg=PA498 http://portalparts.acm.org/70000/65780/bm/backmatter.pdf http://www.ics.uci.edu/~eppstein/pubs/Epp-IC-92.pdf http://dml.cz/bitstream/handle/10338.dmlcz/101517/CzechMathJ_28-1978-1_10.pdf |
| dbo:wikiPageID | 32183016 (xsd:integer) |
| dbo:wikiPageLength | 14950 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1093782187 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Matroid_theory dbr:Perfect_matching dbr:Undirected_graph dbr:Degree_(graph_theory) dbc:Graph_theory_objects dbr:Lowest_common_ancestor dbr:Combinatorica dbr:Parallel_algorithm dbr:Path_(graph_theory) dbr:Spanning_tree dbr:Theoretical_Computer_Science_(journal) dbr:Matroid dbr:Matroid_oracle dbr:K-edge-connected_graph dbr:K-vertex-connected_graph dbr:American_Mathematical_Monthly dbr:Partition_of_a_set dbr:Directed_graph dbr:Graph_drawing dbr:Graph_theory dbr:Graphic_matroid dbr:Circuit_rank dbr:Polynomial_time dbr:Graph_algorithm dbr:Greedy_algorithms dbr:Indegree dbr:Outdegree dbr:Factor-critical_graph dbr:Planarity_testing dbr:Series–parallel_graph dbr:Robbins_theorem dbr:Symposium_on_Foundations_of_Computer_Science dbr:Transactions_of_the_American_Mathematical_Society dbr:SIGACT_News dbr:Strongly_connected dbr:Chain_decomposition_(undirected_graphs) dbr:File:Ear_decomposition.png |
| dbp:authorlink | László Lovász (en) David Eppstein (en) Hassler Whitney (en) Herbert Robbins (en) |
| dbp:first | David (en) Herbert (en) László (en) Hassler (en) |
| dbp:last | Robbins (en) Whitney (en) Lovász (en) Eppstein (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Harv dbt:Harvtxt dbt:Refbegin dbt:Refend dbt:Short_description dbt:Harvs |
| dbp:year | 1932 (xsd:integer) 1939 (xsd:integer) 1972 (xsd:integer) 1992 (xsd:integer) |
| dcterms:subject | dbc:Matroid_theory dbc:Graph_theory_objects |
| gold:hypernym | dbr:P |
| rdf:type | yago:Object100002684 yago:PhysicalEntity100001930 yago:WikicatGraphTheoryObjects dbo:Album |
| 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) |
| rdfs:label | Descomposición en orejas (es) Ear decomposition (en) Ушная декомпозиция (ru) Вушна декомпозиція (uk) |
| owl:sameAs | freebase:Ear decomposition yago-res:Ear decomposition wikidata:Ear decomposition dbpedia-es:Ear decomposition dbpedia-fa:Ear decomposition dbpedia-ru:Ear decomposition dbpedia-uk:Ear decomposition https://global.dbpedia.org/id/4j67p |
| prov:wasDerivedFrom | wikipedia-en:Ear_decomposition?oldid=1093782187&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Ear_decomposition.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Ear_decomposition |
| is dbo:wikiPageRedirects of | dbr:Ear_(graph_theory) |
| is dbo:wikiPageWikiLink of | dbr:Glossary_of_graph_theory dbr:Matroid_oracle dbr:K-edge-connected_graph dbr:Bridge_(graph_theory) dbr:Strongly_connected_component dbr:Herbert_Robbins dbr:Bipolar_orientation dbr:Circuit_rank dbr:Factor-critical_graph dbr:Series–parallel_graph dbr:Robbins'_theorem dbr:Ear_(graph_theory) |
| is foaf:primaryTopic of | wikipedia-en:Ear_decomposition |
