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 semi-homomorphism 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 semi-homomorphisms of the convex subgraph lattice. Homomorphisms which 'contract' subgraphs (which are analogous to the rewriting rules of context-sensitive 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