Classi cation Of Problems Of Determining The Maximum Common Fragments For Two Structures Of a Temporal Digraph

Abstract

A new approach is proposed for classifying the problems of determining the maximum common fragments (MCF) for two connected structures included in the T -digraph, based on the type of the maximum common fragment. A tree of classi cation the problems of determining the maximum common fragments (MCF) for two structures tiG; tjG(MCF (tiG; tjG)) included in the T -digraph is proposed. Examples are given for a digraph tG with three types of its fragments (parts), and for ve connectivity types of digraphs. The formulation of six basic problems of determining the maximum common fragments (MCF) for two connected structures included in the T -digraph is given. A classi cation is proposed for an isomorphic embedding of a digraph into another.