Search

This report includes a list of papers completed and published, a description of the activities of each of the investigators, and a discussion of some of the most significant results obtained.

The various theoretical results outlined are concerned with such matters as the structure of graphs having a maximum and minimum number of 'cliques' as used in clustering and classification schemes, with the enumeration of acyclic configurations of generalizations of mathematical models of the biological growth cells and paving problems in statistical mechanics, with properties of 'anticritical' graphs such as point and line-connectivity, with duals of tree graphs, with enumeration of random walks in graphs in terms of the moments of the eigenvalues of their adjacency matrices, and with determining the minimum number of prints of a digraph which must be removed so that the result is acyclic, i.e., finding the minimum feedback vertex set of a digraph. The report also provides a listing of the publications in which the detailed accomplishments are presented., See also report dated 30 Aug 74, AD/A-003 983.

An effort has been made to present the various topics in the theory of graphs in a logical order, to indicate the historical background, and to clarify the exposition by including figures to illustrate concepts and results. In addition, there are three appendices which provide diagrams of graphs, directed graphs, and trees. The emphasis throughout is on theorems rather than algorithms or applications, which however are occasionally mentioned., Availability: Paper copy available from Addison-Wesley Publishing Co., Reading, MA.

Contents: The four color conjecture and other graphical diseases; Several proofs of the number of labeled 2-dimensional trees; On the chromatic number of permutation graphs; The expanding unicurse; Problems and results in chromatic graph theory; Forbidden subgraphs; A proof technique in graph theory; Independence and covering numbers of line graphs and total graphs; The decline and fall of Zarankiewicz's Theorem; On the intersection number of a graph; On endomorphisms of graphs and their homomorphic images; Counterexamples in the theory of well-quasi-ordered sets; On the existence of certain minimal regular n-systems with given girth; Reconstruction of unicyclic graphs; The group of a graph whose adiacency matrix has all distinct eigenvalues; Extremal nonseparable graphs of diameter 2; A class of strongly regular graphs; The exponentiation group as the automorphism group of A graph; Remarks on the Heawood conjecture; Indifference graphs; Enumeration of Euler graphs; A graph-theoretical model for periodic discrete structures; Even and odd 4-colorings; A theorem on Tait colorings with an application to the generalized Petersen graphs; The Mobius function in combinatorial analysis and chromatic graph theory; and Key-word indexed bibliography of graph theory., Proceedings of the Ann Arbor Graph Theory Conference (2nd), Feb 68.

The opening six chapters present a coherent body of graph theoretic concepts. The remaining eight chapters report lectures presented by various seminar participants. Topics presented include: Complete Bipartite Graphs, Extremal Problems in Graph Theory, Applications of Probabilistic Methods to Graph Theory, The Minimal Regular Graph Containing a Given Graph, Various Proofs of Cayley's Formula for Counting Trees, On Well-Quasi-Ordering Trees, Universal Graphs and Graphs and Composite Games. (Author)

This report is a brief summary of research accomplishments by the author and his associates during the period 1 April 1973 through 30 Mar 1974. The areas discussed include graphical enumeration, e.g., counting the number of spanning trees of a graph, graph topology, generalized Ramsey theory, integral characteristic polynomials of adjacency matrices, and communication problems. A list of publications which contain the detailed research findings is provided.

Laser scintillation was measured for a horizontal optical path 500 m long and 1 m high for various conditions of horizontally homogeneous turbulence. Wind direction, average vertical distributions of wind speed and temperature, and, in some cases, turbulent fluctuations of wind velocity were measured simultaneously. The results of the measurements were analyzed in relation to a set of theoretical relationships derived by Tatarski (1961) for electromagnetic wave propagation in turbulent flow. Tatarski's derivation of the scintillation frequency spectrum (at a point in a plane perpendicular to the optical path) in relation to the three-dimensional spectral density of index of refraction inhomogeneities is summarized and interpreted in relation to its validity for various conditions of turbulence. Analysis of the spectral data showed that their characteristics were similar to Tatarski's theoretical spectrum if the divergence of the laser beam, the size of the receiver aperture, the intensity of scintillation and turbulence spectra were considered. (Author)

