É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.Bryoukhovetskaya

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 pourrez par exemple interpréter des cartes routières et des circuits électriques, Cartes géographiques et des molécules composants chimiques, les liens entre les personnes et les 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 quoi 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 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 recherche 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.

« Un jour, on m'a 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 banale, me paraissait pourtant digne d'attention car ni la géométrie, ni l'algèbre, ni l'art combinatoire ne suffisent à le 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, car cette décision est soutenue par le seul raisonnement, et il n'y a pas de raison. Il faut impliquer, pour trouver cette solution, toutes les 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 ont plus de chances 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 déterminer 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 zones il y a sont, séparés par l'eau - tels , qui n'ont pas d'autre passage de l'un à l'autre que par un pont. Dans cet exemple, il y a quatre de ces sections - A, B, C, D. Ensuite, vous devez distinguer si le nombre 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 chacun au reste, c'est-à-dire que le nombre de ponts menant à des sections individuelles est impair, et cela seul suffit pour résoudre le problème. Une fois cela déterminé, nous appliquons la règle suivante : si le nombre de ponts menant à chaque section individuelle était pair, alors le contournement sur lequel nous parlons de, serait possible, et en même temps il serait possible de démarrer ce contournement depuis n'importe quel site. Si deux de ces nombres étaient impairs, car un seul ne peut pas être impair, alors même alors la transition pourrait avoir lieu, comme prescrit, mais seul le début du détour doit certainement être pris à partir de l'un de ces deux tronçons vers lesquels il n'y a pas de chemin. . nombre pair des 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 graphique est une collection nombre fini des points appelés sommets du graphe, et des lignes reliant certains de ces sommets par paires, 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 avec des lettres latines A B C D. Parfois, nous désignerons le graphique dans son ensemble par un lettre capitale.

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é.
Considérons 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'en sortant de 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 tu te souviens, le chasseur âmes mortes Chichikov a rendu visite à des propriétaires fonciers célèbres une fois chacun. 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é arrangement mutuel domaines et 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 d'un trait gras MF ; 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 - Nozdryov, 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. Nombre moyens possibles les coups de 1 à 9 sont égaux 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. Prouve-le:

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. Nombre total des 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, Andreï, 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, alors 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 téléphoner 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é. 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 cette étude.

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 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. On utilise souvent des arbres moléculaires - les arbres principaux des graphes moléculaires, qui contiennent uniquement tous les sommets correspondant aux atomes C. Compilation d'ensembles de mol. les arbres et l'établissement de leur isomorphisme permettent de déterminer ce qu'ils disent. structures et trouver numéro complet 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. onze].

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

Généralement l'arbre représentant système hiérarchique, un sommet principal est identifié, 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].

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

Résolution de problème

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, à quoi servent-ils ? Composants ils consistent en les outils utilisés pour résoudre les problèmes.

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 cet ouvrage, 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 en texte Éditeur de mots. Ainsi, les tâches travail scientifique complété.

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. La 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. V., 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

Application

P.

Riz. 14

application

Application

La théorie des graphes trouve des applications, par exemple, dans les systèmes d'information géographique (SIG). Les maisons, structures, blocs, etc. existants ou nouvellement conçus sont considérés comme des sommets, et les routes, réseaux publics, lignes électriques, etc. qui les relient sont considérés comme des bords. L'utilisation de différents calculs effectués sur un tel graphique permet par exemple de trouver le détour le plus court ou l'épicerie la plus proche, ou encore de planifier l'itinéraire optimal.

La théorie des graphes contient un grand nombre de problèmes non résolus et d’hypothèses non encore prouvées.

Les principaux domaines d'application de la théorie des graphes :

En chimie (pour décrire les structures, les cheminements de réactions complexes, la règle de phase peut aussi être interprétée comme un problème de théorie des graphes) ; La chimie computationnelle est un domaine de la chimie relativement jeune basé sur l'application de la théorie des graphes. La théorie des graphes est la base mathématique de la chimioinformatique. La théorie des graphes permet de déterminer avec précision le nombre d'isomères théoriquement possibles d'hydrocarbures et d'autres composés organiques ;

