About: Multitree

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Multitree Goto Sponge NotDistinct Permalink

An Entity of Type : yago:WikicatDirectedGraphs, within Data Space : dbpedia.org:8891 associated with source document(s)
QRcode icon

http://dbpedia.org:8891/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FMultitree

In combinatorics and order-theoretic mathematics, a multitree may describe either of two equivalent structures: a directed acyclic graph (DAG) in which there is at most one directed path between any two vertices, or equivalently in which the subgraph reachable from any vertex induces an undirected tree, or a partially ordered set (poset) that does not have four items a, b, c, and d forming a diamond suborder with a ≤ b ≤ d and a ≤ c ≤ d but with b and c incomparable to each other (also called a diamond-free poset).

Attributes	Values
rdf:type	Thing yago:Abstraction100002137 yago:Communication100033020 yago:Graph107000195 yago:VisualCommunication106873252 yago:WikicatDirectedGraphs
rdfs:label	Multi-arbre (fr) Multitree (en)
rdfs:comment	En combinatoire et en théorie des ordres, le terme multi-arbre peut décrire l'une des deux structures suivantes : un graphe orienté acyclique dans lequel l'ensemble des sommets accessibles depuis un nœud est toujours un arbre, ou un ensemble partiellement ordonné dans lequel il n'existe pas quatre éléments a, b, c, et d qui forment un sous-ordre en diamant, avec a ≤ b ≤ d et a ≤ c ≤ d mais où b et c sont incomparables (un tel ensemble ordonné est aussi appelé diamond-free poset (ou ordre partiel sans diamant). (fr) In combinatorics and order-theoretic mathematics, a multitree may describe either of two equivalent structures: a directed acyclic graph (DAG) in which there is at most one directed path between any two vertices, or equivalently in which the subgraph reachable from any vertex induces an undirected tree, or a partially ordered set (poset) that does not have four items a, b, c, and d forming a diamond suborder with a ≤ b ≤ d and a ≤ c ≤ d but with b and c incomparable to each other (also called a diamond-free poset). (en)
differentFrom	MultiTree
foaf:depiction
dcterms:subject	Directed acyclic graphs Order theory
Wikipage page ID	27131455 (xsd:integer)
Wikipage revision ID	1110421112 (xsd:integer)
Link from a Wikipage to another Wikipage	Arborescence (graph theory) Directed acyclic graphs Order theory Order theory Orientation (graph theory) Glossary of graph theory Combinatorics Computational complexity theory Tree (graph theory) Transitive reduction Partially ordered set Family of sets Family tree Reachability Taxonomy (general) Directed acyclic graph Polytree Series-parallel partial order Vertex (graph theory) Nondeterministic algorithm
sameAs	Multitree Multitree Multitree Multitree Multitree
dbp:wikiPageUsesTemplate	dbt:Distinguish dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description
thumbnail	wiki-commons:Special:FilePath/Butterfly_multitree.svg?width=300
has abstract	In combinatorics and order-theoretic mathematics, a multitree may describe either of two equivalent structures: a directed acyclic graph (DAG) in which there is at most one directed path between any two vertices, or equivalently in which the subgraph reachable from any vertex induces an undirected tree, or a partially ordered set (poset) that does not have four items a, b, c, and d forming a diamond suborder with a ≤ b ≤ d and a ≤ c ≤ d but with b and c incomparable to each other (also called a diamond-free poset). In computational complexity theory, multitrees have also been called strongly unambiguous graphs or mangroves; they can be used to model nondeterministic algorithms in which there is at most one computational path connecting any two states. Multitrees may be used to represent multiple overlapping taxonomies over the same ground set. If a family tree may contain multiple marriages from one family to another, but does not contain marriages between any two blood relatives, then it forms a multitree. (en) En combinatoire et en théorie des ordres, le terme multi-arbre peut décrire l'une des deux structures suivantes : un graphe orienté acyclique dans lequel l'ensemble des sommets accessibles depuis un nœud est toujours un arbre, ou un ensemble partiellement ordonné dans lequel il n'existe pas quatre éléments a, b, c, et d qui forment un sous-ordre en diamant, avec a ≤ b ≤ d et a ≤ c ≤ d mais où b et c sont incomparables (un tel ensemble ordonné est aussi appelé diamond-free poset (ou ordre partiel sans diamant). (fr)
prov:wasDerivedFrom	wikipedia-en:Multitree?oldid=1110421112&ns=0
page length (characters) of wiki page	4986 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:Multitree
is Link from a Wikipage to another Wikipage of	Arborescence (graph theory) Tree (graph theory) Directed graph Hierarchy Directed acyclic graph Polytree Series-parallel partial order Mangrove (graph theory) Strongly unambiguous graph
is Wikipage redirect of	Mangrove (graph theory) Strongly unambiguous graph
is foaf:primaryTopic of	wikipedia-en:Multitree

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3331 as of Sep 2 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (62 GB total memory, 48 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software