Titov Maksim

1. Nijnegorskiy viloyatining barcha yo'nalishlarini ko'rib chiqing.

2. Marshrut ma'lumotlariga asoslanib, yangi marshrutlar yarating.

3. Yangi marshrutlar Eyler grafiklari ekanligini ko'rsating.

4. Yangi marshrutlar uchun qo'shnilik matritsasini tuzing.

5. Nijnegorskoye qishlog'idan aholi punktlarigacha bo'lgan eng qisqa masofalarni toping.

Yuklab oling:

Ko‘rib chiqish:

KIRISH……………………………………………………………………………….3

1-BO'lim. GRAFIKALARNING ASOSIY TA'RIFLARI…………………………………5

Grafiklar nazariyasining asosiy tushunchalari……………………………………5
Eyler grafiklarining xarakteristikalari…………………………………7
Grafikdagi eng qisqa masofani topish (Dijkstree algoritmi)…………..8

2-BO'lim. NIJNEGORSKY TUMANI MARSHRUTLARI ……………………..………10

Nijnegorskiy tumani marshrutlari………………………………….10
Nijnegorskiy tumani marshrutlarini o'rganish ………………………..11

XULOSA…………………………………………………………………………………….17

ADABIYOTLAR RO‘YXATI………………………………….19

KIRISH

Grafiklar matematik, iqtisodiy va mantiqiy muammolarni hal qilish uchun ishlatilishi mumkin bo'lgan ajoyib matematik ob'ektlardir. Shuningdek, siz turli jumboqlarni hal qilishingiz va fizika, kimyo, elektronika va avtomatlashtirish masalalari shartlarini soddalashtirishingiz mumkin. Grafiklardan xaritalar va oila daraxtlarini tuzishda foydalaniladi. Grafiklar - bu kompyuter dasturlari sxemalari, tarmoqni qurish grafiklari, bunda cho'qqilar ma'lum bir saytdagi ishlarning tugallanganligini ko'rsatadigan hodisalardir va bu cho'qqilarni bog'laydigan qirralar bir voqea sodir bo'lgandan keyin boshlanishi mumkin bo'lgan ishdir va ularni bajarish uchun bajarilishi kerak. Keyingisi. Eng keng tarqalgan grafiklardan biri bu metro liniyalari diagrammasi.

Hatto matematikada "Grafik nazariyasi" deb nomlangan maxsus bo'lim mavjud. Grafik nazariyasi topologiya va kombinatorikaning bir qismidir. Bu topologik nazariya ekanligi grafik xossalarining cho'qqilarning joylashuvi va ularni bog'laydigan chiziqlar turidan mustaqilligidan kelib chiqadi. Kombinatoriy masalalarni grafiklar bo‘yicha shakllantirish qulayligi esa grafiklar nazariyasining kombinatorikaning eng kuchli vositalaridan biriga aylanishiga olib keldi. Mantiqiy masalalarni yechishda shartda berilgan ko‘plab faktlarni xotirada saqlash, ular o‘rtasida bog‘lanish o‘rnatish, gipotezalarni ifodalash, muayyan xulosalar chiqarish va ulardan foydalanish odatda ancha qiyin.

Mavzuning dolzarbligi shundan iboratki, grafiklar nazariyasi hozirgi vaqtda diskret matematikaning jadal rivojlanayotgan sohasi hisoblanadi. Bu ko'plab ob'ektlar va vaziyatlar grafik modellar shaklida tasvirlanganligi bilan izohlanadi: aloqa tarmoqlari, elektr va elektron qurilmalarning sxemalari, kimyoviy molekulalar, odamlar o'rtasidagi munosabatlar, barcha turdagi transport sxemalari va boshqalar. Ijtimoiy hayotning normal ishlashi uchun juda muhimdir. Aynan shu omil ularni batafsilroq o'rganishning dolzarbligini belgilaydi.

Ishning maqsadi Nijnegorsk viloyatidagi transport yo'nalishlarini o'rganishdir.

Ish maqsadlari:

1 . Nijnegorskiy viloyatining barcha yo'nalishlarini ko'rib chiqing.

2 . Marshrut ma'lumotlari asosida yangi marshrutlarni yarating.

3. Yangi marshrutlar Eyler grafiklari ekanligini ko'rsating.

4. Yangi marshrutlar uchun qo'shnilik matritsasini tuzing.

5. Nijnegorskoye qishlog'idan aholi punktlarigacha bo'lgan eng qisqa masofalarni toping.

Tadqiqot ob'ekti - Nijnegorsk viloyatining transport yo'nalishlari xaritasi.

Bu ishning amaliy ahamiyati shundan iboratki, undan darslarda turli masalalarni yechishda hamda fanning turli sohalarida va zamonaviy hayotda foydalanish mumkin.

Qo'llaniladigan usullar: axborot manbalarini izlash, kuzatish, taqqoslash, tahlil qilish, matematik modellashtirish.

Bo'limlarning tuzilishi ishning umumiy g'oyasi bilan bog'liq. Asosiy qism uch bobdan iborat. Birinchisi grafiklarning asosiy tushunchalarini qamrab oladi. Ikkinchi bobda Nijnegorskiy viloyatining yo'nalishlari ko'rib chiqiladi.

Ish davomida men bir qator adabiy manbalardan foydalandim: grafik nazariyasiga oid maxsus adabiyotlar, o'quv adabiyotlari, turli ilmiy-ommabop, o'quv va maxsus jurnallar.

1-BO'lim

ASOSIY GRAFIK TA’RIFLARI

1.1. Grafiklar nazariyasining asosiy tushunchalari

Grafik bo'sh bo'lmagan nuqtalar va segmentlar to'plami bo'lib, ularning ikkala uchi ham berilgan nuqtalar to'plamiga tegishli. (1.1-rasm)

1.1-rasm.

Grafikning cho'qqisi qirralarning va/yoki yoylarning birlashishi/chiqishi mumkin bo'lgan nuqtadir.

Grafik chekkasi - chekka grafikning ikkita uchini bog'laydi.

Cho'qqi darajasi - bu grafikning bir cho'qqisidan chiqadigan qirralarning soni.

Grafikning toq darajaga ega bo'lgan cho'qqisi toq deyiladi, juft darajaga ega bo'lgan cho'qqi esa juft deyiladi.

Agar ulanish yo'nalishi muhim bo'lsa, unda chiziqlar o'qlar bilan ta'minlanadi, bu holda grafik yo'naltirilgan grafik, digraf deb ataladi. (1.2-rasm)

1.2-rasm.

Og'irlangan grafik - bu har bir chekkaga ma'lum bir qiymat (qirraning og'irligi) berilgan grafik. (1.3-rasm)

Guruch. 1.3.

Barcha mumkin bo'lgan qirralari tuzilgan grafiklar to'liq grafiklar deyiladi. (1.4-rasm)

Guruch. 1.4.

Grafik bog'langan deb ataladi, agar uning istalgan ikkita uchini yo'l orqali, ya'ni har biri oldingisining oxiridan boshlanadigan qirralarning ketma-ketligi bilan bog'lash mumkin bo'lsa.

Qo'shni matritsa - bu matritsa bo'lib, uning elementi M[i] [j] i cho'qqidan j cho'qqigacha bo'lgan chekka bo'lsa 1 ga, agar bunday chekka bo'lmasa 0 ga teng (grafik uchun 1.5-rasm). 1.1-rasmda).

1.2. Eyler grafiklarining xarakteristikalari

Qog'ozdan qalamni ko'tarmasdan chizish mumkin bo'lgan grafik Eyler grafigi deyiladi. (1.6-rasm)

Bu grafiklar olim Leonhard Eyler nomi bilan atalgan.

Shakl 1.

Toq sonli toq burchakli grafik chizish mumkin emas.
Shakl 2.

Agar grafikning barcha cho'qqilari juft bo'lsa, siz qalamni qog'ozdan ko'tarmasdan ("bitta zarba bilan") har bir chekka bo'ylab faqat bir marta harakatlanmasdan ushbu grafikni chizishingiz mumkin. Harakat har qanday cho'qqidan boshlanib, bir xil cho'qqida tugashi mumkin.
Shakl 3.

Qog'ozdan qalamni ko'tarmasdan faqat ikkita toq uchi bo'lgan grafik chizish mumkin va harakat shu toq uchlardan birida boshlanib, ikkinchisida tugashi kerak.
Shakl 4.

Ikkidan ortiq toq uchlari boʻlgan grafikni “bir zarba” bilan chizish mumkin emas.
Qog'ozdan qalamni ko'tarmasdan chizish mumkin bo'lgan rasm (grafik) unikursal deyiladi.

1.6-rasm.

1.3. Grafikdagi eng qisqa masofani topish (Dijkstree algoritmi)

Muammo: shaharlar orasidagi yo'llar tarmog'i berilgan, ularning ba'zilari bir tomonlama harakatga ega bo'lishi mumkin. Berilgan shahardan boshqa barcha shaharlargacha bo'lgan eng qisqa masofalarni toping (1.7-rasm).

Xuddi shu masala: N cho'qqi bilan bog'langan grafik berilgan, qirralarning og'irliklari W matritsasi tomonidan berilgan. Berilgan cho'qqidan qolgan barcha nuqtalargacha bo'lgan eng qisqa masofalarni toping.

Dijkstra algoritmi (E.V. Dijkstra, 1959):

1. Barcha cho'qqilarga ∞ yorlig'ini belgilang.

2. Ko‘rib chiqilmagan cho‘qqilar orasidan eng kichik yorliqli j uchini toping.

3. Har bir i cho‘qqisi uchun: agar i cho‘qqisi orqali j cho‘qqigacha bo‘lgan yo‘l mavjud yorliqdan kichik bo‘lsa, yorliqni yangi masofa bilan almashtiring.

4. Agar hali ham ishlov berilmagan cho'qqilar mavjud bo'lsa, 2-bosqichga o'ting.

5. Belgisi = minimal masofa.

1.7-rasm.

1.8-rasm. Muammoni hal qilish

2-BO'lim

NIJNEGORSKY TUMANI MARSHRUTLARI

2.1. Nijnegorskiy tumani yo'nalishlari

Nijnegorskiy tumani Qrim avtonom respublikasining shimolidagi dasht qismida joylashgan. Nijnegorskiy tumani tarkibiga Nijnegorskiy shahri va 59 ta aholi punkti kiradi.

Nijnegorskiy tumanidan ikkita yo'nalish o'tadi: 2R58 va 2R64. Nijnegorskaya A/S dan boshqa aholi punktlariga 8 ta yo'nalish mavjud. Ishimda men ushbu yo'nalishlarni ko'rib chiqaman:

1 marshrut "Nijnegorsk - Krasnogvardeysk". Quyidagi yo'llar bilan: Nijnegorsk - Plodovoye - Mitofanovka - Burevestnik - Vladislavovka.

2-marshrut “Nijnegorsk – Izobilnoye”: Nijnegorsk – Semennoe – Kirsanovka – Listvennoye – Oxotskoye – Tsvetushchee – Emelyanovka – Izobilnoye.

3-marshrut “Nijnegorsk - Velikoselye”: Nijnegorsk – Semennoye – Dvurechye – Akimovka – Lujki – Zalivnoye – Stepanovka – Lugovoye – Chkalovo – Velikoselye.

4-marshrut "Nijnegorsk - Belogorsk (2P64 marshrut)": Nijnegorsk - Jelyabovka - Ivanovka - Zarechye - Serovo - Sadovoe - Peny.

5-marshrut "Nijnegorsk - Uvarovka": Nijnegorsk - Semennoye - Novoivanovka - Uvarvka.

6-marshrut “Nijnegorsk – Lyubimovka”: Nijnegorsk – Semennoe – Dvurechye – Akimovka – Lujki – Zalivnoe – Stepanovka – Lugovoye – Kovorovo – Dvorovoe – Lyubimovka.

7-marshrut “Nijnegorsk – Pshenichnoye”: Nijnegorsk – Semennoye – Dvurechye – Akimovka – Lujki – Zalivnoye – Stepanovka – Lugovoye – Kovorovo – Dvorovoe – Slivyanka – Pshenichnoye.

8-yo'nalish "Nijnegorsk - Zorkino (2P58 marshrut)": Nijnegorsk - Razlivy - Mixaylovka - Kuntsevo - Zorkino.

Avtobus yo‘nalishlari qo‘ng‘iroq qilmaydigan qishloqlar ko‘p, odamlar o‘z manzillariga o‘zlari, asosan, piyoda yetib borishlariga to‘g‘ri keladi. Shu bois, oldimda shunday vazifa turardi: yangi marshrutlarni yaratish va ularga avtobuslar ketmaydigan aholi punktlarini kiritish mumkinmi?

"Nijnegorsk - Uvarovka" "Nijnegorsk - Lyubimovka" "Nijnegorsk - Pshenichnoye" yo'nalishlarini o'zgartirib bo'lmaydi, chunki yo'lda avtobuslar barcha aholi punktlariga qo'ng'iroq qiladi, shuning uchun men bu yo'nalishlarni hisobga olmayman.

Keling, boshqa beshta yo'nalishni ko'rib chiqaylik. Biz aholi punktlarini raqamlar bilan belgilaymiz - bu grafikning uchlari va ular orasidagi masofalar - grafikning qirralari bilan biz beshta grafikni olamiz. Keling, har bir grafikni alohida ko'rib chiqaylik.

2.2. Nijnegorsk viloyatining yo'nalishlarini o'rganish

1-marshrut: Nijnegorsk - Krasnogvardeysk.

Nijnegorsk - 1

Meva - 2

Mitrofanovka - 3

Chervonoye - 6

Burevestnik - 4

Novogrigoryevka - 7

Vladislavivka - 5

6, 7 nuqtalarga bormaydi. Keling, ushbu aholi punktlarini marshrutga qo'shamiz.

2.1-rasm.

Grafik Eylerian emas. Yangi yo'nalish quyidagicha ko'rinadi: Nijnegorsk - Plodovoye - Mitrofanovka - Burevestnik - Novogrigoryevka - Vladislavovka. Novogrigorievka qishlog'i qo'shildi.

2 Yo'nalish: Nijnegorsk - Izobilnoye.

Nijnegorsk - 1

Urug' - 2

Kirsanovka - 3

Bargli - 4

Oxotskoye - 5

Gullash - 6

Emelyanovka - 7

Ko'p - 8

Kulichki - 9

Buloqlar - 10

9,10 bandlariga kirmaydi. Keling, ushbu aholi punktlarini marshrutga qo'shamiz.

2.2-rasm.

Grafik Eyler emas va ulangan, shuning uchun yangi marshrutni qurish mumkin emas. Yo'nalish avvalgidek qoladi.

3-marshrut: Nijnegorsk - Velikosele

Nijnegorsk - 1

Urug' - 2

Mesopotamiya - 3

Akimovka – 4

Yaylovlar - 5

Jellied - 6

Stepanovka - 7

Lugovo - 8

Chkalovo - 9

Velikosele - 10

Keng - 11

11-bandga bormaydi. Keling, ushbu aholi punktini marshrutga qo'shamiz.

2.3-rasm.

Grafik Eylerian emas. Yo'nalish avvalgidek qoladi.

4-marshrut: Nijnegorsk - Belogorsk (marshrut 2R64)

Nijnegorsk - 1 Kostochkovka - 12

Jelyabovka – 2, Frunze – 13

Ivanovka - 3 Prirechnoye - 14

Zarechye - 4 marvarid - 15

Serovo - 5

Sadovoe - 6

Ko'piklar - 7

Lomonosovo - 8

Makkajo'xori - 9

Tambovka - 10

Tarasovka - 11

8-18-bandlarga kirmaydi. Keling, ushbu aholi punktlarini marshrutga qo'shamiz.

2.4-rasm.

Grafik Eylerian emas. Yangi yo'nalish quyidagicha ko'rinadi: Nijnegorsk - Jelyabovka - Ivanovka - Zarechye - Tambovka - Tarsovka - Prirechnoye - Jemchujina - Peny.

5-marshrut: Nijnegorsk - Zorkino (2R58 marshrut)

Nijnegorsk - 1

To'kilishlar - 2

Mixaylovka - 3

Kuntsevo - 4

Zorkino - 5

Qulay - 6

Nijinskoe - 7

6,7 bandlariga kirmaydi. Keling, ushbu aholi punktlarini marshrutga qo'shamiz.

2.5-rasm.

Grafik Eyler emas va ulangan, shuning uchun marshrut bir xil bo'lib qoladi.

XULOSA

Fraktal fani juda yosh va uni buyuk kelajak kutmoqda. Fraktallarning go'zalligi tugamaydi va bizga hali ham ko'plab durdonalarni beradi - ko'zni quvontiradigan va ongga haqiqiy zavq keltiradigan. Bu ishning yangiligi.

Xulosa qilib shuni aytmoqchimanki, fraktallar kashf etilgandan so'ng, ko'plab olimlar uchun Evklid geometriyasining eski yaxshi shakllari ko'pchilik tabiiy ob'ektlardan ancha past ekanligi, ularda biron bir tartibsizlik, tartibsizlik va oldindan aytib bo'lmaydiganligi sababli ma'lum bo'ldi. Fraktal geometriyaning yangi g'oyalari atrofdagi tabiatning ko'plab sirli hodisalarini o'rganishga yordam berishi mumkin. Hozirgi vaqtda fraktallar fizika, biologiya, tibbiyot, sotsiologiya va iqtisodning ko'plab sohalariga tez kirib bormoqda. Yangi kontseptsiyalardan foydalanadigan tasvirni qayta ishlash va naqshni aniqlash usullari tadqiqotchilarga ushbu matematik apparatdan juda ko'p sonli tabiiy ob'ektlar va tuzilmalarni miqdoriy tavsiflash uchun foydalanish imkonini beradi.

Tadqiqot jarayonida quyidagi ishlar amalga oshirildi:

1. Tadqiqot mavzusi bo'yicha adabiyotlar tahlil qilindi va o'rganildi.

2. Fraktallarning har xil turlari ko'rib chiqiladi va o'rganiladi.

3. Fraktallarning tasnifi keltirilgan.

4. Fraktallar dunyosi bilan dastlabki tanishish uchun fraktal tasvirlar to'plami to'plangan.

5. Fraktallarning grafik tasvirini qurish dasturlari tuzilgan.

Shaxsan men uchun "Fraktal geometriyaning bitmas-tuganmas boyliklari" mavzusini o'rganish juda qiziqarli va g'ayrioddiy bo'lib chiqdi. Tadqiqot jarayonida men o'zim uchun nafaqat loyiha mavzusiga, balki umuman atrofdagi dunyoga tegishli ko'plab yangi kashfiyotlar qildim. Men bu mavzuga juda qiziqaman va shuning uchun bu ish mening zamonaviy fanni tushunishimga juda ijobiy ta'sir ko'rsatdi.

Loyihamni tugatgandan so'ng, rejalashtirilgan hamma narsa muvaffaqiyatli bo'ldi, deb ayta olaman. Kelgusi yil men "fraktallar" mavzusida ishlashni davom ettiraman, chunki bu mavzu juda qiziqarli va ko'p qirrali. O'ylaymanki, men o'z loyihamning muammosini hal qildim, chunki men barcha maqsadlarimga erishdim. Loyiha ustida ishlash menga matematika nafaqat aniq, balki go'zal fan ekanligini ko'rsatdi.

FOYDALANILGAN MANBALAR RO'YXATI

1. V.M. Bondarev, V.I. Rublinetskiy, E.G. Kachko. Dasturlash asoslari, 1998 yil

2. N. Kristofid. Grafik nazariyasi: algoritmik yondashuv, Jahon, 1978.

3. F.A. Novikov. Dasturchilar uchun diskret matematika, Sankt-Peterburg, 2001 yil.

4. V.A. Nosov. Kombinatorika va grafik nazariyasi, MSTU, 1999 yil.

5. O. Ruda. Grafik nazariyasi, fan, 1982 yil.

Tadqiqot maqsadi :

Mantiqiy va kombinatsion masalalarni yechishda grafik apparatlardan foydalanish imkoniyatlarini ko‘rib chiqing.

Tadqiqot maqsadlari:

masalalarni grafik yordamida yechish haqida o‘ylash;

muammolarni grafik tiliga tarjima qilishni o'rganish;

muammoni hal qilishning an'anaviy usullarini grafika nazariyasi usullari bilan solishtiring.

Tadqiqotning dolzarbligi:

Grafiklar hayotimizning barcha sohalarida qo'llaniladi. Grafik nazariyasi asoslarini bilish ishlab chiqarishni boshqarish, biznes (masalan, tarmoq qurilishi jadvali, pochta jo'natmalari jadvallari), transport va etkazib berish yo'nalishlarini qurish va muammolarni hal qilish bilan bog'liq turli sohalarda zarur. Grafiklar ehtimollar nazariyasi, matematik mantiq va axborot texnologiyalarining rivojlanishi bilan bog'liq holda qo'llaniladi.

