ev Kullanışlı Graf teorisinin ortaya çıkışı ve gelişiminin tarihi. Grafik Teorisi: Temel Kavramlar ve Görevler

Graf teorisinin ortaya çıkışı ve gelişiminin tarihi. Grafik Teorisi: Temel Kavramlar ve Görevler

Grafikler teorisinin ortaya çıkış tarihi ve gelişimi 1736, Leonard Euler, bir zamanlar Königsberg köprüleri sorunu mu?) o 19. yüzyılın ortalarında. , G. Kirchhoff elektrik devrelerinin grafikler kullanarak açıklaması, A. Cayley kimyasal devreler o Matematik disiplini 30'ların ortalarında nasıl oluştu. 20. yüzyıl (1936, yayın o

Grafik teorisinin uygulama alanları ooo Elektrik ve diğer devrelerin ve sistemlerin analizi ve sentezi, ağ planlaması ve kontrolü, yöneylem araştırması, ağlarda optimal yolların ve akışların seçimi, organizmaların hayati aktivitesinin modellenmesi, rastgele süreçlerin incelenmesi, vb. Çözümü, nesnelerin toplanması ve aralarındaki ilişkilerin dikkate alınmasına indirgenen pratik problemler. Örneğin, bir yol haritası - yerleşim yerleri, insanlar, olaylar, durumlar ve genel olarak herhangi bir nesne arasındaki çeşitli bağlantılar ve ilişkiler arasında bir bağlantı olarak Çok sayıda bulmaca ve oyun

o Kesintisiz veya satırları tekrarlamadan belirli bir şekil çizmenizi gerektiren bulmacalar veya örneğin Mahomet's Saber

Temel tanımlar o o o Grafik, sonlu sayıda nokta ve bazı noktaları birbirine bağlayan doğruların birleşimidir. Noktalara grafiğin köşeleri, bunları birleştiren çizgilere kenar denir.Bir köşeden çıkan kenarların sayısına bu köşenin derecesi denir.

Grafik örnekleri o o Uzaydaki herhangi bir çokyüzlülüğün çerçevesi Metrodaki çizgilerin şeması Yapısal formüller moleküller soy ağacı

Grafikler yardımıyla çözülen görev örnekleri 1. Gezginler o Turizm ofisi, A şehrinden B şehrine seyahat etmek isteyen gezginler için C, D, E, F, G şehirlerinde bulunan tüm turistik yerleri ziyaret eden bir rota çizer. Yol boyunca H, K, M. Turistlerin belirtilen tüm şehirleri ziyaret etmesi ve her birini tam olarak bir kez ziyaret etmesi için bir gezi rotası yapmanız gerekir.

o Sorunun durumuna göre yolculuk A noktasında başlamalı ve B noktasında bitmelidir. D ve F şehirlerine giden sadece iki yol olduğunu unutmayın. Bu yüzden yolcular mutlaka bu yollardan geçecektir. Onları kalın çizgilerle işaretleyelim. Bu, rota segmenti CDEFG'yi tanımlar. Bu, turistlerin AE, AG, EM yollarından geçmeyecekleri anlamına gelir (aksi takdirde E noktasını iki kez ziyaret edeceklerdir). Bu yolları geçelim. A'dan sadece bu yol kaldığından, AC bölümünü kalın bir çizgiyle işaretleyelim. CM'yi geçelim (zaten C'ye gittik). M: MH ve MB üzerinden iki yol geçmedi, bu da turistlerin onlardan geçeceği anlamına geliyor. Onları kalın çizgilerle işaretleyelim. Geriye kalan tek yol G'den H'ye gitmek

o Böylece doğru rotayı bulduk. Bunda, aslında 10 köşesi ve 17 kenarı olan bir grafik olan şehirlerin ve yolların düzeni bize yardımcı oldu. A, D, F köşeleri ikinci dereceden, C ve K köşeleri üçüncü dereceden, H, M, B köşeleri dördüncü dereceden ve G ve E beşinci derecedendir.

2. Tanıdıklar o 8 kişilik bir şirkette herkes tam olarak iki kişiyi tanıyor olabilir mi?

2. Tanıdıklar (karar) o o Grafiğin köşelerini şirket üyeleriyle karşılaştıralım, karşılık gelen iki kişi birbirini tanıyorsa iki köşeyi bir kenarla birleştirelim. Herkesin iki kişiyi tam olarak tanıması için, grafiğin herhangi bir köşesinin derecesi 2 olmalıdır. Bu tür grafiklere örnekler: Bu tür grafikler mevcut olduğundan, problemde açıklanan durum mümkündür.

3. Satranç Turnuvası o Turnuvaya n satranç oyuncusu katılsın, hepsi birbiriyle tam olarak bir oyun oynamalıdır. Her katılımcıyı grafiğin bir tepe noktasıyla ilişkilendirin ve her bir oyun, karşılık gelen köşeleri birleştiren grafiğin bir kenarıyla oynayın

Tam grafik o o o Turnuva başlamadan önce, grafik sadece noktalardan oluşur, kenarları yoktur. Bu tür grafiklere boş grafikler denir.Turnuvanın sonunda, her katılımcı diğeriyle oynadı ve her bir köşe çifti bir kenar ile birbirine bağlanır. Böyle bir grafiğe tam denir. n köşeli tam bir grafikte, her bir köşenin derecesi (n-1)'dir. Eksik kenarlar eklenerek tamamlanmamış bir grafik tamamlanabilir. Şek. kalın çizgi, tamamlanmamış 5 köşeli bir grafiği gösterir. Toplayarak

Yönlendirilmiş grafik ooo Genellikle nesneler arasındaki bağlantılar belirli bir yönelim ile karakterize edilir (tek yönlü trafiğe sahip yolların şeması, insanlar arasındaki ilişkilerde tahakkuk veya kıdem, spor yarışmalarında takımlar arasındaki toplantıların sonuçları). tarafımızdan gösterilenler, her oyunu kimin kazandığı hakkında bilgi sağlamaz. Satranç oyuncusu A, satranç oyuncusu B'ye kaybettiyse, yani kenarları onlara yönü belirterek yönlendirirse, A noktasından B noktasına kadar her kenara bir ok koyabilirsiniz.Her kenarın yönünün gösterildiği grafiğe denir.

o Hem yönlendirilmiş hem de yönlendirilmemiş kenarları içeren bir grafiğe karışık denir (örneğin, bazı oyunların berabere bittiği bir satranç turnuvasının grafiği. Oksuz bir kenarı beraberlik sonucuyla karşılaştırırız)

