Polidrzewo - Polytree

W matematyce , a dokładniej w teorii wykres , A polytree (zwany również skierowane drzewa , zorientowane na drzewo lub pojedynczo połączone w sieci ) jest skierowany acykliczny wykres którego bazowego nieukierunkowane wykres jest drzewo . Innymi słowy, jeśli zastąpimy jego skierowane krawędzie krawędziami nieskierowanymi, otrzymamy graf nieskierowany, który jest zarówno połączony, jak i acykliczny .

Polyforest (lub skierowane lasu lub zorientowane las ) jest skierowany acykliczny wykres którego bazowego nieukierunkowane wykres jest las . Innymi słowy, jeśli zastąpimy jego skierowane krawędzie krawędziami nieskierowanymi, otrzymamy graf nieskierowany, który jest acykliczny.

Polytree jest przykładem grafu zorientowanego .

Termin polytree został ukuty w 1987 roku przez Rebane i Pearl .

Powiązane struktury

• Arborescence jest skierowany zakorzenione drzewo , czyli skierowany graf acykliczny , w których istnieje pojedynczy węzeł źródłowy, który posiada unikalną ścieżkę do każdego innego węzła. Każda arborescencja jest drzewostanem, ale nie każde drzewo jest arborescencją.
• Multitree jest skierowany acykliczny wykres w którym osiągalna subgraph z dowolnego węzła tworzy drzewo. Każde wielodrzewo to wielodrzewo .
• Osiągalność zależność między węzłami polytree tworzy porządek częściowy , który ma wymiarowym co najwyżej trzech. Jeśli wymiar rzędu wynosi trzy, musi istnieć podzbiór siedmiu elementów x , y _i , oraz z _i (dla i = 0, 1, 2 ) taki, że dla każdego i , albo x ≤ y _i ≥ z _i , albo x ≥ y _i ≤ z _i , z tymi sześcioma nierównościami definiującymi strukturę wielodrzewa na tych siedmiu elementach.
• Płot lub zygzak poset jest szczególnym przypadkiem polytree w którym podstawowa drzewo jest ścieżką i krawędzie mają orientacje że alternatywne wzdłuż ścieżki. Osiągalności zamawiania w polytree został również nazywany uogólnione płot .

Wyliczenie

Liczba odrębnych polidrzewa na n nieoznaczonych węzłach, dla n = 1, 2, 3, ..., wynosi

1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180, ... (sekwencja A000238 w OEIS ).

przypuszczenie Sumnera

Hipoteza Sumnera , nazwana na cześć Davida Sumnera, stwierdza, że turnieje są uniwersalnymi grafami dla wielodrzewa, w tym sensie, że każdy turniej z 2 n  − 2 wierzchołkami zawiera jako podgraf każde wielodrzewo z n wierzchołkami. Chociaż pozostaje nierozwiązana, została udowodniona dla wszystkich wystarczająco dużych wartości n .

Aplikacje

Polytrees zostały wykorzystane jako model graficzny do rozumowania probabilistycznego . Jeśli sieć bayesowska ma strukturę wielodrzewa, wówczas propagację przekonań można wykorzystać do skutecznego wnioskowania na jej podstawie.

Drzewo kontur z funkcją o wartościach rzeczywistych na przestrzeni wektorowej jest polytree który opisuje Ustawia poziom tej funkcji. Węzły drzewa konturów to zestawy poziomów, które przechodzą przez punkt krytyczny funkcji, a krawędzie opisują ciągłe zestawy zestawów poziomów bez punktu krytycznego. Orientacja krawędzi jest określana przez porównanie wartości funkcji na odpowiednich dwóch zestawach poziomów.

Zobacz też

• Słowniczek teorii grafów

Uwagi

Bibliografia

• Carr, Hamish; Snoeyink, Jack; Axen, Ulrike (2000), "Obliczanie drzew konturowych we wszystkich wymiarach", w Proc. XI Sympozjum ACM-SIAM na temat algorytmów dyskretnych (SODA 2000) , s. 918–926
• Dasgupta, Sanjoy (1999), "Nauka wielodrzewa", w Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Sztokholm, Szwecja, lipiec-sierpień 1999 (PDF) , s. 134-141.
• Deo, Narsingh (1974), Teoria grafów z zastosowaniami w inżynierii i informatyce (PDF) , Englewood, New Jersey: Prentice-Hall, ISBN 0-13-363473-6.
• Harary, Frank ; Sumner, David (1980), „Dichromatyczna liczba zorientowanego drzewa”, Journal of Combinatorics, Information & System Sciences , 5 (3): 184-187, MR  0603363.
• Kim, Jin H.; Pearl, Judea (1983), „Model obliczeniowy do rozumowania przyczynowego i diagnostycznego w silnikach wnioskowania”, w Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI 1983), Karlsruhe, Niemcy, sierpień 1983 (PDF) , s. 190–193.
• Kuhn, Daniela ; Mycroft, Richard; Osthus, Deryk (2011), „Dowód na uniwersalną hipotezę Sumnera dotyczącą turniejów na duże turnieje”, Proceedings of the London Mathematical Society , Third Series, 102 (4): 731–766, arXiv : 1010.4430 , doi : 10.1112/plms/pdq035 , MR  2793448.
• Rebane, George; Pearl, Judea (1987), „Odzyskiwanie przyczynowych drzew poli z danych statystycznych”, w Proc. 3. doroczna konferencja nt. niepewności w sztucznej inteligencji (UAI 1987), Seattle, WA, USA, lipiec 1987 (PDF) , s. 222–228.
• Simion, Rodica (1991), "Drzewa z 1-czynnikami i drzewami zorientowanymi", Matematyka dyskretna , 88 (1): 93-104, doi : 10.1016/0012-365X (91) 90061-6 , MR  1099270.
• Trotter, William T., Jr.; Moore, John I., Jr. (1977), "Wymiar płaskich posetów", Journal of Combinatorial Theory , Seria B , 22 (1): 54-67, doi : 10.1016/0095-8956 (77) 90048-X.