Gipoteza:

Grafik nazariyasini qo'llash ko'plab mantiqiy va kombinatoryal muammolarni echishni kamroq mehnat talab qiladi.

Tarkib:

Kirish. Grafik tushunchasi.

Grafikning asosiy xossalari.

Grafiklar nazariyasining asosiy tushunchalari va ularning isbotlari.

Tanlangan vazifalar.

Grafikning xromatik raqami.

Adabiyot.

Kirish. Grafik tushunchasi.

Har birimiz haqmiz, albatta,

Kechikmasdan topib,

U nima... oddiy hisob

Tayoqlardan va nuqtalardan.

Grafiklar nazariyasi hozirgi vaqtda diskret matematikaning jadal rivojlanayotgan sohasi hisoblanadi. Grafiklar va tegishli tadqiqot usullari deyarli barcha zamonaviy matematikaga turli darajadagi organik ravishda kirib boradi. Grafiklarning tili sodda, tushunarli va ingl. Grafik masalalar bir qator afzalliklarga ega bo'lib, ulardan fikrlashni rivojlantirish, mantiqiy fikrlashni yaxshilash va zukkolikdan foydalanishga imkon beradi. Grafiklar ajoyib matematik ob'ektlar bo'lib, ularning yordami bilan siz juda ko'p turli xil tashqi ko'rinishdagi muammolarni hal qilishingiz mumkin;

Matematikada butun bir bo'lim - grafiklar nazariyasi mavjud bo'lib, u grafiklarni, ularning xususiyatlarini va qo'llanilishini o'rganadi. "Hisoblash" nomli matematik grafiklar lotincha "graphio" so'zidan kelib chiqqan umumiy kelib chiqishi bilan bog'langan - men yozaman. Odatdagi grafiklar havo yo'llarining diagrammalari bo'lib, ular ko'pincha aeroportlarda, metro diagrammalarida va geografik xaritalarda - temir yo'llarning tasvirlarida joylashtiriladi. Grafikning tanlangan nuqtalari uning uchlari, ularni tutashtiruvchi chiziqlar esa qirralar deb ataladi. Grafiklardan biri moskvaliklar va poytaxt mehmonlariga yaxshi ma'lum - bu Moskva metrosining diagrammasi: tepaliklar - yakuniy stansiyalar va uzatish stantsiyalari, qirralari - bu stantsiyalarni bog'laydigan yo'llar. Graf L.N. Tolstoyning oila daraxti - bu boshqa raqam. Bu erda cho'qqilar yozuvchining ajdodlari, qirralari esa ular orasidagi oilaviy aloqalarni ko'rsatadi.

1-rasm. 2

Matematikada "grafik" so'zi bir nechta nuqtalar chizilgan, ularning ba'zilari chiziqlar bilan bog'langan rasmni, tekislikdagi cho'qqilarning joylashishini, qirralarning egriligini va uzunligini anglatadi (3-rasm). muhim emas, grafiklarning uchlari harflar yoki natural sonlar bilan belgilanadi. Grafikning chekkalari raqamlar juftligidir.

guruch. 3

Grafiklar - bu kompyuter dasturlarining blok-sxemalari, tarmoq qurilishi grafiklari, bu erda cho'qqilar ma'lum bir sohada ish tugallanganligini ko'rsatadigan hodisalar va bu cho'qqilarni bog'laydigan qirralar bir voqea sodir bo'lgandan keyin boshlanishi mumkin bo'lgan va keyingisini bajarish uchun bajarilishi kerak bo'lgan ishdir. .Grafiklarning xususiyatlari, shuningdek, ularning tasvirlari cho'qqilarning segmentlar yoki egri chiziqlar bilan bog'langanligiga bog'liq bo'lmaydi va o'zgarmaydi. Bu ularning xususiyatlarini yosh fanlardan biri - topologiya yordamida o'rganish imkonini beradi, garchi grafiklar nazariyasi muammolarining o'zi kombinatorikaning tipik muammolari bo'lsa ham.

Topologiya va kombinatorikani nima bog'laydi? Grafik nazariyasi topologiya va kombinatorikaning bir qismidir. Bu topologik nazariya ekanligi grafik xossalarining cho'qqilarning joylashuvi va ularni bog'laydigan chiziqlar turidan mustaqilligidan kelib chiqadi. Kombinatoriy masalalarni grafiklar bo‘yicha shakllantirish qulayligi esa grafiklar nazariyasining kombinatorikaning eng kuchli vositalaridan biriga aylanishiga olib keldi.

Ammo bu grafiklarni kim o'ylab topdi? Ular qayerda ishlatiladi? Ularning barchasi bir xilmi yoki farqlari bormi?

Grafik nazariyasining paydo bo'lish tarixi. Königsberg ko'priklarining klassik muammosi.

Grafiklar nazariyasining matematik fan sifatida asoslari 1736 yilda Leonhard Eyler tomonidan Kenigsberg ko'priklari muammosini ko'rib chiqqan holda qo'yilgan.“Mendan Kenigsberg shahrida joylashgan va daryo bo‘ylab 7 ta ko‘prik bilan o‘ralgan orol haqida savol berishdi. Savol shundaki, kimdir har bir ko'prikdan faqat bir marta o'tib, ularni doimiy ravishda chetlab o'tishi mumkinmi ... " (L. Eylerning italiyalik matematik va muhandis Marinoniga 1736 yil 13 martdagi maktubidan).

Sobiq Koenigsberg (hozirgi Kaliningrad) Pregel daryosida joylashgan. Shahar ichida daryo ikkita orolni yuvadi. Sohillardan orollarga ko'priklar qurilgan. Qadimgi ko'priklar saqlanib qolmagan, ammo ular tasvirlangan shahar xaritasi saqlanib qolgan (4-rasm). Koenigsbergerlar tashrif buyuruvchilarga quyidagi vazifani taklif qilishdi: barcha ko'priklarni kesib o'tish va boshlang'ich nuqtaga qaytish va har bir ko'prikni faqat bir marta ziyorat qilish kerak edi. Eylerni shahar ko'priklari bo'ylab sayr qilishga ham taklif qilishdi. Kerakli aylanma yo'lni amalga oshirish uchun muvaffaqiyatsiz urinishdan so'ng, u ko'priklarning soddalashtirilgan sxemasini chizdi. Natijada cho‘qqilari shaharning daryo bilan ajratilgan qismlari, chetlari esa ko‘priklar bo‘lgan grafik hosil bo‘ladi (5-rasm).

guruch. 4 rasm. 5

Kerakli marshrutning imkoniyatini asoslashdan oldin Eyler boshqa, murakkabroq xaritalarni ko'rib chiqdi. Natijada, u umumiy fikrni isbotladi: grafikning barcha qirralarini bir marta bosib o'tish va dastlabki cho'qqiga qaytish uchun quyidagi ikkita shartni qondirish zarur va etarli:

grafikning istalgan cho'qqisidan uning chetlari bo'ylab boshqa har qanday cho'qqiga yo'l bo'lishi kerak (bu talabni qondiradigan grafiklar bog'langan deb ataladi);

Har bir cho'qqidan teng miqdordagi qirralar chiqishi kerak.

“Shunday qilib, quyidagi qoidaga rioya qilish kerak: agar biron bir chizmada ma'lum bir hududga olib boradigan ko'priklar soni toq bo'lsa, barcha ko'priklar orqali bir vaqtning o'zida kerakli o'tishni amalga oshirish mumkin emas, agar o'tish boshlangan bo'lsa. yoki shu sohada tugaydi. Va agar ko'priklar soni juft bo'lsa, bundan hech qanday qiyinchilik bo'lmaydi, chunki o'tishning boshlanishi ham, oxiri ham aniq emas. Bu quyidagi umumiy qoidaga olib keladi: agar toq sonli ko'priklar yetib boradigan ikkitadan ortiq maydon mavjud bo'lsa, unda kerakli o'tishni umuman amalga oshirib bo'lmaydi. Chunki o'tishning ushbu sohalarning birida boshlanishi va tugashi mutlaqo mumkin emasdek tuyuladi. Va agar bu turdagi faqat ikkita maydon mavjud bo'lsa (chunki bunday turdagi bitta maydon yoki toq sonli maydonlarni berish mumkin emas), unda barcha ko'priklar bo'ylab o'tish mumkin, ammo o'tish boshlanadi. birida, ikkinchisida esa bu sohalardan. Taklif etilayotgan A va B rasmlarida toq sonli ko'priklar olib boruvchi va C ga olib boradigan ko'priklar soni juft son bo'lgan maydonlar mavjud bo'lsa, men o'tish yoki ko'prik qurilishi sodir bo'lishi mumkinligiga ishonaman. A yoki B dan boshlanadi va agar kimdir C dan o'tishni boshlamoqchi bo'lsa, u hech qachon maqsadiga erisha olmaydi. Königsberg ko'priklari joylashgan joyda men bir-biridan suv bilan ajratilgan to'rtta maydonga egaman, ularning har biri toq sonli ko'priklar bilan boshqariladi (6-rasm).

guruch. 6

Shuning uchun, siz, eng ulug'vor odam, bu yechim o'z tabiatiga ko'ra, matematikaga unchalik aloqasi yo'qligiga amin bo'lishingiz mumkin va men nima uchun bu yechimni boshqa odamdan emas, balki matematikdan kutish kerakligini tushunmayapman, buning uchun yechim faqat fikrlash bilan quvvatlanadi va bu yechimni topish uchun matematikaga xos bo'lgan har qanday qonunlarni jalb qilishning hojati yo'q. Shunday qilib, men matematikaga juda oz aloqasi bo'lgan savollarni boshqa [olimlar]ga qaraganda matematiklar ko'proq hal qilishlari qanday sodir bo'lishini bilmayman. Ayni paytda, siz, eng taniqli odam, bu savolning pozitsiya geometriyasida o'rnini aniqlang va bu yangi fanga kelsak, men Leybnits va Bo'riga bu bilan bog'liq qanday muammolar yoqqanini bilmayman. Shunday ekan, sizdan so‘rayman, agar siz meni ushbu yangi fanda biror narsa yaratishga qodirman deb hisoblasangiz, menga u bilan bog‘liq bir qancha aniq topshiriqlarni yuborishingizni ma’qul ko‘rasiz...”

Grafikning asosiy xossalari.

Königsberg ko'priklari haqidagi masalani hal qilishda Eyler grafikning quyidagi xususiyatlarini o'rnatdi:

Agar grafikning barcha cho'qqilari juft bo'lsa, unda siz bitta zarba bilan (ya'ni qalamni qog'ozdan ko'tarmasdan va bir xil chiziq bo'ylab ikki marta chizmasdan) grafik chizishingiz mumkin.

Ikkita toq cho'qqilari bo'lgan grafikni bir zarba bilan ham chizish mumkin. Harakat har qanday toq cho'qqidan boshlanib, boshqa toq cho'qqida tugashi kerak.

Ikkitadan ortiq toq uchlari boʻlgan grafikni bir zarba bilan chizish mumkin emas.

Eyler va Gamilton sikllari tushunchasi.

Barcha qirralardan bir marta o'tadigan yopiq yo'l hali ham Eyler tsikli deb ataladi.

Agar biz asl cho'qqiga qaytish shartidan voz kechsak, unda toq sonli qirralar paydo bo'ladigan ikkita cho'qqi mavjudligini taxmin qilishimiz mumkin. Bunday holda, harakat ushbu cho'qqilarning biridan boshlanib, ikkinchisida tugashi kerak.

