Vortrag zum Thema Graphen. Grafiken

1 Folie

2 Folie

Die Grundlagen der Graphentheorie tauchten erstmals in den Werken von Leonhard Euler (1707–1783; Schweizer, deutscher und russischer Mathematiker) auf, in denen er das Lösen von Rätseln und mathematischen Unterhaltungsproblemen beschrieb. Die Graphentheorie begann mit Eulers Lösung des Problems der sieben Brücken von Königsberg.

3 Folie

Das folgende Rätsel ist unter den Königsbergern seit langem verbreitet: Wie kann man alle Brücken (über den Fluss Pregolya) überqueren, ohne eine von ihnen zweimal zu überqueren? Viele haben versucht, dieses Problem sowohl theoretisch als auch praktisch bei Spaziergängen zu lösen. Aber es gelang niemandem, aber es gelang ihnen auch nicht, zu beweisen, dass es überhaupt theoretisch unmöglich war. In einem vereinfachten Diagramm von Teilen einer Stadt (Grafik) entsprechen Brücken Linien (Bögen der Grafik) und Teile der Stadt entsprechen Punkten, die Linien verbinden (Eckpunkte der Grafik). Im Zuge seiner Überlegungen kam Euler zu folgenden Schlussfolgerungen: Es ist unmöglich, alle Brücken zu überqueren, ohne eine von ihnen zweimal zu überqueren.

4 Folie

Es gibt 4 Blutgruppen. Wenn Blut von einer Person zur anderen übertragen wird, sind nicht alle Gruppen kompatibel. Es ist jedoch bekannt, dass identische Gruppen von Person zu Person übertragen werden können, d. h. 1 – 1, 2 – 2 usw. Und auch Gruppe 1 kann auf alle anderen Gruppen übertragen werden, Gruppen 2 und 3 nur auf Gruppe 4. Aufgabe.

5 Folie

6 Folie

Diagramme Ein Diagramm ist ein Informationsmodell, das in grafischer Form dargestellt wird. Ein Graph ist eine Menge von Eckpunkten (Knoten), die durch Kanten verbunden sind. Ein Graph mit sechs Eckpunkten und sieben Kanten. Eckpunkte heißen benachbart, wenn sie durch eine Kante verbunden sind.

7 Folie

Gerichtete Graphen - Digraphen Jede Kante hat eine Richtung. Solche Kanten werden Bögen genannt. Gerichteter Graph

8 Folie

Gewichteter Graph Hierbei handelt es sich um einen Graphen, dessen Kanten oder Bögen numerische Werte zugeordnet sind (sie können beispielsweise die Entfernung zwischen Städten oder die Transportkosten angeben). Das Gewicht eines Graphen ist gleich der Summe der Gewichte seiner Kanten. Die Tabelle (Gewichtsmatrix genannt) verfügt über ein entsprechendes Diagramm. 1 2 4 2 3 A B C D E

Folie 9

Zwischen den Siedlungen A, B, C, D, E, F wurden problematische Straßen gebaut, deren Länge in der Tabelle aufgeführt ist. (Das Fehlen einer Zahl in der Tabelle bedeutet, dass es keinen direkten Weg zwischen den Punkten gibt). Bestimmen Sie die Länge des kürzesten Weges zwischen den Punkten A und F (unter der Annahme, dass die Fahrt nur auf befestigten Straßen möglich ist). 1) 9 2) 10 3) 11 4) 12

10 Folie

1. 2. 3. 4. 5. Die Länge der kürzesten Route A-B-C-E-F beträgt 9 2 4 2 4 7 1 2 4 7 1 3 4 2 4 7 1 3 4 3 2 4 7 1 3 4 3 2

Führen Sie die Schüler in das Konzept des „Graphs“ und die Grundprinzipien seiner Konstruktion ein.

die Fähigkeit entwickeln, Beziehungen zwischen Objekten zu erkennen;

Aufmerksamkeit und Fähigkeit zum logischen Denken entwickeln;

Entwickeln Sie gegenseitige Unterstützung und die Fähigkeit, im Team zu arbeiten

