Grundlagen der Graphentheorie, Entstehungs- und Entwicklungsgeschichte.  Was ist ein Graph? Ein Graph: Definition - History.NES Geschichte der Graphentheorie

Gipfel(Knoten) verbunden Rippen. In einer strengen Definition ist ein Graph ein solches Mengenpaar G = (V , E) (\displaystyle G=(V,E)), Wo V (\displaystyle V) ist eine Teilmenge einer beliebigen abzählbaren Menge und E (\displaystyle E)- Teilmenge V × V (\displaystyle V\times V).

Anwendung findet die Graphentheorie beispielsweise in geografischen Informationssystemen (GIS). Bestehende oder neu entworfene Häuser, Bauwerke, Blöcke usw. werden als Eckpunkte betrachtet, und die sie verbindenden Straßen, Versorgungsnetze, Stromleitungen usw. werden als Kanten betrachtet. Die Verwendung verschiedener Berechnungen, die auf einem solchen Diagramm durchgeführt werden, ermöglicht es beispielsweise, die kürzeste Umleitungsroute oder das nächste Lebensmittelgeschäft zu finden oder die optimale Route zu planen.

Die Graphentheorie enthält eine Vielzahl ungelöster Probleme und noch unbewiesener Hypothesen.

Geschichte der Graphentheorie

Leonard Euler gilt als Begründer der Graphentheorie. 1736 formulierte und schlug er in einem seiner Briefe eine Lösung für das Problem der sieben Brücken von Königsberg vor, das später zu einem der klassischen Probleme der Graphentheorie wurde. Der Begriff „Graph“ wurde erstmals 1878 von Sylvester und James Joseph in seinem Artikel in Nature geprägt [ ] .

Terminologie der Graphentheorie

Anwendung der Graphentheorie

siehe auch

Anmerkungen

Literatur

• Distel R. Graphentheorie Trans. aus dem Englischen - Nowosibirsk: Verlag des Instituts für Mathematik, 2002. - 336 S. ISBN 5-86134-101-X.
• Diestel R. Graphentheorie, elektronische Ausgabe. - NY: Springer-Verlag, 2005. - S. 422.
• Basaker R., Saati T. Endliche Graphen und Netzwerke. M.: Nauka, 1974. 368c.
• Belov V.V., Vorobiev E.M., Shatalov V.E. Graphentheorie. - M.: Höher. Schule, 1976. - S. 392.
• Berge K. Graphentheorie und ihre Anwendungen. M.: IL, 1962. 320c.
• Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Vorlesungen zur Graphentheorie. M.: Nauka, 1990. 384 S. (Ed. 2, überarbeitet M.: URSS, 2009. 392 S.)

Leonard Euler gilt als Begründer der Graphentheorie. 1736 formulierte und schlug er in einem seiner Briefe eine Lösung für das Problem der sieben Königsberger Brücken vor, das später zu einem der klassischen Probleme der Graphentheorie wurde.

Die ersten Probleme der Graphentheorie betrafen die Lösung mathematischer Freizeitaufgaben und Rätsel. Hier ist eine Nacherzählung eines Auszugs aus Eulers Brief vom 13. März 1736: „Mir wurde ein Problem mit einer Insel gestellt, die in der Stadt Königsberg liegt und von einem Fluss umgeben ist, über den sieben Brücken führen. Die Frage ist, ob jemand sie kontinuierlich umrunden und jede Brücke nur einmal überqueren kann. Und dann wurde mir mitgeteilt, dass dies noch niemandem gelungen sei, aber niemand bewiesen habe, dass es unmöglich sei. Obwohl diese Frage trivial ist, schien sie mir dennoch Aufmerksamkeit zu verdienen, da weder Geometrie noch Algebra noch kombinatorische Kunst ausreichen, um sie zu lösen. Nach langem Nachdenken habe ich eine einfache, auf einem völlig überzeugenden Beweis basierende Regel gefunden, mit deren Hilfe man bei allen Problemen dieser Art sofort feststellen kann, ob ein solcher Umweg über beliebig viele und beliebig viele möglich ist Brücken in irgendeiner Weise lokalisiert oder nicht.“ Die Königsberger Brücken lassen sich schematisch wie folgt darstellen:

Eulers Regel:

1. In einem Diagramm, das keine Eckpunkte ungeraden Grades hat, werden alle Kanten durchlaufen (und jede Kante wird genau einmal durchlaufen), beginnend an einem beliebigen Eckpunkt des Diagramms.

2. In einem Graphen, der nur zwei Scheitelpunkte mit ungeradem Grad hat, gibt es eine Durchquerung, die an einem Scheitelpunkt mit ungeradem Grad beginnt und am anderen endet.

3. In einem Graphen, der mehr als zwei Eckpunkte mit ungeraden Graden hat, existiert ein solcher Durchlauf nicht.

Es gibt noch eine andere Art von Problem im Zusammenhang mit dem Reisen entlang von Diagrammen. Wir sprechen von Problemen, bei denen es notwendig ist, einen Pfad zu finden, der durch alle Scheitelpunkte und nicht mehr als einmal durch jeden führt. Ein Zyklus, der jeden Scheitelpunkt einmal und nur einmal durchläuft, wird Hamilton-Linie genannt (nach William Rowan Hamilton, dem berühmten irischen Mathematiker des letzten Jahrhunderts, der als erster solche Linien untersuchte). Leider wurde noch kein allgemeines Kriterium gefunden, mit dessen Hilfe man entscheiden könnte, ob ein gegebener Graph hamiltonsch ist, und wenn ja, dann alle hamiltonschen Linien darauf finden könnte.

Mitte des 19. Jahrhunderts formuliert. Das Vier-Farben-Problem scheint ebenfalls ein unterhaltsames Problem zu sein, aber Versuche, es zu lösen, haben zu einigen Graphenstudien geführt, die theoretische und angewandte Bedeutung haben. Das Vierfarbenproblem wird wie folgt formuliert: „Kann ein Bereich einer beliebigen flachen Karte mit vier Farben eingefärbt werden, sodass zwei beliebige benachbarte Bereiche mit unterschiedlichen Farben eingefärbt werden?“ Die Hypothese, dass die Antwort positiv ist, wurde Mitte des 19. Jahrhunderts formuliert. Im Jahr 1890 wurde eine schwächere Aussage bewiesen, nämlich dass jede flache Karte in fünf Farben eingefärbt werden kann. Indem wir eine beliebige planare Karte mit ihrem dualen planaren Graphen verknüpfen, erhalten wir eine äquivalente Formulierung des Problems in Bezug auf Graphen: Stimmt es, dass die chromatische Zahl eines beliebigen planaren Graphen kleiner oder gleich vier ist? Zahlreiche Versuche, das Problem zu lösen, beeinflussten die Entwicklung einer Reihe von Bereichen der Graphentheorie. 1976 wurde eine positive Lösung des Problems mithilfe eines Computers angekündigt.

Ein weiteres altes topologisches Problem, das seit langem besonders unlösbar ist und die Rätselliebhaber beschäftigt, ist das „Strom-, Gas- und Wasserversorgungsproblem“. Im Jahr 1917 gab ihm Henry E. Dudeney diese Formulierung. In jedem der drei in der Abbildung dargestellten Häuser müssen Gas, Strom und Wasser installiert sein.

Graphentheorie. 1

Die Entstehungsgeschichte der Graphentheorie. 1

Eulers Regel. 1

Literatur

1. Belov-Graphentheorie, Moskau, "Wissenschaft", 1968.

2. Neue pädagogische und Informationstechnologien E.S. Polat , Moskau, „Akademia“ 1999