Königsberg ko'priklari masalasida mos keladigan grafikning barcha to'rtta cho'qqisi toq bo'lib, ya'ni barcha ko'priklardan bir marta o'tib, yo'lni u erda tugatish mumkin emas.

Bir qog'ozga grafikni olish juda oson. Siz qalam olib, bu qog'ozga biron bir narsani chizishingiz kerak, qalamni qog'ozdan ko'tarmasdan va bir xil chiziq bo'ylab ikki marta chizmasdan. Agar ular "kesishmalar" bilan mos kelmasa, "kesishmalar" va boshlang'ich va tugash nuqtalarini nuqta bilan belgilang. Olingan rasmni grafik deb atash mumkin. Agar chizmaning boshlang'ich va tugash nuqtalari bir-biriga to'g'ri kelsa, unda barcha cho'qqilar juft bo'ladi, lekin agar boshlang'ich va tugash nuqtalari bir-biriga to'g'ri kelmasa, ular toq cho'qqilar, qolganlari esa juft bo'ladi.Grafiklardan foydalangan holda ko'plab mantiqiy muammolarni hal qilish yosh talabalar uchun juda qulaydir. Buning uchun ularga grafiklar va ularning eng aniq xossalari haqida intuitiv tushunchaga ega bo'lish kifoya.Ko'pgina bolalar jumboqlarida siz quyidagi vazifalarni topishingiz mumkin: qalamni qog'ozdan ko'tarmasdan va bir xil chiziq bo'ylab ikki marta chizmasdan rasm chizish.

guruch. 7 a) b)

7-rasmda (a) ikkita cho'qqi (pastki) mavjud bo'lib, ulardan toq sonli qirralar chiqadi. Shuning uchun chizma ulardan biri bilan boshlanib, ikkinchisida tugashi kerak. 7(b)-rasmda Eyler sikli mavjud, chunki grafikning oltita uchidan juft sonli qirralar chiqadi.

1859 yilda dunyoga murakkab sonlar va kvaternionlar nazariyasini taqdim etgan mashhur irland matematigi ser Uilyam Hamilton g'ayrioddiy bolalar jumboqini taklif qildi, unda dunyoning turli qismlarida joylashgan 20 ta shaharga "dunyo bo'ylab sayohat" qilish taklif qilindi. globus (8-rasm). Mashhur shaharlardan birining (Bryussel, Dehli, Frankfurt va boshqalar) nomi bilan belgilangan yog'och dodekaedrning har bir tepasiga mix qo'yilgan va ulardan biriga ip bog'langan Dodekaedrni bu ip bilan shunday qilib, uning qirralari bo'ylab harakatlanadi, har bir novdani aynan bir marta o'raladi va natijada ip yo'nalishi yopildi (tsikl har bir shahar uchta qo'shni yo'llar bilan bog'langan, shunda yo'l tarmog'i shakllangan). Dodekaedrning 30 qirrasi, ularning uchlarida a, b ... t shaharlari joylashgan. Majburiy shart har bir shaharga tashrif buyurish talabi edi, birinchisidan tashqari, faqat bir marta.

guruch. 8 rasm. 9

Agar biz a shahridan sayohatni boshlasak, u holda oxirgi shaharlar b, e yoki h bo'lishi kerak, aks holda biz asl a nuqtasiga qaytolmaymiz. To'g'ridan-to'g'ri hisob-kitob shuni ko'rsatadiki, bunday yopiq yo'nalishlar soni 60. Siz barcha shaharlarga to'liq bir marta tashrif buyurishni talab qilishingiz mumkin, shu jumladan birinchisi, ya'ni. har qanday shaharda sayohatni tugatishga ruxsat beriladi (masalan, samolyotda boshlang'ich nuqtaga qaytish mumkin bo'ladi deb taxmin qilinadi). Keyin zanjirli marshrutlarning umumiy soni 162 tagacha ko'tariladi (9-rasm).

Xuddi shu yili, 1859 yilda Gamilton Dublindagi o'yinchoq fabrikasi egasiga uni ishlab chiqarishni taklif qildi. Zavod egasi Hamiltonning taklifini qabul qildi va unga 25 gvineya to'ladi. O'yinchoq Rubik kubiga o'xshardi, u yaqinda juda mashhur bo'lib, matematikada sezilarli iz qoldirdi. Grafikning chetlari bo‘ylab barcha cho‘qqilardan bir marta o‘tuvchi yopiq yo‘lga Gamilton sikli deyiladi. Eyler siklidan farqli o'laroq, ixtiyoriy grafikda Gamilton siklining mavjudligi uchun shartlar hali o'rnatilmagan.

To'liq grafik tushunchasi. Planar grafiklarning xossalari.

Grafikni tekislikda uning qirralari kesishmasligi uchun har doim tasvirlash mumkinmi? Yo'q ekan. Bu mumkin bo'lgan grafiklar tekis deyiladi.Barcha mumkin bo'lgan qirralari tuzilmagan grafiklar to'liq bo'lmagan grafiklar, barcha uchlari barcha mumkin bo'lgan usullar bilan bog'langan grafiklar to'liq grafik deb ataladi.

guruch. 10 ta rasm. 11

10-rasmda chekkalari kesishmagan tekislikka sig'maydigan beshta uchli grafik ko'rsatilgan. Ushbu grafikning har ikki uchi chekka bilan bog'langan. Bu to'liq grafik. 11-rasmda oltita uchi va to'qqiz qirrali grafik ko'rsatilgan. U "uylar - quduqlar" deb ataladi. Bu qadimiy vazifadan - jumboqdan kelib chiqadi. Uch do'st uchta kulbada yashar edi. Ularning uylari yonida uchta quduq bor edi: biri sho'r suvli, ikkinchisida shirin suvli, uchinchisida chuchuk suvli. Ammo bir kuni do'stlar shunchalik janjal qilishdiki, ular hatto bir-birlarini ko'rishni ham xohlamadilar. Va ular yo'llari kesishmasligi uchun uylardan quduqlarga yangi usulda yo'l qo'yishga qaror qilishdi. Buni qanday qilish kerak? 12-rasmda to'qqizta yo'ldan sakkiztasi chizilgan, ammo endi to'qqizinchisini kuzatish mumkin emas.

12-rasm

Polshalik matematik Kazimierz Kuratovski bir-biridan tubdan farq qiladigan tekis bo'lmagan grafiklar yo'qligini aniqladi. Aniqrog'i, agar grafik tekislikka "mos kelmasa", unda ushbu ikkita grafikdan kamida bittasi "o'tiradi" (beshta cho'qqi yoki "uy-quduq" bilan to'liq grafik), ehtimol chekkalarida qo'shimcha cho'qqilar bilan. .

“Alisa mo‘jizalar mamlakatida” kitobining muallifi Lyuis Kerroll do‘stlariga quyidagi jumboqni berishni yaxshi ko‘rardi. U rasmda tasvirlangan figurani qalamni qog'ozdan ko'tarmasdan va bir xil chiziq bo'ylab ikki marta chizmasdan chizishni so'radi. Cho'qqilarning paritetini hisoblab chiqqanimizdan so'ng, biz bu muammoni osonlikcha hal qilish mumkinligiga amin bo'ldik va siz o'tishni istalgan cho'qqidan boshlashingiz mumkin, chunki ularning barchasi teng. Biroq, u chiziq chizishda chiziqlar kesishmasligini talab qilib, vazifani murakkablashtirdi. Siz ushbu muammoni quyidagi yo'l bilan hal qilishingiz mumkin. Keling, rasmni ranglaymiz, shunda uning chegara qismlari turli xil rangda bo'ladi. Keyin soyali qism bitta bo'lak bo'lishi uchun biz kesishgan chiziqlarni ajratamiz. Endi bo'yalgan joyni chekka bo'ylab bir zarba bilan belgilash qoladi - bu kerakli chiziq bo'ladi (13-rasm).

guruch. 13

Grafiklar nazariyasining asosiy tushunchalari va ularning isbotlari .

Planar grafiklar juda ko'p qiziqarli xususiyatlarga ega. Shunday qilib, Eyler cho'qqilar soni (B), qirralarning soni (P) va grafik tekislikni ajratadigan qismlar soni (G) o'rtasidagi oddiy bog'liqlikni topdi.

B - P + G = 2.

1. Ta'rif . Bir cho'qqidan chiqadigan qirralarning soni shu cho'qqining darajasi deb ataladi.

Lemma1. Grafikdagi qirralarning soni cho'qqilarning darajalari yig'indisidan to'liq 2 marta kam.

Isbot. Grafikning istalgan cheti 2 ta burchak bilan bog'langan. Bu shuni anglatadiki, agar biz grafikning barcha cho'qqilarining darajalari sonini qo'shsak, qirralarning soni ikki baravar ko'p bo'ladi, chunki har bir chekka ikki marta hisoblangan.

Lemma2 . Grafik cho'qqilarining darajalari yig'indisi juft .

Isbot. Lemma 1 bo'yicha, grafikdagi qirralarning soni uchlari darajalari yig'indisidan 2 baravar kam, ya'ni cho'qqilarning darajalari yig'indisi juft (2 ga bo'linadi).

2. Ta'rif . Agar cho'qqining darajasi juft bo'lsa, u holda daraja juft bo'lmasa, u holda toq deb ataladi.

Lemma3 . Grafikdagi toq uchlari soni juft.

Isbot. Agar grafik mavjud bo'lsanhatto vaktoq uchlari bo'lsa, u holda juft cho'qqilar darajalarining yig'indisi juft bo'ladi. Toq cho'qqilarning darajalari yig'indisi toq bo'ladi, agar bu uchlari soni toq bo'lsa. Ammo cho'qqilarning darajalarining umumiy soni ham toq bo'ladi, bu bo'lishi mumkin emas. Ma'nosi,khatto.

Lemma 4. Agar to'liq grafik n ta uchga ega bo'lsa, unda qirralarning soni teng bo'ladi

Isbot. To'liq grafikda bilannhar bir cho'qqidan cho'qqilar chiqadin- 1 qovurg'a. Bu cho'qqilarning darajalari yig'indisi teng ekanligini anglatadin ( n-1). Qirralarning soni 2 barobar kamroq, ya'ni .

Tanlangan vazifalar.

Eyler tomonidan olingan grafikning xossalarini bilgan holda, endi siz quyidagi muammolarni osongina echishingiz mumkin:

Masala 1. Bir-biri bilan yonma-yon turgan uch kishidan biri doim haqiqatni aytadi (haqiqatni aytadi), ikkinchisi doim yolg‘on gapiradi (yolg‘onchi), uchinchisi esa vaziyatga qarab yo haqiqatni yoki yolg‘on gapiradi (diplomat). Chap tomonda turgandan: "Yana kim turibdi?" U: «Haqiqat izlovchi», deb javob berdi. Markazda turgan kishiga “Siz kimsiz?” degan savolga u: “Men diplomatman”, deb javob berdi. O'ng tomonda turgan kishidan: "Yonimda kim turibdi?", deb so'ralganda, u: "Yolg'onchi", dedi. Kim qayerda turdi?

Yechim: Agar bu masalada grafikning cheti u yoki bu shaxs egallagan joyga mos kelsa, u holda bizga quyidagi imkoniyatlar taqdim etilishi mumkin.

Keling, birinchi imkoniyatni ko'rib chiqaylik. Agar "haqiqat izlovchi" chap tomonda bo'lsa, uning yonida, uning javobiga ko'ra, "haqiqat izlovchi" ham bor. Bizda "yolg'onchi" bor. Binobarin, bu tartib muammoning shartlarini qondirmaydi. Boshqa barcha imkoniyatlarni ko'rib chiqib, biz "diplomat", "yolg'onchi", "haqiqatni aytuvchi" pozitsiyasi vazifani qondiradi degan xulosaga kelamiz. Haqiqatan ham, agar "haqiqatni aytuvchi" o'ng tomonda bo'lsa, uning javobiga ko'ra, "yolg'onchi" uning yonida turibdi, bu bajariladi. Markazda turgan kishi o'zini "diplomat" deb e'lon qiladi va shuning uchun yolg'on gapiradi (bu shartdan mumkin), o'ng tomonda turgan ham yolg'on gapiradi. Shunday qilib, muammoning barcha shartlari bajariladi.

Masala 2. 10 xonali sonda ketma-ket kelgan har ikki raqam 13 ga bo‘linadigan ikki xonali son hosil qiladi. Bu raqamlar orasida 8 ta yo‘qligini isbotlang.

Yechim. 13 ga bo'linadigan 7 ta ikki xonali sonlar mavjud. Keling, bu raqamlarni nuqta bilan belgilaymiz va grafik ta'rifini qo'llaymiz. Shartga ko'ra, har 2 ta ketma-ket raqam ikki xonali sonni hosil qiladi, ular 13 ga bo'linadi, ya'ni 10 xonali sonni tashkil etuvchi raqamlar takrorlanadi. Grafikning cho'qqilarini qirralar bilan bog'laymiz, bu grafikga kiritilgan raqamlar takrorlanadi.

13 65

91 39 52

Tuzilgan grafiklardan ko'rinib turibdiki, 10 xonali sonning raqamlari orasida 8 raqami bo'lishi mumkin emas.

Masala 3. Qishloqda 10 ta uy bor va har biridan boshqa uylarga olib boruvchi 7 ta yo‘lak bor. Uylar orasida nechta yo'l bor?

Yechim. Uylar grafaning uchlari, yo'llar esa chekkalari bo'lsin. Shartga ko'ra, har bir uydan (cho'qqi) 7 ta yo'l (qirra) chiqadi, keyin har bir cho'qqining darajasi 7 ga, cho'qqilarning darajalari yig'indisi 7 × 10 = 70 ga, qirralarning soni esa 70 ga teng. : 2 = 35. Shunday qilib, uylar orasidan 35 ta yo'l o'tadi.

4-topshiriq: Quyosh sistemasining 9 ta sayyorasi o‘rtasida kosmik aloqa o‘rnatildi. Raketalar quyidagi yo‘nalishlarda uchadi: Yer-Merkuriy, Pluton-Venera, Yer-Pluton, Pluton-Merkuriy, Merkuriy-Venera, Uran-Neptun, Neptun-Saturn, Saturn-Yupiter, Yupiter-Mars va Mars-Uran. Yerdan Marsga borish mumkinmi?

Yechim. Keling, diagramma chizamiz: sayyoralar nuqtalarga mos keladi va ularni bog'laydigan marshrutlar bir-birini kesib o'tmaydigan chiziqlarga mos keladi.

Marshrutlarning rasmini chizib, biz muammoning shartlariga mos keladigan grafikni chizdik. Quyosh sistemasining barcha sayyoralari bir-biriga bog'liq bo'lmagan ikkita guruhga bo'linganligini ko'rish mumkin. Yer bir guruhga, Mars ikkinchi guruhga tegishli. Erdan Marsga uchib bo'lmaydi.

Klassik "sayohatchi sotuvchi muammosi". "Ochko'z" algoritmlari.

Grafik nazariyasidagi klassik muammolardan biri sayohatchi sotuvchi muammosi yoki sayohatchi savdogar muammosi deb ataladi. Tasavvur qilaylik, bir nechta shaharlarga sayohat qilib, qaytib kelishi kerak bo'lgan savdo agenti. Bu shaharlarni qanday yo'llar bog'lab turgani va bu yo'llar bo'ylab bu shaharlar orasidagi masofa qancha ekanligi ma'lum. Siz eng qisqa yo'lni tanlashingiz kerak. Bu "o'yinchoq" vazifasi emas. Misol uchun, pochta qutilaridan xat olib ketayotgan pochta haydovchisi eng qisqa yo'lni bilishni juda xohlaydi, xuddi kiosklarga tovarlarni etkazib beradigan yuk mashinasi haydovchisi. Lekin bu masalani yechish ancha mushkul, chunki grafikdagi uchlari soni juda katta. Ammo bu erda yana bir vazifa, qaysidir ma'noda sayohatchi sotuvchining vazifasiga qarama-qarshidir. Bir qancha yirik shaharlarni bog‘laydigan temir yo‘l qurilishi rejalashtirilgan. Har qanday shaharlar juftligi uchun ular orasidagi yo'lni yotqizish narxi ma'lum. Siz eng arzon qurilish variantini topishingiz kerak. Aslida, optimal qurilish variantini topish algoritmi juda oddiy. Keling, buni beshta A, B, C shaharlarini bog'laydigan yo'l misolida ko'rsatamiz.Dva E. Har bir juft shahar o'rtasida yo'l yotqizish narxi jadvalda (14-rasm) va shaharlarning xaritadagi joylashuvi (15-rasm) ko'rsatilgan.

