B - P + G = 1, (*)

où B est le nombre total de sommets, P est le nombre total d'arêtes, G est le nombre de polygones (faces).

Preuve. Montrons que l'égalité ne change pas si une diagonale est tracée dans un polygone d'une partition donnée (Fig. 2, a).

a)b)

Figure 2

En effet, après avoir tracé une telle diagonale, la nouvelle partition aura B sommets, P+1 arêtes, et le nombre de polygones augmentera de un. Par conséquent, nous avons

B - (P + 1) + (G+1) = B – P + G.

En utilisant cette propriété, nous dessinons des diagonales qui divisent les polygones entrants en triangles, et pour la partition résultante, nous montrons la faisabilité de la relation.

Pour ce faire, nous supprimerons séquentiellement les arêtes externes, réduisant ainsi le nombre de triangles. Dans ce cas, deux cas sont possibles :

pour supprimer le triangle ABC, vous devez supprimer deux arêtes, dans notre cas AB et BC ;

Pour supprimer le triangle MKN, vous devez supprimer une arête, dans notre cas MN.

Dans les deux cas, l’égalité ne changera pas. Par exemple, dans le premier cas, après avoir supprimé le triangle, le graphique sera composé de sommets B-1, d'arêtes P-2 et d'un polygone G-1 :

(B - 1) - (P + 2) + (G -1) = B – P + G.

Ainsi, supprimer un triangle ne change pas l’égalité.

En poursuivant ce processus de suppression des triangles, nous arriverons finalement à une partition constituée d'un seul triangle. Pour une telle partition B = 3, P = 3, G = 1 et donc

B-P + G = 1.

Cela signifie que l'égalité vaut également pour la partition d'origine, d'où on obtient finalement que la relation est valable pour cette partition du polygone.

Notez que la relation d'Euler ne dépend pas de la forme des polygones. Les polygones peuvent être déformés, agrandis, réduits ou même courbés sur leurs côtés, à condition qu'il n'y ait pas d'espace sur les côtés. La relation d'Euler ne changera pas.

Passons maintenant à la résolution du problème des trois maisons et des trois puits.

Solution . Supposons que cela puisse être fait. Marquons les maisons par les points D1, D2, D3, et les puits par les points K1, K2, K3 (Fig. 1). Nous connectons chaque point de la maison à chaque point du puits. Nous obtenons neuf arêtes qui ne se coupent pas deux à deux.

Ces arêtes forment un polygone sur le plan, divisé en polygones plus petits. Par conséquent, pour cette partition, la relation d'Euler B - P + G = 1 doit être satisfaite.

Ajoutons une face supplémentaire aux faces considérées - la partie extérieure du plan par rapport au polygone. Alors la relation d'Euler prendra la forme B - P + G = 2, avec B = 6 et P = 9.

Par conséquent, Г = 5. Chacune des cinq faces a au moins quatre arêtes, puisque, selon les conditions du problème, aucun des chemins ne doit relier directement deux maisons ou deux puits. Puisque chaque arête repose sur exactement deux faces, le nombre d’arêtes doit être d’au moins (5 4)/2 = 10, ce qui contredit la condition selon laquelle leur nombre est 9.

La contradiction qui en résulte montre que la réponse au problème est négative - il est impossible de tracer des chemins non sécants de chaque maison à chaque village

Théorie des graphes en chimie

Application de la théorie des graphes à la construction et à l'analyse de diverses classes de graphiques chimiques et chimico-technologiques, également appelés topologie, modèles, c'est-à-dire des modèles qui prennent en compte uniquement la nature des connexions entre les sommets. Les arcs (bords) et les sommets de ces graphiques reflètent des concepts, des phénomènes, des processus ou des objets chimiques et chimico-technologiques et, par conséquent, des relations qualitatives et quantitatives ou certaines relations entre eux.

Problèmes théoriques. Les graphiques chimiques permettent de prédire les transformations chimiques, d'expliquer l'essence et de systématiser certains concepts de base de la chimie : structure, configuration, confirmations, interactions de mécanique quantique et statistique-mécanique des molécules, isomérie, etc. Les graphiques chimiques comprennent des graphiques moléculaires, bipartis et de signaux. des équations de réaction cinétique. Les graphiques moléculaires, utilisés en stéréochimie et en topologie structurale, en chimie des clusters, des polymères, etc., sont des graphiques non orientés qui affichent la structure des molécules. Les sommets et les arêtes de ces graphiques correspondent aux atomes correspondants et aux liaisons chimiques entre eux.

Dans l'organisation de stéréochimie. c-c les plus couramment utilisés sont les arbres moléculaires - arbres couvrants de graphes moléculaires qui contiennent uniquement tous les sommets correspondant aux atomes. Compiler des ensembles d'arbres moléculaires et établir leur isomorphisme permet de déterminer les structures moléculaires et de trouver le nombre total d'isomères des alcanes, alcènes et alcynes. Les graphiques moléculaires permettent de réduire les problèmes liés au codage, à la nomenclature et aux caractéristiques structurelles (ramification, cyclicité, etc.) des molécules de divers composés à l'analyse et à la comparaison de caractéristiques et propriétés purement mathématiques des graphiques moléculaires et de leurs arbres, ainsi qu'à leurs matrices correspondantes. Pour identifier le nombre de corrélations entre la structure des molécules et les propriétés physico-chimiques (y compris pharmacologiques) des composés, plus de 20 soi-disant corrélations ont été développées. Indices topologiques de molécules (Wiener, Balaban, Hosoya, Plata, Randich, etc.), déterminés à l'aide de matrices et de caractéristiques numériques d'arbres moléculaires. Par exemple, l'indice de Wiener W = (m3 + m)/6, où m est le nombre de sommets correspondant aux atomes de C, est en corrélation avec les volumes moléculaires et les réfractions, les enthalpies de formation, la viscosité, la tension superficielle, les constantes chromatographiques des composés, l'octane. nombre d'hydrocarbures et même de physiol. activité des médicaments. Les paramètres importants des graphiques moléculaires utilisés pour déterminer les formes tautomères d'une substance donnée et leur réactivité, ainsi que dans la classification des acides aminés, des acides nucléiques, des glucides et d'autres composés naturels complexes, sont la capacité d'information moyenne et totale (H). L'analyse de graphes moléculaires de polymères, dont les sommets correspondent à des unités monomères, et les arêtes correspondent à des liaisons chimiques entre eux, permet d'expliquer, par exemple, les effets de volume exclu conduisant aux qualités. changements dans les propriétés prévues des polymères. En utilisant la théorie des graphes et les principes de l'intelligence artificielle, des logiciels pour les systèmes de recherche d'informations en chimie, ainsi que des systèmes automatisés pour l'identification des structures moléculaires et la planification rationnelle de la synthèse organique, ont été développés. Pour la mise en œuvre pratique sur ordinateur d'opérations de sélection de chemins chimiques rationnels. les transformations basées sur les principes rétrosynthétiques et syntoniques utilisent des graphiques de recherche ramifiés à plusieurs niveaux pour les options de solution, dont les sommets correspondent aux graphiques moléculaires des réactifs et des produits, et les arcs représentent les transformations.