3. Kuznetsov O.P., Adelson-Velsky G.M. Diskrete Mathematik für den Ingenieur. – M.: Energoatomizdat, 1988.

4. Cook D., Baze G. Computermathematik. – M.: Wissenschaft, 1990.

5. Nefedov V.N., Osipova V.A. Diskreter Mathematikkurs. – M.: MAI-Verlag, 1992.

6. Erz O. Graphentheorie. – M.: Wissenschaft, 1980.

7. Ismagilov R.S., Kalinkin A.V. Materialien für den praktischen Unterricht im Kurs: Diskrete Mathematik

Als Begründer der Graphentheorie gilt der Mathematiker Leonhard Euler (1707-1783). Die Geschichte 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 verschickt wurde [siehe. S. 41-42]:

„Mir wurde einmal ein Problem zu einer Insel in der Stadt Königsberg gestellt, die von einem Fluss umgeben ist, über den sieben Brücken geworfen werden. Die Frage ist, ob jemand sie ständig umrunden kann und jede Brücke nur einmal passiert. Und dann wurde ich gefragt Ich habe mitgeteilt, dass es noch niemandem gelungen ist, dies zu tun, aber niemand hat bewiesen, dass es unmöglich ist. Obwohl diese Frage trivial ist, schien sie mir dennoch insofern Aufmerksamkeit wert, als weder Geometrie noch Algebra noch kombinatorische Kunst dies tun ausreichen, um es zu lösen... Nach langem Nachdenken habe ich eine einfache, auf einem völlig überzeugenden Beweis basierende Regel gefunden, mit deren Hilfe man bei allen Problemen dieser Art sofort feststellen kann, ob ein solcher Umweg über irgendein Problem gemacht werden kann Anzahl der Brücken beliebig angeordnet oder nicht, so dass sie in der folgenden Abbildung dargestellt werden können[Abb.1] , wobei A eine Insel bezeichnet und B, C und D Teile des Kontinents sind, die durch Flussarme voneinander getrennt sind. Die sieben Brücken sind mit a, b, c, d, e, f, g bezeichnet.“

(ABBILDUNG 1.1)

Über die von ihm entdeckte Methode zur Lösung solcher Probleme schrieb Euler [siehe. S. 102-104]:

„Diese Lösung hat ihrer Natur nach offenbar wenig mit Mathematik zu tun, und ich verstehe nicht, warum man diese Lösung eher von einem Mathematiker als von irgendeiner anderen Person erwarten sollte, denn diese Entscheidung wird allein durch Argumentation gestützt, und das gibt es nicht.“ Um diese Lösung zu finden, müssen alle der Mathematik inhärenten Gesetze einbezogen werden. Ich weiß also nicht, wie es dazu kommt, 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 überquert? Um die Antwort zu finden, setzen wir Eulers Brief an Marinoni fort:

0 „Die Frage besteht darin, festzustellen, 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 dort durch Wasser getrennt – diejenigen, die außer über eine Brücke keinen anderen Übergang von einem zum anderen haben. In diesem Beispiel gibt es vier solcher Abschnitte – A, B, C, D. Als nächstes müssen Sie unterscheiden, ob die Anzahl der Die Anzahl der Brücken, die zu diesen einzelnen Abschnitten führen, ist gerade oder ungerade. In unserem Fall führen also fünf Brücken zu Abschnitt A und jeweils drei Brücken zu den übrigen, d. h. die Anzahl der Brücken, die zu einzelnen Abschnitten führen, ist ungerade, und dies allein reicht zur Lösung aus Das Problem. Sobald 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 von dort aus zu beginnen Jeder Abschnitt. Wenn sie ungerade wären, weil nur einer nicht ungerade sein kann, dann könnte auch dann der Übergang wie vorgeschrieben abgeschlossen werden, aber nur der Anfang des Umweges muss sicherlich von einem der beiden Abschnitte genommen werden, zu denen eine ungerade Anzahl von Brücken führen. 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 hier andere, schwerwiegendere Probleme auftreten könnten, könnte und sollte diese Methode von noch größerem Nutzen sein nicht vernachlässigt werden." .

Die Begründung für die obige Regel findet sich in einem Brief von L. Euler an seinen Freund Ehler vom 3. April desselben Jahres. Wir werden im Folgenden einen Auszug aus diesem Brief noch einmal erzählen.

Der Mathematiker schrieb, dass der Übergang möglich sei, wenn es in der Flussgabelung nicht mehr als zwei Bereiche gebe, zu denen eine ungerade Anzahl von Brücken führe. Damit wir uns das besser vorstellen können, streichen wir in der Abbildung die bereits überquerten Brücken weg. Es ist leicht zu überprüfen, dass, wenn wir uns gemäß den Euler-Regeln 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 wenn ja Sind Gebiete mit einer ungeraden Anzahl Brücken, werden wir uns in einem von ihnen befinden. Wenn wir so weitermachen, werden wir alle Brücken einmal überqueren.

Die Geschichte der Brücken der Stadt Königsberg hat eine moderne Fortsetzung. Öffnen wir zum Beispiel ein Schullehrbuch über Mathematik, herausgegeben von N.Ya. Vilenkina für die sechste Klasse. Darin finden wir auf Seite 98 unter der Überschrift „Aufmerksamkeit und Intelligenz entwickeln“ ein Problem, das in direktem Zusammenhang mit dem Problem steht, das Euler einst gelöst hat.

Problem Nr. 569. Es gibt sieben Inseln im See, die wie in Abbildung 1.2 dargestellt miteinander verbunden sind. Zu welcher Insel soll ein Boot Reisende bringen, damit sie jede Brücke nur einmal überqueren können? Warum können Reisende nicht auf die Insel transportiert werden? A?

Lösung. Da dieses Problem dem Problem der Königsberger Brücken ähnelt, werden wir bei seiner Lösung auch die Eulersche Regel verwenden. Als Ergebnis erhalten wir folgende Antwort: Das Boot muss Reisende zur Insel bringen E oder F damit sie jede Brücke einmal überqueren können. Aus derselben Euler-Regel folgt, dass der erforderliche Umweg unmöglich ist, wenn er von der Insel ausgeht A.

Zusammenfassend stellen wir fest, dass das Problem der Königsberg-Brücken und ähnliche Probleme zusammen mit einer Reihe von Methoden zu ihrer Untersuchung einen in praktischer Hinsicht sehr wichtigen Zweig der Mathematik darstellen, der als Graphentheorie bezeichnet wird. Das erste Werk über Graphen gehörte L. Euler und erschien 1736. Anschließend arbeiteten Koenig (1774-1833), Hamilton (1805-1865) und die modernen Mathematiker C. Berge, O. Ore, A. Zykov an Graphen.

Graphentheorie- einer der umfangreichsten Abschnitte der diskreten Mathematik, der häufig zur Lösung von Wirtschafts- und Managementproblemen, in der Programmierung, Chemie, beim Entwurf und Studium elektrischer Schaltkreise, in der Kommunikation, in der Psychologie, in der Soziologie, in der Linguistik und in anderen Wissensgebieten eingesetzt wird. Graphentheorie untersucht systematisch und konsequent die Eigenschaften von Graphen, von denen man sagen kann, dass sie aus Punktmengen und Linienmengen bestehen, die die Verbindungen zwischen diesen Punkten darstellen. Als Begründer der Graphentheorie gilt Leonhard Euler (1707–1882), der 1736 das damals bekannte Problem der Königsberger Brücken löste.