Bir grafiğin yolu o o o Rastgele bir grafikteki m uzunluğundaki bir yol, iki komşu kenarın sınır köşelerinin çakıştığı (mutlaka farklı olmak zorunda olmayan) bir m kenar dizisidir. Rotanın uzunluğu, kenarların sayısıdır (kenar boyunca 2 kez geçersek, bu kenarı 2 kez sayarız) Rota, ilk ve son köşeleri aynıysa kapalıdır Zincir - tüm kenarların olduğu açık bir rota farklı Basit zincir - tüm köşelerin farklı olduğu bir zincir (örnek - görev 1. (Yolcular hakkında)

Döngüler, bağlantılı grafikler o o o Döngü, tüm kenarların farklı olduğu kapalı bir yoldur. Basit bir döngü, tüm köşelerin farklı olduğu bir döngüdür (bir örnek, bir tarihleme problemidir. İlk grafik bir basit döngü içerir, ikinci ve üçüncü her biri iki basit döngü içerir) Herhangi bir noktadan bir rota varsa, bir grafiğe bağlı denir. köşelerinden herhangi birine ve aksi takdirde bağlantısız (bir örnek, bir randevu problemidir, ilk grafik bağlantılıdır, her kişi geri kalanını arkadaşları aracılığıyla öğrenebilir, ikinci ve üçüncü bağlantı kopuk, yabancılar şirkette kalacak)

o o o o B-D-A-C-D-A - açık rota A-C-D-A-B-D-A- kapalı rota A-C-D-E-F-D-B - devre A-B-G-H - basit devre A-C-D-E-F-D-A - döngü D-E-F-D– basit döngü Bu rotaların uzunluğunu hesaplayın Ne tür rotaların A-B-D-F-E-D-C-A olduğunu belirleyin; A-D-E; D-E-F-D; A-C-D-B-A;

Ağaçlar o o Ağaç, soy ağacı, dosya sistemi vb. döngüleri olmayan bağlantılı bir grafiktir.

Görev 4. Parçalara ayırma o Bir kağıdı 3 parçaya kesin. Elde edilen yaprakların bir kısmı yine 3 parçaya kesilir. Kesilen yapraklardan bazıları - yine üç parçaya, vb. k kesim yapılırsa kaç ayrı yaprak elde edilir?

Görev 4. Bölümleme (çözüm) o o Kağıt grafik üst sayfaları. Doldurulmuş köşeler, kesilmiş yapraklara karşılık gelir, doldurulmamış olanlar kesilmemiş olanlara karşılık gelir. Bir yaprak kesildiğinde yaprak sayısı 2 artar. Toplamda k yaprak kesilirse yaprak sayısı 2k artar. Başlangıçta, bir sayfamız vardı. , yani k kesimden sonra (2 k+1) yaprak elde edersiniz. Grafik, k=6 olduğu durumu göstermektedir. (2k+1)=13

Bir grafiğin köşelerinin derecelerinin toplamına ilişkin teorem o o Grafiğin Г N köşesi ve M kenarı olsun. Her i-inci köşenin di derecesi vardır. Her kenar iki köşeyi birbirine bağladığından, grafiğin köşelerinin derecelerinin toplamına iki ekler, yani köşelerin derecelerinin toplamı, kenarların sayısının iki katına eşittir.

Problem 5. Yol sayısı o Her bir şehirden tam olarak 3 yolun ayrıldığı bir eyalette tam olarak 100 yol olabilir mi?

Görev 5. Yol sayısı (çözüm) o Böyle bir durumun mümkün olduğunu varsayalım. Eyalette N tane şehir var, her şehirden 3 yol çıkıyor. Böylece, her biri derece 3 olan N köşeli bir grafiğimiz var. Bu nedenle, köşelerin derecelerinin toplamı 3 N ve kenarların sayısı 3 N/2'dir. Bu sayı koşullu olarak 100'e eşittir. Yani, 3 N / 2 \u003d 100 veya 3 N \u003d 200. Böyle bir doğal sayı yoktur. Bu, bu devletin 100 yola sahip olamayacağı anlamına gelir.

Bağımsız olarak o Belirli bir krallıkta kral bir kararname çıkardı: 7 şehir inşa et ve her şehirden 3 yol çıkacak şekilde onları yollara bağla. Bu sırayı takip edecek miyiz? Her şehirden 4 yol ayrılıyorsa bu mümkün olacak mı?

Problem 6. Koenigsberg köprüleri hakkında o Koenigsberg şehri, Pregel Nehri'nin kıyısında, 7 köprünün bulunduğu şehirde yer almaktadır. Her köprüden sadece bir kez geçerek evden çıkmak ve tekrar geri dönmek için yürüyüş yapmak mümkün mü?

Koenigsberg köprüleri problemini çözme o o o Şehrin A, B, C, D kısımlarını belirtin. Bunlar grafiğin köşeleri olacaktır. Şehrin bölümlerini birbirine bağlayan köprüler - grafiğin kenarları. Euler, sorunun çözümü olmadığını, yani tüm kenarlardan tam olarak bir kez geçen bir döngü olmadığını gösterdi. Gerçekten de, böyle bir döngü mevcut olsaydı, o zaman grafiğin her köşesinde ona giren ve onu terk eden kadar çok kenar olurdu, yani grafiğin her bir köşesinde çift sayıda kenar olurdu (tepe noktasına birer birer giren kenar, ondan başka bir kenar boyunca çıkmalıyız). Ancak bu koşul, Königsberg haritasını temsil eden grafik için açıkça sağlanmamaktadır. Grafiğin her bir köşesinin derecesini belirleyerek bunu doğrulayın.

Euler Grafiği o o Königsberg köprü probleminin çözümünün ana hatlarını çizen Euler, çalışmasında aşağıdaki genel çizge teorisi problemine döndü: grafiğin tüm kenarlarını içeren bir döngü, her bir kenarı tam olarak bir kez olmak üzere hangi grafiklerde bulunabilir? Böyle bir döngüye Euler çizgisi veya Euler döngüsü denir ve Euler çizgisine sahip bir grafiğe Euler grafiği denir. Böylece, Euler grafiği, her bir kenar üzerinden yalnızca bir kez geçerek tamamen geçilebilir. Bu nedenle, kalemi kağıttan kaldırmadan ve aynı çizgiyi iki kez çizmeden Euler grafikleri oluşturulabilir.

Euler grafiğinin varlığı için gerekli ve yeterli koşul o o o Bir grafiğin Euler doğrusuna sahip olması için bağlantılı olması gerekir. Königsberg köprü probleminde olduğu gibi, her Euler çizgisinin her köşeye aynı sayıda girip çıkması gerektiği, yani grafiğin tüm köşelerinin derecelerinin eşit olması gerektiği açıktır. Bu, bir grafiğin Euler olması için iki koşulun gerekli olduğu anlamına gelir: grafik bağlıdır ve tüm köşelerinin dereceleri eşittir. Euler, bu koşulların da yeterli olduğunu kanıtladı: tüm köşelerin dereceleri çift olan bağlantılı bir grafiğin bir Euler doğrusu var.

Kendi başınıza o Bu grafiklerin Euler grafikleri olup olmadığını belirleyin? (çizgileri kesmeden veya tekrar etmeden, tek bir kalem darbesiyle daire içine alıp başladığımız noktaya geri dönmek mümkün mü?) Evet ise, içlerinde Euler döngülerini bulun (bunun nasıl yapıldığını gösterin)

Euler yolu o o Bir Euler yolu, tüm kenarların bir kez geçildiği, ancak başlangıç noktasına geri dönülmeden bir yoldur. Grafiğin bir Euler döngüsü yoksa, bir Euler yolu bulma problemini ortaya koyabiliriz.

Bir Euler yolunun varlığı için yeterli bir koşul o o Eğer Г grafiğinin A ve B uçlarına sahip bir Euler yolu varsa (A, B ile çakışmaz), bu durumda Г grafiği bağlantılıdır ve A ve B onun tek tek köşeleridir. Gerçekten de, bir grafiğin bağlantılılığı, bir Euler yolunun tanımından gelir. Yol A'da başlıyor ve başka bir B köşesinde bitiyorsa, yol A ve B'den tekrar tekrar geçse bile, hem A hem de B tektir. Yol, grafiğin herhangi bir başka köşesine, yani tüm köşelerin geri kalanı eşit olmalıdır.

Bir Euler yolunun varlığı için gerekli bir koşul oo Tersi de doğrudur: Γ grafiği bağlantılıysa ve A ve B onun tek tek köşeleriyse, o zaman Γ grafiğinin A ve B uçları olan bir Euler yolu vardır. Köşeler A ve B, grafikte bir kenar ile bağlanabilir veya bağlı olabilir ve olmayabilir. Her durumda, ek veya yeni bir kenar (A, B) ekleriz, o zaman tüm köşeleri eşit olur. Bir Euler grafiğinin varlığı için yeterli koşulun yukarıdaki yapıcı kanıtına göre yeni grafik, herhangi bir kenar boyunca başlatılabilen bir Euler döngüsüne sahiptir. Euler döngüsünü, eklenen kenar (A, B) boyunca A noktasından başlatır ve A noktasında bitiririz. Şimdi silersek

Euler yolu teoreminin uygulanması oo Böylece, tam olarak iki tek köşesi olan herhangi bir kapalı şekil, tek köşelerden birinden başlayıp diğerinde biten tekrarlama olmaksızın tek bir vuruşta çizilebilir. Bu teoreme göre, Königsberg köprülerinden geçen bir Euler yolu yoktur, çünkü karşılık gelen graf bağlantılı olmasına rağmen, tüm köşelerinin dereceleri tektir ve Euler yolunun mevcut

Bağımsız olarak o Euler yolu teoremine göre, grafiklerde bir Euler yolu olup olmadığını belirleyiniz. (köşelerden birinden başlayıp diğerinde biten, tekrarsız bir vuruşla çizmek mümkün mü). Varsa bulun (nasıl yapılacağını gösterin)

Problem 7. 2. Hayali bir şehir için Koenigsberg köprüleri hakkında (bağımsız olarak) o Şekil, Euler'in çalışmalarında örneklediği hayali bir şehrin planını göstermektedir. Euler planı için bir grafik çizin ve içinde bir Euler döngüsü olup olmadığını belirleyin? Ve Euler yolu? Evet ise, bulun.

Görev 8. Hayvanat bahçesi (kendi başınıza) o Şekil, hayvanat bahçesinin bir diyagramını göstermektedir (grafiğin köşeleri, hücrelerin bulunduğu giriş, çıkış, kavşaklar, dönüşler, çıkmaz uçlar, kenarlar-izlerdir). Rehberin ziyaretçilere tüm hayvanları göstererek ve yolun tek bir bölümünden birden fazla geçmeyerek yönlendirebileceği bir rota bulun, yani Euler yolunu bulun.

grafik teorisi- bölüm ayrık Matematiközelliklerini incelemek sayar . Genel anlamda, bir grafik, kenarlarla birbirine bağlanan bir dizi köşe (düğüm) olarak temsil edilir. Kesin tanımda, bir grafik böyle bir çift kümedir. G=(V,E), burada V herhangi bir sayılabilir kümenin bir alt kümesidir ve E, V×V'nin bir alt kümesidir.

Grafik teorisinin ortaya çıkış tarihi
Leonhard Euler, çizge teorisinin babası olarak kabul edilir. 1736'da mektuplarından birinde, daha sonra çizge teorisinin klasik problemlerinden biri haline gelen yedi Königsberg köprüsü sorununa bir çözüm formüle eder ve önerir.
Grafik teorisindeki ilk problemler, matematiksel eğlence problemlerini ve bulmacaları çözmekle ilgiliydi. İşte Euler'in 13 Mart 1736 tarihli mektubundan bir alıntı: “Koenigsberg şehrinde bulunan ve üzerine 7 köprünün atıldığı bir nehirle çevrili bir ada hakkında bir sorun teklif edildi. Soru, herhangi birinin her köprüden yalnızca bir kez geçerek sürekli olarak çevrelerinden geçip geçemeyeceğidir. Ve sonra kimsenin bunu henüz başaramadığı bilgisi verildi, ama hiç kimse bunun imkansız olduğunu kanıtlamadı. Bu soru banal olmasına rağmen, yine de dikkate değer görünüyordu, çünkü ne geometri, ne cebir, ne de kombinatoryal sanat, çözümü için yeterli değil. Çok düşündükten sonra, tamamen ikna edici bir kanıta dayanan kolay bir kural buldum, bu tür tüm problemlerde böyle bir turun herhangi bir sayıda ve rastgele yerleştirilmiş köprülerden yapılıp yapılmayacağını hemen belirlemenin mümkün olduğu yardımı ile. . Königsberg köprüleri şematik olarak aşağıdaki gibi gösterilebilir:
Euler kuralı:

1. Tek dereceli köşeleri olmayan bir grafikte, grafiğin herhangi bir köşesinden başlayarak tüm kenarların bir geçişi vardır (ve her kenar tam olarak bir kez geçilir).
2. İki ve yalnızca iki tek dereceli köşesi olan bir grafikte, bir tek dereceli köşeden başlayıp diğerinde biten bir baypas vardır.
3. İkiden fazla tek dereceli köşesi olan bir grafikte böyle bir geçiş yoktur.

Grafiklerde gezinmeyle ilgili bir tür problem daha vardır. Tüm köşelerden geçen ve her birinden birden fazla olmayan bir yol bulmanın gerekli olduğu problemlerden bahsediyoruz. Her tepe noktasından yalnızca bir kez geçen bir döngüye Hamilton doğrusu denir (bu tür doğruları ilk inceleyen, geçen yüzyılın ünlü İrlandalı matematikçisi William Rowan Hamilton'un onuruna). Ne yazık ki, verilen bir grafiğin Hamiltonyen olup olmadığına karar verebilecek ve eğer öyleyse, üzerindeki tüm Hamilton çizgilerini bulabilecek genel bir kriter bulunamadı.
19. yüzyılın ortalarında formüle edilmiştir. dört renk problemi de eğlenceli bir problem gibi görünse de, onu çözmeye yönelik girişimler teorik ve uygulamalı öneme sahip bazı grafik çalışmalarının ortaya çıkmasına neden olmuştur. Dört renk problemi şu şekilde formüle edilmiştir: “Herhangi bir düz haritanın bir alanı, bitişik herhangi iki alanı farklı renklerle boyanacak şekilde dört renkle renklendirilebilir mi?”. Cevabın evet olduğu hipotezi 19. yüzyılın ortalarında formüle edildi. 1890'da, herhangi bir düz haritanın beş renkle renklendirilebileceğine dair daha zayıf bir iddia kanıtlandı. Herhangi bir düz grafiği çift düz gr ile ilişkilendirmeaf, grafikler açısından problemin eşdeğer bir formülasyonunu elde edin: Herhangi bir düzlemsel grafiğin kromatik sayısının dörtten küçük veya ona eşit olduğu doğru mu? Problemi çözmeye yönelik çok sayıda girişim, çizge teorisinin birçok alanının gelişimini etkilemiştir. 1976'da bir bilgisayar kullanılarak soruna olumlu bir çözüm olduğu açıklandı.

Leonhard Euler, çizge teorisinin babası olarak kabul edilir. 1736'da mektuplarından birinde, daha sonra çizge teorisinin klasik problemlerinden biri haline gelen yedi Königsberg köprüsü sorununa bir çözüm formüle eder ve önerir.

Grafik teorisindeki ilk problemler, matematiksel eğlence problemlerini ve bulmacaları çözmekle ilgiliydi. İşte Euler'in 13 Mart 1736 tarihli mektubundan bir alıntı: “Koenigsberg şehrinde bulunan ve üzerine 7 köprünün atıldığı bir nehirle çevrili bir ada hakkında bir sorun teklif edildi. Soru, herhangi birinin her köprüden yalnızca bir kez geçerek sürekli olarak çevrelerinden geçip geçemeyeceğidir. Ve sonra kimsenin bunu henüz başaramadığı bilgisi verildi, ama hiç kimse bunun imkansız olduğunu kanıtlamadı. Bu soru banal olmasına rağmen, yine de dikkate değer görünüyordu, çünkü ne geometri, ne cebir, ne de kombinatoryal sanat, çözümü için yeterli değil. Çok düşündükten sonra, tamamen ikna edici bir kanıta dayanan kolay bir kural buldum, bu tür tüm problemlerde böyle bir turun herhangi bir sayıda ve rastgele yerleştirilmiş köprülerden yapılıp yapılmayacağını hemen belirlemenin mümkün olduğu yardımı ile. . Königsberg köprüleri şematik olarak aşağıdaki gibi gösterilebilir:

Euler kuralı:

1. Tek dereceli köşeleri olmayan bir grafikte, grafiğin herhangi bir köşesinden başlayarak tüm kenarların bir geçişi vardır (ayrıca her kenar tam olarak bir kez geçilir).

2. İki ve yalnızca iki tek dereceli köşesi olan bir grafikte, bir tek dereceli köşeden başlayıp diğerinde biten bir baypas vardır.

3. İkiden fazla tek dereceli köşesi olan bir grafikte böyle bir geçiş yoktur.

19. yüzyılın ortalarında formüle edilmiştir. dört renk problemi de eğlenceli bir problem gibi görünse de, onu çözmeye yönelik girişimler teorik ve uygulamalı öneme sahip bazı grafik çalışmalarının ortaya çıkmasına neden olmuştur. Dört renk problemi şu şekilde formüle edilmiştir: “Herhangi bir düz haritanın bir alanı, bitişik herhangi iki alanı farklı renklerle boyanacak şekilde dört renkle renklendirilebilir mi?”. Cevabın evet olduğu hipotezi 19. yüzyılın ortalarında formüle edildi. 1890'da, herhangi bir düz haritanın beş renkle renklendirilebileceğine dair daha zayıf bir iddia kanıtlandı. Herhangi bir düzlemsel haritayı onun ikili düzlemsel grafiğiyle karşılaştırarak, problemin grafikler açısından eşdeğer bir formülasyonunu elde ederiz: Herhangi bir düzlemsel grafiğin kromatik sayısının dörtten küçük veya ona eşit olduğu doğru mu? Problemi çözmeye yönelik çok sayıda girişim, çizge teorisinin birçok alanının gelişimini etkilemiştir. 1976'da bir bilgisayar kullanılarak soruna olumlu bir çözüm olduğu açıklandı.

Özellikle uzun süredir çözüme kavuşamayan ve bulmaca severlerin aklını başından alan bir başka eski topolojik problem, “elektrik, gaz ve su temini sorunu” olarak biliniyor. 1917'de Henry E. Dudeney ona bu formülasyonu verdi. Şekilde gösterilen üç evin her birinde gaz, elektrik ve su iletilmesi gerekmektedir.

Grafik teorisi. bir

Grafik teorisinin ortaya çıkış tarihi. bir

Euler kuralı. bir

Edebiyat

1. Belov Grafik Teorisi, Moskova, "Nauka", 1968.

2. Yeni pedagojik ve bilgi teknolojileri E.S. Polat , Moskova, "Akademia" 1999

3. Kuznetsov O.P., Adelson-Velsky G.M. Bir Mühendis için Ayrık Matematik. - Moskova: Energoatomizdat, 1988.

4. Cook D., Baize G. Bilgisayar Matematiği. - M.: Nauka, 1990.

5. Nefedov V.N., Osipova V.A. Ayrık Matematik Kursu. - M.: MAI yayınevi, 1992.

6. Cevher O. Grafik Teorisi. - M.: Nauka, 1980.

7. İsmagilov R.S., Kalınkin A.V. Kurstaki uygulamalı dersler için materyaller: Ayrık Matematik

BELEDİYE ÖZERK GENEL EĞİTİM KURULUŞU ORTAÖĞRETİM OKULU № 2

Hazırlanmış

Legkokonets Vladislav, 10A öğrencisi

Pratik kullanım Grafik Teorileri

süpervizör

L.I. Noskova, matematik öğretmeni

st.Bryukhovetskaya

2011

1.Giriş…………………………………………………………………….………….3

2. Grafik teorisinin ortaya çıkış tarihi………………………………………….………..4

3.Çizge teorisinin temel tanımları ve teoremleri……………………………….………6

4. Grafikler yardımıyla çözülen görevler……………………………..……………………..8

4.1 Ünlü görevler………………………………….…………………………...8

4.2 Bazı ilginç görevler………………………………….……………..9

5. Grafiklerin insanların hayatlarının çeşitli alanlarında uygulanması…………………………………….11

6. Problem çözme……………………………………………………………………………...12

7. Sonuç………………….…………………………………………………………….13

8. Referans listesi………….………………………………………………………………………………………………………… ………………………………………………………………………………………………………………………………… ………………………………………………………………………………………………………………….

9.Ek………………………………………………………………….…………15

Tanıtım

Bulmacaları çözmek için doğmuş ve eğlenceli oyunlar, grafik teorisi artık çok çeşitli problemlerle ilgili sorunları çözmek için basit, erişilebilir ve güçlü bir araç haline geldi. Grafikler kelimenin tam anlamıyla her yerde bulunur. Örneğin, yol haritaları ve elektrik devreleri, coğrafi haritalar ve moleküller grafikler şeklinde yorumlanabilir. kimyasal bileşikler, insanlar ve insan grupları arasındaki bağlantılar. Son kırk yılda çizge teorisi, matematiğin en hızlı gelişen dallarından biri haline geldi. Bu, hızla genişleyen bir uygulama alanının taleplerinden kaynaklanmaktadır. Entegre devrelerin ve kontrol devrelerinin tasarımında, otomatların çalışmasında, mantıksal devrelerde, program akış şemalarında, ekonomi ve istatistikte, kimya ve biyolojide, çizelgeleme teorisinde kullanılır. Böyle alaka Konu, bir yandan grafiklerin ve ilgili araştırma yöntemlerinin popülaritesinden ve diğer yandan uygulanması için gelişmemiş, entegre bir sistemden kaynaklanmaktadır.

Birçok yaşam probleminin çözümü uzun hesaplar gerektirir ve bazen bu hesaplamalar başarı getirmez. İşte bundan ibaret Araştırma problemi. Soru ortaya çıkıyor: Çözümleri için basit, rasyonel, kısa ve zarif bir çözüm bulmak mümkün mü? Grafikleri kullanırsanız sorunları çözmek daha mı kolay? belirledi araştırmamın konusu: "Grafik Teorisinin Pratik Uygulaması"

nişan almak araştırma, pratik problemlerin nasıl hızlı bir şekilde çözüleceğini öğrenmek için grafiklerin yardımıyla yapıldı.

Araştırma hipotezi. Graf yöntemi çok önemlidir ve bilimin ve insan yaşamının çeşitli alanlarında yaygın olarak kullanılmaktadır.

Araştırma hedefleri:

1. Bu konudaki literatürü ve internet kaynaklarını incelemek.

2. Pratik problemlerin çözümünde grafik yönteminin etkinliğini kontrol edin.

3. Bir sonuca varın.

Çalışmanın pratik önemi sonuçların şüphesiz birçok insanın ilgisini çekeceğidir. Hiç biriniz ailenizin soy ağacını oluşturmaya çalışmadınız mı? Ve nasıl doğru yapılır? Bir nakliye şirketinin başkanı, malları bir varış noktasından çeşitli yerleşim yerlerine taşırken muhtemelen nakliyenin daha karlı kullanımı sorununu çözmek zorundadır. Her öğrenci mantıksal transfüzyon görevleriyle karşı karşıya kaldı. Grafikler yardımıyla kolayca çözüldüğü ortaya çıktı.

Çalışmada aşağıdaki yöntemler kullanılır: gözlem, arama, seçim, analiz.

Grafik teorisinin ortaya çıkış tarihi

Matematikçi Leonhard Euler (1707-1783), çizge teorisinin kurucusu olarak kabul edilir. Bu teorinin ortaya çıkış tarihi, büyük bilim adamının yazışmalarıyla izlenebilir. İşte Euler'in İtalyan matematikçi ve mühendis Marinoni'ye 13 Mart 1736'da St. Petersburg'dan gönderilen mektubundan alınan Latince metnin çevirisi.

“Bir keresinde bana Koenigsberg şehrinde bulunan ve yedi köprünün atıldığı bir nehirle çevrili bir ada hakkında bir problem verildi.

[Ek Şekil1] Soru, herhangi birinin her köprüden yalnızca bir kez geçerek sürekli olarak çevrelerinden geçip geçemeyeceğidir. Ve sonra kimsenin bunu henüz başaramadığı bilgisi verildi, ama hiç kimse bunun imkansız olduğunu kanıtlamadı. Bu soru banal olmasına rağmen, yine de dikkate değer görünüyordu, çünkü ne geometri, ne cebir, ne de kombinatoryal sanat, çözümü için yeterli değil. Çok düşündükten sonra, tamamen ikna edici bir kanıta dayanan kolay bir kural buldum; bu tür tüm problemlerde, böyle bir turun herhangi bir sayıda ve rastgele yerleştirilmiş köprülerden yapılıp yapılmayacağını hemen belirleyebilir. Königsberg köprüleri, aşağıdaki şekilde gösterilebilecek şekilde yerleştirilmiştir. [Ek Şekil.2], burada A bir adayı belirtir ve B , C ve D kıtanın birbirinden nehir kollarıyla ayrılmış bölümleridir.

Euler, bu tür sorunları çözmek için keşfettiği yöntemle ilgili olarak şunları yazdı:

"Bu çözümün doğası gereği matematikle pek ilgisi yok gibi görünüyor ve bu çözümün neden başka herhangi bir kişiden değil de bir matematikçiden beklenmesi gerektiği bana açık değil, çünkü bu çözüm yalnızca akılla destekleniyor ve Bu çözümü, matematiğin doğasında bulunan herhangi bir yasayı bulmaya dahil olmaya gerek yok. Bu yüzden, matematikle çok az ilgisi olan soruların matematikçiler tarafından diğerlerinden daha fazla çözülme olasılığının nasıl ortaya çıktığını bilmiyorum. "

Peki bu köprülerin her birinden sadece bir kez geçerek Königsberg köprülerinin etrafından dolaşmak mümkün mü? Cevabı bulmak için Euler'in Marinoni'ye yazdığı mektupla devam edelim:

"Mesele bu yedi köprünün hepsini birer kez geçerek dolaşıp dolaşmanın mümkün olup olmadığını belirlemektir. Benim kuralım bu sorunun çözümünü şu şekilde gösteriyor. Öncelikle kaç bölüm olduğuna bakmak gerekiyor. su ile ayrılırlar - köprü dışında birinden diğerine geçişi olmayanlar.Bu örnekte, bu tür dört bölüm vardır - A, B, C, D. Daha sonra, sayı olup olmadığını ayırt etmeniz gerekir. Bu ayrı bölümlere giden köprüler çift veya tektir.Yani, bizim durumumuzda, beş köprü A bölümüne ve üç köprü geri kalanlara gidiyor, yani Tek tek bölümlere giden köprülerin sayısı tek ve bu zaten yeterli. Bu belirlendiğinde, aşağıdaki kuralı uygularız: Her bir bölüme giden köprülerin sayısı çift olsaydı, o zaman söz konusu dolambaçlı yol mümkün olurdu ve aynı zamanda bu dolambaçlı yolu başlatmak da mümkün olurdu. herhangi bir bölümden. tek olur, çünkü sadece biri n olur eğer çift olamazsa, o zaman bile geçiş, öngörüldüğü gibi gerçekleşebilir, ancak tek sayıda köprünün götürdüğü bu iki bölümden birinden dolambaçlı yolun yalnızca başlangıcı kesinlikle alınmalıdır. Son olarak, tek sayıda köprünün yol açtığı ikiden fazla bölüm varsa, o zaman böyle bir hareket genellikle imkansızdır ... eğer burada daha ciddi problemlerden bahsedilebilirse, bu yöntem daha da yararlı olabilir ve olmamalıdır. ihmal edilmek".

Grafik teorisinin temel tanımları ve teoremleri

Grafik teorisi, matematikçilerin çabalarıyla oluşturulmuş bir matematik disiplinidir, bu nedenle sunumu gerekli titiz tanımları içerir. Öyleyse, bu teorinin temel kavramlarının organize tanıtımına geçelim.

Tanım 1. Bir grafik, grafiğin köşeleri olarak adlandırılan ve grafiğin kenarları veya yayları olarak adlandırılan bu doğruların bazı köşelerini çift olarak birbirine bağlayan sonlu sayıda nokta topluluğudur.

Bu tanım farklı şekilde formüle edilebilir: bir grafik, her iki ucu da belirli bir nokta kümesine ait olan, boş olmayan bir noktalar (köşeler) ve segmentler (kenarlar) kümesidir.

Gelecekte, grafiğin köşelerini A, B, C, D Latin harfleriyle göstereceğiz. Bazen bir bütün olarak grafik bir ile gösterilir büyük harf.

Tanım 2. Grafiğin herhangi bir kenara ait olmayan köşelerine izole denir.

Tanım 3. Yalnızca yalıtılmış köşelerden oluşan bir grafa sıfır denir - saymak .

Notasyon: O "– köşeleri olan ve kenarları olmayan bir grafik

Tanım 4. Her bir köşe çiftinin bir kenarla bağlandığı bir grafiğe tam denir.

Tanım: U" – n tane köşe ve bu köşelerin tüm olası çiftlerini birleştiren kenarlardan oluşan bir grafik. Böyle bir grafik, tüm köşegenlerin çizildiği bir n-gon olarak temsil edilebilir.

Tanım 5. Bir tepe noktasının derecesi, tepe noktasının ait olduğu kenarların sayısıdır.

Tanım 6. Tüm k köşelerinin dereceleri aynı olan grafa k dereceli homojen graf denir. .

Tanım 7. Belirli bir grafiğin tümleyeni, tam bir grafik elde etmek için orijinal grafiğe eklenmesi gereken tüm kenarlardan ve uçlarından oluşan bir grafiktir.

Tanım 8. Bir düzlemde, kenarları yalnızca köşelerde kesişecek şekilde temsil edilebilen bir grafa düzlemsel denir.

Tanım 9.İçinde grafiğin köşeleri veya kenarları olmayan düzlemsel bir grafiğin çokgenine yüzü denir.

Düzlem grafiği ve grafik yüzleri kavramları, çeşitli haritaların "doğru" renklendirilmesi için problemlerin çözümünde kullanılır.

Tanım 10. A'dan X'e bir yol, A'dan X'e giden bir kenarlar dizisidir, öyle ki her iki bitişik kenar ortak bir köşeye sahiptir ve hiçbir kenar bir kereden fazla oluşmaz.

Tanım 11. Bir döngü, başlangıç ve bitiş noktalarının aynı olduğu bir yoldur.

Tanım 12. Basit bir döngü, grafiğin herhangi bir noktasından bir kereden fazla geçmeyen bir döngüdür.

Tanım 13. uzun yol , bir döngü üzerine koydu , bu yolun kenar sayısıdır.

Tanım 14. Bir grafikteki iki A ve B köşesine, içinde A'dan B'ye giden bir yol varsa (yoksa) bağlı (bağlantısız) denir.

Tanım 15. Her iki köşesi birbirine bağlıysa bir graf bağlı olarak adlandırılır; grafik en az bir çift bağlantısız köşe içeriyorsa, grafik bağlantısız olarak adlandırılır.

Tanım 16. Ağaç, döngü içermeyen bağlantılı bir grafiktir.

Bir grafik ağacının üç boyutlu modeli, örneğin, karmaşık dallara ayrılmış tacı olan gerçek bir ağaçtır; nehir ve kolları da bir ağaç oluşturur, ancak zaten düzdür - dünya yüzeyinde.

Tanım 17. Yalnızca ağaçlardan oluşan bağlantısız bir grafa orman denir.

tanım 18. Tüm n köşeleri 1'den n'ye kadar numaralandırılmış bir ağaca, köşeleri yeniden numaralandırılmış bir ağaç denir.

Bu nedenle, teoremleri kanıtlamanın ve sonuç olarak sorunları çözmenin imkansız olacağı grafik teorisinin ana tanımlarını düşündük.

Grafikler kullanılarak çözülen problemler

Ünlü Zorluklar

gezgin satıcı problemi

Gezgin satıcı problemi, kombinatorik teorisindeki ünlü problemlerden biridir. 1934'te kuruldu ve en iyi matematikçiler bu konuda dişlerini kırdılar.

Sorun ifadesi aşağıdaki gibidir.
Gezgin satıcı (gezgin tüccar) ilk şehri terk etmeli, 2,1,3..n şehirlerini bilinmeyen bir sırayla bir kez ziyaret etmeli ve ilk şehre dönmelidir. Şehirler arası mesafeler biliniyor. Gezgin satıcının kapalı yolunun (turunun) en kısa olması için şehirlerden hangi sırayla geçilmelidir?

Gezgin satıcı problemini çözme yöntemi

Açgözlü algoritma “En yakın (henüz girmediğiniz) şehre gidin.”
Bu algoritmaya "açgözlü" denir çünkü son adımlarda açgözlülük için çok pahalı ödemeniz gerekir.
Örneğin, Şekildeki ağı düşünün [uygulama şek.3] dar bir eşkenar dörtgeni temsil eder. Satıcının 1. şehirden başlamasına izin verin. “En yakın şehre git” algoritması onu şehir 2'ye, sonra 3'e, sonra 4'e götürecektir; son adımda, eşkenar dörtgenin uzun köşegeni boyunca geri dönerek açgözlülük için ödeme yapmanız gerekecek. Sonuç en kısa değil, en uzun tur.

Königsberg köprülerinin sorunu.

Görev aşağıdaki gibi formüle edilmiştir.
Königsberg şehri, Pregel Nehri ve iki adanın kıyısında yer almaktadır. Şehrin farklı bölgeleri yedi köprü ile birbirine bağlandı. Pazar günleri kasaba halkı şehirde yürüyüşe çıkardı. Soru: Evden çıkıp her köprüden tam olarak bir kez geçerek geri dönecek şekilde yürüyüş yapmak mümkün mü?
Pregel nehri üzerindeki köprüler resimdeki gibi yer almaktadır.[Ek Şekil.1].

Köprü şemasına karşılık gelen bir grafik düşünün [ek şek.2].

Sorunun sorusunu cevaplamak için grafiğin Euler olup olmadığını bulmak yeterlidir. (En az bir tepe noktası çift sayıda köprüye sahip olmalıdır). Şehri dolaşıp bütün köprüleri bir kez geçip geri dönmek mümkün değil.

Birkaç ilginç zorluk

1. "Rotalar".

Görev 1

Hatırladığınız gibi, ölü ruhlar için avcı Chichikov, her biri ünlü toprak sahiplerini ziyaret etti. Onları şu sırayla ziyaret etti: Manilov, Korobochka, Nozdrev, Sobakevich, Plyushkin, Tentetnikov, General Betrishchev, Petukh, Konstanzholgo, Albay Koshkarev. Chichikov'un mülklerin ve onları birbirine bağlayan köy yollarının göreceli konumunu çizdiği bir diyagram bulundu. Chichikov yollardan hiçbirini bir kereden fazla geçmediyse, hangi mülkün kime ait olduğunu belirleyin. [ek şek.4].

Çözüm:

Yol haritasına göre, Chichikov'un yolculuğuna E mülkü ile başladığı ve O mülkü ile sona erdiği görülebilir.Sadece iki yolun B ve C mülklerine çıktığını fark ettik, bu yüzden Chichikov bu yolları kullanmak zorunda kaldı. Onları kalın çizgilerle işaretleyelim. Rotanın A'dan geçen bölümleri belirlenir: AC ve AB. Chichikov, AE, AK ve AM yollarında seyahat etmedi. Onları geçelim. Kalın bir çizgi ile işaretleyelim ED ; DK'yi geç. MO ve MN'nin üzerini çizin; kalın bir çizgi MF ile işaretleyin; FO'yu çaprazlayın; FH , NK ve KO'yu kalın bir çizgi ile işaretliyoruz. Verilen koşul altında mümkün olan tek yolu bulalım. Ve şunu alıyoruz: E - mülkü Manilov, D - Korobochka, C - Nozdrev, A - Sobakevich, V - Plyushkin, M - Tentetnikov, F - Betrishchev, N - Petukh, K - Konstanzholgo, O - Koshkarev'e ait [uygulama şek.5].

Görev 2

Şekil, bölgenin bir haritasını göstermektedir. [ek şek.6].

Sadece okların yönünde hareket edebilirsiniz. Her nokta birden fazla ziyaret edilemez. 1. noktadan 9. noktaya kaç farklı şekilde ulaşabilirsiniz? Hangi rota en kısa ve hangisi en uzun.

Çözüm:

1 numaralı köşeden başlayarak şemayı sırayla bir ağaca "katıştırın" [uygulama şek.7]. Bir ağaç alalım. 1'den 9'a ulaşmanın olası yollarının sayısı, ağacın "asılı" köşelerinin sayısına eşittir (14 tanesi vardır). Açıkçası en kısa yol 1-5-9'dur; en uzunu 1-2-3-6-5-7-8-9'dur.

2 "Gruplar, flört"

Görev 1

Müzik festivaline katılanlar bir araya gelerek adresleri ile zarf alışverişinde bulundular. Kanıtla:

a) toplamda çift sayıda zarf gönderildi;

b) zarfları tek sayıda değiştiren katılımcı sayısı çifttir.

