1736, Königsberg. Pregelya Nehri şehrin içinden akıyor. Şehirde yukarıdaki şekilde görüldüğü gibi yedi adet köprü bulunmaktadır. Antik çağlardan beri Königsberg sakinleri bir bilmeceyle uğraşmışlardır: Her köprüden yalnızca bir kez yürüyerek tüm köprüleri geçmek mümkün müdür? Bu sorun hem teorik olarak kağıt üzerinde hem de pratikte bu köprülerden geçen yürüyüşlerde çözüldü. Kimse bunun imkansız olduğunu kanıtlayamadı ama kimse köprüler arasında bu kadar "gizemli" bir yürüyüş yapamadı.

Ünlü matematikçi Leonhard Euler problemi çözmeyi başardı. Üstelik sadece bu özel sorunu çözmekle kalmadı, benzer sorunları çözmek için genel bir yöntem de buldu. Euler, Königsberg köprüleri sorununu çözerken şu şekilde ilerledi: Araziyi noktalar halinde "sıkıştırdı" ve köprüleri çizgiler halinde "gerdi". Noktalardan ve bu noktaları birleştiren doğrulardan oluşan böyle bir şekle denir. SAYMAK.

Grafik, boş olmayan bir köşe kümesi ve köşeler arasındaki bağlantılardan oluşan bir koleksiyondur. Dairelere grafiğin köşeleri, ok içeren çizgilere yay, ok içermeyen çizgilere ise kenar denir.

Grafik türleri:

1. Yönlendirilmiş grafik(kısaca digraf) - kenarlarına bir yön atanan.

2. Yönlendirilmemiş grafikçizgilerin yönü olmayan bir grafiktir.

3. Ağırlıklı grafik– yayların veya kenarların ağırlığı vardır (ek bilgi).

Grafikleri kullanarak problemleri çözme:

Görev 1.

Çözüm: Bilim adamlarını grafiğin köşeleri olarak gösterelim ve her köşeden diğer dört köşeye doğrular çizelim. El sıkışma sayılacak 10 satır alıyoruz.

Görev 2.

Okul sahasında 8 ağaç büyüyor: elma ağacı, kavak, huş ağacı, üvez, meşe, akçaağaç, karaçam ve çam. Üvez karaçamdan daha yüksektir, elma ağacı akçaağaçtan daha yüksektir, meşe huş ağacından daha alçaktır ancak çamdan daha yüksektir, çam üvezden daha yüksektir, huş ağacı kavaktan daha alçaktır ve karaçam elma ağacından daha yüksektir. Ağaçları en kısadan en uzuna doğru sıralayın.

Çözüm:

Grafiğin köşeleri ağaç adının ilk harfiyle gösterilen ağaçlardır. Bu görevde iki ilişki vardır: “aşağıda olmak” ve “yukarıda olmak”. "Aşağıda olma" ilişkisini göz önünde bulundurun ve aşağıdaki ağaçtan yukarıya doğru oklar çizin. Sorun, üvezin karaçamdan daha uzun olduğunu söylüyorsa, o zaman karaçamdan üveze vb. bir ok koyarız. En kısa ağacın akçaağaç olduğunu, ardından elma, karaçam, üvez, çam, meşe, huş ağacı ve kavağın geldiğini gösteren bir grafik elde ediyoruz.

Görev 3.

Natasha'nın 2 zarfı var: normal ve hava ve 3 pul: dikdörtgen, kare ve üçgen. Natasha bir mektubu göndermek için bir zarf ve pulu kaç farklı şekilde seçebilir?

Çözüm:

Aşağıda görevlerin bir dökümü bulunmaktadır.

BELEDİYE ÖZERK EĞİTİM KURUMU 2 Nolu ORTAOKUL

Tedarikli

Legkokonets Vladislav, 10A sınıfı öğrencisi

Grafik Teorisinin pratik uygulaması

Süpervizör

L.I. Noskova, matematik öğretmeni

Sanat Bryukhovetskaya

2011

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

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

3. Graf teorisinin temel tanımları ve teoremleri……………………………….………6

4. Grafikler kullanılarak çözülen problemler……………………………..………………………..8

4.1 Ünlü problemler………………………………….…………………………8

4.2 Birkaç ilginç problem………………………………….……………..9

5. Grafiklerin insanların yaşamının çeşitli alanlarına uygulanması…………………………………11

6. Sorunları çözmek……………………………………………………………………………………………12

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

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

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

giriiş

Bulmaca çözmekten ve eğlenceli oyunlardan doğan grafik teorisi, artık çok çeşitli problemlerle ilgili soruları çözmek için basit, erişilebilir ve güçlü bir araç haline geldi. Grafikler kelimenin tam anlamıyla her yerde mevcuttur. Grafikler biçiminde, örneğin yol haritalarını ve elektrik devrelerini, coğrafi haritaları ve kimyasal bileşik moleküllerini, insanlar ve insan grupları arasındaki bağlantıları yorumlayabilirsiniz. Geçtiğimiz 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 talepleri tarafından yönlendirilmektedir. Entegre devrelerin ve kontrol devrelerinin tasarımında, otomatların, mantıksal devrelerin, program blok diyagramlarının incelenmesinde, ekonomi ve istatistik, kimya ve biyolojide, planlama teorisinde kullanılır. Bu yüzden alaka Konu, bir yandan grafiklerin ve ilgili araştırma yöntemlerinin popülaritesi, diğer yandan bunun uygulanması için gelişmemiş, bütünsel bir sistem tarafından belirlenmektedir.

Hayattaki birçok problemi çözmek uzun hesaplamalar gerektirir ve bazen bu hesaplamalar bile başarı getirmez. Bu nedir Araştırma problemi. Şu soru ortaya çıkıyor: Bunları çözmek için basit, akılcı, kısa ve zarif bir çözüm bulmak mümkün mü? Grafik kullanırsanız problem çözmek daha mı kolay olur? Bu belirlendi araştırmamın konusu: “Grafik teorisinin pratik uygulaması”

Amaç Araştırma, pratik sorunların nasıl hızla çözüleceğini öğrenmek için grafikleri kullanmaktı.

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

Araştırma hedefleri:

1. Bu konuyla ilgili literatürü ve İnternet kaynaklarını inceleyin.

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

3. Bir sonuç çıkarın.

Çalışmanın pratik önemi sonuçların şüphesiz birçok insanın ilgisini çekeceğidir. Hiçbiriniz soy ağacınızı oluşturmaya çalışmadınız mı? Bu nasıl doğru şekilde yapılır? Bir ulaştırma işletmesinin başkanı, malları bir varış noktasından çeşitli yerleşim yerlerine taşırken muhtemelen ulaşımın daha karlı kullanılması sorununu çözmek zorundadır. Her okul çocuğu mantıksal kan nakli sorunlarıyla karşı karşıya kalmıştır. Grafikler kullanılarak kolayca çözülebilecekleri ortaya çıktı.

Çalışmada aşağıdaki yöntemler kullanılmaktadır: gözlem, araştırma, seçme, analiz.

Grafik teorisinin tarihi

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

“Bir zamanlar Königsberg şehrinde bulunan ve etrafı yedi köprüyle çevrili bir nehirle çevrili bir adayla ilgili bir problemle karşılaştım.

[Ek Şekil 1] Soru, birisinin her köprüden yalnızca bir kez geçerek sürekli olarak onların etrafından dolaşıp dolaşamayacağıdır. Daha sonra bana bunu henüz kimsenin başaramadığı ancak kimsenin bunun imkansız olduğunu kanıtlamadığı bilgisi verildi. Bu soru her ne kadar önemsiz olsa da bana ilgiye değer göründü, çünkü ne geometri, ne cebir, ne de kombinatoryal sanat bu soruyu çözmeye yeterli değildi. Çok düşündükten sonra, tamamen ikna edici bir kanıta dayanan kolay bir kural buldum; bunun yardımıyla, bu tür tüm problemlerde, böyle bir dolambaçlı yolun herhangi bir sayıda ve herhangi bir sayıda köprüden geçip geçemeyeceğini hemen belirlemek mümkündür. ya da değil. Koenigsberg köprüleri aşağıdaki şekilde gösterilebilecek şekilde konumlandırılmıştır. [Ek Şekil 2] A'nın bir adayı temsil ettiği ve B, C ve D'nin kıtanın nehir kolları ile ayrılmış kısımları olduğu

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

"Bu çözümün, doğası gereği, görünüşe göre matematikle çok az ilgisi var ve bu çözümün neden başka bir kişiden değil de bir matematikçiden beklenmesi gerektiğini anlamıyorum, çünkü bu karar yalnızca akıl yürütmeyle destekleniyor ve bu çözümün hiçbir yolu yok." Bu çözümü bulmak için matematiğin doğasında bulunan herhangi bir yasayı dahil etmemiz gerekiyor. Dolayısıyla, matematikle çok az ilgisi olan soruların matematikçiler tarafından diğerlerinden daha fazla çözülme ihtimalinin nasıl ortaya çıktığını bilmiyorum."

Peki Königsberg köprülerinin her birinden yalnızca bir kez geçerek geçmek mümkün mü? Cevabı bulmak için Euler'in Marinoni'ye mektubuna devam edelim:

"Soru, bu yedi köprünün tamamının her birinden yalnızca bir kez geçerek bypass edilmesinin mümkün olup olmadığını belirlemektir. Benim kuralım bu soruyu şu çözüme götürüyor. Öncelikle orada kaç alan olduğuna bakmanız gerekiyor. su ile ayrılmışlardır - bir köprü dışında birinden diğerine başka geçişi olmayanlar. Bu örnekte, bu tür dört bölüm vardır - A, B, C, D. Daha sonra, sayının olup olmadığını ayırt etmeniz gerekir. Bu ayrı bölümlere giden köprülerin sayısı çift veya tektir.Yani bizim durumumuzda A bölümüne beş köprü ve geri kalanlara üçer köprü gidiyor, yani Bireysel bölümlere giden köprülerin sayısı tektir ve bu tek başına yeterlidir Sorunu çözmek için Bu belirlendikten sonra şu kuralı uygularız: Her ayrı bölüme giden köprülerin sayısı eşit olsaydı, o zaman söz konusu dolambaçlı yol mümkün olurdu ve aynı zamanda bunu başlatmak da mümkün olurdu. Bununla birlikte, bu sayılardan ikisi tek ise, çünkü yalnızca biri tek olamaz, o zaman bile geçiş, belirtildiği gibi tamamlanabilir, ancak kesinlikle dolambaçlı yolun yalnızca başlangıcı alınmalıdır. tek sayıda köprünün çıktığı iki bölümden biri. Son olarak, tek sayıda köprünün çıktığı ikiden fazla bölüm varsa, o zaman böyle bir hareket genellikle imkansızdır ... eğer buraya daha ciddi sorunlar getirilebilirse, bu yöntem daha da büyük fayda sağlayabilir ve kullanılmalıdır. ihmal edilmemelidir."

Grafik teorisinin temel tanımları ve teoremleri

Graf teorisi matematikçilerin çabalarıyla oluşturulmuş bir matematik disiplinidir, bu nedenle sunumu gerekli katı tanımları içerir. Öyleyse, bu teorinin temel kavramlarının düzenli bir şekilde tanıtılmasına devam edelim.

