Breite Anwendung der Graphentheorie in der Informatik. Die Verwendung von Graphen in verschiedenen Bereichen des Lebens von Menschen

STÄDTISCHE AUTONOME ALLGEMEINE BILDUNGSEINRICHTUNG SEKUNDÄRE BILDUNGSSCHULE № 2

Bereit

Legkokonets Vladislav, 10A Student

Praktische Anwendung der Graphentheorie

Aufsicht

LI Noskova, Mathematiklehrerin

st.Bryukhovetskaya

2011

1.Einführung………………………………………………………………………….………….3

2. Die Entstehungsgeschichte der Graphentheorie………………………………………….………..4

3.Grundlegende Definitionen und Theoreme der Graphentheorie……………………………….………6

4. Aufgaben gelöst mit Hilfe von Grafiken……………………………..……………………..8

4.1 Berühmte Aufgaben………………………………….………………………...8

4.2 Einige interessante Aufgaben………………………………….……………..9

5. Anwendung von Graphen in verschiedenen Lebensbereichen……………………………...11

6. Problemlösung……………………………………………………………………………...12

7. Fazit ………………….……………………………………………………………….13

8. Literaturverzeichnis ………….………………………………………………………………………………………………………… ……………………………………………………………………………………………………………………………………… ……………………………………………………………………………………………………………………….

9. Anhang…………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………

Einführung

Die Graphentheorie, die aus dem Lösen von Rätseln und unterhaltsamen Spielen stammt, ist heute zu einem einfachen, zugänglichen und leistungsstarken Werkzeug zum Lösen von Problemen im Zusammenhang mit einer Vielzahl von Problemen geworden. Diagramme sind buchstäblich allgegenwärtig. In Form von Grafiken können Sie beispielsweise Straßenkarten und Stromkreise interpretieren, geografische Karten und Moleküle Chemische Komponenten, Verbindungen zwischen Menschen und Personengruppen. In den letzten vier Jahrzehnten hat sich die Graphentheorie zu einem der sich am schnellsten entwickelnden Zweige der Mathematik entwickelt. Dies wird durch die Anforderungen eines schnell wachsenden Anwendungsbereichs getrieben. Es wird beim Entwurf integrierter Schaltungen und Steuerschaltungen, beim Studium von Automaten, logischen Schaltungen, Programmflussdiagrammen, in Wirtschaft und Statistik, Chemie und Biologie, in der Planungstheorie verwendet. Deshalb Relevanz Das Thema ist einerseits der Popularität von Graphen und verwandten Forschungsmethoden geschuldet, andererseits einem unentwickelten, integralen System zu ihrer Umsetzung.

Die Lösung vieler Lebensprobleme erfordert lange Berechnungen, und manchmal bringen diese Berechnungen keinen Erfolg. Darin besteht es Forschungsproblem. Es stellt sich die Frage: Ist es möglich, eine einfache, rationale, kurze und elegante Lösung für ihre Lösung zu finden? Ist es einfacher, Probleme zu lösen, wenn Sie Diagramme verwenden? Es bestimmt Thema meiner Forschung: "Praktische Anwendung der Graphentheorie"

Ziel Die Forschung bestand darin, mithilfe von Grafiken zu lernen, wie praktische Probleme schnell gelöst werden können.

Forschungshypothese. Die Graphenmethode ist sehr wichtig und wird in verschiedenen Bereichen der Wissenschaft und des menschlichen Lebens häufig verwendet.

Forschungsschwerpunkte:

1. Studium der Literatur und Internetquellen zu diesem Thema.

2. Überprüfen Sie die Wirksamkeit der Graphenmethode bei der Lösung praktischer Probleme.

3. Machen Sie eine Schlussfolgerung.

Praktische Bedeutung Forschung ist, dass die Ergebnisse zweifellos das Interesse vieler Menschen wecken werden. Hat keiner von Ihnen versucht, einen Stammbaum Ihrer Familie zu erstellen? Und wie macht man es richtig? Der Leiter eines Transportunternehmens muss wahrscheinlich das Problem einer rentableren Nutzung des Transports beim Transport von Waren von einem Zielort zu mehreren Siedlungen lösen. Jeder Schüler stand vor logischen Transfusionsaufgaben. Es stellt sich heraus, dass sie mit Hilfe von Graphen leicht gelöst werden können.

In der Arbeit kommen folgende Methoden zum Einsatz: Beobachtung, Suche, Auswahl, Analyse.

Die Entstehungsgeschichte der Graphentheorie

Der Mathematiker Leonhard Euler (1707-1783) gilt als Begründer der Graphentheorie. Die Entstehungsgeschichte dieser Theorie lässt sich anhand der Korrespondenz des großen Wissenschaftlers nachvollziehen. Hier ist eine Übersetzung des lateinischen Textes, der Eulers Brief an den italienischen Mathematiker und Ingenieur Marinoni entnommen ist, der am 13. März 1736 aus St. Petersburg geschickt wurde.

„Einmal wurde mir ein Problem über eine Insel in der Stadt Königsberg gegeben, die von einem Fluss umgeben ist, über den sieben Brücken geworfen werden.

[Anhang Abb.1] Die Frage ist, ob jemand sie kontinuierlich umgehen und jede Brücke nur einmal passieren kann. Und dann wurde mir gesagt, dass dies noch niemand geschafft habe, aber niemand habe bewiesen, dass es unmöglich sei. Diese Frage, obwohl banal, schien mir jedoch bemerkenswert die Tatsache, dass weder Geometrie noch Algebra noch kombinatorische Kunst zu ihrer Lösung ausreichen. Nach langem Nachdenken habe ich auf der Grundlage eines völlig überzeugenden Beweises eine einfache Regel gefunden, mit deren Hilfe man bei allen Aufgaben dieser Art sofort feststellen kann, ob eine solche Runde durch beliebig viele und beliebig angeordnete Brücken gemacht werden kann oder nicht. Die Königsberger Brücken sind so angeordnet, dass sie in der folgenden Abbildung dargestellt werden können [Anhang Abb.2], wobei A eine Insel bezeichnet und B , C und D Teile des Kontinents sind, die durch Flussarme voneinander getrennt sind

Über die von ihm entdeckte Methode zur Lösung solcher Probleme schrieb Euler:

„Diese Lösung scheint ihrer Natur nach wenig mit Mathematik zu tun zu haben, und ich verstehe nicht, warum diese Lösung eher von einem Mathematiker als von irgendeiner anderen Person erwartet werden sollte, denn diese Lösung wird allein durch die Vernunft gestützt, und die gibt es Um diese Lösung zu finden, müssen keine der Mathematik innewohnenden Gesetze einbezogen werden. Daher weiß ich nicht, wie sich herausstellt, dass Fragen, die sehr wenig mit Mathematik zu tun haben, eher von Mathematikern als von anderen gelöst werden. "

Ist es also möglich, die Königsberger Brücken zu umgehen, indem man jede dieser Brücken nur einmal passiert? Um die Antwort zu finden, setzen wir Eulers Brief an Marinoni fort:

„Die Frage ist, ob es möglich ist, alle diese sieben Brücken zu umgehen und jede nur einmal zu passieren, oder nicht. Meine Regel führt zu folgender Lösung dieser Frage. Zunächst müssen Sie sich ansehen, wie viele Abschnitte sind durch Wasser getrennt - solche , die keinen anderen Übergang von einem zum anderen haben, außer durch die Brücke. In diesem Beispiel gibt es vier solcher Abschnitte - A, B, C, D. Als nächstes müssen Sie unterscheiden, ob die Anzahl von Brücken, die zu diesen einzelnen Abschnitten führen, ist gerade oder ungerade, also in unserem Fall führen fünf Brücken zu Abschnitt A und drei Brücken zu den restlichen, dh Die Anzahl der Brücken, die zu einzelnen Abschnitten führen, ist ungerade, und diese eine reicht bereits dazu das Problem lösen. Wenn dies festgestellt ist, wenden wir die folgende Regel an: Wenn die Anzahl der Brücken, die zu jedem einzelnen Abschnitt führen, gerade wäre, dann die Umgehung, um welche fraglich, wäre möglich, und gleichzeitig wäre es möglich, diese Umleitung von jedem beliebigen Abschnitt aus zu starten. Wenn aber zwei dieser Nummern ungerade wären, denn nur eine kann nicht ungerade sein, dann könnte auch dann der Übergang wie vorgeschrieben erfolgen, aber nur der Beginn der Umgehungsstraße muss notwendigerweise von einem der beiden Abschnitte genommen werden, zu denen die ungerade Anzahl führt Brücken. Wenn es schließlich mehr als zwei Abschnitte gäbe, zu denen eine ungerade Anzahl von Brücken führt, dann ist eine solche Bewegung im Allgemeinen unmöglich ... wenn andere, schwerwiegendere Probleme hier angeführt werden könnten, könnte diese Methode noch nützlicher sein und sollte es nicht vernachlässigt werden“.

Grundlegende Definitionen und Theoreme der Graphentheorie

Die Graphentheorie ist eine mathematische Disziplin, die durch die Bemühungen von Mathematikern geschaffen wurde, daher enthält ihre Präsentation die notwendigen strengen Definitionen. Fahren wir also mit der organisierten Einführung der Grundkonzepte dieser Theorie fort.

Bestimmung 1. Ein Graph ist eine Sammlung endliche Zahl Punkte, die Scheitelpunkte des Graphen genannt werden, und paarweises Verbinden einiger dieser Scheitelpunkte von Linien, die Kanten oder Bögen des Graphen genannt werden.

Diese Definition kann anders formuliert werden: Ein Graph ist eine nicht leere Menge von Punkten (Knoten) und Segmenten (Kanten), deren beide Enden zu einer gegebenen Menge von Punkten gehören

In Zukunft werden wir die Eckpunkte des Graphen mit den lateinischen Buchstaben A, B, C, D bezeichnen. Manchmal wird der Graph als Ganzes mit Eins bezeichnet Großbuchstabe.

Bestimmung 2. Die Ecken des Graphen, die zu keiner Kante gehören, heißen isoliert.

Bestimmung 3. Ein Graph, der nur aus isolierten Knoten besteht, heißt Null - Anzahl .

Notation: O "– ein Graph mit Ecken und ohne Kanten

Bestimmung 4. Ein Graph, in dem jedes Knotenpaar durch eine Kante verbunden ist, heißt vollständig.

Bezeichnung: U" – ein Graph, der aus n Scheitelpunkten und Kanten besteht, die alle möglichen Paare dieser Scheitelpunkte verbinden. Ein solcher Graph kann als n-Eck dargestellt werden, in dem alle Diagonalen eingezeichnet sind

Bestimmung 5. Der Grad eines Knotens ist die Anzahl der Kanten, zu denen der Knoten gehört.

Bestimmung 6. Ein Graph, dessen Grad aller k Knoten gleich sind, heißt homogener Graph vom Grad k .

Bestimmung 7. Das Komplement eines gegebenen Graphen ist ein Graph, der aus allen Kanten und ihren Enden besteht, die zu dem ursprünglichen Graphen hinzugefügt werden müssen, um einen vollständigen Graphen zu erhalten.

Bestimmung 8. Ein Graph, der in einer Ebene so dargestellt werden kann, dass sich seine Kanten nur an den Ecken schneiden, heißt planar.

Bestimmung 9. Ein Polygon eines planaren Graphen, das keine Ecken oder Kanten des Graphen enthält, wird als Fläche bezeichnet.

Die Konzepte eines ebenen Graphen und Graphflächen werden verwendet, um Probleme für die "korrekte" Färbung verschiedener Karten zu lösen.

Bestimmung 10. Ein Pfad von A nach X ist eine Folge von Kanten, die von A nach X führen, sodass jeweils zwei benachbarte Kanten einen gemeinsamen Scheitelpunkt haben und keine Kante mehr als einmal vorkommt.

Bestimmung 11. Ein Zyklus ist ein Pfad, bei dem Anfangs- und Endpunkt gleich sind.

