### Junction Tree Construction

```JUNCTION TREE
CONSTRUCTION
Practice exercise
Example 1: Junction Tree Construction
2
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
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
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
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
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
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
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
```