Tanım 1. Grafik, grafiğin köşeleri adı verilen sonlu sayıda noktanın ve bu köşelerden bazılarını birbirine bağlayan, grafiğin kenarları veya yayları adı verilen ikili çizgilerin bir koleksiyonudur.

Bu tanım farklı şekilde formüle edilebilir: Bir grafik, her iki ucu da belirli bir nokta kümesine ait olan, boş olmayan bir nokta (köşe) ve parça (kenar) kümesidir.

Aşağıda grafiğin köşelerini A, B, C, D Latin harfleriyle göstereceğiz. Bazen grafiğin tamamı bir büyük harfle gösterilir.

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

Tanım 3. Yalnızca yalıtılmış köşelerden oluşan bir grafiğe null denir - saymak .

Gösterim: O "– kenarları olmayan köşelere sahip bir grafik

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

Tanım: U" – n adet köşe ve bu köşelerin olası tüm çiftlerini birbirine bağlayan 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, o tepe noktasının ait olduğu kenarların sayısıdır.

Tanım 6. Tüm k köşelerinin dereceleri aynı olan grafiğe homojen derece grafiği denir. .

Tanım 7. Belirli bir grafiğin tamamlayıcısı, 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 gösterilebilen bir grafiğe düzlemsel denir.

Tanım 9. Grafiğin herhangi bir köşesini veya kenarını içermeyen düzlemsel bir grafiğin çokgenine yüzü denir.

Düzlemsel grafik ve grafik yüzü kavramları, çeşitli haritaların “doğru” renklendirilmesiyle ilgili problemleri çözerken kullanılır.

Tanım 10. A'dan X'e yol, A'dan X'e uzanan, her iki bitişik kenarın ortak bir tepe noktasına sahip olduğu ve hiçbir kenarın birden fazla oluşmadığı bir kenar dizisidir.

Tanım 11. Döngü, başlangıç ​​ve bitiş noktalarının çakıştığı bir yoldur.

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

Tanım 13. Yolun uzunluğu , bir döngüye yerleştirildi , bu yolun kenar sayısına denir.

Tanım 14. Bir grafikteki iki A ve B köşesi, A'dan B'ye giden bir yol varsa (mevcut değilse) bağlantılı (bağlantısız) olarak adlandırılır.

Tanım 15. Bir grafın her iki köşesi bağlantılıysa bağlantılı olarak adlandırılır; Grafik en az bir çift bağlantısız köşe içeriyorsa, grafiğe bağlantısız denir.

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

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

Tanım 17. Tamamen ağaçlardan oluşan bağlantısız bir grafiğe orman denir.

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

Böylece, grafik teorisinin temel tanımlarını inceledik; bunlar olmadan teoremleri kanıtlamanın ve dolayısıyla problemleri çözmenin imkansız olacağı.

Grafikler kullanılarak çözülen problemler

Ünlü sorunlar

Gezgin satıcı problemi

Gezgin satıcı problemi kombinatorik teorisindeki ünlü problemlerden biridir. 1934 yılında ortaya atıldı ve en iyi matematikçiler bu konuda dişlerini kırdılar.

Sorun ifadesi aşağıdaki gibidir.
Gezgin bir satıcının (gezgin tüccar) ilk şehri terk etmesi, 2,1,3..n şehirlerini bilinmeyen bir sırayla ziyaret etmesi ve ilk şehre geri dönmesi gerekir. Şehirler arası mesafeler biliniyor. Gezgin bir satıcının kapalı yolunun (turunun) en kısa olması için şehirlerde hangi sırayla dolaşılmalıdır?

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üğün bedelini ağır bir şekilde ödemek zorunda kalırsınız.
Örneğin şekildeki ağı düşünün [Ek Şekil 3], dar bir eşkenar dörtgeni temsil ediyor. Gezgin bir satıcının 1. şehirden başlamasına izin verin. "En yakın şehre git" algoritması onu 2. şehre, sonra 3. şehre, sonra 4. şehre götürecektir; son adımda, elmasın uzun köşegeni boyunca geri dönerek açgözlülüğünüzü ödemek zorunda kalacaksınız. Sonuç en kısa değil en uzun tur olacak.

Königsberg köprüleriyle ilgili sorun.

Sorun şu şekilde formüle edilmiştir.
Koenigsberg şehri, Pregel Nehri'nin ve iki adanın kıyısında yer almaktadır. Şehrin farklı bölgeleri yedi köprüyle birbirine bağlanıyordu. Pazar günleri kasaba halkı şehirde yürüyüşe çıktı. Soru: Evden çıktığınızda her köprüden tam olarak bir kez yürüyerek geri dönebileceğiniz şekilde yürüyüş yapmak mümkün müdür?
Pregel Nehri üzerindeki köprüler resimdeki gibi yerleştirilmiştir[Ek Şekil 1].

Köprü diyagramına karşılık gelen grafiği düşünün [Ek Şekil 2].

Sorunun sorusunu cevaplamak için grafiğin Eulerian olup olmadığını öğrenmek yeterlidir. (En az bir tepe noktasından çift sayıda köprü uzanmalıdır). Şehri dolaşıp tüm köprüleri bir kez geçip geri dönemezsiniz.

Birkaç ilginç görev

1. "Rotalar".

Sorun 1

Hatırladığınız gibi, ölü ruhların avcısı Chichikov, ünlü toprak sahiplerini birer kez ziyaret etti. Onları şu sırayla ziyaret etti: Manilov, Korobochka, Nozdryov, 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 konumlarını çizdiği bir diyagram bulundu. Chichikov yollardan herhangi birini birden fazla kullanmadıysa, hangi mülkün kime ait olduğunu belirleyin [Ek Şekil 4].

Çözüm:

Yol haritası, Chichikov'un yolculuğuna E mülkünden başladığını ve O mülküyle sona erdiğini gösteriyor. B ve C mülklerine yalnızca iki yolun çıktığını, dolayısıyla Chichikov'un bu yollar boyunca seyahat etmek zorunda kaldığını not ediyoruz. Bunları kalın bir çizgiyle işaretleyelim. A'dan geçen güzergahın bölümleri belirlendi: AC ve AB. Chichikov, AE, AK ve AM yollarında seyahat etmedi. Hadi bunların üzerini çizelim. Kalın çizgiyle ED işaretleyelim; DK'nin üstünü çizelim. MO ve MN'nin üzerini çizelim; Kalın çizgiyle işaretleyelim MF; FO'nun üzerini çizin; FH, NK ve KO'yu kalın çizgiyle işaretleyelim. Bu koşul altında mümkün olan tek rotayı bulalım. Ve şunu elde ediyoruz: E - Manilov, D - Korobochka, C - Nozdryov, A - Sobakevich, B - Plyushkin, M - Tentetnikov, F - Betrishchev, N - Petukh, K - Konstanzholgo, O - Koshkarev'e ait [Ek Şekil 5].

Sorun 2

Şekil bölgenin haritasını göstermektedir [Ek Şekil 6].

Sadece okların yönünde hareket edebilirsiniz. Her noktayı en fazla bir kez ziyaret edebilirsiniz. 1. noktadan 9. noktaya kaç farklı yoldan ulaşabilirsiniz? Hangi rota en kısa, hangisi en uzun.

Çözüm:

Devreyi 1. köşeden başlayarak sırayla bir ağaca "katmanlaştırıyoruz" [Ek Şekil 7]. Bir ağaç alalım. 1'den 9'a kadar olan olası yolların sayısı, ağacın "asılı" köşelerinin sayısına eşittir (bunlardan 14 tane 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"

Sorun 1

Müzik festivalinin katılımcıları tanışarak zarfları adreslerle değiştirdiler. Kanıtla:

a) çift sayıda zarf teslim edildi;

b) Tek sayıda zarf alışverişinde bulunan katılımcıların sayısı çifttir.

Çözüm: Festival katılımcıları A 1, A 2, A 3 olsun. . . , Ve n, grafiğin köşe noktalarıdır ve kenarlar, zarf alışverişi yapan adamları temsil eden köşe çiftlerini birleştirir [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 = derece. 1 + adım. bir 2++. . . + adım. Bir n -1 + derece. Ve n, N =2p, burada p grafiğin kenar sayısıdır, yani. N – çift. Sonuç olarak çift sayıda zarf teslim edildi;

b) eşitlikte N = derece. 1 + adım. bir 2++. . . + adım. Bir n -1 + derece. Ve n tek terimlerin toplamı çift olmalıdır ve bu da ancak tek terimlerin sayısı çift olduğunda olabilir. Bu, tek sayıda zarf alışverişinde bulunan katılımcıların sayısının çift olduğu anlamına gelir.

Sorun 2

Bir gün Andrei, Boris, Volodya, Dasha ve Galya akşam sinemaya gitmeyi kabul ettiler. Sinema ve gösteri seçimini telefonla koordine etmeye karar verdiler. Ayrıca birine telefonla ulaşılamaması durumunda sinema gezisinin iptal edilmesine karar verildi. Akşam herkes sinemada toplanamadığı için sinema ziyareti iptal edildi. Ertesi gün kimin kimi aradığını bulmaya 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 çağırdığı ortaya çıktı. Kim telefona ulaşamadı ve bu nedenle toplantıya gelmedi?

Çözüm:

Beş nokta çizip üzerlerine A, B, C, D, D harfleriyle etiketleyelim. Bunlar isimlerin ilk harfleridir. Arayan adamların isimlerine karşılık gelen noktaları birleştirelim.

[Ek Şekil 9]

Resimden her birinin - Andrey, Boris ve Volodya'nın - herkese telefon ettiği açık. Bu adamlar bu yüzden sinemaya geldiler. Ancak Galya ve Dasha birbirleriyle telefona ulaşamadılar (G ve E noktaları bir çizgi parçasıyla birbirine bağlı değil) ve bu nedenle anlaşma uyarınca sinemaya gelmediler.

Grafiklerin insanların yaşamlarının çeşitli alanlarına uygulanması

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 üretimin otomasyonu, psikoloji ve reklamcılık alanlarında yaygın olarak kullanılmaktadır. Dolayısıyla, yukarıdakilerin hepsinden, grafik teorisinin pratik değeri inkar edilemez bir şekilde ortaya çıkıyor ve bunun kanıtı bu çalışmanın amacıydı.

Bilim ve teknolojinin herhangi bir alanında grafiklerle karşılaşırsınız. Grafikler, matematiksel, ekonomik ve mantıksal problemleri, çeşitli bulmacaları çözebileceğiniz ve fizik, kimya, elektronik ve otomasyondaki problemlerin koşullarını basitleştirebileceğiniz harika matematiksel nesnelerdir. Pek çok matematiksel gerçek, grafik dilinde rahatlıkla formüle edilebilir. Graf teorisi birçok bilimin bir parçasıdır. Graf teorisi en güzel ve görsel matematik teorilerinden biridir. Son zamanlarda, grafik teorisi uygulamalı konularda giderek daha fazla uygulama buluyor. Grafik teorisinin uygulanmasına dayanan nispeten genç bir kimya alanı olan hesaplamalı kimya bile ortaya çıktı.