Pour résoudre des problèmes multidimensionnels d'analyse et d'optimisation des systèmes technologiques chimiques (CTS), les graphiques technologiques chimiques suivants sont utilisés : graphiques de flux, de flux d'informations, de signaux et de fiabilité. Pour étudier en chimie. La physique des perturbations dans les systèmes constitués d'un grand nombre de particules utilise ce qu'on appelle. Les diagrammes de Feynman sont des graphiques dont les sommets correspondent aux interactions élémentaires de particules physiques, les bords de leurs trajectoires après collisions. Ces graphiques permettent notamment d'étudier les mécanismes des réactions oscillatoires et de déterminer la stabilité des systèmes réactionnels. Les graphiques de flux de matières affichent l'évolution de la consommation de substances dans le CTS. Les graphiques de flux thermique affichent les bilans thermiques dans CTS ; les sommets des graphiques correspondent aux dispositifs dans lesquels la consommation thermique des flux physiques change et, en plus, aux sources et puits d'énergie thermique du système ; les arcs correspondent à des flux de chaleur physiques et fictifs (conversion d'énergie physico-chimique dans les appareils), et les poids des arcs sont égaux aux enthalpies des flux. Les graphiques de matériaux et thermiques sont utilisés pour compiler des programmes pour le développement automatisé d'algorithmes permettant de résoudre des systèmes d'équations pour les bilans de matériaux et de chaleur de systèmes chimiques complexes. Les graphiques de flux d'informations affichent la structure logique de l'information des systèmes d'équations mathématiques. Modèles XTS ; sont utilisés pour développer des algorithmes optimaux pour calculer ces systèmes. Un graphe d'information biparti est un graphe non orienté ou orienté dont les sommets correspondent respectivement. les équations fl -f6 et les variables q1 – V, et les branches reflètent leur relation. Graphique d'information – un digraphe illustrant l'ordre de résolution des équations ; les sommets du graphe correspondent à ces équations, sources et récepteurs d'informations XTS, et les branches correspondent à des informations. variables. Les graphiques de signaux correspondent à des systèmes linéaires d'équations de modèles mathématiques de processus et de systèmes technologiques chimiques. Les graphiques de fiabilité sont utilisés pour calculer divers indicateurs de fiabilité X.

Littérature utilisée:

1.Berge K., T. g. et son application, traduction du français, M., 1962 ;

2. Kemeny J., Snell J., Thompson J., Introduction aux mathématiques finies, trans. de l'anglais, 2e éd., M., 1963 ;

3.Ope O., Les graphiques et leur application, trans. de l'anglais, M., 1965 ;

4. Belykh O.V., Belyaev E.V., Possibilités d'application de la sociologie en sociologie, dans : L'Homme et la Société, vol. 1, [L.], 1966 ;

5. Méthodes quantitatives dans la recherche sociologique, M., 1966 ; Belyaev E.V., Problèmes de mesures sociologiques, "VF", 1967, n° 7 ; Bavelas. Modèles de communication dans des groupes axés sur des tâches, dans le livre. Lerner D., Lass Well H., Sciences politiques, Stanford, 1951 ;

ÉTABLISSEMENT D'ENSEIGNEMENT AUTONOME MUNICIPAL ÉCOLE SECONDAIRE N°2

Préparé

Legkokonets Vladislav, élève de classe 10A

Application pratique de la théorie des graphes

Superviseur

L.I. Noskova, professeur de mathématiques

Art. Brioukhovetskaïa

2011

1.Introduction…………………………………………………………………………………….………….3

2. Historique de l'émergence de la théorie des graphes………………………………………….………..4

3. Définitions et théorèmes de base de la théorie des graphes…………………………….………6

4. Problèmes résolus à l'aide de graphiques……………………………..………………………..8

4.1 Problèmes célèbres………………………………….………………………...8

4.2 Plusieurs problèmes intéressants………………………………….……………..9

5. Application des graphiques dans divers domaines de la vie des gens……………………………...11

6. Résoudre les problèmes………………………………………………………………………...12

7. Conclusion………………….…………………………………………………………….13

8. Liste des références………….……………………………………………………………14

9.Annexe……………………………………………………………………………….…………15

Introduction

Née de la résolution d'énigmes et de jeux divertissants, la théorie des graphes est aujourd'hui devenue un outil simple, accessible et puissant pour résoudre des questions liées à un large éventail de problèmes. Les graphiques sont littéralement omniprésents. Sous forme de graphiques, vous pouvez par exemple interpréter des cartes routières et des circuits électriques, des cartes géographiques et des molécules de composés chimiques, des connexions entre des personnes et des groupes de personnes. Au cours des quatre dernières décennies, la théorie des graphes est devenue l’une des branches mathématiques qui se développe le plus rapidement. Ceci est motivé par les exigences d’un domaine d’application en expansion rapide. Il est utilisé dans la conception de circuits intégrés et de circuits de contrôle, dans l'étude des automates, des circuits logiques, des schémas fonctionnels de programmes, en économie et statistiques, en chimie et biologie, en théorie de l'ordonnancement. C'est pourquoi pertinence Le sujet est déterminé, d'une part, par la popularité des graphiques et des méthodes de recherche associées, et, d'autre part, par un système holistique sous-développé pour sa mise en œuvre.

Résoudre de nombreux problèmes dans la vie nécessite de longs calculs, et parfois même ces calculs n'aboutissent pas. C'est ce que problème de recherche. La question se pose : est-il possible de trouver une solution simple, rationnelle, courte et élégante pour les résoudre. La résolution de problèmes est-elle plus facile si vous utilisez des graphiques ? Cela a déterminé sujet de ma recherche: « Application pratique de la théorie des graphes »

But La recherche consistait à utiliser des graphiques pour apprendre à résoudre rapidement des problèmes pratiques.

Hypothèse de recherche. La méthode graphique est très importante et est largement utilisée dans divers domaines de la science et de l'activité humaine.

Objectifs de recherche :

1. Étudiez la littérature et les ressources Internet sur cette question.

2.Vérifiez l'efficacité de la méthode graphique pour résoudre des problèmes pratiques.

3. Tirez une conclusion.

Importance pratique de l'étude c'est que les résultats susciteront sans aucun doute l'intérêt de nombreuses personnes. Aucun d’entre vous n’a-t-il essayé de construire son arbre généalogique ? Comment faire cela correctement ? Le chef d'une entreprise de transport doit probablement résoudre le problème d'une utilisation plus rentable des transports lors du transport de marchandises d'une destination vers plusieurs agglomérations. Chaque écolier a rencontré des problèmes logiques de transfusion. Il s’avère qu’ils peuvent être facilement résolus à l’aide de graphiques.

Les méthodes suivantes sont utilisées dans le travail : observation, recherche, sélection, analyse.

Histoire de la théorie des graphes

Le fondateur de la théorie des graphes est considéré comme le mathématicien Leonhard Euler (1707-1783). L'histoire de cette théorie peut être retracée à travers la correspondance du grand scientifique. Voici une traduction du texte latin, tiré de la lettre d’Euler au mathématicien et ingénieur italien Marinoni, envoyée de Saint-Pétersbourg le 13 mars 1736.

« On m'a un jour posé un problème concernant une île située dans la ville de Königsberg et entourée d'une rivière traversée par sept ponts.

[Annexe Fig.1] La question est de savoir si quelqu’un peut les contourner continuellement, en passant une seule fois par pont. Et puis on m’a informé que personne n’avait encore réussi à le faire, mais que personne n’avait prouvé que c’était impossible. Cette question, bien que triviale, m'a cependant paru digne d'attention dans la mesure où ni la géométrie, ni l'algèbre, ni l'art combinatoire ne suffisent à la résoudre. Après mûre réflexion, j'ai trouvé une règle simple, basée sur une preuve tout à fait convaincante, à l'aide de laquelle il est possible, dans tous les problèmes de ce genre, de déterminer immédiatement si un tel détour peut être fait à travers un nombre quelconque et un nombre quelconque de ponts situés ou non. Les ponts de Koenigsberg sont situés de telle manière qu'ils peuvent être représentés dans la figure suivante [Annexe Fig.2], dans lequel A désigne une île, et B, C et D - des parties du continent séparées les unes des autres par des bras fluviaux

Concernant la méthode qu’il a découverte pour résoudre des problèmes de ce genre, Euler écrit :

« Cette solution, de par sa nature, n'a apparemment pas grand-chose à voir avec les mathématiques, et je ne comprends pas pourquoi on devrait attendre cette solution d'un mathématicien plutôt que de n'importe quelle autre personne, puisque cette décision est étayée par le seul raisonnement, et il n'y a pas de raison. Il faut s’impliquer pour trouver cette solution, il existe des lois inhérentes aux mathématiques. Donc, je ne sais pas comment il se fait que des questions qui ont très peu à voir avec les mathématiques sont plus susceptibles d’être résolues par des mathématiciens que par d’autres.

Alors est-il possible de contourner les ponts du Königsberg en passant une seule fois sur chacun de ces ponts ? Pour trouver la réponse, poursuivons la lettre d'Euler à Marinoni :

"La question est de savoir s'il est possible de contourner ces sept ponts, en passant par chacun une seule fois, ou non. Ma règle conduit à la solution suivante à cette question. Tout d'abord, vous devez regarder combien de sections il y a des sections d'eau séparées - celles qui n'ont pas d'autre transition de l'une à l'autre, sauf par un pont. Dans cet exemple, il y a quatre de ces sections - A, B, C, D. Ensuite, vous devez distinguer si le nombre est le même. Le nombre de ponts menant à ces sections individuelles est pair ou impair. Ainsi, dans notre cas, cinq ponts mènent à la section A et trois ponts mènent chacun au reste, c'est-à-dire que le nombre de ponts menant à des sections individuelles est impair, et cela seul est. suffisant pour résoudre le problème. Lorsque cela est déterminé, nous appliquons la règle suivante : si le nombre de ponts menant à chaque section individuelle était pair, alors le détour en question serait possible, et en même temps il serait possible de le faire. commencer ce détour à partir de n'importe quelle section. Si deux de ces nombres étaient impairs, car un seul ne peut pas être impair, alors même alors la transition pourrait être complétée, comme prescrit, mais seul le début du détour doit certainement être pris. une de ces deux sections auxquelles mène un nombre impair de ponts. Si, finalement, il y avait plus de deux sections auxquelles mènent un nombre impair de ponts, alors un tel mouvement est généralement impossible... si d'autres problèmes plus graves pouvaient être apportés ici, cette méthode pourrait être encore plus bénéfique et devrait ne pas être négligé." .

Définitions de base et théorèmes de la théorie des graphes

La théorie des graphes est une discipline mathématique créée par les efforts de mathématiciens, sa présentation comprend donc les définitions strictes nécessaires. Passons donc à une introduction organisée des concepts de base de cette théorie.

Définition 1. Un graphe est une collection d'un nombre fini de points, appelés sommets du graphe, et de lignes par paires reliant certains de ces sommets, appelées arêtes ou arcs du graphe.

Cette définition peut être formulée différemment : un graphe est un ensemble non vide de points (sommets) et de segments (arêtes) dont les deux extrémités appartiennent à un ensemble de points donné.

Dans ce qui suit, nous désignerons les sommets du graphe par les lettres latines A, B, C, D. Parfois, le graphique dans son ensemble sera désigné par une lettre majuscule.

Définition 2. Les sommets d’un graphe qui n’appartiennent à aucune arête sont appelés isolés.

Définition 3. Un graphe constitué uniquement de sommets isolés est appelé nul - compter .

Notation : O " – un graphe avec des sommets qui n'ont pas d'arêtes

Définition 4. Un graphe dans lequel chaque paire de sommets est relié par une arête est dit complet.

Désignation : U" – un graphe composé de n sommets et arêtes reliant toutes les paires possibles de ces sommets. Un tel graphique peut être représenté comme un n-gone dans lequel toutes les diagonales sont dessinées

Définition 5. Le degré d'un sommet est le nombre d'arêtes auxquelles appartient le sommet.

Définition 6. Un graphe dont les degrés de tous les k sommets sont identiques est appelé graphe de degrés homogène. .

Définition 7. Le complément d'un graphe donné est un graphe constitué de toutes les arêtes et de leurs extrémités qu'il faut ajouter au graphe d'origine pour obtenir un graphe complet.

Définition 8. Un graphe qui peut être représenté sur un plan de telle manière que ses arêtes ne se coupent qu'aux sommets est appelé planaire.

Définition 9. Un polygone d'un graphe planaire qui ne contient aucun sommet ni arête du graphe est appelé sa face.

Les concepts de graphe planaire et de face de graphe sont utilisés pour résoudre des problèmes sur la coloration « correcte » de diverses cartes.

Définition 10. Un chemin A vers X est une séquence d’arêtes menant de A à X de telle sorte que deux arêtes adjacentes aient un sommet commun et qu’aucune arête n’apparaisse plus d’une fois.

Définition 11. Un cycle est un chemin dont les points de départ et d'arrivée coïncident.

Définition 12. Un cycle simple est un cycle qui ne passe par aucun des sommets du graphe plus d’une fois.

Définition 13. Longueur du chemin , posé sur une boucle , le nombre d'arêtes de ce chemin est appelé.

Définition 14. Deux sommets A et B dans un graphe sont dits connectés (déconnectés) s'il existe (n'existe pas) un chemin menant de A à B.