Diagramme werden erstellt um Beziehungen auf Mengen darzustellen. Sei zum Beispiel eine Menge A = {A1 , A 2 , ... A N)- viele Leute, und jedes Element wird als Punkt angezeigt. Ein Haufen B = {B1 , B 2 , ... B M)- viele Verbindungen (gerade Linien, Bögen, Segmente – das spielt noch keine Rolle). Am Set A das Bekanntschaftsverhältnis zwischen Personen aus dieser Gruppe ist gegeben. Erstellen eines Diagramms aus Punkten und Verknüpfungen. Links verbinden Paare von Personen, die sich kennen. Natürlich kann sich die Anzahl der Bekannten einiger Personen von der Anzahl der Bekannten anderer Personen unterscheiden, und einige kennen möglicherweise überhaupt niemanden (solche Elemente sind Punkte, die nicht miteinander verbunden sind). Wir haben also eine Grafik!

Was wir zuerst „Punkte“ nannten, sollten wir Eckpunkte des Graphen nennen, und was wir „Verbindungen“ nannten, sollten wir Kanten des Graphen nennen.

Die Graphentheorie berücksichtigt nicht die spezifische Natur von Mengen A Und B. Es gibt eine Vielzahl sehr unterschiedlicher spezifischer Probleme, bei deren Lösung man den spezifischen Inhalt von Mengen und ihren Elementen vorübergehend vergessen kann. Diese Besonderheit hat keinerlei Einfluss auf den Fortschritt der Lösung des Problems, unabhängig von seiner Schwierigkeit! Zum Beispiel bei der Entscheidung, ob es von einem Punkt aus möglich ist A komm zum Punkt e, wir bewegen uns nur entlang der Linien, die die Punkte verbinden, es spielt keine Rolle, ob wir es mit Menschen, Städten, Zahlen usw. zu tun haben. Aber wenn das Problem gelöst ist, erhalten wir eine Lösung, die für jeden Inhalt gilt, der als Diagramm modelliert wurde. Daher ist es nicht verwunderlich, dass die Graphentheorie eines der beliebtesten Werkzeuge bei der Schaffung künstlicher Intelligenz ist: Schließlich kann künstliche Intelligenz mit einem Gesprächspartner Fragen der Liebe, Fragen der Musik oder des Sports sowie Fragen der Lösung verschiedener Probleme diskutieren , und zwar ohne jeglichen Übergang (Umschaltung), auf den man in solchen Fällen nicht verzichten kann.

Und nun die strengen mathematischen Definitionen eines Graphen.

Definition 1.Man nennt es ein Diagramm ein System von Objekten beliebiger Natur (Scheitelpunkte) und Verbindungen (Kanten), die einige Paare dieser Objekte verbinden.

Definition 2. Lassen V– (nicht leere) Menge von Eckpunkten, Elementen v∈V- Gipfel. Graph G = G(V) mit vielen Eckpunkten V Es gibt eine bestimmte Familie von Paaren der Form: e = (A, B) , Wo A,B∈V , was angibt, welche Eckpunkte verbunden bleiben. Jedes Paar e = (A, B) - Rand des Diagramms. Ein Haufen U- viele Kanten e Graph. Gipfel A Und B– Endpunkte der Kante e .

Diagramme als Datenstruktur. Die weit verbreitete Verwendung der Graphentheorie in der Informatik und Informationstechnologie ist auf die Hinzufügung des Konzepts eines Graphen als Datenstruktur zu den obigen Definitionen zurückzuführen. In der Informatik und Informationstechnologie wird ein Graph als eine nichtlineare Datenstruktur definiert. Was ist nun eine lineare Datenstruktur und wie unterscheiden sich Graphen davon? Lineare Datenstrukturen zeichnen sich dadurch aus, dass sie Elemente durch Beziehungen vom Typ „einfache Nachbarschaft“ verbinden. Lineare Datenstrukturen sind beispielsweise Arrays, Tabellen, Listen, Warteschlangen, Stacks, Strings. Im Gegensatz dazu sind nichtlineare Datenstrukturen solche, in denen sich Elemente auf verschiedenen Ebenen der Hierarchie befinden und in drei Typen unterteilt werden: ursprünglich, generiert und ähnlich. Ein Graph ist also eine nichtlineare Datenstruktur.

Das Wort Graph ist griechischen Ursprungs und leitet sich von den Wörtern „ich schreibe“ und „ich beschreibe“ ab. Vom Anfang dieses Artikels an wissen wir, was die Grafik genau beschreibt: Sie beschreibt Beziehungen. Das heißt, jedes Diagramm beschreibt Beziehungen. Und umgekehrt: Jede Beziehung kann als Diagramm beschrieben werden.

Grundbegriffe der Graphentheorie

Das Konzept der Inzidenz ist auch bei der Entwicklung von Algorithmen zur Lösung vieler praktischer Probleme mit Graphen notwendig. So können Sie sich beispielsweise mit der Software-Implementierung vertraut machen Tiefendurchquerung des durch die Inzidenzmatrix dargestellten Diagramms. Die Idee ist einfach: Sie können sich nur durch Eckpunkte bewegen, die durch Kanten verbunden sind. Und wenn den Kanten einige Werte zugeordnet werden („Skalen“, meist in Form von Zahlen, solche Graphen werden gewichtet oder beschriftet genannt), dann lassen sich komplexe angewandte Probleme lösen, von denen einige im letzten Absatz erwähnt werden dieser Lektion.

Klassische Probleme der Graphentheorie und ihre Lösungen

Eines der ersten veröffentlichten Beispiele für Arbeiten zur Graphentheorie und der Anwendung von Graphen ist die Arbeit über das „Königsberg Bridges Problem“ (1736), verfasst von dem bedeutenden Mathematiker Leonhard Euler aus dem 18. Jahrhundert. Das Problem besteht aus einem Fluss, Inseln, die von diesem Fluss umspült werden, und mehreren Brücken. Frage des Problems: Ist es möglich, nach dem Verlassen eines bestimmten Punktes jede Brücke nur einmal zu überqueren und zum Ausgangspunkt zurückzukehren? (Bild unten)

Das Problem kann wie folgt modelliert werden: An jeder Landfläche wird ein Punkt befestigt, und zwei Punkte werden genau dann durch eine Linie verbunden, wenn die entsprechenden Landflächen durch eine Brücke verbunden sind (Abbildung unten, Verbindungslinien sind in gestrichelten Linien dargestellt). . Somit ist der Graph konstruiert.

Eulers Antwort auf die Problemfrage lautet wie folgt. Wenn dieses Problem eine positive Lösung hätte, gäbe es im resultierenden Diagramm einen geschlossenen Pfad, der entlang der Kanten verläuft und jede Kante nur einmal enthält. Wenn ein solcher Pfad existiert, darf jeder Scheitelpunkt nur eine gerade Anzahl von Kanten haben. Der resultierende Graph hat jedoch Eckpunkte mit einer ungeraden Anzahl von Kanten. Daher gibt es für das Problem keine positive Lösung.

Nach etablierter Tradition ist ein Euler-Graph ein Graph, in dem es möglich ist, alle Eckpunkte und gleichzeitig eine Kante nur einmal zu durchlaufen. Darin darf jeder Scheitelpunkt nur eine gerade Anzahl von Kanten haben. Ein Problem mittlerer Schwierigkeit zu Euler-Graphen befindet sich im Material „Grundlegende Diagrammtypen“.