En informatique et programmation (schéma graphique de l'algorithme) ;

Dans les systèmes de communication et de transport. Notamment pour le routage de données sur Internet ;

En économie;

En logistique;

En conception de circuits (la topologie des interconnexions d'éléments sur un circuit imprimé ou un microcircuit est un graphe ou un hypergraphe).

Il existe un type particulier de graphique, arbre.Arbre est un graphe acyclique connecté. La connectivité signifie la présence de chemins entre n'importe quelle paire de sommets, l'acyclicité signifie l'absence de cycles et le fait qu'il n'y a qu'un seul chemin entre des paires de sommets. Sur Figure 1.3 présenté arbre binaire.

Arbre binaire- une structure de données arborescente dans laquelle chaque nœud n'a pas plus de deux descendance(enfants). Généralement, le premier s'appelle nœud parent, et les enfants s'appellent gauche Et héritiers légitimes.

Représentation matricielle des graphiques. Matrice des incidents.

Le développement d'approches algorithmiques pour l'analyse des propriétés des graphiques nécessite certaines méthodes de description des graphiques plus adaptées aux calculs pratiques, notamment à l'aide d'un ordinateur. Examinons les trois manières les plus courantes de représenter des graphiques.

Supposons que tous les sommets et toutes les arêtes d'un graphe non orienté ou tous les sommets et tous les arcs (y compris les boucles) d'un graphe orienté soient numérotés à partir de un. Un graphe (non orienté ou orienté) peut être représenté comme une matrice de type , où est le nombre de sommets et est le nombre d'arêtes (ou d'arcs). Pour un graphe non orienté, les éléments de cette matrice sont précisés comme suit :

Pour un graphe orienté, les éléments de la matrice sont spécifiés comme suit :

Une matrice de type ainsi définie est appelée matrice des incidents.

Un exemple d'obtention d'une matrice d'incidents. Pour le graphique ci-dessous ( Riz. 2.1 unGraphique 2.1b).

Fig. 2.1 a Fig. 2.1b

Matrice de contiguïté.

Malgré le fait que la représentation d'un graphique sous forme de matrice d'incidence joue un rôle très important dans la recherche théorique, en pratique cette méthode est très inefficace. Tout d'abord, la matrice ne comporte que deux éléments non nuls dans chaque colonne, ce qui rend cette méthode de représentation d'un graphe peu économique lorsqu'il y a un grand nombre de sommets. De plus, résoudre des problèmes pratiques à l'aide d'une matrice d'incidents demande beaucoup de travail.

Estimons, par exemple, le temps nécessaire pour résoudre un problème aussi simple dans un graphe orienté en utilisant la matrice d'incidence : pour un sommet donné, trouvez son « environnement » - l'ensemble des successeurs et l'ensemble des prédécesseurs du sommet, c'est-à-dire l'ensemble de tous les sommets à partir desquels il est directement accessible, et l'ensemble de tous les sommets à partir desquels il est directement accessible.

Pour résoudre ce problème sur la matrice d'incidence d'un graphe orienté, il faut parcourir la ligne avec le nombre jusqu'à ce qu'un élément non nul apparaisse (+1 ou –1). Si +1 est détecté, dans la colonne correspondante, vous devez trouver la ligne dans laquelle le nombre –1 est écrit. Le numéro de la ligne dans laquelle apparaît ce numéro donne le numéro du sommet directement accessible depuis ce sommet. Si -1 est détecté, vous devez trouver la ligne dans la colonne qui contient 1 et obtenir le numéro du sommet à partir duquel elle est directement accessible ce sommet. Pour obtenir l'intégralité de « l'environnement », vous devez effectuer la recherche spécifiée pour tous les éléments non nuls de la k-ème ligne. La procédure la plus longue consiste à rechercher un élément non nul dans une colonne. Le nombre de ces procédures de recherche est égal au degré du sommet. Dans ce cas, nous dirons que la complexité de l'algorithme d'analyse de l'environnement d'un sommet est de (ordre).

On peut voir que la recherche de « l’environnement » de tous les sommets prendra un temps de l’ordre du produit du nombre de sommets d’un graphe orienté par la somme des degrés de tous les sommets, ce qui, comme on peut le montrer, est proportionnel au nombre d'arcs du graphe orienté. Ainsi, la complexité de l'algorithme de recherche « environnement » est , c'est-à-dire : la recherche prend du temps de l'ordre du produit du nombre de sommets par le nombre d'arcs.

Une structure matricielle plus efficace représentant un graphique est matrice de contiguïté des sommets, ou Matrice booléenne graphique. C'est une matrice carrée d'ordre B n, dont les éléments sont définis comme suit :

pour un graphe non orienté :

pour un graphe orienté :

Pour le graphique ci-dessous ( Riz. 2.2 un) la matrice d'incidence sera la matrice présentée sur ( Graphique 2.2b).

Le début de la théorie des graphes est unanimement attribué à 1736, lorsque L. Euler résolut le problème des ponts de Königsberg, alors populaire. Cependant, ce résultat est resté le seul résultat de la théorie des graphes pendant plus de cent ans. Ce n'est qu'au milieu du XIXe siècle que l'ingénieur électricien G. Kirchhoff a développé la théorie des arbres à des fins de recherche. circuits électriques, et le mathématicien A. Cayley, dans le cadre de la description de la structure des hydrocarbures, ont résolu des problèmes de dénombrement pour trois types d'arbres.

Né en résolvant des énigmes et des jeux divertissants (problèmes concernant les chevaliers d'échecs, les reines, " voyage autour du monde", problèmes de mariages et de harems, etc.), 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. Dans une large mesure, les méthodes mathématiques pénètrent désormais dans la science et la technologie grâce à la théorie des graphes.

Cet article ne considère pas les problèmes propres à la théorie des graphes, mais la manière dont elle est utilisée dans cours scolaire géométrie.

Par conséquent, la pertinence du sujet de recherche est due, d'une part, à la popularité des graphiques et des méthodes de recherche associées, qui imprègnent organiquement presque toutes les mathématiques modernes à différents niveaux, et d'autre part, au système holistique pour sa mise en œuvre dans aucun cours de géométrie n’a été développé.

Le but de l'étude est d'étudier l'utilisation des graphiques dans un cours de géométrie scolaire.

L'objet est le processus d'enseignement de la géométrie.

Sujet – travail en classe et parascolaire

Objectifs : 1) déterminer l'essence et le contenu de l'utilisation des graphiques dans un cours de géométrie scolaire ;

2) développer un PMC pour donner des cours de géométrie de la 7e à la 9e année.

Le sujet principal est la construction d'un modèle graphique pour prouver des théorèmes géométriques.

Base théorique :