Çözüm: Festival katılımcıları A 1 , A 2 , A 3 olsun. . . , Ve n, grafiğin köşeleridir ve kenarlar, zarf değiştiren adamları temsil eden köşe çiftlerini birbirine bağlar. [Ek Şekil 8]

Çözüm:

a) her A i köşesinin derecesi, katılımcı A i'nin arkadaşlarına verdiği zarf sayısını gösterir. İletilen zarfların toplam sayısı N, grafiğin tüm köşelerinin derecelerinin toplamına eşittir N = adım. 1 + adım. 2 + + . . . + adım. Ve n -1 + adım. Ve n , N =2p , burada p grafik kenarlarının sayısıdır, yani. N eşittir. Bu nedenle, çift sayıda zarf gönderildi;

b) eşitlikte N = adım. 1 + adım. 2 + + . . . + adım. Ve n -1 + adım. Ve n tek terimlerin toplamı çift olmalıdır ve bu ancak tek terimlerin sayısı çift ise olabilir. Bu da zarfları tek sayıda değiştiren katılımcı sayısının çift olduğu anlamına gelir.

Görev 2

Andrei, Boris, Volodya, Dasha ve Galya bir kez akşam sinemaya gitmeyi kabul ettiler. Sinema ve seans seçimi konusunda telefonla anlaşmaya karar verdiler. Ayrıca birine telefon etmek mümkün değilse, sinema gezisinin iptal edilmesine karar verildi. Akşam, herkes sinemada toplanmadı ve bu nedenle sinema ziyareti düştü. Ertesi gün kimin kimi aradığını öğrenmeye başladılar. Andrey'in Boris ve Volodya'yı, Volodya'nın Boris ve Dasha'yı, Boris'in Andrey ve Dasha'yı, Dasha'nın Andrey ve Volodya'yı ve Galya'nın Andrey, Volodya ve Boris'i aradığı ortaya çıktı. Kim telefon edemedi ve bu nedenle toplantıya gelmedi?