Bestimmung 12. Ein einfacher Zyklus ist ein Zyklus, der keinen der Scheitelpunkte des Graphen mehr als einmal durchläuft.

Bestimmung 13. langer Weg , auf eine Schlaufe gelegt , ist die Anzahl der Kanten dieses Pfades.

Bestimmung 14. Zwei Knoten A und B in einem Graphen heißen verbunden (nicht verbunden), wenn es (nicht existiert) einen Pfad gibt, der von A nach B führt.

Bestimmung 15. Ein Graph heißt zusammenhängend, wenn alle zwei seiner Ecken zusammenhängend sind; Wenn der Graph mindestens ein Paar nicht verbundener Knoten enthält, wird der Graph als nicht verbunden bezeichnet.

Bestimmung 16. Ein Baum ist ein zusammenhängender Graph, der keine Zyklen enthält.

Ein dreidimensionales Modell eines Graphenbaums ist beispielsweise ein echter Baum mit seiner fein verzweigten Krone; Der Fluss und seine Nebenflüsse bilden ebenfalls einen Baum, aber bereits flach - auf der Erdoberfläche.

Bestimmung 17. Ein nicht zusammenhängender Graph, der ausschließlich aus Bäumen besteht, wird als Wald bezeichnet.

Bestimmung 18. Ein Baum, dessen n Ecken alle von 1 bis n nummeriert sind, heißt Baum mit umnummerierten Ecken.

Wir haben also die Hauptdefinitionen der Graphentheorie betrachtet, ohne die es unmöglich wäre, Theoreme zu beweisen und folglich Probleme zu lösen.

Probleme gelöst mit Graphen

Berühmte Herausforderungen

Das Problem des Handlungsreisenden

Das Problem des Handlungsreisenden ist eines der bekanntesten Probleme in der Theorie der Kombinatorik. Es wurde 1934 aufgestellt, und die besten Mathematiker haben sich darüber die Zähne ausgebrochen.

Die Problemstellung ist die folgende.
Der Handelsreisende (reisender Kaufmann) muss die erste Stadt verlassen, die Städte 2,1,3..n einmal in unbekannter Reihenfolge besuchen und in die erste Stadt zurückkehren. Entfernungen zwischen den Städten sind bekannt. In welcher Reihenfolge sollen die Städte durchfahren werden, damit der geschlossene Weg (Tour) des Handlungsreisenden am kürzesten ist?

Methode zur Lösung des Problems des Handlungsreisenden

Gieriger Algorithmus „Geh in die nächste (die du noch nicht betreten hast) Stadt.“
„Greedy“ nennt sich dieser Algorithmus, weil man Gier in den letzten Schritten teuer bezahlen muss.
Betrachten Sie zum Beispiel das Netzwerk in Abbildung [App Abb. 3] eine schmale Raute darstellt. Lassen Sie den Verkäufer bei Stadt 1 beginnen. Der Algorithmus „Zur nächsten Stadt gehen“ bringt ihn zu Stadt 2, dann 3, dann 4; Auf dem letzten Schritt müssen Sie für die Gier bezahlen und entlang der langen Diagonale der Raute zurückkehren. Das Ergebnis ist nicht die kürzeste, sondern die längste Tour.

Das Problem der Königsberger Brücken.

Die Aufgabenstellung ist wie folgt formuliert.
Die Stadt Königsberg liegt am Ufer des Flusses Pregel und zweier Inseln. Verschiedene Teile der Stadt wurden durch sieben Brücken verbunden. Sonntags machten die Bürger Spaziergänge durch die Stadt. Frage: Ist es möglich, einen Spaziergang so zu machen, dass man, nachdem man das Haus verlassen hat, zurückkommt und genau einmal über jede Brücke geht?
Brücken über den Fluss Pregel befinden sich wie auf dem Bild[Anhang Abb.1].

Betrachten Sie einen Graphen, der dem Brückenschema entspricht [Anhang Abb.2].

Um die Frage des Problems zu beantworten, genügt es herauszufinden, ob der Graph Euler ist. (Mindestens ein Knoten muss eine gerade Anzahl von Brücken haben). Wenn man durch die Stadt läuft, ist es unmöglich, alle Brücken einmal zu durchqueren und wieder zurückzukommen.

Mehrere interessante Herausforderungen

1. „Routen“.

Aufgabe 1

Wie Sie sich erinnern, der Jäger tote Seelen Chichikov besuchte berühmte Landbesitzer jeweils einmal. Er besuchte sie in der folgenden Reihenfolge: Manilow, Korobochka, Nozdrev, Sobakevich, Plyushkin, Tentetnikov, General Betrishchev, Petukh, Konstanzholgo, Oberst Koshkarev. Es wurde ein Diagramm gefunden, auf dem Chichikov skizzierte gegenseitige Übereinkunft Landgüter und Landstraßen, die sie verbinden. Stellen Sie fest, welches Anwesen wem gehört, wenn Chichikov keine der Straßen mehr als einmal passiert hat [Anhang Abb.4].

Lösung:

Laut der Straßenkarte ist ersichtlich, dass Chichikov seine Reise mit dem Anwesen E begann und mit dem Anwesen O endete.Wir stellen fest, dass nur zwei Straßen zu den Anwesen B und C führen, also musste Chichikov diese Straßen entlang fahren. Markieren wir sie mit fetten Linien. Die durch A verlaufenden Streckenabschnitte sind festgelegt: AC und AB. Chichikov fuhr nicht auf den Straßen AE, AK und AM. Streichen wir sie durch. Markieren wir mit einer dicken Linie ED ; DK streichen. MO und MN durchstreichen; markieren Sie mit einer fetten Linie MF ; durchstreichen FO ; wir markieren FH , NK und KO mit einer fetten Linie. Lassen Sie uns die einzig mögliche Route unter der gegebenen Bedingung finden. Und wir bekommen: Das Anwesen E - gehört Manilov, D - Korobochka, C - Nozdrev, A - Sobakevich, V - Plyushkin, M - Tentetnikov, F - Betrishchev, N - Petukh, K - Konstanzholgo, O - Koshkarev [App Abb.5].

Aufgabe 2

Die Abbildung zeigt eine Karte des Gebiets [Anhang Abb.6].

Sie können sich nur in Pfeilrichtung bewegen. Jeder Punkt kann höchstens einmal besucht werden. Auf wie viele Arten kommt man von Punkt 1 nach Punkt 9? Welche Strecke ist die kürzeste und welche die längste.

Lösung:

„Schichten“ Sie das Schema sequentiell in einen Baum, beginnend bei Scheitelpunkt 1 [App Abb.7]. Holen wir uns einen Baum. Anzahl mögliche Wege Treffer von 1 bis 9 entsprechen der Anzahl der "hängenden" Knoten des Baums (es gibt 14 davon). Offensichtlich ist der kürzeste Weg 1-5-9; die längste ist 1-2-3-6-5-7-8-9.

2 "Gruppen, Dating"

Aufgabe 1

Teilnehmer des Musikfestivals, nachdem sie sich getroffen hatten, tauschten Umschläge mit Adressen aus. Beweise das:

a) insgesamt wurde eine gerade Anzahl von Umschlägen verschickt;

b) die Anzahl der Teilnehmer, die ungerade oft Umschläge getauscht haben, gerade ist.

Lösung: Die Festivalteilnehmer seien A 1 , A 2 , A 3 . . . , Und n sind die Eckpunkte des Graphen, und die Kanten verbinden Eckpunktpaare, die Typen darstellen, die Umschläge ausgetauscht haben [Anhang Abb.8]

Lösung:

a) Der Grad jedes Knotens A i zeigt die Anzahl der Umschläge, die Teilnehmer A i seinen Freunden gegeben hat. Gesamtzahlübertragenen Hüllkurven N ist gleich der Summe der Grade aller Eckpunkte des Graphen N = step. Ein 1 + Schritt. A 2 + + . . . + Schritt. Und n -1 + Schritt. Und n , N =2p , wobei p die Anzahl der Graphkanten ist, d.h. N ist gerade. Daher wurde eine gerade Anzahl von Umschlägen verschickt;

b) in der Gleichheit N = Schritt. Ein 1 + Schritt. A 2 + + . . . + Schritt. Und n -1 + Schritt. Und n muss die Summe der ungeraden Terme gerade sein, und dies kann nur sein, wenn die Anzahl der ungeraden Terme gerade ist. Und das bedeutet, dass die Anzahl der Teilnehmer, die ungerade oft Umschläge getauscht haben, gerade ist.

Aufgabe 2

Einmal einigten sich Andrei, Boris, Volodya, Dasha und Galya darauf, abends ins Kino zu gehen. Sie beschlossen, die Wahl des Kinos und der Sitzung telefonisch abzustimmen. Es wurde auch beschlossen, dass der Kinobesuch abgesagt wird, wenn niemand telefonisch erreichbar ist. Am Abend versammelten sich nicht alle im Kino, und somit fiel der Kinobesuch aus. Am nächsten Tag begannen sie herauszufinden, wer wen angerufen hatte. Es stellte sich heraus, dass Andrey Boris und Volodya hieß, Volodya Boris und Dasha hieß, Boris Andrey und Dasha hieß, Dasha Andrey und Volodya hieß und Galya Andrey, Volodya und Boris hieß. Wer konnte nicht telefonieren und kam deshalb nicht zum Treffen?

Lösung:

Zeichnen wir fünf Punkte und bezeichnen sie mit den Buchstaben A, B, C, D, E. Dies sind die Anfangsbuchstaben der Namen. Lassen Sie uns die Punkte verbinden, die den Namen der Jungs entsprechen, die sich gegenseitig angerufen haben.

[App Abb.9]

Auf dem Bild ist zu sehen, dass jeder der Jungs - Andrey, Boris und Volodya - alle anderen angerufen hat. Deshalb kamen diese Typen ins Kino. Aber Galya und Dasha haben sich nicht angerufen (Punkte D und D sind nicht durch ein Segment verbunden) und sind daher gemäß der Vereinbarung nicht ins Kino gekommen.

Die Verwendung von Graphen in verschiedenen Bereichen des Lebens von Menschen

Zusätzlich zu den angegebenen Beispielen werden Graphen häufig in Bauwesen, Elektrotechnik, Management, Logistik, Geographie, Maschinenbau, Soziologie, Programmierung, Automatisierung technologischer Prozesse und Industrien, Psychologie und Werbung verwendet. Aus alledem ergibt sich also unwiderlegbar der praktische Wert der Graphentheorie, dessen Nachweis das Ziel dieser Studie war.

In jedem Bereich der Wissenschaft und Technologie trifft man auf Graphen. Graphen sind wunderbare mathematische Objekte, mit denen Sie mathematische, wirtschaftliche und logische Probleme lösen, verschiedene Rätsel lösen und die Bedingungen von Problemen in Physik, Chemie, Elektronik und Automatisierung vereinfachen können. Es ist bequem, viele mathematische Fakten in der Sprache der Graphen zu formulieren. Die Graphentheorie ist Teil vieler Wissenschaften. Die Graphentheorie ist eine der schönsten und anschaulichsten mathematischen Theorien. In letzter Zeit hat die Graphentheorie immer mehr Anwendungen in angewandten Fragestellungen gefunden. Sogar die Computerchemie ist entstanden - ein relativ junges Gebiet der Chemie, das auf der Anwendung der Graphentheorie basiert.

Molekulare Graphen, die in der Stereochemie und strukturellen Topologie, der Chemie von Clustern, Polymeren usw. verwendet werden, sind ungerichtete Graphen, die die Struktur von Molekülen darstellen [App Abb. 10]. Die Ecken und Kanten dieser Graphen entsprechen den entsprechenden Atomen und den chemischen Bindungen zwischen ihnen.

Molekulare Graphen und Bäume: [App Abb. 10] a, b - Multigraphen bzw. Ethylen und Formaldehyd; Mol. Isomere von Pentan (Bäume 4, 5 sind isomorph zu Baum 2).