1. La théorie des graphes, née en 1736 (Léonard Euler (1708-1783), a connu un développement rapide et reste d'actualité aujourd'hui, car dans Vie courante Les illustrations graphiques, les représentations géométriques et d'autres techniques et méthodes de visualisation sont de plus en plus utilisées.

1. La théorie des graphes est utilisée dans divers domaines des mathématiques modernes et ses nombreuses applications (Lipatov E. P.)

2. La théorie des graphes est utilisée dans des domaines mathématiques tels que la logique mathématique, la combinatoire, etc.

La signification théorique du travail réside dans :

Identification des domaines d'application de la théorie des graphes ;

Utiliser la théorie des graphes pour étudier des théorèmes et des problèmes géométriques ;

L'importance pratique du travail réside dans l'utilisation de graphiques pour prouver des théorèmes géométriques et résoudre des problèmes.

À la suite de ce travail, les éléments suivants ont été créés :

Complexe logiciel et méthodologique pour animer des cours de géométrie de la 7e à la 9e année.

La chose la plus difficile pour trouver une solution à un problème est d’établir une chaîne de conséquences logiques qui mène à une affirmation prouvée. Afin de raisonner logiquement avec compétence, il est nécessaire de développer les compétences d'une telle pensée qui aideraient à transformer des faits géométriques disparates en relations logiques.

Les formes jouent un rôle particulier dans le développement des compétences d'une culture de pensée. en écrivantétudiants. Les formes de travail écrit constituent le type d'activité le plus important qui développe des compétences stables en raisonnement logique lors de la preuve de théorèmes et de la résolution de problèmes. La forme d'enregistrement des conditions du problème, les abréviations et notations raisonnables dans les calculs et les preuves de problèmes disciplinent la pensée et favorisent la vision géométrique. Comme vous le savez, la vision donne naissance à la pensée. Un problème se pose : comment établir des liens logiques entre des faits géométriques disparates et comment les former en un tout unique. La méthode des diagrammes graphiques vous permet de voir la progression de la preuve des théorèmes et de la résolution des problèmes, ce qui rend la preuve plus visuelle et vous permet de présenter brièvement et avec précision les preuves des théorèmes et la résolution des problèmes.

Un graphique arborescent est utilisé pour cela.

Les sommets de « l'arbre » (les conditions du théorème ou du problème et la séquence de connecteurs logiques) sont représentés par des rectangles contenant des informations, qui sont ensuite reliés par des flèches. La fin du diagramme graphique contient l’énoncé à prouver. La forme décrite de preuve de théorèmes et de résolution de problèmes est utile et pratique pour les étudiants, car elle permet d'identifier facilement les principales étapes de la preuve des théorèmes et de la résolution du problème.

Partie recherche.

Section 1. Etude de l'histoire de l'émergence 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 sur laquelle sont jetés sept ponts. La question est de savoir si quelqu'un peut les contourner en continu, en passant une seule fois par chaque pont. Et puis j'ai été interrogé. informé que personne ne pouvait encore le faire, mais personne n'a prouvé que c'était impossible. Cette question, bien que triviale, m'a cependant semblé digne d'attention dans la mesure où ni la géométrie, ni l'algèbre, ni l'art combinatoire ne suffisent à 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 de déterminer immédiatement dans tous les problèmes de ce genre si un tel détour peut être effectué par un certain nombre de ponts situés dans de quelque manière que ce soit, de sorte qu'ils peuvent être représentés dans la figure suivante, dans laquelle A désigne l'île, et B, C et D les parties du continent séparées les unes des autres par les bras du fleuve. Les sept ponts sont désignés par les lettres a, b, c, d, e, f, g".

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, car cette décision est soutenue par le seul raisonnement, et il n'y a pas de raison. Il faut impliquer, pour trouver cette solution, toutes les 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 ont plus de chances 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 déterminer 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 zones il y a sont, séparés par l'eau - tels , qui n'ont pas d'autre passage de l'un à l'autre, sauf par un pont. Dans cet exemple, il existe quatre de ces sections - A, B, C, D. Ensuite, vous devez distinguer si le nombre 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 chacun au reste, c'est-à-dire que le nombre de ponts menant à des sections individuelles est impair, et cela seul suffit pour résoudre le problème. Une fois celui-ci déterminé, on applique la règle suivante : si le nombre de ponts menant à chaque tronçon distinct était pair, alors le détour en question serait possible, et en même temps il serait possible de commencer ce détour détour de n'importe quelle section. Si, toutefois, deux de ces nombres étaient s'ils é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 de 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 serait absolument impossible ; si d'autres problèmes plus graves pouvaient être soulevés ici, cette méthode pourrait être encore plus bénéfique et devrait ne soit pas négligé. »

La justification de la règle ci-dessus se trouve dans une lettre de L. Euler à son ami Ehler datée du 3 avril de la même année. Nous reprenons ci-dessous un extrait de cette lettre.

Le mathématicien a écrit que la transition est possible s'il n'y a pas plus de deux zones à l'embranchement de la rivière, auxquelles mènent un nombre impair de ponts. Pour faciliter l'imagination, nous effacerons les ponts déjà traversés sur la figure. Il est facile de vérifier que si nous commençons à nous déplacer conformément aux règles d'Euler, traversons un pont et l'effaçons, alors la figure montrera une section où, encore une fois, il n'y a pas plus de deux zones auxquelles mène un nombre impair de ponts, et s'il y a sont des zones avec un nombre impair de ponts, nous serons situés dans l'une d'entre elles. En continuant à avancer ainsi, nous traverserons tous les ponts une fois.

L'histoire des ponts de la ville de Königsberg a une suite moderne.

Problème Il y a sept îles sur le lac, qui sont reliées les unes aux autres comme le montre la figure 2. Vers quelle île un bateau doit-il emmener les voyageurs pour qu'ils puissent traverser chaque pont et une seule fois ? Pourquoi les voyageurs ne peuvent-ils pas être transportés vers l’île A ?

Solution. Puisque ce problème est similaire à celui des ponts de Königsberg, nous utiliserons également la règle d’Euler pour le résoudre. Du coup, on obtient la réponse suivante : le bateau doit emmener les voyageurs vers l'île E ou F afin qu'ils puissent traverser une fois chaque pont. De la même règle d'Euler il résulte que le détour requis est impossible s'il part de l'île A.

Par la suite, Koenig (1774-1833), Hamilton (1805-1865) et les mathématiciens modernes C. Berge, O. Ore, A. Zykov travaillèrent sur les graphiques.

Historiquement, la théorie des graphes est née il y a plus de deux cents ans dans le processus de résolution d’énigmes. Pendant très longtemps, elle fut en marge des grandes orientations de la recherche scientifique, au royaume des mathématiques elle fut dans la position de Cendrillon, dont les talents ne se révélèrent pleinement que lorsqu'elle se retrouva au centre de l'attention générale.

Les premiers travaux sur la théorie des graphes, appartenant au célèbre mathématicien suisse L. Euler, parurent en 1736. La théorie des graphes reçut une impulsion de développement au tournant des XIXe et XXe siècles, lorsque le nombre d'ouvrages dans le domaine de la topologie et de la combinatoire , avec lequel il est étroitement lié, la parenté s'est fortement accrue. Les graphiques ont commencé à être utilisés dans la construction de schémas de circuits électriques et de circuits moléculaires. Comme séparé discipline mathématique la théorie des graphes a été introduite pour la première fois dans les travaux du mathématicien hongrois Koenig dans les années 30 du XXe siècle.

Récemment, les graphiques et les méthodes de recherche associées ont imprégné de manière organique presque toutes les mathématiques modernes à différents niveaux. La théorie des graphes est considérée comme l'une des branches de la topologie ; il est également directement lié à l'algèbre et à la théorie des nombres. Les graphiques sont utilisés efficacement dans la théorie de la planification et du contrôle, la théorie de l’ordonnancement, la sociologie, la linguistique mathématique, l’économie, la biologie, la médecine et la géographie. Les graphiques sont largement utilisés dans des domaines tels que la programmation, la théorie des machines à états finis, l'électronique, pour résoudre des problèmes probabilistes et combinatoires, distance la plus courte, etc. Les divertissements mathématiques et les énigmes font également partie de la théorie des graphes. La théorie des graphes se développe rapidement et trouve de nouvelles applications.

Section 2. Types de base, concepts et structure des graphiques.

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.

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

N° Nom du graphique Définition Figure Exemple d'utilisation de ce type de graphique

1 Graphique zéro Sommets du graphique qui n'appartiennent pas Problème : Arkady, Boris. Vladimir, Grigory et Dmitry ont échangé des poignées de main lors de la réunion ; chacun s'est serré la main une fois. Le nombre d’arêtes qu’il y a est appelé isolé. les poignées de main ont été faites ? La situation correspondant au moment où les poignées de main n'ont pas encore été effectuées est le motif de points représenté sur la figure.

Un graphe constitué uniquement de sommets isolés est appelé graphe nul.

Notation : O" – un graphe avec des sommets et sans arêtes

2 Graphiques complets Un graphique dans lequel chaque paire de sommets Notez que si un graphe complet a n sommets, alors le nombre d'arêtes sera Toutes les poignées de main ont été terminées.

Désignation : U" – un graphique composé de n 10.

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

3 Graphiques incomplets Les graphiques dans lesquels toutes les poignées de main ne sont pas encore terminées, les poignées de main A et B, A et D, D et les éventuelles arêtes ont été secouées, sont appelés G, C et D incomplets.

4 Chemin dans le graphique. Faire du vélo. Un chemin dans le graphique d'un sommet à un autre. Au point A, il y a un garage pour un chasse-neige. Le conducteur de la voiture a été appelé pour déneiger les rues de la partie de la ville illustrée sur la photo. Peut-il disposer d'une séquence de bords le long desquels il peut terminer son travail à l'intersection où se trouve le garage, si le conducteur ne peut emprunter qu'une seule fois chaque rue entre ces rues dans son quartier de la ville ?

pics.

Dans ce cas, aucun bord de l'itinéraire ne doit apparaître plus d'une fois. Sommet, de C'est impossible, puisqu'un chemin fermé passant le long de toutes les arêtes du graphe, et le long duquel l'itinéraire est tracé, n'existe pour chaque arête qu'une seule fois, si les degrés de tous les sommets du graphe sont pairs.

le début du chemin, le sommet à la fin du parcours -

fin de la route. Un cycle est un parcours dans lequel la figure montre, à l'aide d'un graphique, un schéma de routes entre des zones peuplées dont le début et la fin coïncident. En points simples.

un cycle est un cycle qui ne passe pas. Par exemple, du point A (le sommet du graphe) au point H peut être atteint par différentes routes : ADGH, AEH, AEFCEH, ABCEH.

il y en a plusieurs à travers l'un des sommets du graphe. En quoi la route AEH diffère-t-elle de la route AEFCEH ?

fois. Parce que sur le deuxième itinéraire, nous avons visité deux fois le « carrefour » au point E.

Cet itinéraire est plus long que AEH. L'itinéraire AEH peut être obtenu à partir de l'itinéraire

Si le cycle comprend toutes les arêtes AEFCEH, « rayer » l'itinéraire FCE du dernier.

graphique une fois à la fois, alors une telle route cyclable AEH est un chemin dans le graphique, mais la route AEFCEH n'est pas un chemin.

appelée la ligne Euler.

Graphiques connectés et déconnectés. Détermination 1 : Est-il possible de réaliser une charpente d'un cube avec une longueur d'arête à partir d'un fil de 12 dm de long

Deux sommets d'un graphe sont-ils dits connectés, 1 dm, sans casser le fil en morceaux ?

s'il y a un chemin dans le graphique qui se termine à ces sommets. Si un tel chemin n’existe pas, on dit que les sommets ne sont pas connectés.

Puisqu'un chemin passant le long de toutes les arêtes du graphe, et le long de chaque arête une seule fois, n'existe que dans les cas suivants :

1) lorsque le degré de chaque sommet est pair (le chemin est fermé)