Définition 15. Un graphe est dit connecté si tous ses deux sommets sont connectés ; si le graphe contient au moins une paire de sommets déconnectés, alors le graphe est dit déconnecté.

Définition 16. Un arbre est un graphe connecté qui ne contient pas de cycles.

Un modèle tridimensionnel d'un arbre graphique est, par exemple, un arbre réel avec sa couronne aux ramifications complexes ; le fleuve et ses affluents forment également un arbre, mais déjà plat - à la surface de la terre.

Définition 17. Un graphe déconnecté composé entièrement d’arbres s’appelle une forêt.

Définition 18. Un arbre dans lequel tous les n sommets sont numérotés de 1 à n est appelé un arbre à sommets renumérotés.

Nous avons donc examiné les définitions de base de la théorie des graphes, sans lesquelles il serait impossible de prouver des théorèmes et, par conséquent, de résoudre des problèmes.

Problèmes résolus à l'aide de graphiques

Problèmes célèbres

Problème de voyageur de commerce

Le problème du voyageur de commerce est l’un des problèmes les plus connus de la théorie combinatoire. Il a été proposé en 1934 et les meilleurs mathématiciens se sont cassés les dents.

L'énoncé du problème est le suivant.
Un voyageur de commerce (marchand errant) doit quitter la première ville, visiter les villes 2,1,3..n une fois dans un ordre inconnu et revenir dans la première ville. Les distances entre les villes sont connues. Dans quel ordre faut-il parcourir les villes pour que le parcours fermé d'un voyageur de commerce soit le plus court ?

Méthode pour résoudre le problème du voyageur de commerce

Algorithme gourmand « Allez dans la ville la plus proche (dans laquelle vous n’êtes pas encore entré). »
Cet algorithme est appelé « gourmand » car dans les dernières étapes, vous devez payer cher pour la cupidité.
Prenons par exemple le réseau dans la figure [Annexe Fig.3], représentant un losange étroit. Supposons qu'un voyageur de commerce parte de la ville 1. L'algorithme « aller dans la ville la plus proche » l'amènera à la ville 2, puis 3, puis 4 ; à la dernière étape, vous devrez payer votre cupidité en revenant le long de la longue diagonale du diamant. Le résultat ne sera pas le voyage le plus court, mais le plus long.

Problème avec les ponts de Königsberg.

Le problème est formulé comme suit.
La ville de Koenigsberg est située sur les rives de la rivière Pregel et de deux îles. Les différentes parties de la ville étaient reliées par sept ponts. Le dimanche, les citadins se promenaient dans la ville. Question : est-il possible de se promener de telle sorte qu'après avoir quitté la maison, on revienne en marchant exactement une fois sur chaque pont.
Les ponts sur la rivière Pregel sont situés comme sur la photo[Annexe Fig.1].

Considérons le graphique correspondant au schéma du pont [Annexe Fig.2].

Pour répondre à la question du problème, il suffit de savoir si le graphe est eulérien. (Un nombre pair de ponts doit s'étendre à partir d'au moins un sommet). Vous ne pouvez pas vous promener dans la ville, traverser tous les ponts une fois et revenir.

Plusieurs tâches intéressantes

1. "Itinéraires".

Problème 1

Comme vous vous en souvenez, le chasseur d'âmes mortes Chichikov a rendu visite une fois à des propriétaires fonciers célèbres. Il leur rendit visite dans l'ordre suivant : Manilov, Korobochka, Nozdryov, Sobakevich, Plyushkin, Tentetnikov, le général Betrishchev, Petukh, Konstanzholgo, le colonel Koshkarev. Un diagramme a été trouvé sur lequel Chichikov a dessiné les positions relatives des domaines et des routes de campagne qui les relient. Déterminez quel domaine appartient à qui, si Chichikov n'a parcouru aucune des routes plus d'une fois [Annexe Fig. 4].

Solution:

La carte routière montre que Chichikov a commencé son voyage à partir du domaine E et s'est terminé par le domaine O. Nous notons que seules deux routes mènent aux domaines B et C, Chichikov a donc dû emprunter ces routes. Marquons-les d'une ligne grasse. Des tronçons de l'itinéraire passant par A ont été identifiés : AC et AB. Chichikov n'a pas circulé sur les routes AE, AK et AM. Rayons-les. Marquons d'un trait gras ED ; Rayons NSP. Rayons MO et MN ; Marquons MF avec une ligne grasse ; rayer FO; Marquons FH, NK et KO avec une ligne grasse. Trouvons le seul itinéraire possible dans ces conditions. Et nous obtenons : le domaine E - appartient à Manilov, D - Korobochka, C - Nozdrev, A - Sobakevich, B - Plyushkin, M - Tentetnikov, F - Betrishchev, N - Petukh, K - Konstanzholgo, O - Koshkarev [Annexe Fig.5].

Problème 2

La figure montre une carte de la zone [Annexe Fig. 6].

Vous ne pouvez vous déplacer que dans le sens des flèches. Vous ne pouvez visiter chaque point qu'une seule fois. De combien de manières pouvez-vous passer du point 1 au point 9 ? Quel itinéraire est le plus court et lequel est le plus long.

Solution:

Nous « stratifions » séquentiellement le circuit en un arbre, en commençant par le sommet 1 [Annexe Fig.7]. Prenons un arbre. Le nombre de chemins possibles pour passer de 1 à 9 est égal au nombre de sommets « suspendus » de l'arbre (il y en a 14). Évidemment, le chemin le plus court est 1-5-9 ; le plus long est 1-2-3-6-5-7-8-9.

2 "Groupes, rencontres"

Problème 1

Les participants du festival de musique, s'étant rencontrés, ont échangé des enveloppes avec des adresses. Prouver que :

a) un nombre pair d'enveloppes a été remis ;