Moleküler grafikler Stereokimya ve yapısal topolojide, kümelerin kimyasında, polimerlerde vb. kullanılan, moleküllerin yapısını gösteren yönlendirilmemiş grafiklerdir. [Ek Şekil 10]. Bu grafiklerin köşeleri ve kenarları karşılık gelen atomlara ve aralarındaki kimyasal bağlara karşılık gelir.

Moleküler grafikler ve ağaçlar: [Ek Şekil 10] a, b - sırasıyla çoklu grafikler. etilen ve formaldehit; onlar söylüyor pentan izomerleri (ağaç 4, 5, ağaç 2'ye izomorfiktir).

Organizmaların stereokimyasında en çok. Moleküler ağaçlar sıklıkla kullanılır - 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ın izomorfizmalarının kurulması ve bunların belirlenmesini mümkün kıldıklarını söylüyorlar. alkanların, alkenlerin ve alkinlerin toplam izomer sayısını bulun

Protein ağları

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

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 yolun bulunmasıdır. Ağaç döngüler veya döngüler içermez.

Tipik olarak hiyerarşik bir sistemi temsil eden bir ağacın, ağacın kökü adı verilen bir ana tepe noktası vardır. Ağacın her köşesinin (kök hariç) yalnızca bir atası vardır; onun tarafından belirlenen nesne, bir üst düzey sınıfa dahil edilir. Bir ağacın herhangi bir tepe noktası, daha düşük düzeydeki sınıflara karşılık gelen birkaç alt öğe üretebilir.

Her bir ağaç köşesi çifti için onları birbirine bağlayan benzersiz bir yol vardır. Bu özellik, soyağacı grafik teorisi anlamında bir "ağaç" olan bir aile ağacı biçiminde temsil edilen herhangi bir kişinin örneğin erkek soyundaki tüm atalarını bulurken kullanılır.

Aile ağacımın örneği [Ek Şekil 12].

Bir örnek daha. Resimde İncil'deki aile ağacı gösterilmektedir [Ek Şekil 13].

Problem çözme

1. Taşıma görevi. Krasnodar şehrinde, Krymsk, Temryuk, Slavyansk-on-Kuban ve Timashevsk şehirlerine tek seferde dağıtılması gereken hammaddelerin bulunduğu bir üs olsun, mümkün olduğunca az zaman ve yakıt harcayıp Krasnodar'a geri dönün. .

Çözüm:

Öncelikle olası tüm seyahat rotalarının bir grafiğini oluşturalım [Ek Şekil 14] bu yerleşim yerleri arasındaki gerçek yollar ve aralarındaki mesafe dikkate alınarak. Bu sorunu çözmek için ağaç benzeri başka bir grafik oluşturmamız gerekiyor. [Ek Şekil 15].

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

Sonuç 24 çözümdür, ancak yalnızca en kısa yollara ihtiyacımız var. Tüm çözümlerden sadece ikisi tatmin edicidir, bu 350 km'dir.

Benzer şekilde, bir bölgeden diğerine gerçek ulaşımın hesaplanması da mümkün ve bence gerekli.

Transfüzyonla ilgili mantıksal problem. Kovada 8 litre su, 5 ve 3 litre kapasiteli iki adet tava bulunmaktadır. Beş litrelik tavaya 4 litre su döküp kovada 4 litre bırakmanız yani suyu kovaya ve geniş bir tavaya eşit miktarda dökmeniz gerekiyor.

Çözüm:

Her anki durum üç rakamla açıklanabilir [Ek Şekil 16].

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

Çözüm

Yani problemlerin nasıl çözüleceğini öğrenmek için onların ne olduğunu, nasıl yapılandırıldığını, hangi bileşenlerden oluştuğunu, problemlerin çözüldüğü araçların neler olduğunu anlamanız gerekir.

Grafik teorisini kullanarak pratik problemleri çözerken, çözümlerinin her aşamasında, her aşamasında yaratıcılığın uygulanmasının gerekli olduğu ortaya çıktı.

En başından beri, ilk aşamada sorunun durumunu analiz edebilmeniz ve 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 unsuru çok önemlidir, çünkü koşulun unsurları ile koşulun karşılık gelen unsurları arasındaki yazışmaları bulmak kolay olmaktan çok uzaktır. grafik.

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

Grafiklerin ekonomi, yönetim ve teknolojide yaygın olarak kullanıldığına ikna oldum. Grafik teorisi programlamada da kullanılıyor, bu çalışmada bu konu tartışılmadı, ancak bunun sadece bir zaman meselesi olduğunu düşünüyorum.

Bu bilimsel çalışma matematiksel grafikleri, uygulama alanlarını incelemekte ve grafikleri kullanarak çeşitli problemleri çözmektedir. Üretim ve iş yönetimi ile ilgili çeşitli alanlarda (örneğin, ağ oluşturma programı, posta dağıtım programları) grafik teorisinin temelleri bilgisi gereklidir. Ayrıca bilimsel bir makale üzerinde çalışırken WORD metin editörünü kullanarak bilgisayarda çalışma konusunda ustalaştım. Böylece bilimsel çalışmanın hedeflerine ulaşılmıştır.

Dolayısıyla, yukarıdakilerin hepsinden, grafik teorisinin pratik değeri inkar edilemez bir şekilde ortaya çıkıyor ve bunun kanıtı bu çalışmanın amacıydı.

Edebiyat

Berge K. Graf 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.

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

Zykov A.A. Sonlu grafik teorisi. -Novosibirsk: Bilim, 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 eğlence", M. "Dünya", 1972 (bölüm 35);

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

Başvuru

Başvuru

P

Pirinç. 6

Pirinç. 7

Pirinç. 8

başvuru

Başvuru

Başvuru

Başvuru

P

Pirinç. 14

başvuru

Başvuru

Mantıksal problemlerin çözümüyle ilgili problemler arasında, son yıllarda araştırmacıların yakın ilgisi, grafik teorisinin bu tür problemlere uygulanması sorusu üzerine yoğunlaşmıştır.

Graf teorisi şu anda ayrık matematiğin yoğun olarak gelişen bir dalıdır. Bu, birçok nesnenin ve durumun grafik modelleri biçiminde tanımlanmasıyla açıklanmaktadır: iletişim ağları, elektrikli ve elektronik cihaz devreleri, kimyasal moleküller, insanlar arasındaki ilişkiler ve çok daha fazlası.

Grafik görevlerinin, hayal gücünü geliştirmek ve mantıksal düşünmeyi geliştirmek için kullanılmalarına olanak tanıyan bir takım avantajları vardır. Grafik problemleri eğlenceli ve eğlenceli bir biçimde sunulabilir.

Araştırma konusu Bu çalışmada mantıksal problemlerin grafikleri kullanarak çözümü yer almaktadır.

Bu çalışmanın amacı: Mantıksal problemleri çözmek için grafik aygıtını uygular.

Hipotez: Bizce birçok mantıksal problemin çözümü daha az emek gerektiren bir işlem olacaktır; bunun için çizge teorisini kullanacağız.

Araştırma hedefleri:

grafikleri kullanarak problemleri çözmeyi düşünün;

problemleri grafik diline çevirmeyi öğrenin;

Geleneksel problem çözme yöntemlerini grafik teorisi yöntemleriyle karşılaştırır.

1736 yılında büyük matematikçi Leonhard Euler, Königsberg Köprüsü Problemi adı verilen bilmeceye bir çözüm buldu. Kaliningrad'ın (eskiden şehrin adı Königsberg) içinden geçen Pregel Nehri iki adayı yıkar (Şekil 1 Şekil 1). Euler'in zamanında nehrin kıyıları ile adalar şekilde görüldüğü gibi köprülerle birbirine bağlanıyordu. Bulmaca, dört kara kütlesinin hepsinden bir kez geçen bir rota bulmayı gerektiriyordu ve yolun sonu ve başlangıcı çakışmalıdır.

Resim 1

L. Euler, bulmacanın koşullarını sağlayacak bir rotanın olmadığını kanıtladı ve bu tür bulmacanın çözümüne yönelik bir teori geliştirdi. “Grafiklere Giriş” dersinin giriş kısmındaki materyali bilmek, L. Euler'in akıl yürütme fikrini yeniden oluşturmak zor değildir. Bunu yapmak için öncelikle Şekil 1'i, adaların ve kıyıların noktalarla temsil edildiği Şekil 2'de gösterilen diyagramla değiştirmeniz gerekir.

şekil 2

Şekil 2'de gösterilen diyagram, kesin olarak bir grafik değildir: birden fazla kenarı vardır. Ancak bu bulmacanın çözüldüğü 1736 yılı genel olarak grafik teorisinin doğduğu yıl olarak kabul edilir.

Yüz yıldan fazla bir süre sonra, 1874'te Alman bilim adamı G. Kirchhoff, daha sonra grafik teorisinde vatandaşlık hakkı kazanan yöntem ve kavramları kullanarak, bir elektrik devresindeki akımın değerini belirlemek için etkili bir yöntem geliştirdi. Başka bir 10 yıl sonra, İngiliz matematikçi A. Keli (annesi Rus'tu, Rusça konuşuyordu ve Rus matematik literatürünü takip ediyordu; en başından beri N.I. Lobaçevski'nin fikirlerini anlayan ve destekleyen az sayıda matematikçiden biriydi) teorisini geliştirdi. Belirli bir sayıya sahip doymuş hidrokarbonların izomerlerinin sayısını saymak için ağaçlar N karbon atomları.

Matematikte bir grafik, köşe adı verilen noktaların sonlu bir koleksiyonudur; hangisinin birbirine grafik kenarları adı verilen çizgilerle bağlı olduğu.

Grafik, bir düzlem üzerinde (kağıt, tahta) gösterilen ve bazı çiftleri çizgilerle birbirine bağlanan bir dizi noktadır. Noktalara grafiğin köşeleri, çizgilere ise kenarlar denir. Bir tepe noktasının derecesi, tepe noktasından çıkan kenarların sayısıdır.

Coğrafi bir haritaya baktığınızda demiryolu ağı hemen gözünüze çarpıyor. Bu tipik bir grafiktir: daireler grafiğin köşeleri olan istasyonları, bunları bağlayan yollar ise kenarları temsil eder.

Figür 3

Şekil 3'teki grafik M, A, B, C ve D köyleri arasındaki yolların diyagramını göstermektedir. Burada her iki köşe bir kenarla birbirine bağlanmıştır. Böyle bir grafiğe tam denir. Şekildeki sayılar bu yollar üzerindeki köyler arasındaki mesafeleri göstermektedir. M köyünde bir postane olsun ve postacı diğer dört köye mektup dağıtsın. Birçok farklı seyahat rotası var. En kısa olanı nasıl seçilir? En kolay yol tüm seçenekleri analiz etmektir. Yeni bir grafik bunu yapmanıza yardımcı olacak ve olası rotaları görmenizi kolaylaştıracak. En üstteki M zirvesi rotaların başlangıcıdır. Buradan yolculuğa dört farklı şekilde başlayabilirsiniz: A'ya, B'ye, C'ye veya D'ye. Köylerden birini ziyaret ettikten sonra rotaya devam etmek için üç seçenek vardır, ardından iki, ardından son köye giden yol. ve tekrar M'ye. Toplam 43 21  24 yol.

Malları mağazalara ve malzemeleri şantiyelere dağıtmak için en iyi seçenekleri bulurken de benzer sorunlar sıklıkla ortaya çıkar.

En basit sorunlardan birini düşünün: “Kırmızı, mavi, sarı ve yeşil kalemler teker teker dört kutudadır. Kalemin rengi kutunun renginden farklıdır. Yeşil kalemin mavi kutuda olduğu, kırmızı kalemin ise sarı kutuda olmadığı bilinmektedir. Her kalem hangi kutuya giriyor?"

Kalemleri ve kutuları noktalarla gösterelim. Düz çizgi, kalemin ilgili kutuda olduğunu, noktalı çizgi ise olmadığını gösterir. Daha sonra sorunu dikkate alarak, G 1 (Şekil 4).

Şekil 4

Daha sonra grafiği aşağıdaki kurala göre tamamlıyoruz: Kutunun içinde tam olarak bir kalem bulunabileceğinden, her noktadan bir düz çizgi ve üç nokta çıkmalıdır. Sonuç bir grafiktir G 2 , bu da soruna bir çözüm sağlar.

Popüler bilim ve metodolojik literatürde genellikle mantıksal olarak adlandırılan problemleri çözerken, kural olarak okul bilgi ve becerilerine önemli bir şekilde güvenmezler. Bu bağlamda, geleneksel olarak bir yaratıcılık ölçüsü, matematiksel yetenek seviyesinin, düşünme keskinliğinin, hafızayı kullanma yeteneğinin bir göstergesi olarak kabul edilirler ve genellikle okul matematik kulüplerinde tartışılırlar.

Grafikleri kullanarak birçok mantıksal problemi çözmek, genç öğrenciler için oldukça erişilebilirdir. Bunu yapmak için, grafikleri ve onların en belirgin özelliklerini yalnızca sezgisel olarak anlamaları yeterlidir.

Bazı iyi bilinen problemleri çözmek için grafik kullanma örneklerine bakalım. Bu durumda, nesneleri noktalarla ve aralarındaki ilişkileri bölümlerle temsil edeceğiz (noktaların konumları ve bölümlerin uzunlukları isteğe bağlıdır).

Mantıksal problemlerin yapılarının uygulanan çözüm yöntemleri açısından açıklığa kavuşturulması, bu tür problemlerin belirli sınıflarının izole edilmesini mümkün kılar.

Görev 1. Üç arkadaş konuşuyor: Belokurov, Chernov ve Ryzhov. Esmer Belokurov'a şunları söyledi: "Birimizin sarışın, diğerimizin esmer, üçüncümüzün kızıl olması ilginç ama kimsenin saç rengi soyadına uymuyor." Arkadaşlarınızdan her birinin saç rengi nedir?

Detaylı bir çözüm verelim. Problem ifadesinde belirtilen ilişkinin grafiğini oluşturalım. Bunu yapmak için öncelikle birçok soyadını vurgulayalım M ve birçok saç rengi İLE, elemanları noktalarla gösterilecektir. Set sayıları M onlara B, Ch, R (Belokurov, Chernov ve Ryzhov) harfleri diyelim; ikinci setin puanları - b, br, p (sarışın, esmer, kırmızı). Bir kümedeki bir nokta diğerindeki bir noktaya karşılık geliyorsa, onları düz bir çizgiyle, uyuşmuyorsa kesikli bir çizgiyle birleştireceğiz. Sorunun durumu yalnızca tutarsızlıkları gösterir, bu nedenle öncelikle Şekil 5'te gösterilen grafiğin görünmesi gerekir.

Şekil 5

Sorunun koşullarından şu sonuç çıkar: kümedeki her nokta için M birçok tonkadan yalnızca bir tane var İLE, bu, birinciye ve tersine kümedeki her noktaya karşılık gelir İLE kümeden yalnızca bir noktaya karşılık gelir M. Görev, kümelerin elemanları arasındaki bu tek olası eşleşmeyi bulmaktır. M Ve İLE, yani, kümelerin karşılık gelen noktalarını birleştiren üç düz çizgiyi bulmak.

Sorunu çözme prensibi basittir. Bir nokta başka bir kümenin iki noktasına kesikli çizgilerle bağlıysa, o zaman üçüncü noktasına düz bir çizgiyle bağlanmalıdır. Bu nedenle, Şekil 5'teki grafik, B ve p, P ve b noktalarını birleştiren düz çizgilerle tamamlanmıştır (Şekil 6).

Şekil 7

Böylece, bu şeklin grafiğinde otomatik olarak cevabı okuyoruz: Belokurov kızıl saçlı, Çernov sarışın, Ryzhov esmer. Aynı teknik örneğin 2. ve 3. problemleri çözmek için kullanılabilir.

Görev 2. Vanya, Kolya ve Misha için turtalar pişirildi: biri lahanalı, diğeri pirinçli, üçüncüsü elmalı. Misha elmalı turtayı sevmiyor ve lahanayla birlikte yemiyor. Vanya lahana turtasını sevmiyor. Kim hangi pastayı yiyor?

Görev 3. Üç arkadaş aynı fabrikada çalışıyor: bir tamirci, bir tornacı ve bir kaynakçı. Soyadları Borisov, Ivanov ve Semenov'dur. Çilingirin erkek veya kız kardeşi yoktur, arkadaşlarının en küçüğüdür. Borisov'un kız kardeşiyle evli olan Semenov, tornacıdan daha yaşlı. Tamirci, tornacı ve kaynakçının isimleri nelerdir?

Yukarıdaki problemler tablolar kullanılarak başarıyla çözülebilir. Bu yöntem veya onun modifikasyonları birçok popüler bilim kitabında ve öğretim yardımcısında tavsiye edilmekte ve tartışılmaktadır. Bununla birlikte, noktalar ve bölümlerle temsil edilen grafiklerin kullanımının daha uygun ve haklı olduğu problem sınıflarını belirtmek mümkündür. Kararlarda turnuva tabloları gibi tabloların yönteminin veya bunların genellemelerinin kullanılması, akıl yürütmenin önemli bir kısmının “sözlü” olarak yürütülmesini zorlamaktadır. Aynı zamanda sorunun koşullarına, ara sonuçlara tekrar tekrar dönmeniz, çok şey hatırlamanız ve alınan bilgileri doğru zamanda kullanmanız gerekir. Bu tür problemler, ele alınan üç veya daha fazla nesne kümesiyle ilgili problemleri içerir.

Görev 4. Üç yoldaş - Ivan, Dmitry ve Stepan - Moskova, Leningrad ve Kiev'deki okullarda çeşitli konuları (kimya, biyoloji, fizik) öğretiyorum. Bilinen:

1. Ivan Moskova'da çalışmıyor ve Dmitry Leningrad'da çalışmıyor;

2. Moskvich fizik öğretmiyor;

3. Leningrad'da çalışan kimya öğretiyor;

4. Dmitry biyoloji öğretmiyor.

Yoldaşların her biri hangi konuyu ve hangi şehirde öğretiyor?

Çözüm. Üç kümeyi ayırt edelim: bir dizi isim, bir dizi nesne ve bir dizi şehir. Şekil 4'teki kümelerin her birinin bir elemanı kendi noktasıyla verilmektedir (bu şekildeki harfler karşılık gelen kelimelerin ilk harfleridir). Farklı kümelerden iki nokta farklı insanların özelliklerini karakterize ediyorsa, bu noktaları kesikli çizgiyle birleştireceğiz. Farklı kümelerden iki nokta bir kişinin özelliklerine karşılık geliyorsa, bu noktaları çiftler halinde düz çizgilerle birleştireceğiz. Problemin koşullarına göre, diğer kümelerin her birindeki herhangi bir kümenin her noktası için, ona karşılık gelen tek ve tek bir noktanın olması önemlidir.

Şekil 8

Böylece Şekil 8'deki grafik, koşulda belirtilen kümelerin tüm elemanlarını ve aralarındaki ilişkileri içermektedir. Grafik dilindeki sorun, köşeleri farklı kümelerde olan üç "katı" üçgenin bulunmasından kaynaklanmaktadır.

Şekil 8'deki grafiği ele alalım. Kesikli XD parçası kendini göstermektedir.Aslında A, X'e karşılık gelir ve aynı zamanda A, D'ye karşılık gelmez, yani X, D'ye karşılık gelemez. Böyle bir problem kullanılır: Eğer köşeleri üç farklı kümede olan üçgenin bir tarafı düzse, ikincisi kesikliyse, üçüncüsü de kesikli olmalıdır. Sorunun koşullarından, grafikteki başka bir işlemin tekdüze olduğu sonucu çıkıyor: eğer bir nokta, ikinci kümedeki iki noktaya kesikli bölümlerle bağlıysa, o zaman bu kümenin üçüncü noktasına katı bir bölümle bağlanmalıdır. DF'nin sürekli bir parçası bu şekilde çizilir. Daha sonra, kesikli DM segmentini çizin (DFM üçgeninde DF tarafı katıdır ve FM kesiklidir), DK katıdır (DM ve DL kesiklidir), Şimdi F ve K noktalarını katı bir segmentle birleştiriyoruz. Köşeleri farklı kümelerde olan bir üçgende iki taraf katı ise, üçüncüsü de katı olacaktır. İlk “katı” üçgen DFK bulundu. Böylece problemin metnine dönmeden, yalnızca yukarıda açıklanan grafikteki doğal işlemlerin rehberliğinde bir çözüm buluyoruz (Şekil 9).

Şekil 9

Segmentlerin gerçekleştirildiği sırayı not edelim: HD, DF, DM, DK, FC, MS, IL, CI, BM, BS. Ortaya çıkan üç "katı" üçgenin her birinin köşeleri sorunun cevabını belirliyor: Ivan Leningrad'da kimya öğretiyor, Dmitry Kiev'de fizik öğretiyor ve Stepan Moskova'da biyoloji öğretiyor.

Aşağıdaki problemde grafiklerin kullanılması iki çözümün varlığını tespit etmeye yardımcı olur.

Görev 5. Masha, Lida, Zhenya ve Katya farklı enstrümanlar (çello, piyano, gitar ve keman) çalabiliyorlar, ancak her biri yalnızca bir enstrüman çalabiliyorlar.Ayrıca farklı yabancı diller de konuşuyorlar (İngilizce, Fransızca, Almanca ve İspanyolca), ancak her biri yalnızca bir enstrüman üzerinde . Biliniyor :

1. gitar çalan kız İspanyolca konuşuyor;

2. Lida keman veya çello çalmıyor ve İngilizce bilmiyor;

3. Masha keman veya çello çalmıyor ve İngilizce konuşmuyor;

4. Almanca konuşan bir kız çello çalamaz;

5. Zhenya Fransızca biliyor ama keman çalmıyor.

Kim hangi enstrümanı çalıyor ve hangi yabancı dili biliyor?

Sorun koşulları Şekil 10'da gösterilen grafiğe karşılık gelir.

Şekil 10

Buradaki gösterim ve çözüm ilkesi problem 4'tekiyle aynıdır. Aşağıdaki katı parçaları sırayla çizelim: KS, VZH, VF, AK (Şekil 11).

Şekil 11

Böylece iki “katı” üçgen ZHVF ve KSA oluşur. Fırlatma aracının sürekli bir bölümünü daha gerçekleştiriyoruz. Artık problemin koşullarının, RN ve GI çiftlerinin her biri için üçüncü noktanın kesin seçimini garanti etmediğine ikna olduk. "Düz" üçgenler için aşağıdaki seçenekler mümkündür: MGI ve OSR veya LGI ve MRN. Dolayısıyla problemin iki çözümü vardır.

Grafiğin, bir koşulun fazlalığını oldukça kolay bir şekilde tespit etmeye olanak sağladığı bir problem sunalım.

Görev 6. Satranç turnuvasına farklı mesleklerden altı ortak katıldı: bir tornacı, bir tamirci, bir mühendis, bir öğretmen, bir doktor ve bir sürücü. Bilinen:

1. ilk turda Andreev doktorla, öğretmen Borisov'la ve Grigoriev Evdokimov'la oynadı;

2. ikinci turda Dmitriev turnerla, doktor ise Borisov'la oynadı;

3. üçüncü turda Evdokimov bir mühendisle oynadı;

4. Turnuvanın sonunda yerler şu şekilde dağıtıldı - BorisovBENyer, Grigoriev ve mühendis paylaştıIIVeIIIDmitriev'in aldığı yerlerIVsırayı alırken Zolotarev ve tamirci beşinci ve altıncı sırayı paylaştı.

Grigoriev, Dmitriev ve Evdokimov'un meslekleri nelerdi?

Eserin metni görseller ve formüller olmadan yayınlanmaktadır.
Çalışmanın tam versiyonuna PDF formatında "Çalışma Dosyaları" sekmesinden ulaşılabilir.

GİRİİŞ

“Matematikte hatırlanması gereken formüller değil, düşünme sürecidir…”

E. I. Ignatiev

Graf teorisi şu anda matematiğin yoğun olarak gelişen bir dalıdır. Bu durum sosyal hayatın normal işleyişi için oldukça önemli olan birçok nesne ve durumun grafik modeller halinde anlatılmasıyla açıklanmaktadır. Daha ayrıntılı çalışmalarının uygunluğunu belirleyen bu faktördür. Bu nedenle bu çalışmanın konusu oldukça alakalı.

Hedef araştırma çalışması: grafik teorisinin çeşitli bilgi alanlarında ve mantıksal problemlerin çözümünde uygulanmasının özelliklerini bulmak.

Hedef aşağıdakileri belirledi görevler:

grafik teorisinin tarihi hakkında bilgi sahibi olmak;

grafik teorisinin temel kavramlarını ve grafiklerin temel özelliklerini incelemek;

Grafik teorisinin çeşitli bilgi alanlarındaki pratik uygulamasını göstermek;

Grafikleri kullanarak problemleri çözmenin yollarını düşünün ve kendi problemlerinizi yaratın.

Bir obje araştırma: grafik yönteminin uygulanması için insan faaliyet alanı.

Öğe Araştırma: Matematiğin “Grafik Teorisi” bölümü.

Hipotez. Grafik teorisini öğrenmenin öğrencilerin matematikteki mantık problemlerini çözmelerine yardımcı olabileceğini ve bunun da gelecekteki ilgilerini şekillendireceğini varsayıyoruz.

Yöntemler Araştırma çalışması:

Araştırmamız sırasında aşağıdaki yöntemler kullanıldı:

1) Çeşitli bilgi kaynaklarıyla çalışmak.