1,5

2,5

1,5

1,2

0,8

1,2

1,1

0,9

1,1

2,7

2,5 5

ya'ni, va har bir transport vositasining A, B C va yuk mashinasining shaharlarining joylashuvi, div.

0,8

0,9

2,7

A A

D D

BILAN

14-rasm. 15

Avval biz eng past narxga ega bo'lgan yo'lni quramiz. Bu B → E yo'nalishi. Keling, B yoki E ni istalgan shahar bilan bog'laydigan eng arzon chiziqni topamiz. Bu E va C o'rtasidagi yo'l. Biz uni diagrammaga kiritamiz. Keyinchalik, biz shunga o'xshash tarzda harakat qilamiz - biz B, C, E shaharlaridan birini qolganlaridan biri bilan bog'laydigan yo'llarning eng arzonini qidiramiz - A yokiD. Bu C va A o'rtasidagi yo'l. Faqat shaharni temir yo'l tarmog'iga ulash qoladiD.

Eng arzon yo'l - uni S. bilan bog'lash Biz temir yo'l yo'llari tarmog'ini olamiz (16-rasm).

guruch. 16

Temir yo'lni qurish uchun optimal variantni topishning ushbu algoritmi "ochko'z" toifasiga kiradi: ushbu muammoni hal qilishning har bir bosqichida biz marshrutning eng arzon davomini tanlaymiz. Bu vazifa uchun juda mos keladi. Ammo sayohatchi sotuvchi muammosida ochko'z algoritm optimal echimni bermaydi. Agar siz eng boshidanoq "eng arzon" elementlarni tanlasangiz, ya'ni. eng qisqa masofalar, oxirida siz juda "qimmat" - uzunlardan foydalanishingiz kerak bo'lishi mumkin va marshrutning umumiy uzunligi optimaldan sezilarli darajada yuqori bo'ladi.

Shunday qilib, ba'zi muammolarni hal qilish uchun siz "ochko'z" deb nomlangan usul yoki algoritmdan foydalanishingiz mumkin. "Ochko'z" algoritmi - bu allaqachon tanlangan qirralar bilan tsikl hosil qilmaslik sharti bilan, eng qisqa, hali tanlanmagan chetni tanlash orqali eng qisqa masofani topish algoritmidir. Ushbu algoritm "ochko'z" deb ataladi, chunki oxirgi bosqichlarda siz ochko'zlik uchun jiddiy pul to'lashingiz kerak. Keling, sayohatchi sotuvchi muammosini hal qilishda "ochko'z" algoritm qanday harakat qilishini ko'rib chiqaylik. Bu erda u "eng yaqin (hali kirmagan) shaharga borish" strategiyasiga aylanadi. Ochko'z algoritm bu muammoda kuchsizligi aniq. Misol uchun, tor olmosni ifodalovchi 17-rasmdagi tarmoqni ko'rib chiqaylik. Sayyor sotuvchi 1-shahardan boshlasin. “Eng yaqin shaharga borish” algoritmi uni 2-shaharga, keyin 3-ga, keyin 4-ga olib boradi; oxirgi bosqichda siz olmosning uzun diagonali bo'ylab qaytib, ochko'zligingiz uchun to'lashingiz kerak bo'ladi. Natijada eng qisqa emas, balki eng uzun tur bo'ladi. Biroq, ba'zi hollarda, "ochko'z" algoritm hali ham eng qisqa yo'lni aniqlaydi.

4 3

guruch. 17

Shunga o'xshash muammolarni hal qilishning yana bir usuli mavjud - to'liq qidiruv usuli (ba'zida ular "Qo'pol kuch usuli" deyishadi, bu to'liq qidiruvni anglatadi - bu mutlaqo to'g'ri emas, chunki qidiruv to'liq bo'lmasligi mumkin), bu barcha mumkin bo'lgan kombinatsiya nuqtalarini qidirishdan iborat. (maqsad nuqtalari). Matematikadan ma'lumki, bunday almashtirishlar soni n! ga teng, bu erda n - nuqtalar soni. Sayohatchi sotuvchi muammosida boshlang'ich nuqta odatda bir xil (birinchi nuqta) sifatida qabul qilinganligi sababli, qolganlarini o'tishimiz kifoya qiladi, ya'ni. almashtirishlar soni (n-1) ga teng bo'ladi!. Ushbu algoritm deyarli har doim sayohatchi sotuvchi muammosiga aniq yechim beradi, ammo hisoblash vaqti juda ko'p bo'lishi mumkin. Ma'lumki, n > 12 qiymatlari bilan zamonaviy kompyuter koinotning butun mavjudligi davomida ham sayohatchi sotuvchi muammosini hal qila olmaydi. Sayohatchi sotuvchi muammosini hal qilish uchun boshqa algoritmlar mavjud bo'lib, ular "ochko'z" algoritmga qaraganda ancha aniqroq va qo'pol kuch usulidan ancha tezroq. Biroq, biz grafiklarni ko'rib chiqamiz va bu usullar grafik nazariyasi bilan bog'liq emas.

Grafikning xromatik raqami.

Geografik xaritani rang berish muammosi

Chegaralar bilan ajratilgan mamlakatlarni ko'rsatadigan geografik xarita berilgan. Chegaraning umumiy qismlari bo'lgan mamlakatlar turli xil ranglarda bo'yalganligi va ranglarning minimal soni qo'llanilishi uchun xaritani rang berish talab qilinadi.

Ushbu xaritadan foydalanib, biz quyidagi tarzda grafik tuzamiz. Grafikning uchlarini xarita mamlakatlariga moslashtiramiz. Agar ba'zi ikki davlat chegaraning umumiy qismiga ega bo'lsa, unda tegishli cho'qqilar chekka bilan bog'lanadi, aks holda xaritaning ranglanishi olingan grafikning cho'qqilarining to'g'ri ranglanishiga mos kelishini ko'rish oson. va kerakli ranglarning minimal soni ushbu grafikning xromatik soniga teng.

Xromatik raqamlar grafigi - grafikning uchlarini shunday rang berish uchun ishlatilishi mumkin bo'lgan ranglarning eng kichik soni, shunda chekka bilan bog'langan har qanday ikkita cho'qqi turli ranglar bilan bo'yalgan. Uzoq vaqt davomida matematiklar bu muammoni hal qila olmadilar: umumiy chegaraga ega bo'lgan har qanday ikki mamlakat turli xil ranglar bilan bo'yalgan bo'lishi uchun o'zboshimchalik bilan geografik xaritani bo'yash uchun to'rtta rang etarlimi? Agar biz mamlakatlarni nuqta sifatida tasvirlasak - grafikning cho'qqilari, tegishli mamlakatlar ular bilan chegaradosh bo'lgan cho'qqilarni qirralar bilan bog'laydi (18-rasm), u holda muammo quyidagicha qisqartiriladi: har qanday mamlakatning xromatik soni rostmi? tekislikda joylashgan grafik to'rtdan ortiq emasmi? Bu savolga ijobiy javob faqat yaqinda kompyuter yordamida olingan.

guruch. 18

"To'rt rang" o'yini

Stiven Barr ikki o'yinchi uchun "To'rt rang" deb nomlangan qog'oz mantiqiy o'yinni taklif qildi. Martin Gardnerning so'zlariga ko'ra, "Men to'rtta rang muammosini hal qilishda duch keladigan qiyinchiliklarni tushunishning ushbu qiziqarli o'yinni o'ynashdan ko'ra yaxshiroq usulini bilmayman".

Ushbu o'yin uchun to'rtta rangli qalam kerak. Birinchi o'yinchi tasodifiy bo'sh maydonni chizish bilan o'yinni boshlaydi. Ikkinchi o'yinchi uni to'rtta rangning istalgani bilan bo'yaydi va o'z navbatida o'zining bo'sh joyini chizadi. Birinchi o'yinchi ikkinchi o'yinchining maydonini bo'yab, yangi maydon qo'shadi va hokazo - har bir o'yinchi raqib maydonini bo'yab, o'zinikini qo'shadi. Bunday holda, umumiy chegaraga ega bo'lgan joylar turli ranglarda bo'yalgan bo'lishi kerak. O'z navbatida beshinchi bo'yoqni olishga majbur bo'lgan kishi yutqazadi.

Kombinator va mantiqiy masalalar.

1936 yilda nemis matematigi D.Kenig birinchi marta bunday sxemalarni o'rganishni o'tkazdi va bunday sxemalarni "grafiklar" deb nomlashni va ularning xususiyatlarini tizimli ravishda o'rganishni taklif qildi. Shunday qilib, alohida matematik intizom sifatida grafiklar nazariyasi faqat XX asrning 30-yillarida "katta tizimlar" deb ataladigan narsa foydalanishga kirishganligi sababli kiritildi, ya'ni. turli munosabatlar bilan o'zaro bog'langan ko'p sonli ob'ektlarga ega tizimlar: temir yo'llar va aviakompaniyalar tarmoqlari, ko'p minglab abonentlar uchun telefon stansiyalari, zavodlar - iste'molchilar va korxonalar - etkazib beruvchilar tizimlari, radio sxemalar, yirik molekulalar va boshqalar. va hokazo. Bunday tizimlarning ishlashini ularning dizayni, tuzilishini o'rganmasdan turib tushunish mumkin emasligi ma'lum bo'ldi. Bu erda grafik nazariyasi foydali bo'ladi. 20-asr oʻrtalarida sof matematikada (algebra, topologiya, toʻplamlar nazariyasi) grafiklar nazariyasi muammolari ham paydo boʻla boshladi. Grafik nazariyasini juda xilma-xil sohalarda qo'llash uchun u juda mavhum va rasmiylashtirilgan bo'lishi kerak. Hozirgi kunda u tez tiklanish davrini boshdan kechirmoqda Grafiklar: 1) rejalashtirish va boshqarish nazariyasida, 2) jadval tuzish nazariyasida, 3) sotsiologiyada, 4) matematik tilshunoslikda, 5) iqtisodda, 6) biologiyada. , 7) kimyo, 8) tibbiyot, 9) avtomatlar nazariyasi, elektronika kabi amaliy matematikaning sohalarida, 10) ehtimollik va kombinatoriy masalalarni yechishda va hokazo. Grafiklarga eng yaqin topologiya va kombinatorika hisoblanadi.

Kombinatorika (Kombinatorial analiz) — matematikaning diskret obʼyektlar, toʻplamlar (kombinatsiyalar, almashtirishlar, elementlarni joylashtirish va sanash) va ulardagi munosabatlarni (masalan, qisman tartib) oʻrganuvchi boʻlimi. Kombinatorika matematikaning boshqa ko'plab sohalari - algebra, geometriya, ehtimollar nazariyasi bilan bog'liq va turli xil bilim sohalarida (masalan, genetika, informatika, statistik fizika) keng qo'llanilishiga ega. "Kombinatorika" atamasi matematik foydalanishga Leybnits tomonidan kiritilgan bo'lib, u 1666 yilda o'zining "Kombinatorlik san'ati bo'yicha nutqlar" asarini nashr etgan. Ba'zan kombinatorika diskret matematikaning yanada kengroq bo'limi sifatida tushuniladi, xususan, grafiklar nazariyasi.

Grafik nazariyasi 50-yillardan boshlab keng rivojlandi. 20-asr kibernetikaning shakllanishi va kompyuter texnikasining rivojlanishi munosabati bilan. VAGrafiklar ustida uchta zamonaviy matematik ishlagan: C. Berge, O. Ore, A. Zikov.

Grafiklar ko'pincha variantlarni sanab o'tish bilan bog'liq mantiqiy muammolarni hal qilish uchun ishlatiladi. Masalan, quyidagi muammoni ko'rib chiqing. Paqirda 8 litr suv bo'lib, 5 va 3 litr hajmli ikkita idish bor. besh litrli idishga 4 litr suv quyib, chelakda 4 litrni qoldirib ketishingiz kerak, ya'ni suvni chelakka va katta idishga teng ravishda to'kib tashlang. Har bir lahzadagi vaziyatni uchta raqam bilan tasvirlash mumkin, bu erda A - chelakdagi litr suv soni, B - katta idishda, C - kichikroq. Dastlabki vaqtda vaziyat uchta (8, 0, 0) raqamlar bilan tasvirlangan, shundan ikkita holatdan biriga o'tishimiz mumkin: (3, 5, 0), agar biz katta idishni suv bilan to'ldirsak, yoki (5,0, 3), kichikroq idishni to'ldiring. Natijada biz ikkita yechimga ega bo'lamiz: biri 7 ta harakatda, ikkinchisi 8 ta harakatda.

Grafik chizish orqali oson yechish mumkin bo'lgan masalalarni ko'rib chiqamiz.

Vazifa № 1. Andrey, Boris, Viktor va Grigoriy shaxmat o'ynashdi. Har biri bir-biri bilan bitta o'yin o'ynadi. Qancha o'yin o'tkazildi?

Muammo o'g'il bolalarning har birining ismlarining birinchi harflari bilan belgilangan to'rtta A, B, C, D uchlari bo'lgan to'liq grafik yordamida hal qilinadi. To'liq grafik barcha mumkin bo'lgan qirralarni o'z ichiga oladi. Bunday holda, chekka segmentlar o'ynalgan shaxmat o'yinlarini bildiradi. Rasmdan ko'rinib turibdiki, grafik 6 ta chekkaga ega, ya'ni 6 ta o'yin o'ynalgan.

Javob: 6 ta o'yin.

Vazifa № 2. Andrey, Boris, Viktor va Grigoriy bir-birlariga o'zlarining fotosuratlarini esdalik sovg'alari sifatida berishdi. Bundan tashqari, har bir bola o'z do'stlariga bittadan fotosurat berdi. Qancha fotosurat sovg'a qilindi?

Agar siz grafik chizsangiz, yechimni osongina topish mumkin:

1 yo'l. To'liq grafikning chetidagi strelkalar yordamida fotosuratlarni almashish jarayoni ko'rsatilgan. Shubhasiz, qirralardan 2 barobar ko'p o'qlar bor, ya'ni. 12.

2-usul. 4 o'g'ilning har biri o'z do'stlariga 3 tadan fotosurat berdi, shuning uchun jami 3 tasi berildi4=12 ta surat.

Javob: 12 ta fotosurat.

Muammo No 3. Ma'lumki, uchta qizning har bir familiyasi ismlari bilan bir xil harf bilan boshlanadi. Anyaning familiyasi - Anisimova. Katyaning familiyasi Kareva emas va Kiraning familiyasi Krasnova emas. Har bir qizning familiyasi nima?

Yechish: Masala shartlariga ko‘ra, uchlari qizlarning ismlari va familiyasi bo‘lgan grafik tuzamiz. Qattiq chiziq qizning familiyasi borligini, nuqtali chiziq esa uning yo'qligini ko'rsatadi. Muammoning shartlaridan ko'rinib turibdiki, Anyaning familiyasi Anisimova (biz ikkita mos keladigan nuqtani qattiq chiziq bilan bog'laymiz). Bundan kelib chiqadiki, Katya va Kiraning familiyasi Anisimova emas. Katya Anisimova yoki Kareva emasligi sababli, bu uning Krasnova ekanligini anglatadi. Kiraning familiyasi Kareva bo'lib qolmoqda. Javob: Anya Anisimova, Katya Krasnova, Kira Kareva.