b) le nombre de participants ayant échangé des enveloppes un nombre impair de fois est pair.

Solution : Que les participants au festival soient A 1, A 2, A 3. . . , Et n sont les sommets du graphe, et les arêtes relient des paires de sommets représentant les gars échangeant des enveloppes [Annexe Fig.8]

Solution:

a) le degré de chaque sommet A i montre le nombre d'enveloppes que le participant A i a données à ses amis. Le nombre total d'enveloppes transmises N est égal à la somme des degrés de tous les sommets du graphe N = degré. Un pas de 1 +. Un 2 + + . . . + étape. Un n -1 + degré. Et n, N =2p, où p est le nombre d'arêtes du graphe, c'est-à-dire N – même. Par conséquent, un nombre pair d'enveloppes ont été remises ;

b) dans l'égalité N = degré. Un pas de 1 +. Un 2 + + . . . + étape. Un n -1 + degré. Et n la somme des termes impairs doit être paire, et cela ne peut être que si le nombre de termes impairs est pair. Cela signifie que le nombre de participants ayant échangé des enveloppes un nombre impair de fois est pair.

Problème 2

Un jour, Andrei, Boris, Volodia, Dasha et Galya ont accepté d'aller au cinéma le soir. Ils ont décidé de coordonner le choix du cinéma et du spectacle par téléphone. Il a également été décidé que s'il n'était pas possible de contacter quelqu'un par téléphone, la sortie au cinéma serait annulée. Le soir, tout le monde n'était pas réuni au cinéma et la visite du cinéma a donc été annulée. Le lendemain, ils ont commencé à découvrir qui appelait qui. Il s'est avéré qu'Andrey a appelé Boris et Volodia, Volodia a appelé Boris et Dasha, Boris a appelé Andrey et Dasha, Dasha a appelé Andrey et Volodia et Galya a appelé Andrey, Volodia et Boris. Qui n’a pas pu joindre le téléphone et n’est donc pas venu à la réunion ?

Solution:

Dessinons cinq points et étiquetons-les avec les lettres A, B, C, D, D. Ce sont les premières lettres des noms. Relions les points qui correspondent aux noms des gars qui ont appelé.

[Annexe Fig.9]

D'après la photo, il est clair que chacun des gars - Andrey, Boris et Volodia - a téléphoné à tout le monde. C'est pour ça que ces gars sont venus au cinéma. Mais Galya et Dasha n'ont pas pu se téléphoner (les points G et E ne sont pas reliés par un segment de ligne) et donc, conformément à l'accord, ne sont pas venues au cinéma.

Application de graphiques dans divers domaines de la vie des gens

En plus des exemples donnés, les graphiques sont largement utilisés dans la construction, l'électrotechnique, la gestion, la logistique, la géographie, le génie mécanique, la sociologie, la programmation, l'automatisation des processus technologiques et de la production, la psychologie et la publicité.

Dans n’importe quel domaine scientifique et technologique, vous rencontrez des graphiques. Les graphiques sont de merveilleux objets mathématiques avec lesquels vous pouvez résoudre des problèmes mathématiques, économiques et logiques, diverses énigmes et simplifier les conditions des problèmes de physique, de chimie, d'électronique et d'automatisation. De nombreux faits mathématiques peuvent être facilement formulés dans le langage des graphiques. La théorie des graphes fait partie de nombreuses sciences. La théorie des graphes est l’une des théories mathématiques les plus belles et les plus visuelles. Récemment, la théorie des graphes trouve de plus en plus d’applications dans des problématiques appliquées. Même la chimie computationnelle a émergé – un domaine de la chimie relativement jeune basé sur l’application de la théorie des graphes.

Graphiques moléculaires, utilisés en stéréochimie et topologie structurale, chimie des clusters, polymères, etc., sont des graphiques non orientés affichant la structure des molécules [Annexe Fig.10]. Les sommets et les arêtes de ces graphiques correspondent aux atomes correspondants et aux liaisons chimiques entre eux.

Graphiques et arbres moléculaires : [Annexe Fig.10] a, b - multigraphes, respectivement. l'éthylène et le formaldéhyde; ils disent les isomères du pentane (les arbres 4, 5 sont isomorphes à l'arbre 2).

C'est surtout dans la stéréochimie des organismes. Les arbres moléculaires sont souvent utilisés - les arbres principaux des graphes moléculaires, qui contiennent uniquement tous les sommets correspondant aux atomes C. Compilation d'ensembles de moles. les arbres et l'établissement de leur isomorphisme permettent de déterminer ce qu'ils disent. structures et trouver le nombre total d'isomères d'alcanes, d'alcènes et d'alcynes

Réseaux de protéines

Les réseaux de protéines sont des groupes de protéines en interaction physique qui fonctionnent ensemble et de manière coordonnée dans une cellule, contrôlant les processus interconnectés se produisant dans le corps. [pièce jointe fig. 11].

Graphique du système hiérarchique appelé un arbre. Une caractéristique distinctive d’un arbre est qu’il n’y a qu’un seul chemin entre deux de ses sommets. L'arborescence ne contient ni cycles ni boucles.