2) Materyalin tanımı, toplanması, sistemleştirilmesi.

3) Gözlem, analiz ve karşılaştırma.

4) Görevlerin hazırlanması.

Teorik ve pratik önemi Bu çalışma, sonuçların bilgisayar bilimleri, matematik, geometri, çizim ve sınıf öğretiminde kullanılabileceği gibi bu konuyla ilgilenen geniş bir okuyucu kitlesi için de kullanılabileceği gerçeğiyle belirlenmiştir. Araştırma çalışması açık bir pratik yönelime sahiptir, çünkü çalışmada yazar birçok bilgi alanında grafik kullanımına ilişkin çok sayıda örnek sunmakta ve kendi görevlerini hazırlamaktadır. Bu materyal seçmeli matematik derslerinde kullanılabilir.

BÖLÜM I. ARAŞTIRMA KONUSUNA İLİŞKİN MATERYALİN KURAMSAL İNCELENMESİ

1. Grafik teorisi. Temel konseptler

Matematikte bir “grafik”, çizgilerle birbirine bağlanan bir dizi noktayı temsil eden bir resim olarak tasvir edilebilir. "Count" Latince "graphio" kelimesinden geliyor - tanınmış bir asil unvan gibi yazıyorum.

Matematikte grafiğin tanımı şu şekilde verilir:

Matematikte "graf" terimi şu şekilde tanımlanır:

Grafik - bu sonlu bir nokta kümesidir - zirveler, hatlarla bağlanabilen - pirzola .

Grafik örnekleri arasında çokgen çizimleri, elektrik devreleri, havayollarının, metroların, yolların vb. şematik gösterimleri yer alır. Bir aile ağacı aynı zamanda köşelerin klanın üyeleri olduğu ve aile bağlarının grafiğin kenarları olduğu bir grafiktir.

Pirinç. 1 Grafik Örnekleri

Bir köşeye ait olan kenar sayısına denir grafiğin tepe noktası derecesi . Bir köşenin derecesi tek sayı ise köşeye - denir. garip . Bir köşenin derecesi çift sayı ise o köşeye denir. eşit.

Pirinç. 2 grafiğin tepe noktası

Boş grafik yalnızca kenarlarla birbirine bağlanmayan izole köşelerden oluşan bir grafiktir.

Grafiği tamamla her köşe çiftinin bir kenarla bağlandığı bir grafiktir. Tüm köşegenlerin çizildiği bir N-gon, tam bir grafiğin örneği olabilir.

Bir grafikte başlangıç ​​ve bitiş noktalarının çakıştığı bir yol seçerseniz, böyle bir yola yol denir. grafik döngüsü . Grafiğin her köşesinden en fazla bir kez geçiliyorsa, o zaman döngü isminde basit .

Bir grafikteki her iki köşe bir kenarla birbirine bağlıysa bu durumda bu bağlı grafik. Grafik denir ilgisiz , en az bir çift bağlantısız köşe içeriyorsa.

Bir grafik bağlıysa ancak döngü içermiyorsa, böyle bir grafik denir ağaç .

1. Grafiklerin özellikleri

Kont'un Yolu ortak bir tepe noktasını paylaşan her iki bitişik kenarın yalnızca bir kez meydana geldiği bir dizidir.

En kısa köşe zincirinin uzunluğu A ve b denir mesafe zirveler arasında A ve B.

Tepe noktası A isminde merkez grafik, köşeler arasındaki mesafe ise A ve diğer herhangi bir köşe mümkün olan en küçük köşedir. öyle bir mesafe var ki yarıçap grafik.

Bir grafiğin herhangi iki köşesi arasındaki mümkün olan maksimum mesafeye denir çap grafik.

Grafik renklendirme ve uygulaması.

Coğrafi bir haritaya yakından bakarsanız demiryollarını veya otoyolları grafik olarak görebilirsiniz. Ayrıca harita üzerinde ülkeler arasındaki sınırları (ilçeler, bölgeler) gösteren bir grafik bulunmaktadır.

1852'de İngiliz öğrencisi Francis Guthrie'ye, her ilçeyi ayrı bir renkle vurgulayacak şekilde Büyük Britanya haritasını renklendirme görevi verildi. Boya seçiminin az olması nedeniyle Guthrie bunları yeniden kullandı. Renkleri, sınırın ortak bir bölümünü paylaşan ilçelerin mutlaka farklı renklere boyanması için seçti. Çeşitli haritaları renklendirmek için gereken minimum boya miktarının ne olduğu sorusu ortaya çıktı. Francis Guthrie kanıtlayamasa da dört rengin yeterli olacağını öne sürdü. Bu sorun öğrenci çevrelerinde hararetle tartışıldı, ancak daha sonra unutuldu.

"Dört renk problemi" giderek artan bir ilgi uyandırdı, ancak seçkin matematikçiler tarafından bile hiçbir zaman çözülemedi. 1890'da İngiliz matematikçi Percy Heawood, herhangi bir haritayı renklendirmek için beş rengin yeterli olacağını kanıtladı. Kırktan az ülkeyi gösteren bir haritayı renklendirmek için 4 rengin yeterli olacağını ancak 1968 yılında kanıtlayabildiler.

1976 yılında bu problem iki Amerikalı matematikçi Kenneth Appel ve Wolfgangt Haken tarafından bilgisayar kullanılarak çözüldü. Bunu çözmek için tüm kartlar 2000 türe bölündü. Dört rengin renklendirilmesinin yeterli olmayacağı kartları tespit etmek amacıyla tüm türleri inceleyen bir bilgisayar programı oluşturuldu. Bilgisayar yalnızca üç tür haritayı inceleyemediği için matematikçiler bunları kendi başlarına incelediler. Sonuç olarak 2000 çeşit kartın tamamını renklendirmek için 4 rengin yeterli olacağı görüldü. Dört renk sorununa bir çözüm açıkladılar. O gün, Appel ve Haken'in çalıştığı üniversitenin postanesi tüm pullara "Dört renk yeter" yazan bir pul bastı.

Dört renk sorununu biraz farklı şekilde hayal edebilirsiniz.

Bunu yapmak için, onu bir grafik biçiminde sunan rastgele bir harita düşünün: durumların başkentleri grafiğin köşeleridir ve grafiğin kenarları, durumları ortak bir sınıra sahip olan köşeleri (büyük harfleri) birbirine bağlar. Böyle bir grafiği elde etmek için aşağıdaki problem formüle edilir: ortak kenara sahip köşelerin farklı renklerle renklendirilmesi için grafiği dört renk kullanarak renklendirmek gerekir.

Euler ve Hamilton grafikleri

1859'da İngiliz matematikçi William Hamilton bir bulmaca yayınladı - yirmi köşesi saplamalarla işaretlenmiş ahşap bir dodecahedron (dodecahedron). Her zirve, dünyanın en büyük şehirlerinden birinin adını taşıyordu - Kanton, Delhi, Brüksel vb. Görev, çokyüzlünün kenarları boyunca uzanan, her köşeyi yalnızca bir kez ziyaret eden kapalı bir yol bulmaktı. Yolu işaretlemek için çivilere bağlanan bir kordon kullanıldı.

Hamilton döngüsü, yolu grafiğin tüm köşelerinden bir kez geçen basit bir döngü olan bir grafiktir.

Kaliningrad şehri (eski adıyla Koenigsberg) Pregel Nehri üzerinde yer almaktadır. Nehir, birbirine ve kıyılara köprülerle bağlanan iki adayı yıkadı. Eski köprüler artık yok. Bunların anısı sadece şehrin haritasında kalıyor.

