Qrafiklər və ŞəbəkələrKönigsberg körpüləri

Qrafiklər və şəbəkələr haqqında düşünən ilk riyaziyyatçılardan biri Leonhard Euler idi . Euler, Baltik dənizi yaxınlığındakı Königsberg qəsəbəsi ilə bağlı köhnə bir problemlə maraqlandı.

Pregel çayı Königsberg'i yeddi körpü ilə bağlanan dörd ayrı hissəyə ayırır. Bütün körpülərin hamısını bir dəfə - ancaq bir dəfədən çox keçməyən şəhərin ətrafında gəzmək mümkündürmü? (Hər yerdə başlaya və bitirə bilərsən, mütləq eyni yerdə deyil.)

Bu xəritələrdə rəsm çəkərək etibarlı bir yol tapmağa çalışın:

Map 1

Map 2

Map 3

Map 4

Königsberg vəziyyətində etibarlı bir marşrut tapmaq mümkün olmur, ancaq digər şəhərlərdən bəziləri işləyir. Euler, çox sayda fürsət sınamadan - hər hansı bir şəhərə tətbiq oluna biləcək sadə bir qayda - grafik nəzəriyyəsini istifadə edərək tapmağı bacardı.

Əvvəlcə şəhər xəritələrini kənarları və ucları olan qrafiklərə çevirməliyik. Hər ada və ya torpaq sahəsi ilə təmsil olunur və iki bölgəni birləşdirən hər körpü uyğun bir təmsil olunur .

İndi "hər körpünü bir dəfə keçərkən bir şəhər gəzmək" problemi "hər kənarı tam bir dəfə izləyərkən bir fasiləsiz vuruşla bir qrafik çəkmək" probleminə çevrildi.

Kağızda bir neçə fərqli qrafik hazırlayın və sonra hansının tək, davamlı vuruşla çəkilə biləcəyini çalışın.

Əvvəllər şəhər xəritələrində olduğu kimi, digərlərində olmadıqda bəzi qrafiklərin mümkün olduğunu görürük. Bunun səbəbini anlamağımızı təmin etmək üçün gəlin hər bir ucu öz dərəcəsi ilə etiketləyin. Sonra ucları müxtəlif yollarla rəngləyə bilərik və bir nümunə ortaya qoymağa çalışırıq:

Value

Size

Prime Numbers

Even and Odd

These graphs are possible:

These graphs are not possible:

Mümkün olan və mümkün olmayan qrafiklər üçün bu rəqəmləri müqayisə edərək görünür ki, bir qraf tərtib edilə bilər . Bu şərt qrafikdə yalnız bir dikliyə baxsaq izah edilə bilər:

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.

Königsberg-in xəritəsinə dönsəniz, tək sayda körpü olan ikidən çox adanın olduğunu görərsiniz. Buna görə hər körpünü tam bir dəfə keçən bir yol həqiqətən mümkün deyil - Leonard Euler'in kəşf etdiyi budur.

Euler-in kəşfi real həyatda xüsusilə faydalı görünə bilməz, lakin qrafiklər iki yer arasında istiqamət tapmaq kimi bir çox digər coğrafi problemlərin əsasını təşkil edir. Bu tətbiqlərdən daha sonra kəşf edəcəyik.

Mathigon-a daxil olun

Paylaşın

Bizə rəy göndərin

Geribildiriminiz üçün təşəkkür edirik!

Giriş Ayarları

Tərəqqi sıfırlayın

Lüğət

Qrafiklər və ŞəbəkələrKönigsberg körpüləri

Map 1

Map 2

Map 3

Map 4

Dili dəyişdirin