In der Stereochemie von Organismen am meisten verwenden häufig molekulare Bäume - die Hauptbäume von molekularen Graphen, die nur alle Knoten enthalten, die C-Atomen entsprechen. Bäume und die Feststellung ihrer Isomorphie ermöglichen es Ihnen, den Pier zu bestimmen. Strukturen und finden Gesamtzahl Isomere von Alkanen, Alkenen und Alkinen

Proteinnetzwerke

Proteinnetzwerke - Gruppen physikalisch interagierender Proteine, die in einer Zelle gemeinsam und koordiniert funktionieren und die miteinander verbundenen Prozesse steuern, die im Körper ablaufen [App Abb. elf].

Hierarchischer Systemgraph einen Baum genannt. Unterscheidungsmerkmal Das Besondere an einem Baum ist, dass es zwischen je zwei seiner Eckpunkte nur einen Weg gibt. Der Baum enthält keine Zyklen und Schleifen.

Normalerweise repräsentiert ein Baum hierarchisches System, wird ein Hauptknoten zugewiesen, der als Wurzel des Baums bezeichnet wird. Jeder Scheitelpunkt des Baums (mit Ausnahme der Wurzel) hat nur einen Vorfahren – das von ihm bezeichnete Objekt gehört zu einer Klasse der obersten Ebene. Jeder Knoten des Baums kann mehrere Nachkommen erzeugen – Knoten, die Klassen auf niedrigerer Ebene entsprechen.

Für jedes Paar von Baumknoten gibt es einen eindeutigen Pfad, der sie verbindet. Diese Eigenschaft wird verwendet, wenn alle Vorfahren, beispielsweise in männlicher Linie, einer Person gefunden werden, deren Stammbaum in Form eines Stammbaums dargestellt wird, der auch ein „Baum“ im Sinne der Graphentheorie ist.

Ein Beispiel für meinen Stammbaum [Anhang Abb.12].

Noch ein Beispiel. Die Abbildung zeigt den biblischen Stammbaum [Anhang Abb.13].

Probleme lösen

1. Transportaufgabe. Lassen Sie es in der Stadt Krasnodar eine Basis mit Rohstoffen geben, die in einem Durchgang in den Städten Krymsk, Temryuk, Slavyansk-on-Kuban und Timashevsk gepflanzt werden muss, während Sie so wenig Zeit und Treibstoff wie möglich aufwenden und zurückkehren müssen nach Krasnodar.

Lösung:

Lassen Sie uns zunächst ein Diagramm aller möglichen Routen erstellen. [App Abb.14], unter Berücksichtigung der realen Straßen zwischen diesen Siedlungen und der Entfernung zwischen ihnen. Um dieses Problem zu lösen, müssen wir einen weiteren Graphen, einen Baum, erstellen [App Abb.15].

Zur Vereinfachung der Lösung bezeichnen wir die Städte mit Zahlen: Krasnodar - 1, Krymsk - 2, Temryuk - 3, Slavyansk - 4, Timashevsk - 5.

Das ergab 24 Lösungen, aber wir brauchen nur kürzeste Wege. Von allen Lösungen sind nur zwei zufrieden, das sind 350 km.

Ebenso ist es möglich und meiner Meinung nach notwendig, den tatsächlichen Transport von einem Ort zum anderen zu berechnen.

Logische Aufgabe zur Transfusion. In einem Eimer befinden sich 8 Liter Wasser und es gibt zwei Töpfe mit einem Fassungsvermögen von 5 und 3 Litern. Es ist erforderlich, 4 Liter Wasser in einen Fünf-Liter-Topf zu gießen und 4 Liter in einem Eimer zu lassen, d. H. Wasser zu gleichen Teilen in einen Eimer und einen großen Topf zu gießen.

Lösung:

Die Situation zu jedem Zeitpunkt kann durch drei Zahlen beschrieben werden [Anhang Abb.16].

Als Ergebnis erhalten wir zwei Lösungen: eine in 7 Zügen, die andere in 8 Zügen.

Fazit

Um also zu lernen, wie man Probleme löst, muss man verstehen, was sie sind, wie sie angeordnet sind, woraus sie bestehen Bestandteile Sie bestehen darin, welche Werkzeuge verwendet werden, um Probleme zu lösen.

Bei der Lösung praktischer Probleme mit Hilfe der Graphentheorie wurde deutlich, dass bei jedem Schritt, in jeder Phase ihrer Lösung, Kreativität erforderlich ist.

Von Anfang an, in der ersten Phase, liegt es darin, dass Sie in der Lage sein müssen, die Problemsituation zu analysieren und zu codieren. Die zweite Stufe ist eine schematische Notation, die in der geometrischen Darstellung von Graphen besteht, und in dieser Stufe ist das Element der Kreativität sehr wichtig, da es alles andere als einfach ist, Entsprechungen zwischen den Elementen der Bedingung und den entsprechenden Elementen des Graphen zu finden .

Bei der Lösung eines Transportproblems oder eines Problems bei der Erstellung eines Stammbaums kam ich zu dem Schluss, dass die Diagrammmethode sicherlich interessant, schön und visuell ist.

Ich war davon überzeugt, dass Graphen in Wirtschaft, Management und Technologie weit verbreitet sind. Die Graphentheorie wird auch in der Programmierung verwendet, was in diesem Beitrag nicht diskutiert wurde, aber ich denke, dass dies nur eine Frage der Zeit ist.

In dieser wissenschaftlichen Arbeit werden mathematische Graphen, ihre Anwendungsgebiete betrachtet, mehrere Probleme werden mit Hilfe von Graphen gelöst. Kenntnisse der Grundlagen der Graphentheorie sind in verschiedenen Bereichen des Produktionsmanagements, der Wirtschaft (z. B. Baunetzdiagramm, Postzustellungspläne) erforderlich. Darüber hinaus habe ich während der Arbeit an einer wissenschaftlichen Arbeit das Arbeiten am Computer mit Texten gemeistert WORD-Editor. Also Aufgaben wissenschaftliche Arbeit abgeschlossen.

Aus alledem folgt also unwiderlegbar der praktische Wert der Graphentheorie, dessen Beweis das Ziel dieser Arbeit war.

Literatur

Berge K. Graphentheorie und ihre Anwendungen. -M.: IIL, 1962.

Kemeny J., Snell J., Thompson J. Einführung in die endliche Mathematik. -M.: IIL, 1963.

Erz O. Graphen und ihre Anwendung. -M.: Mir, 1965.

Harry F. Graphentheorie. -M.: Mir, 1973.

Zykov A.A. Theorie endlicher Graphen. -Nowosibirsk: Nauka, 1969.

Beresina L. Yu. Graphen und ihre Anwendung. -M.: Bildung, 1979. -144 p.

„Soros Educational Journal“ Nr. 11 1996 (Artikel „Flat Graphs“);

Gardner M. "Mathematical Leisure", M. "Mir", 1972 (Kapitel 35);

Olekhnik S. N., Nesterenko Yu. V., Potapov M. K. "Alte unterhaltsame Probleme", M. "Nauka", 1988 (Teil 2, Abschnitt 8; Anhang 4);

Blinddarm

Reis. 6

Reis. 7

Reis. 8

Anwendung

Blinddarm

Reis. vierzehn

Anwendung

Blinddarm

Anwendung findet die Graphentheorie beispielsweise in Geoinformationssystemen (GIS). Bestehende oder neu gestaltete Häuser, Gebäude, Quartiere usw. werden als Gipfel betrachtet, und die sie verbindenden Straßen, Ingenieurnetze, Stromleitungen usw. als Kanten. Die Verwendung verschiedener Berechnungen, die auf einem solchen Diagramm durchgeführt werden, ermöglicht es beispielsweise, den kürzesten Umweg oder das nächste Lebensmittelgeschäft zu finden, um die beste Route zu planen.

Die Graphentheorie enthält eine große Anzahl ungelöster Probleme und unbewiesener Hypothesen.

Die Hauptanwendungsgebiete der Graphentheorie:

In der Chemie (zur Beschreibung von Strukturen, Wegen komplexer Reaktionen kann die Phasenregel auch als Problem der Graphentheorie interpretiert werden); Computerchemie ist ein relativ junges Gebiet der Chemie, das auf der Anwendung der Graphentheorie basiert. Die Graphentheorie ist die mathematische Grundlage der Chemoinformatik. Die Graphentheorie ermöglicht es, die Zahl der theoretisch möglichen Isomere von Kohlenwasserstoffen und anderen organischen Verbindungen genau zu bestimmen;

In Informatik und Programmierung (Algorithmus-Graph-Diagramm);

In Kommunikations- und Transportsystemen. Insbesondere zum Routing von Daten im Internet;

In Wirtschaft;

in der Logistik;

In der Schaltungstechnik (die Topologie der Verbindungen von Elementen auf einer Leiterplatte oder einem Mikroschaltkreis ist ein Graph oder Hypergraph).

Es gibt eine besondere Art von Graphen, Holz.Holz ist ein zusammenhängender azyklischer Graph. Konnektivität bedeutet das Vorhandensein von Pfaden zwischen jedem Knotenpaar, Azyklizität bedeutet das Fehlen von Zyklen und die Tatsache, dass es nur einen Pfad zwischen Knotenpaaren gibt. Auf der Abb. 1.3 vorgestellt binärer Baum.

binärer Baum ist eine baumartige Datenstruktur, in der jeder Knoten höchstens zwei hat Nachkommenschaft(Kinder). Normalerweise wird der erste aufgerufen Elternknoten und die Kinder werden benannt Linke Und richtige Erben.

Matrixdarstellung von Graphen. Incident-Matrix.

Die Entwicklung algorithmischer Ansätze zur Analyse der Eigenschaften von Graphen erfordert bestimmte Methoden zur Beschreibung von Graphen, die besser für praktische Berechnungen geeignet sind, einschließlich solcher, die Computer verwenden. Betrachten Sie die drei gebräuchlichsten Arten, Diagramme darzustellen.

Angenommen, alle Knoten und alle Kanten eines ungerichteten Graphen oder alle Knoten und alle Bögen (einschließlich Schleifen) eines gerichteten Graphen sind von eins beginnend nummeriert. Ein Graph (ungerichtet oder gerichtet) kann als Matrix vom Typ dargestellt werden, wobei die Anzahl der Scheitelpunkte und die Anzahl der Kanten (oder Bögen) ist. Für einen ungerichteten Graphen sind die Elemente dieser Matrix wie folgt gegeben:

Für einen gerichteten Graphen sind die Matrixelemente wie folgt gegeben:

Eine so definierte Typmatrix wird aufgerufen Ereignismatrix.

Ein Beispiel für den Erhalt einer Inzidenzmatrix. Für die unten gezeigte Grafik ( Reis. 2.1 einAbb. 2.1 b).

Abb. 2.1 a Abb. 2.1 b

Nachbarschaftsmatrix.

Obwohl die Darstellung eines Graphen in Form einer Inzidenzmatrix in theoretischen Studien eine sehr wichtige Rolle spielt, ist diese Methode in der Praxis sehr ineffizient. Erstens gibt es in der Matrix in jeder Spalte nur zwei Nicht-Null-Elemente, was diese Art der Darstellung des Graphen mit einer großen Anzahl von Knoten unökonomisch macht. Außerdem ist die Lösung praktischer Probleme anhand der Inzidenzmatrix sehr mühsam.

Schätzen wir zum Beispiel die Zeit, die für die Lösung eines so einfachen Problems in einem gerichteten Graphen aufgewendet wird, unter Verwendung der Inzidenzmatrix: Finden Sie für einen bestimmten Knoten seine "Umgebung" - die Menge der Nachfolger und die Menge der Vorgänger des Knotens, d.h. die Menge aller Scheitelpunkte, von denen aus sie direkt erreichbar sind, und die Menge aller Scheitelpunkte, von denen sie direkt erreichbar ist.