Grafik - bu ular orasidagi bog'lanishga ega bo'lgan ob'ektlar to'plami. Ob'ektlar grafikning cho'qqilari yoki tugunlari (ular nuqtalar bilan belgilanadi), ulanishlar esa yoylar yoki qirralar sifatida ifodalanadi. Agar diagrammada bir yo'nalishli aloqa strelkali chiziqlar bilan ko'rsatilgan bo'lsa, ob'ektlar orasidagi ikki tomonlama aloqa diagrammada o'qsiz chiziqlar bilan ko'rsatilgan. Kombinatoriy masalalar bilan ishlashning asosiy yo'nalishi variantlarni tasodifiy sanab o'tishdan tizimli sanab o'tishga o'tishdir. Bu turdagi masalalarni grafik yordamida aniqroq yechish mumkin.

Ko'pgina mantiqiy muammolarni grafiklar yordamida hal qilish osonroq. Grafiklar muammoning shartlarini vizual tarzda ko'rsatishga imkon beradi va shuning uchun uni hal qilishni sezilarli darajada soddalashtiradi.

Vazifa No 4. Fizika va matematika fanlariga abituriyent o'n balli tizimdan foydalangan holda uchta kirish imtihonini topshirishi kerak. Agar o'sha yili o'tish balli 28 ball bo'lsa, u universitetga o'qishga kirish uchun imtihonlarni nechta usulda topshirishi mumkin?

Yechim. Bu masalani yechish uchun, boshqa ko‘plab kombinatsion va ehtimolli masalalarda bo‘lgani kabi, tahlil qilinayotgan to‘plam elementlarini daraxt ko‘rinishida tartibga solish samaralidir. Tanlangan bir cho'qqidan birinchi imtihondagi bahoga mos qirralar chiziladi, so'ngra ularning uchlariga ikkinchi imtihonning mumkin bo'lgan natijalariga mos keladigan yangi qirralar qo'shiladi, keyin esa uchinchi.

Shunday qilib, fizika va matematikaga kirish uchun siz 10 xil usulda kirish imtihonlarini topshirishingiz mumkin.

Daraxt grafigi daraxtga tashqi o'xshashligi uchun shunday nomlangan. Daraxt grafigidan foydalanib, variantlarni hisoblash ancha oson. Variantlar daraxtini chizish siz barcha mavjud elementlar kombinatsiyasini yozib olishni xohlaganingizda ham foydalidir.

Muammo № 5. Uzoqdagi bir orolda ikkita qabila yashaydi: ritsarlar (har doim haqiqatni aytadilar) va yolg'onchilar (doim yolg'on gapiradi). Bir dono sayohatchi bu voqeani aytib berdi. “Orolga kelganimda, men ikki mahalliy aholini uchratdim va ularning qaysi qabiladan ekanligini bilmoqchi edim. Men birinchisidan so'radim: "Ikkalangiz ham ritsarmisiz?" U "ha" yoki "yo'q" deb javob bergani esimda yo'q, lekin uning javobidan qaysi biri qaysi ekanligini aniq aniqlay olmadim. Keyin men o'sha yashovchidan: "Siz bir qabiladanmisiz?" Yana, u "ha" yoki "yo'q" deb javob berganini eslay olmayman, lekin bu javobdan keyin qaysi biri ekanligini darhol taxmin qildim." Donishmand kim bilan uchrashdi?

Yechim:

Yo'q

Javob: birinchi javob "ha", ikkinchi javob "yo'q" - donishmand ikkita yolg'onchi bilan uchrashdi.

Xulosa. Grafiklar nazariyasini fan va texnikaning turli sohalarida qo‘llash.

Muhandis elektr sxemalarini chizadi.

Kimyogar murakkab molekuladagi atomlarning valentlik bog'lanishlari yordamida bir-biri bilan qanday bog'langanligini ko'rsatish uchun strukturaviy formulalarni chizadi. Tarixchi oila daraxti bo'ylab ajdodlar aloqalarini kuzatadi. Harbiy qo'mondon aloqa tarmog'ining xaritasini tuzadi, bu orqali armatura orqa tomondan oldinga bo'linmalarga yetkaziladi.

Sotsiolog bitta yirik korporatsiyaning turli bo'limlari bir-biriga qanday bo'ysunishini ko'rsatish uchun juda murakkab diagrammadan foydalanadi.

Bu misollarning barchasida qanday umumiylik bor? Ularning har birida grafik mavjud.

Grafiklar nazariyasi tilida ko‘plab texnik masalalar, iqtisodiyot, sotsiologiya, menejment va hokazo sohalarga oid masalalar shakllantiriladi va yechiladi. Grafiklar ob'ektlarni va ular o'rtasidagi munosabatlarni vizual tasvirlash uchun ishlatiladi

Grafiklar nazariyasi haligacha yechilmagan bir qancha matematik muammolarni ham o‘z ichiga oladi.

Adabiyot.

"Bolalar uchun entsiklopediya. T.11. Matematika” /Bosh muharrir. M.D.Aksenova / Avanta+ nashriyot markazi, 1998 yil.

“Matematika darsligining sahifalari ortida” Komp. S. A. Litvinova. -2-nashr, kengaytirilgan. – M.: Globus, Volgograd: Panorama, 2008 yil.

Grafiklar // Kvant. -1994.- 6-son.

Matematik jumboq va o'yin-kulgi. M. Gardner. - M.: "Mir", 1971 yil.

Zikov A.A. Grafik nazariyasi asoslari M.: Universitet kitobi, 2004 yil.

Melnikov O.I. Grafik nazariyasidagi qiziqarli muammolar Nashriyotchi: TetraSystems, 2001.

Berge K. Grafik nazariyasi va uning ilovalari. M.: IL, 1962 yil.

Vikipediya materiallari - bepul ensiklopediya.

To‘ldiruvchi: Muxina Anna, 9A sinf o‘quvchisi
Rahbar: Kolchanova G.R.
matematika o'qituvchisi

Grafik usuli juda muhim va kengdir
 Grafik usuli juda muhim va kengdir
fanning turli sohalarida qo'llaniladi va
inson hayotiy faoliyati.
inson hayotiy faoliyati.
 Ko'pgina matematik masalalarni yechish
foydalanishingiz mumkin bo'lsa, soddalashtiradi
grafiklar. Ma'lumotlarni grafik sifatida ko'rsatish
ularga aniqlik va soddalik beradi.
ham soddalashtirilgan, orttirilgan
agar siz grafiklardan foydalansangiz ishontirish.
 Ko'p matematik dalillar

Maqsad: muammolarni hal qilishni ko'rib chiqing
"Grafik" dan foydalanib, ko'rib chiqing
Algoritmlar misollari yordamida "grafiklar" va
oila daraxtlari
Vazifalar:
 Ilmiy-ommabop adabiyotlarni o'rganish
 O'tkazilgan natijalarni tahlil qiling
bu masala.
tajribalar

 Grafik - bu intuitiv tarzda ko'rish mumkin bo'lgan tizim
ko'plab doiralar va ularni bog'laydigan ko'pchilik kabi. Krujkalar
Grafikning cho'qqilari deb ataladi, o'qlari bo'lgan chiziqlar - yoylar,
o'qlarsiz - qirralar.
 Grafiklar nazariyasining boshlanishi L. Eyler qaror qilgan 1736 yilga to‘g‘ri keladi.
O'sha paytda mashhur bo'lgan "Konigsberg ko'prigi muammosi".
 “Grafik” atamasi birinchi marta 200 yildan keyin (1936 yilda) D.Kenig tomonidan kiritilgan.
 "Son" nomli matematik grafiklar umumiy belgi bilan bog'langan
 Grafiklar - kompyuter dasturlari algoritmlari, tarmoq diagrammalari
qurilish, bu erda cho'qqilar ish tugaganligini ko'rsatadigan hodisalardir
ba'zi bir maydon va bu cho'qqilarni bog'laydigan qirralarning ishlaydi
bir voqea tugagandan so'ng boshlash mumkin va yakunlanishi kerak
quyidagilarni bajaring.
lotincha "graphio" so'zidan kelib chiqqan - men yozaman. Oddiy grafiklar
tez-tez aeroportlarda joylashtirilgan aviakompaniya diagrammalari, diagrammalar
metro, geografik xaritalarda esa temir yo'llarning tasvirlari.
Grafikning tanlangan nuqtalari uning uchlari va ularni tutashtiruvchi chiziqlar deyiladi
- qovurg'alar.
 Grafiklar nazariyasidagi “daraxt” so‘zi tsikllar bo‘lmagan grafikni bildiradi, ya’ni
unda ma'lum bir cho'qqidan bir necha xilga o'tish mumkin emas
qovurg'alar va bir xil vertexga qayting.

 Königsberg shahri joylashgan
Pregel daryosining qirg'oqlari va ikkitasi
orollar. Shaharning turli qismlari
yettita ko‘prik bilan bog‘langan. tomonidan
Yakshanba kunlari shaharliklar chiqish qilishdi
shahar bo'ylab sayr qiladi. Savol: mumkinmi
shunday sayr qilishim kerakmi?
Shunday qilib, siz uydan chiqqaningizda,
ga borib orqaga qayting
har bir ko'prikda aniq bir marta.
Pregel daryosi ustidagi ko'priklar
rasmdagi kabi joylashgan.
 Tegishli grafikni ko'rib chiqing
ko'prik diagrammasi
 Muammoli savolga javob berish uchun,
hech bo'lmaganda dan bilib olish kifoya
bir cho'qqisi juft chiqadi
ko'priklar soni.
 Siz shahar bo'ylab sayr qila olmaysiz,
barcha ko'priklarni bir marta kesib o'ting
ortga qaytish.

 Chiqish yo'lini topish muammosini ko'rib chiqing
koridorlari bo'lmagan labirintdan
masalan, aylanib yurganda sodir bo'ladi
birida bo'lishi kerak
darajasi. Xuddi shunday holat
g'orlarda yoki katakombalarda.
Sud
 Rasmda qiziqarli ko'rsatilgan
Xampton bog'laridagi labirintga misol
 Tegishlisini tuzamiz
grafik. Labirintning koridorlari
grafikning qirralari va kesishmalar, o'lik uchlari,
kirish va chiqishlar cho'qqilardir.
 Endi siz buni markazda aniq ko'rishingiz mumkin
labirintga quyidagi yo'llar bilan erishish mumkin
 Va shunga ko'ra, markazni tark eting
quyidagi cho'qqilar:
1 - 4 - 7 - 10 - 9 - 11 - 12 - 13.
marshrut bo'ylab labirint:
13 - 12 - 11 - 9 - 10 - 7 - 4 - 1.

Biz grafiklarni ikkitasida batafsil ko'rib chiqamiz
misollar:
 Algoritmlar
 Oila daraxtlari

“Vatanning shonli farzandlari” nominatsiyasi

Mavzu: "Aleksey Petrovich Chulkov - Sovet Ittifoqi Qahramoni"

Galiullin Ravil

MBOU "Sovet Ittifoqi Qahramoni Aleksey Petrovich Chulkov nomidagi Yuxmachinskaya o'rta maktabi"

7-sinf o'quvchisi

Moskvina G.A.

1.Kirish.

2. Asosiy qism

2.1. A.P.ning hayoti va jasorati. Chulkova

2.2. Xotira - Sovet Ittifoqi Qahramoni nomini yodgorlik ob'ektlarida abadiylashtirish

3. Xulosa

4. Foydalanilgan adabiyotlar ro'yxati

1. Kirish

Ulug 'Vatan urushi xalqimiz boshiga tushgan eng dahshatli sinovlardan biridir. Urushning og‘irligi, qon to‘kishi odamlar ongida katta iz qoldirdi. Rossiya davlatida vatanparvarlik har doim milliy xususiyat bo'lib kelgan.

Har bir shaharu qishloqning yurtimiz sharafini ulug‘lagan o‘z qahramonlari bor. Afsuski, so‘nggi paytlarda yosh avlod bobo va bobolarimiz mehnatlarini unuta boshlagani aytilmoqda. Atrofda esa sovet xalqining jasoratini yana bir bor qoralamoqchi bo'lgan ma'lumotlar ko'paymoqda. Shuning uchun tadqiqot ishining ushbu mavzusi axloqiy va vatanparvar shaxsni tarbiyalash kabi muammolarni hal qilish uchun dolzarbdir. Bizning vazifamiz qahramonlarni yodga olish, bu xotirani asrab-avaylash va keyingi avlodlarga yetkazishdir.

O‘tmish xotirasi... Yo‘q, bu shunchaki inson ongiga xos xususiyat, uning o‘tmish izlarini saqlab qolish qobiliyati emas.

Xotira o'tmish va kelajak o'rtasidagi bog'liqlikdir. Oradan qancha yillar, necha asrlar o‘tmasin, dunyoni qo‘ng‘ir vabodan, xalqimizni halokatdan qutqarganlarni shukronalik bilan eslashimiz kerak. Va tarixning qayta yozilishiga yo'l qo'ymang.

Endi G'arbda, Boltiqbo'yi davlatlarining sobiq ittifoq respublikalarida va Ukrainada Qizil Armiya askarlarining jasoratlari fashistlar tomonidagi xizmat bilan tenglashtirilganda va SS askarlariga yodgorliklar o'rnatilganda, biz buni qilishimiz kerak. Vatan qurbongohida jonini fido qilganlarni qayta-qayta eslang.

Loyiha maqsadi: maktabimiz nomi bilan atalgan Sovet Ittifoqi Qahramonining harbiy yo'li va jasoratini o'rganish.

Vazifalar:- loyiha ustida ishlash algoritmi bilan tanishish;

Tadqiqot mavzusi bo'yicha barcha mavjud adabiyotlar va ommaviy axborot vositalarini o'rganish;

Qabul qilingan ma'lumotlarni tahlil qiling va xulosa chiqaring

Asar Sovet Ittifoqi Qahramoni, Tatar Avtonom Sovet Sotsialistik Respublikasining Yuxmachi qishlog'ida tug'ilgan Aleksey Petrovich Chulkovning tarjimai holini o'rganishga bag'ishlangan.

Sovet Ittifoqi Qahramoni Aleksey Petrovich Chulkov hamyurtimiz, Yuxmachi qishlog‘idagi maktabimiz uning nomi bilan ataladi. U kim, qanday yashagan, nimani orzu qilgan, nega Sovet Ittifoqi Qahramoni unvoni berilgan?

Ulug 'Vatan urushi tugaganiga 70 yildan ortiq vaqt o'tdi. Vatanimizning bepoyon hududida halok bo‘lganlar, jang maydonlaridan qaytmaganlar uchun obelisklar o‘rnatilgan. Ular yosh edi. Qachon ular bunchalik katta ishlarni amalga oshirib, Vatanning oliy mukofotiga nomzod bo‘lishdi? Nega ular o'zlarini qurbon qilishdi? Ular haqiqatan ham omon qolishni xohlamadilarmi?

Ilmiy ishim mavzusi: Yurtdoshim taqdiri.

Men bu savolni batafsilroq yoritishga qaror qildim. Buning uchun men maktab muzeyiga tashrif buyurdim, u erda Aleksey Petrovichga bag'ishlangan bo'lim mavjud. Shuningdek, men o'z ishimda Sovet Ittifoqi Qahramoni, general - polkovnik Vasiliy Vasilyevich Reshetnikovning Vikipediyadagi xotiralariga, shuningdek, Yu.N. Xudov "Qanotli komissar".

Usullari: Loyihani amalga oshirish jarayonida tadqiqot ishlarini olib borish algoritmi bilan tanishdim, o‘lkashunoslik bo‘yicha adabiyotlarni o‘rgandim, mavjud adabiyotlarni, internet materiallarini, bir hamkasbning xotiralarini ko‘zdan kechirdim.

Tadqiqotning ahamiyati: ushbu materialdan tarix darslarida, unutilmas sanalar va yubileylarga bag'ishlangan sinfdan tashqari mashg'ulotlarda, muzey darslarida foydalanish mumkin.

2. Asosiy qism

2.1. A.P.ning hayoti va jasorati. Chulkova