2) lorsqu’il n’y a que deux sommets de degré impair.

Définition 2 :

Un graphe est dit connecté si une paire de ses sommets est connectée.

Un graphe est dit déconnecté s’il possède au moins une paire de sommets déconnectés.

6 Arbres Un arbre est tout graphe connexe, annexe n°1. Arbre généalogique Zholmurzaeva Tomiris.

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

7 Graphiques isomorphes. Les graphiques présentés dans la figure fournissent les mêmes informations. De tels graphiques sont appelés isomorphes (identiques).

8 Le concept de graphe planaire Un graphe qui peut être représenté sur le Problème. Trois avions vivent dans trois maisons différentes et les voisins se sont disputés. Non loin de leurs maisons, à l'intersection de ses côtes, se trouvent trois puits. Est-il possible de poser à plat sur chacun des puits seulement à partir des sommets, appelés chaque maison. chemin pour qu'aucun d'entre eux ne se croise ?

Solution : Après avoir dessiné huit chemins, vous pouvez vous assurer qu'il n'est pas possible d'en tracer un neuvième qui ne croise aucun des chemins tracés précédemment.

Construisons un graphe dont les sommets

A, B, C, 1, 2, 3

les conditions du problème correspondent aux maisons et aux puits, et nous essaierons de prouver que le neuvième chemin - une arête du graphe qui ne coupe pas les autres arêtes - ne peut pas être tracé.

Les arêtes dessinées dans le graphique de la figure

A1, A2, A3 et B1, B2, VZ (correspondant aux chemins des maisons A et B vers tous les puits).

Le graphe construit divise le plan en trois régions : X, Y, Z. Le sommet B, en fonction de son emplacement sur le plan, appartient à l'une de ces trois régions. Si l'on considère chacun des trois cas de "frapper" le sommet

B à l'une des aires X, Y ou Z, puis assurez-vous qu'à chaque fois un des sommets du graphe est 1, 2 ou 3

(l'un des puits) sera « inaccessible » pour le sommet B (c'est-à-dire qu'il ne sera pas possible de tracer une des arêtes B1, B2 ou B3 qui ne couperait pas les arêtes déjà existantes dans le graphe).

La réponse à la question problématique sera : « Non ! »

Graphes orientés Une arête d'un graphe est appelée arête dirigée si l'un de ses sommets est considéré comme le début et l'autre comme la fin de cette arête.

Un graphe dans lequel toutes les arêtes sont dirigées est appelé graphe orienté.

J'ai donc passé en revue les concepts de base de la théorie des graphes, sans lesquels il serait impossible de prouver des théorèmes et, par conséquent, de résoudre des problèmes.

Conclusion sur le travail effectué :

J'ai appris à structurer tout le matériel d'information dans un tableau ;

La disposition du matériel théorique contribue à une compréhension visuelle des types de graphiques et de leur application ;

J'ai travaillé sur des exemples d'utilisation de la théorie des graphes pour dresser mon arbre généalogique.

Annexe n°1.

ARBRE GÉNÉOLOGIQUE

Construisez un arbre généalogique de Zholmurzaeva Tomiris.

Méthode de résolution.

Manière graphique de résoudre le problème.

Une manière graphique de résoudre le problème consiste à dessiner un « arbre de conditions logiques ». « Arbre » exprime sous la forme d’un simple dessin la relation logique entre parents. Chaque génération sur l'arbre correspond à une branche.

J'ai pris mon arbre généalogique comme exemple.

Section 3. Application de la théorie des graphes.

Nous rencontrons des graphiques plus souvent qu’il n’est possible à première vue. Des exemples de graphiques incluent n'importe quelle feuille de route, schéma électrique, dessin de polygones, etc. Pendant longtemps, on a cru que la théorie des graphes était principalement utilisée pour résoudre des problèmes logiques. Lors de la résolution de problèmes logiques, il est souvent difficile de se souvenir des nombreuses conditions données dans le problème et d'établir des liens entre elles. Les graphiques aident à résoudre de tels problèmes, permettant de représenter visuellement les relations entre les données du problème. La théorie des graphes elle-même était considérée comme faisant partie de la géométrie. Cependant, au XXe siècle, de larges applications de la théorie des graphes ont été trouvées dans l’économie, la biologie, la chimie, l’électronique, la planification de réseaux, la combinatoire et d’autres domaines scientifiques et technologiques. En conséquence, il a commencé à se développer rapidement et s'est transformé en une théorie ramifiée indépendante. La solution de nombreux problèmes mathématiques est simplifiée s'il est possible d'utiliser des graphiques. La présentation des données sous forme de graphique rend les choses plus claires. De nombreuses preuves sont également simplifiées et deviennent plus convaincantes si vous utilisez des graphiques.

3. 1. Application des graphiques dans problèmes géométriques et des théorèmes.

À l’aide de graphiques, vous pouvez facilement établir des chaînes de conséquences logiques qui conduisent à la preuve de l’énoncé. Énoncer brièvement et précisément la preuve du théorème et la solution du problème.

Prouvez que vous avez triangle isocèle les bissectrices tirées des sommets à la base sont égales.

Méthodes de solutions.

Preuve du problème par le raisonnement.

Soit ABC un triangle isocèle de

B1 A1 base AB et bissectrices AA1 et BB1.

Considérons ∆АВВ1 et ∆ВАА1. Ils ont ∟В1АВ=

∟A1BA comme les angles à la base du triangle isocèle ∆ABC. ∟АВВ1= ∟А1АВ

A B puisque AA1 et BB1 sont les bissectrices des angles à la base d'un triangle isocèle. AB est le côté commun. Moyens

∆АВВ1 = ∆ВАВ1 le long du côté et de deux angles adjacents. De l'égalité des triangles il résulte que leurs côtés AA1 et BB1 sont égaux.

Preuve du problème à l'aide d'un graphique.

Prouver : AA=BB

Nous utilisons le graphique pour raisonner. Les sommets du graphe sont les conditions du théorème ou du problème et les étapes de la preuve.

Les bords du graphique sont des conséquences logiques. La fin du diagramme graphique est une déclaration prouvable.

La couleur est utilisée pour mettre en valeur les composants. Le théorème et les conditions du problème sont en bleu. La déclaration à prouver est rouge. Étapes de preuve - noir.

La forme décrite de preuve de théorèmes et de résolution de problèmes est utile et pratique pour les étudiants, car elle permet de mettre en évidence les principales étapes de la preuve des théorèmes et de la résolution du problème.

3. 2. Complexe logiciel et méthodologique.

a) Manuel de l'enseignant.

