Report

JUNCTION TREE CONSTRUCTION Practice exercise Example 1: Junction Tree Construction 2 Step1: Insert link between parents of common child A D B E C G F H Example 1: Junction Tree Construction 3 Step2: Convert into undirected graph A D B A E C D B E C G F H G F H Example 1: Junction Tree Construction 4 Step3: Triangulate a graph if it has circle of length>3 A D B E C G F Note : No need of triangulation in this example. H Example 1: Junction Tree Construction 5 Step3: Numbered the node if its numbered neighboured nodes are connected together. 1 A 5 2 B 4 3 D E C 6 F 7 H 8 G Example 1: Junction Tree Construction 6 Definition: A Clique in a graph is set of adjacent vertices which is a complete graph. Five cliques are found in Example 1: •One clique of four nodes •Four cliques of three nodes ABCDE 4 1 A 5 ACD CDF Step4: Ordered the node by max cardinality search. 6 5 7 8 4 E C 6 EHG B 3 D CEH 2 F 7 H 8 G Example 1: Junction Tree Construction 7 Construct Tree ABCDE 4 ACD 5 ABCDE ACD CEH CDF 6 CEH 7 EHG CDF EHG 8 Example 2: Junction Tree Construction 8 Step1: Insert link between parents of common child A B C D E F G H I Example 2: Junction Tree Construction 9 Step2: Convert into undirected graph A A B C D E F G H I B C D E F G H I Example 2: Junction Tree Construction 10 Step3: Triangulate a graph if it has circle of length>3 A B C D E F G H I Example 2: Junction Tree Construction 11 Step3: Numbered the node if its numbered neighboured nodes are connected together. 1 A 2 4 3 B C D F G 5 E H I F has three numbered neighbour B, C and D where B and D are not connected therefore add link between B and D and restart numbering again from beginning. Example 2: Junction Tree Construction 12 Step3: Numbered the node if its numbered neighboured nodes are connected together. 1 A 2 4 3 B C D 5 6 E 7 F H 8 G I 9 Example 2: Junction Tree Construction 13 Five cliques are found in Example 2: •Two cliques of four nodes •Four cliques of three nodes Step4: Ordered the node by max cardinality search. Clique Nodes Max Cardinality ABCD 4 BCDF 5 BEF 6 DFG 7 1 A 2 B C FGI D 5 6 E EFH 4 3 7 F G 8 9 H 8 I 9 Example 2: Junction Tree Construction 14 Construct Tree ABCD ABCD 4 BCDF 5 BEF 6 DFG 7 BCDF BEF DFG EFH FGI EFH FGI 8 9 Example 2: Junction Tree Construction (with different triangulation ) 15 Step1: Insert link between parents of common child A B C D E F G H I Example 2: Junction Tree Construction 16 Step2: Convert into undirected graph A A B C D E F G H I B C D E F G H I Example 2: Junction Tree Construction 17 Step3: Triangulate a graph if it has circle of length>3 A B C D E F G H I Example 2: Junction Tree Construction 18 Step3: Numbered the node if its numbered neighboured nodes are connected together. 1 A 2 4 3 B C D 6 5 E 7 F H G I G has three numbered neighbour F, C and D where F and D are not connected therefore add link between F and D and restart numbering again from beginning. Example 2: Junction Tree Construction 19 Step3: Numbered the node if its numbered neighboured nodes are connected together. 1 A 2 4 3 B C D 6 5 E F H G I F has three numbered neighbour E, C and D where E and D are not connected therefore add link between E and D and restart numbering again from beginning. Example 2: Junction Tree Construction 20 Step3: Numbered the node if its numbered neighboured nodes are connected together. 1 A 2 4 3 B C D E F G 5 H I E has three numbered neighbour B, C and D where B and D are not connected therefore add link between B and D and restart numbering again from beginning. Example 2: Junction Tree Construction 21 Step3: Numbered the node if its numbered neighboured nodes are connected together. 1 A 2 4 3 B C D 6 5 E G 7 F H 8 I 9 Example 2: Junction Tree Construction 22 Cliques are found in Example 2: •Four cliques of four nodes. •Two cliques of three nodes. Step4: Ordered the node by max cardinality search. Clique Nodes Max Cardinality ABCD 4 BCDE 5 CDEF 6 CDFG 7 1 A 2 B C 8 FGI 9 D 6 5 EFH 4 3 E G 7 F H 8 I 9 Example 2: Junction Tree Construction 23 Construct Tree ABCD BCDE CDEF EFH CDFG FGI ABCD 4 BCDE 5 CDEF 6 CDFG 7 EFH 8 FGI 9