Çözüm:

Beş nokta çizelim ve bunları A, B, C, D, E harfleriyle belirleyelim. İsimlerin ilk harfleri bunlar. Birbirini arayan adamların isimlerine karşılık gelen noktaları birleştirelim.

[uygulama şek.9]

Resimden her birinin - Andrey, Boris ve Volodya - herkesi aradığı görülebilir. Bu adamlar bu yüzden sinemaya geldiler. Ancak Galya ve Dasha birbirlerini aramadılar (D ve D noktaları bir segmentle bağlı değil) ve bu nedenle anlaşmaya göre sinemaya gelmediler.

İnsanların hayatlarının çeşitli alanlarında grafiklerin kullanımı

Verilen örneklere ek olarak, grafikler inşaat, elektrik mühendisliği, yönetim, lojistik, coğrafya, makine mühendisliği, sosyoloji, programlama, teknolojik süreçlerin ve endüstrilerin otomasyonu, psikoloji ve reklamcılıkta yaygın olarak kullanılmaktadır. Bu nedenle, yukarıdakilerin hepsinden, ispatı bu çalışmanın amacı olan grafik teorisinin pratik değeri reddedilemez bir şekilde takip eder.

Bilim ve teknolojinin her alanında grafiklerle karşılaşırsınız. Grafikler, matematiksel, ekonomik ve mantıksal problemleri, çeşitli bulmacaları çözebileceğiniz ve fizik, kimya, elektronik, otomasyondaki problemlerin koşullarını basitleştirebileceğiniz harika matematiksel nesnelerdir. Birçok matematiksel gerçeği grafik dilinde formüle etmek uygundur. Grafik teorisi birçok bilimin bir parçasıdır. Grafik teorisi en güzel ve görsel matematik teorilerinden biridir. Son zamanlarda, grafik teorisi uygulamalı konularda giderek daha fazla uygulama bulmuştur. Bilgisayar kimyası bile ortaya çıktı - çizge teorisinin uygulanmasına dayanan nispeten genç bir kimya alanı.