Chulkov Aleksey Petrovich 1908 yil 30 aprelda Rossiya imperiyasining Yuxmachi qishlog'ida, hozirgi Tataristonning Alkeevskiy tumanida ishchi oilasida tug'ilgan. millatiga ko'ra rus. 1920 yilda frontda yaralanib, otasi vafot etadi. To'rt bola yetim qoldi. Katta Sergey, bundan oldinroq, qarindoshlarinikiga tashrif buyurish uchun Karabanovoga jo'nab ketdi va u erda zavodga ishga joylashdi. O'n yoshli Aleksey bilan birga onasi ikkita singlisini - Olya va Polinani qoldirdi. Bu yil Volga bo'yida dahshatli qurg'oqchilik boshlandi. Katta ocharchilik boshlandi. Lyosha o'z qo'ylarini kam oziq-ovqat uchun boqib, quloqqa fermer bo'lib ishga kiradi. Bir kuni egasi Leshani kaltakladi. Va bola onasi va opalari bilan xayrlashib, Karabanovodagi ukasinikiga borishga qaror qiladi. Sayohat va oziq-ovqat uchun pul - bir tiyin emas. Xuddi shu ko'cha bolalari to'dasi bilan Lyosha Moskva tomon yo'l oladi. Kostromadagi vokzalda bizni yana bir reydda ushlab qolishdi. Shunday qilib, Aleksey Kostroma bolalar uyida tugadi, u erda qolgan ikki sinfni tugatdi va boshlang'ich maktabni tugatganligi to'g'risidagi guvohnoma bilan 14 yoshida Karabanovoga keldi.

1925 yildan - Vladimir viloyatidagi Karabanovo (hozirgi shahar) qishlog'ida yashovchi. Bu erda Aleksey 1927 yildan 1933 yilgacha 3-International to'quv fabrikasida ishlagan. Bu erda fabrikada u bo'lajak rafiqasi Vera bilan uchrashdi. Aleksey Petrovichning to'rt o'g'li bor edi.

1931 yildan KPSS(b)/KPSS aʼzosi. Moskva pedagogika institutining ishchilar fakultetini va 1-kursni tamomlagan. Moskvada ishlagan.

1933 yilda Qizil Armiya safiga chaqirilgan, 1934 yilda Lugansk harbiy aviatsiya bilim yurtini tamomlagan. U o'zining birinchi jangovar missiyalarini 1939-1940 yillardagi Sovet-Fin urushi paytida amalga oshirdi va Mannerheim liniyasi istehkomlarini bombardimon qilish va havo hujumida muvaffaqiyatli ishtirok etdi. Uchuvchi, katta siyosiy instruktor Aleksey Chulkovning jangovar mahorati va mohir samarali siyosiy faoliyati qo‘mondonlik tomonidan yuqori baholandi. Qizil Bayroq ordeni bilan taqdirlangan va unga batalyon komissari harbiy unvoni berilgan.

Birinchi kunlardan boshlab Ulug 'Vatan urushi janglarida. 1942 yil noyabr oyiga kelib, 751-havo polki eskadron komandirining siyosiy ishlar bo'yicha o'rinbosari mayor Aleksey Chulkov dushman chizig'i orqasida joylashgan harbiy-sanoat ob'ektlarini va oldingi chiziqdagi qo'shinlarini bombardimon qilish uchun 114 ta jangovar topshiriqni bajardi.

1942 yil 7-noyabrda Orsha shahri yaqinida jangovar missiyadan qaytayotganda uning samolyoti zenit o'qqa tutildi va Kaluga hududida quladi.

2004 yilda Sovet Ittifoqi Qahramoni, general-polkovnik Vasiliy Vasilyevich Reshetnikovning kitobi nashr etildi.

Urush yillarida 17-uzoq masofali bombardimonchi havo diviziyasining 751-polkida uchuvchi boʻlgan. 1942 yilda u Chulkov komissari bo'lgan eskadronda jang qildi. U bir necha bor uning rahbarligi ostida jangovar missiyalarda uchgan. Vasiliy Vasilyevich o'z komissarini shunday eslaydi: O'sha kuni, 1942 yil ettinchi noyabrdan sakkizinchi noyabrga o'tar kechasi, komissar Aleksey Petrovich Chulkovning ekipaji jangovar topshiriqdan qaytmadi. U Uruta eskadronining komissari bo'lsa-da, butun polk uni o'z komissari sifatida hurmat qildi, bu boshqalar, shu jumladan polk, ammo uchmaydigan siyosiy xodimlar orasida beixtiyor hasadni keltirib chiqardi.

Bu nozik narsa - hokimiyat, ayniqsa komissar hokimiyati. Rasmiy lavozim mezonlari bu erda umuman ishlamaydi, hatto ular hurmatning tashqi belgilarining butun majmuasini muvaffaqiyatli ta'minlasa ham. Hurmatning qat'iy bahosida faqat shaxsning axloqiy va intellektual ko'lami ko'rsatilgan. Aynan shaxslar, lavozimlar emas. Urushda amallar qadrlanardi va hatto so'z o'lik emas, balki tirik bo'lsa ham, rasmiy.

Aleksey Petrovich darslik komissari bo'lishdan yiroq edi - u tashqi tomondan mutlaqo kamtar va, albatta, tribunaga o'xshamas edi. U zo'r jangovar uchuvchi sifatida ko'proq mashhur edi va esimda, u hech kimni hisobot yoki ma'lumot bilan aldamagan. Unga kuchli tabiiy aql, mehribon qalb va kuchli jangovar ruh berilgan. U o'z Vatanining sodiq askari kabi Sovet-Fin urushidan o'tdi va Ulug' Vatan urushining birinchi kunida ikkilanmadi. Endi uning jangovar topshiriqlari soni ikkinchi yuzta edi. U oddiy kema komandiri kabi biz bilan birga uchdi, lekin u birinchi bo'lib uchishni yaxshi ko'rardi yoki ehtimol u buni yoqtirmasdi, unda taktik afzalliklarni ko'rmaydi, lekin u eskadron oldidagi joyni o'ziniki deb hisoblardi. .

Chulkov, Orsha aerodromini portlatib yuborganidan so'ng, allaqachon uyga ketayotgan edi va o'z odamlaridan yarim soat uzoqda edi, to'satdan ular o'qqa tutildi, o'ng dvigatelga bir qobiq tegdi. U cheka boshladi, gurilladi, yo'taldi va o'chirishga to'g'ri keldi. Pervanel, afsuski, aylanishda davom etdi, sirpanish muqarrar bo'ldi va mashina biroz pasayishni boshladi. Oldingi chiziqqa juda oz balandlik qolgan edi, lekin Aleksey Petrovich va uning doimiy navigatori Grigoriy Chumash yo'lda Kaluga viloyatida jangchilarimiz uchun baza topdilar va harakatda qo'nishga qaror qilishdi.

Kechasi bunday aerodromlar ishlamaydi va hatto tungi qo'nish moslamalari ham yo'q, lekin navbatchi "T" chiroqlari yoniq edi va Aleksey Petrovich qo'nish chizig'i bo'ylab, ehtimol biroz oshib ketgan holda muvaffaqiyatli qo'ndi. Aerodrom kichkina edi, kamuflyaj uchun u pichan va hayvonlarning maketlari bilan jihozlangan edi va samolyot uning eng chekkasida bo'lganida, bu "qishloq manzarasi" ni ko'rgan radio o'qotarlari bir ovozda: "Soxta aerodrom!" Aleksey Petrovich chinqirig'iga bo'ysundi va keyingi lahzada Chumash qichqirdi: "O'tir!" - allaqachon kech edi. Chap dvigatel mashinani to'liq gaz bilan tortib oldi, lekin u yo'qolgan tezlik va balandlikni tiklay olmadi, hatto bitta qo'nish moslamasi tortilmagan bo'lsa ham. Samolyot aerodrom tashqarisida aylanayotganda qanoti bilan qarag‘aylarga urilib, yerga qulagan va yonib ketgan. Tanklardan chiqqan alanga uchuvchilar kabinasi tomon o‘rmaladi. Chulkov yaralangan va o'zi o'rnidan turolmagan. U erda yonib ketdi. Yong‘inda radio operatori Dyakov ham halok bo‘lgan. Otishmachi Glazunov ko'karishlar va aşınmalar og'rig'ini engib, minora halqasi orqali chiqdi, lekin komandirga olovdan o'ta olmadi. Grisha Chumash singan navigator qobig'idan uloqtirildi va yiqilish paytida oyog'ini ikki joyidan sindirdi. U olovdan sudralib ketdi, qon oqayotgan yaralarini zig'ir parchalari bilan bog'ladi va yordam kuta boshladi. U aerodromdan keldi. Ko'p operatsiyalardan so'ng oyog'im sezilarli darajada qisqardi va men uchish ishi bilan xayrlashishga majbur bo'ldim.

Bizning afsonaviy komissarimiz shunday vafot etdi.

Urushning atigi bir yilida u 119 ta jangovar missiyani amalga oshirdi, ulardan 111 tasi tunda.

Berlin va Germaniyadagi boshqa shaharlar va harbiy ob'ektlarni bombardimon qildi. Bomba zarbalarini amalga oshirib, u front chizig'ida quruqlikdagi qo'shinlarimizni qo'llab-quvvatladi. Umri evaziga G'alaba soatini yaqinlashtirib.

Dekabr oyida polkni tuzish paytida buyruq o'qildi. Bu so'zlar bor:

Batalyon komissari Chulkov Vatanga cheksiz sadoqati, eskadronning jangovar ishini yaxshi tashkil etgani, jangdagi shaxsiy jasorati va qahramonligi uchun o'limni mensimagani uchun "Sovet Ittifoqi Qahramoni" unvoniga sazovor bo'lgan oliy hukumat mukofotiga loyiqdir. ” Lenin ordeni va “Oltin yulduz” medalini topshirish bilan - vafotidan keyin

U Kaluga shahrida dafn etilgan.

Mukofotlar

SSSR Oliy Kengashi Prezidiumining 1942 yil 31 dekabrdagi farmoni bilan Qo'mondonlikning jangovar topshiriqlarini jasorati va a'lo darajada bajarganligi uchun mayor Aleksey Petrovich Chulkov vafotidan keyin Sovet Ittifoqi Qahramoni unvoni bilan taqdirlandi.

Ikkita Lenin ordeni va ikkita Qizil Bayroq ordeni bilan taqdirlangan.

Mukofot ro'yxatidan:

Mayor Chulkov havo eskadronining siyosiy ishlar bo'yicha o'rinbosari bo'lib ishlaydi. Il-4 samolyotida tungi ekipaj tarkibida uchish, u erda navigator kapitan Chumash, o'qchi-radio operatori brigadir Kozlovskiy va havo o'qotar katta serjant Dyakov.

Ikkinchi jahon urushining birinchi kunlaridanoq faol armiya safida. Bu davrda u 114 ta jangovar jangni amalga oshirdi, ulardan 111 tasi tunda va barchasi jangovar topshiriqni a'lo darajada bajardi. U dushmanning harbiy-sanoat ob'ektlarini va orqadagi siyosiy markazlarni bombalash uchun uchdi: Berlin - 2 marta, Budapesht - 1 marta, Danzig - 1 marta, Koenigsberg - 1 marta, Varshava - 2 marta.

Nemis fashizmini mag'lub etish uchun qo'mondonlikning jangovar topshiriqlarini a'lo darajada bajarganligi uchun u Lenin va Qizil Bayroq ordeni bilan taqdirlangan. Mukofotdan keyin u 55 ta jangovar topshiriqni bajardi. Havo eskadronining harbiy komissari lavozimida ishlab yurib, shaxsiy tarkibni Vatanga sadoqat, dushmanga nafrat ruhidagi tarbiyachi sifatida ko‘rsatdi. Uning eskadroni jangovar harakatlar davomida dushmanga qarshi 951 marta parvoz qildi. O'rtoq Chulkov o'zining shaxsiy namunasi bilan qo'l ostidagi xodimlarni qahramonona ishlarga ilhomlantiradi. Intizomli, o'ziga va qo'l ostidagilarga nisbatan talabchan. U xodimlar orasida munosib obro'ga ega. U Lenin partiyasi va sotsialistik Vatan ishiga sodiqdir.

Nemis fashizmini mag'lub etish bo'yicha qo'mondonlikning jangovar topshiriqlarini a'lo darajada bajargani, ko'rsatgan jasorati va qahramonligi uchun mayor Chulkov Lenin ordeni bilan hukumat mukofotiga sazovor bo'ldi.

751 AP DD qo'mondoni Sovet Ittifoqi Qahramoni
Podpolkovnik TIHONOV 1942 yil 4 noyabr.

Harbiy kengashning xulosasi.

Sovet Ittifoqi Qahramoni unvoni hukumat mukofotiga loyiq.

Havo qo'mondoni Harbiy kengash a'zosi
uzoq masofali aviatsiya
Aviatsiya generali GOLOVANOV
Bo'lim komissari GURYANOV
1942 yil 30 noyabr

2.2. Xotira - Sovet Ittifoqi Qahramoni nomini yodgorlik ob'ektlarida abadiylashtirish

Moskvadagi Poklonnaya tepaligidagi Shon-sharaf yodgorligi

Kaluga memorial majmuasi

Vladimir viloyati, Karabanovo shahridagi ko'cha Qahramon nomi bilan atalgan.

2004 yilda V.V.Reshetnikovning Chulkov haqida hikoya qiluvchi "Nima edi, edi" kitobi nashr etildi.

Yu.N.ning "Qanotli komissar" hujjatli hikoyasi. Xudova

2000 yilda maktabimizga Yurtdosh qahramon nomi berildi.

Maktabimiz direktori Chulkov Aleksey Petrovichning qarindoshi Chulkov Petr Aleksandrovich. Maktabimiz Qahramon nomini olgani ham aynan uning faoliyati tufaylidir. Pyotr Aleksandrovichning o‘zi ham Vatanga munosib farzand. 1983 yilda SSSR Qurolli Kuchlari safiga chaqirilgan. Afgʻoniston Respublikasida xizmat qilgan, alohida motorli miltiq eskortining xavfsizlik vzvodining komandiri. U o‘z safdoshlari bilan KAMAZ avtomashinalari karvonlarini yuk bilan kuzatib bordi. Bir kuni ustun o'qqa tutildi va Pyotr Aleksandrovich yaralandi.

Chulkov Pyotr Aleksandrovich: "Afg'on urushi qatnashchisi" yulduzi, "Jangchi - internatsionalist" ordeni, "Minnatdor afg'on xalqidan" medali, SSSR Oliy Soveti Prezidiumining "Jasorat uchun" yorlig'i bilan taqdirlangan. va harbiy jasorat".

U kamtarlik, mas'uliyat, qat'iylik va nafislik bilan ajralib turadi. U o'qituvchilar va talabalar jamoalarining iqtidorli rahbari va tashkilotchisi. Uning rahbarligida maktab hududdagi eng yaxshi maktablardan biri hisoblanadi.

Yuxmachi qishlog'i maktab muzeyida ko'rgazma

Qozondagi G'alaba bog'i

Chulkov A.P.ga bag'ishlangan yodgorlik. Qahramonning Vatanidagi Yuxmachi qishlog'ida.

V.V. Reshetnikov nabirasi A.P. Chulkova bilan Elena Shusharina. Moskva 2007 yil.

3. Xulosa

Hayot va jasorat, biz bu so'zlarni tez-tez eshitamiz. O‘ttiz to‘rt yoshga to‘lgan chekkalik oddiy odam urush va qonli janglarning haqiqiy qahramoni bo‘lib chiqdi. A.P.Chulkov negadir Qahramon bo‘ldi, u oilasi, Vatani tarbiyalagan haqiqiy inson edi.

Qahramon haqidagi materiallar ustida ishlash ma'naviy yo'nalishlarni, axloqiy qadriyatlarni, umuminsoniy ustuvorliklarni belgilashga, vatanparvarlik ongini ma'naviy-axloqiy birlikning eng muhim qadriyatlaridan biri sifatida shakllantirishga yordam berdi.

Va men a'zo bo'lgan Rossiya maktab o'quvchilari harakatining ishlarida ishtirok etish zarurati aniq bo'ladi. Bu M.V nomidagi Moskva universitetida 2016 yil 28 martdagi ta'sis yig'ilishining qarori bilan tuzilgan jamoat-davlat bolalar va yoshlar tashkiloti. Lomonosov. Rossiya Federatsiyasi Prezidentining 2015 yil 29 oktyabrdagi farmoniga muvofiq. RDS quyidagi yo'nalishlarda ishlaydi: - harbiy-vatanparvarlik - "Yoshlar armiyasi"

