La théorie des graphes est une branche des mathématiques (discrètes) qui traite de la façon dont les objets sont connectés.$^1$ Ainsi, la connectivité dans un système est une qualité fondamentale de la théorie des graphes. Le concept principal de la théorie des graphes est celui d’un graphe. Pour un mathématicien, un graphe est l’application d’un ensemble sur lui-même, c’est-à-dire une collection d’éléments de l’ensemble et les relations binaires entre ces éléments$^2$. Les graphes sont des objets unidimensionnels$^3$, mais ils peuvent être intégrés ou réalisés de dimensions supérieures.
La théorie des graphes est liée à la topologie (en fait, la théorie des graphes est une topologie unidimensionnelle$^3$). théorie de la matrice, théorie des groupes. établir la théorie, la probabilité, la combinatoire et l’analyse numérique. Il a été utilisé dans des domaines aussi variés que l’écononie $^4$ et la physique théorique $^5$, la psychologie $^6$ et la physique nucléaire $^7$, la biomathématique $^8$ et la linguistique $^9$, la sociologie $^{10}$ et la zoologie $^{11}$, la technologie $^{12}$ et l’anthropologie $^{13}$, l’informatique $^{14}$ et la géographie $^{16}$, etc.
La théorie des graphes chimiques est une branche de la chimie mathématique qui s’intéresse aux analyses de toutes les conséquences d’une connectivité dans un graphe chimique. Le graphe chimique sert de modèle pratique pour tout système chimique réel ou abstrait (molécule ou schéma réactionnel dans une transformation chimique) $^{11}$. En d’autres termes, la théorie des graphes chimiques concerne tous les aspects de l’application de la théorie des graphes à la chimie. En ce qui concerne l’utilisation du terme chimique, il est à souligner que la théorie des graphes chimiques permet, contrairement à la théorie des graphes, de s’appuyer sur la compréhension intuitive de nombreux concepts et théorèmes plutôt que sur des preuves mathématiques formelles.
Ces dernières années ont vu une croissance remarquable de la théorie des graphes chimiques $^{19. 43}$ Il y a plusieurs raisons à la popularité croissante de la théorie des graphes en chimie $^{17-21, 25-28, 30,34,37,38,41,42,44-46}$ :
- Il n’y a guère de concept dans les sciences naturelles qui soit plus proche de la notion de graphe que la formule structurelle (constitutionnelle) d’un composé chimique, $^7$ car un graphe est, en fait, un modèle mathématique $^8$ qui peut être utilisé directement pour représente une molécule lorsque la seule propriété considérée est la connectivité interne. Le langage naturel de la chimie par lequel les chimistes communiquent se base de plus en plus sur la théorie des graphes (chimiques).
- La théorie des graphes fournit des règles simples par lesquelles les chimistes peuvent obtenir de nombreuses prédictions qualitatives sur la structure et la réactivité de divers composés. Toutes ces prédictions peuvent être atteintes en utilisant rien de plus qu’un crayon et du papier. De plus, les résultats obtenus ont souvent une validité générale et peuvent être formulés sous forme de théorèmes et / ou de règles qui peuvent ensuite être appliqués à une variété de problèmes similaires sans aucun travail numérique ou conceptuel. $^{40, 49- 51},
- La théorie des graphes peut être utilisée comme base pour la représentation, la classification et la catégorisation d’un très grand nombre de systèmes chimiques. $^{52, 53}$
- le développement de schémas simples sur la théorie des liaisons en résonance est principalement influencé, sciemment ou inconsciemment, par une apporche « théorie eds graphes » sur l’énumération des états de valence.$^{54, 55}$
Une raison de plus doit être mentionnée ici: c’est l’utilisation explosive des invariants de la théorie des graphes dans les relations structure-propriété-activité ( en anglais, SPAR : Structure-Property-Activity relations) $^{23, 31, 56, 57}$. C’est peut-être un domaine de la chimie pour lequel la théorie des graphes pourrait être l’outil théorique le plus utile.
Les chimistes connaissent et utilisent également un certain nombre de théorèmes issus de la théorie des graphes sans en être conscients dans de nombreux cas.$^{58}$
Un exemple classique est fourni par le concept d’hydrocarbures alternants, utilisé en chimie $^{58}$ depuis 1940 et qui revient en fait pour les théoriciens des graphes au problème des deux couleurs.$^{61}$ Par conséquent, les chimistes peuvent facilement saisir la base de la théorie des graphes.
Cependant, le langage de la théorie des graphes est différent de celui de la chimie. Puisqu’il n’y a pas de terminologie unique en théorie des graphes, un glossaire est proposé dans le tableau ci-dessous qui contient la terminologie de la théorie des graphes qui est proposée pour une utilisation standard en chimie avec les termes chimiques correspondants.
En mettant en rapport les termes de la théorie des graphes et les termes chimiques, une certaine prudence s’impose, car un ensemble de termes est tiré de la théorie abstraite et l’autre des modèles concrets utilisés en chimie. Ainsi, dans un cas, par exemple, des arbres peuvent être utilisés pour représenter des structures acycliques et dans un autre, certains schémas réactionnels.
Correspondance entre les termes issus de la théorie des graphes et ceux issus de la chimie
| Termes – théorie des graphes | Termes chimiques |
|---|---|
| Graphe chimique (moléculaire) | Formule chimique |
| Sommet (point) Vertex |
Atome |
| Sommet pondéré Weighted Vertex |
Atome d’un élément spécifié |
| Arête Edge |
Liaison chimique |
| Arête pondérée Weighted Edge |
Liaison entre deux éléments spécifiées |
| degré ou valence d’un sommet Valency of a vertex |
Valence d’un atome |
| Graphe en arbre Tree Graph |
Structure acyclique |
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1. Wilson, R. J., Introduction 10 Graph Theory, Oliver &. Boyd, Edinburgh, 1912.
2. Johnson, D. E. and Johnson, J. R., Graph Theory with Engineering Applications, Ronald Press, New York, 1972.
3. Biggs, N. L., Algebraic Graph Theory, University Press, Cambridge, 1974.
4. Avondo-Bodino, G., Economic Applications of the Theory of Graphs, Gordon & Breach,New York, 1962.
5. Harary, F., Ed., Graph Theory and Theoretical Physics, Academic Press, New York, 1967; Capra, F., Am. J. Phys 47, 11, 1979.
6. Cartwright, D. and Harary, F., Psychol. Rev., 63,277, 1963.
7. Mattuck, R. D., A Guide to Feynman Diagrams in the Many·Body Problem, McGrawHill. New York. 1967.
8. Lane, R., Elemete der Graphentheorie und ihre Anwendung in den biologischen Wissenschaften. Akademischer Verlag, Leipzig, 1970.
9. Culik, K., Application of Graph Theory to Mathematical Logic and Linguistics. Czechoslovak Academy of Sciences, Prague, 1964.
10. Flament, C., Applications of Graph Theory to Group Structure, Prentice-Hall, Englewood Cliffs, NJ, 1963.
11. Lissovski, A., Acta Protozool., II, 131, 1971.
12. Korach, M. and Hasko, L., Acta Chem. Acad. Sci. Hung., 72, 77, 1972.
13. Hage, P. and Harary, F., Structural Models in Anthropology. Cambridge University Press, Cambridge, 1983; J. Graph Theory, 10, 353, 1986.
14. Even, S., Graph Algorithms, Pitman, London, 1979.
15. Cliff, A., Haggett, P., and Ord, K., in Applications of Graph Theory, Wilson, R. J. and Beineke, L. W., Eds., Academic Press, London, 1979, 293.
16. Roberts, F., Ed., Applications of Combinatorics and Graph Theory to the Biological and Social Sciences, Springer-Verlag, New York, 1989.
17. Turro, N. J., Angew. Chem. Int. Ed. Engl., 25, 882, 1986.
18. Trinajstić, N., in MATH/CHEM/COMP 1987, Lacher. R. C., Ed., Elsevier, Amsterdam, 1988, 83.
19. Rouvray, D. H., Roy. Inst. Chem. Rev., 4, 173, 1971.
20. Gutman, I. and Trinajstić, N., Topics Curr. Chem .. 42, 49, 1973.
21. Balaban, A. T., Ed., Chemical Applications of Graph Theory, Academic Press, London, 1976.
22. Wilson, R. J., in Colloquia Mathematica Societatis Janos Bolyai, Vol. 18, Combinatorics, Keszthely, Hungary, 1976, 1147.
23. Kier, L. B. and Hall, L. H., Molecular Connectivity in Chemistry and Drug Research, Academic Press. New York, 1976.
24. Graovac, A., Gutman, I., and Trinajstić, N., Topological Approach to the Chemistry of Conjugated Molecules, Springer-Verlag, Berlin, 1977.
25. Slanina, Z., Chem. Listy, 72, I, 1978.
26. Rouvray, D. H. and Balaban, A. T., in Applications of Graph Theory, Wilson, R. J. and Beineke, L.. Eds. Academic Press. London. 1979, 177.
27. King, R. B., Ed., Chemical Applications of Topology and Graph Theory, Elsevier, Amsterdam,1983.
28. Balasubramanlan, K., Chem. Rev .85, 599, 1985.
29. Trinajstić, N., Ed., Mathematics and Computational Concepts in Chemistry, Horwood, Chichester, 1986.
30. Gutman, I. and Polansky, O. E., Mathematical Concepts in Organic Chemistry, Springer· Verlag, Berlin, 1986.
31. Kier, L. B. and Hall, L. H., Molecular Connectivity in Structure-Activity Analysis, Research Studies Press, Letchworth, Hertfordshire, 1986.
32. Slanina, Z., Contemporary Theory of Chemical Isomerism, Academia, Prague. 1986.
33. Dias, J, R., Handbook of Polycyclic Hydrocarbons. Part A. Benzenoid Hydrocarbons. Elsevier, Amsterdam, 1987.
34. King, R. B. and Rouvray, D. H., Eds., Graph Theory and Topology in Chemistry. Elsevier, Amsterdam, 1987.
35. Dias, J, R., Handbook of Polycyclic Hydrocarbons. Part B. Polycyclic Isomers and Heteroatom Analogs of Benzenoid Hydrocarbons, Elsevier, Amsterdam, 1988.
36. Lacher, R. C., Ed., MATH/CHEM/COMP 1987. Elsevier. Amsterdam. 1988.
37. Hansen, P. J. and Jurs, P. C., J. Chem. Educ .. 65, 575, 1988.
38. Gutman, I. and Cyvin, S. J. Introduction to the Theory of Benzenoid Hydrocarbons, Springer.Verlag, Berlin, 1989.
39. Graovac, A., Ed., MATH/CHEM/COMP 1988, Elsevier, Amsterdam, 1989.
40. Rouvray, D. H., Ed., Computational Chemical Graph Theory, Nova Science Publishers, Commack, NY, 199o.
41. Polansky, O. E., in Theoretical Models of Chemical Bonding, Maksic, Z. B., Ed., Springer-Verlag, Berlin, 1990, 29.
42. Bonchev, D. and Rouvray, U. H., Eds., Chemical Graph Theory: Introduction and Fundamentals, Abacus Press/Gordon & Breach Science Publishers, New York, 1991.
43. Trinajstić, N., Rep. Mol. Theory, 1, 185, 1990.
44. Balaban, A. T., J. Chem. Inf. Comput. Sci., 25. 334. 1985.
45. Balaban, A. T., J. Mol. Srruct. (Theochem ). 120, 117, 1985.
46. Trinajstić, N., Klein, D. J., and Randie, M., Int. J. Quantum. Chem.: Quantum Chem. Symp. 20, 699, 1986.
47. Prelog, V., Nobel Lecture, December 12, 1975; reprinted in Science, 193, 17, 1976.
48. Chartrand, G., Graphs as Mathematical Models. Prindle, Weber & Schmidt, Boston, 1977.
49. Lynch, M. J., Harrison, J. M., Town, V. G., and Ash, J. E., Computer Handling of Chemical Structure Information, MacDonald, London, 1971.
50. Carthart, R. E., Smith, D. H., Brown, H., and Sridharam, N. S., J. Chem. Inf. Comput. Sci., 15, 124, 1975.
51. Trinajstić, N., Nikolic, S., Knop, J. V., Müller, W. R., and Szymanski, K., Computational Chemical Graph Theory: Characterization, Enumeration and Generation of chemical Structure by Computer Methods, Simon & Schuster, Chichester, 1991.
52. Corey, E. J., Q. Rev. Chem. Soc., 25, 455, 1971.
53. Hendrickson, J. B., Grier, D. L., and Toczko, A. G., J. Am. Chem. Soc., 107, 5288, 1985.
54. Ruščic, B.,Křivka, P., and Trinajstić, N., Theor. Chim. Acta, 69, 107, 1986.
55. Cyvin, S. J. and Gutman, I., Kekule Structures in Benzenoid Hydrocarbons, Springer Verlag, Berlin. 1988.
56. Rouvray, D. H., Sci. Am 254, 40, 1986.
57. Trinajstić, N., Nikolic, S., and Carter, S., Kem. Ind. (Zagreb), 38, 469, 1989.
58. Mallion, R. B., Chem. Br., 9, 242, 1973.
59. Coulson, C. A. and Rushbrooke, G. S., Proc. Cambridge Philos. Soc 36, 193, 1940.
60. Mallion, R. B. and Rouvray, D. H., J. Math. Chem., 5, 1, 1990; J. Math. Chem 8, 399, 1991.
61. Trinajstić, N., in Semiempirical Methods of Electronic Structure Calculation. Part A. Techniques, Segal, G. A., Ed. Plenum Press, New York, 1977, 1.
62. Essam, J. W. and Fisher, M. E., Rev. Mod. Phys., 42, 272, 1970.
63. Harary, F., Graph Theory, Addison·Wesley, Reading, MA, 1971. 2nd printing.