Bir gün bir şehir sakini arkadaşına tüm köprüleri yürüyerek geçmenin, her birini yalnızca bir kez ziyaret etmenin ve yürüyüşün başladığı yere dönmenin mümkün olup olmadığını sordu. Bu sorun birçok kasaba insanının ilgisini çekti ama kimse çözemedi. Bu konu birçok ülkeden bilim insanlarının ilgisini çekmiştir. Sorunun çözümü matematikçi Leonhard Euler tarafından elde edildi. Ayrıca bu tür sorunların çözümüne yönelik genel bir yaklaşım formüle etti. Bunu yapmak için haritayı bir grafiğe dönüştürdü. Bu grafiğin köşeleri arazi, kenarları ise onu bağlayan köprülerdi.

Euler, Königsberg köprüsü problemini çözerken grafiklerin özelliklerini formüle etmeyi başardı.

Grafiğin tüm köşeleri çift ise, bir köşeden başlayıp tek vuruşla aynı köşede biten (aynı çizgi boyunca iki kez çizmeden ve kalemi kağıttan kaldırmadan) bir grafik çizmek mümkündür.

İki tek köşeli bir grafik varsa, köşeleri de tek vuruşla bağlanabilir. Bunu yapmak için, herhangi bir tek köşe noktasından başlayıp diğerinde bitirmeniz gerekir.

İkiden fazla tek köşeli bir grafik varsa, grafik tek vuruşla çizilemez.

Bu özellikleri köprü problemine uygularsak, incelenen grafiğin tüm köşelerinin tek olduğunu görebiliriz, bu da bu grafiğin tek bir vuruşla bağlanamayacağı anlamına gelir; Tüm köprüleri bir kez geçip yolculuğu başladığı yerde bitirmek imkansızdır.

Bir grafiğin, grafiğin tüm kenarlarını bir kez içeren bir döngüsü (mutlaka basit olması gerekmez) varsa, bu tür bir döngüye döngü denir. Euler döngüsü . Euler zinciri (yol, döngü, kontur), grafiğin tüm kenarlarını (yaylarını) bir kez içeren bir zincirdir (yol, döngü, kontur).

BÖLÜM II. ÇALIŞMANIN TANIMI VE SONUÇLARI

2.1. Çalışmanın aşamaları

Hipotezi test etmek için çalışma üç aşamayı içeriyordu (Tablo 1):

Araştırma aşamaları

Tablo 1.

		Kullanılan yöntemler
Sorunun teorik çalışması	Eğitimsel ve bilimsel literatürü inceleyin ve analiz edin.	- Bağımsız düşünme; - bilgi kaynaklarının incelenmesi; - gerekli literatürü arayın.
Sorunun pratik araştırması	Grafiklerin pratik uygulama alanlarını göz önünde bulundurun ve analiz edin;	- gözlem; - analiz; - karşılaştırmak; - anket.
Sahne 3. Sonuçların pratik kullanımı	Çalışılan bilgileri özetleyin;	- sistemleştirme; - Rapor (sözlü, yazılı, materyallerin gösterimiyle birlikte)	Eylül 2017

2.2. Grafiklerin pratik uygulama alanları

Grafikler ve bilgiler

Bilgi teorisi ikili ağaçların özelliklerinden geniş ölçüde yararlanır.

Örneğin, belirli sayıda mesajı belirli sıfır dizileri ve çeşitli uzunluklarda birler şeklinde kodlamanız gerekiyorsa. Ortalama kelime uzunluğunun diğer olasılık dağılımlarıyla karşılaştırıldığında en küçük olması durumunda, bir kodun belirli bir kod sözcüğü olasılığı için en iyi olduğu kabul edilir. Bu sorunu çözmek için Huffman, arama teorisi çerçevesinde kodun ağaç grafiği olarak temsil edildiği bir algoritma önerdi. Her köşe için, köşeden çıkan iki kenara karşılık gelen, cevabı "evet" veya "hayır" olabilecek bir soru önerilir. Böyle bir ağacın yapımı, gerekli olanın belirlenmesinin ardından tamamlanır. Bu, birkaç kişiyle röportaj yaparken kullanılabilir; önceki sorunun cevabı önceden bilinmediğinde, görüşme planı ikili ağaç olarak temsil edilir.

Grafikler ve kimya

A. Cayley ayrıca molekülleri aşağıdaki formülle verilen doymuş (veya doymuş) hidrokarbonların olası yapıları sorununu da ele aldı:

CnH 2n+2

Tüm hidrokarbon atomları 4 değerlikli, tüm hidrojen atomları 1 değerliklidir. En basit hidrokarbonların yapısal formülleri şekilde gösterilmiştir.

Her doymuş hidrokarbon molekülü bir ağaç olarak temsil edilebilir. Hidrojen atomlarının tamamı çıkarıldığında geriye kalan hidrokarbon atomları, köşeleri derecesi dörtten fazla olmayan bir ağaç oluşturur. Bu, istenen olası yapıların (belirli bir maddenin homologları) sayısının, tepe derecesi 4'ten fazla olmayan ağaçların sayısına eşit olduğu anlamına gelir. Bu sorun, belirli bir türdeki ağaçların numaralandırılması problemine indirgenir. D. Polya bu sorunu ve genellemelerini değerlendirdi.

Grafikler ve biyoloji

Bakteriyel üreme süreci, biyolojik teoride bulunan dallanma süreçlerinden biridir. Her bakteri belli bir süre sonra ya ölsün ya da ikiye bölünsün. Bu nedenle, bir bakteri için yavrularının üremesinin ikili ağacını elde ederiz. Sorunun sorusu şudur: kaç tane vaka içeriyor? k bir bakterinin n'inci neslinin torunları mı? Biyolojideki bu ilişkiye gerekli vaka sayısını ifade eden Galton-Watson süreci denir.

Grafikler ve Fizik

Herhangi bir radyo amatör için zor ve sıkıcı bir görev, baskılı devreler (bir dielektrik yalıtım malzemesi plakası ve metal şeritler şeklinde kazınmış izler) oluşturmaktır. İzlerin kesişmesi yalnızca belirli noktalarda (triyotların, dirençlerin, diyotların vb. yerleri) belirli kurallara göre gerçekleşir. Sonuç olarak, bilim adamı köşeleri olan düz bir grafik çizme göreviyle karşı karşıyadır.

Dolayısıyla yukarıdakilerin tümü grafiklerin pratik değerini doğrular.

İnternet matematiği

İnternet, bilgilerin depolanması ve iletilmesi için birbirine bağlı bilgisayar ağlarından oluşan dünya çapında bir sistemdir.

İnternet, grafiğin köşelerinin İnternet siteleri olduğu ve kenarların bir siteden diğerine giden bağlantılar (köprüler) olduğu bir grafik olarak temsil edilebilir.

Milyarlarca köşesi ve kenarı olan web grafiği (İnternet) sürekli değişiyor - siteler kendiliğinden ekleniyor ve kayboluyor, bağlantılar kayboluyor ve ekleniyor. Ancak İnternet matematiksel bir yapıya sahiptir, grafik teorisine uyar ve birçok “kararlı” özelliğe sahiptir.

Web grafiği seyrek. Köşelerden yalnızca birkaç kat daha fazla kenar içerir.

İnternet seyrekliğine rağmen oldukça kalabalıktır. 5-6 tıklamayla (ünlü "altı el sıkışma" teorisi) bağlantıları kullanarak bir siteden diğerine gidebilirsiniz.

Bildiğimiz gibi bir grafiğin derecesi, bir tepe noktasının ait olduğu kenarların sayısıdır. Bir web grafiğinin köşelerinin dereceleri belirli bir yasaya göre dağıtılır: çok sayıda bağlantıya (kenara) sahip sitelerin (köşelerin) oranı küçüktür ve az sayıda bağlantıya sahip sitelerin payı büyüktür. Matematiksel olarak şu şekilde yazılabilir:

burada belirli bir derecedeki köşelerin oranı, bir tepe noktasının derecesi, web grafiğindeki köşe sayısından bağımsız bir sabittir, yani. site (köşe) ekleme veya kaldırma işlemi sırasında değişmez.

Bu güç yasası, biyolojik ağlardan bankalar arası ağlara kadar karmaşık ağlar için evrenseldir.

İnternet bir bütün olarak sitelere yapılan rastgele saldırılara karşı dayanıklıdır.

Sitelerin yok edilmesi ve oluşturulması bağımsız olarak ve aynı olasılıkla gerçekleştiğinden, 1'e yakın olasılıkla web grafiği bütünlüğünü korur ve bozulmaz.

İnterneti incelemek için rastgele bir grafik modeli oluşturmak gerekir. Bu model gerçek internetin özelliklerine sahip olmalı ve çok karmaşık olmamalıdır.

Bu sorun henüz tam olarak çözülmedi! Bu sorunu çözmek - yüksek kaliteli bir İnternet modeli oluşturmak - bilgi aramayı geliştirmek, spam'ı belirlemek ve bilgiyi yaymak için yeni araçlar geliştirmemize olanak sağlayacaktır.

Biyolojik ve ekonomik modellerin inşası, İnternet'in matematiksel bir modelini oluşturma görevinin ortaya çıkmasından çok daha önce başladı. Ancak İnternet'in geliştirilmesi ve incelenmesindeki ilerlemeler, tüm bu modellere ilişkin birçok soruyu yanıtlamayı mümkün kılmıştır.

İnternet matematiği birçok uzman tarafından talep edilmektedir: biyologlar (bakteriyel popülasyonların büyümesini tahmin eden), finansörler (kriz riskleri), vb. Bu tür sistemlerin incelenmesi uygulamalı matematik ve bilgisayar biliminin merkezi dallarından biridir.

Grafiği kullanarak Murmansk.

Bir kişi yeni bir şehre vardığında, kural olarak ilk arzu, ana turistik yerleri ziyaret etmektir. Ancak aynı zamanda zaman miktarı genellikle sınırlıdır ve bir iş gezisinde bu süre çok küçüktür. Bu nedenle gezinizi önceden planlamanız gerekir. Ve grafikler rotanızı oluşturmada çok yardımcı olacaktır!

Örnek olarak, havaalanından Murmansk'a ilk kez gelmenin tipik bir durumunu düşünün. Aşağıdaki turistik yerleri ziyaret etmeyi planlıyoruz:

1. Sudaki Kurtarıcı'nın Deniz Ortodoks Kilisesi;

2. Aziz Nicholas Katedrali;

3. Okyanus Akvaryumu;

4. Kedi Semyon Anıtı;

5. Nükleer buzkıran Lenin;

6. Murmansk'ın Park Işıkları;

7. Konfor Vadisi Parkı;

8. Kola Köprüsü;

9. Murmansk Denizcilik Şirketi Tarihi Müzesi;

10. Beş Köşeli Kare;

11. Deniz ticaret limanı

Öncelikle bu yerleri harita üzerinde konumlandıralım ve konum ve turistik yerler arasındaki mesafenin görsel bir temsilini elde edelim. Karayolu ağı oldukça gelişmiş olup arabayla seyahat etmek zor olmayacaktır.