Im Jahr 1847 entwickelte Kirchhoff die Baumtheorie zur Lösung eines simultanen Systems linearer algebraischer Gleichungen, die es ermöglichte, den Wert des Stroms in jedem Leiter (Bogen) und in jedem Stromkreis eines Stromkreises zu ermitteln. Ausgehend von elektrischen Schaltkreisen und Schaltkreisen, die Widerstände, Kondensatoren, Induktivitäten usw. enthalten, betrachtete er die entsprechenden kombinatorischen Strukturen, die nur Scheitelpunkte und Verbindungen (Kanten oder Bögen) enthielten, und bei Verbindungen besteht keine Notwendigkeit, zu berücksichtigen, welche Arten von elektrischen Elementen vorhanden sind sie entsprechen . Somit ersetzte Kirchhoff jeden Stromkreis durch einen entsprechenden Graphen und zeigte, dass es zur Lösung eines Gleichungssystems nicht notwendig ist, jeden Zyklus des Stromkreisgraphen separat zu betrachten.

Als Cayley 1858 an rein praktischen Problemen der organischen Chemie arbeitete, entdeckte er eine wichtige Klasse von Graphen, die Bäume genannt wurden. Er versuchte, die Isomere gesättigter Kohlenwasserstoffe mit einer bestimmten Anzahl von Kohlenstoffatomen aufzulisten. Cayley formulierte das Problem zunächst abstrakt: Finden Sie die Anzahl aller Bäume mit P Eckpunkte, von denen jeder Eckpunkte mit den Graden 1 und 4 hat. Er konnte dieses Problem nicht sofort lösen und begann, seine Formulierung so zu ändern, dass ein neues Aufzählungsproblem gelöst werden konnte:

• verwurzelte Bäume (bei denen einer der Eckpunkte ausgewählt ist);
• alle Bäume;
• Bäume, deren Scheitelgrad 4 nicht überschreitet;
• Bäume, deren Scheitelpunktgrade 1 und 4 sind (Stellung eines Problems aus der Chemie).

Diagrammprobleme zur Festigung grundlegender Konzepte

Beispiel 1. Lassen A- Satz der Zahlen 1, 2, 3: A= (1, 2, 3) . Erstellen Sie ein Diagramm, um die Beziehung anzuzeigen.

Lösung. Offensichtlich sollten die Zahlen 1, 2, 3 als Eckpunkte eines Diagramms dargestellt werden. Dann muss jedes Eckpunktpaar durch eine Kante verbunden sein. Bei der Lösung dieses Problems kamen wir zu grundlegenden Konzepten der Graphentheorie wie gerichtete und ungerichtete Graphen. Ungerichtete Graphen sind solche, deren Kanten keine Richtung haben. Oder wie man noch häufiger sagt: Die Reihenfolge der beiden Enden einer Kante ist nicht von Bedeutung. Tatsächlich benötigt der zu Beginn dieser Lektion erstellte Graph, der die Bekanntschaftsbeziehung zwischen Personen widerspiegelt, keine Kantenrichtungen, da argumentiert werden kann, dass „Person Nummer 1“ mit „Person Nummer 2“ im gleichen Maße vertraut ist als „Person Nummer 2“ mit „Person Nummer 1“. In unserem aktuellen Beispiel ist eine Zahl kleiner als eine andere, aber nicht umgekehrt. Daher muss die entsprechende Kante des Diagramms eine Richtung haben, die angibt, welche Zahl kleiner als die andere ist. Das heißt, die Reihenfolge der Kantenenden ist von Bedeutung. Ein solcher Graph (mit Kanten, die eine Richtung haben) wird gerichteter Graph oder Digraph genannt.

Also, in unserer Menge A Nummer 1 ist kleiner als Nummer 2 und Nummer 3, und Nummer 2 ist kleiner als Nummer 3. Wir zeigen diese Tatsache durch Kanten an, die eine Richtung haben, die durch Pfeile angezeigt wird. Wir erhalten die folgende Grafik:

Beispiel 2. Lassen A- Zahlensatz 2, 4, 6, 14: A= (2, 4, 6, 14) . Erstellen Sie ein Diagramm, um die Beziehung „teilbar durch“ für diese Menge anzuzeigen.

Lösung. In diesem Beispiel haben einige Kanten eine Richtung, andere nicht, das heißt, wir bauen gemischtes Diagramm. Listen wir die Beziehungen auf der Menge auf: 4 ist durch 2 teilbar, 6 ist durch 2 teilbar, 14 ist durch 2 teilbar und jede Zahl aus dieser Menge ist durch sich selbst teilbar. Diese Beziehung, das heißt, wenn eine Zahl durch sich selbst teilbar ist, wird in Form von Kanten dargestellt, die den Scheitelpunkt mit sich selbst verbinden. Solche Kanten heißen Schleifen. In diesem Fall ist es nicht erforderlich, der Schleife eine Richtung vorzugeben. In unserem Beispiel gibt es also drei regelmäßig gerichtete Kanten und vier Schleifen. Wir erhalten die folgende Grafik:

Beispiel 3. Seien gegebene Mengen A= (α, β, γ) und B= (a, b, c) . Erstellen Sie ein Diagramm, um die Beziehung „Kartesisches Produkt von Mengen“ anzuzeigen.

Lösung. Wie aus der Definition bekannt ist Kartesisches Produkt von Mengen, es gibt keine geordneten Mengen von Elementen derselben Menge. Das heißt, in unserem Beispiel können Sie griechische Buchstaben nicht mit Griechisch und Latein mit Latein kombinieren. Diese Tatsache wird angezeigt als zweiteiliger Graph, das heißt, eine, bei der die Scheitelpunkte in zwei Teile geteilt sind, sodass die Scheitelpunkte, die zum gleichen Teil gehören, nicht miteinander verbunden sind. Wir erhalten die folgende Grafik:

Beispiel 4. Die Immobilienagentur beschäftigt die Manager Igor, Sergey und Peter. Die Objekte O1, O2, O3, O4, O5, O6, O7, O8 werden bedient. Erstellen Sie ein Diagramm, um die Beziehungen „Igor arbeitet mit den Objekten O4, O7“, „Sergey arbeitet mit den Objekten O1, O2, O3, O5, O6“, „Peter arbeitet mit Objekt O8“ anzuzeigen.

Lösung. Das Diagramm, das diese Beziehungen anzeigt, ist ebenfalls zweiteilig, da der Manager nicht mit dem Manager und das Objekt nicht mit dem Objekt zusammenarbeitet. Im Gegensatz zum vorherigen Beispiel wird der Graph jedoch gerichtet sein. Tatsächlich funktioniert Igor beispielsweise mit Objekt O4, Objekt O4 jedoch nicht mit Igor. Wenn eine solche Eigenschaft von Beziehungen offensichtlich ist, erscheint die Notwendigkeit, den Kanten eine Richtung zu geben, oft wie „mathematische Dummheit“. Aber dennoch, und das folgt aus der strengen Natur der Mathematik, ist es notwendig, den Kanten Richtungen zu geben, wenn die Beziehung einseitig ist. In relationalen Anwendungen zahlt sich diese Strenge aus, beispielsweise in Planungsprogrammen, in denen auch Graphen verwendet werden und die Route entlang von Eckpunkten und Kanten strikt in einer vorgegebenen Richtung verlaufen muss. Wir erhalten also den folgenden gerichteten bipartiten Graphen:

Und noch einmal zu Beispielen mit Zahlen.

Beispiel 5. Gegeben sei eine Menge C = {2, 3, 5, 6, 15, 18} . Konstruieren Sie einen Graphen, der eine Beziehung implementiert, die alle Zahlenpaare definiert A Und B Von vielen C, wobei wir, wenn wir das zweite Element durch das erste dividieren, einen Quotienten erhalten, der eine ganze Zahl größer als 1 ist.

