please answer the question below:

(a) If support is defined in terms of induced subgraph relationship, show
that the confidence of the rule g1 ?? g2 can be greater than 1 if g1 and
g2 are allowed to have overlapping vertex sets.
What is the time complexity needed to determine the canonical label
of a graph that contains |V | vertices?
(c) The core of a subgraph can have multiple automorphisms. This will
increase the number of candidate subgraphs obtained after merging two
frequent subgraphs that share the same core. Determine the maximum
number of candidate subgraphs obtained due to automorphism of a core
of size k.
Two frequent subgraphs of size k may share multiple cores. Determine
the maximum number of cores that can be shared by the two frequent
subgraphs.

(a) We illustrate this with an example. Consider the five graphs, G1, G2,

··· , G5, shown in Figure 7.6. The graph g1 shown on the top-right hand



support of g2, we obtain a confidence value greater than 1 because

s(g3) > s(g2).

(b) A na ??ve approach requires |V |! computations to examine all possible

permutations of the canonical label.

(c) k.

(d) k ? 1.