Généralement, un arbre représentant un système hiérarchique a un sommet principal, appelé racine de l'arbre. Chaque sommet de l'arbre (à l'exception de la racine) n'a qu'un seul ancêtre - l'objet qu'il désigne est inclus dans une classe de niveau supérieur. Tout sommet d'un arbre peut générer plusieurs descendants - sommets correspondant aux classes du niveau inférieur.

Pour chaque paire de sommets d’un arbre, il existe un chemin unique qui les relie. Cette propriété est utilisée pour retrouver tous les ancêtres, par exemple, dans la lignée masculine, de toute personne dont le pedigree est représenté sous la forme d'un arbre généalogique, qui est un « arbre » au sens de la théorie des graphes.

Exemple de mon arbre généalogique [Annexe Fig. 12].

Un autre exemple. L'image montre l'arbre généalogique biblique [Annexe Fig. 13].

Résolution de problèmes

1.Tâche de transport. Qu'il y ait une base dans la ville de Krasnodar avec des matières premières qui doivent être distribuées dans les villes de Krymsk, Temryuk, Slavyansk-on-Kuban et Timashevsk en un seul voyage, en dépensant le moins de temps et de carburant possible et en revenant à Krasnodar .

Solution:

Tout d'abord, faisons un graphique de tous les itinéraires de voyage possibles [Annexe Fig.14], en tenant compte des routes réelles entre ces agglomérations et de la distance qui les sépare. Pour résoudre ce problème, nous devons créer un autre graphique, un arbre [Annexe Fig.15].

Pour la commodité de la solution, nous désignons les villes par des numéros : Krasnodar - 1, Krymsk - 2, Temryuk - 3, Slavyansk - 4, Timashevsk - 5.

Le résultat est 24 solutions, mais nous n’avons besoin que des chemins les plus courts. De toutes les solutions, seules deux sont satisfaisantes, soit 350 km.

De même, il est possible et, je pense, nécessaire de calculer les transports réels d'une localité à une autre.

Problème logique impliquant la transfusion. Le seau contient 8 litres d'eau et il y a deux casseroles d'une capacité de 5 et 3 litres. vous devez verser 4 litres d'eau dans une casserole de cinq litres et laisser 4 litres dans le seau, c'est-à-dire verser l'eau à parts égales dans le seau et dans une grande casserole.

Solution:

La situation à tout moment peut être décrite par trois chiffres [Annexe Fig. 16].

Du coup, on obtient deux solutions : une en 7 coups, l'autre en 8 coups.

Conclusion

Ainsi, pour apprendre à résoudre des problèmes, vous devez comprendre ce qu'ils sont, comment ils sont structurés, de quels composants ils sont constitués, quels sont les outils avec lesquels les problèmes sont résolus.

En résolvant des problèmes pratiques à l'aide de la théorie des graphes, il est devenu clair qu'à chaque étape, à chaque étape de leur solution, il est nécessaire de faire preuve de créativité.

Dès le début, dès la première étape, cela réside dans le fait qu'il faut être capable d'analyser et de coder l'état du problème. La deuxième étape est une notation schématique, qui consiste en une représentation géométrique des graphiques, et à cette étape l'élément de créativité est très important car il est loin d'être facile de trouver des correspondances entre les éléments de la condition et les éléments correspondants de la graphique.

En résolvant un problème de transport ou une tâche d'établissement d'un arbre généalogique, je suis arrivé à la conclusion que la méthode graphique est certainement intéressante, belle et visuelle.

Je suis devenu convaincu que les graphiques sont largement utilisés en économie, en gestion et en technologie. La théorie des graphes est également utilisée en programmation. Cela n’a pas été abordé dans ce travail, mais je pense que ce n’est qu’une question de temps.

Ce travail scientifique examine les graphiques mathématiques, leurs domaines d'application et résout plusieurs problèmes à l'aide de graphiques. La connaissance des bases de la théorie des graphes est nécessaire dans divers domaines liés à la production et à la gestion d'entreprise (par exemple, calendrier de construction du réseau, calendrier de livraison du courrier). De plus, tout en travaillant sur un article scientifique, j'ai maîtrisé le travail sur ordinateur à l'aide de l'éditeur de texte WORD. Ainsi, les objectifs du travail scientifique ont été atteints.

Ainsi, de tout ce qui précède, découle incontestablement la valeur pratique de la théorie des graphes, dont la preuve était le but de ce travail.

Littérature

Bergé K. Théorie des graphes et ses applications. -M. : III, 1962.

Kemeny J., Snell J., Thompson J. Introduction aux mathématiques finies. -M. : III, 1963.

Minerai O. Graphiques et leur application. -M. : Mir, 1965.

Harari F. Théorie des graphes. -M. : Mir, 1973.

Zykov A.A. Théorie des graphes finis. -Novossibirsk : Science, 1969.

Bérézina L.Yu. Graphiques et leur application. -M. : Éducation, 1979. -144 p.

« Soros Educational Journal » n° 11 1996 (article « Flat graphs ») ;

Gardner M. « Loisirs mathématiques », M. « Monde », 1972 (chapitre 35) ;

Olehnik S. N., Nesterenko Yu., Potapov M. K. « Vieux problèmes divertissants », M. « Science », 1988 (partie 2, section 8 ; annexe 4) ;

Application

Application

P.

Riz. 6

Riz. 7

Riz. 8

Application

Application

Application

P.

Riz. 14

Application

Résumé sur le sujet mathématiques supérieures sur le sujet :

Application de la théorie des graphes en chimie

Interprété par un étudiant du groupe NH-202

Moscou 2011
Les graphes sont le domaine des mathématiques finies qui étudie les structures discrètes ; utilisé pour résoudre divers problèmes théoriques et appliqués.
Quelques notions de base. Un graphe est un ensemble de points (sommets) et un ensemble de paires de ces points (pas nécessairement tous) reliés par des lignes (Fig. 1, a). Si les lignes du graphique sont orientées (c'est-à-dire que les flèches indiquent la direction de connexion des sommets), elles sont appelées arcs ou branches ; s'il n'est pas orienté, - les bords. En conséquence, un graphe contenant uniquement des arcs est appelé graphe orienté ou digraphe ; non orienté sur les bords uniquement ; arcs et côtes - mélangés. Un graphe ayant plusieurs arêtes est appelé un multigraphe ; un graphe contenant uniquement des arêtes appartenant à deux de ses sous-ensembles (parties) disjoints est biparti ; les arcs (arêtes) et (ou) les sommets qui correspondent à certains poids ou valeurs numériques de tout paramètre sont pondérés. Un chemin dans un graphe est une séquence alternée de sommets et d'arcs dans laquelle aucun des sommets n'est répété (par exemple, a, b sur la Fig. 1, a) ; contour - un chemin fermé dans lequel les premier et dernier sommets coïncident (par exemple, f, h) ; boucle - un arc (arête) qui commence et se termine au même sommet. Un chemin de graphe est une séquence d'arêtes dans laquelle aucun des sommets n'est répété (par exemple, c, d, e) ; cycle - une chaîne fermée dans laquelle ses sommets initial et final coïncident. Un graphe est dit connecté si une paire de ses sommets est reliée par une chaîne ou un chemin ; sinon, le graphe est dit déconnecté.
Un arbre est un graphe connecté non orienté qui ne contient ni cycles ni contours (Fig. 1, b). Le sous-graphe couvrant d'un graphe en est un sous-ensemble qui contient tous les sommets et seulement certaines arêtes. L'arbre couvrant d'un graphe est son sous-graphe couvrant, qui est un arbre. Les graphiques sont appelés isomorphes s'il existe une correspondance biunivoque entre les ensembles de leurs sommets et arêtes (arcs).
Pour résoudre les problèmes de théorie des graphes et ses applications, les graphiques sont représentés à l'aide de matrices (contiguïté, incidence, à deux lignes, etc.), ainsi que de matrices spéciales. caractéristiques numériques. Par exemple, dans la matrice d'adjacence (Fig. 1c), les lignes et colonnes correspondent aux numéros des sommets du graphe, et ses éléments prennent les valeurs 0 et 1 (respectivement l'absence et la présence d'un arc entre une paire de sommets donnée) ; dans la matrice d'incidence (Fig. 1d), les lignes correspondent aux numéros des sommets, les colonnes correspondent aux numéros des arcs, et les éléments prennent les valeurs 0, + 1 et - 1 (respectivement, l'absence , présence d'un arc entrant et sortant du sommet). Les caractéristiques numériques les plus courantes : le nombre de sommets (m), le nombre d'arcs ou d'arêtes (n), le nombre cyclomatique ou le rang du graphe (n - m + k, où k est le nombre de sous-graphes connectés dans un graphe déconnecté ; par exemple, pour le graphe de la figure 1, le rang b sera : 10-6+ 1 = 5).
L'application de la théorie des graphes repose sur la construction et l'analyse de diverses classes de graphiques chimiques et chimico-technologiques, également appelés modèles topologiques, c'est-à-dire des modèles qui prennent en compte uniquement la nature des connexions entre les sommets. Les arcs (bords) et les sommets de ces graphiques représentent des concepts, des phénomènes, des processus ou des objets chimiques et chimico-technologiques et, par conséquent, des relations qualitatives et quantitatives ou certaines relations entre eux.

Riz. 1. Illustration de quelques concepts de base : un graphe mixte ; arbre couvrant b (arcs pleins a, h, d, f, h) et un certain sous-graphe (arcs pointillés c, e, g, k, l) du digraphe ; c, r-matrices resp. contiguïté et incidence d'un digraphe.
Problèmes théoriques. Les graphiques chimiques permettent de prédire les transformations chimiques, d'expliquer l'essence et de systématiser certains concepts de base de la chimie : structure, configuration, conformations, interactions mécaniques quantiques et statistiques-mécaniques des molécules, isomérie, etc. Les graphiques chimiques comprennent les graphiques moléculaires, bipartis et de signaux. des équations de réaction cinétique.
Les graphiques moléculaires, utilisés en stéréochimie et en topologie structurale, en chimie des clusters, des polymères, etc., sont des graphiques non orientés qui affichent la structure des molécules (Fig. 2). Les sommets et les arêtes de ces graphiques correspondent respectivement aux atomes et aux liaisons chimiques entre eux.

Riz. 2. Graphiques et arbres moléculaires : a, b - multigraphes, respectivement. l'éthylène et le formaldéhyde; ils disent les isomères du pentane (les arbres 4, 5 sont isomorphes à l'arbre 2).
Dans la stéréochimie des substances organiques, les arbres moléculaires sont le plus souvent utilisés - des arbres couvrant des graphes moléculaires, qui contiennent uniquement tous les sommets correspondant aux atomes de C (Fig. 2, a et b). Compiler des ensembles d'arbres moléculaires et établir leur isomorphisme permet de déterminer les structures moléculaires et de trouver le nombre total d'isomères d'alcanes, d'alcènes et d'alcynes (Fig. 2, c).
Les graphiques moléculaires permettent de réduire les problèmes liés au codage, à la nomenclature et aux caractéristiques structurelles (ramification, cyclicité, etc.) des molécules de divers composés à l'analyse et à la comparaison de caractéristiques et propriétés purement mathématiques des graphiques moléculaires et de leurs arbres, ainsi qu'à leurs matrices correspondantes. Pour identifier des corrélations quantitatives entre la structure des molécules et les propriétés physico-chimiques (y compris pharmacologiques) des composés, plus de 20 000 noms d'indices topologiques de molécules (Wiener, Balaban, Hosoya, Plat, Randich, etc.) ont été développés, qui sont déterminé à l’aide de matrices et de caractéristiques numériques d’arbres moléculaires. Par exemple, l'indice de Wiener W = (m 3 + m)/6, où m est le nombre de sommets correspondant aux atomes de C, est en corrélation avec les volumes moléculaires et les réfractions, les enthalpies de formation, la viscosité, la tension superficielle, les constantes chromatographiques des composés, l'indice d'octane des hydrocarbures et même l'activité physiologique des médicaments.
Les paramètres importants des graphiques moléculaires utilisés pour déterminer les formes tautomères d'une substance donnée et leur réactivité, ainsi que dans la classification des acides aminés, des acides nucléiques, des glucides et d'autres composés naturels complexes, sont les capacités d'information moyennes et totales (H). Le paramètre est calculé à l'aide de la formule d'entropie d'information de Shannon : , où p t est la probabilité que les sommets m du graphique appartiennent au i-ème type, ou classe d'équivalence, k ; je = , Paramètre. L'étude des structures moléculaires telles que les clusters inorganiques ou les bandes de Möbius revient à établir l'isomorphisme des graphes moléculaires correspondants en les plaçant (embedding) dans des polyèdres complexes (par exemple des polyèdres dans le cas des clusters) ou particuliers. surfaces multidimensionnelles (par exemple, surfaces de Riemann). L'analyse de graphiques moléculaires de polymères, dont les sommets correspondent à des unités monomères et les arêtes à des liaisons chimiques entre eux, permet d'expliquer, par exemple, les effets de volume exclu, conduisant à des changements qualitatifs dans les propriétés prédites des polymères. .

Riz. 3. Graphiques de réaction : a-bipartite ; niveau de cinétique du signal b ; r 1, g 2 -r-tion; a 1 -a 6 -réactifs ; constantes de taux-k p-tsny ; Variable de transformation de Laplace complexe s.
En utilisant la théorie des graphes et les principes de l'intelligence artificielle, des logiciels ont été développés pour les systèmes de recherche d'informations en chimie, ainsi que pour les systèmes automatisés d'identification des structures moléculaires et de planification rationnelle de la synthèse organique. Pour la mise en œuvre pratique sur un ordinateur d'opérations de sélection de chemins rationnels de transformations chimiques basées sur les principes rétrosynthétiques et syntoniques, des graphes de recherche ramifiés à plusieurs niveaux d'options de solution sont utilisés, dont les sommets correspondent aux graphes moléculaires des réactifs et des produits, et les arcs représentent les transformations des substances.

Riz. 4. Système chimico-technologique à circuit unique et graphiques correspondants : a-schéma structurel ; b, c-graphiques de flux de matériaux, respectivement. par les débits massiques totaux et le débit du composant A ; r - graphique du flux thermique ; d-fragment du système d'équations (f 1 - f 6) du bilan matière, obtenu à partir de l'analyse des graphiques de la Fig. 4, b et c ; Digraphe d'information e-bipartite ; graphique d'information g, mélangeur I ; II-réacteur ; Colonne de distillation III ; IV-réfrigérateur ; I 1 -I 8 -technologie. ruisseaux; q-débit massique ; H est l'enthalpie de l'écoulement ; je. s et je*, s* - resp. sources et puits réels et fictifs de flux de matières et de chaleur ; c-concentration du réactif ; V est le volume du réacteur.
Les représentations matricielles de graphiques moléculaires de divers composés sont équivalentes (après transformation des éléments matriciels correspondants) aux méthodes matricielles de la chimie quantique. Par conséquent, la théorie des graphes est utilisée lors de la réalisation de calculs chimiques quantiques complexes : pour déterminer le nombre, les propriétés et les énergies des orbitales moléculaires, prédire la réactivité des polyènes conjugués alternés et non alternés, identifier les propriétés aromatiques et anti-aromatiques des substances, etc.
Pour étudier les perturbations dans les systèmes constitués d'un grand nombre de particules en physique chimique, on utilise des diagrammes dits de Feynman - des graphiques dont les sommets correspondent aux interactions élémentaires des particules physiques, les bords à leurs trajectoires après des collisions. Ces graphiques permettent notamment d'étudier les mécanismes des réactions oscillatoires et de déterminer la stabilité des systèmes réactionnels.
Pour sélectionner des chemins rationnels pour la transformation des molécules de réactifs pour un ensemble donné d'interactions connues, des graphiques de réactions bipartites sont utilisés (les sommets correspondent aux molécules et à ces réactions, les arcs correspondent aux interactions des molécules dans la réaction ; Fig. 3,a). De tels graphiques permettent de développer des algorithmes interactifs pour sélectionner les chemins optimaux de transformations chimiques qui nécessitent le plus petit nombre de réactions intermédiaires, le nombre minimum de réactifs dans la liste des réactifs acceptables ou obtiennent le rendement de produits le plus élevé.
Les graphiques de signaux des équations cinétiques de réaction affichent des systèmes d'équations cinétiques présentés sous forme d'opérateur algébrique (Fig. 3b). Les sommets des graphiques correspondent aux soi-disant variables d'information, ou signaux, sous forme de concentrations de réactifs, d'arcs - aux relations des signaux, et les poids des arcs sont déterminés par des constantes cinétiques. De tels graphiques sont utilisés pour étudier les mécanismes et la cinétique des réactions catalytiques complexes, les équilibres de phases complexes dans la formation de composés complexes, ainsi que pour calculer les paramètres des propriétés additives des solutions.
Problèmes appliqués. Pour résoudre des problèmes multidimensionnels d'analyse et d'optimisation des systèmes chimico-technologiques (CTS), les graphiques chimico-technologiques suivants sont utilisés (Fig. 4) : graphiques de flux, de flux d'informations, de signaux et de fiabilité. Les graphiques de débit, qui sont des digraphes pondérés, incluent des matériaux paramétriques en termes de débits massiques totaux des flux physiques et des débits massiques de certains composants ou éléments chimiques, ainsi que des graphiques thermiques. Les graphiques répertoriés correspondent aux transformations physiques et chimiques des substances et de l'énergie dans un système chimique donné.
Des graphiques de flux paramétriques affichent la transformation des paramètres (débits massiques, etc.) des flux physiques par éléments CTS ; les sommets des graphiques correspondent aux modèles mathématiques des appareils, ainsi qu'aux sources et puits des flux spécifiés, et les arcs correspondent aux flux eux-mêmes, et les poids des arcs sont égaux au nombre de paramètres du flux correspondant. Les graphiques paramétriques sont utilisés pour développer des algorithmes d'analyse des modes technologiques des systèmes chimiques multicircuits. De tels algorithmes établissent la séquence de calcul de systèmes d'équations de modèles mathématiques de dispositifs individuels de tout système pour déterminer les paramètres de ses flux de sortie avec des valeurs connues de flux d'entrée variables.
Les graphiques de flux de matières affichent les changements dans la consommation de substances chimiques. Les sommets des graphiques correspondent aux dispositifs dans lesquels sont transformés les débits massiques totaux des flux physiques et les débits massiques de certains composants ou éléments chimiques, ainsi que les sources et puits de substances des flux ou de ces composants ; En conséquence, les arcs des graphiques correspondent à des flux physiques ou à des sources et puits physiques et fictifs (transformations chimiques de substances dans des appareils) de tous composants, et les poids des arcs sont égaux aux débits massiques des deux types. Les graphiques de flux thermique affichent les bilans thermiques dans CTS ; les sommets des graphiques correspondent aux dispositifs dans lesquels la consommation thermique des flux physiques change et, en plus, aux sources et puits d'énergie thermique du système ; les arcs correspondent à des flux de chaleur physiques et fictifs (conversion d'énergie physico-chimique dans les appareils), et les poids des arcs sont égaux aux enthalpies des flux. Les graphiques de matériaux et thermiques sont utilisés pour compiler des programmes pour le développement automatisé d'algorithmes permettant de résoudre des systèmes d'équations pour les bilans de matériaux et de chaleur de systèmes chimiques complexes.
Les graphiques de stock d'informations affichent la structure d'information logique des systèmes d'équations des modèles mathématiques de CTS ; sont utilisés pour développer des algorithmes optimaux pour calculer ces systèmes. Un graphe d'information biparti (Fig. 4, e) est un graphe non orienté ou orienté dont les sommets correspondent respectivement aux équations f l -f 6 et aux variables q 1 - V, et les branches reflètent leur relation. Graphique d'information (Fig. 4, g) - un digraphe illustrant l'ordre de résolution des équations ; les sommets du graphe correspondent à ces équations, sources et récepteurs d'informations XTS, et les branches correspondent à des variables d'information.
Les graphiques de signaux correspondent à des systèmes linéaires d'équations de modèles mathématiques de processus et de systèmes technologiques chimiques. Les sommets des graphiques correspondent à des signaux (par exemple la température), et les branches correspondent à des connexions entre eux. De tels graphiques sont utilisés pour analyser les modes statiques et dynamiques des processus multiparamétriques et des systèmes chimiques, ainsi que les indicateurs d'un certain nombre de leurs propriétés les plus importantes (stabilité, sensibilité, contrôlabilité).
Les graphiques de fiabilité sont utilisés pour calculer divers indicateurs de la fiabilité des équipements chimiques. Parmi les nombreux groupes de ces graphiques (par exemple paramétriques, logiques-fonctionnels), les arbres de défaillances sont particulièrement importants. Chacun de ces arbres est un digraphe pondéré qui affiche la relation entre de nombreuses défaillances simples de processus individuels et de dispositifs CTS, qui conduisent à de nombreuses défaillances secondaires et à la défaillance résultante du système dans son ensemble.
Pour créer des complexes de programmes de synthèse automatisée d'une production optimale hautement fiable (y compris l'économie des ressources), ainsi que les principes de l'intelligence artificielle, des graphiques sémantiques orientés ou sémantiques des options de solution CTS sont utilisés. Ces graphiques, qui dans un cas particulier sont des arbres, décrivent les procédures permettant de générer un ensemble de schémas CTS alternatifs rationnels (par exemple, 14 possibles lors de la séparation d'un mélange à cinq composants de produits cibles par rectification) et les procédures de sélection ordonnée parmi eux de un schéma optimal selon un certain critère d’efficacité du système.
etc.............