Lösung. Der Graph, der diese Beziehungen anzeigt, wird orientiert sein, da die Bedingung eine Erwähnung des zweiten und ersten Elements enthält, d. h. die Kante wird vom ersten Element zum zweiten gerichtet. Daraus lässt sich eindeutig erkennen, welches Element das erste und welches das zweite ist. Fügen wir auch etwas Terminologie hinzu: Orientierte Kanten werden normalerweise als Bögen bezeichnet. In unserem Diagramm gibt es 7 Bögen: e1 = (3, 15) , e2 = (3, 18) , e3 = (5, 15) , e4 = (3, 6) , e5 = (2, 18) , e6 = (6, 18) , e7 = (2, 6) . In diesem Beispiel werden die Kanten (Bögen) des Diagramms einfach nummeriert, aber fortlaufende Nummern sind nicht das Einzige, was einem Bogen zugewiesen werden kann. Dem Bogen können auch Skalen zugeordnet werden, die beispielsweise die Kosten für den Transport von Fracht von einem Punkt zum anderen bedeuten. Mit Bogengewichten werden wir uns jedoch später und ausführlicher vertraut machen. Wir erhalten also den folgenden gerichteten Graphen:

Wie wir bereits aus dem theoretischen Einführungsteil wissen, berücksichtigt die Graphentheorie nicht die spezifische Natur von Mengen und mit Hilfe desselben Graphen ist es möglich, Beziehungen auf Mengen mit sehr unterschiedlichen Inhalten zu definieren. Das heißt, von eben diesem Inhalt kann bei der Modellierung eines Problems abstrahiert werden. Kommen wir zu Beispielen, die diese bemerkenswerte Eigenschaft der Graphentheorie veranschaulichen.

Beispiel 6. Auf einem 3 x 3 großen Schachbrett werden zwei weiße Springer und zwei schwarze Springer platziert, wie in der Abbildung unten gezeigt.

Ist es möglich, die Ritter in den in der folgenden Abbildung gezeigten Zustand zu bewegen, ohne zu vergessen, dass zwei Figuren nicht auf demselben Feld stehen dürfen?

Lösung. Im konstruierten Diagramm werden Scheitelpunktpaare durch die „Ritterbewegung“-Beziehung verbunden. Das heißt, ein Scheitelpunkt ist der, von dem aus der Ritter gegangen ist, und der andere ist der, an dem er angekommen ist, und die Zwischenzelle des Buchstabens „r“ liegt außerhalb dieser Beziehung. Wir erhalten die folgende Grafik:

Und doch erwies sich das Design als umständlich. Darin sind die Zellen eines Schachbretts sichtbar und viele Kanten des Diagramms schneiden sich. Ist es möglich, von der physischen Erscheinung des Schachbretts zu abstrahieren und sich die Beziehung einfacher vorzustellen? Es stellt sich heraus, dass es möglich ist. Im neuen Diagramm sind die benachbarten Scheitelpunkte diejenigen, die durch die Beziehung „Springerzug“ verbunden sind, und nicht diejenigen, die auf dem Schachbrett benachbart sind (Abbildung unten).

Nun ist leicht zu erkennen, dass die Antwort auf die Frage zu diesem Problem negativ ist. Im Ausgangszustand gibt es keinen schwarzen Ritter zwischen zwei weißen Rittern, aber im Endzustand muss es diesen schwarzen Ritter geben. Die Kanten des Diagramms werden so platziert, dass zwei benachbarte Ritter nicht übereinander springen können.

Beispiel 7. Das Problem mit dem Wolf, der Ziege und dem Kohl. An einem Flussufer gibt es einen Mann (H), ein Boot, einen Wolf (V), eine Ziege (Kz) und einen Kohlkopf (Kp). Es dürfen sich eine Person und maximal einer der transportierten Gegenstände gleichzeitig im Boot aufhalten. Eine Person muss alle Gegenstände auf die andere Seite transportieren und dabei die Bedingung beachten: Ein Wolf darf nicht unbeaufsichtigt mit einer Ziege und eine Ziege mit Kohl bleiben.

Lösung. Im konstruierten Diagramm sind die Eckpunkte Konfigurationen und die Kanten die „Verbindung durch eine Bootsfahrt“-Beziehung zwischen den Konfigurationen. Unter Konfiguration versteht man die Anordnung von Objekten am ursprünglichen Ufer und am gegenüberliegenden Ufer. Jede Konfiguration wird angezeigt als ( A|B) , Wo A- Objekte, die sich am ursprünglichen Ufer befinden, und B- Objekte, die sich am gegenüberliegenden Ufer befinden. Die anfängliche Konfiguration ist daher - (PMCpKz| ) . Nach dem Transport einer Ziege auf die andere Seite sieht die Konfiguration beispielsweise so aus (VKp|ChKz) . Die endgültige Konfiguration ist immer ( |PMCpKz) . Jetzt können wir einen Graphen erstellen, wobei wir bereits wissen, was die Eckpunkte und Kanten bedeuten:

Platzieren wir die Eckpunkte des Diagramms so, dass sich die Kanten nicht schneiden und die benachbarten Eckpunkte diejenigen sind, die durch eine Beziehung im Diagramm verbunden sind. Dann ist es viel einfacher, die Zusammenhänge zu erkennen (zum Vergrößern des Bildes klicken Sie mit der linken Maustaste darauf):

Wie wir sehen können, gibt es zwei verschiedene kontinuierliche Routen von der anfänglichen Konfiguration bis zur endgültigen Konfiguration. Daher gibt es für das Problem zwei verschiedene Lösungen (und beide sind richtig).

Graphentheorie und die wichtigsten modernen angewandten Probleme

Basierend auf der Graphentheorie wurden Methoden zur Lösung angewandter Probleme entwickelt, bei denen sehr komplexe Systeme in Form von Graphen modelliert werden. In diesen Modellen enthalten Knoten einzelne Komponenten und Kanten stellen Verbindungen zwischen Komponenten dar. Typischerweise werden gewichtete Diagramme zur Modellierung von Transportnetzwerken, Warteschlangensystemen und Netzwerkplanung verwendet. Wir haben bereits darüber gesprochen; es handelt sich um Diagramme, in denen den Bögen Gewichte zugewiesen werden.

Baumdiagramme werden beispielsweise zur Konstruktion verwendet Entscheidungsbäume(dienen zur Risikoanalyse, Analyse möglicher Gewinne und Verluste unter Bedingungen der Unsicherheit). Unter Verwendung der Graphentheorie entwickelt und weitere zahlreiche mathematische Modelle Probleme in bestimmten Fachgebieten zu lösen.

Graphen und das Strömungsproblem

Formulierung des Problems. Es gibt ein System von Wasserleitungen, dargestellt durch die Grafik in der Abbildung unten.

Jeder Bogen des Diagramms stellt ein Rohr dar. Die Zahlen über den Bögen (Skalen) geben die Rohrkapazität an. Knoten sind Orte, an denen Rohre verbunden sind. Wasser fließt durch Rohre nur in eine Richtung. Knoten S- Wasserquelle, Knoten T- Aktie. Es ist erforderlich, die Wassermenge, die von der Quelle zum Abfluss fließt, zu maximieren.

Um das Strömungsproblem zu lösen, können Sie die Ford-Fulkerson-Methode verwenden. Die Idee der Methode: Die Suche nach dem maximalen Durchfluss erfolgt schrittweise. Zu Beginn des Algorithmus wird der Fluss auf Null gesetzt. Bei jedem weiteren Schritt erhöht sich der Wert des Flusses, für den ein komplementärer Weg gesucht wird, über den der zusätzliche Fluss ankommt. Diese Schritte werden wiederholt, solange weitere Pfade vorhanden sind. Das Problem wurde erfolgreich in verschiedenen verteilten Systemen angewendet: Stromversorgungssystem, Kommunikationsnetzwerk, Eisenbahnsystem und anderen.