Festigung des erworbenen Wissens in der Praxis

Entwicklung von Gedächtnis, Aufmerksamkeit;

Entwicklung der Unabhängigkeit;

Bildung kognitiver Aktivität.

Ausrüstung:

Computerkurs ausgestattet mit moderner Technik, Videoprojektor, Leinwand;
Computer mit Windows XP-Betriebssystem, Microsoft Office 2003 PowerPoint;
Bordausrüstung (Unterrichtsthema, neue Begriffe). Handzettel.

Unterrichtsplan.

II. Präsentation von neuem Material. (10 Minuten.)

III. Fixieren des Materials. Praktische Arbeit. (15-20 Min.)

IV. Zusammenfassung der Lektion. (2 Min.)

V. Hausaufgaben.

I. Organisatorischer Moment. Wissen aktualisieren.

Guten Tag! Unsere Lektion heißt „Grafiken“. Wir werden uns mit dem Konzept der „Graphen“ vertraut machen, lernen, sie darzustellen und Probleme zu diesem Thema zu lösen.

II Präsentation von neuem Material.

Das erste Werk zur Graphentheorie stammt von Leonhard Euler (1736), obwohl der Begriff „Graph“ erstmals 1936 vom ungarischen Mathematiker Dénes König eingeführt wurde. Als Graphen bezeichnet man Schemata, die aus Punkten und Liniensegmenten oder Kurven bestehen, die diese Punkte verbinden (Beispiele für Graphen sind in Abbildung 1 dargestellt).

Mit Hilfe von Grafiken wurde oft die Lösung von Problemen vereinfacht, die in verschiedenen Wissensgebieten formuliert wurden: in der Automatisierung, Elektronik, Physik, Chemie usw. Mit Hilfe von Grafiken werden Diagramme von Straßen, Gasleitungen, Wärme- und Stromnetzen dargestellt . Grafiken helfen bei der Lösung mathematischer und wirtschaftlicher Probleme.

Graph – (aus dem Griechischen grapho – ich schreibe) ist ein Mittel zur visuellen Darstellung der Elemente eines Objekts und der Verbindungen zwischen ihnen. Das sind wunderbare mathematische Objekte, mit deren Hilfe man viele verschiedene, äußerlich unterschiedliche Probleme lösen kann.

Ein Diagramm ist eine Art Informationsmodell

Der Graph besteht aus Eckpunkten oder Knoten, die durch Bögen oder Segmente – Kanten – verbunden sind. Eine Linie kann gerichtet sein, also einen Pfeil (Bogen) haben; wenn sie nicht gerichtet ist, hat sie eine Kante. Zwei durch einen Bogen oder eine Kante verbundene Scheitelpunkte werden als benachbart bezeichnet.

Beispiele für Grafiken (Folie 4, 5, 6)

Aufgabe 1 (Folie 7):

Zwischen den neun Planeten des Sonnensystems wurde eine Weltraumkommunikation hergestellt. Geplante Raketen fliegen auf folgenden Strecken:

Erde - Merkur; Pluto - Venus; Erde - Pluto; Pluto – Merkur; Merkur - Venus; Uranus - Neptun; Neptun - Saturn; Saturn – Jupiter; Jupiter - Mars; Mars - Uranus.

Ist es möglich, mit normalen Raketen von der Erde zum Mars zu fliegen?

Lösung: Zeichnen wir ein Diagramm der Bedingung: Wir stellen die Planeten als Punkte und die Raketenrouten als Linien dar.

Jetzt ist sofort klar, dass es unmöglich ist, von der Erde zum Mars zu fliegen.

Zwei durch einen Bogen oder eine Kante verbundene Scheitelpunkte werden als benachbart bezeichnet. Jeder Kante oder jedem Bogen ist eine Zahl zugeordnet. Die Zahl kann den Abstand zwischen Siedlungen, den Zeitpunkt des Übergangs von einem Gipfel zum anderen usw. angeben.