De plus, au cours des 12 dernières années de sa vie, Euler fut gravement malade, devint aveugle et, malgré sa grave maladie, continua à travailler et à créer.

Les calculs statistiques montrent qu'Euler faisait en moyenne une découverte par semaine.

Il est difficile de trouver un problème mathématique qui n’ait pas été abordé dans les travaux d’Euler.

Tous les mathématiciens des générations suivantes ont étudié avec Euler d'une manière ou d'une autre, et ce n'est pas pour rien que le célèbre scientifique français P.S. Laplace disait : « Lisez Euler, il est notre maître à tous. »

Lagrange dit : « Si vous aimez vraiment les mathématiques, lisez Euler ; la présentation de ses travaux est remarquable par sa clarté et sa précision étonnantes. » En effet, l'élégance de ses calculs était portée au plus haut degré. Condorcet conclut son discours à l'Académie à la mémoire d'Euler par les mots suivants : « Alors Euler a arrêté de vivre et de calculer ! Vivre pour calculer - comme cela semble ennuyeux de l'extérieur !

Il est d’usage d’imaginer un mathématicien sec et sourd à tout ce qui intéresse le quotidien, à ce qui intéresse les gens ordinaires.

Nommé d'après Euler, c'est le problème de trois maisons et de trois puits.