Haritadaki ilgi çekici yerler (solda) ve ortaya çıkan grafik (sağda), EK No. 1'deki ilgili şekilde gösterilmektedir. Böylece, yeni gelen ilk önce Kola Köprüsü'nün yanından geçecek (ve istenirse onu ileri geri geçebilir); daha sonra Murmansk Parkı'nın Işıkları ve Konfor Vadisi'nde rahatlayacak ve yoluna devam edecek. Sonuç olarak en uygun rota şu şekilde olacaktır:

Grafiği kullanarak kamuoyu yoklamalarını yürütme planını da görselleştirebilirsiniz. Örnekler EK No. 2'de sunulmuştur. Verilen cevaplara göre cevaplayıcıya farklı sorular sorulur. Örneğin, 1 No'lu sosyolojik ankette katılımcı matematiğin bilimlerin en önemlisi olduğunu düşünüyorsa, kendisine fizik derslerinde kendine güvenip güvenmediği sorulacaktır; aksini düşünüyorsa ikinci soru beşeri bilimlere olan taleple ilgili olacaktır. Böyle bir grafiğin köşeleri sorular, kenarları ise cevap seçenekleridir.

2.3. Grafik teorisinin problem çözümüne uygulanması

Grafik teorisi birçok konu alanındaki problemleri çözmek için kullanılır: matematik, biyoloji, bilgisayar bilimi. Grafik teorisini kullanarak problem çözme ilkesini inceledik ve araştırma konusunda kendi problemlerimizi yarattık.

Görev No.1.

Beş sınıf arkadaşı lise toplantısında el sıkıştı. Kaç el sıkışma yapıldı?

Çözüm: Sınıf arkadaşlarımızı grafiğin köşeleriyle gösterelim. Her köşeyi çizgilerle diğer dört köşeye bağlayalım. 10 satır alıyoruz, bunlar el sıkışma.

Cevap: 10 el sıkışma (her satır bir el sıkışma anlamına gelir).

Görev No.2.

Büyükannemin köyünde, evinin yakınında 8 ağaç büyüyor: kavak, meşe, akçaağaç, elma ağacı, karaçam, huş ağacı, üvez ve çam. Üvez karaçamdan daha yüksektir, elma ağacı akçaağaçtan daha yüksektir, meşe huş ağacından daha alçaktır ancak çamdan daha yüksektir, çam üvezden daha yüksektir, huş ağacı kavaktan daha alçaktır ve karaçam elma ağacından daha yüksektir. Ağaçlar en uzundan en kısaya doğru hangi sırayla sıralanacak?

Çözüm:

Ağaçlar grafiğin köşeleridir. Bunları dairenin ilk harfiyle gösterelim. Alçak bir ağaçtan daha yüksek bir ağaca ok çizelim. Üvezin karaçamdan daha yüksek olduğu söylenir, sonra karaçamdan üveze ok koyarız, huş ağacı kavaktan daha alçaktır, sonra oku kavaktan huş ağacına koyarız vb. En kısa ağacın akçaağaç, ardından elma, karaçam, üvez, çam, meşe, huş ağacı ve kavak olduğunu görebildiğimiz bir grafik elde ediyoruz.

Cevap: akçaağaç, elma, karaçam, üvez, çam, meşe, huş ağacı ve kavak.

Görev No.3.

Annemin 2 zarfı var: normal ve hava ve 3 pul: kare, dikdörtgen ve üçgen. Annem, babama mektup göndermek için bir zarf ve pulu kaç farklı şekilde seçebilir?

Cevap: 6 yol

Görev No.4.

A, B, C, D, E yerleşim yerleri arasında yollar yapılmıştır. A ve E noktaları arasındaki en kısa yolun uzunluğunu belirlemeniz gerekiyor. Sadece şekilde uzunluğu gösterilen yollarda ilerleyebilirsiniz.

Görev No.5.

Üç sınıf arkadaşı - Maxim, Kirill ve Vova spor yapmaya karar verdiler ve spor bölümleri seçimini geçtiler. Basketbol bölümüne 1 erkek çocuğun başvurduğu, 3 çocuğun ise hokey oynamak istediği biliniyor. Maxim yalnızca 1. bölüm için seçmelere katıldı, Kirill üç bölüm için de seçildi ve Vova 2. bölüm için seçildi. Erkeklerden hangisi hangi spor bölümü için seçildi?

Çözüm: Sorunu çözmek için grafikleri kullanacağız

Basketbol Maxim

Futbol Kirill

Hokey Vova

Den beri Basketbol sadece bir ok gidiyor, ardından bölüme Kirill seçildi Basketbol. O zaman Kirill oynamayacak hokey, yani içinde hokey bölüm yalnızca bu bölüm için seçmelere katılan Maxim tarafından seçildiyse, Vova Futbol oyuncusu.

Görev No. 6.

Bazı öğretmenlerin hastalığı nedeniyle okul müdürü, aşağıdaki koşulları dikkate alarak en az bir günlük okul programının bir bölümünü hazırlamalıdır:

1. Can güvenliği öğretmeni yalnızca son dersi vermeyi kabul eder;

2. Coğrafya öğretmeni ikinci veya üçüncü dersi verebilir;

3. Matematikçi ya yalnızca birinci dersi ya da yalnızca ikinci dersi vermeye hazırdır;

4. Bir fizik öğretmeni birinci, ikinci veya üçüncü dersi verebilir, ancak yalnızca bir sınıfta.

Bir okulun müdürü tüm öğretmenleri memnun edecek şekilde nasıl bir program oluşturabilir?

Çözüm: Bu sorun olası tüm seçeneklerin üzerinden geçilerek çözülebilir, ancak grafik çizerseniz daha kolay olur.

1. 1) fizik 2. 1) matematik 3. 1) matematik

2) matematik 2) fizik 2) coğrafya

3) coğrafya 3) coğrafya 3) fizik

4) OBZH 4) OBZH 4) OBZH

Çözüm

Bu araştırma çalışmasında grafik teorisi ayrıntılı olarak incelenmiş, grafiklerin incelenmesinin mantıksal problemlerin çözümünde yardımcı olabileceği hipotezi kanıtlanmış, ayrıca farklı bilim alanlarındaki grafik teorisi dikkate alınmış ve 7 problem derlenmiştir.

Öğrencilere problemlere nasıl çözüm bulacaklarını öğretirken grafiklerin kullanılması, öğrencilerin grafik becerilerini geliştirmelerine ve bazıları çizgilerle birbirine bağlanan sonlu noktalardan oluşan özel bir dilde akıl yürütme yapmalarına olanak tanır. Bütün bunlar öğrencilere düşünmeyi öğretme çalışmasına katkıda bulunur.

Düşünceyi geliştirmede eğitim faaliyetlerinin etkinliği büyük ölçüde öğrencilerin matematik problemlerini çözerken yaratıcı aktivite derecesine bağlıdır. Bu nedenle okul çağındaki çocukların zihinsel aktivitelerini harekete geçirecek matematiksel görevlere ve alıştırmalara ihtiyaç vardır.

Okuldaki seçmeli derslerde görevlerin uygulanması ve grafik teorisi unsurlarının kullanılması, tam olarak öğrencilerin zihinsel aktivitesini harekete geçirme hedefine yöneliktir. Araştırmamızdaki pratik materyallerin seçmeli matematik derslerinde faydalı olabileceğine inanıyoruz.

Böylece araştırma çalışmasının amacına ulaşılmış, sorunlar çözülmüştür. Gelecekte, grafik teorisini incelemeye devam etmeyi ve kendi rotalarımızı geliştirmeyi planlıyoruz; örneğin, ZATO Aleksandrovsk'taki bir okul otobüsü için Murmansk'taki müzelere ve unutulmaz yerlere gezi rotası oluşturmak için bir grafik kullanmak.

KULLANILAN REFERANSLARIN LİSTESİ

Berezina L. Yu. “Grafikler ve uygulamaları” - M .: “Aydınlanma”, 1979

Gardner M. “Matematiksel eğlence”, M. “Mir”, 1972

Gardner M. “Matematiksel bulmacalar ve eğlence”, M. “Mir”, 1971

Gorbaçov A. “Olimpiyat problemlerinin toplanması” - M. MTsNMO, 2005

Zykov A. A. Grafik teorisinin temelleri. - M.: “Üniversite Kitabı”, 2004. - S. 664

Kasatkin V. N. “Matematiğin olağandışı problemleri”, Kiev, “Radianska Okulu”, 1987

Matematiksel bileşen / Editörler ve derleyiciler Andreev, S.P. Konovalov, N.M. Panyuşkin. - M.: Vakfı "Matematiksel Etütler" 2015 - 151 s.

Melnikov O. I. “Grafik teorisinde eğlenceli problemler”, Mn. "TetraSistemler", 2001

Melnikov O.I. Sayımlar diyarında bilmiyorum: Öğrenciler için bir el kitabı. Ed. 3. basmakalıp. M.: KomKniga, 2007. - 160 s.

Olehnik S.N., Nesterenko Yu.V., Potapov M.K. “Eski eğlenceli problemler”, M. “Bilim”, 1988

Cevher O. “Grafikler ve uygulamaları”, M. “Mir”, 1965

Harari F. Grafik Teorisi / İngilizce'den Çeviri. ve önsöz V. P. Kozyreva. Ed. G. P. Gavrilova. Ed. 2.. - M .: Editör URSS, 2003. - 296 s.

EK No.1

Ana turistik yerleri ziyaret etmek için en uygun rotayı hazırlamak

Grafiği kullanarak Murmansk.

En uygun rota şöyle olacaktır:

8. Kola Köprüsü6. Murmansk'ın Park Işıkları7. Konforun Park Vadisi2. Aziz Nicholas Katedrali10. Beş Köşeli Kare5. Nükleer buzkıran Lenin9. Murmansk Denizcilik Şirketi Tarihi Müzesi11. Deniz ticaret limanı1. Sudaki Kurtarıcı'nın Deniz Ortodoks Kilisesi4. Kedi Semyon3 Anıtı. Okyanus akvaryumu.

MURMANSK GÖRÜLECEK GEZİLER REHBERİ

EK No.2

Sosyolojik araştırmalar No. 1, 2

Eğitim baskısı

Yuyukin Nikolay Alekseevich

LR hayır. Mühür için imza atıldı

Ah. Ed. ben.. , .

Voronej Devlet Teknik Üniversitesi

394026 Voronej, Moskovsky Bulvarı. 14

MANYETİK DİSK DİZİNİ

Yüksek Matematik ve Fiziksel ve Matematiksel Modelleme Bölümü

ÜZERİNDE. Yuyukin

AYRIK MATEMATİK Bölüm 1. Grafik teorisinin unsurları

öğretici

ÜZERİNDE. Yuyukin

AYRIK MATEMATİK Bölüm 1. Grafik teorisinin unsurları

öğretici

Voronej 2004

GİRİİŞ

Bu kılavuz, aşağıdaki uzmanlık alanlarında eğitim gören VSTU öğrencileri tarafından “Ayrık Matematik” dersinde kullanılabilir:

090102 – Bilgisayar güvenliği;