Aufgabe 2 (9 Folie) – Lösung an der Tafel. Mascha ist in den Zoo gekommen und möchte so viele Tiere wie möglich sehen. Welchen Weg soll sie einschlagen? Gelb, Rot, Grün?

Aufgabe 3 (11 Folie) – Lösung an der Tafel. Fünf Fußballmannschaften A, B, C, D, D müssen gegeneinander spielen. A mit B, C, D bereits gespielt; B mit A, C, D. Wie viele Spiele wurden bereits gespielt? Wie viel Zeit bleibt noch zum Spielen?

Präsentation von Grafiken (Folie 12)

Der Graph kann als Liste von Bögen (AB; 7), grafisch oder tabellarisch dargestellt werden.

Arc-Listen

Grafische Form

Tabellarische Form

(AB; 7),

	A	IN	MIT
A			3
IN			4
MIT	3	4

III. Verstärkungsmaterialien: Die Schüler werden gebeten, sich in Gruppen aufzuteilen und Aufgaben zu erledigen. In einer Kleingruppe diskutieren die Studierenden Modelle auf Basis der zu Beginn der Unterrichtsstunde erworbenen theoretischen Kenntnisse. Dies sorgt für Wiederholung und Festigung des Stoffes.

Aufgabe 2 (Folie 13)

IV. Zusammenfassung der Lektion

Leute, welche neuen Wörter habt ihr heute gelernt? (Graph, Scheitelpunkt des Graphen, Kanten des Graphen.)

Was können die Eckpunkte des Diagramms darstellen? (Städte; Objekte, die miteinander verbunden sind.)

Was bedeuten die Kanten des Diagramms (Wege, Bewegungen, Richtungen)

Geben Sie ein Beispiel dafür, wo im Leben wir sie treffen können?

Wie werden Diagramme dargestellt?

V. Hausaufgaben. (Folie 15)

Die Anzahl der Eckpunkte wird aufgerufen
Reihenfolge des Diagramms.
Die Anzahl der Kanten wird aufgerufen
die Größe des Diagramms.

Einige Begriffe-1

- Sei R=(a,b) eine der Kanten des Graphen. Dann
Die Scheitelpunkte a und b heißen Endscheitelpunkte
Scheitelpunkte der Rippe;
- Endscheitelpunkte derselben Kante
Nachbarn genannt;
- Zwei Kanten heißen benachbart, wenn sie vorhanden sind
gemeinsamer Endscheitel;
- Zwei Kanten heißen mehrere wenn
die Mengen ihrer Endscheitelpunkte fallen zusammen;
- Eine Kante heißt Schleife, wenn sie endet
zusammenpassen.

Einige Begriffe-2

- Der Grad eines Scheitelpunkts V wird mit deg(V) bezeichnet.
heißt die Anzahl der Kanten für
wovon dieser Scheitelpunkt der letzte ist;
- Ein Knoten heißt isoliert, wenn
Es ist für niemanden der Endpunkt
Rippen;
- Ein Scheitelpunkt wird als Blatt bezeichnet, wenn er
ist das Ende von genau einem
Rippen Für Blatt q ist offensichtlich deg(q)=1.

Beispiel:

Grad(C)=4
H1,…H4 – Blätter

Ein anderes Beispiel:

Städte B und D – isoliert
Oberteile; Die Städte G und E sind Blätter.

Vollständige Grafik

Ein Graph heißt vollständig, falls vorhanden
Zwei Eckpunkte sind durch eine Kante verbunden.
Wie viele Kanten hat ein vollständiger Graph?
Bestellnr.?
Ein vollständiger Graph der Ordnung n hat die Anzahl der Kanten
entspricht Cn2=n!/(2*(n-2)!) =n*(n-1)/2

Lasst es uns beweisen...

Vollständiger Graph mit zwei Eckpunkten
enthält eine Kante - das ist offensichtlich.
Setze n=2 in die Formel n*(n-1)/2 ein
Wir bekommen:
n*(n-1)/2=1
Die Formel ist korrekt, wenn n=2

Induktionshypothese