Le manuel proposé est rédigé conformément au manuel de géométrie pour les classes 7 à 9 de A.V. Pogorelov. Son objectif principal est de fournir au processus d'étude de la géométrie les aides visuelles nécessaires, d'aider l'enseignant dans l'enseignement de la géométrie : de faciliter le processus de preuve des théorèmes, de maîtriser le matériel théorique dans le processus de résolution de problèmes. Les diagrammes graphiques sont de nature multiforme et, selon les objectifs et les formes des cours, peuvent être utilisés de différentes manières : à titre illustratif, visant à améliorer la clarté lors de l'explication de nouveau matériel théorique, lors de la généralisation et de la systématisation de nouveau matériel (diagrammes graphiques avec théorèmes) ; comme cartes utilisées lors de la réalisation d'enquêtes individuelles et frontales (schémas graphiques avec tâches). Ce manuel est accompagné de classeur pour les étudiants. Un classeur peut être utilisé pour organiser travail indépendantélèves pendant et après les heures de cours.

b) Cahier d'exercices pour les étudiants.

Le manuel est réalisé sous la forme d'un cahier d'exercices. Le manuel comprend 28 diagrammes graphiques avec des théorèmes et 28 diagrammes graphiques avec des tâches. Les diagrammes graphiques contiennent le matériel principal du programme, qui est présenté avec la clarté nécessaire et représente le cadre de la solution. Les élèves remplissent séquentiellement les cellules vides avec les informations qui constituent la solution au problème.

La couleur est utilisée pour mettre en valeur les composants. Les conditions du théorème et du problème sont en bleu, l'énoncé à prouver est en rouge, les étapes de la preuve sont en noir.

Le manuel est utile aux élèves de la 7e à la 9e année.

c) Manuel électronique.

Résultats des travaux et de leur discussion. Le projet est le résultat d'une étude de deux ans sur l'utilisation de graphiques dans un cours de mathématiques à l'école.

Création par programmation – complexe méthodologique et sa mise en œuvre a été réalisée au cours de :

Animation de cours pour le club Aristote sur le thème « Résoudre des problèmes logiques à l'aide de graphiques ».

Applications des graphiques dans les preuves de théorèmes et de problèmes géométriques

Dans les cours de géométrie en 8e et 9e années.

Présentations avec un projet à l'école scientifique et pratique conférences.

CONCLUSION.

En résumant les résultats de l'étude de l'utilisation des graphiques dans un cours de géométrie scolaire, je suis arrivé à la conclusion suivante :

1. L'avantage de la preuve graphique des théorèmes et de la résolution de problèmes par rapport à la preuve traditionnelle est l'illustration de la dynamique de la preuve des théorèmes et des problèmes.

2. L’introduction au processus de preuve de théorèmes géométriques et de problèmes de la méthode des schémas graphiques aide à renforcer les compétences des étudiants dans la construction d’une preuve.

3. Développement d'un logiciel et d'un complexe méthodologique pour l'étude de la géométrie de la 7e à la 9e année : a) manuel de l'enseignant ; b) cahier d'exercices pour les étudiants ; c) le manuel électronique est utile pour les élèves de la 7e à la 9e année.

Envoyer votre bon travail dans la base de connaissances est simple. Utilisez le formulaire ci-dessous

Les étudiants, étudiants diplômés, jeunes scientifiques qui utilisent la base de connaissances dans leurs études et leur travail vous seront très reconnaissants.

Documents similaires

Restauration de graphiques à partir de matrices de contiguïté de sommets données. Construction pour chaque graphe d'une matrice de contiguïté des bords, d'incidence, d'accessibilité, de contre-accessibilité. Trouver la composition des graphiques. Détermination des degrés locaux des sommets du graphe. Recherche d'une base de données de graphiques.

travaux de laboratoire, ajouté le 01/09/2009


Théorie des graphes en tant que branche des mathématiques discrètes qui étudie les propriétés d'ensembles finis avec des relations données entre leurs éléments. Concepts de base de la théorie des graphes. Matrices de contiguïté et d’incidence et leurs utilisation pratique lors de l’analyse des solutions.

résumé, ajouté le 13/06/2011


Concepts de base de la théorie des graphes. Diplôme supérieur. Itinéraires, chaînes, cycles. Connectivité et propriétés des graphes orientés et planaires, algorithme pour leur reconnaissance, isomorphisme. Opérations sur eux. Revue des méthodes de spécification des graphiques. Cycles d'Euler et d'Hamiltonien.

présentation, ajouté le 19/11/2013


Description d'un graphe donné par ensembles de sommets V et d'arcs X, listes de contiguïté, matrice d'incidence et de contiguïté. La matrice de poids du graphe non orienté correspondant. Détermination de l'arbre des chemins les plus courts à l'aide de l'algorithme de Dijkstra. Trouver des arbres sur un graphique.

travail de cours, ajouté le 30/09/2014


Concepts de base de la théorie des graphes. Distances en graphiques, diamètre, rayon et centre. Application des graphiques aux activités humaines pratiques. Détermination des itinéraires les plus courts. Graphiques d'Euler et d'Hamiltonien. Éléments de théorie des graphes dans les cours au choix.

thèse, ajoutée le 19/07/2011


Concept et représentation matricielle des graphiques. Graphiques orientés et non orientés. Définition de la matrice d'adjacence. Itinéraires, chaînes, cycles et leurs propriétés. Caractéristiques métriques du graphique. Application de la théorie des graphes à divers domaines scientifiques et technologiques.

travail de cours, ajouté le 21/02/2009


Description mathématique du système contrôle automatiqueà l'aide de graphiques. Établir un graphique et le transformer, en éliminant les différentiels. Optimisation de graphes orientés et non orientés, compilation de matrices de contiguïté et d'incidence.