Une des branches de la topologie. Un graphique est un diagramme géométrique qui est un système de lignes reliant certains points. Les points sont appelés sommets et les lignes qui les relient sont appelées arêtes (ou arcs). Tous les problèmes de théorie des graphes peuvent être résolus sous forme graphique et matricielle. Dans le cas de l'écriture sous forme matricielle, la possibilité de transmettre un message d'un sommet donné à un autre est notée par un, et son absence est notée par zéro.

L'origine de la théorie des graphes au XVIIIe siècle. associé à des énigmes mathématiques, mais une impulsion particulièrement forte pour son développement a été donnée au 19e siècle. et principalement au 20ème siècle, lorsque les possibilités de ses applications pratiques ont été découvertes : pour calculer des circuits radioélectroniques, résoudre ce qu'on appelle. tâches de transport, etc. Depuis les années 50. La théorie des graphes est de plus en plus utilisée en psychologie sociale et en sociologie.

Dans le domaine de la théorie des graphes, il faut citer les travaux de F. Harry, J. Kemeny, K. Flament, J. Snell, J. French, R. Norman, O. Oyser, A. Beivelas, R. Weiss, etc. . En URSS, selon les travaux de T. g. M. Borodkine et coll.

Le langage de théorie des graphes est bien adapté à l’analyse de divers types de structures et au transfert d’états. Conformément à cela, nous pouvons distinguer les types suivants de problèmes sociologiques et socio-psychologiques résolus à l'aide de la théorie des graphes.

Formalisation et construction d'un modèle structurel général d'un objet social à différents niveaux de sa complexité. Par exemple, un schéma structurel d'une organisation, des sociogrammes, une comparaison des systèmes de parenté dans différentes sociétés, une analyse de la structure des rôles des groupes, etc.

On peut considérer que la structure des rôles comprend trois composantes : les personnes, les postes (dans une version simplifiée - postes) et les tâches effectuées dans un poste donné.

Chaque composant peut être représenté sous forme de graphique :

Il est possible de combiner les trois graphiques pour toutes les positions ou pour une seule, et nous obtenons ainsi une idée claire de la structure spécifique d'un c.l. ce rôle. Ainsi, pour le rôle de la position P5 nous avons un graphique (Fig.). L'intégration de relations informelles dans la structure formelle spécifiée compliquera considérablement le graphique, mais ce sera une copie plus précise de la réalité.

a) les quantités. évaluer le poids (le statut) d'un individu dans une organisation hiérarchique. L'une des options possibles pour déterminer le statut est la formule :

où r (p) est le statut d'une certaine personne p, k est la valeur du niveau de subordination, défini comme le plus petit nombre d'étapes d'une personne donnée à son subordonné, nk est le nombre de personnes à un niveau donné k . Par exemple, dans l’organisation représentée par ce qui suit. Compter:

poids a=1·2+2·7+3·4=28 ; 6=1·3+2·3=9, etc.

b) détermination du chef de groupe. Le leader se caractérise généralement par une plus grande connectivité avec le reste du groupe par rapport aux autres. Comme dans la tâche précédente, diverses méthodes peuvent également être utilisées ici pour identifier le leader.

La méthode la plus simple est donnée par la formule : r=Σdxy/Σdqx, soit le quotient de la division de la somme de toutes les distances de chaque personne à toutes les autres par la somme des distances d'un individu donné à toutes les autres.

4) Analyse de l'efficacité de l'activité de ce système, qui comprend également des tâches telles que la recherche de la structure optimale de l'organisation, l'augmentation de la cohésion du groupe, l'analyse du système social du point de vue de sa durabilité ; étude des flux d'informations (transmission de messages lors de la résolution de problèmes, influence des membres du groupe les uns sur les autres dans le processus d'unification du groupe) ; avec l'aide de la technologie, ils résolvent le problème de la recherche d'un réseau de communication optimal.

Lorsqu'on l'applique à la théorie des graphes, ainsi qu'à tout appareil mathématique, il est vrai que les principes de base pour résoudre un problème sont fixés par une théorie substantielle (en l'occurrence, la sociologie).

Tâche : Trois voisins ont trois puits communs. Est-il possible de construire des chemins sans croisement de chaque maison à chaque puits ? Les chemins ne peuvent pas traverser des puits et des maisons (Fig. 1).

Riz. 1. Au problème des maisons et des puits.

Pour résoudre ce problème, nous utiliserons un théorème prouvé par Euler en 1752, qui est l'un des principaux de la théorie des graphes. Le premier ouvrage sur la théorie des graphes appartient à Leonhard Euler (1736), bien que le terme « graphe » ait été introduit pour la première fois en 1936 par le mathématicien hongrois Dénes König. Les graphiques étaient appelés diagrammes constitués de points et de segments de lignes droites ou de courbes reliant ces points.

Théorème. Si un polygone est divisé en un nombre fini de polygones de telle sorte que deux polygones quelconques de la partition soit n'ont pas de points communs, soit ont des sommets communs, soit ont des arêtes communes, alors l'égalité est vraie.

B - P + G = 1, (*)

où B est le nombre total de sommets, P est le nombre total d'arêtes, G est le nombre de polygones (faces).

Preuve. Montrons que l'égalité ne change pas si une diagonale est tracée dans un polygone d'une partition donnée (Fig. 2, a).

UN) b)

En effet, après avoir tracé une telle diagonale, la nouvelle partition aura B sommets, P+1 arêtes, et le nombre de polygones augmentera de un. Par conséquent, nous avons

B - (P + 1) + (G+1) = B – P + G.

En utilisant cette propriété, nous dessinons des diagonales qui divisent les polygones entrants en triangles, et pour la partition résultante, nous montrons la faisabilité de la relation.

Pour ce faire, nous supprimerons séquentiellement les arêtes externes, réduisant ainsi le nombre de triangles. Dans ce cas, deux cas sont possibles :

pour supprimer le triangle ABC, vous devez supprimer deux arêtes, dans notre cas AB et BC ;

Pour supprimer le triangle MKN, vous devez supprimer une arête, dans notre cas MN.

Dans les deux cas, l’égalité ne changera pas. Par exemple, dans le premier cas, après avoir supprimé le triangle, le graphique sera composé de sommets B-1, d'arêtes P-2 et d'un polygone G-1 :

(B - 1) - (P + 2) + (G -1) = B – P + G.

Ainsi, supprimer un triangle ne change pas l’égalité.

En poursuivant ce processus de suppression des triangles, nous arriverons finalement à une partition constituée d'un seul triangle. Pour une telle partition B = 3, P = 3, G = 1 et donc

Cela signifie que l'égalité vaut également pour la partition d'origine, d'où on obtient finalement que la relation est valable pour cette partition du polygone.

Notez que la relation d'Euler ne dépend pas de la forme des polygones. Les polygones peuvent être déformés, agrandis, réduits ou même courbés sur leurs côtés, à condition qu'il n'y ait pas d'espace sur les côtés. La relation d'Euler ne changera pas.

