In
chemical graph theory
Chemical graph theory is the topology branch of mathematical chemistry which applies graph theory to mathematical modelling of chemical phenomena.
The pioneers of chemical graph theory are Alexandru Balaban, Ante Graovac, Iván Gutman, Haruo Hosoy ...
, the Wiener index (also Wiener number) introduced by
Harry Wiener
Harry Wiener (Oct. 29, 1924 in Vienna, Austria – Nov. 8, 1998 in New York City, USA) was an Austrian-American chemist, physician and psychologist, a pioneer in cheminformatics and chemical graph theory, and a long-time employee at Pfizer.
Edu ...
, is a
topological index
In the fields of chemical graph theory, molecular topology, and mathematical chemistry, a topological index, also known as a connectivity index, is a type of a molecular descriptor that is calculated based on the molecular graph of a chemical compo ...
of a
molecule
A molecule is a group of two or more atoms held together by attractive forces known as chemical bonds; depending on context, the term may or may not include ions which satisfy this criterion. In quantum physics, organic chemistry, and bioch ...
, defined as the sum of the lengths of the
shortest path
In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
The problem of finding the shortest path between tw ...
s between all pairs of vertices in the
chemical graph
In chemical graph theory and in mathematical chemistry, a molecular graph or chemical graph is a representation of the structural formula of a chemical compound in terms of graph theory. A chemical graph is a labeled graph whose vertices corres ...
representing the non-
hydrogen
Hydrogen is the chemical element with the symbol H and atomic number 1. Hydrogen is the lightest element. At standard conditions hydrogen is a gas of diatomic molecules having the formula . It is colorless, odorless, tasteless, non-toxic, an ...
atoms in the molecule.
[.]
Wiener index can be used for the representation of
computer networks
A computer network is a set of computers sharing resources located on or provided by network nodes. The computers use common communication protocols over digital interconnections to communicate with each other. These interconnections are ma ...
and enhancing lattice
hardware security
Hardware security as a discipline originated out of cryptographic engineering and involves hardware design, access control, secure multi-party computation, secure key storage, ensuring code authenticity, measures to ensure that the supply chain tha ...
.
History
The Wiener index is named after
Harry Wiener
Harry Wiener (Oct. 29, 1924 in Vienna, Austria – Nov. 8, 1998 in New York City, USA) was an Austrian-American chemist, physician and psychologist, a pioneer in cheminformatics and chemical graph theory, and a long-time employee at Pfizer.
Edu ...
, who introduced it in 1947; at the time, Wiener called it the "path number".
[.] It is the oldest topological index related to molecular branching. Based on its success, many other topological indexes of chemical graphs, based on information in the distance matrix of the graph, have been developed subsequently to Wiener's work.
The same quantity has also been studied in pure mathematics, under various names including the gross status, the distance of a graph,
[.] and the transmission. The Wiener index is also closely related to the
closeness centrality In a connected graph, closeness centrality (or closeness) of a node is a measure of centrality in a network, calculated as the reciprocal of the sum of the length of the shortest paths between the node and all other nodes in the graph. Thus, the mo ...
of a vertex in a graph, a quantity inversely proportional to the sum of all distances between the given vertex and all other vertices that has been frequently used in
sociometry
Sociometry is a quantitative method for measuring social relationships. It was developed by psychotherapist Jacob L. Moreno and Helen Hall Jennings in their studies of the relationship between social structures and psychological well-being, and ...
and the theory of
social network
A social network is a social structure made up of a set of social actors (such as individuals or organizations), sets of dyadic ties, and other social interactions between actors. The social network perspective provides a set of methods for an ...
s.
Example
Butane
Butane () or ''n''-butane is an alkane with the formula C4H10. Butane is a gas at room temperature and atmospheric pressure. Butane is a highly flammable, colorless, easily liquefied gas that quickly vaporizes at room temperature. The name but ...
(C
4H
10) has two different
structural isomers
In chemistry, a structural isomer (or constitutional isomer in the IUPAC nomenclature) of a compound is another compound whose molecule has the same number of atoms of each element, but with logically distinct bonds between them. The term meta ...
: ''n''-butane, with a linear structure of four carbon atoms, and
isobutane
Isobutane, also known as ''i''-butane, 2-methylpropane or methylpropane, is a chemical compound with molecular formula HC(CH3)3. It is an isomer of butane. Isobutane is a colourless, odourless gas.
It is the simplest alkane with a tertiary carbon a ...
, with a branched structure. The chemical graph for ''n''-butane is a four-vertex
path graph
In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two terminal ...
, and the chemical graph for isobutane is a tree with one central vertex connected to three leaves.
Image:Butane simple.svg, n-Butane
Image:Isobutane simple.svg, Isobutane
The ''n''-butane molecule has three pairs of vertices at distance one from each other, two pairs at distance two, and one pair at distance three, so its Wiener index is
:
The isobutane molecule has three pairs of vertices at distances one from each other (the three leaf-center pairs), and three pairs at distance two (the leaf-leaf pairs). Therefore, its Wiener index is
:
These numbers are instances of formulas for special cases of the Wiener index: it is
for any
-vertex path graph such as the graph of ''n''-butane, and
for any
-vertex
star
A star is an astronomical object comprising a luminous spheroid of plasma (physics), plasma held together by its gravity. The List of nearest stars and brown dwarfs, nearest star to Earth is the Sun. Many other stars are visible to the naked ...
such as the graph of isobutane.
Thus, even though these two molecules have the same chemical formula, and the same numbers of carbon-carbon and carbon-hydrogen bonds, their different structures give rise to different Wiener indices.
Relation to chemical properties
Wiener showed that the Wiener index number is closely correlated with the
boiling point
The boiling point of a substance is the temperature at which the vapor pressure of a liquid equals the pressure surrounding the liquid and the liquid changes into a vapor.
The boiling point of a liquid varies depending upon the surrounding envir ...
s of
alkane
In organic chemistry, an alkane, or paraffin (a historical trivial name that also has other meanings), is an acyclic saturated hydrocarbon. In other words, an alkane consists of hydrogen and carbon atoms arranged in a tree structure in which ...
molecules.
Later work on
quantitative structure–activity relationship
Quantitative structure–activity relationship models (QSAR models) are regression or classification models used in the chemical and biological sciences and engineering. Like other regression models, QSAR regression models relate a set of "predic ...
s showed that it is also correlated with other quantities including the parameters of its
critical point, the
density
Density (volumetric mass density or specific mass) is the substance's mass per unit of volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' can also be used. Mathematical ...
,
surface tension
Surface tension is the tendency of liquid surfaces at rest to shrink into the minimum surface area possible. Surface tension is what allows objects with a higher density than water such as razor blades and insects (e.g. water striders) to f ...
, and
viscosity
The viscosity of a fluid is a measure of its resistance to deformation at a given rate. For liquids, it corresponds to the informal concept of "thickness": for example, syrup has a higher viscosity than water.
Viscosity quantifies the inte ...
of its liquid phase, and the
van der Waals surface area
The Van der Waals surface of a molecule is an abstract representation or model of that molecule, illustrating where, in very rough terms, a surface might reside for the molecule based on the hard cutoffs of Van der Waals radii for individual at ...
of the molecule.
Calculation in arbitrary graphs
The Wiener index may be calculated directly using an algorithm for computing all pairwise distances in the graph. When the graph is unweighted (so the length of a path is just its number of edges), these distances may be calculated by repeating a
breadth-first search
Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next de ...
algorithm, once for each starting vertex.
The total time for this approach is O(''nm''), where ''n'' is the number of vertices in the graph and ''m'' is its number of edges.
For weighted graphs, one may instead use the
Floyd–Warshall algorithm
In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with p ...
or
Johnson's algorithm
Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in an edge-weighted directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist. It works by using ...
, with running time O(''n''
3) or O(''nm'' + ''n''
2 log ''n'') respectively. Alternative but less efficient algorithms based on repeated
matrix multiplication
In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...
have also been developed within the chemical informatics literature.
Calculation in special types of graph
When the underlying graph is a
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
(as is true for instance for the alkanes originally studied by Wiener), the Wiener index may be calculated more efficiently. If the graph is partitioned into two subtrees by removing a single edge ''e'', then its Wiener index is the sum of the Wiener indices of the two subtrees, together with a third term representing the paths that pass through ''e''. This third term may be calculated in linear time by computing the sum of distances of all vertices from ''e'' within each subtree and multiplying the two sums. This
divide and conquer algorithm
In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dire ...
can be generalized from trees to graphs of bounded
treewidth
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...
, and leads to near-linear-time algorithms for such graphs.
An alternative method for calculating the Wiener index of a tree, by
Bojan Mohar Bojan Mohar (born September 21, 1956) is a Slovenian and Canadian mathematician, working in graph theory. He is a professor of mathematics at the University of Ljubljana and the holder of a Canada Research Chair in graph theory at Simon Fraser Unive ...
and
Tomaž Pisanski
Tomaž (Tomo) Pisanski (born 24 May 1949 in Ljubljana, Yugoslavia, which is now in Slovenia) is a Slovenian mathematician working mainly in discrete mathematics and graph theory. He is considered by many Slovenian mathematicians to be the "father ...
, works by generalizing the problem to graphs with weighted vertices, where the weight of a path is the product of its length with the weights of its two endpoints. If ''v'' is a leaf vertex of the tree then the Wiener index of the tree may be calculated by merging ''v'' with its parent (adding their weights together), computing the index of the resulting smaller tree, and adding a simple correction term for the paths that pass through the edge from ''v'' to its parent. By repeatedly removing leaves in this way, the Wiener index may be calculated in linear time.
[.]
For graphs that are constructed as
products
Product may refer to:
Business
* Product (business), an item that serves as a solution to a specific consumer problem.
* Product (project management), a deliverable or set of deliverables that contribute to a business solution
Mathematics
* Produ ...
of simpler graphs, the Wiener index of the product graph can often be computed by a simple formula that combines the indices of its factors.
Benzenoid
In organic chemistry, benzenoids are a class of organic compounds with at least one benzene ring. These compounds have increased stability due resonance in the benzene rings. Most aromatic hydrocarbons are benzenoid. Notable counterexamples are cyc ...
s (graphs formed by gluing regular hexagons edge-to-edge) can be embedded
isometrically into the
Cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\ti ...
of three trees, allowing their Wiener indices to be computed in linear time by using the product formula together with the linear time tree algorithm.
Inverse problem
considered the problem of determining which numbers can be represented as the Wiener index of a graph. They showed that all but two positive integers have such a representation; the two exceptions are the numbers 2 and 5, which are not the Wiener index of any graph. For graphs that must be bipartite, they found that again almost all integers can be represented, with a larger set of exceptions: none of the numbers in the set
:
can be represented as the Wiener index of a bipartite graph.
Gutman and Yeh conjectured, but were unable to prove, a similar description of the numbers that can be represented as Wiener indices of trees, with a set of 49 exceptional values:
:2, 3, 5, 6, 7, 8, 11, 12, 13, 14, 15, 17, 19, 21, 22, 23, 24, 26, 27, 30, 33, 34, 37, 38, 39, 41, 43, 45, 47, 51, 53, 55, 60, 61, 69, 73, 77, 78, 83, 85, 87, 89, 91, 99, 101, 106, 113, 147, 159
The conjecture was later proven by Wagner, Wang, and Yu.
[.]
References
External links
* {{MathWorld, id=WienerIndex, title=Wiener Index
Mathematical chemistry
Cheminformatics
Graph invariants