Um dieses Problem zu lösen, müssen Sie in der Inzidenzmatrix eines gerichteten Graphen entlang der Zeile mit der Nummer gehen, bis ein Element ungleich Null (+1 oder -1) erscheint. Wenn +1 gefunden wird, müssen Sie in der entsprechenden Spalte die Zeile finden, in der die Zahl -1 steht. Die Nummer der Zeile, die diese Nummer enthält, gibt die Nummer der Ecke an, die direkt von der gegebenen Ecke aus erreichbar ist. Wenn -1 gefunden wird, müssen Sie in der Spalte die Zeile finden, in der 1 steht, und die Nummer des Scheitelpunkts erhalten, von dem aus sie direkt erreichbar ist gegebener Scheitelpunkt. Um die gesamte "Umgebung" zu erhalten, müssen Sie die angegebene Suche nach allen Nicht-Null-Elementen der k-ten Zeile durchführen. Das zeitaufwändigste Verfahren besteht darin, ein Nicht-Null-Element in einer Spalte zu finden. Die Anzahl solcher Suchvorgänge ist gleich dem Grad der Ecke. In diesem Fall werden wir sagen, dass die Komplexität des Algorithmus zum Analysieren der Umgebung eines Knotens (in der Größenordnung von) ist.

Es ist ersichtlich, dass das Auffinden der "Umgebung" aller Scheitelpunkte Zeit in der Größenordnung des Produkts aus der Anzahl der Scheitelpunkte des gerichteten Graphen mal der Summe der Grade aller Scheitelpunkte benötigt, was als proportional zu gezeigt werden kann die Anzahl der Bögen des gerichteten Graphen. Somit ist die Komplexität des "Umgebungs"-Suchalgorithmus, d.h. Die Suche benötigt Zeit in der Größenordnung des Produkts aus der Anzahl der Eckpunkte und der Anzahl der Bögen.

Eine effizientere Matrixstruktur, die einen Graphen darstellt, ist Scheiteladjazenzmatrix, oder Boolesche Matrix Graph. Dies ist eine quadratische Matrix B der Ordnung n, deren Elemente wie folgt definiert sind:

für einen ungerichteten Graphen:

für einen gerichteten Graphen:

Für die unten gezeigte Grafik ( Reis. 2.2 ein) wird die Inzidenzmatrix die Matrix sein, die auf ( Abb. 2.2 b).

Der Beginn der Graphentheorie wird einhellig auf das Jahr 1736 zurückgeführt, als L. Euler das damals populäre Problem der Königsberger Brücken löste. Dieses Ergebnis blieb jedoch für mehr als hundert Jahre das einzige Ergebnis der Graphentheorie. Erst Mitte des 19. Jahrhunderts entwickelte der Elektroingenieur G. Kirchhoff die Theorie der Bäume zum Studium Stromkreise, und der Mathematiker A. Cayley lösten im Zusammenhang mit der Beschreibung der Struktur von Kohlenwasserstoffen Aufzählungsprobleme für drei Baumarten.

Geboren beim Lösen von Rätseln und unterhaltsamen Spielen (Probleme über ein Schachpferd, über Damen, „ Weltreise“, Probleme über Hochzeiten und Harems usw.), ist die Graphentheorie inzwischen zu einem einfachen, zugänglichen und mächtigen Werkzeug zur Lösung von Fragen im Zusammenhang mit einer Vielzahl von Problemen geworden. Diagramme sind buchstäblich allgegenwärtig. In Form von Graphen kann man zum Beispiel Straßendiagramme und Stromkreise, Landkarten und Moleküle chemischer Verbindungen, Verbindungen zwischen Menschen und Menschengruppen interpretieren. In den letzten vier Jahrzehnten hat sich die Graphentheorie zu einem der sich am schnellsten entwickelnden Zweige der Mathematik entwickelt. Dies wird durch die Anforderungen eines schnell wachsenden Anwendungsbereichs getrieben. Es wird beim Entwurf integrierter Schaltungen und Steuerschaltungen, beim Studium von Automaten, logischen Schaltungen, Programmflussdiagrammen, in Wirtschaft und Statistik, Chemie und Biologie, in der Planungstheorie verwendet. Über die Theorie der Graphen findet heute in hohem Maße die Durchdringung mathematischer Methoden in Wissenschaft und Technik statt.

In diesem Aufsatz betrachten wir nicht die eigenen Probleme der Graphentheorie, sondern wie sie verwendet wird Schulkurs Geometrie.

Daher ergibt sich die Relevanz des Forschungsthemas einerseits aus der Popularität von Graphen und verwandten Forschungsmethoden, die fast die gesamte moderne Mathematik auf verschiedenen Ebenen organisch durchdringen, und andererseits aus einem integralen System für ihre Implementierung in der Kurs der Geometrie wurde nicht entwickelt.

Ziel der Studie ist es, die Verwendung von Graphen im Geometrieunterricht der Schule zu untersuchen.

Objekt ist der Prozess des Lehrens von Geometrie.

Thema – Unterrichts- und außerschulische Aktivitäten

Aufgaben: 1) bestimmen Sie das Wesen und den Inhalt der Verwendung von Grafiken im Schulgeometriekurs;

2) Entwicklung von PMK für die Durchführung von Geometrieunterricht in den Klassen 7-9.

Leitthema ist die Konstruktion eines Graphenmodells zum Beweis geometrischer Theoreme.

Theoretische Basis:

1. Die Theorie der Graphen, die 1736 entstand (Leonhard Euler (1708-1783) entwickelte sich rasant, bleibt auch heute noch aktuell, denn in Alltagsleben grafische Illustrationen, geometrische Darstellungen und andere Techniken und Methoden der Visualisierung werden zunehmend eingesetzt.

1. Die Graphentheorie findet Anwendung in verschiedenen Bereichen der modernen Mathematik und ihren zahlreichen Anwendungen (Lipatov E.P.)

2. Die Graphentheorie wird in Bereichen der Mathematik wie mathematische Logik, Kombinatorik usw. verwendet.

Die theoretische Bedeutung der Arbeit liegt in:

Identifizierung von Anwendungsbereichen der Graphentheorie;

Verwendung der Graphentheorie zum Studium geometrischer Theoreme und Probleme;

Die praktische Bedeutung der Arbeit liegt in der Verwendung von Graphen beim Beweis geometrischer Theoreme und beim Lösen von Problemen.

Als Ergebnis dieser Arbeit ist Folgendes entstanden:

Software- und Methodenkomplex zur Durchführung des Geometrieunterrichts in den Klassen 7-9.

Das Schwierigste beim Finden einer Lösung für ein Problem ist das Aufstellen einer Kette logischer Konsequenzen, die zu einer beweisbaren Aussage führt. Um logisch kompetent zu argumentieren, ist es notwendig, die Fähigkeiten eines solchen Denkens zu entwickeln, das helfen würde, disparate geometrische Fakten in logische Beziehungen zu bringen.

Formen spielen eine besondere Rolle bei der Entwicklung der Fähigkeiten einer Denkkultur. Schreiben Studenten. Schriftliche Arbeitsformen sind die wichtigste Aktivität, die stabile Fähigkeiten im logischen Denken beim Beweisen von Theoremen und Lösen von Problemen bildet. Die Form des Schreibens der Bedingungen des Problems, sinnvolle Abkürzungen und Notationen in Berechnungen und Beweisen von Problemen diszipliniert das Denken und fördert das geometrische Sehen. Wie Sie wissen, führt das Sehen zum Denken. Es stellt sich das Problem, wie man logische Verbindungen zwischen disparaten geometrischen Tatsachen herstellt und wie man sie in Form eines einzigen Ganzen anordnet. Um den Fortschritt beim Beweisen von Theoremen und beim Lösen von Problemen zu sehen, ermöglicht die Methode der Graphschemata, die den Beweis anschaulicher macht und es Ihnen ermöglicht, die Beweise von Theoremen und das Lösen von Problemen kurz und genau anzugeben.

Dazu wird ein Baumdiagramm verwendet.

Die Eckpunkte des "Baums" (die Bedingung eines Theorems oder Problems und eine Folge logischer Verknüpfungen) werden als Rechtecke mit darin platzierten Informationen dargestellt, die dann durch Pfeile verbunden werden. Das Ende des Graphenschemas enthält die zu beweisende Behauptung. Die beschriebene Form des Beweisens von Theoremen und Lösen von Problemen ist für die Schüler nützlich und bequem, da sie es ermöglicht, die Hauptphasen des Beweises eines Theorems und der Lösung eines Problems leicht zu unterscheiden.

Forschungsteil.

Abschnitt 1. Untersuchung der Entstehungsgeschichte der Graphentheorie.

"Einmal wurde mir das Problem einer Insel in der Stadt Königsberg angeboten, die von einem Fluss umgeben ist, über den sieben Brücken geworfen werden. Die Frage ist, ob jemand sie kontinuierlich umgehen kann und nur einmal durch jede Brücke geht. Bisher hat er es nicht getan konnte dies tun, aber niemand hat bewiesen, dass es unmöglich ist.Diese Frage, obwohl banal, schien mir jedoch der Aufmerksamkeit wert, weil weder Geometrie noch Algebra noch kombinatorische Kunst zu ihrer Lösung ausreichen , habe ich auf der Grundlage eines völlig überzeugenden Beweises eine einfache Regel gefunden, mit deren Hilfe man bei allen Problemen dieser Art sofort feststellen kann, ob eine solche Schaltung über beliebig viele und beliebig angeordnete Brücken machbar ist oder nicht Sie können in der folgenden Abbildung dargestellt werden, in der A für eine Insel steht und B, C und D Teile des Kontinents sind, die durch Flussarme voneinander getrennt sind. Brücken sind mit den Buchstaben a, b, c, d, e, f, g gekennzeichnet.

Über die Methode, die er entdeckte, um Probleme dieser Art zu lösen, schrieb Euler

Ist es also möglich, die Königsberger Brücken zu umgehen, indem man jede dieser Brücken nur einmal passiert? Um die Antwort zu finden, setzen wir Eulers Brief an Marinoni fort:

„Die Frage ist, ob es möglich ist, alle diese sieben Brücken zu umgehen und jede nur einmal zu passieren, oder nicht. Meine Regel führt zu der folgenden Lösung dieser Frage. Zunächst müssen Sie sich ansehen, wie viele Abschnitte sind durch Wasser getrennt - solche , die keinen anderen Übergang von einem zum anderen haben, außer durch die Brücke. In diesem Beispiel gibt es vier solcher Abschnitte - A, B, C, D. Als nächstes müssen Sie unterscheiden, ob die Anzahl von Brücken, die zu diesen einzelnen Abschnitten führen, ist gerade oder ungerade, also in unserem Fall führen fünf Brücken zu Abschnitt A und drei Brücken zu den restlichen, dh Die Anzahl der Brücken, die zu einzelnen Abschnitten führen, ist ungerade, und diese eine reicht bereits dazu Lösung des Problems. Wenn dies festgestellt ist, wenden wir die folgende Regel an: Wenn die Anzahl der Brücken, die zu jedem einzelnen Abschnitt führen, gerade wäre, wäre die betreffende Umleitung möglich, und gleichzeitig wäre es möglich, diese Umleitung zu beginnen aus irgendeiner Sektion wäre ungerade, denn nur einer wäre ungerade nicht, dann könnte auch dann der Übergang wie vorgeschrieben erfolgen, aber nur der Beginn der Umleitung muss sicher von einem der beiden Abschnitte genommen werden, zu denen eine ungerade Anzahl von Brücken führt. Gäbe es schließlich mehr als zwei Abschnitte, zu denen eine ungerade Zahl von Brücken führt, dann ist eine solche Bewegung im Allgemeinen unmöglich; ließen sich hier andere, schwerwiegendere Probleme anführen, könnte diese Methode noch sinnvoller sein und sollte nicht vernachlässigt werden .

Die Begründung für die obige Regel findet sich in einem Brief von L. Euler an seinen Freund Eler vom 3. April desselben Jahres. Wir werden unten einen Auszug aus diesem Brief nacherzählen.

Der Mathematiker schrieb, dass der Übergang möglich ist, wenn es im Gabelungsabschnitt des Flusses nicht mehr als zwei Bereiche gibt, zu denen eine ungerade Anzahl von Brücken führt. Um sich das besser vorstellen zu können, löschen wir die bereits überwundenen Brücken in der Abbildung. Es ist leicht zu überprüfen, dass, wenn wir beginnen, uns gemäß den Eulerschen Regeln zu bewegen, eine Brücke überqueren und sie löschen, die Abbildung einen Abschnitt zeigt, in dem es wiederum nicht mehr als zwei Bereiche gibt, zu denen eine ungerade Anzahl von Brücken führt, und hinein das Vorhandensein von Bereichen mit einer ungeraden Anzahl von Brücken werden wir uns in einem von ihnen befinden. Wenn wir so weitermachen, werden wir alle Brücken einmal passieren.

Die Geschichte der Brücken der Stadt Königsberg findet eine moderne Fortsetzung.

Problem Es gibt sieben Inseln auf dem See, die wie in Abbildung 2 gezeigt miteinander verbunden sind. Zu welcher Insel soll das Boot die Reisenden bringen, damit sie jede Brücke nur einmal passieren können? Warum können Reisende nicht zur Insel A gebracht werden?

Lösung. Da dieses Problem dem Königsberger Brückenproblem ähnlich ist, werden wir auch die Euler-Regel verwenden, um es zu lösen. Als Ergebnis erhalten wir folgende Antwort: Das Boot muss Reisende zur Insel E oder F bringen, damit sie jede Brücke einmal passieren können. Dieselbe Euler-Regel impliziert, dass der erforderliche Umweg unmöglich ist, wenn er von Insel A ausgeht.

Später arbeiteten Koenig (1774-1833), Hamilton (1805-1865) unter modernen Mathematikern - K. Berzh, O. Ore, A. Zykov - an Graphen.

Historisch gesehen wurde die Graphentheorie vor mehr als zweihundert Jahren im Zuge des Lösens von Rätseln geboren. Sie war sehr lange abseits der Hauptforschungsrichtungen der Wissenschaftler, befand sich im Bereich der Mathematik in der Position von Cinderella, deren Talente erst dann voll zum Vorschein kamen, wenn sie im Mittelpunkt der allgemeinen Aufmerksamkeit stand.

Die erste Arbeit zur Graphentheorie des berühmten Schweizer Mathematikers L. Euler erschien 1736. Der Anstoß für die Entwicklung der Graphentheorie kam um die Wende vom 19. zum 20. Jahrhundert, als die Zahl der Arbeiten auf dem Gebiet der Topologie u Die Kombinatorik, mit der sie am engsten verbunden ist, nahm dramatisch zu. Graphen wurden bei der Konstruktion von elektrischen Schaltplänen und molekularen Schaltkreisen verwendet. Als eigenständige mathematische Disziplin wurde die Graphentheorie erstmals in den 30er Jahren des 20. Jahrhunderts im Werk des ungarischen Mathematikers Koenig eingeführt.

In letzter Zeit durchdringen Graphen und verwandte Forschungsmethoden organisch fast die gesamte moderne Mathematik auf verschiedenen Ebenen. Die Graphentheorie wird als einer der Zweige der Topologie betrachtet; es steht auch in direktem Zusammenhang mit Algebra und Zahlentheorie. Graphen werden effektiv in der Planungs- und Managementtheorie, Planungstheorie, Soziologie, mathematischen Linguistik, Ökonomie, Biologie, Medizin und Geographie verwendet. Graphen werden häufig in Bereichen wie Programmierung, Theorie der endlichen Automaten, Elektronik, zur Lösung probabilistischer und kombinatorischer Probleme, kürzeste Distanz, usw. Mathematischer Spaß und Rätsel gehören auch zur Graphentheorie. Die Graphentheorie entwickelt sich schnell und findet neue Anwendungen.

Abschnitt 2. Haupttypen, Konzepte und Struktur von Graphen.

Die Graphentheorie ist eine mathematische Disziplin, die durch die Bemühungen von Mathematikern geschaffen wurde, daher enthält ihre Präsentation die notwendigen strengen Definitionen.

Ein Graph ist eine Sammlung einer endlichen Anzahl von Punkten, die Scheitelpunkte des Graphen genannt werden, und einige dieser Scheitelpunkte von Linien paarweise verbindet, die Kanten oder Bögen des Graphen genannt werden.

Nr. Name des Diagramms Definition Abbildung Ein Beispiel für die Verwendung dieses Diagrammtyps

1 Nullgraph Knoten des Graphen, die nicht dazugehören Problem: Arkady, Boris. Vladimir, Grigory und Dmitry schüttelten bei dem Treffen niemandem die Hand, jeder schüttelte jedem einmal die Hand. Wie viele Kanten insgesamt vorhanden sind, nennt man isoliert. Handschlag wurde gemacht? Die Situation, die dem Moment entspricht, in dem Handshakes noch nicht stattgefunden haben, ist in der Figur als gepunktetes Diagramm dargestellt.

Ein Graph, der nur aus isolierten Knoten besteht, heißt Nullgraph.

Notation: O" - ein Graph mit Ecken und ohne Kanten

2 Vollständige Graphen Ein Graph, in dem jedes Knotenpaar Beachten Sie, dass, wenn ein vollständiger Graph n Knoten hat, die Anzahl der Kanten gleich ist Alle Handshakes werden durchgeführt.

Notation: U" ist ein Graph bestehend aus n 10.

Ecken und Kanten, die alle möglichen Paare dieser Ecken verbinden. Ein solcher Graph kann als n-Eck dargestellt werden, in dem alle Diagonalen eingezeichnet sind

3 Unvollständige Graphen Graphen, in denen noch nicht alle gebaut sind Die Situation, wenn noch nicht alle Handshakes abgeschlossen sind, A und B, A und D, E die Hände geschüttelt haben und mögliche Kanten D, C und E unvollständig genannt werden.

4 Pfad im Diagramm. Zyklus. Ein Weg im Graphen von einem Scheitelpunkt zum anderen Am Punkt A gibt es eine Garage für einen Schneepflug. Der Fahrer des Autos soll angewiesen worden sein, den Schnee von den Straßen des im Bild gezeigten Stadtteils zu entfernen. Ist es ihm möglich, seine Arbeit an der Kreuzung, an der sich die Garage befindet, zu beenden, wenn es möglich ist, eine Route zwischen diesen Straßen seines Stadtteils nur einmal entlang zu legen?

Spitzen.

Dabei sollte keine Kante der Route mehr als einmal vorkommen. Der Scheitelpunkt, von Es ist unmöglich, da ein geschlossener Pfad, der durch alle Kanten des Graphen geht und entlang dem die Route gelegt wird, für jede Kante nur einmal aufgerufen wird, wenn die Grade aller Scheitelpunkte des Graphen gerade sind.

der anfang des weges, der gipfel am ende der route -

Ende des Weges. Ein Zyklus ist ein Weg, in der Abbildung wird anhand eines Diagramms ein Diagramm von Straßen zwischen besiedelten Gebieten gezeigt, bei dem Anfang und Ende zusammenfallen. Einfache Punkte.

Ein Zyklus ist ein Zyklus, der nicht durchläuft.Zum Beispiel kann von Punkt A (oben in der Grafik) bis Punkt H auf verschiedenen Wegen erreicht werden: ADGH, AEH, AEFCEH, ABCEH.

durch einen der Scheitelpunkte des Graphen mehr als einen Was ist der Unterschied zwischen der AEH-Route und der AEFCEH-Route?

mal. Die Tatsache, dass wir in der zweiten Route an der "Kreuzung" am Punkt E zweimal besuchten.

Diese Route ist länger als AEH. Route AEH ist unter route erhältlich

Wenn der Zyklus alle Kanten enthält, "löscht" AEFCEH die FCE-Route von der letzten.

Einmal grafisch darstellen, dann so ein Zyklus. Die Strecke AEH ist in der Graphik ein Weg, aber die Strecke AEFCEH ist kein Weg.

heißt Euler-Linie.

Verbundene und getrennte Graphen. Definition 1: Ist es möglich, aus einem 12 dm langen Draht einen Würfelrahmen mit einer Längskante herzustellen?

Zwei Eckpunkte des Graphen heißen verbunden, 1 dm, ohne den Draht auseinander zu brechen?

wenn es einen Pfad im Graphen gibt, der an diesen Knoten endet. Wenn es keinen solchen Weg gibt, heißen die Knoten nicht verbunden.

Da der Pfad durch alle Kanten des Graphen und nur einmal entlang jeder Kante verläuft, existiert nur in den folgenden Fällen:

1) wenn der Grad jedes Scheitelpunkts gerade ist (der Pfad geschlossen ist)

2) wenn es nur zwei Ecken mit ungeradem Grad gibt.

Definition 2:

Ein Graph heißt zusammenhängend, wenn jedes Paar seiner Ecken zusammenhängend ist.

Ein Graph heißt unzusammenhängend, wenn er mindestens ein unzusammenhängendes Knotenpaar hat.

6 Bäume Ein Baum ist jeder zusammenhängende Graph, Anhang Nr. 1. Stammbaum Zholmurzaeva Tomiris.

Spitzen. Ein nicht zusammenhängender Graph, der ausschließlich aus Bäumen besteht, wird als Wald bezeichnet.

7 Isomorphe Graphen. Die in der Abbildung gezeigten Diagramme geben die gleichen Informationen. Solche Graphen heißen isomorph (identisch).

8 Das Konzept eines planaren Graphen Ein Graph, der auf einer Aufgabe dargestellt werden kann. In drei verschiedenen Häusern leben drei Flugzeuge bei Nachbarn, die sich miteinander gestritten haben. Es gibt drei Brunnen, nicht weit von der Stelle entfernt, an der sich seine Rippen von ihren Häusern kreuzen. Ist es möglich nur an den Spitzen ab, heißt jedes Haus flach auf jeden der Brunnen zu legen. Pfad, damit sich keine zwei von ihnen schneiden?

Lösung: Nachdem Sie acht Pfade gezeichnet haben, können Sie sicherstellen, dass es nicht möglich ist, den neunten Pfad zu zeichnen, der sich mit keinem der zuvor gezeichneten Pfade schneidet.

Wir konstruieren einen Graphen, dessen Ecken

A, B, C, 1, 2, 3

Die Bedingungen des Problems entsprechen den Häusern und Brunnen, und wir werden versuchen zu beweisen, dass der neunte Pfad - die Kante des Diagramms, die die anderen Kanten nicht schneidet, nicht gezeichnet werden kann.

In der Grafik in der Abbildung gezeichnete Kanten

A1, A2, A3 und B1, B2, VZ (entspricht den Wegen von den Häusern A und B zu allen Brunnen).

Der konstruierte Graph teilte die Ebene in drei Bereiche: X, Y, Z. Vertex B fällt abhängig von seiner Position auf der Ebene in einen dieser drei Bereiche. Wenn Sie jeden der drei Scheitelpunkte berücksichtigen

B zu einem der Bereiche X, Y oder Z, dann stellen Sie sicher, dass jedes Mal einer der Eckpunkte des Graphen 1, 2 oder 3 ist

(einer der Brunnen) ist für den Knoten B „unzugänglich“ (d. h. es ist nicht möglich, eine der Kanten B1, B2 oder B3 zu zeichnen, die die bereits im Diagramm vorhandenen Kanten nicht schneiden würden).

Die Antwort auf die Frage der Aufgabe lautet: „Es ist unmöglich!“

Gerichtete Graphen Eine Kante eines Graphen heißt gerichtete Kante, wenn einer ihrer Knoten als Anfang und der andere als Ende dieser Kante betrachtet wird.

Ein Graph, in dem alle Kanten gerichtet sind, heißt gerichteter Graph.

Ich habe also die grundlegenden Konzepte der Graphentheorie betrachtet, ohne die es unmöglich wäre, Theoreme zu beweisen und folglich Probleme zu lösen.

Fazit zur geleisteten Arbeit:

Ich habe gelernt, alle Informationsmaterialien in einer Tabelle zu strukturieren;