Moleküler grafikler, stereokimyada ve yapısal topolojide, kümelerin kimyasında, polimerlerde vb. kullanılan, moleküllerin yapısını gösteren yönsüz grafiklerdir. [uygulama şek.10]. Bu grafiklerin köşeleri ve kenarları karşılık gelen atomlara ve Kimyasal bağlar onların arasında.

Moleküler grafikler ve ağaçlar: [uygulama şek.10] a, b - multigraflar etilen ve formaldehit; in-mol. pentan izomerleri (ağaçlar 4, 5, ağaç 2 ile izomorfiktir).

Organizmaların stereokimyasında en çok genellikle moleküler ağaçları kullanırlar - yalnızca C atomlarına karşılık gelen tüm köşeleri içeren moleküler grafiklerin ana ağaçları. ağaçlar ve izomorfizmlerinin kurulması, iskeleyi belirlemenizi sağlar. alkanların, alkenlerin ve alkinlerin toplam izomer sayısını bulun

Protein ağları

Protein ağları - vücutta meydana gelen birbirine bağlı süreçleri kontrol ederek, bir hücrede birlikte ve koordineli bir şekilde işlev gören fiziksel olarak etkileşime giren protein grupları [uygulama şek. on bir].

Hiyerarşik sistem grafiği ağaç denir. Bir ağacın ayırt edici özelliği, herhangi iki köşesi arasında yalnızca bir yol olmasıdır. Ağaç döngüler ve döngüler içermez.