Shaxsiy rivojlanish

Fuqarolik faolligi (ko'ngillilik, qidiruv ishlari, tarix, o'lka tarixini o'rganish)

Axborot va ommaviy axborot vositalari.

4. Adabiyotlar:

1.V.V. Reshetnikov "Nima bo'ldi, nima bo'ldi", M., 2004 yil.

2. Yu.N. Xudov "Qanotli komissar"

3. Yuxmachi qishlog‘i maktab muzeyidan olingan materiallar

4. Chulkov P.A.ning shaxsiy arxividan olingan fotosurat.

5.http://ru.wikipedia.org

Ishtirokchi ariza shakli

Respublika loyiha tanlovi “Tarixning shonli sahifalari.

“Qahramonlar maktabi” umumta’lim maktablarining 5-7-sinf o‘quvchilari uchun

Tatariston Respublikasining Qahramon nomini olgan tashkilotlari

Hudud RT, Alkeevskiy tumani, Yuxmachi qishlog'i

Nomzodlik "Vatanning shonli o'g'illari"

Ishtirokchining ismi, familiyasi Ravil Galiullin

Tug'ilgan kuni 05. 01.2005

Yosh guruhi 7-sinf

Ta'lim tashkilotining to'liq nomi MBOU "Sovet Ittifoqi Qahramoni Aleksey Petrovich Chulkov nomidagi Yuxmachinskaya o'rta maktabi"Yuxmachi qishlog'i, ko'ch. Shkolnaya, uy 10 a

Telefon raqami 89276781352

Elektron pochta [elektron pochta himoyalangan]

O'qituvchining to'liq ismi (to'liq) Moskvina Galina Aleksandrovna

O'qituvchining aloqa telefon raqami 89270389187

Shaxsiy ma'lumotlarni qayta ishlashga rozilik

men, Shubina Tatyana Nikolaevna, pasport 9200097914 , berilgan sana Qozon samolyotsozlik okrugi ATC, 01.11.2002 ________________________________________________________
(qachon, kim tomonidan)

RT, Alkeevskiy tumani, Yuxmachi qishlog'i, st. 4-maktab.

____________________________________________________________________________________________________________________

Men farzandimning shaxsiy ma'lumotlarini qayta ishlashga roziman Galiullin Ravil Rashitovich

RT, Alkeevskiy tumani, Yuxmachi qishlog'i, st. 4-maktab.

tanlovda ishtirok etish uchun Tatariston Respublikasi Ta'lim va fan vazirligining operatori.

Qayta ishlashga rozilik beriladigan shaxsiy ma'lumotlar ro'yxati: familiyasi, ismi, otasining ismi, maktab, sinf, uy manzili, tug'ilgan sanasi, telefon raqami, elektron pochta manzili, tanlovning yakuniy bosqichida ishtirok etish natijalari.

Operator shaxsiy ma'lumotlarni to'plash, tizimlashtirish, to'plash, saqlash, aniqlashtirish, foydalanish, uchinchi shaxslarga - ta'lim tashkilotlariga, tumanlar (shaharlar) ta'lim organlariga, Tatariston Respublikasi Ta'lim va fan vazirligiga, Vazirlikka o'tkazish huquqiga ega. Rossiya Federatsiyasi Ta'lim vazirligi, tanlovning turli bosqichlarini tashkil etish va o'tkazish, shaxsiy ma'lumotlarni shaxsiylashtirish, blokirovka qilish va yo'q qilish uchun mas'ul bo'lgan boshqa yuridik va jismoniy shaxslar.

Ushbu bayonot bilan men farzandimning quyidagi shaxsiy ma'lumotlarini, shu jumladan Internetda ochiq deb hisoblanishiga ruxsat beraman: familiyasi, ismi, sinfi, maktabi, maktabgacha ta'lim muassasasi, tanlovning yakuniy bosqichi natijalari, shuningdek asarning skanerlangan nusxasini jamoat mulki sifatida e'lon qilish.

Shaxsiy ma'lumotlarni qayta ishlash Rossiya Federatsiyasining 2006 yil 27 iyuldagi "Shaxsiy ma'lumotlar to'g'risida" gi 152-FZ-sonli Federal qonuni normalariga muvofiq amalga oshiriladi.

Ushbu Shartnoma imzolangan kundan boshlab kuchga kiradi va 3 yil davomida amal qiladi.

______________________ _________________________________ (shaxsiy imzo, sana)

Uchinchi shahar ilmiy

talabalar konferensiyasi

Informatika va matematika

Tadqiqot ishi

Eyler doiralari va masalani yechishda grafiklar nazariyasi

maktab matematika va informatika

Valiev Ayrat

Munitsipal ta'lim muassasasi

“10-sonli chuqurlashtirilgan o‘rta ta’lim maktabi

individual fanlar", 10 B sinf, Nijnekamsk

Ilmiy rahbarlar:

Xalilova Nafise Zinnyatullovna, matematika o‘qituvchisi

Informatika o'qituvchisi

Naberejnye Chelni

Kirish. 3

1-bob. Eyler doiralari. 4

1.1. Eyler doiralari haqidagi nazariy asoslar. 4

1.2. Eyler doiralari yordamida masalalar yechish. 9

2-bob. 13-ustunlar haqida

2.1.Grafiklar nazariyasi. 13

2.2. Grafiklar yordamida masalalarni yechish. 19

Xulosa. 22

Ma'lumotnomalar. 22

Kirish

“Bizning barcha qadr-qimmatimiz fikrlashda.

Bu bo'sh joy emas, biz to'ldira olmaydigan vaqt emas,

bizni, ya'ni fikrimizni yuksaltiradi.

Keling, yaxshi fikrlashni o'rganaylik."

B. Paskal,

Muvofiqlik. Maktabning asosiy vazifasi bolalarga katta hajmdagi bilim berish emas, balki o'quvchilarni bilimlarni o'zlari egallashga, bu bilimlarni qayta ishlash va kundalik hayotda qo'llash qobiliyatiga o'rgatishdir. Berilgan vazifalarni nafaqat yaxshi va qattiq ishlash qobiliyatiga ega, balki mantiqiy tafakkuri rivojlangan talaba ham hal qila oladi. Shu munosabat bilan ko'plab maktab fanlari bolalarda mantiqiy fikrlashni rivojlantiradigan turli xil vazifalarni o'z ichiga oladi. Ushbu muammolarni hal qilishda biz turli xil echimlardan foydalanamiz. Yechish usullaridan biri Eyler doiralari va grafiklaridan foydalanishdir.

Tadqiqot maqsadi: matematika va informatika darslarida qoʻllaniladigan materialni oʻrganish, bunda Eyler doiralari va grafiklar nazariyasi masalalarni yechish usullaridan biri sifatida qoʻllaniladi.

Tadqiqot maqsadlari:

1. "Euler doiralari", "Grafiklar" tushunchalarining nazariy asoslarini o'rganing.

2. Yuqoridagi usullardan foydalangan holda maktab kursi masalalarini yeching.

3. Matematika va informatika darslarida o‘quvchilar va o‘qituvchilar foydalanishi uchun tanlangan materiallarni tuzing.

Tadqiqot gipotezasi: Eyler doiralari va grafiklaridan foydalanish masalalarni yechishda aniqlikni oshiradi.

Tadqiqot mavzusi: tushunchalar: "Eyler doiralari", "Grafiklar", matematika va informatika bo'yicha maktab kursining muammolari.

1-bob. Eyler doiralari.

1.1. Eyler doiralari haqidagi nazariy asoslar.

Eyler doiralari (Euler doiralari) - mantiqda qabul qilingan modellashtirish usuli, mashhur matematik L. Eyler (1707-1783) tomonidan taklif qilingan, doiralar yordamida tushunchalar hajmlari orasidagi munosabatlarning vizual tasviri.

Tushunchalar hajmlari o'rtasidagi munosabatlarni doiralar yordamida belgilashni Afina neoplatonik maktabining vakili - Filopon (VI asr) ishlatgan, u Aristotelning "Birinchi Analitika" ga sharhlar yozgan.

Doira bir tushunchaning hajmini vizual ravishda tasvirlashi shartli ravishda qabul qilinadi. Tushunchaning ko'lami u yoki bu ob'ektlar sinfi ob'ektlari yig'indisini aks ettiradi. Shunday qilib, ob'ektlar sinfining har bir ob'ekti rasmda ko'rsatilganidek, aylana ichiga joylashtirilgan nuqta bilan ifodalanishi mumkin:

Berilgan ob'ektlar sinfining ko'rinishini tashkil etuvchi ob'ektlar guruhi rasmda ko'rsatilganidek, kattaroq doira ichida chizilgan kichikroq doira sifatida tasvirlangan.

https://pandia.ru/text/78/128/images/image003_74.gif" alt=" bir-biriga o'xshash sinflar" width="200" height="100 id=">!}

Aynan shu munosabat "talaba" va "komsomol a'zosi" tushunchalari doirasi o'rtasida mavjud. Ba'zi talabalar (hammasi emas) komsomol a'zolaridir; ba'zi (hammasi emas) komsomol a'zolari talabalardir. "A" doirasining soyasiz qismi "talaba" tushunchasi ko'lamining "komsomolchi" tushunchasi doirasiga to'g'ri kelmaydigan qismini aks ettiradi; B doirasining soyasiz qismi "komsomol a'zosi" tushunchasi doirasining "talaba" tushunchasi doirasiga to'g'ri kelmaydigan qismini aks ettiradi. Ikkala doira uchun umumiy bo'lgan soyali qism komsomol a'zosi bo'lgan talabalarni va talaba bo'lgan komsomol a'zolarini bildiradi.

Agar A kontseptsiya hajmida ko'rsatilgan biron bir ob'ektni bir vaqtning o'zida B kontseptsiya hajmida ko'rsatish mumkin bo'lmasa, bu holda tushunchalar hajmlari o'rtasidagi munosabatlar bir-biridan tashqarida chizilgan ikkita doira yordamida tasvirlanadi. Bir doira yuzasida yotadigan bironta ham nuqta boshqa doira yuzasida bo'lishi mumkin emas.

https://pandia.ru/text/78/128/images/image005_53.gif" alt=" bir xil hajmli tushunchalar - mos keladigan doiralar" width="200" height="100 id=">!}

Bunday munosabat, masalan, "ingliz materializmining asoschisi" va "Yangi organon muallifi" tushunchalari o'rtasida mavjud. Bu tushunchalar doirasi bir xil, ular bir xil tarixiy shaxs - ingliz faylasufi F.Bekonni aks ettiradi.

Ko'pincha shunday bo'ladi: bitta tushuncha (umumiy) bir vaqtning o'zida bir nechta aniq tushunchalarga bo'ysunadi, bu holda ular subordinatsiya deb ataladi. Bunday tushunchalar o'rtasidagi munosabatlar vizual ravishda bitta katta doira va bir nechta kichik doiralar orqali tasvirlangan, ular kattaroq doira yuzasida chizilgan:

https://pandia.ru/text/78/128/images/image007_46.gif" alt=" qarama-qarshi tushunchalar" width="200" height="100 id=">!}

Shu bilan birga, qarama-qarshi tushunchalar orasida uchinchi, o'rtacha bo'lishi mumkinligi aniq, chunki ular umumiy tushuncha doirasini to'liq tugatmaydi. Aynan shu munosabat "engil" va "og'ir" tushunchalari o'rtasida mavjud. Ular bir-birini istisno qiladilar. Bir vaqtning o'zida va bir xil munosabatda olingan bir xil narsa haqida uni ham engil, ham og'ir deb aytish mumkin emas. Ammo bu tushunchalar orasida o'rta, uchinchisi bor: ob'ektlar nafaqat engil va og'ir vaznli, balki o'rtacha og'irlikdir.

Tushunchalar o‘rtasida qarama-qarshi munosabat mavjud bo‘lsa, u holda tushunchalar hajmlari o‘rtasidagi munosabat turlicha tasvirlanadi: aylana quyidagicha ikki qismga bo‘linadi: A umumiy tushuncha, B va noB (B bilan belgilanadi) qarama-qarshi tushunchalardir. . Qarama-qarshi tushunchalar bir-birini istisno qiladi va bir xil turga tegishli bo'lib, ularni quyidagi diagramma bilan ifodalash mumkin:

https://pandia.ru/text/78/128/images/image009_38.gif" alt="ta'rif mavzusi va predikati" width="200" height="100 id=">!}

Tushunchaning ta’rifi bo‘lmagan umumiy tasdiqlovchi hukmdagi predmet hajmlari va predikat o‘rtasidagi munosabat diagrammasi boshqacha ko‘rinadi. Bunday hukmda predmet doirasi predmet doirasiga to‘liq kiradi; Shuning uchun ular orasidagi munosabatlar rasmda ko'rsatilganidek, katta va kichik doiralar orqali tasvirlangan:

Maktab kutubxonalari" href="/text/category/shkolmznie_biblioteki/" rel="bookmark">maktab kutubxonasi, 20 - tumanda. Beshinchi sinf o'quvchilaridan nechtasi:

a) maktab kutubxonasi o'quvchilari emas;

b) tuman kutubxonasi kitobxonlari emas;

v) faqat maktab kutubxonasining kitobxonlari;

d) faqat viloyat kutubxonasi kitobxonlari;

e) ikkala kutubxonaning kitobxonlarimi?

3. Sinfdagi har bir o'quvchi ingliz yoki fransuz tillarini yoki ikkalasini ham o'rganadi. 25 kishi ingliz tilini, 27 kishi fransuz tilini va 18 kishi ikkalasini ham o'rganadi. Sinfda nechta o'quvchi bor?

4. Bir varaqda maydoni 78 sm2 bo'lgan doira va 55 sm2 kvadrat chizing. Doira va kvadratning kesishish maydoni 30 sm2. Varaqning doira va kvadrat bilan band bo'lmagan qismi 150 sm2 maydonga ega. Varaqning maydonini toping.

5. Bog‘chada 52 nafar bola tarbiyalanadi. Ularning har biri kekni yoki muzqaymoqni yoki ikkalasini ham yaxshi ko'radi. Bolalarning yarmi tortni, 20 kishi esa tort va muzqaymoqni yaxshi ko'radi. Qancha bolalar muzqaymoqni yaxshi ko'radilar?

6. Talabalar ishlab chiqarish brigadasida 86 nafar yuqori sinf o‘quvchilari bor. Ulardan 8 nafari na traktorni, na kombaynni boshqarishni bilmaydi. 54 nafar o‘quvchi traktorni, 62 nafari kombaynni yaxshi o‘zlashtirgan. Bu jamoadan qancha odam traktorda ham, kombaynda ham ishlay oladi?

7. Sinfda 36 nafar o‘quvchi bor. Ularning ko'pchiligi to'garaklar: fizika (14 kishi), matematika (18 kishi), kimyo (10 kishi). Bundan tashqari, ma'lumki, uchta to'garakda 2 kishi qatnashadi; Ikkita to‘garakka qatnaydiganlardan 8 nafari matematika-fizika, 5 nafari matematika-kimyo, 3 nafari fizika-kimyo to‘garaklariga jalb etilgan. Qancha odam biron bir klubga bormaydi?

8. Maktabimizning 100 nafar oltinchi sinf o‘quvchilari o‘zlariga qaysi kompyuter o‘yinlari: simulyatorlar, kvestlar yoki strategiyalar ko‘proq yoqqanini aniqlash maqsadida so‘rovnomada qatnashdilar. Natijada 20 nafar respondent simulyatorlar, 28 nafari kvestlar, 12 nafari strategiyalarni nomladi. Ma’lum bo‘lishicha, 13 nafar maktab o‘quvchisi simulyator va kvestlarga, 6 nafar o‘quvchi simulyator va strategiyaga, 4 nafar o‘quvchi kvest va strategiyaga teng ustunlik beradi, 9 nafar o‘quvchi esa bu kompyuter o‘yinlariga mutlaqo befarq. Ba'zi maktab o'quvchilari simulyatorlar, kvestlar va strategiyalarga teng darajada qiziqish bildirishdi. Bu yigitlarning nechtasi bor?

Javoblar