Nehmen wir an, dass die Formel gilt für
Diagramm mit k Eckpunkten.
Beweisen wir, dass dies impliziert
Gültigkeit der Formel für den Graphen
mit (k+1) Scheitelpunkt.

Fügen wir dem vollständigen Diagramm mit K Eckpunkten einen weiteren Eckpunkt hinzu.

Und verbinde es mit dem ersten K
Gipfel...

Wir bekommen:

Wir zählen, wie viele Rippchen wir haben...

K*(K-1)/2 + K
=
K*(K+1)/2
Der letzte Ausdruck stellt sich als heraus
wenn in der Formel n*(n-1)/2 statt n
Ersatz K+1.

Aus der Annahme der Fairness
Es folgen Aussagen für n=k
Gültigkeit der Aussage wann
n=k+1.
Der Satz ist bewiesen.

Beispiele für vollständige Diagramme

Wichtige Klarstellung

Die Paare, die Kanten in einem ungerichteten Graphen definieren, sind ungeordnet (d. h.
Paare (a,b) und (b,a) unterscheiden sich nicht)

Gerichteter Graph

Wenn es viele Kanten des Diagramms gibt
geordnete Paare (d. h. (a,b) ≠ (b,a)),
Dann heißt der Graph gerichtet
(oder Digraph)
Wie man dem Konzept Orientierung gibt
visuelle Bedeutung?
Ganz einfach – die Rippchen werden mitgeliefert
Pfeile (von Anfang bis Ende)!

Digraph-Beispiel

Gemischte Grafik

Ein gemischter Graph ist ein Tripel (V, E, A).
V – Satz von Eckpunkten;
E – Satz von unorientierten
Rippen;
A ist eine Menge orientierter Kanten.
Übrigens orientierte Kanten
werden Bögen genannt.

Graphisomorphismus

Es seien zwei Graphen G1 und G2 vorhanden
Wenn es eine Eins-zu-Eins-Korrespondenz F gibt
zwischen den Eckpunkten der Graphen G1 und G2, so dass:
- Wenn es eine Kante (a,b) im Graphen G1 gibt, dann gibt es auch eine Kante im Graphen G2
es gibt eine Kante (F(a),F(b))
- Wenn es eine Kante (p,q) im Graphen G2 gibt, dann gibt es auch eine Kante im Graphen G1
Es gibt eine Kante (F-1(p),F-1(q))
dann heißen die Graphen G1 und G2 isomorph und
Korrespondenz F ist ein Isomorphismus.

Klärung

Für Digraphen und gemischte Graphen
Compliance F muss erhalten bleiben
Ausrichtung der Bögen.

Notwendige Bedingungen für Isomorphismus

Unter welchen Bedingungen zwischen Elementen
zwei endliche Mengen
eins zu eins festlegen
Korrespondenz?
Dann und nur dann, ihre Nummer
Elemente sind gleich.
Eine notwendige Bedingung für Isomorphismus
die Anzahl der Graphen ist gleich
Gipfel

Ist diese Bedingung ausreichend?

Nein, denn die Spitzen können sein
anders verbunden.

Sind diese Graphen isomorph?

Die Anzahl der Eckpunkte ist gleich -
die notwendige Bedingung ist erfüllt...

Wir versuchen, eine Korrespondenz F zu konstruieren...

Dies ist kein Isomorphismus: G1 hat eine Kante (A,D),
und die Bilder dieser Kanten in G2 sind nicht zusammenhängend.

Noch ein Versuch...

Und das ist Isomorphismus!

Sind diese Graphen isomorph?

Leider nein…

Aus theoretischer Sicht zwei
isomorphe Graphen sind ein und dasselbe
das gleiche Objekt (nur vielleicht anders dargestellt...)

Pfade (Ketten):

Ein Pfad (Kette) ist eine Sequenz
Eckpunkte:
a1, a2, … , an
in denen benachbarte Eckpunkte ai und ai+1 sind
durch Rippen verbunden.
Die Länge eines Pfades ist die Anzahl seiner Komponenten
Rippen

Beispielpfade:

(A, D, C) und (A, B, D) sind Pfade. (A, B, C) ist nicht der Weg.

Das Konzept eines Pfades für einen Digraphen bleibt erhalten
Stärke, braucht aber Ergänzung -
benachbarte Gipfel in
Sequenzen
a1, a2, … , an
müssen durch Bögen verbunden sein.

Fahrräder

Ein Zyklus ist ein Pfad mit einem Anfangs- und einem Anfangspunkt
der letzte Scheitelpunkt fällt zusammen.
Die Länge eines Zyklus ist die Anzahl seiner Komponenten
Rippen
Ein Kreis heißt einfach, wenn die Kanten darin vorhanden sind
werden nicht wiederholt.
Ein Zyklus heißt elementar, wenn er
einfach und die Eckpunkte werden darin nicht wiederholt.

Konnektivitätskomponenten

Die Eckpunkte eines beliebigen Graphen können sein
in Klassen unterteilt, so dass für
zwei beliebige Knoten derselben Klasse v1
und v2 gibt es einen Pfad von v1 nach v2
Diese Klassen werden Komponenten genannt
Konnektivität.
Wenn der Graph genau eine Komponente hat
Zusammenhang, dann heißt der Graph
kohärent.

Maschinelle Darstellung von Diagrammen.

Adjazenzmatrix

- Nummerieren wir die Eckpunkte des Graphen G
aufeinanderfolgende ganze Zahlen von 1 bis n;
- Lasst uns eine quadratische n×n-Tabelle erstellen und
fülle es mit Nullen;
- Wenn es eine Kantenverbindung gibt
Eckpunkte i und j, dann in den Positionen (i,j) und (j,i)
wir liefern Einheiten;
- Die resultierende Tabelle wird aufgerufen
Adjazenzmatrix des Graphen G.

Beispiel

Einige offensichtliche Eigenschaften der Adjazenzmatrix

- Wenn ein Scheitelpunkt isoliert ist, dann sind seine Reihe und
die Spalte wird vollständig Null sein;
- Anzahl der Einheiten in einer Zeile (Spalte)
gleich dem entsprechenden Abschluss
Oberteile;
- Für eine ungerichtete Graphmatrix
Nachbarschaft ist symmetrisch in Bezug auf
Hauptdiagonale;
- Eine Schleife entspricht einer darauf stehenden Einheit
Hauptdiagonale.

Verallgemeinerung für Digraph

Adjazenzmatrix für einen Digraphen
kann auf ähnliche Weise aufgebaut werden
Art und Weise, sondern die Reihenfolge zu berücksichtigen
Scheitelpunkte, Sie können dies tun:
Wenn der Bogen am Scheitelpunkt j und beginnt
tritt in Scheitelpunkt k ein, dann an Position (j,k)
Adjazenzmatrizen sollten auf 1 und in gesetzt werden
Position (k,j) set -1.

Inzidenzmatrix

- Nummerieren wir die Eckpunkte des Graphen G
aufeinanderfolgende ganze Zahlen von 1 bis
N;
- Lass uns einen rechteckigen Tisch bauen mit
n Zeilen und m Spalten (Spalten).
entsprechen den Kanten des Diagramms);
- Wenn die j-te Kante einen Anschluss hat
der Scheitelpunkt ist Scheitelpunkt k, dann in Position
(k,j) wird auf eins gesetzt. Insgesamt
in anderen Fällen wird es auf Null gesetzt.

Inzidenzmatrix für einen Digraphen

- Wenn der j-te Bogen vom Scheitelpunkt k kommt,
dann wird 1 an Position (k,j) platziert;
- Wenn der j-te Bogen in den Scheitelpunkt k eintritt, dann
-1 wird an Position (k,j) platziert.
- In anderen Fällen in Position (k,j)
bleibt Null.

Da die Matrixspalten
Inzidenz beschreibt also die Rippen
Jede Spalte darf nicht enthalten
mehr als zwei Nicht-Null-Elemente

Beispiel einer Inzidenzmatrix

Liste der Kanten