Genellikle, hiyerarşik bir sistemi temsil eden bir ağaç, ağacın kökü olarak adlandırılan bir ana tepe noktasına sahiptir. Ağacın her tepe noktasının (kök hariç) yalnızca bir atası vardır - onun tarafından belirlenen nesne bir üst düzey sınıfa aittir. Ağacın herhangi bir köşesi, birkaç alt öğe üretebilir - alt düzey sınıflara karşılık gelen köşeler.

Her bir ağaç köşe çifti için onları birbirine bağlayan benzersiz bir yol vardır. Bu özellik, soy ağacı soy ağacı olarak gösterilen herhangi bir kişinin tüm atalarını, örneğin erkek soyunu bulurken kullanılır, ki bu da graf teorisi anlamında bir “ağaç”tır.

aile ağacımdan bir örnek [ek şek.12].

Bir örnek daha. Şekil İncil'deki soy ağacını göstermektedir [ek şek.13].

Problem çözme

1. Taşıma görevi. Mümkün olduğunca az zaman ve yakıt harcayarak ve geri dönerken Krymsk, Temryuk, Slavyansk-on-Kuban ve Timashevsk şehirlerine tek seferde ekilmesi gereken Krasnodar şehrinde hammadde içeren bir üs olsun. Krasnodar'a.