Diagramme und Netzwerkplanung

Bei Planungsproblemen komplexer Prozesse, die aus vielen Aufgaben bestehen, die teils parallel, teils sequentiell ausgeführt werden, haben sich gewichtete Graphen, sogenannte PERT-Netzwerke, durchgesetzt.

PERT – Program (Project) Evaluation and Review Technique – eine Technik zur Bewertung und Analyse von Programmen (Projekten), die im Projektmanagement eingesetzt wird.

Das PERT-Netzwerk ist ein gewichteter azyklischer gerichteter Graph, in dem jeder Bogen eine Aufgabe (Aktion, Operation) darstellt und die Gewichtung des Bogens die Zeit ist, die für die Ausführung erforderlich ist.

Wenn es Bögen im Netzwerk gibt ( A, B) Und ( B, C), dann ist die durch den Bogen dargestellte Arbeit ( A, B) muss abgeschlossen sein, bevor die durch den Bogen dargestellte Arbeit ( B, C). Jeder Scheitelpunkt ( vich) stellt den Zeitpunkt dar, zu dem alle Arbeiten, definiert durch Bögen, die an einem Scheitelpunkt enden ( vich).

In einer Kolumne wie dieser:

• ein Scheitelpunkt, der keine Vorgänger hat, bestimmt den Startzeitpunkt der Arbeit;
• Ein Scheitelpunkt, der keine Anhänger hat, entspricht dem Zeitpunkt, an dem die Gesamtheit der Arbeiten abgeschlossen ist.

Der Weg maximaler Länge zwischen diesen Eckpunkten des Graphen (vom Anfang bis zum Ende des Arbeitsprozesses) wird als kritischer Weg bezeichnet. Um den Zeitaufwand für die Erledigung des gesamten Arbeitskomplexes zu verkürzen, ist es notwendig, Arbeiten zu finden, die auf dem kritischen Pfad liegen, und deren Dauer zu verkürzen, indem beispielsweise zusätzliche Künstler, Mechanismen und neue Technologien angezogen werden.

Der gesamte Block „Graphentheorie“

Material aus Wikipedia – der freien Enzyklopädie

Graphentheorie- ein Zweig der diskreten Mathematik, der die Eigenschaften von Graphen untersucht. Im Allgemeinen wird ein Graph als Menge dargestellt Gipfel(Knoten) verbunden Rippen. In einer strengen Definition wird ein solches Mengenpaar als Graph bezeichnet. $G\; =\; (V,\; E)$, Wo $V$ ist eine Teilmenge einer beliebigen abzählbaren Menge und $E$- Teilmenge $V\backslash mal\; V$.

Anwendung findet die Graphentheorie beispielsweise in geografischen Informationssystemen (GIS). Bestehende oder neu entworfene Häuser, Bauwerke, Blöcke usw. werden als Eckpunkte betrachtet, und die sie verbindenden Straßen, Versorgungsnetze, Stromleitungen usw. werden als Kanten betrachtet. Die Verwendung verschiedener Berechnungen, die auf einem solchen Diagramm durchgeführt werden, ermöglicht es beispielsweise, die kürzeste Umleitungsroute oder das nächste Lebensmittelgeschäft zu finden oder die optimale Route zu planen.

Die Graphentheorie enthält eine Vielzahl ungelöster Probleme und noch unbewiesener Hypothesen.

Geschichte der Graphentheorie

Leonard Euler gilt als Begründer der Graphentheorie. 1736 formulierte und schlug er in einem seiner Briefe eine Lösung für das Problem der sieben Brücken von Königsberg vor, das später zu einem der klassischen Probleme der Graphentheorie wurde.

Terminologie der Graphentheorie

Darstellung von Graphen auf einer Ebene

Bei der Darstellung von Diagrammen in Zeichnungen wird am häufigsten das folgende Notationssystem verwendet: Die Scheitelpunkte des Diagramms werden als Punkte dargestellt oder, wenn die Bedeutung des Scheitelpunkts angegeben wird, als Rechtecke, Ovale usw., wobei die Bedeutung des Scheitelpunkts im Inneren offenbart wird die Abbildung (Grafiken von Flussdiagrammen von Algorithmen). Befindet sich zwischen den Eckpunkten eine Kante, werden die entsprechenden Punkte (Formen) durch eine Linie oder einen Bogen verbunden. Bei einem gerichteten Graphen werden Bögen durch Pfeile ersetzt oder die Richtung einer Kante wird explizit angegeben. Manchmal werden neben der Kante erklärende Inschriften angebracht, die die Bedeutung der Kante verraten, beispielsweise in Übergangsgraphen endlicher Automaten. Es gibt planare und nichtplanare Graphen. Ein planarer Graph ist ein Graph, der in einem Bild (Ebene) ohne sich schneidende Kanten dargestellt werden kann (die einfachsten sind ein Dreieck oder ein Paar verbundener Eckpunkte), andernfalls ist der Graph nicht planar. Für den Fall, dass der Graph keine Zyklen enthält (die mindestens einen Pfad enthalten). einmal Durchquerung von Kanten und Scheitelpunkten mit Rückkehr zum ursprünglichen Scheitelpunkt) wird er üblicherweise als „Baum“ bezeichnet. Wichtige Arten von Bäumen in der Graphentheorie sind Binärbäume, bei denen jeder Scheitelpunkt eine eingehende Kante und genau zwei ausgehende Kanten hat oder endlich ist – also keine ausgehenden Kanten hat und einen Wurzelscheitelpunkt ohne eingehende Kante enthält.

Das Bild eines Diagramms sollte nicht mit dem Diagramm selbst (abstrakte Struktur) verwechselt werden, da einem Diagramm mehr als eine grafische Darstellung zugeordnet werden kann. Das Bild soll nur zeigen, welche Scheitelpunktpaare durch Kanten verbunden sind und welche nicht. In der Praxis ist es oft schwierig, die Frage zu beantworten, ob zwei Bilder Modelle desselben Graphen sind oder nicht (mit anderen Worten, ob die den Bildern entsprechenden Graphen isomorph sind). Abhängig von der Aufgabe können einige Bilder mehr Klarheit bieten als andere.

Einige Probleme der Graphentheorie

• Das Sieben-Brücken-von-Königsberg-Problem ist eines der ersten Ergebnisse der Graphentheorie, veröffentlicht von Euler im Jahr 2010.
• Das Vierfarbenproblem wurde 1852 formuliert, aber ein nichtklassischer Beweis wurde erst 1976 erhalten (4 Farben reichen für eine Karte auf einer Kugel (Ebene)).
• Das Problem des Handlungsreisenden ist eines der bekanntesten NP-vollständigen Probleme.
• Das Cliquenproblem ist ein weiteres NP-vollständiges Problem.
• Finden des minimalen Spannbaums.
• Graphisomorphismus – ist es möglich, einen anderen zu erhalten, indem man die Eckpunkte eines Graphen neu nummeriert?
• Planarität des Diagramms – ist es möglich, das Diagramm auf einer Ebene ohne Schnittpunkte der Kanten darzustellen (oder mit einer minimalen Anzahl von Schichten, die beim Verfolgen von Verbindungen von Elementen von Leiterplatten oder Mikroschaltungen verwendet wird)?

Anwendung der Graphentheorie

siehe auch

Schreiben Sie eine Rezension zum Artikel „Graphentheorie“

Anmerkungen

Literatur