090105 – Otomatik sistemlerin bilgi güvenliğinin kapsamlı sağlanması;

090106 - Telekomünikasyon sistemlerinin bilgi güvenliği.

“Ayrık Matematik” disiplini, devlete, genel eğitim standardına uygun olarak bilgi ve becerilerin kazanılmasını sağlar ve aynı zamanda temel eğitimin kazanılmasını, bir dünya görüşünün oluşmasını ve mantıksal düşüncenin gelişimini teşvik eder.

Grafik teorisi, ayrık nesnelerle ilişkili modern mühendislik problemlerini resmileştirmek için etkili bir araçtır. Entegre devrelerin ve kontrol devrelerinin tasarımında, otomat ve mantık devrelerinin incelenmesinde, sistem analizinde, otomatik üretim kontrolünde, bilgisayar ve bilgi ağlarının geliştirilmesinde, devre tasarımında ve tasarım-topolojik tasarımda vb. kullanılır.

Eğitimde grafik teorisinin temelleri, temel yöntemleri ve algoritmaları özetlenmektedir. Burada n-grafikler ve digraflar sunuyoruz; izomorfizmler; ağaçlar; Euler grafikleri; düzlemsel grafikler; kaplamalar ve bağımsız kümeler; güçlü bağlantı

V digraflar; Markov zinciri grafiği analizi; grafiklerde en kısa yolları bulmaya yönelik algoritmalar; Hamilton çevrimi arama problemi

V grafik; gezici satıcı problemi; grafiklerin ve eşlemelerin numaralandırılması; aşırı görevler; optimizasyon problemleri; evrensel görevler; dal ve sınır yöntemi; ve ayrıca yukarıdaki kavramları kullanma konusunda pratik beceriler geliştirin.

Dersin amacı öğrencilerin doğa bilimleri ve teknolojisindeki süreç ve olguların modellenmesi alanında teorik bilgi, pratik beceri ve yeteneklerini geliştirmektir.

Ke, bilgi güvenliği alanındaki resmi faaliyetleri yüksek profesyonel düzeyde gerçekleştirmek için gerekli olan nesnelerin niceliksel ve niteliksel ilişkilerini ifade etmek için matematiksel sembolleri kullanma becerisine sahip.

Aşağıdaki görevler bu hedefe ulaşmaya yarar:

mümkün olan en geniş grafik teorisi kavramlarını incelemek;

eğitimsel ve pratik sorunları çözme becerisi kazanmak;

ana optimizasyon yöntemleri;

Bilgi problemlerini belirleme ve çözme, grafikleri kullanarak bilgiyi modelleme ve analiz etme becerilerini geliştirmek.

“Ayrık Matematik” disiplini uygulamalı matematik disiplinlerinden biridir. Öğrencilerin “Cebir” ve “Matematiksel Mantık ve Algoritma Teorisi” disiplinlerini incelerken edindikleri bilgilere dayanmaktadır. Çalışmada “Ayrık Matematik” disiplininin çalışmasında edinilen bilgi ve beceriler kullanılmıştır. genel profesyonel ve özel disiplinler.

1. GRAFİK TEORİSİNİN TEMEL KAVRAMLARI.

1.1. Grafik teorisinin sorunları.

Grafik teorisi, tıpkı ilişki kavramında olduğu gibi, farklı nesneler arasındaki bağlantı sistemlerini inceleyen bir matematik dalıdır. Ancak grafiğin bağımsız bir şekilde tanımlanması teorinin sunumunu basitleştirir, daha anlaşılır ve görsel hale getirir.

Grafik teorisinin ilk problemleri eğlence problemlerini ve bulmacaları çözmekle ilgiliydi.

İlk görev. Königsberg köprülerinin problemi 1786 yılında Euler tarafından ortaya atılmış ve çözülmüştür. Şehir, Pregolya Nehri'nin kıyısında ve iki adasında bulunuyordu. Adalar, şekilde görüldüğü gibi birbirleriyle kıyılara yedi köprüyle bağlanıyordu.

Şu soru ortaya çıktı: Her köprüyü tam olarak bir kez geçerek evden çıkıp geri dönmek mümkün mü?

İkinci görev. Üç ev ve üç kuyu sorunu. Üç ev ve üç kuyu var.

Yolların kesişmemesi için her evden her kuyuya bir yol çizilmesi gerekiyor. Görev şuydu:

Pontryagin tarafından ve ondan bağımsız olarak Kuratovsky tarafından çözüldü.

Üçüncü görev. Yaklaşık dört renk. Bir düzlemdeki herhangi bir haritayı dört renkle boyayın, böylece iki bitişik alan aynı renge boyanmaz.

Grafik teorisinden elde edilen birçok sonuç, bilim ve teknolojideki pratik problemleri çözmek için kullanılır. Böylece, 19. yüzyılın ortalarında Kirchhoff, karmaşık elektrik devrelerini hesaplamak için grafik teorisini kullandı. Ancak matematiksel bir disiplin olarak grafik teorisi ancak 20. yüzyılın 30'lu yıllarında oluşmuştur. Bu durumda grafikler bazı soyut matematiksel nesneler olarak kabul edilir. Devrelerin ve sistemlerin analizinde ve sentezinde, ağ planlama ve yönetiminde, yöneylem araştırmasında, programlamada, bir organizmanın yaşamının modellenmesinde ve diğer alanlarda kullanılırlar.

1.2. Temel tanımlar.

Bir G= (V,E) grafiği iki kümeden oluşan bir koleksiyondur: boş olmayan bir V köşe kümesi ve sırasız ve sıralı E köşe çiftlerinden oluşan bir küme. Aşağıda sonlu grafikleri ele alacağız; sonlu bir köşe kümesine ve sonlu bir çift ailesine sahip grafikler. Sırasız bir köşe çiftine kenar, sıralı bir çifte ise yay adı verilir.

Tipik olarak, bir grafik bir diyagramla temsil edilir: köşeler noktalardır (veya dairelerdir), kenarlar isteğe bağlı konfigürasyondaki çizgilerdir. Bir ok ayrıca yay üzerindeki yönünü gösterir. Bir grafiği tasvir ederken taşıyıcının

Kenarların geometrik özelliklerinin (uzunluk, eğrilik) yanı sıra köşelerin düzlem üzerindeki göreceli konumu da önemlidir.

Herhangi bir kenara (yaya) ait olmayan köşelere izole edilmiş köşeler denir. Bir kenar veya yay ile bağlanan köşelere bitişik denir. Bir kenar (yay) ve onun iki köşesinden herhangi birine olay denir.

Bir kenarın (u,v) u ve v köşelerini birbirine bağladığını ve bir yayın (u,v) u köşesinde başlayıp v köşesinde bittiğini, u'nun bu yayın başlangıcı ve v'nin sonu olduğunu söylüyorlar.

Bir çift köşe, iki veya daha fazla kenar (aynı yöndeki yaylar) ile bağlanabilir. Bu tür kenarlara (yaylara) çoklu denir. Bir yay (veya kenar) aynı tepe noktasında başlayabilir veya bitebilir. Böyle bir yay (kenar) döngü olarak adlandırılır. Döngüler içeren bir grafiğe sözde grafik denir. Birden fazla kenarı (yayı) olan bir grafiğe çoklu grafik denir.

Döngüleri veya birden fazla kenarı olmayan bir grafiğe basit denir. Basit bir grafik, herhangi bir köşe çifti için onları bağlayan bir kenar (yay) varsa tamamlanmış olarak adlandırılır. N köşeli tam bir grafik K n ile gösterilir. Örneğin bunlar grafikler

İzole edilmiş bir köşeden (K 1) oluşan bir grafiğe önemsiz denir.

Bir G grafiğinin tamamlayıcısı, G grafiği ile aynı köşelere sahip olan ve tam bir grafik elde etmek için G grafiğine eklenmesi gereken kenarları içeren bir G grafiğidir.

Digraf bilmeyen herkese kanonik olarak eşleşir her bir kenarın aynı köşelere gelen ve zıt yönlere sahip iki yay ile değiştirildiği, aynı köşe kümesine sahip yönlendirilmiş bir grafik.

1.3. Grafik köşelerinin dereceleri.

Basit bir G grafiğinin bir v köşesinin derecesi (değerlik) (d (v) veya derece (v) gösterimi), belirli bir v köşesine gelen kenarların veya yayların sayısıdır. Bir sözde grafiğin köşelerinin değerliliği hesaplanırken her döngü iki kez sayılmalıdır.

Bir n-grafının tüm köşelerinin dereceleri k'ye eşitse bu grafiğe denir. düzenli (üniform) derece k. Bir köşenin derecesi 0 ise izoledir. Bir köşenin derecesi 1 ise, o zaman köşeye terminal köşe (asılı, çıkmaz) adı verilir.

Bir digraf için, v köşesinden çıkan yayların sayısına denir.

değişir yarı dereceli sonuç										(v) ve gelenler – yarım adım-
yeni arama d							(v), Bu durumda d(v)= bağıntısı
		(v)+			(v).

Euler teoremi: Bir grafiğin köşe noktalarının derecelerinin toplamı

kaburga sayısını iki katına çıkarın, yani

d(vi)

			(v)

N, köşelerin sayısıdır; m – sayı

kaburgalar (kemerler). Bu ifade, köşe derecelerinin toplamını hesaplarken, her bir kenarın, kenarın bir ucu ve diğeri için iki kez dikkate alınmasıyla kanıtlanmıştır.

1.4. Grafik izomorfizmi.

Bir grafın köşeleri bir şekilde birbirinden farklıysa, bu grafa etiketlenmiş (veya yeniden numaralandırılmış) adı verilir.

etiketler (sayılar). Sayım düşünülüyor tamamen dar anlamda verilmiştir, eğer köşelerinin ve kenarlarının numaralandırması sabitse. Bu durumda, G 1 ve G 2 grafiklerine, köşe ve kenar kümeleri çakışıyorsa eşit denir (G 1 = G 2 tanımı). G 1 = (V 1 ,E 1 ) ve G 2 = (V 2 ,E 2 ) iki grafik veya sözde graf denir

	izomorfik (gösterim G				eğer varlarsa
	bire bir eşlemeler: 1)				: V 1 V 2
: E 1 E 2 öyle ki grafikteki herhangi iki u, v köşesi için
	((u, v)) ((u), (v)) ilişkisi geçerlidir.
	İki basit grafik (döngüler ve çoklu kenarlar olmadan) G 1					ve G2

eğer karşılıklı olarak aynıysa izomorfik olduğu ortaya çıkar

değer eşleme

: V 1 V 2

Ne olmuş?

(u , v ) ((u ), (v )) .

Bu nedenle, yalnızca köşelerin ve kenarların numaralandırılmasında farklılık gösteren grafikler izomorfiktir. Grafik izomorfizmi bir denklik ilişkisidir çünkü şu özelliklere sahiptir:

Yansıma -

G1,

ve bijeksiyon

özdeş bir fonksiyondur.

Simetri.

bijeksiyon ile

bijeksiyon ile

Geçişlilik.

G 1 G 2

birebir örten

1 A

bijeksiyon ile

o zaman G G

bijeksiyon ile

2 (1 ) .