Çözüm:

İlk olarak, tüm olası rotaların bir grafiğini oluşturalım. [uygulama şek.14], bu yerleşimler arasındaki gerçek yollar ve aralarındaki mesafe dikkate alınarak. Bu sorunu çözmek için başka bir grafik, bir ağaç oluşturmamız gerekiyor. [uygulama şek.15].

Çözümün rahatlığı için şehirleri sayılarla belirtiyoruz: Krasnodar - 1, Krymsk - 2, Temryuk - 3, Slavyansk - 4, Timashevsk - 5.

Bu 24 çözümle sonuçlandı, ancak yalnızca en kısa yollara ihtiyacımız var. Tüm çözümlerden sadece ikisi tatmin edici, bunlar 350 km.

Benzer şekilde, mümkün ve bence gerçek ulaşımı birinden hesaplamak gerekiyor. yerellik diğerlerine.

Transfüzyon için mantıksal görev. Bir kovada 8 litre su bulunmakta olup, 5 ve 3 litre kapasiteli iki tencere bulunmaktadır. 4 litre suyu beş litrelik bir tencereye koyup 4 litreyi bir kovaya bırakmak gerekiyor yani suyu bir kovaya ve büyük bir tencereye eşit miktarda dökün.

Çözüm:

Herhangi bir andaki durum üç sayı ile tanımlanabilir [ek şek.16].

Sonuç olarak, iki çözüm elde ederiz: biri 7 hamlede, diğeri 8 hamlede.

Çözüm

Bu nedenle, sorunları nasıl çözeceğinizi öğrenmek için, bunların ne olduğunu, nasıl düzenlendiğini, hangi bileşenlerden oluştuğunu, sorunları çözmek için kullanılan araçların neler olduğunu anlamanız gerekir.

Pratik problemleri grafik teorisi yardımıyla çözerek, çözümlerinin her aşamasında, her aşamada yaratıcılığın uygulanması gerektiği ortaya çıktı.

En başından itibaren, ilk aşamada, sorunun durumunu analiz edip kodlayabilmeniz gerektiği gerçeğinde yatmaktadır. İkinci aşama, grafiklerin geometrik temsilinden oluşan şematik bir gösterimdir ve bu aşamada yaratıcılık öğesi çok önemlidir, çünkü koşulun öğeleri ile grafiğin karşılık gelen öğeleri arasındaki karşılıkları bulmak kolay değildir. .

Bir taşıma problemini veya bir soy ağacı derleme problemini çözerken, grafik yönteminin kesinlikle ilginç, güzel ve görsel olduğu sonucuna vardım.

Grafiklerin ekonomide, yönetimde ve teknolojide yaygın olarak kullanıldığına ikna oldum. Grafik teorisi programlamada da kullanılır.Bu bu yazıda tartışılmadı, ama bunun sadece bir zaman meselesi olduğunu düşünüyorum.

Bu bilimsel çalışmada matematiksel grafikler, uygulama alanları ele alınmakta, çeşitli problemler grafikler yardımıyla çözülmektedir. Üretim yönetimi, işletme ile ilgili çeşitli alanlarda (örneğin, inşaat ağı diyagramı, posta dağıtım çizelgeleri) grafik teorisinin temelleri bilgisi gereklidir. Ayrıca bilimsel bir çalışma üzerinde çalışırken, bir WORD metin editöründe bilgisayarda çalışma konusunda ustalaştım. Böylece görevler bilimsel çalışma Tamamlandı.

Dolayısıyla, yukarıdakilerin hepsinden, ispatı bu çalışmanın amacı olan grafik teorisinin pratik değeri reddedilemez bir şekilde takip eder.

Edebiyat

Berge K. Grafik teorisi ve uygulamaları. -M.: IIL, 1962.

Kemeny J., Snell J., Thompson J. Sonlu matematiğe giriş. -M.: IIL, 1963.

cevher O. Grafikler ve uygulamaları. -M.: Mir, 1965.

Harry F. Grafik teorisi. -M.: Mir, 1973.

Zykov A.A. Sonlu Grafikler Teorisi. -Novosibirsk: Nauka, 1969.

Berezina L.Yu. Grafikler ve uygulamaları. -M.: Eğitim, 1979. -144 s.

"Soros Eğitim Dergisi" No. 11 1996 ("Düz Grafikler" Makalesi);

Gardner M. "Matematiksel boş zaman", M. "Mir", 1972 (bölüm 35);

Olekhnik S.N., Nesterenko Yu.V., Potapov M.K. "Eski eğlenceli problemler", M. "Nauka", 1988 (bölüm 2, bölüm 8; ek 4);

Pirinç. 6

Pirinç. 7

Pirinç. sekiz

uygulama

Pirinç. 14

uygulama

2016 akademik yılı Yıl

1. Giriş

2. Grafik teorisinin ortaya çıkış tarihi

3. Grafik teorisinin temel kavramları

4. Grafik teorisinin temel teoremleri

5. Bilgisayarda grafikleri temsil etme yolları

6. Grafik teorisindeki problemlere genel bakış

7. Karar

8. Referanslar

Tanıtım

Son zamanlarda, geleneksel olarak ayrık matematikle ilgili alanlardaki araştırmalar giderek daha fazla öne çıkmaktadır. Matematiksel analiz, diferansiyel denklemler gibi matematiğin klasik dallarıyla birlikte, müfredat uzmanlık "Uygulamalı Matematik" ve diğer birçok uzmanlık matematiksel mantık, cebir, kombinatorik ve çizge teorisi üzerine bölümler ortaya çıktı. Bunun nedenlerini anlamak zor değil, sadece bu matematiksel aparat temelinde çözülen problemlerin aralığını belirterek.