Eine andere Möglichkeit, ein Diagramm darzustellen
– zweidimensionales Array (Liste von Paaren).
Die Anzahl der Paare ist gleich der Anzahl der Kanten
(oder Bögen).

Beispiel für eine Kantenliste

Vergleich verschiedener Präsentationsmethoden

- Die Liste der Kanten ist am kompaktesten und
Inzidenzmatrix am wenigsten
kompakt;
- Die Inzidenzmatrix ist praktisch, wenn
Suche nach Zyklen;
- Die Adjazenzmatrix ist einfacher
der Rest im Einsatz.

Graphdurchquerung

Das Durchlaufen eines Graphen wird als Aufzählung bezeichnet
Scheitelpunkte, so dass jeder Scheitelpunkt
einmal angeschaut.

Vereinbarung-1

Bevor Sie eine Suche in einem Diagramm durchführen
Mit n Eckpunkten erstellen wir ein Array Chk
von n Elementen und fülle es
Nullen.
Wenn Chk[i] = 0, dann ist der i-te Scheitelpunkt still
nicht angesehen.

Vereinbarung-2

Lassen Sie uns eine Datenstruktur erstellen
(Speicherung), in der wir werden
Merken Sie sich dabei die Eckpunkte
Bypass. Speicherschnittstelle
sollte drei Funktionen bieten:
- Bringen Sie die Oberseite ein;
- Extrahieren Sie den Scheitelpunkt.
- Überprüfen Sie, ob der Speicher leer ist;

Vereinbarung-3

Wenn Scheitelpunkt j platziert wird
Lagerung, es ist markiert als
angesehen (d. h. installiert) werden
Chk[j]=1)

Bypass-Algorithmus-1

1) Nehmen Sie einen beliebigen Anfangsscheitelpunkt,
wir drucken es aus und lagern es ein;

3) Nehmen Sie den Scheitelpunkt Z aus dem Speicher.
4) Wenn es einen Scheitelpunkt Q gibt, der mit Z verbunden ist und nicht
markiert, dann Z in den Speicher zurückgeben,
Q einlagern, Q drucken;
5) Gehen Sie zu Schritt 2

Bypass-Algorithmus-2

1) Nehmen Sie einen beliebigen Anfangsscheitelpunkt und
wir lagern es ein;
2) Ist der Speicher leer? Wenn JA – es ist vorbei;
3) Nehmen Sie den Scheitelpunkt Z aus dem Speicher, drucken Sie ihn aus und
aus dem Speicher löschen;
4) Wir platzieren alle Eckpunkte im Speicher,
Z-bezogen und noch nicht vermerkt;
5) Gehen Sie zu Schritt 2

Welche Datenstrukturen eignen sich als Speicher?

- Stapel (PUSH – hinzufügen; POP – entfernen)
- Warteschlange (ENQUE – eingeben; DEQUE –
Extrakt)
Beide Strukturen ermöglichen eine Überprüfung
Verfügbarkeit von Daten.

Algorithmus-1 in Kombination mit einem Stack
Dies wird Tiefendurchquerung genannt
Algorithmus-2 in Kombination mit einer Warteschlange
Dies wird Breiten-erste-Durchquerung genannt

Korobova Anastasia, Schülerin Gr. 14-PGS-48D

Heutzutage ist es wichtig, verschiedene Methoden, Eigenschaften und nicht standardmäßige Anwendungen zu untersuchen. Wir werden die Anwendung der Graph-Methode in der Realität um uns herum betrachten.

Das Wort „Graph“ bedeutet in der Mathematik ein Bild mit mehreren gezeichneten Punkten, von denen einige durch Linien verbunden sind. Zunächst ist festzuhalten, dass die Grafen, die besprochen werden, nichts mit den Aristokraten vergangener Zeiten zu tun haben. Unsere „Graphen“ haben ihren Ursprung im griechischen Wort „grapho“, was „ich schreibe“ bedeutet. Die gleiche Wurzel liegt in den Wörtern „Grafik“, „Biografie“.