• Distel R. Graphentheorie Trans. aus dem Englischen - Nowosibirsk: Verlag des Instituts für Mathematik, 2002. - 336 S. ISBN 5-86134-101-X.
• Diestel R.. - NY: Springer-Verlag, 2005. - S. 422.
• Basaker R., Saati T.
• Belov V.V., Vorobiev E.M., Shatalov V.E. Graphentheorie. - M.: Höher. Schule, 1976. - S. 392.
• Berge K.
• Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Vorlesungen zur Graphentheorie. M.: Nauka, 1990. 384 S. (Ed. 2, überarbeitet M.: URSS, 2009. 392 S.)
• Zykow A. A.. - M.: „Universitätsbuch“, 2004. - S. 664. - ISBN 5-9502-0057-8.(M.: Nauka, 1987. 383c.)
• Chemische Anwendungen der Topologie und Graphentheorie. Ed. R. König. Pro. aus dem Englischen M.: Mir, 1987.
• Kirsanov M. N. Diagramme in Maple. M.: Fizmatlit, 2007. 168 S. vuz.exponenta.ru/PDF/book/GrMaple.pdf eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf
• Christofides N.
• Cormen T.H. et al. Teil VI. Algorithmen für die Arbeit mit Graphen // Algorithmen: Konstruktion und Analyse = Einführung in Algorithmen. - 2. Aufl. - M.: Williams, 2006. - S. 1296. - ISBN 0-07-013151-1.
• Erz O.. - 2. Aufl. - M.: Wissenschaft, 1980. - S. 336.
• Salii V. N. Bogomolov A. M.. - M.: Physik- und Mathematikliteratur, 1997. - ISBN 5-02-015033-9.
• Swami M., Thulasiraman K.
• Tutt W.
• Wilson R.
• Harari F.. - M.: Mir, 1973.(Ed. 3, M.: KomKniga, 2006. - 296 S.)
• Harari F., Palmer E.. - Welt, 1977.
• Sergej Melnikow// Wissenschaft und Leben. - 1996. - Ausgabe. 3. - S. 144-145. Der Artikel handelt vom Graphenspiel Sim, erfunden von Gustav Simmons.

Links

• : ein Programm, das dem Benutzer eine breite Palette von Werkzeugen und Methoden zur Visualisierung und Suche nach Informationen in Diagrammen bietet

Klassische Analyse Funktionstheorie Differential und Integralgleichungen

Ein Auszug zur Charakterisierung der Graphentheorie

Doch bevor er diese Worte beendete, sprang Prinz Andrei bereits von seinem Pferd und rannte zum Banner, während ihm Tränen der Scham und der Wut in die Kehle stiegen.
- Leute, macht weiter! – schrie er kindisch.
"Hier ist es!" dachte Prinz Andrei, ergriff den Fahnenmast und hörte mit Vergnügen das Pfeifen der Kugeln, die offensichtlich gezielt auf ihn zielten. Mehrere Soldaten fielen.
- Hurra! - Prinz Andrei schrie, hielt kaum das schwere Banner in seinen Händen und rannte vorwärts mit der unbestrittenen Zuversicht, dass das gesamte Bataillon ihm nachlaufen würde.
Tatsächlich lief er nur ein paar Schritte alleine. Ein Soldat machte sich auf den Weg, dann ein anderer, und das ganze Bataillon rief „Hurra!“ rannte vorwärts und überholte ihn. Der Unteroffizier des Bataillons rannte herbei und nahm das vom Gewicht zitternde Banner in den Händen von Fürst Andrei, wurde aber sofort getötet. Prinz Andrei packte erneut das Banner und floh mit dem Bataillon, indem er es an der Stange zog. Vor ihm sah er unsere Artilleristen, von denen einige kämpften, andere ihre Kanonen zurückließen und auf ihn zuliefen; Er sah auch französische Infanteriesoldaten, die sich Artilleriepferde schnappten und die Geschütze drehten. Prinz Andrei und sein Bataillon waren bereits 20 Schritte von den Geschützen entfernt. Er hörte das unaufhörliche Pfeifen von Kugeln über sich, und Soldaten stöhnten ständig und fielen rechts und links von ihm. Aber er sah sie nicht an; er blickte nur auf das, was vor ihm geschah – auf die Batterie. Er sah deutlich die Gestalt eines rothaarigen Artilleristen mit einem auf eine Seite geschlagenen Tschako, der auf der einen Seite ein Banner zog, während auf der anderen Seite ein französischer Soldat das Banner zu sich heranzog. Prinz Andrey sah bereits deutlich den verwirrten und zugleich verbitterten Gesichtsausdruck dieser beiden Menschen, die offenbar nicht verstanden, was sie taten.
"Was machen sie? - dachte Prinz Andrei und sah sie an: - Warum rennt der rothaarige Artillerist nicht, wenn er keine Waffen hat? Warum ersticht ihn der Franzose nicht? Bevor er ihn erreichen kann, wird sich der Franzose an die Waffe erinnern und ihn erdolchen.“
Tatsächlich rannte ein anderer Franzose mit einer Waffe zu seinem Vorteil auf die Kämpfer zu, und das Schicksal des rothaarigen Artilleristen, der immer noch nicht verstand, was ihn erwartete, und triumphierend das Banner herauszog, sollte entschieden werden. Aber Prinz Andrei sah nicht, wie es endete. Es schien ihm, als ob einer der Soldaten in der Nähe ihn mit einem starken Stock in den Kopf schlug. Es tat ein wenig weh und vor allem war es unangenehm, denn dieser Schmerz unterhielt ihn und hinderte ihn daran zu sehen, was er sah.
"Was ist das? Ich falle? Meine Beine geben nach“, dachte er und fiel auf den Rücken. Er öffnete die Augen und hoffte zu sehen, wie der Kampf zwischen den Franzosen und den Artilleristen endete, und wollte wissen, ob der rothaarige Artillerist getötet wurde oder nicht, ob die Waffen erbeutet oder gerettet wurden. Aber er sah nichts. Über ihm war nichts mehr außer dem Himmel – ein hoher Himmel, nicht klar, aber immer noch unermesslich hoch, über dem leise graue Wolken zogen. „Wie ruhig, gelassen und feierlich, ganz und gar nicht so, wie ich gelaufen bin“, dachte Prinz Andrei, „nicht so, wie wir gelaufen, geschrien und gekämpft haben; Es ist überhaupt nicht so, wie der Franzose und der Artillerist mit verbitterten und verängstigten Gesichtern gegenseitig die Banner zogen – ganz und gar nicht so, wie die Wolken über diesen hohen, endlosen Himmel kriechen. Wie kommt es, dass ich diesen hohen Himmel noch nie gesehen habe? Und wie glücklich bin ich, dass ich ihn endlich erkannt habe. Ja! Alles ist leer, alles ist Täuschung, außer diesem endlosen Himmel. Es gibt nichts, nichts außer ihm. Aber selbst das ist nicht da, es gibt nichts als Stille, Ruhe. Und Gott sei Dank!…“