travaux de laboratoire, ajouté le 11/03/2012

Le texte de l'ouvrage est affiché sans images ni formules.
Version complète le travail est disponible dans l'onglet "Fichiers de travail" au format PDF

Introduction

Notre monde regorge non seulement de lettres et de chiffres, mais aussi d’une grande variété d’images. Il s'agit notamment de peintures, de toutes sortes de photographies, ainsi que de nombreux diagrammes. Les schémas se trouvent sur les logos d'entreprise et de voiture, panneaux routiers et des cartes. Si vous regardez le plan du métro ou ligne de bus, ce ne sont que des lignes avec des points. De tels modèles de lignes (arêtes) et de points (sommets) sont appelés graphiques.

La théorie des graphes est née grâce à un problème intéressant résolu par Leonhard Euler. L'histoire raconte qu'en 1736 ce brillant mathématicien s'arrêta à Königsberg. La ville était divisée par le fleuve en 4 parties, reliées par sept ponts. Il fallait déterminer s’il était possible de contourner tous les ponts en traversant chacun d’eux exactement une fois. Euler a déterminé qu'il était impossible de résoudre le problème. Les ponts de Königsberg ont été détruits pendant la Seconde Guerre mondiale, mais cette histoire a donné naissance à une belle théorie mathématique : la théorie des graphes.

Au XXe siècle, la théorie des graphes a connu un développement incroyable ; elle a trouvé de nombreuses applications dans des problèmes de planification, d'architecture, d'ingénierie, et surtout en informatique et en télécommunications. Les graphiques sont liés à la combinatoire, aux mathématiques discrètes, à la topologie, à la théorie des algorithmes et à d'autres branches des mathématiques.

Quelles opportunités un étudiant qui maîtrise cette théorie a-t-il ? Sera-t-il capable de réussir ses études ou vie ordinaire? Ce projet est dédié à une telle recherche.

Objectif du projet : Montrer que les méthodes de la théorie des graphes donnent aux écoliers un outil qui leur permet de résoudre des problèmes complexes de l'Olympiade et, dans la vie, d'organiser le transfert d'informations urgentes entre les personnes.

Hypothèses:

À l'aide de graphiques, vous pouvez facilement résoudre de nombreux problèmes de l'Olympiade

La théorie des graphes aide à créer un système de notification d'équipe urgente

Tâches:

Comprendre les méthodes de résolution de problèmes à l'aide de graphiques

Développer un site Web pour tester problèmes aux Olympiades

Concevoir un système de notification de classe urgente à l'aide d'un graphique

Objets d'étude : Tâches de l'Olympiade, systèmes d'alerte

Sujet d'étude: théorie des graphes, programmation web.

Méthodes de recherche:

méthodes de la théorie des graphes

méthodes de programmation Web

Plan de recherche:

Découvrez l'histoire de la théorie des graphes

Apprenez les règles pour résoudre les problèmes de l'Olympiade à l'aide de graphiques

Suivre le cours de programmation Web de l'école Technologies de l'information"REAL-IT"

Développer un site Web pour tester les problèmes de l'Olympiade en théorie des graphes et le tester sur des amis

Concevoir un système d'alerte de classe urgente (UCA)

Mener une expérience pour tester le système RNS

Chapitre 1. La théorie des graphes dans nos vies

1.1. Application de la théorie des graphes dans différentes régions

Les graphiques sont utilisés dans divers domaines : lors de la conception de circuits électriques, de réseaux téléphoniques, lors de la recherche d'itinéraires entre des zones peuplées, en économie.

En chimie, les graphiques sont utilisés pour représenter différents composés. À l'aide de graphiques, vous pouvez le représenter comme molécules simples, et des composés organiques assez complexes.

La théorie des graphes joue un rôle clé à différentes étapes des projets architecturaux. Une fois les parties du projet identifiées, et avant de passer des croquis aux dessins, il est utile de construire un graphique des relations entre les éléments du projet. L'analyse des graphiques dans les bâtiments publics permettra de déterminer le degré d'accessibilité des différents services, la localisation des locaux (buffet, bibliothèque, etc.), ainsi que les issues de secours. Les graphiques peuvent simplifier considérablement l’analyse situations difficiles.

Aujourd’hui, grâce à Internet, un « réseau de réseaux » reliant les ordinateurs du monde entier, la révolution numérique est devenue possible. La puissance des ordinateurs n’a cessé de croître, mais c’est grâce aux réseaux que le grand pas vers le monde numérique a été possible. Les graphiques et les télécommunications ont toujours fait bon ménage.

La figure 1.1 montre différents schémas permettant de connecter des ordinateurs entre eux. Le plus souvent, il existe trois manières de connecter des ordinateurs à un réseau local : « bus commun », « étoile » et « anneau ». Chaque circuit possède un graphique correspondant, c'est pourquoi le terme « topologie de réseau » est utilisé. La topologie du réseau est la configuration d'un graphe dont les sommets sont des ordinateurs et des routeurs, et les bords sont des lignes de communication (câble) entre eux. Dans la figure 1.2, toutes les topologies sont représentées sous forme de graphiques.

Un arbre est un graphe très simple dans lequel il n’y a qu’un seul chemin entre deux sommets quelconques. Les arbres sont utilisés en génétique pour illustrer les relations familiales (arbres généalogiques) et pour analyser les probabilités de divers événements.

Graphique 1.1. Options pour créer des réseaux informatiques locaux

Graphique 1.2. Options pour créer des réseaux informatiques locaux

a - bus commun, b - étoile, c - anneau

Il existe de nombreux jeux dans lesquels vous devez créer un certain graphique (jeux de labyrinthe) ou utiliser le graphique pour déterminer s'il existe une stratégie gagnante.

Le GPS, les cartes et les itinéraires présentés sur Internet sont un autre excellent exemple d’utilisation de graphiques. Les bords en eux sont des rues et des routes, et les sommets sont colonies. Les sommets de ces graphiques ont des noms et les arêtes correspondent à des nombres indiquant la distance en kilomètres. Ainsi, un tel graphique est étiqueté et pondéré. Les graphiques vous aident à visualiser les schémas de transports publics, ce qui facilite la planification de votre déplacement.

Les graphiques sont également utilisés dans l’industrie pétrolière et gazière dans les systèmes de transport pétrolier et gazier. En utilisant des méthodes d'analyse graphique des systèmes de transport de gaz, il est possible de sélectionner l'option la plus courte parmi tous les itinéraires possibles contournant le gazoduc.

Le développement de l'informatique a conduit à ce que de nombreux modèles mathématiques a commencé à être utilisé dans les processus automatiques. Une machine peut facilement effectuer des calculs, mais choisir la meilleure option parmi un ensemble dans des conditions d’incertitude est une tâche beaucoup plus difficile. De nouveaux algorithmes sont apparus qui utilisent des mécanismes rappelant la révolution biologique. Ils utilisent des graphiques pour visualiser les processus. La modélisation des neurones du cerveau humain et du principe de leur fonctionnement constitue la base nouvelle théorie- théorie des réseaux de neurones.

