Schimbă limba

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

Conectați-vă la Mathigon

sau

Cont nou     Reseteaza parola     

Grafice și rețele
Introducere
Podurile din Königsberg
Strângeri de mână și întâlniri
Graficele planare
Harta de colorat
Problema vânzătorului călător
Programarea problemelor
Grafice în viața de zi cu zi

Acțiune

Resetați Progresul

Acest lucru vă va șterge progresul și datele de chat pentru toate capitolele din acest curs și nu poate fi anulat!

Glosar

Selectați unul dintre cuvintele cheie din stânga ...

Grafice și rețelePodurile din Königsberg

Timp de citit: ~20 min

Unul dintre primii matematicieni care s-a gândit la grafice și rețele a fost Leonhard Euler . Euler a fost intrigat de o veche problemă cu privire la orașul Königsberg, lângă Marea Baltică.

Râul Pregel împarte Königsberg în patru părți separate, care sunt conectate de șapte poduri. Este posibil să vă plimbați prin oraș care traversează toate podurile exact o dată - dar nu mai mult de o dată? (Puteți începe și termina oriunde, nu neapărat în același loc.)

Încercați să găsiți un traseu valid desenând pe aceste hărți:

Map 1

Map 2

Map 3

Map 4

În cazul Königsberg se pare că este imposibil să se găsească o rută validă, dar unele dintre celelalte orașe funcționează. Euler a reușit să găsească o regulă simplă care să poată fi aplicată oricărui oraș, fără a fi nevoie să încerci o mulțime de posibilități - folosind teoria graficului.

În primul rând, trebuie să convertim hărțile orașului în grafice cu margini și vertexuri. Fiecare insulă sau regiune de pământ este reprezentată de și fiecare pod care leagă două regiuni este reprezentat de o corespunzătoare .

Acum, problema „turului unui oraș în timp ce traversați fiecare pod exact o dată” a devenit o problemă a „desenării unui grafic cu o cursă continuă în timp ce urmărim fiecare muchie exact o dată”.

Pe hârtie, apăsați cu câteva grafice diferite și apoi încercați să aflați care pot fi desenate cu un singur accident continuu.

La fel ca și pentru hărțile orașului de dinainte, descoperim că unele grafice sunt posibile în timp ce altele nu. Pentru a ne ajuta să înțelegem de ce, să etichetăm fiecare vertex cu gradul său. Apoi putem colora vârfurile în moduri diferite și vom încerca să dezvăluim un model:

Value
Size
Prime Numbers
Even and Odd

These graphs are possible:

2 4 3 3 4 4 2 2 4 4 2 2 2 4 4 2 2 2 4 4 2 4 4 8 2 2 4 4 4 4 2

These graphs are not possible:

2 3 2 3 4 3 2 3 2 2 2 2 2 3 5 3 3 5 3 3 6 3 3 3 3 3

Comparând aceste numere pentru grafice care sunt posibile și cele care nu sunt posibile, se pare că un grafic poate fi desenat dacă nu . Această condiție poate fi explicată dacă ne uităm la un singur vertex în grafic:

Here you can see a single, magnified vertex in a graph.
If we draw the graph, we will eventually have an edge leading towards this vertex, and then another one leading away. This makes two edges meeting at the vertex.
Maybe the vertex is a crossing rather than a corner. In that case there will be another edge leading towards the vertex, and another edge leading away. Now we have four edges.
And in some graphs, there may even be a third pair of edges leading towards and away from the vertex. Now there are six edges.
Notice that, either way, there always is an even number of edges meeting at the vertex.
The only two exceptions are the vertices where the path starts, and where it ends – these two may have an odd number of edges. If the start and end point are the same, all vertices in the graph are even.

Dacă derulați înapoi la harta Königsberg, veți vedea că există mai mult de două insule cu un număr impar de poduri. Prin urmare, un traseu care traversează fiecare pod exact o dată este într-adevăr imposibil - și asta a descoperit Leonard Euler.

Descoperirea lui Euler nu poate părea deosebit de utilă în viața reală, dar graficele sunt la baza multor alte probleme geografice, cum ar fi găsirea direcțiilor între două locații. Mai multe dintre aceste aplicații vom descoperi mai târziu.

Archie