Auf Bagrations rechter Flanke um 9 Uhr hatte das Geschäft noch nicht begonnen. Da Fürst Bagration der Forderung Dolgorukows, das Unternehmen zu gründen, nicht nachkommen wollte und die Verantwortung von sich abschieben wollte, schlug er vor, Dolgorukow zu entsenden, um den Oberbefehlshaber diesbezüglich zu befragen. Bagration wusste, dass aufgrund der Entfernung von fast 10 Werst, die eine Flanke von der anderen trennte, der Gesendete nicht getötet wurde (was sehr wahrscheinlich war) und selbst wenn er den Oberbefehlshaber finden würde, was sehr schwierig war, Der Gesandte hätte an früheren Abenden keine Zeit mehr gehabt, zurückzukehren.
Bagration blickte sich mit seinen großen, ausdruckslosen, schlaflosen Augen zu seinem Gefolge um, und Rostows kindliches Gesicht, unwillkürlich vor Aufregung und Hoffnung erstarrt, fiel ihm als Erstes ins Auge. Er hat es geschickt.
- Was wäre, wenn ich Seine Majestät vor dem Oberbefehlshaber, Exzellenz, treffe? - sagte Rostow und hielt seine Hand an das Visier.
„Sie können es Ihrer Majestät übergeben“, sagte Dolgorukow und unterbrach Bagration hastig.
Nachdem er von der Kette befreit war, gelang es Rostow, vor dem Morgen mehrere Stunden zu schlafen und fühlte sich fröhlich, mutig, entscheidungsfreudig, mit dieser Elastizität der Bewegungen, dem Vertrauen in sein Glück und in dieser Stimmung, in der alles einfach, lustig und möglich erscheint.
Alle seine Wünsche wurden an diesem Morgen erfüllt; es wurde eine allgemeine Schlacht geschlagen, an der er teilnahm; Außerdem war er ein Ordonnanzbeamter unter dem tapfersten General; Außerdem reiste er in einem Auftrag nach Kutusow und vielleicht sogar zum Herrscher selbst. Der Morgen war klar, das Pferd unter ihm war gut. Seine Seele war fröhlich und glücklich. Nachdem er den Befehl erhalten hatte, setzte er sein Pferd ab und galoppierte die Linie entlang. Zunächst ritt er entlang der Linie der Truppen Bagrations, die noch nicht in Aktion getreten waren und regungslos dastanden; dann betrat er den von Uvarovs Kavallerie besetzten Raum und bemerkte hier bereits Bewegungen und Anzeichen von Vorbereitungen für den Fall; Nachdem er Uvarovs Kavallerie passiert hatte, hörte er bereits deutlich den Lärm von Kanonen und Schüssen vor sich. Die Schießerei intensivierte sich.
In der frischen Morgenluft fielen nicht mehr wie zuvor in unregelmäßigen Abständen zwei, drei Schüsse und dann ein oder zwei Gewehrschüsse, und entlang der Berghänge vor Pratzen waren die Schüsse unterbrochen zu hören durch so häufige Schüsse aus Kanonen, dass manchmal mehrere Kanonenschüsse nicht mehr voneinander getrennt waren, sondern zu einem gemeinsamen Brüllen verschmolzen.
Es war zu sehen, wie der Rauch der Geschütze über die Hänge zu laufen schien und sich gegenseitig einholte, und wie der Rauch der Geschütze wirbelte, verschwamm und miteinander verschmolz. Durch den Glanz der Bajonette im Rauch waren die sich bewegenden Massen der Infanterie und schmale Artilleriestreifen mit grünen Büchsen zu erkennen.
Rostow hielt sein Pferd auf einem Hügel für eine Minute an, um zu untersuchen, was los war; aber so sehr er seine Aufmerksamkeit auch anstrengte, er konnte weder verstehen noch etwas von dem Geschehen erkennen: Einige Leute bewegten sich dort im Rauch, einige Truppleinwände bewegten sich sowohl vor als auch hinter ihnen; aber warum? WHO? Wo? es war unmöglich zu verstehen. Dieser Anblick und diese Geräusche erweckten in ihm nicht nur kein dumpfes oder ängstliches Gefühl, sondern verliehen ihm im Gegenteil Energie und Entschlossenheit.
„Nun, mehr, gib mehr!“ - Er wandte sich gedanklich diesen Geräuschen zu und begann erneut entlang der Linie zu galoppieren, wobei er immer weiter in den Bereich der bereits in Aktion getretenen Truppen eindrang.
„Ich weiß nicht, wie es dort sein wird, aber alles wird gut!“ dachte Rostow.
Nachdem er an einigen österreichischen Truppen vorbeigekommen war, bemerkte Rostow, dass der nächste Teil der Linie (es war die Wache) bereits im Einsatz war.
"Umso besser! Ich schaue es mir genauer an“, dachte er.
Er fuhr fast an der Frontlinie entlang. Mehrere Reiter galoppierten auf ihn zu. Das waren unsere Rettungsflieger, die in ungeordneten Reihen vom Angriff zurückkehrten. Rostow ging an ihnen vorbei, bemerkte unwillkürlich, dass einer von ihnen blutüberströmt war, und galoppierte weiter.
„Das ist mir egal!“ er dachte. Bevor er noch ein paar hundert Schritte weitergeritten war, erschien zu seiner Linken über die gesamte Länge des Feldes eine riesige Schar Kavalleristen auf schwarzen Pferden in glänzend weißen Uniformen, die direkt auf ihn zu trotteten. Rostow setzte sein Pferd in vollen Galopp, um diesen Kavalleristen aus dem Weg zu gehen, und er wäre ihnen entkommen, wenn sie den gleichen Gang beibehalten hätten, aber sie beschleunigten weiter, so dass einige Pferde bereits galoppierten. Rostow hörte ihr Stampfen und das Klirren ihrer Waffen immer deutlicher, und ihre Pferde, Gestalten und sogar Gesichter wurden immer deutlicher sichtbar. Dies waren unsere Kavalleriewachen, die einen Angriff auf die französische Kavallerie starteten, die auf sie zukam.
Die Kavalleriewachen galoppierten, hielten aber immer noch ihre Pferde. Rostow sah bereits ihre Gesichter und hörte den Befehl: „Marsch, marsch!“ geäußert von einem Offizier, der sein Blutpferd mit voller Geschwindigkeit losließ. Rostow, der befürchtete, zerquetscht oder zu einem Angriff auf die Franzosen verleitet zu werden, galoppierte so schnell sein Pferd konnte an der Front entlang und schaffte es dennoch nicht, an ihnen vorbeizukommen.
Der letzte Kavalleriewächter, ein riesiger, pockennarbiger Mann, runzelte wütend die Stirn, als er Rostow vor sich sah, mit dem er unweigerlich zusammenstoßen würde. Dieser Kavalleriewächter hätte Rostow und seine Beduinen sicherlich niedergeschlagen (Rostow selbst schien im Vergleich zu diesen riesigen Menschen und Pferden so klein und schwach), wenn er nicht daran gedacht hätte, dem Pferd des Kavalleriewächters seine Peitsche in die Augen zu schwingen. Das schwarze, schwere, fünf Zoll große Pferd scheute zurück und legte die Ohren ab; Aber die pockennarbige Kavalleriewache stieß ihr riesige Sporen in die Seite, und das Pferd stürmte, seinen Schwanz wedelnd und seinen Hals streckend, noch schneller. Sobald die Kavalleriewache an Rostow vorbeikam, hörte er sie rufen: „Hurra!“ und als er zurückblickte, sah er, dass sich in ihren vordersten Reihen Fremde, wahrscheinlich französische, Kavalleristen mit roten Schulterklappen befanden. Es war unmöglich, etwas weiter zu sehen, denn unmittelbar danach begannen von irgendwoher Kanonen zu schießen und alles war in Rauch gehüllt.
In diesem Moment, als die Kavalleriewachen, nachdem sie an ihm vorbeigekommen waren, im Rauch verschwanden, zögerte Rostow, ob er ihnen nachgaloppieren oder dorthin gehen sollte, wo er hin musste. Dies war der brillante Angriff der Kavalleriewachen, der die Franzosen selbst überraschte. Rostow hatte Angst, als er später hörte, dass von all dieser Masse riesiger, gutaussehender Menschen, von all diesen brillanten, reichen jungen Männern auf Tausenden von Pferden, Offizieren und Kadetten, die an ihm vorbeigaloppierten, nach dem Angriff nur noch achtzehn Menschen übrig waren.