Grafik teorisinin ortaya çıkış tarihi.

1. Königsberg köprülerinin sorunu.Şek. Şekil 1, Pergol Nehri'nin iki kıyısı, iki ada ve yedi bağlantı köprüsü dahil olmak üzere Koenigsberg şehrinin (şimdi Kaliningrad) orta kısmının şematik bir planını göstermektedir. Görev, arazinin dört tarafını da dolaşarak, her köprüden bir kez geçmek ve başlangıç noktasına geri dönmek. Bu problem 1736 yılında Euler tarafından çözülmüştür (çözümün olmadığı gösterilmiştir).

pilav. bir

2. Üç ev ve üç kuyu sorunu. Uçakta bir şekilde yerleştirilmiş üç ev ve üç kuyu var. Yolların kesişmemesi için her evden her kuyuya bir yol çizin (Şekil 2). Bu sorun 1930'da Kuratovsky tarafından çözüldü (çözümün olmadığı gösterildi).

pilav. 2

3. Dört renk sorunu. Bir düzlemde kesişmeyen bölgelere bölünmeye harita denir. Bir haritadaki alanlara, varsa komşular denir. ortak sınır. Görev, haritayı, iki bitişik alan aynı renkle doldurulmayacak şekilde renklendirmektir (Şekil 3). Geçen yüzyılın sonundan beri, bunun için dört rengin yeterli olduğu hipotezi biliniyordu. 1976'da Appel ve Heiken, bilgisayar kullanarak seçeneklerin numaralandırılmasına dayanan dört renk sorununa bir çözüm yayınladı. Bu sorunun "programla" çözümü, hiçbir şekilde bitmeyen ateşli bir tartışmaya yol açan bir emsaldi. Yayınlanan çözümün özü, dört renk teoremine karşı büyük ama sonlu sayıda (yaklaşık 2000) potansiyel karşı örnek türünü sıralamak ve hiçbir durumun bir karşı örnek olmadığını göstermektir. Bu numaralandırma, program tarafından yaklaşık bin saatlik bir süper bilgisayar çalışmasında gerçekleştirildi. Elde edilen çözümü “manuel” olarak kontrol etmek imkansızdır - numaralandırma miktarı insan yeteneklerinin çok ötesine geçer. Birçok matematikçi şu soruyu gündeme getiriyor: Böyle bir "yazılım kanıtı" geçerli bir kanıt olarak kabul edilebilir mi? Sonuçta, programda hatalar olabilir ... Programların doğruluğunun resmi kanıt yöntemleri, tartışılan gibi karmaşık programlara uygulanamaz. Test, hataların bulunmadığını garanti edemez ve bu durumda bu kesinlikle imkansızdır. Bu nedenle, programcının yazarların niteliklerine güvenmek ve her şeyi doğru yaptıklarına inanmak kalır.

Pirinç. 3

Grafik teorisinin temel kavramları

1) Grafik G(V,E) iki kümenin bir koleksiyonudur - boş olmayan bir V kümesi (bir köşe kümesi) ve V kümesinin iki elemanlı alt kümelerinden oluşan bir E kümesi (E bir kenar kümesidir).

2) odaklı(x, y) biçimindeki sıralı köşe çiftlerinden oluşan bir grafiğe denir, burada x başlangıç ve y yayın sonu olarak adlandırılır. Bir yay (x, y) genellikle olarak yazılır. Ayrıca arkın x tepe noktasından y tepe noktasına ve y tepe noktasına gittiği söylenir. bitişiküst x ile.

3) E kümesinin bir elemanı bir çift olabilirse özdeş(farklı değil) V'nin elemanları, o zaman E kümesinin böyle bir elemanına denir döngü, ve grafik denir döngüler ile grafik(veya sözde yazı).

4) E bir küme değilse, ancak ayarlamak birkaç özdeş eleman içeriyorsa, bu elemanlara denir. çoklu kenarlar, ve grafik denir multigraf.

5) E kümesinin elemanları mutlaka iki elemanlı değil, V kümesinin herhangi bir alt kümesi ise, E kümesinin bu tür elemanlarına denir. hiperarklar, ve grafik denir hipergraf.

6) İşlev ayarlanmışsa F:V→M ve/veya F: E → M, ardından küme m küme denir notlar, ve grafik denir etiketli(veya yüklendi). Not kümesi olarak genellikle harfler veya tam sayılar kullanılır. eğer fonksiyon F injektiftir, yani farklı köşeler (kenarlar) farklı etiketlere sahiptir, o zaman grafik denir sayılı.

7) alt yazı G′(V′,E′), ve/veya grafı olarak adlandırılır.

a) V' = V ise, G' denir çekirdek alt yazı G.

b) ise, G grafiği denir sahip olmak G grafiğinin alt grafiği

c) Bir G'(V',E') alt grafiği, G', G'nin tüm olası kenarlarını içeriyorsa, G(V,E)'nin uygun bir alt grafiği olarak adlandırılır.

8) Derece (değerlik) köşeler, bu köşeye gelen kenarların sayısıdır (bu köşeye bitişik köşelerin sayısı).

9) rota Bir grafikte, herhangi iki bitişik öğenin geldiği alternatif bir köşe ve kenar dizisi denir.

a) ise, rota kapalı, aksi halde açık.

b) Tüm kenarlar farklıysa, rota denir. zincir.

c) Tüm köşeler (ve dolayısıyla kenarlar) farklıysa, rota denir. basit zincir.

d) Kapalı devre denir Çevrim.

e) Kapalı basit devre denir basit döngü.

f) Döngüleri olmayan bir grafiğe denir. asiklik.

g) Digraflar için zincir denir vasıtasıyla, ve döngü kontur.

pilav. 4. Rotalar, zincirler, döngüler

Örnek

Şeması Şekil 4'te gösterilen grafikte:

1. v 1 , v 3 , v 1 , v 4 - bir rota, ancak bir zincir değil;

2. v 1 , v 3 , v 5 , v 2 , v 3 , v 4 bir zincirdir, ancak basit bir zincir değildir;

3. v 1 , v 4 , v 3 , v 2 , v 5 basit bir zincirdir;

4. v 1 , v 3 , v 5 , v 2 , v 3 , v 4 , v 1 bir döngüdür, ancak basit bir döngü değildir;

5. v 1 , v 3 , v 4 , v 1 basit bir döngüdür.

10) Grafiğin tüm kenarlarını bir kez içeren bir döngü (mutlaka basit değil) varsa, böyle bir döngüye denir. EulerÇevrim.

11) Grafiğin tüm köşelerini (bir kez) içeren basit bir döngüsü varsa, böyle bir döngüye denir. HamiltoniyenÇevrim.

12) ağaççevrimsiz bağlantılı çizge denir.

13) Ostovom grafiğin tüm köşelerini içeren bir ağaç olarak adlandırılır.

14) Eşleştirme hiçbir ikisinin bitişik olmadığı bir kenar kümesidir.

15) Eşleştirme denir maksimum eğer hiçbir üst kümesi bağımsız değilse.

16) Bir grafikte iki köşe bağlı onları birbirine bağlayan basit bir zincir varsa.

17) Bütün köşeleri birbirine bağlı olan grafa denir. bağlı.

18) Yalnızca yalıtılmış köşelerden oluşan bir grafa denir. oldukça tutarsız.

19) Rota uzunluğu içindeki kenar sayısı olarak adlandırılır (tekrarlarla).

20) Mesafe u ve v köşeleri arasındaki en kısa zincirin uzunluğu olarak adlandırılır ve en kısa zincirin kendisine denir jeodezik.

21) çap grafik G en uzun jeodeziğin uzunluğudur.

22) eksantriklik bağlantılı bir G(V,E) grafiğindeki v tepe noktasının, bir v tepe noktasından G grafiğinin diğer köşelerine olan maksimum uzaklığıdır.

23) yarıçap G grafiğine köşelerin eksantrikliklerinin en küçüğü denir.

24) Vertex v denir merkezi, eksantrikliği grafiğin yarıçapı ile çakışıyorsa.

25) Merkezi köşeler kümesine denir. merkez grafik.