1.2. Conclusions sur le chapitre.

La théorie des graphes a trouvé son application dans de nombreux domaines de la science, de la technologie et de la vie quotidienne. Cependant, malgré sa large application dans divers domaines, seule une attention superficielle lui est accordée dans les cours de mathématiques à l'école. Dans le même temps, diverses expériences dans le domaine de l'éducation montrent que les éléments de la théorie des graphes ont une grande valeur pédagogique et devraient donc être inclus dans le programme scolaire.

En effet, il sera très utile aux collégiens d'étudier les bases de la théorie des graphes, puisqu'ils les aideront à maîtriser le cours de base de mathématiques, et notamment à résoudre les problèmes olympiques de théorie combinatoire et probabiliste.

Chapitre 2. La théorie des graphes pour aider les écoliers

2.1. Théorie des graphes dans les problèmes des Olympiades

Diverses Olympiades mathématiques, telles que « Kangourou », « Dino-Olympiad Uchi.ru », Olympiade heuristique internationale « Owl », incluent également souvent des problèmes sur la théorie des graphes dans différentes formulations.

Comme vous le savez, les enfants sont très friands de tout ce qui touche aux ordinateurs et à Internet, et il n'est pas si facile de les asseoir à table avec un livre de mathématiques. Afin de susciter l'intérêt des écoliers pour la théorie des graphes, les auteurs de l'article, sur la base des cours suivis en programmation Web à la REAL-IT School of Information Technologies, ont développé un simulateur en ligne, comprenant des tests en théorie des graphes, situé sur la page de l'école privée de Tioumen "Evolventa" " : évoluenta-tmn.github.io. Les écoliers sont invités à résoudre six problèmes de différents niveaux de difficulté, il inscrit les réponses dans les cases, puis en cliquant sur le bouton « Terminé », le résultat est donné : le nombre de problèmes qu'il a résolus correctement (Figure 2.1).

Graphique 2.1. Fragment de l'écran du site avec options de test

Naturellement, un enfant rusé commencera immédiatement à chercher des réponses sur les serveurs de recherche, mais il ne trouvera pas exactement les mêmes formulations, seulement des similaires, par exemple sur le site de la revue électronique scientifique et méthodologique « Concept ». Ainsi, pour obtenir le résultat souhaité : 6 tâches sur 6 que l'étudiant devra comprendre principes généraux résoudre des problèmes en utilisant la théorie des graphes. Et à l'avenir, les connaissances acquises l'aideront à résoudre avec succès les problèmes scolaires et olympiques.

Lorsque le site a été complètement prêt, testé et publié sur Internet, nos camarades de classe ont reçu un lien vers celui-ci. Le site a suscité un grand intérêt : à en juger par le compteur de visites, il a été visité plus de 150 fois la première semaine ! Beaucoup de gars ont essayé de résoudre les problèmes, mais ils ont trouvé cela difficile. Même certains parents ayant fait des études supérieures éducation technique, un certain nombre de problèmes ont déconcerté, ce qui suggère que la théorie des graphes n'est même pas étudiée dans tous les établissements d'enseignement supérieur. les établissements d'enseignement. Cela signifie que les tests que nous avons préparés seront utiles non seulement aux écoliers, mais aussi aux adultes !

2.2. Théorie des graphes dans la conception d'un système d'alarme pour salle de classe

Actuellement, le domaine des systèmes de gestion du personnel d'urgence dans les organisations se concentre sur grande attention, du fait que de tels systèmes jouent un rôle important dans l'organisation de toutes les activités des salariés.

Initialement, les systèmes d'alerte et de contrôle d'évacuation ont été conçus pour informer en urgence les travailleurs, le personnel et les invités d'un incendie dans un bâtiment, en fournissant et en diffusant des informations importantes pour une évacuation rapide et réussie des personnes. Aujourd'hui, de tels systèmes peuvent être observés non seulement au sein d'une organisation ou d'une entreprise, mais dans tout notre pays, utilisés pour améliorer la sécurité des personnes.

Il convient de noter que la plupart des systèmes d'alerte utilisés s'adressent aux adultes. Mais l’âge le plus dangereux est l’enfance. Les enfants ont également besoin de leurs propres systèmes qui leur permettent d'informer rapidement la plupart de leurs pairs d'un danger imminent ou d'un changement de situation.

Chaque enfant passe une partie importante de son temps à l'école : cinq à six jours par semaine à raison de plusieurs heures. Par conséquent, la création d'un système d'alerte pour les enfants permettrait d'organiser chaque enfant pour qu'il réagisse rapidement et avec compétence à une situation modifiée.

Par exemple, ce système serait très utile pour transmettre un message de danger, une information sur un rassemblement urgent ou un changement de situation lorsqu'ils se trouvent dans différentes parties de l'école ou même en forêt en vacances (Figure 2.2).

Graphique 2.2. Notre classe en excursion à l'Institution autonome d'État "Centre régional de formation préalable à la conscription et d'éducation patriotique "Avanpost"

Dans ce travail, une tentative est faite pour créer un système de notification collective en utilisant l'exemple d'une classe établissement d'enseignement: Lycée MAOU n°89.

Étant donné que les enfants doivent diffuser eux-mêmes des informations, ils ne doivent utiliser que tous les types de communication à leur disposition : les communications mobiles. L'ensemble de la classe doit être notifié, donc pour analyser quels enfants étaient prêts à notifier lesquels de leurs amis, une enquête de classe a été réalisée. Les questionnaires fixaient dans un premier temps une limite : chaque enfant a le temps d'appeler au maximum quatre amis, et s'il reste du temps, deux de plus.

L'enquête a montré une activité assez élevée des enfants : au total, environ 118 appels seront effectués dans la classe. Il est presque impossible d’analyser mentalement un tel volume d’informations. Il a donc été décidé d’utiliser les technologies de l’information. Le modèle de notification d'équipe est mieux représenté sous forme de graphique. Les bords sont des appels (ou SMS) et les sommets sont des enfants. Étant donné que les sommets du graphique ont des noms et que les arêtes correspondent à des nombres indiquant la probabilité d'un appel (1 ou 0,5), un tel graphique est étiqueté et pondéré. Le graphique permet de visualiser le schéma de notification de l'équipe, ce qui facilite la modélisation.

Il a été décidé de visualiser le graphique à l'aide de l'outil RAMUS CASE, car il vous permet de travailler avec la couleur des sommets et des arêtes, et vous permet également de déplacer les sommets du graphique auxquels sont attachées les arêtes pour plus de clarté. La figure 2.3 montre le graphique du système RNS.

Le 19 novembre 2017, le système SOC conçu a été testé. Initialement, nous avions prévu que l'annonce se fasse sur trois tours. Pour le premier cercle (début de notification), nous avons choisi deux enfants que personne ne veut appeler, mais qui sont prêts à appeler, ainsi que les auteurs du Projet eux-mêmes (Fig. 2.3, blocs roses). Ensuite, l'information est transmise au deuxième cercle d'avertissement (Fig. 2.4, blocs jaunes). Et sur le troisième cercle de notification (Fig. 2.4, blocs verts), toute la classe sera informée. Mais au cours de l'expérience, nous avons vu que certains enfants passent 1,5 à 2 heures en formation et ne regardent pas le téléphone, d'autres ont un solde négatif et ne peuvent donc pas passer d'appels.