https://pandia.ru/text/78/128/images/image012_31.gif" alt="Oval: A" width="105" height="105">1.!}

A – shaxmat 25-5=20 – kishi. qanday o'ynashni bilish

B – shashka 20+18-20=18 – odamlar ham shashka, ham shaxmat o‘ynaydi

2. Sh – maktab kutubxonasiga ko‘p tashrif buyuruvchilar

P - tuman kutubxonasiga ko'plab tashrif buyuruvchilar

https://pandia.ru/text/78/128/images/image015_29.gif" width="36" height="90">.jpg" width="122 height=110" height="110">

5. 46. P – tort, M – muzqaymoq

6 - bolalar tortni yaxshi ko'radilar

6. 38. T – traktor, K – kombayn

54+62-(86-8)=38 – traktorda ham, kombaynda ham ishlay oladi

grafiklar” va ularning xossalarini tizimli o‘rganadi.

Asosiy tushunchalar.

Grafiklar nazariyasining asosiy tushunchalaridan birinchisi cho'qqi tushunchasidir. Grafik nazariyasida u asosiy sifatida qabul qilinadi va aniqlanmagan. Buni o'zingizning intuitiv darajangizda tasavvur qilish qiyin emas. Odatda grafikning cho'qqilari aylana, to'rtburchaklar va boshqa shakllar ko'rinishida vizual tarzda tasvirlangan (1-rasm). Har bir grafikda kamida bitta cho'qqi bo'lishi kerak.

Grafiklar nazariyasidagi yana bir asosiy tushuncha yoylardir. Odatda, yoylar cho'qqilarni bog'laydigan tekis yoki egri segmentlardir. Yoyning har ikki uchi qandaydir cho'qqiga to'g'ri kelishi kerak. Yoyning ikkala uchi bir xil cho'qqiga to'g'ri keladigan holat istisno qilinmaydi. Masalan, 2-rasmda yoylarning maqbul tasvirlari mavjud va 3-rasmda ular qabul qilinishi mumkin emas:

Grafik nazariyasida yoylarning ikki turi qo'llaniladi - yo'naltirilmagan yoki yo'naltirilgan (yo'naltirilgan). Faqat yo'naltirilgan yoylarni o'z ichiga olgan grafik yo'naltirilgan grafik yoki digraf deb ataladi.

Yoylar bir yo'nalishli bo'lishi mumkin, har bir yoy faqat bitta yo'nalishga ega yoki ikki tomonlama bo'lishi mumkin.

Ko'pgina ilovalarda ma'noni yo'qotmasdan ko'p yo'nalishli yoyni ikki tomonlama yoy bilan, ikki tomonlama yoyni ikkita bir yo'nalishli yoy bilan almashtirish mumkin. Misol uchun, rasmda ko'rsatilganidek. 4.

Qoida tariqasida, grafik yoki darhol barcha yoylar bir xil yo'nalish xususiyatiga ega bo'ladigan tarzda tuziladi (masalan, barchasi bir yo'nalishli) yoki transformatsiyalar orqali bu shaklga keltiriladi. Agar AB yoyi yo'naltirilgan bo'lsa, demak, uning ikki uchidan biri (A) boshi, ikkinchisi (B) oxiri hisoblanadi. Bunda AB yoyining boshi A cho'qqi, oxiri esa B cho'qqisi bo'ladi, agar yoy A dan B ga yo'naltirilgan bo'lsa yoki AB yoyi A cho'qqisidan kelib, B ga kirsa, deyishadi (5-rasm). ).

Grafikning qandaydir yoy bilan bog‘langan ikkita cho‘qqisi (ba’zan yoyning yo‘nalishidan qat’iy nazar) qo‘shni cho‘qqilar deyiladi.

Grafiklarni o'rganishda muhim tushuncha yo'l tushunchasidir. A1,A2,...An yoʻli A1,A2,...An choʻqqilari va A1, 2,A2,3,...,An-1, n yoylarining ketma-ket tutashuvchi chekli ketma-ketligi (kordeji) sifatida aniqlanadi. bu uchlari.

Grafiklar nazariyasidagi muhim tushuncha ulanish tushunchasidir. Agar grafaning istalgan ikkita uchi uchun kamida bitta yo'l bo'lsa, u holda grafik bog'langan deb ataladi.

Misol uchun, agar siz odamning qon aylanish tizimini grafik sifatida tasvirlasangiz, u erda cho'qqilari ichki organlarga va yoylar qon kapillyarlariga to'g'ri keladi, unda bunday grafik aniq bog'langan. Ikki ixtiyoriy odamning qon aylanish tizimi uzilgan grafik deyish mumkinmi? Shubhasiz, yo'q, chunki ular tabiatda kuzatiladi. "Siam egizaklari".

Ulanish grafikning nafaqat sifat ko'rsatkichi (ulangan/ajralgan), balki miqdoriy ham bo'lishi mumkin.

Grafik K-bog'langan deb ataladi, agar uning har bir uchi boshqa K cho'qqi bilan bog'langan bo'lsa. Ba'zan ular zaif va kuchli bog'langan grafiklar haqida gapirishadi. Bu tushunchalar sub'ektivdir. Agar tadqiqotchining fikricha, uning har bir uchi uchun qo‘shni cho‘qqilar soni ko‘p bo‘lsa, tadqiqotchi grafikni kuchli bog‘langan deb ataydi.

Ba'zan bog'lanish har birining emas, balki bitta (ixtiyoriy) cho'qqining xarakteristikasi sifatida aniqlanadi. Keyin tip ta'riflari paydo bo'ladi: agar uning cho'qqilaridan kamida bittasi K boshqa uchlari bilan bog'langan bo'lsa, grafik K-ulangan deb ataladi.

Ba'zi mualliflar bog'lanishni miqdoriy xususiyatning ekstremal qiymati sifatida belgilaydilar. Misol uchun, agar grafada kamida bitta K qo'shni cho'qqi bilan bog'langan cho'qqi bo'lsa va K dan ortiq qo'shni cho'qqi bilan bog'lanmagan cho'qqi bo'lsa, grafik K bilan bog'langan.

Misol uchun, bolaning shaxsni chizishi (6-rasm) maksimal ulanishga ega bo'lgan 4 ga teng bo'lgan grafikdir.

Grafikning bir qator masalalarda o'rganilgan yana bir xarakteristikasi ko'pincha grafikning kardinalligi deb ataladi. Bu xarakteristika ikkita cho'qqini bog'laydigan yoylar soni sifatida aniqlanadi. Bunday holda, qarama-qarshi yo'nalishga ega bo'lgan yoylar ko'pincha alohida ko'rib chiqiladi.

Masalan, agar grafikning cho'qqilari axborotni qayta ishlash tugunlarini ifodalasa va yoylar ular o'rtasida ma'lumot uzatish uchun bir yo'nalishli kanallar bo'lsa, u holda tizimning ishonchliligi umumiy kanallar soni bilan emas, balki eng kichik kanallar soni bilan belgilanadi. har qanday yo'nalish.

Kardinallik, bog'lanish kabi, grafikning har bir juft uchi uchun ham, ba'zi (ixtiyoriy) juftlik uchun ham aniqlanishi mumkin.

Grafikning muhim xususiyati uning o'lchamidir. Ushbu kontseptsiya odatda grafikda mavjud bo'lgan cho'qqilar va yoylar soni sifatida tushuniladi. Ba'zan bu qiymat har ikkala turdagi elementlarning miqdorlari yig'indisi sifatida, ba'zan mahsulot sifatida, ba'zan faqat bir (u yoki boshqa) turdagi elementlarning soni sifatida aniqlanadi.

Grafik turlari.

Grafiklar yordamida modellashtirilgan ob'ektlar juda xilma-xil xarakterga ega. Ushbu o'ziga xoslikni aks ettirish istagi grafiklarning ko'p navlarini tavsiflashga olib keldi. Bu jarayon bugungi kungacha davom etmoqda. Ko'pgina tadqiqotchilar o'zlarining aniq maqsadlari uchun yangi navlarni kiritadilar va ularning matematik tadqiqotlarini katta yoki kamroq muvaffaqiyat bilan amalga oshiradilar.

Bu xilma-xillikning markazida biz bu erda gaplashadigan bir nechta oddiy g'oyalar mavjud.

Rang berish

Grafikni bo'yash - grafiklarni o'zgartirishning juda mashhur usuli.

Ushbu texnika modelning ravshanligini oshirish va matematik ish hajmini oshirish imkonini beradi. Rangni kiritish usullari boshqacha bo'lishi mumkin. Yoylar ham, tepaliklar ham ma'lum qoidalarga muvofiq ranglanadi. Rangni bir marta aniqlash mumkin yoki vaqt o'tishi bilan o'zgarishi mumkin (ya'ni, grafik har qanday xususiyatga ega bo'lganda); ranglar ma'lum qoidalarga muvofiq aylantirilishi mumkin va hokazo.

Misol uchun, grafik inson qon aylanishining modelini ko'rsatsin, bu erda tepaliklar ichki organlarga, yoylar esa qon kapillyarlariga to'g'ri keladi. Keling, arteriyalarni qizil va tomirlarni ko'k rangga aylantiramiz. Shunda quyidagi bayonot aniq to'g'ri - ko'rib chiqilayotgan grafikda (8-rasm) chiqadigan qizil yoylari bo'lgan faqat ikkita cho'qqi mavjud (rasmda qizil rang qalin qilib ko'rsatilgan).

Uzunlik

Ba'zan cho'qqilar bilan modellashtirilgan ob'ekt elementlari sezilarli darajada farq qiladigan belgilarga ega. Yoki rasmiylashtirish jarayonida ob'ektda haqiqatda mavjud bo'lgan elementlarga qandaydir uydirma elementlarni qo'shish foydali bo'lib chiqadi. Bu va boshqa ba'zi hollarda grafikning uchlarini sinflarga (ulushlarga) bo'lish tabiiydir. Ikki turdagi cho'qqilarni o'z ichiga olgan grafik ikki tomonlama va hokazo deb ataladi. Bu holda grafik cheklovlari turli tipdagi cho'qqilar orasidagi munosabatlarga oid qoidalarni o'z ichiga oladi. Masalan: "bir xil turdagi cho'qqilarni bog'laydigan yoy yo'q." Ushbu turdagi grafiklarning turlaridan biri "Petri to'ri" deb ataladi (9-rasm) va juda keng tarqalgan. Petri to'rlari ushbu seriyadagi keyingi maqolada batafsilroq muhokama qilinadi.

Vodiylar tushunchasini nafaqat cho'qqilarga, balki yoylarga ham qo'llash mumkin.

2.2. Grafiklar yordamida masalalarni yechish.

1. Königsberg ko'priklari bilan bog'liq muammo. Shaklda. 1-rasmda Pergola daryosining ikkita qirg'og'i, undagi ikkita orol va etti bog'lovchi ko'prikni o'z ichiga olgan Koenigsberg (hozirgi Kaliningrad) shahrining markaziy qismining sxematik rejasi ko'rsatilgan. Vazifa - quruqlikning barcha to'rt qismini aylanib o'tish, har bir ko'prikdan bir marta o'tish va boshlang'ich nuqtaga qaytish. Bu muammo 1736 yilda Eyler tomonidan hal qilingan (hech qanday yechim yo'qligi ko'rsatilgan). (10-rasm).

2. Uchta uy va uchta quduq muammosi. Uchta uy va uchta quduq bor, qandaydir tarzda samolyotda joylashgan. Yo'llar kesishmasligi uchun har bir uydan har bir quduqqa yo'lni torting (2-rasm). Bu muammo 1930 yilda Kuratovskiy tomonidan hal qilingan (hech qanday yechim yo'qligi ko'rsatilgan). (11-rasm).

3. To'rt rang muammosi. Samolyotning bir-birining ustiga chiqmaydigan hududlarga bo'linishi xarita deyiladi. Xaritadagi hududlar umumiy chegaraga ega bo'lsa, qo'shni deyiladi. Vazifa xaritani shunday rang berishdirki, ikkita qo'shni hudud bir xil rangga bo'yalmaydi (12-rasm). O'tgan asrning oxiridan boshlab, buning uchun to'rtta rang etarli ekanligi haqidagi faraz ma'lum bo'ldi. 1976 yilda Appel va Heiken kompyuter qidiruviga asoslangan to'rt rangli muammoning echimini nashr etdi. Ushbu muammoning "dasturiy" yechimi qizg'in bahs-munozaralarga sabab bo'lgan pretsedent bo'ldi, bu hech qachon tugamaydi. Nashr etilgan yechimning mohiyati to'rtta rangli teoremaga katta, ammo chekli sonli (taxminan 2000 ga yaqin) potentsial qarama-qarshi misollarni sinab ko'rish va bitta holat ham qarshi misol emasligini ko'rsatishdir. Ushbu qidiruv dastur tomonidan ming soatga yaqin superkompyuter ishida yakunlandi. Olingan yechimni "qo'lda" tekshirishning iloji yo'q - ro'yxatga olish doirasi inson imkoniyatlaridan ancha uzoqdir. Ko'pgina matematiklar savol tug'diradilar: bunday "dastur isboti" ni haqiqiy dalil deb hisoblash mumkinmi? Axir, dasturda xatolar bo'lishi mumkin ... Dasturlarning to'g'riligini rasman isbotlash usullari muhokama qilinayotgan dastur kabi murakkablikdagi dasturlarga taalluqli emas. Sinov xatolar yo'qligiga kafolat bera olmaydi va bu holda umuman mumkin emas. Shunday qilib, biz faqat mualliflarning dasturlash qobiliyatlariga tayanamiz va ular hamma narsani to'g'ri qilganiga ishonishimiz mumkin.

Dudeneyning vazifalari.

1. Smit, Jons va Robinson bir xil poyezd ekipajida haydovchi, konduktor va o‘t o‘chiruvchi sifatida ishlaydi. Ularning kasblari familiyalari bilan bir xil tartibda nomlanishi shart emas. Brigada xizmat ko‘rsatayotgan poyezdda familiyalari bir xil bo‘lgan uchta yo‘lovchi bor. Kelajakda biz har bir yo'lovchini hurmat bilan "janob" deb nomlaymiz.

2. Janob Robinson Los-Anjelesda yashaydi.

3. Dirijyor Omaxada yashaydi.

4. Janob Jons kollejda o‘rgatilgan barcha algebrani allaqachon unutgan.

5. Yo‘lovchi, dirijyorning ismi, Chikagoda yashaydi.

6. Dirijyor va yo'lovchilardan biri, matematik fizika bo'yicha mashhur mutaxassis, garchi ular bir cherkovga boradilar.

7. Smit bilyard o'yinida tasodifan uchrashganda, o't o'chiruvchini doimo yutib yuboradi.

Haydovchining familiyasi nima? (13-rasm)

Bu yerda 1-5 - harakat raqamlari, qavs ichida masala nuqtalarining raqamlari, ular asosida harakatlar (xulosalar) qilingan. Bundan tashqari, 7-banddan kelib chiqadiki, o't o'chiruvchi Smit emas, shuning uchun Smit mashinistdir.

Xulosa

O'rganilayotgan mavzu bo'yicha nazariy va amaliy materialni tahlil qilish bolalarda mantiqiy fikrlashni rivojlantirish, o'rganilayotgan materialga qiziqish uyg'otish, darslarda vizualizatsiyadan foydalanish uchun Eyler doiralari va grafiklaridan foydalanishning muvaffaqiyati haqida xulosa chiqarishga imkon beradi. shuningdek, tushunish va hal qilish uchun qiyin muammolarni osonga qisqartirish.

Ma'lumotnomalar

1. “Informatika fanidan qiziqarli vazifalar”, Moskva, 2005 yil

2. "Maktab bayramlari uchun stsenariylar" E. Vladimirova, Rostov-Don, 2001 y.

3. Qiziquvchanlar uchun topshiriqlar. , M., Ta'lim, 1992,

4. Matematikadan sinfdan tashqari ishlar, Saratov, Litsey, 2002 yil.

5. Raqamlarning ajoyib olami. , ., M., Ta'lim, 1986,

6. Algebra: 9-sinf uchun darslik. , va boshqalar, ed. , - M.: Ma'rifat, 2008 yil