Die Zusammenstellung des theoretischen Materials trägt zu einer visuellen Darstellung der Arten von Graphen und ihrer Anwendung bei;

Sie arbeitete Beispiele für die Anwendung der Graphentheorie bei der Erstellung ihres Stammbaums aus.

Antrag Nr. 1.

GENEOLOGISCHER BAUM

Erstellen Sie einen Stammbaum von Zholmurzaeva Tomiris.

Lösungsmethode.

Grafischer Weg, um das Problem zu lösen.

Eine grafische Möglichkeit, das Problem zu lösen, besteht darin, einen "Baum logischer Bedingungen" zu zeichnen. "Tree" drückt in Form einer einfachen Zeichnung die logische Beziehung zwischen Verwandten aus. Jede Generation auf dem Baum entspricht einem Zweig.

Als Beispiel habe ich meinen Stammbaum genommen.

Abschnitt 3. Anwendung der Graphentheorie.

Wir begegnen Graphen öfter als es möglich ist, so scheint es auf den ersten Blick. Beispiele für Graphen können Straßenkarten, elektrische Schaltungen, Polygonzeichnungen usw. sein. Lange Zeit glaubte man, dass die Graphentheorie hauptsächlich zur Lösung logischer Probleme verwendet wird. Beim Lösen logischer Probleme ist es oft schwierig, sich an die zahlreichen im Problem gegebenen Bedingungen zu erinnern und eine Verbindung zwischen ihnen herzustellen.Graphen helfen bei der Lösung solcher Probleme, indem sie es ermöglichen, die Beziehung zwischen den Daten des Problems zu visualisieren. Die Graphentheorie selbst wurde als Teil der Geometrie angesehen. Im zwanzigsten Jahrhundert fanden sich jedoch breite Anwendungen der Graphentheorie in Wirtschaftswissenschaften, Biologie, Chemie, Elektronik, Netzwerkplanung, Kombinatorik und anderen Bereichen von Wissenschaft und Technologie. Dadurch begann sie sich schnell zu entwickeln und wurde zu einer eigenständigen verzweigten Theorie.Die Lösung vieler mathematischer Probleme wird vereinfacht, wenn man Graphen verwenden kann. Die Darstellung von Daten in Form einer Grafik macht sie sichtbar. Viele Beweise werden auch vereinfacht und überzeugender, wenn Graphen verwendet werden.

3. 1. Anwendung von Graphen in geometrische Probleme und Theoreme.

Mit Hilfe von Graphen kann man leicht logische Folgerungen aufstellen, die zu einer beweisbaren Aussage führen. Geben Sie kurz und genau den Beweis des Satzes und die Lösung des Problems an.

Beweise das gleichschenkligen Dreiecks die von den Scheitelpunkten an der Basis gezogenen Winkelhalbierenden sind gleich.

Lösungsmethoden.

Beweis des Problems durch Argumentation.

Sei ABC ein gleichschenkliges Dreieck mit

B1 A1 Basis AB und Winkelhalbierende AA1 und BB1.

Betrachten Sie ∆ABB1 und ∆BAA1. Sie haben ∟B1AB=

∟A1BA als Winkel an der Basis des gleichschenkligen Dreiecks ∆ABC. ∟ABB1= ∟A1AB

A B, da AA1 und BB1 die Winkelhalbierenden der Winkel an der Basis eines gleichschenkligen Dreiecks sind. AB ist die gemeinsame Seite. Bedeutet

∆ABB1 = ∆BAB1 entlang der Seite und zwei angrenzenden Ecken. Aus der Gleichheit der Dreiecke folgt die Gleichheit ihrer Seiten AA1 und BB1.

Beweis des Problems anhand einer Grafik.

Beweisen Sie: AA=BB

Lassen Sie uns eine Grafik zum Nachdenken verwenden. Die Eckpunkte des Graphen sind die Bedingungen des Theorems oder Problems und die Stadien des Beweises.

Die Kanten des Graphen sind logische Konsequenzen. Das Ende des Graphenschemas ist die zu beweisende Behauptung.

Farbe wird verwendet, um Komponenten hervorzuheben. Die Bedingung des Theorems und das Problem sind blau. Die zu beweisende Behauptung ist rot. Beweisschritte sind in schwarz.

Die beschriebene Form des Beweises von Theoremen und der Lösung von Problemen ist für die Schüler nützlich und bequem, da sie es ermöglicht, die Hauptphasen des Beweises eines Theorems und der Lösung eines Problems herauszugreifen.

3. 2. Programm-methodischer Komplex.

a) Leitfaden für Lehrer.

Das vorgeschlagene Handbuch ist in Übereinstimmung mit dem Geometrielehrbuch der Klassen 7-9 von A. V. Pogorelov zusammengestellt. Sein Hauptzweck besteht darin, den Prozess des Geometriestudiums mit den notwendigen Visualisierungsmitteln auszustatten, den Lehrer beim Unterrichten der Geometrie zu unterstützen: den Prozess des Beweisens von Theoremen, Assimilation von theoretischem Material bei der Lösung von Problemen zu erleichtern. Graphendiagramme sind vielfältig und können je nach Zielsetzung und Unterrichtsform unterschiedlich eingesetzt werden: als illustrativ, zur besseren Sichtbarkeit bei der Erläuterung neuen theoretischen Materials, bei der Verallgemeinerung und Systematisierung von neuem Material (Graphendiagramme mit Theoremen); als Karten zur Durchführung von Einzel- und Frontalbefragungen (Diagramme mit Aufgaben). Dieser Leitfaden wird angeboten Arbeitsheft für Studierende. Das Arbeitsbuch kann zur Organisation verwendet werden unabhängige Arbeit Schülerinnen und Schüler während und nach der Schule.

b) Arbeitsheft für Studierende.

Das Handbuch hat die Form eines Arbeitsbuches. Das Handbuch enthält 28 Graphschemata mit Theoremen und 28 Graphschemata mit Aufgaben. Graph-Diagramme enthalten das wesentliche Programmmaterial, das mit der nötigen Übersichtlichkeit dargestellt wird und das Gerüst der Lösung darstellt. Die Schüler füllen die leeren Zellen nacheinander mit Informationen aus, die die Lösung des Problems ausmachen.

Farbe wird verwendet, um Komponenten hervorzuheben. Die Bedingung des Theorems und das Problem sind blau, die zu beweisende Behauptung ist rot, die Stadien des Beweises sind schwarz.

Das Handbuch ist nützlich für Schüler der Klassen 7-9.

c) Elektronisches Handbuch.

Die Ergebnisse der Arbeit und ihre Diskussion. Das Projekt ist das Ergebnis einer zweijährigen Studie zum Einsatz von Graphen im Schulmathematikunterricht.

Erstellung programmgesteuert - methodischer Komplex und deren Umsetzung erfolgte im Rahmen von:

Durchführung von Klassen des Clubs "Aristoteles" zum Thema "Lösen logischer Probleme mit Graphen".

Anwendungen von Graphen in den Beweisen geometrischer Theoreme und Probleme

Beim Geometrieunterricht in der Klasse 8.9.

Auftritte mit dem Projekt an der Schule wissenschaftlich und praktisch Konferenzen.

FAZIT.

Als ich die Ergebnisse der Untersuchung der Verwendung von Graphen im Schulgeometriekurs zusammenfasste, kam ich zu folgendem Schluss:

1. Der Vorteil des graphischen Beweises von Theoremen und der Problemlösung gegenüber dem traditionellen ist die Veranschaulichung der Dynamik des Beweises von Theoremen und Problemen.

2. Die Einführung in den Prozess des Beweisens geometrischer Theoreme und Probleme der Graph-Schema-Methode trägt dazu bei, die Fähigkeiten der Schüler im Konstruieren von Beweisen zu stärken.

3. Der entwickelte Software- und Methodenkomplex für das Studium der Geometrie in den Klassen 7-9: a) ein Leitfaden für den Lehrer; b) ein Arbeitsbuch für Studierende; c) Das elektronische Handbuch ist nützlich für Schüler der Klassen 7-9.

Senden Sie Ihre gute Arbeit in die Wissensdatenbank ist einfach. Verwenden Sie das untenstehende Formular

Studenten, Doktoranden, junge Wissenschaftler, die die Wissensbasis in ihrem Studium und ihrer Arbeit nutzen, werden Ihnen sehr dankbar sein.

Ähnliche Dokumente

Wiederherstellen von Graphen aus gegebenen Vertex-Adjazenzmatrizen. Konstruktion für jeden Graphen der Matrix der Nachbarschaft von Kanten, Inzidenz, Erreichbarkeit, Gegenerreichbarkeit. Suchen Sie nach der Zusammensetzung von Diagrammen. Bestimmung von lokalen Graden von Grapheckpunkten. Suche nach der Basis von Graphen.

Laborarbeit, hinzugefügt am 01.09.2009

Graphentheorie als Zweig der diskreten Mathematik, der die Eigenschaften endlicher Mengen mit gegebenen Beziehungen zwischen ihren Elementen untersucht. Grundbegriffe der Graphentheorie. Adjazenz- und Inzidenzmatrizen und ihre praktischer Nutzen bei der Analyse von Lösungen.

Zusammenfassung, hinzugefügt am 13.06.2011

Grundbegriffe der Graphentheorie. Scheitelgrad. Routen, Ketten, Zyklen. Zusammenhang und Eigenschaften gerichteter und planarer Graphen, ein Algorithmus zu ihrer Erkennung, Isomorphie. Operationen an ihnen. Eine Übersicht über die Definition von Diagrammen. Euler- und Hamilton-Zyklen.

Präsentation, hinzugefügt am 19.11.2013

Beschreibung eines gegebenen Graphen durch Sätze von Eckpunkten V und Bögen X, Adjazenzlisten, Inzidenz- und Adjazenzmatrix. Die Gewichtsmatrix des entsprechenden ungerichteten Graphen. Bestimmung des Kürzeste-Wege-Baums mit dem Dijkstra-Algorithmus. Bäume in einem Diagramm finden.

Seminararbeit, hinzugefügt am 30.09.2014

Grundbegriffe der Graphentheorie. Abstände in Diagrammen, Durchmesser, Radius und Mittelpunkt. Die Verwendung von Graphen in praktischen menschlichen Aktivitäten. Definition der kürzesten Wege. Euler- und Hamilton-Graphen. Elemente der Graphentheorie im Wahlfach.

Dissertation, hinzugefügt am 19.07.2011

Konzept und Matrixdarstellung von Graphen. Gerichtete und ungerichtete Graphen. Definition von Adjazenzmatrix. Routen, Ketten, Zyklen und ihre Eigenschaften. Metrische Eigenschaften des Diagramms. Anwendung der Graphentheorie in verschiedenen Bereichen der Wissenschaft und Technik.

Seminararbeit, hinzugefügt am 21.02.2009

Mathematische Beschreibung des Systems automatische Kontrolle Graphen verwenden. Erstellen eines Diagramms und seiner Transformation, Beseitigung von Differentialen. Optimierung gerichteter und ungerichteter Graphen, Erstellung von Adjazenz- und Inzidenzmatrizen.

Laborarbeit, hinzugefügt am 11.03.2012

Der Text der Arbeit wird ohne Bilder und Formeln platziert.
Vollversion Die Arbeit ist auf der Registerkarte "Arbeitsdateien" im PDF-Format verfügbar

Einführung

Unsere Welt ist nicht nur voll von Buchstaben und Zahlen, sondern auch von den unterschiedlichsten Bildern. Dies sind Gemälde und Fotografien aller Art sowie zahlreiche Diagramme. Schemata finden sich auf den Logos von Firmen und Autos, Straßenschilder und Karten. Wenn Sie sich den U-Bahn-Plan ansehen bzw Busstrecke, es sind nur Linien mit Punkten. Solche Schemata von Linien (Kanten) und Punkten (Ecken) werden Graphen genannt.