Passons maintenant à la résolution du problème des trois maisons et des trois puits.

Solution. Supposons que cela puisse être fait. Marquons les maisons par les points D1, D2, D3, et les puits par les points K1, K2, K3 (Fig. 1). Nous connectons chaque point de la maison à chaque point du puits. Nous obtenons neuf arêtes qui ne se coupent pas deux à deux.

Ces arêtes forment un polygone sur le plan, divisé en polygones plus petits. Par conséquent, pour cette partition, la relation d'Euler B - P + G = 1 doit être satisfaite.

Ajoutons une face supplémentaire aux faces considérées - la partie extérieure du plan par rapport au polygone. Alors la relation d'Euler prendra la forme B - P + G = 2, avec B = 6 et P = 9.

Par conséquent, Г = 5. Chacune des cinq faces a au moins quatre arêtes, puisque, selon les conditions du problème, aucun des chemins ne doit relier directement deux maisons ou deux puits. Puisque chaque arête repose sur exactement deux faces, le nombre d’arêtes doit être d’au moins (5 4)/2 = 10, ce qui contredit la condition selon laquelle leur nombre est 9.

La contradiction qui en résulte montre que la réponse au problème est négative - il est impossible de tracer des chemins non sécants de chaque maison à chaque village

Théorie des graphes en chimie

Application de la théorie des graphes à la construction et à l'analyse de diverses classes de graphiques chimiques et chimico-technologiques, également appelés topologie, modèles, c'est-à-dire des modèles qui prennent en compte uniquement la nature des connexions entre les sommets. Les arcs (bords) et les sommets de ces graphiques reflètent des concepts, des phénomènes, des processus ou des objets chimiques et chimico-technologiques et, par conséquent, des relations qualitatives et quantitatives ou certaines relations entre eux.

Problèmes théoriques. Les graphiques chimiques permettent de prédire les transformations chimiques, d'expliquer l'essence et de systématiser certains concepts de base de la chimie : structure, configuration, confirmations, interactions de mécanique quantique et statistique-mécanique des molécules, isomérie, etc. Les graphiques chimiques comprennent des graphiques moléculaires, bipartis et de signaux. des équations de réaction cinétique. Les graphiques moléculaires, utilisés en stéréochimie et en topologie structurale, en chimie des clusters, des polymères, etc., sont des graphiques non orientés qui affichent la structure des molécules. Les sommets et les arêtes de ces graphiques correspondent aux atomes correspondants et aux liaisons chimiques entre eux.

Dans l'organisation de stéréochimie. c-c les plus couramment utilisés sont les arbres moléculaires - arbres couvrants de graphes moléculaires qui contiennent uniquement tous les sommets correspondant aux atomes. Compiler des ensembles d'arbres moléculaires et établir leur isomorphisme permet de déterminer les structures moléculaires et de trouver le nombre total d'isomères des alcanes, alcènes et alcynes. Les graphiques moléculaires permettent de réduire les problèmes liés au codage, à la nomenclature et aux caractéristiques structurelles (ramification, cyclicité, etc.) des molécules de divers composés à l'analyse et à la comparaison de caractéristiques et propriétés purement mathématiques des graphiques moléculaires et de leurs arbres, ainsi qu'à leurs matrices correspondantes. Pour identifier le nombre de corrélations entre la structure des molécules et les propriétés physico-chimiques (y compris pharmacologiques) des composés, plus de 20 soi-disant corrélations ont été développées. Indices topologiques de molécules (Wiener, Balaban, Hosoya, Plata, Randich, etc.), déterminés à l'aide de matrices et de caractéristiques numériques d'arbres moléculaires. Par exemple, l'indice de Wiener W = (m3 + m)/6, où m est le nombre de sommets correspondant aux atomes de C, est en corrélation avec les volumes moléculaires et les réfractions, les enthalpies de formation, la viscosité, la tension superficielle, les constantes chromatographiques des composés, l'octane. nombre d'hydrocarbures et même de physiol. activité des médicaments. Les paramètres importants des graphiques moléculaires utilisés pour déterminer les formes tautomères d'une substance donnée et leur réactivité, ainsi que dans la classification des acides aminés, des acides nucléiques, des glucides et d'autres composés naturels complexes, sont la capacité d'information moyenne et totale (H). L'analyse de graphes moléculaires de polymères, dont les sommets correspondent à des unités monomères, et les arêtes correspondent à des liaisons chimiques entre eux, permet d'expliquer, par exemple, les effets de volume exclu conduisant aux qualités. changements dans les propriétés prévues des polymères. En utilisant la théorie des graphes et les principes de l'intelligence artificielle, des logiciels ont été développés pour les systèmes de recherche d'informations en chimie, ainsi que pour les systèmes automatisés d'identification des structures moléculaires et de planification rationnelle de la synthèse organique. Pour la mise en œuvre pratique sur ordinateur d'opérations de sélection de chemins chimiques rationnels. les transformations basées sur les principes rétrosynthétiques et syntoniques utilisent des graphiques de recherche ramifiés à plusieurs niveaux pour les options de solution, dont les sommets correspondent aux graphiques moléculaires des réactifs et des produits, et les arcs représentent les transformations.

Pour résoudre des problèmes multidimensionnels d'analyse et d'optimisation des systèmes technologiques chimiques (CTS), les graphiques technologiques chimiques suivants sont utilisés : graphiques de flux, de flux d'informations, de signaux et de fiabilité. Pour étudier en chimie. La physique des perturbations dans les systèmes constitués d'un grand nombre de particules utilise ce qu'on appelle. Les diagrammes de Feynman sont des graphiques dont les sommets correspondent aux interactions élémentaires de particules physiques, les bords de leurs trajectoires après collisions. Ces graphiques permettent notamment d'étudier les mécanismes des réactions oscillatoires et de déterminer la stabilité des systèmes réactionnels. Les graphiques de flux de matières affichent les changements de débits dans les systèmes de chauffage chimique. Les graphiques de flux thermique affichent les bilans thermiques dans les systèmes de chauffage chimique ; les sommets des graphiques correspondent aux dispositifs dans lesquels la consommation thermique des flux physiques change et, en plus, aux sources et puits d'énergie thermique du système ; les arcs correspondent à des flux de chaleur physiques et fictifs (conversion d'énergie physico-chimique dans les appareils), et les poids des arcs sont égaux aux enthalpies des flux. Les graphiques de matériaux et thermiques sont utilisés pour compiler des programmes pour le développement automatisé d'algorithmes permettant de résoudre des systèmes d'équations pour les bilans de matériaux et de chaleur de systèmes chimiques complexes. Les graphiques de flux d'informations affichent la structure logique de l'information des systèmes d'équations mathématiques. Modèles XTS ; sont utilisés pour développer des algorithmes optimaux pour calculer ces systèmes. Un graphe d'information biparti est un graphe non orienté ou orienté dont les sommets correspondent respectivement. les équations fl -f6 et les variables q1 – V, et les branches reflètent leur relation. Graphique d'information – un digraphe illustrant l'ordre de résolution des équations ; les sommets du graphe correspondent à ces équations, sources et récepteurs d'informations XTS, et les branches correspondent à des informations. variables. Les graphiques de signaux correspondent à des systèmes linéaires d'équations de modèles mathématiques de processus et de systèmes technologiques chimiques. Les graphiques de fiabilité sont utilisés pour calculer divers indicateurs de fiabilité X.

Littérature utilisée:

1.Berge K., T. g. et son application, traduction du français, M., 1962 ;

2. Kemeny J., Snell J., Thompson J., Introduction aux mathématiques finies, trans. de l'anglais, 2e éd., M., 1963 ;

3.Ope O., Les graphiques et leur application, trans. de l'anglais, M., 1965 ;

4. Belykh O.V., Belyaev E.V., Possibilités d'application de la sociologie en sociologie, dans : L'Homme et la Société, vol. 1, [L.], 1966 ;

5. Méthodes quantitatives dans la recherche sociologique, M., 1966 ; Belyaev E.V., Problèmes de mesures sociologiques, "VF", 1967, n° 7 ; Bavelas. Modèles de communication dans des groupes axés sur des tâches, dans le livre. Lerner D., Lass Well H., Sciences politiques, Stanford, 1951 ;

6. Kemeny J. G., Snell J., Modèles mathématiques dans les sciences sociales, N. Y., 1962 ; Filament C., Applications de la théorie des graphes à la structure des groupes, N. Y., 1963 ; Оeser Ο. A., Hararu F., Structures de rôle et description en termes de théorie des graphes, dans le livre : Biddle V., Thomas E. J., Théorie des rôles : concepts et recherche, N. Y., 1966. E. Belyaev. Léningrad.