Graphique 2.3. Graphique du système d'alerte de classe

Graphique 2.4. Cercles d'alerte du système SOK

Par conséquent, en réalité, notre classe n’a été prévenue que 490 minutes à l’avance, soit 8 heures 10 minutes. Mais c'était à 100%. L’important ici est que notre système a la structure non pas d’un arbre, mais d’un graphe. Et dans celui-ci, plusieurs chemins mènent d'un sommet à l'autre, donc dans tous les cas, tout le monde sera prévenu !

La figure 2.6 montre un graphique de notification de classe (nombre de personnes notifiées) en fonction du temps (en minutes).

Graphique 2.6. Calendrier des notifications de cours

Pour faciliter le contrôle de la vigilance, pendant le processus de test, les enfants devaient indiquer aux auteurs du projet leur sujet préféré, et ils tenaient un protocole indiquant quand et qui rapportait l'information.

Un autre résultat de test - une enquête sur les matières préférées (Figure 2.7) a montré que les enfants de notre classe aiment avant tout les mathématiques, l'informatique et les jeux de plein air ! Cela signifie qu’ils aiment peut-être la théorie des graphes autant que nous.

Graphique 2.7. Diagramme circulaire des éléments de classe préférés

2.3. Conclusions sur le chapitre.

Nous avons testé les deux hypothèses. Le site Web que nous avons développé pour tester les problèmes de l'Olympiade en théorie des graphes a permis d'établir qu'un certain nombre de problèmes de l'Olympiade sont tout simplement impossibles à résoudre sans connaissance de la théorie des graphes, même pour les ingénieurs adultes. La première hypothèse a été confirmée.

La deuxième hypothèse s’est également avérée correcte. Le système de notification d'équipe conçu et testé à partir de l'exemple d'une classe a permis de prévenir toute une équipe d'enfants en 8 heures et 10 minutes. En optimisant le graphique, vous pouvez obtenir des résultats plus rapides.

Conclusion.

Nous espérons qu'après s'être familiarisés avec la théorie des graphes et ses nombreuses applications dans divers domaines, les écoliers s'intéresseront à la théorie des graphes et continueront à étudier cette branche des mathématiques par eux-mêmes. Le résultat de l'étude sera de meilleurs résultats aux Olympiades.

Concernant l'application de la théorie des graphes dans vrai vie, la pertinence du sujet à l'étude souligne le fait que la création d'un système d'alerte pour les enfants augmentera la vitesse de transmission des informations urgentes, couvrira une grande partie de l'équipe d'enfants pour laquelle ce système sera utilisé, réduira le temps de réponse des enfants, tout en assurant une sécurité maximale à l'équipe des enfants. Tout cela souligne les avantages évidents de la mise en œuvre du système conçu.

Bibliographie

Beloborodova A.A. Développement de la pensée spatiale à l'aide de jeux de labyrinthe / A.A. Beloborodova // « Forum scientifique des étudiants » : documents du VIIIe International Student Electronic conférence scientifique.- 2017. https://www.site/2017/7/26746

Beloborodova, A.A. Développement d'un web-simulateur pour étudier la théorie des graphes / A.A. Beloborodova, S.V. Pakhotin, A.A. Frolov // Nouvelles technologies de l'information dans l'industrie pétrolière et gazière et dans l'éducation : documents de la VIIe Conférence scientifique et technique internationale ; resp. éd. IL. Kuzyakov. - Tioumen : TIU, 2017. - pp. 156-159.

Beloborodova A.A. On ne peut pas se perdre en mathématiques ! / AA Beloborodova // XVIIIe Concours panrusse de recherche scientifique pour enfants. Et œuvres créatives"Premiers pas dans la science" : collection de résumés. - M. : Intégration NS, Douma d'État de l'Assemblée fédérale de la Fédération de Russie, Ministère de l'Éducation et des Sciences de Russie. - 2016. - P. 110-111.

Gendenstein, L.E. Alice au pays des mathématiques. Conte de fées / Pour les plus jeunes. et mercredi âge scolaire.- Kharkov : Maison d'édition - commerce. entreprise "Paritet" LTD, 1994.-288 p., ill.

Davletshin, M.I. Étude de l'efficacité des méthodes de suppression du bruit d'image / M. I. Davletshin, K. V. Syzrantseva // Économie d'énergie et technologies innovantes dans le complexe combustible et énergétique : matériaux d'Int. scientifique-pratique conf. étudiants, étudiants diplômés, jeunes scientifiques et spécialistes. T.1 / resp. éditeur A.N. Khaline. - Tioumen : TIU, 2016. - pp. 25-29.

Karnaukhova, A.A. Utiliser la théorie des graphes pour résoudre des problèmes en économie / A.A. Karnaukhova, A.F. Dolgopolova // Documents de la VIIe Conférence scientifique électronique internationale des étudiants « Forum scientifique des étudiants ». http://www.scienceforum.ru/2015/991.

Kern, G. Labyrinthes du monde. Saint-Pétersbourg : Maison d'édition « Azbuka-classics », 2007, 448 p.

Krause, M.V. Application des technologies de l'information à la conception d'un système d'alerte d'équipe / M.V. Krause, A.A. Beloborodova, E.I. Arbuzova // Nouvelles technologies de l'information dans l'industrie pétrolière et gazière et dans l'éducation : documents de la VIIe Conférence scientifique et technique internationale ; resp. éd. IL. Kuzyakov. - Tioumen : TIU, 2017. - pp. 153-156.

Cours « Création de sites Web » de l'École des technologies de l'information « REAL-IT » http://it-schools.org/faculties/web/

Le monde des mathématiques : en 40 volumes T.11 : Claudi Alsina. Plans de métro et réseaux de terrons. Théorie des graphes./Trans. de l'espagnol - M. : De Agostini, 2014. - 144 p.

Moskevich L.V. Olympiade éducative - une des formes de cours de mathématiques parascolaires / L.V. Moskevich // Revue électronique scientifique et méthodologique « Concept ». - 2015. - T. 6. - P. 166-170. -URL : http://e-koncept.ru/2015/65234.htm.

Mémo à la population "Avertir la population en cas de menace et d'urgence" http://47.mchs.gov.ru/document/1306125

Roumyantsev, V.O. Modélisation mathématique du système de transport de gaz à l'aide de la théorie des graphes / V. O. Rumyantsev // Problèmes de géologie et d'aménagement du sous-sol : collection. scientifique tr. /TPU. - Tomsk, 2017. - P. 340 - 342.

Site Web du ministère des Situations d'urgence de la Fédération de Russie http://www.mchs.gov.ru/dop/Kompleksnaja_sistema_jekstrennogo_opoves