共查询到20条相似文献,搜索用时 31 毫秒
1.
Milan Randi 《Journal of computational chemistry》1982,3(3):421-435
Existing schemes for evaluation of the characteristic polynomial of a graph suffer from limited practicality. Their application to large molecules inordinately increases the amount of labor. Here a procedure is outlined which is useful even for large molecules. It is based on a not widely known property of the collection of characteristic polynomials for Ulam's subgraphs, which, when added, give the derivative of the characteristic polynomial of the initial graph. The characteristic polynomials for Ulam's subgraphs are, as a rule, easier to derive due to the presence of many pending bonds in graphs of chemical interest. The last step requires an integration of a polynomial (which is a straightforward step) and determining the constant of integration, which represents the determinant of the adjacency matrix. The available methods for determing the additive constant (the determinant) are combinatorially much simpler than the initial task of finding all of the coefficients of the characteristic polynomial. The approach is illustrated on selected benzenoid hydrocarbons, nonbenzenoid, and nonalternant systems. Construction of the characteristic polynomials can be accelerated by considering auxiliary fragments and irreducible subgraphs separately and combining them in the final expression. Many auxiliary fragments allow their characteristic polynomials to be expressed in a closed form using recursive relations. The results for complex molecules can thus be written in a relatively compact form. Finally, the derivative of the characteristic polynomial, expressed in terms of selected auxiliary functions and irreducible components, can be integrated directly to give the result in terms of contributions signifying various fragments rather than as an explicit function of x. 相似文献
2.
Milan Randić 《Theoretical chemistry accounts》1983,62(6):485-498
The characteristic polynomial of a structure (molecule or a graph) is usually expressed as a function ofx. Here we explore an alternative representation of characteristic polynomials expressed in terms ofL n , the characteristic polynomials of linear chains havingn atoms. While the new forms of the characteristic polynomials are mathematically equivalent to the old forms, they appear to reflect selected structural similarities among homologous molecules better. Besides arriving at general expressions for the form of the characteristic polynomials for numerous families of compounds previously unavailable, the approach is of some interest for the old problem of graph isomorphism and graph recognition in cases of structures which can be associated with a homologous series. 相似文献
3.
The structural dependency (effect of branching and cyclisation) of an alternative form, the Chebyshev expansion, for the characteristic
polynomial were investigated systematically. Closed forms of the Chebyshev expansion for an arbitrary star graph and a bicentric
tree graph were obtained in terms of the “structure factor” expressed as the linear combination of the “step-down operator”.
Several theorems were also derived for non-tree graphs. Usefulness and effectiveness of the Chebyshev expansion are illustrated
with a number of examples. Relation with the topological index (Z
G
) was discussed.
Operated for the U.S. Department of Energy by ISU under contract no. W-ENG-7405-82. Supported in part by the Office of Director 相似文献
4.
Milan Randić 《Journal of mathematical chemistry》1987,1(1):145-152
The use of power sum symmetric functions leads to Newton's identities, which relate the traces of various powers ofA, the adjacency matrix of a graph, and the coefficients of the characteristic polynomials. While it is possible to solve Newton's identities and generate the coefficients by recursion or, alternatively, to derive them by sequential manipulations (yielding the explicit formulas), we show how the results can be expressed using a combinatorial approach and relate the evaluation of the coefficients to selected Young diagrams. 相似文献
5.
Tomislav P.
ivkovi 《Journal of computational chemistry》1990,11(2):217-222
The evaluation of the characteristic polynomial of a chemical graph is considered. It is shown that the operation count of the Le Verrier–Faddeev–Frame method, which is presently considered to be the most efficient method for the calculation of the characteristic polynomial, is of the order n4. Here n is the order of the adjacency matrix A or equivalently, the number of vertices in the graph G. Two new algorithms are described which both have the operation count of the order n3. These algorithms are stable, fast, and efficient. A related problem of finding a characteristic polynomial from the known eigenvalues λi of the adjacency matrix is also considered. An algorithm is described which requires only n(n ? 1)/2 operations for the solution of this problem. 相似文献
6.
Bojan Mohar 《Journal of mathematical chemistry》1989,3(4):403-406
An algorithm is given for computing the values of the characteristic polynomial of a tree. Its time complexity is linear; hence, the polynomial is readily accessible from the tree and no computation is necessary to get the polynomial ready for applications. If necessary, the coefficients can be determined in time O(n
2). This improves the complexity O(n
3), reached by Tinhofer and Schreck, to O(1).received by the Publisher 20 September 1989This work was supported in part by the Research Council of Slovenia, Yugoslavia. 相似文献
7.
Noriyuki Mizoguchi 《Journal of mathematical chemistry》1993,12(1):265-277
A vertex-weighted graphG
* is studied which is obtained by deleting edgee
rs
in a circuit of a graphG and giving two vertices r and s weightsh
r
= 1 andh
s
= -1, respectively. It is shown that if subgraphG - r is identical with subgraphG - s, then the reference polynomial ofG
* is identical with that ofG and the characteristic polynomial ofG
* contains the contributions due to only a certain part of the circuits found in the original graphG. This result gives a simple way to find a graph whose characteristic polynomial is equal to the reference polynomial in the topological resonance energy theory or to the circuit characteristic polynomial in the circuit resonance energy theory. This approach can be applied not only to Hilckel graphs but also to Möbius graphs, provided that they satisfy a certain condition. The significances of this new type of reference graph thus obtained are pointed out. 相似文献
8.
Nenad Trinajstić 《Journal of mathematical chemistry》1988,2(3):197-215
We list uses of, and the computational methods for the characteristic polynomial of a (chemical) graph. Pour computational methods are singled out for more detailed presentation. These are the graphical methods of Sachs, the recurrence formulae for several classes of simple graphs, the method based on Ulam subgraphs, and the Le Verrier — Faddeev — Franic recursive method. The latter method appears, at present, to be the most efficient procedure for the computation of the characteristic polynomials of graphs of sizes with up to even a few hundred sites.Dedicated to Dennis H. Rouvray, the friend and one of the foremost popularizers of chemical graph theory in our time.Research supported by the Robert A. Welch Foundation of Houston, Texas, USA. 相似文献
9.
Allen J. Kassman 《Theoretical chemistry accounts》1985,67(4):255-262
The technique of describing the characteristic polynomial of a graph is here extended to construction of the eigenvectors. Recurrence relations and path tracing are combined to generate eigenvector coefficients as polynomial functions of the eigenvalues. The polynomials are expressed as linear functions of Chebyshev polynomials in order to simplify the computational effort. Particular applications to the Hückel MO theory, including heteroatom effects, are shown. 相似文献
10.
Bholanath Mandal Manas Banerjee Asok K. Mukherjee 《International journal of quantum chemistry》2005,101(2):119-126
A method for construction of the characteristic polynomial (CP) coefficients of the three classes of reciprocal graphs, viz., Ln + n(p), Cn + n(p), and K1,n?1 + n(p), has been developed that requires only the value of n. The working formulas have been expressed in matrix product form, computer programs for which can easily be developed. © 2004 Wiley Periodicals, Inc. Int J Quantum Chem, 2005 相似文献
11.
Jerry Ray Dias 《Theoretical chemistry accounts》1985,68(2):107-123
Some previously unknown relationships for determining the a
4 and a
6 coefficients of the characteristic polynomial for polycyclic aromatic hydrocarbons are presented for the first time. The structural information contained in these coefficients is more fully revealed. The equations derived for a
4 and a
6 allow one to determine the characteristic polynomial by inspection for many small molecular graphs. Some relationships for a
8 and a
10 are presented. The set of known graphical invariants (GI) or properties that remain unchanged in isomeric PAH6s is now shown to be GI={a
4, a
6+n
0+2r
6, a
8
c
, d
s+NIc, Nc, Nh, NIc+NPc, q, r}.Part VIII: A periodic table for polycyclic aromatic hydrocarbons 相似文献
12.
Gunnar Brinkmann 《Journal of mathematical chemistry》2018,56(5):1437-1444
Known algorithms computing a canonical form for trees in linear time use specialized canonical forms for trees and no canonical forms defined for all graphs. For a graph \(G=(V,E)\) the maximal canonical form is obtained by relabelling the vertices with \(1,\ldots ,|V|\) in a way that the binary number with \(|V|^2\) bits that is the result of concatenating the rows of the adjacency matrix is maximal. This maximal canonical form is not only defined for all graphs but even plays a special role among the canonical forms for graphs due to some nesting properties allowing orderly algorithms. We give an \(O(|V|^2)\) algorithm to compute the maximal canonical form of a tree. 相似文献
13.
A parallel algorithm is developed for the first time based on Frame's method to compute the characteristic polynomials of chemical graphs. This algorithm can handle all types of graphs: ordinary, weighted, directed, and signed. Our algorithm takes only linear time in the CRCW PRAM model with O(n3) processors whereas the sequential algorithm takes O(n4) time. Especially when the number of vertices of the graph is large this method will be more efficient than the recently developed vectorized Frame and Givens–Householder methods. 相似文献
14.
Gutman et al. [Chem. Phys. Lett. 355 (2002) 378–382] established a relationship between the Coulson function,
, where \phi is the characteristic polynomial, and the Hosoya index Z, which is the sum over all k of the counts of all k-matchings. Like the original Coulson function, this relationship was postulated only for trees. The present study shows that the relationship can be extended to (poly)cyclic graphs by substituting the matching, or acyclic, polynomial for the characteristic polynomial. In addition, the relationship is extended to new types of matching polynomials that match cycles larger than edges (2-cyc1es). Finally, this presentation demonstrates a rigorous mathematical relationship between the graph adjacency matrices and the coefficients of these polynomials and describes computational algorithms for calculating them. 相似文献
15.
The Coulson integral formula for total π-electron energy (Eπ) is analysed, and an elementary derivation of it is presented. Three novel Coulson-type formulae are obtained and one is used for deriving the McClelland (approximate) expression for Eπ. An approximation of a particular formula is proposed which results in a linear relationship between Eπ and the coefficients of the characteristic polynomial of the molecular graph. 相似文献
16.
Teik-Cheng Lim 《Journal of mathematical chemistry》2009,45(4):953-961
It is shown that the diatomic potential energy functions of Dunham, SPF and Ogilvie can be easily converted from one another
when their coefficients are related. Through Maclaurin expansion and comparison of terms, the coefficients can be related
by using the Pascal Triangle. In this paper, the coefficients were related up to the tenth order of δr/R for HX (X = H, Ga, Cl, I). Comparison of all three potential energy curves shows very good agreement for r ≤ 1.5R, thereby verifying the formulated relations. Observation of the plotted potential energy curves for r > 1.5R shows that the difference of the three potential function definitions is not reflected as any consistent trend arising from
the related potential functions. 相似文献
17.
Supplementing the construction of a Möbius ladder graph derived from a ladder graph, the linear fence graph and cyclic fence graph are introduced. These have neater mathematical expressions for the perfect matching numbers and the matching and characteristic polynomials than the graphs in the previous families. 相似文献
18.
Characteristic polynomials of acyclic carbon chains (Huckel trees) are treated in a systematic way. Formulas of coefficients (ak) of the polynomial are obtained in terms of connectivities that were introduced for dealing with moments in a previous paper. Based on the meaning of ak, a graph-theoretical analysis is given such that ak can be expressed as a linear combination of binomial factors specified by a set of graphs containing ½k edges. The numerical relationship is disclosed between each binomial factor and its specified graph. This stimulates the proposal of a novel approach for evaluating ak by simply collecting the graph set of defnite edges. The approach is equally applicable for the evaluation of matching polynomials of cyclic systems and extendable to the investigation of general trees. 相似文献
19.
K. Balasubramanian 《Theoretical chemistry accounts》1984,65(1):49-58
The evaluation of characteristic polynomials of graphs of any size is an extremely tedious problem because of the combinatorial
complexity involved in this problem. While particular elegant methods have been outlined for this problem, a general technique
for any graph is usually tedious. We show in this paper that the Frame method for the characteristic polynomial of a matrix
is extremely useful and can be applied to graphs containing large numbers of vertices. This method reduces the difficult problem
of evaluating the characteristic polynomials to a rather simple problem of matrix products. The coefficients in the characteristic
polynomial are generated as traces of matrices generated in a recursive product of two matrices. This method provides for
an excellent and a very efficient algorithm for computer evaluation of characteristic polynomials of graphs containing a large
number of vertices without having to expand the secular determinant of the matrix associated with the graph. The characteristic
polynomials of a number of graphs including that of a square lattice containing 36 vertices are obtained for the first time. 相似文献
20.
The characteristic polynomial associated with π-electrons of conjugated molecules are discussed by using subgraphs derived from molecular graphs as a basis for their construction. A practical method has been developed for evaluating the coefficient aK of conjugated molecules. Applying this method, the general formulas of evaluating the coefficient aK for homologous conjugated molecules have been obtained. The approach is illustrated on a few simple conjugated systems, including also a few polymeric systems. © 1996 John Wiley & Sons, Inc. 相似文献