Grafik Teorisi nedir ve böyle bir grafik nasıl tanımlanır?

1736'da, İsviçreli fizikçi-matematikçi Leonhard Euler'in (1707-1783) çalışmasına dayanarak, bir dizi köşenin tanımladığı gözlemlendi. bir yol, ancak, söz konusu yol, kenarları tekrar etmeyen farklı köşelerden oluşuyorsa, buna yol veya yol denir. eulerian; ek olarak, her bir kenarı yalnızca bir kez geçerek başlangıç ​​noktasına ulaşırsak, o zaman bir Euler döngüsüne (devre) sahip oluruz.

Teklif (APA)

alexander barraza | Temmuz. 2022
fizik derecesi

Bir grafiği sıralı bir çift olarak tanımlarız. (GİTMEK) nerede v bir grafiğin tüm köşelerinin veya düğümlerinin (boş olmayan) kümesini belirtirken A bir grafiğin köşelerini birleştiren tüm kenarların veya çizgilerin kümesini (boş olabilir) belirtir. Kümenin elemanları A v ve w'nin öğeleri (düğümler veya köşeler) olduğu sırasız bir {v, w} çifti olarak belirlenebilir. v, bu şekilde v ve w'nin bitişik köşeler olduğu söylenir (bir kenarla birleştirilirler).

Grafik teorisi, Euler'in yedi köprüyü nasıl geçeceğini merak eden popüler bir yaratıcılık sorununa verdiği yanıttan doğar. Königsberg topluluğunun iki adasına (o zamanlar Almanya'nın bir parçası ve şu anda Rusya'da Kaliningrad, Rusya'da), aralarında ve anakara ile iki ada kullanmadan katıldı. kez aynı köprüyü geçerek ve başlangıç ​​noktasına (anakarada bulunan) ne olursa olsun vararak, bu durumda nihai olarak hiçbir abilir.

Königsberg'in yedi köprüsü sorunu

Euler, Königsberg'i her noktanın (köşe veya düğüm) bir köprüyü ve her çizginin (kenarın) karada bir yolu temsil ettiği bir grafik olarak modelledi:

Bu sorunun çözümü nedir?

bir tane yok çözüm dayatılan koşulları karşılayan, çünkü Euler'in gösterdiği gibi, köşeler eşit derecede değildir, yani çift sayıda çizgi her noktayı etkilemez. _[3]. Bu kadar basit tanımlanmış bir yapıyla pek bir şey yapamayız gibi görünüyor, ancak çoğu zaman olduğu gibi matematik, Bazen işler göründüğü gibi değildir. Böylece, en üretken, çapraz ve disiplinler arası alanlardan biri _[4] insan bilgisi, grafik teorisi.

Euler grafikleri mi yoksa Euler yörüngesi mi?

Aşağıdaki grafiklerin hepsinde Euler yolları vardır. _[5]. Hepsinde Euler döngüsü var mı?

Üçüncü grafiği ele alalım:

Köşeleri numaralandıralım:

O zaman {3,4,6,2,1,3,7,6,5,4,2} dizisiyle tanımlanan yolun bir Euler yolu olduğunu görürüz, çünkü tüm grafiği kenarları tekrar etmeden geçer, ancak başlangıç ​​noktasına ulaşmadığı için bir Euler döngüsü değildir. Köşeleri farklı şekilde numaralandırsaydık ne olurdu? Çok fazla değil, bunun dışında şimdi yol farklı bir ardıllıkla tanımlanacaktı. İlk çözümümüzde önerilenden farklı yollar izleseydik ne olurdu? Bu soruyu yanıtlamak biraz daha karmaşıktır ve yazılım mühendislerinin genellikle memnun olduğu algoritmaları içerir. programlama.

Burada açığa çıkanın daha kesin bir kanıtı için aşağıdaki sonuca başvurmamız gerekiyor:

"olmak G bağlantılı bir grafik _[6]. O zaman evet G sahip olmak devre Euler, her bir köşenin derecesi çift iken, eğer G bir Euler yoluna sahip, G'nin tam olarak iki tek dereceli köşesi var _[7] (tam olarak yolun başladığı ve bittiği köşeler)".

Daha sonra, aslında aldığımız grafikte sadece 3 ve 6 köşelerinin tek dereceli olduğunu doğrulayabiliriz (bu köşelerin numaralandırılması farklı olsaydı bile meydana gelirdi), bu nedenle söz konusu grafiğin bir yolu vardır. eulerian _[8]. Kalan grafikler için benzer bir şekilde ilerleyebilir ve gerçekten de yolları olup olmadığını doğrulayabiliriz. Euler döngüleri veya başka bir deyişle, bu tür grafikleri kalemi alıp tekrar etmeden çizebilir miyiz? çizgiler? Bu sorunun cevabı şimdiye kadar anlatılanlardan çıkarılabilir, ancak bu bir alıştırmadır. ince motor beceriler, yaratıcılık ve sabır açısından ilginç, okuyucuyu 6 veya daha fazla grafik bulup çizmeye davet ediyorum ile köşeler Yörünge Eulerian.

Başka grafik türleri var mı? Grafik teorisinin 'gerçek' dünyada uygulamaları var mı?

Çok kısaca gözden geçirdiğimiz bu grafikler, grafik teorisinde bulduğumuz birçok grafik türünden sadece biridir. Ağaçlar gibi, öğelerinin hiyerarşiler halinde sınıflandırılabileceği kümelerde ve sayma hesaplamalarında çok temsili grafikler de bulabiliriz. olasılık_[9], digraflar, Hamilton grafikleri _[10], vb.

Psycho.'da Grafik Modeller ve Ağların Görüntüsü, Ruiz, Ana María.

Bu bilmeceler, eğer onlara böyle demek istersek, günümüz dünyasında, aşağıdakiler gibi çeşitli durumlarda muazzam bir uygulanabilirliğe sahiptir: Biyoloji moleküler _[11], bilgi işlem_[12], telekomünikasyon _[13] ve ağ analizi _[14]. O zaman sormaya değer: En azından neredeyse banal matematiğin en ilginç ve göze çarpan sonuçlarından biri mi olacak? Belki de bunun için insanlığın en ünlü beyinlerinden birinin katkısı gerekliydi.