17:
619:
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.
68:. (It is required that no two undirected edges are replaced by the same directed edge; i.e. there must be no pair of vertices linked in the directed graph by edges in both directions.)
381:
335:
469:
263:
224:
197:
534:
126:
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.
574:
554:
425:
287:
170:
390:
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
874:
481:
87:. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is acyclic.
872:; Mycroft, Richard; Osthus, Deryk (2011), "A proof of Sumner's universal tournament conjecture for large tournaments",
812:
857:
in Proc. 8th
International Joint Conference on Artificial Intelligence (IJCAI 1983), Karlsruhe, Germany, August 1983
1043:
786:
in Proc. 15th
Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Sweden, July-August 1999
1005:
920:
in Proc. 3rd Annual
Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987
971:
556:
vertices as a subgraph. Although it remains unsolved, it has been proven for all sufficiently large values of
1038:
133:
is a directed acyclic graph in which the subgraph reachable from any node forms a tree. Every polytree is a
616:
340:
294:
115:
61:
91:
500:
430:
629:
589:
772:
Carr, Hamish; Snoeyink, Jack; Axen, Ulrike (2000), "Computing contour trees in all dimensions",
84:
492:
123:
49:
918:
230:
152:
at most three. If the order dimension is three, there must exist a subset of seven elements
992:
958:
905:
842:
202:
175:
65:
854:(1983), "A computational model for causal and diagnostic reasoning in inference engines",
799:
510:
8:
387:
119:
53:
1000:
883:
855:
597:
559:
539:
410:
272:
155:
615:
of the function. The nodes of the contour tree are the level sets that pass through a
383:, with these six inequalities defining the polytree structure on these seven elements.
1020:
984:
808:
1015:
980:
946:
893:
784:
593:
988:
954:
937:
901:
838:
585:
504:
149:
869:
773:
1032:
966:
145:
57:
932:
826:
822:
608:
604:
496:
391:
141:
29:
897:
474:
1, 1, 3, 8, 27, 91, 350, 1376, 5743, 24635, 108968, 492180, ... (sequence
914:
851:
102:
25:
950:
612:
134:
130:
83:) is a directed acyclic graph whose underlying undirected graph is a
917:(1987), "The recovery of causal poly-trees from statistical data",
775:
in Proc. 11th ACM-SIAM Symposium on
Discrete Algorithms (SODA 2000)
888:
801:
Graph Theory with
Applications to Engineering and Computer Science
60:
with undirected edges, we obtain an undirected graph that is both
935:(1989), "Transposition generation of alternating permutations",
1003:; Moore, John I. Jr. (1977), "The dimension of planar posets",
738:
831:
750:
476:
16:
714:
507:
for polytrees, in the sense that every tournament with
829:(1980), "The dichromatic number of an oriented tree",
646:
644:
562:
542:
513:
433:
413:
343:
297:
275:
233:
205:
178:
158:
600:
may be used to perform inference efficiently on it.
969:(1991), "Trees with 1-factors and oriented trees",
641:
144:relationship among the nodes of a polytree forms a
568:
548:
528:
463:
419:
375:
329:
281:
257:
218:
191:
164:
868:
744:
726:
656:
1030:
771:
756:
783:Dasgupta, Sanjoy (1999), "Learning polytrees",
875:Proceedings of the London Mathematical Society
394:ordering in a polytree has also been called a
999:
821:
720:
674:
912:
708:
1019:
887:
849:
807:, Englewood, New Jersey: Prentice-Hall,
782:
693:
650:
15:
52:whose underlying undirected graph is a
1031:
965:
931:
732:
704:
702:
689:
687:
678:
596:has the structure of a polytree, then
536:vertices contains every polytree with
487:
376:{\displaystyle x\geq y_{i}\leq z_{i}}
330:{\displaystyle x\leq y_{i}\geq z_{i}}
108:
407:The number of distinct polytrees on
56:. In other words, if we replace its
797:
699:
684:
662:
13:
14:
1055:
745:KĂĽhn, Mycroft & Osthus (2011)
611:is a polytree that describes the
101:was coined in 1987 by Rebane and
757:Carr, Snoeyink & Axen (2000)
1006:Journal of Combinatorial Theory
607:of a real-valued function on a
579:
90:A polytree is an example of an
668:
584:Polytrees have been used as a
464:{\displaystyle n=1,2,3,\dots }
402:
1:
765:
1021:10.1016/0095-8956(77)90048-X
985:10.1016/0012-365X(91)90061-6
7:
623:
28:, and more specifically in
10:
1060:
721:Trotter & Moore (1977)
675:Harary & Sumner (1980)
709:Rebane & Pearl (1987)
635:
630:Glossary of graph theory
46:singly connected network
1044:Directed acyclic graphs
1001:Trotter, William T. Jr.
590:probabilistic reasoning
258:{\displaystyle i=0,1,2}
798:Deo, Narsingh (1974),
694:Kim & Pearl (1983)
570:
550:
530:
465:
421:
377:
331:
283:
259:
220:
193:
166:
124:directed acyclic graph
50:directed acyclic graph
21:
571:
551:
531:
466:
427:unlabeled nodes, for
422:
378:
332:
284:
260:
221:
219:{\displaystyle z_{i}}
194:
192:{\displaystyle y_{i}}
167:
118:is a directed rooted
19:
1039:Trees (graph theory)
972:Discrete Mathematics
560:
540:
529:{\displaystyle 2n-2}
511:
431:
411:
341:
295:
273:
231:
203:
176:
156:
898:10.1112/plms/pdq035
493:Sumner's conjecture
488:Sumner's conjecture
951:10.1007/BF00563523
926:, pp. 222–228
863:, pp. 190–193
792:, pp. 134–141
778:, pp. 918–926
598:belief propagation
566:
546:
526:
461:
417:
373:
327:
279:
255:
216:
189:
162:
109:Related structures
22:
569:{\displaystyle n}
549:{\displaystyle n}
420:{\displaystyle n}
396:generalized fence
282:{\displaystyle i}
165:{\displaystyle x}
1051:
1024:
1023:
995:
961:
927:
925:
913:Rebane, George;
908:
891:
878:, Third Series,
864:
862:
845:
817:
806:
793:
791:
779:
760:
754:
748:
742:
736:
730:
724:
718:
712:
706:
697:
691:
682:
672:
666:
660:
654:
648:
594:Bayesian network
575:
573:
572:
567:
555:
553:
552:
547:
535:
533:
532:
527:
505:universal graphs
479:
470:
468:
467:
462:
426:
424:
423:
418:
382:
380:
379:
374:
372:
371:
359:
358:
336:
334:
333:
328:
326:
325:
313:
312:
290:
288:
286:
285:
280:
266:
264:
262:
261:
256:
225:
223:
222:
217:
215:
214:
198:
196:
195:
190:
188:
187:
171:
169:
168:
163:
1059:
1058:
1054:
1053:
1052:
1050:
1049:
1048:
1029:
1028:
923:
860:
815:
804:
789:
768:
763:
755:
751:
743:
739:
731:
727:
719:
715:
707:
700:
692:
685:
673:
669:
661:
657:
651:Dasgupta (1999)
649:
642:
638:
626:
586:graphical model
582:
561:
558:
557:
541:
538:
537:
512:
509:
508:
490:
485:
475:
432:
429:
428:
412:
409:
408:
405:
367:
363:
354:
350:
342:
339:
338:
321:
317:
308:
304:
296:
293:
292:
274:
271:
270:
268:
267:such that, for
232:
229:
228:
226:
210:
206:
204:
201:
200:
183:
179:
177:
174:
173:
157:
154:
153:
150:order dimension
111:
81:oriented forest
77:directed forest
12:
11:
5:
1057:
1047:
1046:
1041:
1027:
1026:
997:
967:Simion, Rodica
963:
945:(3): 227–233,
929:
910:
882:(4): 731–766,
866:
847:
837:(3): 184–187,
819:
813:
795:
780:
767:
764:
762:
761:
749:
737:
725:
713:
698:
683:
667:
665:, p. 206.
655:
639:
637:
634:
633:
632:
625:
622:
617:critical point
581:
578:
565:
545:
525:
522:
519:
516:
499:, states that
495:, named after
489:
486:
473:
460:
457:
454:
451:
448:
445:
442:
439:
436:
416:
404:
401:
400:
399:
384:
370:
366:
362:
357:
353:
349:
346:
324:
320:
316:
311:
307:
303:
300:
278:
254:
251:
248:
245:
242:
239:
236:
213:
209:
186:
182:
161:
138:
127:
110:
107:
92:oriented graph
58:directed edges
9:
6:
4:
3:
2:
1056:
1045:
1042:
1040:
1037:
1036:
1034:
1022:
1017:
1013:
1009:
1007:
1002:
998:
994:
990:
986:
982:
979:(1): 93–104,
978:
974:
973:
968:
964:
960:
956:
952:
948:
944:
940:
939:
934:
933:Ruskey, Frank
930:
922:
921:
916:
911:
907:
903:
899:
895:
890:
885:
881:
877:
876:
871:
870:KĂĽhn, Daniela
867:
859:
858:
853:
850:Kim, Jin H.;
848:
844:
840:
836:
832:
828:
827:Sumner, David
824:
823:Harary, Frank
820:
816:
814:0-13-363473-6
810:
803:
802:
796:
788:
787:
781:
777:
776:
770:
769:
758:
753:
746:
741:
734:
733:Ruskey (1989)
729:
722:
717:
710:
705:
703:
695:
690:
688:
680:
679:Simion (1991)
676:
671:
664:
659:
652:
647:
645:
640:
631:
628:
627:
621:
618:
614:
610:
606:
601:
599:
595:
591:
587:
577:
563:
543:
523:
520:
517:
514:
506:
502:
498:
494:
483:
478:
472:
458:
455:
452:
449:
446:
443:
440:
437:
434:
414:
397:
393:
389:
385:
368:
364:
360:
355:
351:
347:
344:
322:
318:
314:
309:
305:
301:
298:
276:
252:
249:
246:
243:
240:
237:
234:
211:
207:
184:
180:
159:
151:
147:
146:partial order
143:
139:
136:
132:
128:
125:
121:
117:
113:
112:
106:
104:
100:
95:
93:
88:
86:
82:
78:
74:
69:
67:
63:
59:
55:
51:
47:
43:
42:oriented tree
39:
38:directed tree
36:(also called
35:
31:
27:
18:
1014:(1): 54–67,
1011:
1004:
976:
970:
942:
936:
919:
915:Pearl, Judea
879:
873:
856:
852:Pearl, Judea
834:
830:
800:
785:
774:
752:
740:
728:
716:
670:
658:
609:vector space
605:contour tree
602:
583:
580:Applications
497:David Sumner
491:
406:
395:
392:reachability
142:reachability
116:arborescence
98:
96:
89:
80:
76:
72:
70:
45:
41:
37:
33:
30:graph theory
23:
501:tournaments
403:Enumeration
26:mathematics
1033:Categories
1008:, Series B
766:References
663:Deo (1974)
613:level sets
73:polyforest
20:A polytree
889:1010.4430
521:−
459:…
361:≤
348:≥
315:≥
302:≤
148:that has
135:multitree
131:multitree
122:, i.e. a
97:The term
62:connected
624:See also
99:polytree
34:polytree
993:1099270
959:1048093
906:2793448
843:0603363
592:. If a
480:in the
477:A000238
291:either
66:acyclic
48:) is a
991:
957:
904:
841:
811:
199:, and
85:forest
938:Order
924:(PDF)
884:arXiv
861:(PDF)
805:(PDF)
790:(PDF)
636:Notes
471:, is
388:fence
269:each
227:(for
103:Pearl
809:ISBN
603:The
588:for
503:are
482:OEIS
140:The
120:tree
75:(or
64:and
54:tree
32:, a
1016:doi
981:doi
947:doi
894:doi
880:102
337:or
114:An
79:or
44:or
24:In
1035::
1012:22
1010:,
989:MR
987:,
977:88
975:,
955:MR
953:,
941:,
902:MR
900:,
892:,
839:MR
833:,
825:;
701:^
686:^
677:;
643:^
576:.
484:).
386:A
172:,
129:A
105:.
94:.
71:A
40:,
1025:.
1018::
996:.
983::
962:.
949::
943:6
928:.
909:.
896::
886::
865:.
846:.
835:5
818:.
794:.
759:.
747:.
735:.
723:.
711:.
696:.
681:.
653:.
564:n
544:n
524:2
518:n
515:2
456:,
453:3
450:,
447:2
444:,
441:1
438:=
435:n
415:n
398:.
369:i
365:z
356:i
352:y
345:x
323:i
319:z
310:i
306:y
299:x
289:,
277:i
265:)
253:2
250:,
247:1
244:,
241:0
238:=
235:i
212:i
208:z
185:i
181:y
160:x
137:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