Contents: On the history of the theory of graphs; On graphs with a constant link; Some extremal problems on r-graphs; New directions in hamiltonian graph theory; On the use of graphs in group theory; The adjacency matrix and the group of a graph; Unexplored and semi-explored territories in graph theory; Graphical enumeration methods; Isomorphisms between hypergraphs; Counting labeled acyclic digraphs; Almost all trees are cospectral; What is a map., Library of Congress catalog card no. 72-77368. Proceedings of the Ann Arbor Conference on Graph Theory (3rd), 21-23 Oct 71.

The book is a definitive treatise on the enumeration of graphs and related structural configurations, providing historical results as well as recent developments having potential application in the fields of physics, chemistry, computer science, and electrical engineering. Its ten chapters cover the subjects of labeled enumeration, Polya's Theorem, trees, graphs, diagraphs, power group enumeration, superposition, blocks, asymptotics, and as a special feature, a new comprehensive list of unsolved graphical enumeration problems. It includes an extensive bibliography and numerous exercises ranging in difficulty from routine to intractable. (Author), Prepared in cooperation with Michigan State Univ., East Lansing. Library of Congress catalog card no. 72-82653.

The report is a brief summary of the results obtained during a five year basic research effort in the theory of graphs and its application to Air Force systems design and analysis. It includes an identification of the twelve research topics which received major attention, an identification of the scientific and engineering problem areas in which theoretical results have been applied, and a listing of six books and twenty-two technical papers resulting from the grant which describe in detail the theory and methodology developed. (Author)

A new method, called the QZ algorithm, is presented for the solution of the matrix eigenvalue problem Ax = lambda Bx with the general square matrices A and B. Particular attention is paid to the degeneracies which result when B is singular. No inversions of B or its submatrices are used. The algorithm is a generalization of the QR algorithm, and reduces to it when B=I. Problems involving powers of lambda are also mentioned. (Author)

Approximations that result from the natural matching of two stable dissipative difference schemes across a coordinate line are shown to be stable. The basic ideas is to reformulate the matching scheme consistent to an equivalent initial boundary value problem and verify the algebraic conditions for stability of such systems. An interesting comparison to the above result is the case of redefinition of a scheme at a single point. In particular, the author shows that some unstable perturbations do not upset the stability of the Lax-Wendroff scheme. (Author)

The report consists of the abstracts of four Ph. D. theses. The specific topics covered are numerical solution of elliptic partial differential equations, approximation theory, and matrix computations. (Author)

The efficiency of conventional FORTRAN programs for matrix computations can often be improved by reversing the order of nested loops. Such modifications produce modest savings in many common situations and very significant savings for large problems run under an operating system which uses paging. (Author), Prepared in cooperation with Standford Univ., Calif. Dept. of Computer Science, Rept. no. STAN-CS-71-196. Revision of report dated Jun 70.

An observational study was made during August, September and October 1968 to investigate the influence of water waves on the adjacent airflow. Simultaneous measurements of wind and temperature fluctuations and waves were made from a tower on Lake Michigan. 11 periods were analyzed, and 8 included simultaneous measurements of velocity and temperature fluctuations at two levels above the mean water level. Hot-wire anemometers with X-probe sensors were used to obtain both the along-wind and vertical components of the fluctuating wind. High response resistance wires were used to measure temperature fluctuations and a capacitance gauge was used to measure the waves. Data were analyzed to obtain variance and covariance spectra over a frequency range from .01 to 15 Hz and are presented over a range from .03 to 10 Hz. (Author)