Die Theorie der Graphen entstand dank eines unterhaltsamen Problems, das Leonhard Euler löste. Die Geschichte besagt, dass dieser brillante Mathematiker 1736 in Königsberg Station machte. Die Stadt wurde durch den Fluss in 4 Teile geteilt, die durch sieben Brücken verbunden waren. Es musste geprüft werden, ob es möglich ist, alle Brücken zu umgehen, indem man sie jeweils genau einmal überfährt. Euler stellte fest, dass es unmöglich war, das Problem zu lösen. Die Königsberger Brücken wurden im Zweiten Weltkrieg zerstört, aber diese Geschichte führte zu einer schönen mathematischen Theorie – der Graphentheorie.

Im 20. Jahrhundert hat die Graphentheorie eine unglaubliche Entwicklung erfahren, sie hat zahlreiche Anwendungen in der Planung, Architektur, im Ingenieurwesen und insbesondere in der Informatik und Telekommunikation gefunden. Graphen sind verwandt mit Kombinatorik, diskreter Mathematik, Topologie, Algorithmentheorie und anderen Zweigen der Mathematik.

Welche Chancen hat ein Student, der diese Theorie besitzt? Wird er in seinem Studium Erfolge erzielen können bzw gewöhnliches Leben? Dieser Forschung ist dieses Projekt gewidmet.

Ziel des Projekts: Zeigen Sie, dass die Methoden der Graphentheorie dem Schüler ein Werkzeug geben, um komplexe Olympiade-Probleme zu lösen und im Leben - die Übertragung dringender Informationen zwischen Menschen zu organisieren.

Hypothesen:

Mit Hilfe von Grafiken können Sie viele Olympiade-Probleme leicht lösen

Die Graphentheorie hilft, ein System zur dringenden Benachrichtigung des Teams zu erstellen

Aufgaben:

Erfahren Sie, wie Sie Probleme mithilfe von Diagrammen lösen

Entwickeln Sie eine Website zum Testen von Olympiade-Aufgaben

Entwerfen Sie mithilfe eines Diagramms ein dringendes Alarmsystem für das Klassenzimmer

Forschungsobjekte: Olympiade Probleme, Warnsysteme

Gegenstand der Studie: Graphentheorie, Webprogrammierung.

Forschungsmethoden:

Methoden der Graphentheorie

Methoden der Webprogrammierung

Forschungsplan:

Erfahren Sie mehr über die Geschichte der Graphentheorie

Lerne die Regeln für das Lösen von Olympiade-Problemen mit Hilfe von Graphen

Nehmen Sie an der Schule "Web-Programmierung" teil Informationstechnologien"ECHTES ES"

Entwickeln Sie eine Website zum Testen von Olympiade-Problemen in der Graphentheorie und testen Sie sie an Freunden

Entwerfen Sie ein dringendes Klassenzimmer-Warnsystem (SOK).

Führen Sie ein Experiment durch, um das SOC-System zu testen

Kapitel 1. Graphentheorie in unserem Leben

1.1. Anwendung der Graphentheorie in verschiedene Bereiche

Graphen werden in den unterschiedlichsten Bereichen eingesetzt: beim Entwurf von Stromkreisen, Telefonnetzen, bei der Suche nach Wegen zwischen Siedlungen, in der Wirtschaft.

In der Chemie werden Graphen verwendet, um verschiedene Verbindungen darzustellen. Zur Darstellung können Graphen verwendet werden einfache Moleküle und ziemlich komplexe organische Verbindungen.

Die Graphentheorie spielt in verschiedenen Phasen von Architekturprojekten eine Schlüsselrolle. Nachdem die Teile des Projekts definiert sind und bevor von Skizzen zu Zeichnungen übergegangen wird, ist es hilfreich, ein Beziehungsdiagramm der Elemente des Projekts zu erstellen. Die Analyse von Diagrammen in öffentlichen Gebäuden hilft dabei, den Grad der Zugänglichkeit verschiedener Abteilungen, die Lage der Räumlichkeiten (Buffet, Bibliothek usw.) sowie Feuerleitern zu bestimmen. Mit Diagrammen können Sie die Analyse erheblich vereinfachen schwierige Situationen.

In unserer Zeit ist dank des Internets - einem "Netzwerk von Netzwerken", das Computer auf der ganzen Welt verbindet - die digitale Revolution möglich geworden. Die Leistungsfähigkeit von Computern hat stetig zugenommen, aber dank Netzwerken war es möglich, einen großen Sprung in die digitale Welt zu machen. Graphen und Telekommunikation gehen seit jeher Hand in Hand.

Abbildung 1.1 zeigt verschiedene Schemata, um Computer miteinander zu verbinden. Meistens gibt es drei Möglichkeiten, Computer mit einem lokalen Netzwerk zu verbinden: "gemeinsamer Bus", "Stern" und "Ring". Jedes Diagramm hat einen Graphen, daher wird der Begriff "Netzwerktopologie" verwendet. Eine Netzwerktopologie ist eine Graphenkonfiguration, deren Scheitelpunkte Computer und Router und die Kanten Kommunikationsleitungen (Kabel) zwischen ihnen sind. In Abbildung 1.2 sind alle Topologien als Graphen dargestellt.

Ein Baum ist ein sehr einfacher Graph, in dem es nur einen Pfad zwischen zwei Knoten gibt. Bäume werden in der Genetik zur Veranschaulichung von Familienbanden (Stammbäumen) sowie zur Analyse der Wahrscheinlichkeiten verschiedener Ereignisse verwendet.

Abbildung.1.1. Optionen zum Aufbau lokaler Computernetzwerke

Abbildung 1.2. Optionen zum Aufbau lokaler Computernetzwerke

a - gemeinsamer Bus, b - Stern, c - Ring

Es gibt viele Spiele, bei denen Sie eine bestimmte Grafik erstellen müssen (Labyrinth-Spiele) oder die Grafik verwenden müssen, um festzustellen, ob es eine Gewinnstrategie gibt.

GPS, Karten und Wegbeschreibungen im Internet sind weitere großartige Beispiele dafür, wie Grafiken verwendet werden können. Die Kanten in ihnen sind Straßen und Wege, und die Eckpunkte sind es Siedlungen. Die Scheitelpunkte solcher Graphen haben Namen, und die Kanten entsprechen Zahlen, die die Entfernung in Kilometern angeben. Somit wird ein solcher Graph beschriftet und gewichtet. Diagramme helfen bei der Visualisierung von ÖPNV-Mustern und erleichtern die Planung Ihrer Reise.

Diagramme werden auch in der Öl- und Gasindustrie in Öl- und Gastransportsystemen verwendet. Mit Hilfe grafisch-analytischer Methoden von Gastransportsystemen ist es möglich, aus allen möglichen Umgehungswegen die kürzeste Option auszuwählen.

Die Entwicklung der Informatik hat dazu geführt, dass viele mathematische Modelle in automatischen Prozessen verwendet wurden. Die Maschine kann die Berechnungen problemlos bewältigen, aber die Auswahl der besten Option aus der Menge unter Unsicherheit ist eine viel schwierigere Aufgabe. Es sind neue Algorithmen entstanden, die Mechanismen verwenden, die an eine biologische Revolution erinnern. Sie verwenden Diagramme, um Prozesse zu visualisieren. Die Grundlage bildete die Modellierung von Neuronen im menschlichen Gehirn und das Prinzip ihrer Wirkung neue Theorie- Theorien neuronaler Netze.

1.2. Kapitel Schlussfolgerungen.

Die Graphentheorie hat ihre Anwendung in vielen Bereichen der Wissenschaft, Technik und des täglichen Lebens gefunden. Trotz ihrer breiten Anwendung in verschiedenen Bereichen wird ihr im Schulmathematikunterricht jedoch nur oberflächlich Beachtung geschenkt. Gleichzeitig zeigen verschiedene Experimente im pädagogischen Bereich, dass Elemente der Graphentheorie einen hohen pädagogischen Wert haben und daher in den schulischen Lehrplan aufgenommen werden sollten.

In der Tat wird es für Mittelschüler sehr nützlich sein, die Grundlagen der Graphentheorie zu erlernen, da sie ihnen helfen werden, den Grundkurs der Mathematik zu meistern, und insbesondere beim Lösen von Olympiade-Problemen in Kombinatorik und Wahrscheinlichkeitstheorie.

Kapitel 2

2.1. Graphentheorie in Olympiade-Problemen

Verschiedene mathematische Olympiaden, wie "Kangaroo", "Dino-Olympiad Uchi.ru", International Heuristic Olympiad "Owlet", enthalten auch häufig Probleme der Graphentheorie in unterschiedlichen Formulierungen.

Wie Sie wissen, lieben Kinder alles, was mit Computern und dem Internet zu tun hat, und es ist nicht so einfach, sie mit einem Buch über Mathematik an den Tisch zu setzen. Um das Interesse von Schülern an der Graphentheorie zu wecken, haben die Autoren des Artikels, basierend auf den Kursen zur Webprogrammierung an der School of Information Technologies "REAL-IT", einen Online-Simulator entwickelt, der Tests in der Graphentheorie umfasst die Seite der Tjumener Privatschule "Evolventa »: evolutionenta-tmn.github.io . Schulkinder werden aufgefordert, sechs Aufgaben unterschiedlicher Schwierigkeitsgrade zu lösen, er trägt die Antworten in die Kästchen ein und durch Drücken der Schaltfläche „Fertig stellen“ wird das Ergebnis angezeigt: die Anzahl der Aufgaben, die er richtig gelöst hat (Abbildung 2.1).

Abbildung 2.1. Site-Bildschirmfragment mit Testoptionen

Natürlich wird ein schlaues Kind sofort anfangen, in Suchmaschinen nach Antworten zu suchen, aber es wird nicht genau solche Formulierungen finden, sondern nur ähnliche, beispielsweise auf der Website der wissenschaftlichen und methodischen elektronischen Zeitschrift "Concept". Um das gewünschte Ergebnis zu erzielen: 6 von 6 Aufgaben muss der Schüler verstehen allgemeine Grundsätze Problemlösung mit Hilfe der Graphentheorie. Und in Zukunft werden ihm die gewonnenen Erkenntnisse dabei helfen, sowohl Schul- als auch Olympia-Probleme erfolgreich zu lösen.

Als die Seite vollständig fertig, getestet und im Internet veröffentlicht war, erhielten unsere Klassenkameraden einen Link darauf. Das Interesse an der Seite war groß: Dem Besuchszähler nach zu urteilen, wurde sie in der ersten Woche mehr als 150 Mal besucht! Viele Leute versuchten, Probleme zu lösen, aber sie schienen ihnen schwierig. Sogar einige Eltern mit höher technische Erziehung, eine Reihe von Aufgaben verblüfft, deutet dies darauf hin, dass die Graphentheorie nicht einmal in allen höheren Klassen studiert wird Bildungsinstitutionen. Das bedeutet, dass die von uns erstellten Tests nicht nur für Schulkinder, sondern auch für Erwachsene nützlich sind!

2.2. Graphentheorie beim Entwerfen eines Klassenwarnsystems

Derzeit ist der Bereich des dringenden Personalmanagementsystems in Organisationen gegeben großartige Aufmerksamkeit, da solche Systeme eine wichtige Rolle bei der Organisation aller Aktivitäten der Mitarbeiter spielen.

Ursprünglich wurden Beschallungs- und Evakuierungsmanagementsysteme konzipiert, um Mitarbeiter, Personal und Gäste dringend über einen Brand in einem Gebäude zu informieren, Informationen bereitzustellen und wichtige Informationen für eine schnelle und erfolgreiche Evakuierung von Personen zu übertragen. Heutzutage können solche Systeme nicht nur im Rahmen einer Organisation oder eines Unternehmens beobachtet werden, sondern in unserem ganzen Land, um die Sicherheit der Menschen zu verbessern.

Zu beachten ist, dass sich die meisten verwendeten Warnsysteme an Erwachsene richten. Aber das gefährlichste Alter sind Kinder. Auch Kinder brauchen eigene Systeme, um die meisten Gleichaltrigen in kürzester Zeit auf eine drohende Gefahr oder eine Veränderung der Situation aufmerksam zu machen.

