| dbo:abstract
|
- In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest. The names are justified by analogy to the more commonly studied trees and forests. (A tree is a connected graph with no cycles; a forest is a disjoint union of trees.) Gabow and Tarjan attribute the study of pseudoforests to Dantzig's 1963 book on linear programming, in which pseudoforests arise in the solution of certain network flow problems. Pseudoforests also form graph-theoretic models of functions and occur in several algorithmic problems. Pseudoforests are sparse graphs – their number of edges is linearly bounded in terms of their number of vertices (in fact, they have at most as many edges as they have vertices) – and their matroid structure allows several other families of sparse graphs to be decomposed as unions of forests and pseudoforests. The name "pseudoforest" comes from . (en)
- En théorie des graphes, une pseudo-forêt est un graphe non orienté, ou même un multigraphe dans lequel chaque composante connexe possède au plus un cycle. De manière équivalente, une pseudo-forêt est un graphe dans lequel deux cycles ne sont pas connectés par une chaîne. Un pseudo-arbre est une pseudo-forêt connexe. (fr)
- Em teoria dos grafos, uma pseudofloresta é um grafo não direcionado em que cada tem no máximo um ciclo. Ou seja, é um sistema de vértices e arestas que conectam pares de vértices, de tal modo que não há dois ciclos consecutivos de arestas compartilhando qualquer vértice com o outro, nem podem ser quaisquer dois ciclos ligados uns aos outros por um caminho de arestas consecutivos. Uma pseudoárvore é uma pseudofloresta conectada. Os nomes são justificados por analogia em relação as árvores e florestas mais comumente estudadas (uma árvore é um grafo sem ciclos; uma floresta é uma união disjunta de árvores). Gabow e Tarjan atribuem o estudo das pseudoflorestas ao livro de programação linear de Dantzig's (1993), em que pseudoflorestas surgem na solução de certos problemas de fluxo em redes. Pseudoflorestas também formam modelos de grafos teóricos de funções e ocorrem em muitos problemas de algoritmos. Pseudoflorestas são grafos esparsos - eles tem muito poucas arestas em relação ao número de vértices - e sua estrutura permite que muitas outras famílias de grafos esparsos sejam decompostas como a união de florestas e pseudoflorestas. O nome "pseudofloresta" vem de . (pt)
- В теории графов псевдолес — это неориентированный граф , в котором любая связная компонента имеет максимум один цикл. То есть это система вершин и рёбер, соединяющих пары вершин, такая, что никакие два цикла не имеют общих вершин и не могут быть связаны путём. Псевдодерево — это связный псевдолес. Названия взяты по аналогии с общеизвестными деревьями и лесами (дерево — это связный граф без циклов, лес — объединение несвязных деревьев). Габов и Тарьян приписывают изучение псевдолесов книге 1963 Данцига по линейному программированию, в которой псевдолеса появляются в решении некоторых задач транспортных потоков. Псевдолеса также образуют теоретические графовые модели функций и появляются в некоторых алгоритмических задачах. Псевдолеса являются разреженными графами – они имеют очень малое число рёбер по отношению к числу вершин, и их структура матроидов позволяет некоторые другие семейства редких графов разложить на объединение лесов и псевдолесов. Название "псевдолес" пришло из статьи Пикарда и Керанна. (ru)
- У теорії графів псевдолі́с — це неорієнтований граф, у якому будь-яка зв'язна компонента має не більше одного циклу. Тобто це система вершин і ребер, що з'єднують пари вершин, така, що жодні два цикли не мають спільних вершин і не можуть бути пов'язаними шляхом. Псевдоде́рево — це зв'язний псевдоліс. Назви взято за аналогією із деревами та лісами (дерево — це зв'язний граф без циклів, ліс — незв'язне об'єднання дерев). Габов і Тарджан приписують вивчення псевдолісів Данцігу в книзі 1963 року з лінійного програмування, в якій псевдоліси з'являються в розв'язуванні деяких задач транспортних потоків. Псевдоліси також утворюють теоретичні графові моделі функцій і з'являються в деяких алгоритмічних задачах. Псевдоліси є розрідженими графами — вони мають дуже мале число ребер відносно вершин, і їхня структура матроїдів дозволяє деякі інші сімейства розріджених графів розкласти на об'єднання лісів і псевдолісів. Назва «псевдоліс» прийшла зі статті Пікара та Кейрана. (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 30992 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:mode
| |
| dbp:title
| |
| dbp:urlname
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- En théorie des graphes, une pseudo-forêt est un graphe non orienté, ou même un multigraphe dans lequel chaque composante connexe possède au plus un cycle. De manière équivalente, une pseudo-forêt est un graphe dans lequel deux cycles ne sont pas connectés par une chaîne. Un pseudo-arbre est une pseudo-forêt connexe. (fr)
- In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest. (en)
- Em teoria dos grafos, uma pseudofloresta é um grafo não direcionado em que cada tem no máximo um ciclo. Ou seja, é um sistema de vértices e arestas que conectam pares de vértices, de tal modo que não há dois ciclos consecutivos de arestas compartilhando qualquer vértice com o outro, nem podem ser quaisquer dois ciclos ligados uns aos outros por um caminho de arestas consecutivos. Uma pseudoárvore é uma pseudofloresta conectada. (pt)
- В теории графов псевдолес — это неориентированный граф , в котором любая связная компонента имеет максимум один цикл. То есть это система вершин и рёбер, соединяющих пары вершин, такая, что никакие два цикла не имеют общих вершин и не могут быть связаны путём. Псевдодерево — это связный псевдолес. (ru)
- У теорії графів псевдолі́с — це неорієнтований граф, у якому будь-яка зв'язна компонента має не більше одного циклу. Тобто це система вершин і ребер, що з'єднують пари вершин, така, що жодні два цикли не мають спільних вершин і не можуть бути пов'язаними шляхом. Псевдоде́рево — це зв'язний псевдоліс. (uk)
|
| rdfs:label
|
- Pseudo-forêt (fr)
- Pseudoforest (en)
- Pseudofloresta (pt)
- Псевдолес (ru)
- Псевдоліс (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
