25:
776:
769:
374:
367:
360:
252:
Given an ordered graph, its induced graph is another ordered graph obtained by joining some pairs of nodes that are both parents of another node. In particular, nodes are considered in turn according to the ordering, from last to first. For each node, if two of its parents are not joined by an edge,
720:
Processing nodes in order matters, as the introduced edges may create new parents, which are then relevant to the introduction of new edges. The following example shows that a different ordering produces a different induced graph of the same original graph. The ordering is the same as above but
172:
352:
As an example, the induced graph of an ordered graph is calculated. The ordering is represented by the position of its nodes in the figures: a is the last node and d is the first.
1134:
210:
236:
343:
1049:
1029:
1009:
989:
969:
949:
929:
909:
889:
869:
844:
821:
801:
759:
739:
715:
692:
672:
652:
632:
612:
592:
572:
552:
529:
509:
489:
469:
449:
424:
402:
311:
291:
271:
134:
114:
1051:
has no parent as well, the final induced graph is the one above. This induced graph differs from the one produced by the previous ordering.
46:
1090:
68:
96:
In an ordered graph, the parents of a node are the nodes that are adjacent to it and precede it in the ordering. More precisely,
1129:
238:. The width of a node is the number of its parents, and the width of an ordered graph is the maximal width of its nodes.
86:
345:
is added to the graph. Since the parents of a node are always connected with each other, the induced graph is always
39:
33:
245:
of an ordered graph is obtained by adding some edges to an ordering graph, using the method outlined below. The
50:
911:. Therefore, an edge between them is added. According to the new order, the second node that is considered is
139:
177:
1086:
1065:
215:
316:
1060:
1034:
1014:
994:
974:
954:
934:
914:
894:
874:
854:
829:
806:
786:
744:
724:
700:
677:
657:
637:
617:
597:
577:
557:
537:
514:
494:
474:
454:
434:
409:
387:
296:
276:
256:
119:
99:
1123:
346:
1079:
90:
1031:
are not joined this time. As a result, no new edge is introduced. Since
775:
768:
373:
366:
359:
531:
in the ordering. Since they are not joined by an edge, one is added.
951:). Therefore, no new edge is added. The third considered node is
18:
717:
does not produce any change, as this node has no parents.
594:
as a parent in the partially built induced graph. Indeed,
313:
are parents of it and are not joined by an edge, the edge
253:
that edge is added. In other words, when considering node
249:
of an ordered graph is the width of its induced graph.
1037:
1017:
997:
977:
957:
937:
917:
897:
877:
857:
832:
809:
789:
747:
727:
703:
680:
660:
640:
620:
600:
580:
560:
540:
517:
497:
477:
457:
437:
412:
390:
319:
299:
279:
259:
218:
180:
142:
122:
102:
1043:
1023:
1003:
983:
963:
943:
923:
903:
883:
863:
838:
815:
795:
753:
733:
709:
686:
666:
646:
626:
606:
586:
566:
546:
523:
503:
483:
463:
443:
418:
396:
337:
305:
285:
265:
230:
204:
166:
128:
108:
574:as a parent in the original graph, it also has
554:is considered second. While this node only has
1113:Page 87 Dechter. (2003). Constraint Processing
1104:Page 86 Dechter. (2003). Constraint Processing
654:in the ordering. As a result, an edge joining
8:
161:
143:
1036:
1016:
996:
976:
956:
936:
916:
896:
876:
856:
831:
808:
788:
746:
726:
702:
679:
659:
639:
619:
599:
579:
559:
539:
516:
496:
476:
456:
436:
411:
389:
318:
298:
278:
258:
217:
179:
141:
121:
101:
69:Learn how and when to remove this message
1135:Extensions and generalizations of graphs
167:{\displaystyle \langle N,E,<\rangle }
32:This article includes a list of general
1097:
16:Graph with a total order over its nodes
406:Edge added considering the parents of
384:Edge added considering the parents of
451:is considered first. Its parents are
7:
38:it lacks sufficient corresponding
14:
931:. This node has only one parent (
763:
354:
774:
767:
372:
365:
358:
23:
851:As in the previous case, both
332:
320:
193:
181:
1:
783:Same graph, but the order of
491:, as they are both joined to
1151:
205:{\displaystyle (n,m)\in E}
826:Graph after considering
53:more precise citations.
1130:Constraint programming
1078:Dechter, Rina (2003).
1045:
1025:
1005:
985:
965:
945:
925:
905:
885:
865:
840:
817:
797:
755:
735:
711:
688:
668:
648:
628:
608:
588:
568:
548:
525:
505:
485:
465:
445:
420:
398:
339:
307:
287:
267:
232:
231:{\displaystyle n<m}
206:
168:
130:
110:
1081:Constraint Processing
1046:
1026:
1006:
986:
971:. Its only parent is
966:
946:
926:
906:
886:
866:
841:
818:
798:
756:
736:
712:
689:
669:
649:
629:
609:
589:
569:
549:
526:
506:
486:
466:
446:
421:
399:
340:
338:{\displaystyle (m,l)}
308:
288:
268:
233:
207:
169:
136:in the ordered graph
131:
111:
1035:
1015:
995:
975:
955:
935:
915:
895:
875:
855:
830:
807:
787:
745:
725:
701:
678:
658:
638:
618:
598:
578:
558:
538:
515:
495:
475:
455:
435:
410:
388:
381:The original graph.
317:
297:
277:
257:
216:
178:
140:
120:
100:
1084:. Morgan Kaufmann.
1041:
1021:
1001:
981:
961:
941:
921:
901:
881:
861:
836:
813:
793:
751:
731:
707:
684:
664:
644:
624:
604:
584:
564:
544:
521:
501:
481:
461:
441:
416:
394:
335:
303:
283:
263:
228:
202:
164:
126:
106:
1066:Local consistency
1044:{\displaystyle d}
1024:{\displaystyle c}
1004:{\displaystyle b}
984:{\displaystyle d}
964:{\displaystyle b}
944:{\displaystyle b}
924:{\displaystyle c}
904:{\displaystyle a}
884:{\displaystyle c}
864:{\displaystyle b}
849:
848:
839:{\displaystyle a}
816:{\displaystyle c}
796:{\displaystyle b}
754:{\displaystyle c}
734:{\displaystyle b}
710:{\displaystyle d}
687:{\displaystyle d}
667:{\displaystyle c}
647:{\displaystyle b}
634:and also precede
627:{\displaystyle b}
607:{\displaystyle c}
587:{\displaystyle c}
567:{\displaystyle d}
547:{\displaystyle b}
524:{\displaystyle a}
511:and both precede
504:{\displaystyle a}
484:{\displaystyle c}
464:{\displaystyle b}
444:{\displaystyle a}
429:
428:
419:{\displaystyle b}
397:{\displaystyle a}
306:{\displaystyle l}
286:{\displaystyle m}
266:{\displaystyle n}
129:{\displaystyle m}
109:{\displaystyle n}
79:
78:
71:
1142:
1114:
1111:
1105:
1102:
1085:
1050:
1048:
1047:
1042:
1030:
1028:
1027:
1022:
1010:
1008:
1007:
1002:
990:
988:
987:
982:
970:
968:
967:
962:
950:
948:
947:
942:
930:
928:
927:
922:
910:
908:
907:
902:
890:
888:
887:
882:
870:
868:
867:
862:
845:
843:
842:
837:
822:
820:
819:
814:
802:
800:
799:
794:
778:
771:
764:
760:
758:
757:
752:
740:
738:
737:
732:
716:
714:
713:
708:
693:
691:
690:
685:
673:
671:
670:
665:
653:
651:
650:
645:
633:
631:
630:
625:
613:
611:
610:
605:
593:
591:
590:
585:
573:
571:
570:
565:
553:
551:
550:
545:
530:
528:
527:
522:
510:
508:
507:
502:
490:
488:
487:
482:
470:
468:
467:
462:
450:
448:
447:
442:
425:
423:
422:
417:
403:
401:
400:
395:
376:
369:
362:
355:
344:
342:
341:
336:
312:
310:
309:
304:
292:
290:
289:
284:
272:
270:
269:
264:
237:
235:
234:
229:
211:
209:
208:
203:
173:
171:
170:
165:
135:
133:
132:
127:
115:
113:
112:
107:
93:over its nodes.
74:
67:
63:
60:
54:
49:this article by
40:inline citations
27:
26:
19:
1150:
1149:
1145:
1144:
1143:
1141:
1140:
1139:
1120:
1119:
1118:
1117:
1112:
1108:
1103:
1099:
1077:
1074:
1057:
1033:
1032:
1013:
1012:
993:
992:
973:
972:
953:
952:
933:
932:
913:
912:
893:
892:
891:are parents of
873:
872:
853:
852:
828:
827:
805:
804:
785:
784:
743:
742:
723:
722:
699:
698:
676:
675:
656:
655:
636:
635:
616:
615:
596:
595:
576:
575:
556:
555:
536:
535:
513:
512:
493:
492:
473:
472:
453:
452:
433:
432:
408:
407:
386:
385:
315:
314:
295:
294:
275:
274:
255:
254:
214:
213:
176:
175:
138:
137:
118:
117:
116:is a parent of
98:
97:
75:
64:
58:
55:
45:Please help to
44:
28:
24:
17:
12:
11:
5:
1148:
1146:
1138:
1137:
1132:
1122:
1121:
1116:
1115:
1106:
1096:
1095:
1094:
1093:
1073:
1070:
1069:
1068:
1063:
1061:Directed graph
1056:
1053:
1040:
1020:
1000:
980:
960:
940:
920:
900:
880:
860:
847:
846:
835:
824:
812:
792:
780:
779:
772:
750:
730:
706:
683:
663:
643:
623:
603:
583:
563:
543:
520:
500:
480:
460:
440:
427:
426:
415:
404:
393:
382:
378:
377:
370:
363:
334:
331:
328:
325:
322:
302:
282:
262:
227:
224:
221:
201:
198:
195:
192:
189:
186:
183:
163:
160:
157:
154:
151:
148:
145:
125:
105:
77:
76:
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
1147:
1136:
1133:
1131:
1128:
1127:
1125:
1110:
1107:
1101:
1098:
1092:
1091:1-55860-890-7
1088:
1083:
1082:
1076:
1075:
1071:
1067:
1064:
1062:
1059:
1058:
1054:
1052:
1038:
1018:
998:
978:
958:
938:
918:
898:
878:
858:
833:
825:
810:
790:
782:
781:
777:
773:
770:
766:
765:
762:
761:are swapped.
748:
728:
718:
704:
695:
681:
661:
641:
621:
614:is joined to
601:
581:
561:
541:
532:
518:
498:
478:
458:
438:
413:
405:
391:
383:
380:
379:
375:
371:
368:
364:
361:
357:
356:
353:
350:
348:
329:
326:
323:
300:
280:
260:
250:
248:
247:induced width
244:
243:induced graph
239:
225:
222:
219:
199:
196:
190:
187:
184:
158:
155:
152:
149:
146:
123:
103:
94:
92:
88:
84:
83:ordered graph
73:
70:
62:
52:
48:
42:
41:
35:
30:
21:
20:
1109:
1100:
1080:
850:
719:
697:Considering
696:
533:
430:
351:
251:
246:
242:
240:
95:
82:
80:
65:
56:
37:
823:is swapped
91:total order
51:introducing
1124:Categories
1072:References
991:. Indeed,
694:is added.
273:, if both
59:March 2010
34:references
197:∈
162:⟩
144:⟨
1055:See also
347:chordal
89:with a
47:improve
1089:
36:, but
534:Node
431:Node
87:graph
85:is a
1087:ISBN
1011:and
871:and
803:and
741:and
674:and
471:and
293:and
241:The
223:<
212:and
159:<
174:if
81:An
1126::
349:.
1039:d
1019:c
999:b
979:d
959:b
939:b
919:c
899:a
879:c
859:b
834:a
811:c
791:b
749:c
729:b
705:d
682:d
662:c
642:b
622:b
602:c
582:c
562:d
542:b
519:a
499:a
479:c
459:b
439:a
414:b
392:a
333:)
330:l
327:,
324:m
321:(
301:l
281:m
261:n
226:m
220:n
200:E
194:)
191:m
188:,
185:n
182:(
156:,
153:E
150:,
147:N
124:m
104:n
72:)
66:(
61:)
57:(
43:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