Das erste Werk zur Graphentheorie gehört Leonhard Euler und erschien 1736 in den Veröffentlichungen der St. Petersburger Akademie der Wissenschaften.

Anzahl festgestellt:

in der Physik - beim Aufbau elektrischer Schaltkreise

in Chemie und Biologie - beim Studium der Moleküle ihrer Ketten

in der Geschichte – bei der Erstellung von Stammbäumen (Ahnentafeln)

in der Geographie - beim Zeichnen von Karten

in der Geometrie - Zeichnungen von Polygonen, Polyedern, räumlichen Figuren

in den Wirtschaftswissenschaften – bei der Lösung von Problemen bei der Wahl des optimalen Weges für Güterverkehrsströme (Fluglinien, U-Bahnen, Eisenbahnsysteme)

Die Graphentheorie wird zur Lösung von Problemen in mathematischen Olympiaden eingesetzt. Diagramme verdeutlichen die Bedingungen des Problems, vereinfachen die Lösung und offenbaren die Ähnlichkeit der Probleme.

Heutzutage stößt man in jedem Bereich der Wissenschaft und Technologie auf Grafiken.

Herunterladen:

Vorschau:

Um Präsentationsvorschauen zu nutzen, erstellen Sie ein Google-Konto und melden Sie sich an: https://accounts.google.com

Folienunterschriften:

Präsentation zum Thema Mathematik: „Graphen“ Abgeschlossen von der Schülerin der Gruppe 14-PGS-48D Anastasia Korobova

Ein Graph ist eine Figur, die aus Punkten und Linien besteht, die diese Punkte verbinden. Die Linien werden Kanten des Diagramms genannt, und die Punkte werden Eckpunkte genannt. Eckpunkte, aus denen eine gerade Anzahl von Kanten hervorgeht, heißen gerade, und eine ungerade Anzahl heißt ungerade. Graphenbeispiele Graphentheorie

Leonhard Euler (4. April 1707, Basel, Schweiz – 7. September 1783, St. Petersburg, Russisches Reich) war ein Schweizer, deutscher und russischer Mathematiker, der bedeutende Beiträge zur Entwicklung der Mathematik sowie der Mechanik, Physik und Astronomie leistete und eine Reihe von angewandten Wissenschaften. Euler ist Autor von mehr als 800 Werken zu mathematischer Analyse, Differentialgeometrie, Zahlentheorie, Näherungsrechnungen, Himmelsmechanik, mathematischer Physik, Optik, Ballistik, Schiffbau, Musiktheorie usw.

Eine Figur (Grafik), die gezeichnet werden kann, ohne den Bleistift vom Papier abzuheben, wird Unicursal genannt. Muster 1. Ein Diagramm mit nur zwei ungeraden Eckpunkten kann gezeichnet werden, ohne den Bleistift vom Papier zu nehmen, und die Bewegung muss an einem dieser ungeraden Eckpunkte beginnen und am zweiten enden. (Abb. A) Muster 2. Ein Graph mit mehr als zwei ungeraden Eckpunkten kann nicht mit „einem Strich“ gezeichnet werden (Abb. B) Euler-Graphen B A

Muster 3. Wenn alle Eckpunkte eines Diagramms gerade sind, können Sie dieses Diagramm zeichnen, ohne den Bleistift vom Papier abzuheben, indem Sie jede Kante nur einmal nachzeichnen. Die Bewegung kann an jedem beliebigen Scheitelpunkt beginnen und am selben Scheitelpunkt enden.

Dies ist ein Diagramm, in dem einige Kanten gerichtet und einige Kanten ungerichtet sein können. Gemischte Grafik

Gewichtetes Diagramm 1 2 4 2 3 A B C D E

Ein Baum ist ein beliebiger zusammenhängender Graph, der keine Zyklen hat. Bäume Bäume

Dabei handelt es sich um einen (Multi-)Graphen, dessen Kanten eine Richtung zugeordnet ist. Gerichtete Kanten werden auch Bögen genannt. Gerichteter Graph

Anzahl festgestellt:

Vielen Dank für Ihre Aufmerksamkeit!