In der Schule verbringt jedes Kind einen erheblichen Teil seiner Zeit: fünf bis sechs Tage die Woche für mehrere Stunden. Daher würde die Schaffung eines Warnsystems für Kinder es ermöglichen, jedes Kind für eine schnelle und kompetente Reaktion auf die veränderte Situation zu organisieren.

Dieses System wäre beispielsweise sehr nützlich, wenn Sie eine Nachricht über eine Gefahr, Informationen über eine dringende Versammlung oder über eine Änderung der Situation übermitteln, wenn sie sich in verschiedenen Teilen der Schule oder allgemein im Wald in den Ferien befinden (Abbildung 2.2).

Abbildung 2.2. Unsere Klasse bei einer Exkursion zum GAU DO TO „Regional Center for Pre-Comscription Training and Patriotic Education“ Outpost „

In dieser Arbeit wurde versucht, am Beispiel einer Klasse ein Sammelmeldesystem zu erstellen Bildungseinrichtung: MAOU SOSH Nr. 89.

Da Kinder selbst Informationen verbreiten müssen, sollten sie nur die ihnen zur Verfügung stehenden Kommunikationsarten - Mobilfunk - nutzen. Die gesamte Gehaltsliste der Klasse sollte benachrichtigt werden, daher wurde eine Klassenumfrage durchgeführt, um zu analysieren, welches der Kinder bereit ist, welche seiner Freunde zu benachrichtigen. In den Fragebögen wurde zunächst eine Einschränkung festgelegt: Jedes Kind schafft es, maximal vier Freunde anzurufen, und wenn Zeit ist, zwei weitere.

Die Umfrage zeigte eine ziemlich hohe Aktivität der Jungs: Im Allgemeinen werden etwa 118 Anrufe in der Klasse getätigt. Es ist fast unmöglich, eine solche Menge an Informationen im Kopf zu analysieren, also entschied man sich für den Einsatz von Informationstechnologie. Das Teambenachrichtigungsmodell wird am besten als Diagramm dargestellt. Die Kanten darin sind Anrufe (oder SMS) und die Scheitelpunkte sind Kinder. Da die Ecken des Graphen Namen haben und die Kanten Zahlen entsprechen, die die Wahrscheinlichkeit eines Anrufs angeben (1 oder 0,5), wird ein solcher Graph beschriftet und gewichtet. Das Diagramm hilft bei der Visualisierung des Teambenachrichtigungsschemas, was die Modellierung erleichtert.

Es wurde entschieden, den Graphen mit dem Werkzeug RAMUS CASE zu visualisieren, da es Ihnen ermöglicht, mit der Farbe von Scheitelpunkten und Kanten zu arbeiten, und es Ihnen auch ermöglicht, Graphscheitelpunkte mit daran angehängten Kanten zur Verdeutlichung zu verschieben. Abbildung 2.3 zeigt einen Graphen des RNS-Systems.

Am 19. November 2017 wurde das entworfene SOK-System getestet. Ursprünglich hatten wir geplant, dass die Benachrichtigung über drei Runden erfolgen würde. Für den ersten Kreis (Beginn der Benachrichtigung) haben wir zwei Kinder ausgewählt, die niemand anrufen möchte, die aber bereit sind anzurufen, sowie die Autoren des Projekts selbst (Abb. 2.3, rosa Blöcke). Weitere Informationen werden an den zweiten Benachrichtigungskreis übermittelt (Abb. 2.4, gelbe Blöcke). Und auf dem dritten Benachrichtigungskreis (Abb. 2.4, grüne Blöcke) wird die ganze Klasse informiert. Aber während des Experiments haben wir gesehen, dass einige Kinder 1,5-2 Stunden im Training sind und nicht auf das Telefon schauen, andere mit einem negativen Kontostand können daher nicht anrufen.

Abbildung 2.3. Klassenwarnungsdiagramm

Abbildung 2.4. SOK-Alarmkreise

Daher wurde unsere Klasse in Wirklichkeit erst in 490 Minuten benachrichtigt - das sind 8 Stunden und 10 Minuten. Aber es war alles 100%. Wichtig dabei ist, dass unser System nicht die Struktur eines Baumes, sondern eines Graphen hat. Und darin führen mehrere Pfade von einem Scheitelpunkt zum anderen, sodass auf jeden Fall alle benachrichtigt werden!

Abbildung 2.6 zeigt ein Diagramm der Klassenwarnungen (Anzahl der alarmierten Personen) im Vergleich zur Zeit (in Minuten).

Abbildung 2.6. Klassenalarmplan

Um den Überblick über Benachrichtigungen zu behalten, mussten die Kinder während des Testprozesses den Autoren des Projekts ihr Lieblingsthema mitteilen, und sie führten Aufzeichnungen darüber, wann und wer die Informationen meldete.

Ein weiteres Testergebnis – eine Umfrage zu Lieblingsfächern (Bild 2.7) – zeigte, dass Kinder in unserer Klasse Mathematik, Informatik und Outdoor-Spiele am liebsten mögen! Und das bedeutet, dass sie die Graphentheorie genauso mögen wie wir.

Abbildung 2.7. Kreisdiagramm der bevorzugten Klassengegenstände

2.3. Kapitel Schlussfolgerungen.

Wir haben beide Hypothesen getestet. Die Website, die wir zum Testen von Olympia-Problemen in der Graphentheorie entwickelt haben, hat dazu beigetragen, festzustellen, dass eine Reihe von Olympia-Problemen ohne Kenntnisse der Graphentheorie einfach nicht gelöst werden können, selbst für erwachsene Ingenieure. Die erste Hypothese wurde bestätigt.

Auch die zweite Hypothese erwies sich als richtig. Das konzipierte und erprobte Sammelmeldesystem am Beispiel einer Klasse ermöglichte die Benachrichtigung des gesamten Kinderteams in 8 Stunden und 10 Minuten. Durch die Optimierung des Diagramms können Sie schnellere Ergebnisse erzielen.

Fazit.

Wir hoffen, dass die Studierenden nach dem Kennenlernen der Graphentheorie und ihrer zahlreichen Anwendungen in verschiedenen Bereichen das Interesse an der Graphentheorie wecken und sich selbstständig weiter mit diesem Teilgebiet der Mathematik beschäftigen. Das Ergebnis der Studie werden höhere Ergebnisse bei den Olympiaden sein.

Zur Anwendung der Graphentheorie in wahres Leben, wird die Relevanz des behandelten Themas durch die Tatsache unterstrichen, dass die Schaffung eines Warnsystems für Kinder die Übertragungsgeschwindigkeit dringender Informationen erhöht, den größten Teil des Kinderteams abdeckt, für das dieses System verwendet wird, und die Reaktionszeit verkürzt der Kinder und sorgen auch für maximale Sicherheit für das Kinderteam. All dies weist auf die offensichtlichen Vorteile der Implementierung des entworfenen Systems hin.

Referenzliste

Beloborodova A.A. Entwicklung des räumlichen Denkens mit Hilfe von Labyrinthspielen / A.A. Beloborodova // "Student Scientific Forum": Materialien der VIII International Student Electronic wissenschaftliche Konferenz.- 2017. https://www.site/2017/7/26746

Beloborodova, A.A. Entwicklung eines Websimulators zum Studium der Graphentheorie / A.A. Beloborodova, S.V. Pakhotin, A.A. Frolov // Neue Informationstechnologien in der Öl- und Gasindustrie und Bildung: Materialien der VII. Internationalen Wissenschaftlich-Technischen Konferenz; bzw. ed. IST ER. Kusjakow. - Tjumen: TIU, 2017. - S. 156-159.

Beloborodova A.A. Verliere dich nicht in Mathe! / AA Beloborodova // XVIII Allrussischer Kinderwettbewerb für wissenschaftliche Forschung. und kreative Arbeiten "Erste Schritte in der Wissenschaft": eine Sammlung von Abstracts. - M.: NS-Integration, Staatsduma der Bundesversammlung der Russischen Föderation, Ministerium für Bildung und Wissenschaft Russlands. - 2016. - S. 110-111 .

Gendenstein, L.E. Alice im Land der Mathematik. Märchen / Für Junior. und durchschn. Schulalter - Kharkiv: Hrsg. - Werbung. Unternehmen "Paritet" LTD, 1994.-288 S., mit Abb.

Davletshin, M.I. Untersuchung der Wirksamkeit von Verfahren zur Entfernung von Bildrauschen / M.I. Davletshin, K.V. Syzrantseva // Energieeinsparung und innovative Technologien im Brennstoff- und Energiekomplex: Werkstoffe des Int. wissenschaftlich-praktisch. Konf. Studenten, Doktoranden, junge Wissenschaftler und Fachkräfte. T.1 / otv. Herausgeber A. N. Khalin. - Tjumen: TIU, 2016. - S. 25-29.

Karnaukhova, A.A. Die Verwendung der Graphentheorie zur Lösung von Problemen in der Wirtschaft / A.A. Karnaukhova, A.F. Dolgopolova // Proceedings of the VII International Student Electronic Scientific Conference "Student Scientific Forum". http://www.scienceforum.ru/2015/991.

Kern, G. Labyrinthe der Welt. St. Petersburg: Verlag "Azbuka-classika", 2007, 448p.

Krause, M.V. Anwendung von Informationstechnologien zur Gestaltung eines Sammelmeldesystems / M.V. Krause, A.A. Beloborodova, E.I. Arbuzova // Neue Informationstechnologien in der Öl- und Gasindustrie und Bildung: Materialien der VII. Internationalen wissenschaftlichen und technischen Konferenz; bzw. ed. IST ER. Kusjakow. - Tjumen: TIU, 2017. - S. 153-156.

Kurs "Erstellen von Websites" School of Information Technology "REAL-IT" http://it-schools.org/faculties/web/

Die Welt der Mathematik: in 40 Bänden V.11: Claudi Alsina. U-Bahn-Karten und Zugnetze. Graphentheorie./ Per. aus dem Spanischen - M.: De Agostini, 2014.- 144 S.

Moskevich L.V. Bildungsolympiade - eine der Formen außerschulischer Aktivitäten in Mathematik / L.V. Moskevich // Wissenschaftliche und methodische elektronische Zeitschrift "Concept". - 2015. - T. 6. - S. 166-170. -URL: http://e-konzept.ru/2015/65234.htm.

Memo an die Bevölkerung „Benachrichtigung der Bevölkerung im Bedrohungs- und Notfall“ http://47.mchs.gov.ru/document/1306125

Rumjanzew, V.O. Mathematische Modellierung des Gastransportsystems mit Hilfe der Graphentheorie / V. O. Rumyantsev // Probleme der Geologie und Mineralentwicklung: Sa. wissenschaftlich tr. / TPU. - Tomsk, 2017. - S. 340 - 342.

Website des Ministeriums für Notsituationen der Russischen Föderation http://www.mchs.gov.ru/dop/Kompleksnaja_sistema_jekstrennogo_opoves

Breite Anwendung der Graphentheorie in der Informatik. Die Verwendung von Graphen in verschiedenen Bereichen des Lebens von Menschen

Proteinnetzwerke

Matrixdarstellung von Graphen. Incident-Matrix.

Nachbarschaftsmatrix.

Senden Sie Ihre gute Arbeit in die Wissensdatenbank ist einfach. Verwenden Sie das untenstehende Formular

Ähnliche Dokumente

Lesen Sie auch:

neue Einträge

Breite Anwendung der Graphentheorie in der Informatik. Die Verwendung von Graphen in verschiedenen Bereichen des Lebens von Menschen

Proteinnetzwerke

Matrixdarstellung von Graphen. Incident-Matrix.

Nachbarschaftsmatrix.

Senden Sie Ihre gute Arbeit in die Wissensdatenbank ist einfach. Verwenden Sie das untenstehende Formular

Ähnliche Dokumente

Lesen Sie auch:

Ner'zhul, Gul'dan und Grommash Hellscream

Derselbe "Elfenhändler

Einer der stirbt (Sally Green) fb2 kostenlos

neue Einträge