Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математикада, әсіресе графтар теориясында, полидерек (сонымен қатар бағытталған ағаш, бағдарланған ағаш немесе бір байланысты желі деп аталады) – негізгі бағытсыз графигі ағаш болатын бағытталған ациклді граф. Яғни, егер оның бағытталған қабырғаларын бағытталмаған қабырғалармен алмастырсақ, біз байланысты және ациклді бағытталмаған граф аламыз. Полиорман (немесе бағытталған орман немесе бағдарланған орман) – негізгі бағытсыз графигі орман болатын бағытталған ациклді граф. Яғни, егер оның бағытталған қабырғаларын бағытталмаған қабырғалармен алмастырсақ, біз ациклді бағытталмаған граф аламыз. Полидерек – бағдарланған графтың мысалы. Полидерек термині 1987 жылы Ребейн және Перл есімді ғалымдар тарапынан ұсынылған.
In mathematics, and more specifically in graph theory, a polytree (also called directed tree, oriented tree or singly connected network) is a directed acyclic graph whose underlying undirected graph is a tree. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is both connected and acyclic. A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is acyclic. A polytree is an example of an oriented graph. The term polytree was coined in 1987 by Rebane and Pearl.
Қатынасты құрылымдар
Арбосценция – бағытталған тамырлы ағаш, яғни, барлық басқа түйіндерге бірегей жолы бар бір ғана бастапқы түйін болатын бағытталған ациклдік граф. Кез келген арбосценция – полидере, бірақ кез келген полидере арбосценция емес. Полидере – кез келген түйінден қол жетімді болатын кішіграф ағаш құрайтын бағытталған ациклдік граф. Кез келген полидере – көп ағаш. Полидере түйіндері арасындағы қолжетімділік қатынасы ең көп дегенде үш өлшемді ішінара тәртіп құрайды. Егер тәртіп өлшемі үш болса, онда жеті элементтен тұратын , , және (for) жиынтығы болуы керек, әрқайсысы үшін , немесе , осы алты теңсіздікпен осы жеті элементтегі полидере құрылымын анықтайды. Қоршау немесе зигзаг позит – полидеренің ерекше жағдайы, онда негізгі ағаш – жол және қабырғалардың бағыттары жол бойымен кезектеседі. Полидередегі қолжетімділік тәртібі сондай-ақ жалпыланған қоршау деп аталады.
An arborescence is a directed rooted tree, i. e. a directed acyclic graph in which there exists a single source node that has a unique path to every other node. Every arborescence is a polytree, but not every polytree is an arborescence. A multitree is a directed acyclic graph in which the subgraph reachable from any node forms a tree. Every polytree is a multitree. The reachability relationship among the nodes of a polytree forms a partial order that has order dimension at most three. If the order dimension is three, there must exist a subset of seven elements , , and (for ) such that, for each , either or , with these six inequalities defining the polytree structure on these seven elements. A fence or zigzag poset is a special case of a polytree in which the underlying tree is a path and the edges have orientations that alternate along the path. The reachability ordering in a polytree has also been called a generalized fence.
Самнер болжамы
Дэвид Самнердің есімімен аталатын Самнердің болжамы, турнирлердің политрилер үшін әмбебап графтар екенін білдіреді, яғни кез келген n төбелі турнирде n төбелі кез келген политри субграф ретінде кездеседі. Бұл болжам әлі шешілмегенімен, n жеткілікті түрде үлкен мәндер үшін дәлелденген.
Sumner's conjecture, named after David Sumner, states that tournaments are universal graphs for polytrees, in the sense that every tournament with vertices contains every polytree with vertices as a subgraph. Although it remains unsolved, it has been proven for all sufficiently large values of .
Қолданбалар
Полидеректер ықтималдық есептеулер үшін графикалық модель ретінде қолданылған. Егер Байес желісі полидерек құрылымына ие болса, онда сенім тарату арқылы оған тиімді түрде қорытынды жасауға болады. Векторлық кеңістіктегі нақты мәнді функцияның контур ағашы – функцияның деңгейлік жиындарын сипаттайтын полидерек. Контур ағашының түйіндері – функцияның сындық нүктесі арқылы өтетін деңгейлік жиындар, ал қабырғалары – сындық нүктесі жоқ деңгейлік жиындардың тікелей байланысқан жиындарын сипаттайды. Қабырғаның бағыты – сәйкес екі деңгейлік жиындағы функция мәндерін салыстыру арқылы анықталады.
Polytrees have been used as a graphical model for probabilistic reasoning. If a Bayesian network has the structure of a polytree, then belief propagation may be used to perform inference efficiently on it. The contour tree of a real valued function on a vector space is a polytree that describes the level sets of the function. The nodes of the contour tree are the level sets that pass through a critical point of the function and the edges describe contiguous sets of level sets without a critical point. The orientation of an edge is determined by the comparison between the function values on the corresponding two level sets.