Simultaneous measurements of wind velocity components with hot-film anemometers, air temperature fluctuations, and wave heights were made about 200 miles east northeast of Barbados during BOMEX. A total of 54 hours of measurements were made during the last two weeks in May, 1969. Of these, 23 had simultaneous recordings of wind velocity components and temperature fluctuations at two heights. Measurement heights were 2, 3, 6 and 8 meters above mean water level. Three different computer facilities have been employed in processing the data to obtain probability distribution functions, joint probability distribution functions, spectrum functions and cross-spectrum functions for velocity components, temperature fluctuations and wave heights. Examples of the calculation results are given and briefly described. They show specific effects of waves on the velocity components. (Author)

Contents: Development of a dependable 'Smoke producing' rocket to a height limit of 3000 to 4000 ft; Development of photographic techniques for sequentically recording the smoke plumes in three-dimensions, and, the techniques employed in the determination of wind speeds and directions vs. heights from these readings; Development of a night lighting system for the use of 'Smoke rockets' at night; and Development and testing of a smoke rocket system to extend the useful height range to at least 8000 ft above ground.

The hydrodynamic stability of divergent jets is studied under the condition of small but nonzero Rossby number. Small disturbances to the basic state consist of fast waves of inertio-gravity type and slow waves with speed comparable to that of the basic current. It is shown that the fast waves are stable and do not amplify. It is shown also that, for a velocity profile resembling that of the Gulf Stream, the slow waves are destabilized by the presence of nonzero Rossby number. For very shallow jets it is found that the complex wave velocity is small and that, in general, disturbances will be stable unless the jet has a countercurrent. (Author), See also AD-690 555.

During the reporting the principal investigator and some of his collaborators completed seventeen research papers. This work is described. The major effort was devoted to problems of optimal control. Existence theorems were proved for lumped parameter control systems by a new type of analysis. A number of related conditions were analyzed with examples and applications. Existence theorems were proved for distributed parameter control systems by the use of Sobolev spaces technique and for partial differential equations written in the rather general form proposed by Dieudonne and Rashevski. A form of Pontryagin's principle were proved for these systems which is remarkably similar to a K. A. Lurie problem of magnetohydrodynamic channel flow. Further work concerns: measure theory, integration over a surface area, periodic solutions of nonlinear hyperbolic partial differential equations, in particular, nonlinear wave equations. (Author)

The report contains a course given in Bressanone (Italy), June 10-18, 1966. The course concerns existence theorems for problems of optimal control and the calculus of variations. These theorems extend Filippov's existence theorem in optimal control theory, and the Tonelli-Nagumo theorem in the calculus of variations. Complete proofs are given for the case of lumped parameters. For the case of distributed parameters the theorems are only stated. (Author), Presented at Centro Internazionale Matematico Estivo. Course given in Bressanoe (Italy), 10-18 Jun 66.

Research was conducted in the theory of singular integral equations which arise in certain initial value and boundary value problems that come from elliptic and hyperbolic equations. In particular, those related to axially symmetric boundary value problems were studied. Results were obtained on a singular boundary value problem for the Euler Darboux equation, an integral equation in diffraction theory, diffraction by a disc and a boundary value problem associated with the Tricomi equation. (Author)

A hot-wire anemometer system, a fast response resistance wire thermometer and a thermocouple circuit were used in an attempt to measure the structure of turbulence, the turbulent fluxes of heat and momentum and the mean vertical temperature difference over ocean waves. To study data reliability (1) the recorded information was converted to voltage analogs and recorded on a paper chart and (2) spectral analyses were made for all channels of information for a representative six minute interval. It was found that a high noise level was present in all recordings and that it could be accounted for by voltage and frequency fluctuations in the power supplied for the magnetic tape recorder. The noise level masked the temperature measurement outputs which, apparently, were very small because of the nearly neutral thermal stratification during the experiments. On the basis of the preliminary analyses it appears that meaningful velocity spectra and cross spectra for frequencies less than 1.5 Hz may be computed from the recordings; higher frequency information is probably obscured by the high noise level. (Author)

The document gives various papers done under contract on optimal control and plasma physics.