Pseudoforest (original) (raw)
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.
| Property | Value |
|---|---|
| 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 | wiki-commons:Special:FilePath/Pseudoforest.svg?width=300 |
| dbo:wikiPageExternalLink | https://docs.lib.purdue.edu/cgi/viewcontent.cgi%3Farticle=1613&context=cstech https://dmtcs.episciences.org/3486%7Ccontribution=Bipartite http://www.stephenwolfram.com/publications/articles/mathematics/84-properties/%7Cbibcode=1984CMaPh..93..219M%7Cs2cid=6900060%7Caccess-date=2007-10-03%7Carchive-date=2012-02-12%7Carchive-url=https:/web.archive.org/web/20120212210855/http:/www.stephenwolfram.com/publications/articles/mathematics/84-properties/%7Curl-status=dead |
| dbo:wikiPageID | 13511542 (xsd:integer) |
| dbo:wikiPageLength | 30992 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1087757199 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Minor_(graph_theory) dbr:Multigraph dbr:Bicircular_matroid dbr:Algorithm dbc:Matroid_theory dbc:Graph_families dbr:Arboricity dbr:Cuckoo_hashing dbr:Cycle_(graph_theory) dbr:Cycle_detection dbr:Undirected_graph dbr:Vector_space dbr:Induced_subgraph dbr:Integer_factorization dbr:Robertson–Seymour_theorem dbc:Graph_theory_objects dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Conway's_thrackle_conjecture dbr:Cryptographic_hash_function dbr:Cryptography dbr:Mathematische_Zeitschrift dbr:Endomorphism dbr:Glossary_of_graph_theory dbr:Graph_coloring dbr:SIAM_Journal_on_Discrete_Mathematics dbr:Symposium_on_Parallel_Algorithms_and_Architectures dbr:Andrew_Odlyzko dbr:André_Joyal dbr:Cactus_graph dbr:Steiner_system dbr:Stephen_Wolfram dbr:Closure_(mathematics) dbr:Commodity dbr:Computational_number_theory dbr:Parallel_algorithm dbr:Path_(graph_theory) dbr:Still_life_(cellular_automaton) dbr:Matroid dbr:Butterfly_graph dbr:Cayley's_formula dbr:Tree_(graph_theory) dbr:Linear_independence dbr:Linear_programming dbr:Edge_(graph_theory) dbr:Flow_network dbr:Cellular_automaton dbr:Directed_graph dbr:Graph_drawing dbr:Graph_theory dbr:Graphic_matroid dbr:Graphs_and_Combinatorics dbr:Endofunction dbr:Iterated_function dbr:Thrackle dbr:Bijective_proof dbr:Bipartite_graph dbr:Proofs_from_THE_BOOK dbr:Diamond_graph dbr:Ars_Combinatoria_(journal) dbr:Philippe_Flajolet dbr:Planar_graph dbr:Pollard's_rho_algorithm dbr:Connected_component_(graph_theory) dbr:Greedy_algorithm dbr:Independence_system dbr:Minimum_spanning_tree dbr:On-Line_Encyclopedia_of_Integer_Sequences dbr:Sergei_Konyagin dbr:Loop_(graph_theory) dbr:Simplex_algorithm dbr:Vertex_(graph_theory) dbr:Outdegree dbr:Discrete_and_Computational_Geometry dbr:Forest_(graph_theory) dbr:Wagner's_theorem dbr:Random_graph dbr:Transactions_of_the_American_Mathematical_Society dbr:Linear_program dbr:Workshop_on_the_Theory_and_Application_of_Cryptographic_Techniques dbr:Springer-Verlag dbr:Garden_of_Eden_pattern dbr:Forbidden_minor dbr:Birthday_paradox dbr:Self-loop dbr:Sparse_graph dbr:File:Pseudoforest.svg dbr:File:Functional_graph.svg dbr:File:Butterfly_and_diamond_graphs.svg dbr:File:The21.GIF |
| dbp:mode | cs2 (en) |
| dbp:title | Unicyclic Graph (en) |
| dbp:urlname | UnicyclicGraph (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Good_article dbt:Harvtxt dbt:Mathworld dbt:Radic dbt:Redirect dbt:Refbegin dbt:Refend dbt:Reflist dbt:Short_description dbt:OEIS2C |
| dcterms:subject | dbc:Matroid_theory dbc:Graph_families dbc:Graph_theory_objects |
| gold:hypernym | dbr:Graph |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Communication100033020 yago:Family108078020 yago:Graph107000195 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 yago:VisualCommunication106873252 yago:WikicatDirectedGraphs |
| 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 | freebase:Pseudoforest yago-res:Pseudoforest wikidata:Pseudoforest dbpedia-fr:Pseudoforest dbpedia-hu:Pseudoforest dbpedia-pt:Pseudoforest dbpedia-ru:Pseudoforest dbpedia-uk:Pseudoforest https://global.dbpedia.org/id/4ti3T |
| prov:wasDerivedFrom | wikipedia-en:Pseudoforest?oldid=1087757199&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Functional_graph.svg wiki-commons:Special:FilePath/Pseudoforest.svg wiki-commons:Special:FilePath/Butterfly_and_diamond_graphs.svg wiki-commons:Special:FilePath/The21.gif |
| foaf:isPrimaryTopicOf | wikipedia-en:Pseudoforest |
| is dbo:wikiPageRedirects of | dbr:1-forest dbr:Directed_pseudoforest dbr:Maximal_pseudoforest dbr:Bicycle_(graph_theory) dbr:Unicyclic_graph dbr:Pseudoarboricity dbr:Pseudotree dbr:Functional_graph dbr:Near-tree dbr:1-tree dbr:Spanning_pseudoforest |
| is dbo:wikiPageWikiLink of | dbr:Queue_number dbr:Bicircular_matroid dbr:Degeneracy_(graph_theory) dbr:Dense_graph dbr:Arboricity dbr:Cuckoo_hashing dbr:Cycle_(graph_theory) dbr:Vizing's_theorem dbr:Robertson–Seymour_theorem dbr:1-forest dbr:142_(number) dbr:Glossary_of_graph_theory dbr:Graph_minor dbr:Cactus_graph dbr:Combinatorial_proof dbr:Component_(graph_theory) dbr:Cayley's_formula dbr:Tree_(graph_theory) dbr:Treewidth dbr:Cyclic_graph dbr:Laman_graph dbr:Thrackle dbr:Diamond_graph dbr:Directed_pseudoforest dbr:Circuit_rank dbr:Greedy_coloring dbr:Maximal_pseudoforest dbr:Bicycle_(graph_theory) dbr:Unicyclic_graph dbr:Partial_k-tree dbr:Sum_coloring dbr:Pseudoarboricity dbr:Pseudotree dbr:Functional_graph dbr:Near-tree dbr:1-tree dbr:Spanning_pseudoforest |
| is foaf:primaryTopic of | wikipedia-en:Pseudoforest |
