
Accession Number : AD0673420
Title : CONVEXITY IN GRAPHS: MATHEMATICAL PRELIMINARIES TO A THEORY OF GRAPH GRAMMARS,
Corporate Author : MARYLAND UNIV COLLEGE PARK COMPUTER SCIENCE CENTER
Personal Author(s) : Pfaltz,John L.
Report Date : JUL 1968
Pagination or Media Count : 103
Abstract : A natural concept of convexity for directed graphs is introduced, and properties of the lattice of convex subgraphs of a graph are studied. The extent to which this lattice determines the graph is established, and conditions for a lattice to be a convex subgraph lattice are investigated. The concept of a lower semihomomorphism is defined for lattices; it is shown that such mappings preserve basic properties of convex subgraph lattices, and that on such lattices, they are uniquely determined by their kernels. Graph homomorphisms which preserve convexity are also studied, with emphasis on their relationship to lower semihomomorphisms of the convex subgraph lattice. Homomorphisms which 'contract' subgraphs (which are analogous to the rewriting rules of contextsensitive phrase structure grammars) are briefly considered. Finally, a concept of local convexity for directed graphs is introduced. (Author)
Descriptors : (*DATA PROCESSING, IMAGES), (*COMPUTATIONAL LINGUISTICS, *GRAPHICS), PATTERN RECOGNITION, GROUPS(MATHEMATICS), SET THEORY, MAPPING(TRANSFORMATIONS), THEOREMS
Subject Categories : Linguistics
Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE