Qrafik nəzəriyyəsinin müxtəlif fəaliyyət sahələrində tətbiqi. Qrafiklərin tətbiqi

Qrafik nəzəriyyəsinin başlanğıcı yekdilliklə 1736-cı ilə aid edilir, o zaman L.Euler o dövrdə məşhur olan Köniqsberq körpüləri problemini həll edir. Bununla belə, bu nəticə yüz ildən çox müddət ərzində qrafik nəzəriyyəsinin yeganə nəticəsi olaraq qaldı. Yalnız 19-cu əsrin ortalarında elektrik mühəndisi Q.Kirxhoff elektrik dövrələrinin tədqiqi üçün ağaclar nəzəriyyəsini işləyib hazırladı, riyaziyyatçı A.Kayli isə karbohidrogenlərin strukturunun təsviri ilə əlaqədar olaraq üç nəfər üçün sadalama məsələlərini həll etdi. ağac növləri.

Tapmacaların və əyləncəli oyunların (şahmat cəngavərləri, kraliçalar haqqında, “dünyaya səyahətlər”, toylar və hərəmlərlə bağlı problemlər və s.) həllindən doğan qrafik nəzəriyyəsi indi bununla bağlı problemlərin həllində sadə, əlçatan və güclü vasitəyə çevrilmişdir. problemlərin geniş spektrinə. Qrafiklər sözün əsl mənasında hər yerdə mövcuddur. Qrafiklər şəklində, məsələn, yol xəritələrini və elektrik sxemlərini, coğrafi xəritələri və molekulları şərh edə bilərsiniz. kimyəvi birləşmələr, insanlar və insan qrupları arasında əlaqələr. Son dörd onillikdə qrafik nəzəriyyəsi riyaziyyatın ən sürətlə inkişaf edən sahələrindən birinə çevrildi. Bu, sürətlə genişlənən tətbiq sahəsinin tələbləri ilə şərtlənir. İnteqral sxemlərin və idarəetmə sxemlərinin layihələndirilməsində, avtomatların, məntiqi sxemlərin, proqram blok diaqramlarının tədqiqində, iqtisadiyyat və statistikada, kimya və biologiyada, qrafik nəzəriyyəsində istifadə olunur. Böyük ölçüdə riyazi üsullar indi qrafik nəzəriyyəsi vasitəsilə elm və texnologiyaya nüfuz edir.

Bu yazı qrafik nəzəriyyəsinin düzgün problemlərini yox, onun məktəb həndəsə kursunda necə istifadə edildiyini araşdırır.

Buna görə də, tədqiqat mövzusunun aktuallığı, bir tərəfdən, qrafiklərin və əlaqəli tədqiqat metodlarının populyarlığı ilə əlaqədardır. müxtəlif səviyyələrdə demək olar ki, bütün müasir riyaziyyat, digər tərəfdən isə onun həndəsə kursunda həyata keçirilməsi üçün vahid sistem hazırlanmamışdır.

Tədqiqatın məqsədi məktəb həndəsə kursunda qrafiklərin istifadəsini öyrənməkdir.

Obyekt həndəsənin tədrisi prosesidir.

Mövzu – sinif və sinifdənkənar iş

Məqsədlər: 1) məktəb həndəsə kursunda qrafiklərdən istifadənin mahiyyətini və məzmununu müəyyən etmək;

2) 7-9-cu siniflərdə həndəsə dərslərinin keçirilməsi üçün PMC hazırlamaq.

Aparıcı mövzu həndəsi teoremlərin sübutu üçün qrafik modelin qurulmasıdır.

Nəzəri əsas:

1. 1736-cı ildə yaranmış qrafik nəzəriyyəsi (Leonard Euler (1708-1783)) sürətlə inkişaf etmiş və bu gün də öz aktuallığını saxlayır, çünki gündəlik həyat Qrafik təsvirlər, həndəsi təsvirlər və digər vizuallaşdırma üsulları və üsulları getdikcə daha çox istifadə olunur.

1. Qrafik nəzəriyyəsi müasir riyaziyyatın müxtəlif sahələrində və onun çoxsaylı tətbiqlərində istifadə olunur (Lipatov E. P.)

2. Qrafik nəzəriyyəsi riyaziyyatın riyazi məntiq, kombinatorika və s. kimi sahələrində istifadə olunur.

İşin nəzəri əhəmiyyəti aşağıdakılardan ibarətdir:

Qrafik nəzəriyyəsinin tətbiq sahələrinin müəyyən edilməsi;

Həndəsi teoremləri və problemləri öyrənmək üçün qrafik nəzəriyyəsindən istifadə etmək;

İşin praktiki əhəmiyyəti həndəsi teoremlərin isbatında və məsələlərin həllində qrafiklərdən istifadə edilməsindədir.

Bu iş nəticəsində aşağıdakılar yaradıldı:

7-9-cu siniflərdə həndəsə dərslərinin aparılması üçün proqram-metodiki kompleks.

Problemin həllini tapmaqda ən çətin şey sübut edilmiş ifadəyə səbəb olan məntiqi nəticələr zəncirinin qurulmasıdır. Məntiqi səriştəli mülahizə yürütmək üçün müxtəlif həndəsi faktları məntiqi əlaqələrə çevirməyə kömək edəcək belə təfəkkür bacarıqlarını inkişaf etdirmək lazımdır.

Düşüncə mədəniyyəti bacarıqlarını inkişaf etdirmək üçün şagirdlərin yazılı nitq formaları xüsusi rol oynayır. Yazılı iş formaları teoremləri sübut edərkən və problemləri həll edərkən məntiqi əsaslandırmada sabit bacarıqları inkişaf etdirən ən vacib fəaliyyət növüdür. Problemin şərtlərini qeyd etmək forması, hesablamalarda əsaslandırılmış abbreviatura və qeydlər və problemlərin sübutları düşüncə tərzini intizam edir və həndəsi görmə qabiliyyətini artırır. Bildiyiniz kimi, görmə düşüncəni doğurur. Problem yaranır: bir-birindən fərqli həndəsi faktlar arasında məntiqi əlaqəni necə qurmaq və onları vahid bütövlükdə necə formalaşdırmaq. Qrafik diaqramların metodu teoremlərin sübutunun və məsələlərin həllinin gedişatını görməyə imkan verir ki, bu da sübutu daha əyani edir və teoremlərin sübutlarını və məsələlərin həllini qısa və dəqiq təqdim etməyə imkan verir.

Bunun üçün ağac qrafikindən istifadə olunur.

"Ağac" ın təpələri (teorem və ya problemin şərtləri və məntiqi birləşdiricilərin ardıcıllığı) içərisində məlumat yerləşdirilən düzbucaqlılar ilə təsvir olunur və sonra oxlarla birləşdirilir. Qrafik diaqramın sonunda sübut edilməli olan ifadə var. Teoremlərin sübutunun və problemlərin həllinin təsvir edilmiş forması tələbələr üçün faydalı və rahatdır, çünki teoremlərin sübutunun və problemin həllinin əsas mərhələlərini asanlıqla müəyyən etməyə imkan verir.

Tədqiqat hissəsi.

Bölmə 1. Qrafik nəzəriyyənin yaranma tarixinin öyrənilməsi.

Qrafik nəzəriyyəsinin banisi riyaziyyatçı Leonhard Eyler (1707-1783) hesab olunur. Bu nəzəriyyənin tarixini böyük alimin yazışmaları vasitəsilə izləmək olar. Eylerin italyan riyaziyyatçısı və mühəndisi Marinoniyə Sankt-Peterburqdan 1736-cı il martın 13-də göndərdiyi məktubundan götürülmüş latın mətninin tərcüməsini təqdim edirik.

“Bir dəfə mənə Köniqsberq şəhərində yerləşən və üzərindən yeddi körpünün salındığı bir ada ilə bağlı bir problem soruşdular bildirdi ki, mən hələ də bunu bacarmamışam, amma heç kim bunun mümkün olmadığını sübut etməyib. Bunu həll etmək üçün kifayət qədər fikirləşdikdən sonra mən tamamilə inandırıcı sübuta əsaslanan asan bir qayda tapdım ki, onun köməyi ilə bütün bu cür problemlərdə hər hansı bir nömrə ilə belə bir dolamanın mümkün olub olmadığını dərhal müəyyən etmək olar. hər hansı bir şəkildə yerləşən körpülərin və ya Königsberg körpülərinin yerləşə bilməməsi üçün A adanı, B, C və D isə qitənin bir-birindən ayrılmış hissələrini ifadə edən aşağıdakı şəkildə göstərilə bilər. çayın qolları yeddi körpü a, b, c, d, e, f, g hərfləri ilə göstərilmişdir.

Bu cür problemləri həll etmək üçün kəşf etdiyi üsul haqqında Eyler yazdı

“Bu həllin təbiətinə görə, görünür, riyaziyyatla çox az əlaqəsi var və mən başa düşmürəm ki, niyə bu həlli hər hansı bir şəxsdən deyil, bir riyaziyyatçıdan gözləmək lazımdır, çünki bu qərar yalnız mülahizə ilə dəstəklənir və heç bir şey yoxdur. Bu həlli tapmaq üçün cəlb etmək lazımdır, riyaziyyata xas olan qanunlar var, buna görə də riyaziyyatla çox az əlaqəsi olan sualların digərlərindən daha çox riyaziyyatçılar tərəfindən həll olunduğunu bilmirəm.

Yəni bu körpülərin hər birinin üstündən yalnız bir dəfə keçməklə Köniqsberq körpülərinin ətrafından keçmək mümkündürmü? Cavab tapmaq üçün Eylerin Marinoniyə məktubuna davam edək:

"Məsələ müəyyən etməkdir ki, bütün bu yeddi körpüdən yalnız bir dəfə keçməklə yan keçmək mümkündür, ya yox. Mənim qaydam bu sualın aşağıdakı həllinə gətirib çıxarır. İlk növbədə, orada neçə sahəyə baxmaq lazımdır. su ilə ayrılır - belə , körpüdən başqa birindən digərinə keçidi olmayan bu nümunədə dörd belə bölmə var - A, B, C, D. Sonra, sayının olub olmadığını ayırd etmək lazımdır. bu ayrı-ayrı hissələrə aparan körpülərin sayı cüt və ya təkdir. Beləliklə, bizim vəziyyətimizdə A bölməsinə beş körpü, qalanlarına isə üç körpü gedir, yəni ayrı-ayrı hissələrə aparan körpülərin sayı təkdir və bu təkdir. problemi həll etmək üçün aşağıdakı qaydanı tətbiq edirik: əgər hər bir ayrı-ayrı hissəyə aparan körpülərin sayı bərabər olsaydı, o zaman sözügedən yol mümkün olardı və eyni zamanda onu işə salmaq olardı. hər hansı bir hissədən bu dolama yol, əgər bu nömrələrdən ikisi tək idisə, çünki yalnız biri tək ola bilməz, o zaman belə, müəyyən edildiyi kimi, keçid tamamlana bilər, ancaq birindən yalnız dolama yolun başlanğıcı alınmalıdır. tək sayda körpünün apardığı bu iki hissədən. Nəhayət, tək sayda körpünün apardığı iki hissədən çox olsaydı, bura başqa, daha ciddi problemlər gətirilsəydi, belə bir hərəkət ümumiyyətlə mümkün olmazdı, bu üsul daha çox fayda verə bilərdi diqqətdən kənarda qalmamalıdır”.

Yuxarıdakı qaydanın əsaslandırılmasını L. Eylerin dostu Ehlerə elə həmin il aprelin 3-də yazdığı məktubda tapmaq olar. Bu məktubdan bir parçanı aşağıda təkrarlayacağıq.

Riyaziyyatçı yazırdı ki, çayın çəngəlində tək sayda körpünün apardığı iki sahənin olmadığı təqdirdə keçid mümkündür. Bunu təsəvvür etməyi asanlaşdırmaq üçün şəkildəki artıq keçilmiş körpüləri siləcəyik. Yoxlamaq asandır ki, Eyler qaydalarına uyğun hərəkət etməyə başlasaq, bir körpünü keçib onu silsək, o zaman rəqəmdə yenə tək sayda körpünün apardığı iki sahənin olmadığı və əgər varsa, o hissə göstəriləcək. tək sayda körpüləri olan ərazilərdir, onlardan birində yerləşəcəyik. Bu cür irəliləməyə davam edərək bütün körpüləri bir dəfə keçəcəyik.

Köniqsberq şəhərinin körpülərinin hekayəsinin müasir davamı var.

Problem Göldə Şəkil 2-də göstərildiyi kimi bir-birinə bağlı olan yeddi ada var. Qayıq səyahətçiləri hansı adaya aparmalıdır ki, onlar hər körpüdən və yalnız bir dəfə keçə bilsinlər? Niyə səyahətçilər A adasına aparıla bilmirlər?

Həll. Bu problem Köniqsberq körpüləri probleminə bənzədiyi üçün onu həll edərkən Eyler qaydasından da istifadə edəcəyik. Nəticədə belə cavab alırıq: qayıq səyahətçiləri E və ya F adasına aparmalıdır ki, onlar hər körpüdən bir dəfə keçə bilsinlər. Eyni Eyler qaydasından belə çıxır ki, A adasından başlayarsa, tələb olunan dolama yolu qeyri-mümkündür.

Sonradan Koeniq (1774-1833), Hamilton (1805-1865), müasir riyaziyyatçılar C.Berge, O.Ore, A.Zıkov qrafiklər üzərində işlədilər.

Tarixən qrafik nəzəriyyəsi iki yüz ildən çox əvvəl tapmacaların həlli prosesində yaranmışdır. O, çox uzun müddət elmi tədqiqatların əsas istiqamətlərinin kənarında idi, riyaziyyat səltənətində o, yalnız ümumi diqqət mərkəzində olanda istedadları tam üzə çıxan Zoluşka mövqeyində idi.

Məşhur İsveçrə riyaziyyatçısı L. Eylerə məxsus olan qrafik nəzəriyyəsi üzrə ilk əsər 1736-cı ildə ortaya çıxdı. Qrafik nəzəriyyə 19-20-ci əsrlərin əvvəllərində topologiya və kombinatorika sahəsində işlərin sayının artdığı zaman inkişafa təkan verdi. , sıx bağlı olduğu qohumluq əlaqələri kəskin şəkildə artmışdır. Qrafiklərdən elektrik dövrə diaqramlarının və molekulyar sxemlərin qurulmasında istifadə olunmağa başlandı. Ayrı bir riyazi fən kimi qrafik nəzəriyyəsi ilk dəfə XX əsrin 30-cu illərində macar riyaziyyatçısı Koeniqin əsərində təqdim edilmişdir.

Son zamanlarda qrafiklər və əlaqəli tədqiqat metodları müxtəlif səviyyələrdə demək olar ki, bütün müasir riyaziyyata üzvi şəkildə nüfuz etmişdir. Qrafik nəzəriyyə topologiyanın qollarından biri hesab olunur; həm də bilavasitə cəbr və ədədlər nəzəriyyəsi ilə bağlıdır. Qrafiklərdən planlaşdırma və nəzarət nəzəriyyəsi, planlaşdırma nəzəriyyəsi, sosiologiya, riyazi dilçilik, iqtisadiyyat, biologiya, tibb və coğrafiyada səmərəli istifadə olunur. Qrafiklərdən proqramlaşdırma, sonlu dövlət maşınları nəzəriyyəsi, elektronika, ehtimal və kombinator məsələlərin həllində, ən qısa məsafədə və s. kimi sahələrdə geniş istifadə olunur. Riyazi əyləncələr və tapmacalar da qrafik nəzəriyyəsinin bir hissəsidir. Qrafik nəzəriyyəsi sürətlə inkişaf edir və yeni tətbiqlər tapır.

Bölmə 2. Qrafiklərin əsas növləri, anlayışları və strukturu.

Qrafik nəzəriyyə riyaziyyatçıların səyləri ilə yaradılmış riyazi bir intizamdır, buna görə də onun təqdimatı lazımi ciddi tərifləri ehtiva edir.

Qrafik, qrafikin təpələri adlanan sonlu sayda nöqtələrin və bu təpələrdən bəzilərini cüt-cüt birləşdirən xətlərin, qrafikin kənarları və ya qövsləri adlanan məcmusudur.

No. Qrafikin adı Tərif Şəkil Bu tip qrafikdən istifadə nümunəsi

1 Sıfır qrafiki Qrafikin aid olmayan təpələri Problem: Arkadi, Boris. Vladimir, Qriqori və Dmitri görüşəndə bir-birinin əlini sıxdı; Neçə kənarın olduğu təcrid adlanır. əl sıxma edildi? Əl sıxmalarının hələ edilmədiyi ana uyğun olan vəziyyət şəkildə göstərilən nöqtə nümunəsidir.

Yalnız təcrid olunmuş təpələrdən ibarət qrafikə sıfır qrafik deyilir.

Qeyd: O" – təpələri olan və kənarları olmayan qrafik

2 Tam qrafiklər Hər bir təpə cütünün olduğu qrafik Qeyd edək ki, əgər tam qrafikdə n təpə varsa, o zaman kənarların sayı olacaqdır. Bütün əl sıxışmaları tamamlanmışdır.

Təyinat: U" – n 10-dan ibarət qrafik.

bu təpələrin bütün mümkün cütlərini birləşdirən təpələr və kənarlar. Belə bir qrafiki bütün diaqonalların çəkildiyi n-bucaqlı kimi təqdim etmək olar

3 Natamam qrafiklər Bütün əl sıxmaların hələ tamamlanmadığı, A və B, A və D, D əl sıxışmaları və mümkün kənarları sarsıdılmış qrafiklər natamam G, C və D adlanır.

4 Qrafikdəki yol. Velosiped. Qrafikdə bir təpədən digərinə gedən yol A nöqtəsində qar təmizləyən maşın üçün qaraj var. Şəhərin şəkildə görünən hissəsinin küçələrini qardan təmizləmək üçün avtomobilin sürücüsü çağırılıb. Sürücü şəhərin öz hissəsində bu küçələr arasında hər bir küçədən yalnız bir dəfə keçə bilsə, qarajın yerləşdiyi kəsişmədə işini bitirə biləcəyi kənarların ardıcıllığı ola bilərmi?

zirvələri.

Bu halda, marşrutun heç bir kənarı bir dəfədən çox görünməməlidir. Vertex, from Bu qeyri-mümkündür, çünki qrafikin bütün kənarları boyunca keçən və marşrutun çəkildiyi qapalı yol, qrafikin bütün təpələrinin dərəcələri cüt olduqda, hər kənar üçün yalnız bir dəfə mövcud olduğu deyilir.

yolun başlanğıcı, marşrutun sonundakı zirvə -

yolun sonu. Dövr, rəqəmin qrafikdən istifadə edərək başlanğıcı və sonu üst-üstə düşən məskunlaşmış ərazilər arasında yolların diaqramını göstərdiyi bir yoldur. Sadə məqamlarda.

dövrə keçməyən dövrdür, məsələn, A nöqtəsindən (qrafik zirvəsi) H nöqtəsinə müxtəlif marşrutlar ilə çatmaq olar: ADGH, AEH, AEFCEH, ABCEH.

qrafikin təpələrindən birindən çox AEH marşrutu AEFCEH marşrutundan nə ilə fərqlənir?

dəfə. Çünki ikinci marşrut üzrə biz iki dəfə E nöqtəsindəki “yol ayrıcında” olduq.

Bu marşrut AEH-dən daha uzundur. AEH marşrutu marşrutdan əldə edilə bilər

Əgər dövrəyə AEFCEH-nin bütün kənarları daxildirsə, sonuncudan FCE marşrutunu “xırdalayın”.

qrafiki bir dəfə, sonra belə bir dövr Route AEH qrafikdə bir yoldur, lakin marşrut AEFCEH bir yol deyil.

Eyler xətti adlanır.

Birləşdirilmiş və ayrılmış qrafiklər. Müəyyən 1: 12 dm uzunluğunda bir teldən kənar uzunluğu olan bir kub çərçivəsi etmək mümkündürmü?

Qrafikin iki təpəsi naqili parçalara ayırmadan 1 dm-ə bağlıdır?

qrafikdə ucları bu təpələrdə olan yol varsa. Əgər belə bir yol yoxdursa, təpələrin bağlı olmadığı deyilir.

Qrafikin bütün kənarları və hər kənarı boyunca yalnız bir dəfə keçən yol yalnız aşağıdakı hallarda mövcuddur:

1) hər təpənin dərəcəsi bərabər olduqda (yol bağlıdır)

2) tək dərəcə ilə yalnız iki təpə olduqda.

Tərif 2:

Qrafikin təpələrinin hər hansı bir cütü birləşdirilirsə, ona bağlı deyilir.

Qrafik ən azı bir kəsilmiş təpə cütünə malikdirsə, əlaqə kəsilmiş adlanır.

6 Ağaclar Ağac hər hansı əlaqəli qrafikdir, Əlavə №1. Yolmurzaeva Tomirisin nəsil ağacı.

üstlər. Tamamilə ağaclardan ibarət olan əlaqəsi kəsilmiş qrafikə meşə deyilir.

7 İzomorf qrafiklər. Şəkildə göstərilən qrafiklər eyni məlumatları verir. Belə qrafiklər izomorf (eynilik) adlanır.

8 Müstəvi qrafik anlayışı Problemdə göstərilə bilən qrafik. Üç ayrı evdə üç təyyarə yaşayır və qonşular öz aralarında mübahisə edib. Evlərindən bir qədər aralıda qabırğalarının kəsişdiyi yerdə üç quyu var. Yalnız zirvələrdən mümkündürmü, hər bir evin quyularının hər birinə düz qoyulması çağırılır. ikisi kəsişməsin deyə yol?

Həll yolu: Səkkiz yolu çəkdikdən sonra əmin ola bilərsiniz ki, əvvəllər çəkilmiş yolların heç biri ilə kəsişməyən doqquzuncu cığır çəkmək mümkün deyil.

Təpələri olan bir qrafik quraq

A, B, C, 1, 2, 3

məsələnin şərtləri evlərə və quyulara uyğundur və biz sübut etməyə çalışacağıq ki, doqquzuncu yolu - qrafikin digər kənarları kəsməyən kənarını çəkmək olmaz.

Şəkildəki qrafikdə çəkilmiş kənarlar

A1, A2, A3 və B1, B2, VZ (A və B evlərindən bütün quyulara gedən yollara uyğundur).

Qurulmuş qrafik müstəvini üç bölgəyə ayırdı: X, Y, Z. Təpə B müstəvidə yerləşməsindən asılı olaraq bu üç bölgədən birinə düşür. Əgər təpəyə "vurulma"nın üç halının hər birini nəzərə alsanız

X, Y və ya Z sahələrindən birinə B, sonra qrafikin təpələrindən birinin hər dəfə 1, 2 və ya 3 olduğuna əmin olun.

(quyulardan biri) B təpəsi üçün “əlçatmaz” olacaq (yəni, qrafikdə artıq mövcud olan kənarları kəsməyən B1, B2 və ya B3 kənarlarından birini çəkmək mümkün olmayacaq).

Problemli sualın cavabı belə olacaq: “Xeyr!”

İstiqamətləndirilmiş Qrafiklər Qrafikin təpələrindən biri bu kənarın başlanğıcı, digəri isə sonu hesab edilirsə, ona istiqamətlənmiş kənar deyilir.

Bütün kənarlarının istiqamətləndirildiyi qrafikə istiqamətlənmiş qrafik deyilir.

Beləliklə, mən qrafik nəzəriyyəsinin əsas anlayışlarını nəzərdən keçirdim, onsuz teoremləri sübut etmək və nəticədə problemləri həll etmək mümkün olmayacaqdı.

Görülən işlərə dair nəticə:

Mən bütün informasiya materiallarını cədvəl şəklində qurmağı öyrəndim;

Aranjiman nəzəri material qrafiklərin növləri və onların tətbiqi haqqında vizual anlayışa töhfə vermək;

Ailə ağacımı tərtib edərkən qrafik nəzəriyyəsindən istifadə nümunələri üzərində işlədim.

Əlavə №1.

GENEOLOJİ AĞAC

Zholmurzaeva Tomirisin nəsil ağacını qurun.

Həll üsulu.

Problemi həll etməyin qrafik yolu.

Problemi həll etməyin qrafik yolu "məntiqi şərtlər ağacı" çəkməkdir. “Ağac” qohumlar arasında məntiqi əlaqəni sadə rəsm şəklində ifadə edir. Ağacdakı hər nəsil bir budağa uyğun gəlir.

Nümunə olaraq ailə ağacımı götürdüm.

Bölmə 3. Qrafik nəzəriyyəsinin tətbiqi.

Qrafiklərlə ilk baxışda mümkün olduğundan daha tez-tez qarşılaşırıq. Qrafiklərə misal olaraq hər hansı yol xəritəsini, elektrik diaqramını, çoxbucaqlıların rəsmini və s. daxildir. Uzun müddətdir ki, qrafik nəzəriyyəsindən əsasən məntiqi məsələlərin həllində istifadə olunur. Məntiqi məsələləri həll edərkən, problemdə verilmiş çoxsaylı şərtləri xatırlamaq və onlar arasında əlaqə yaratmaq çox vaxt çətin olur, qrafiklər bu cür məsələlərin həllinə kömək edir, problemin verilənləri arasındakı əlaqələri əyani şəkildə təqdim etməyə imkan verir. Qrafik nəzəriyyənin özü həndəsənin bir hissəsi hesab olunurdu. Bununla belə, iyirminci əsrdə qrafik nəzəriyyəsinin geniş tətbiqi iqtisadiyyatda, biologiyada, kimyada, elektronikada, şəbəkə planlaşdırılması, kombinatorika və elm və texnikanın digər sahələri. Nəticədə, o, sürətlə inkişaf etməyə başladı və müstəqil şaxələnmiş nəzəriyyəyə çevrildi, bir çox riyazi məsələlərin həlli qrafiklərdən istifadə etmək mümkün olduqda sadələşdirilir. Məlumatların qrafik şəklində təqdim edilməsi onu daha aydın edir. Bir çox sübutlar da sadələşdirilir və qrafiklərdən istifadə etsəniz daha inandırıcı olur.

3. 1. Həndəsi məsələlərdə və teoremlərdə qrafiklərin tətbiqi.

Qrafiklərdən istifadə edərək, ifadənin sübuta yetirilməsinə səbəb olan məntiqi nəticələrin zəncirlərini asanlıqla qura bilərsiniz. Teoremin isbatını və məsələnin həllini qısa və dəqiq ifadə edin.

Sübut edin ki, ikitərəfli üçbucaq üçün təməldəki təpələrdən çəkilmiş bissektrisalar bərabərdir.

Həll üsulları.

Münaqişədən istifadə edərək problemin sübutu.

ABC ilə ikitərəfli üçbucaq olsun

B1 A1 əsası AB və bissektrisalar AA1 və BB1.

∆АВВ1 və ∆ВАА1-i nəzərdən keçirək. Onların ∟В1АВ= var

∟A1BA, ∆ABC ikitərəfli üçbucağın təməlindəki bucaqlar kimi. ∟АВВ1= ∟А1АВ

A B, çünki AA1 və BB1 ikitərəfli üçbucağın təməlindəki bucaqların bisektorlarıdır. AB ümumi tərəfidir. deməkdir

∆АВВ1 = ∆ВАВ1 yan boyunca və iki bitişik bucaq. Üçbucaqların bərabərliyindən belə çıxır ki, onların AA1 və BB1 tərəfləri bərabərdir.

Qrafikdən istifadə edərək problemin sübutu.

Sübut edin: AA=BB

Məntiq üçün qrafikdən istifadə edirik. Qrafikin təpələri teorem və ya məsələnin şərtləri və sübutun mərhələləridir.

Qrafikin kənarları məntiqi nəticələrdir. Qrafik diaqramın sonu sübut edilə bilən bir ifadədir.

Rəng komponentləri vurğulamaq üçün istifadə olunur. Teorem və problem şərtləri mavidir. Sübut olunan ifadə qırmızıdır. Sübut mərhələləri - qara.

Teoremlərin sübutunun və problemlərin həllinin təsvir edilmiş forması tələbələr üçün faydalı və əlverişlidir, çünki teoremlərin sübutunun və problemin həllinin əsas mərhələlərini vurğulamağa imkan verir.

3. 2. Proqram-metodiki kompleks.

a) Müəllim üçün dərslik.

Təklif olunan dərslik A.V. Poqorelov tərəfindən 7-9-cu siniflər üçün həndəsə dərsliyinə uyğun tərtib edilmişdir. Onun əsas məqsədi həndəsənin öyrənilməsi prosesini lazımi əyani vəsaitlərlə təmin etmək, həndəsənin tədrisində müəllimə köməklik göstərməkdir: məsələlərin həlli prosesində teoremlərin sübutu, nəzəri materialın mənimsənilməsi prosesini asanlaşdırmaqdır. Qrafik diaqramlar çoxşaxəli xarakter daşıyır və dərslərin məqsəd və formalarından asılı olaraq müxtəlif üsullarla istifadə oluna bilər: illüstrativ kimi, yeni nəzəri materialın izahı zamanı aydınlığın artırılmasına yönəldilmiş, yeni materialın ümumiləşdirilməsi və sistemləşdirilməsi zamanı (teoremlərlə qrafik diaqramlar); fərdi və frontal sorğular apararkən istifadə olunan kartlar kimi (tapşırıqlarla qrafik diaqramlar). Bu təlimat tələbə iş dəftəri ilə birlikdə verilir. Təşkil etmək üçün iş dəftərindən istifadə edilə bilər müstəqil iş dərs zamanı və dərsdən sonra tələbələr.

b) Şagirdlər üçün iş dəftəri.

Dərslik iş dəftəri şəklində hazırlanmışdır. Təlimata teoremləri olan 28 qrafik diaqram və tapşırıqları olan 28 qrafik diaqram daxildir. Qrafik diaqramlar lazımi aydınlıqla təqdim olunan və həllin çərçivəsini təmsil edən əsas proqram materialını ehtiva edir. Şagirdlər ardıcıl olaraq boş xanaları problemin həllini təşkil edən məlumatlarla doldururlar.

Rəng komponentləri vurğulamaq üçün istifadə olunur. Teorem və məsələnin şərtləri göy, isbat olunacaq müddəa qırmızı, isbatın mərhələləri qara rəngdədir.

Dərslik 7-9-cu sinif şagirdləri üçün faydalıdır.

c) Elektron təlimat.

İşin nəticələri və onların müzakirəsi. Layihə məktəb riyaziyyat kursunda qrafiklərdən istifadənin iki illik tədqiqatının nəticəsidir.

Proqramlı olaraq yaradılması - metodik kompleks və onun həyata keçirilməsi aşağıdakı müddətdə həyata keçirilmişdir:

Aristotel klubu üçün “Qrafiklərdən istifadə edərək məntiqi məsələlərin həlli” mövzusunda dərslərin keçirilməsi.

Həndəsi teoremlərin və məsələlərin isbatında qrafiklərin tətbiqi

8 və 9-cu siniflərdə həndəsə dərslərində.

Layihə ilə məktəbdə təqdimatlar elmi və praktiki konfranslar.

NƏTİCƏ.

Məktəb həndəsə kursunda qrafiklərdən istifadənin öyrənilməsinin nəticələrini yekunlaşdıraraq aşağıdakı nəticəyə gəldim:

1. Teoremlərin qrafik sübutunun və problemin həllinin ənənəvi üsuldan üstünlüyü teoremlərin və məsələlərin isbat dinamikasının illüstrasiyasıdır.

2. Həndəsi teoremlərin sübutu prosesi və qrafik-sxem metodunun məsələləri ilə tanışlıq şagirdlərin isbat qurma bacarıqlarını gücləndirməyə kömək edir.

3. 7-9-cu siniflərdə həndəsə fənninin öyrənilməsi üçün hazırlanmış proqram-metodiki kompleks: a) müəllim üçün vəsait; b) tələbələr üçün iş dəftəri; c) elektron dərslik 7-9-cu sinif şagirdləri üçün faydalıdır.

Təhsil nəşri

Yuyukin Nikolay Alekseeviç

LR nömrəsi. Möhür üçün imzalanıb

Üç. Ed. l.., .

Voronej Dövlət Texniki Universiteti

394026 Voronej, Moskovski pr. 14

MAQNİT DİSKİN SAYFASI

Ali riyaziyyat və fiziki-riyazi modelləşdirmə kafedrası

N.A. Yuyukin

DISKRET RİYAZİYYAT 1-ci hissə. Qrafik nəzəriyyəsinin elementləri

Dərslik

N.A. Yuyukin

DISKRET RİYAZİYYAT 1-ci hissə. Qrafik nəzəriyyəsinin elementləri

Dərslik

Voronej 2004

GİRİŞ

Bu dərslikdən VSTU-nun aşağıdakı ixtisaslar üzrə təhsil alan tələbələri “Diskret riyaziyyat” kursunda istifadə edə bilərlər:

090102 – Kompüter təhlükəsizliyi;

090105 – Avtomatlaşdırılmış sistemlərin informasiya təhlükəsizliyinin kompleks təminatı;

090106 - Telekommunikasiya sistemlərinin informasiya təhlükəsizliyi.

“Diskret riyaziyyat” fənni dövlət, ümumi təhsil standartlarına uyğun bilik və bacarıqların mənimsənilməsini təmin edir, eyni zamanda mənimsənilməsinə öz töhfəsini verir. fundamental təhsil, dünyagörüşünün formalaşması və məntiqi təfəkkürün inkişafı.

Qrafik nəzəriyyə diskret obyektlərlə əlaqəli müasir mühəndislik problemlərinin rəsmiləşdirilməsi üçün effektiv vasitədir. İnteqral sxemlərin və idarəetmə sxemlərinin layihələndirilməsində, avtomatik maşınların və məntiq sxemlərinin öyrənilməsində istifadə olunur. sistem təhlili, avtomatlaşdırılmış istehsala nəzarət, kompüter və informasiya şəbəkələrinin inkişafında, sxemlərin layihələndirilməsində və konstruksiya-topoloji layihələndirilməsində və s.

IN dərslik qrafik nəzəriyyəsinin əsaslarını, əsas metodlarını və alqoritmlərini təsvir edir. Burada n-qrafikləri və diqrafları təqdim edirik; izomorfizmlər; ağaclar; Eyler qrafikləri; planar qrafiklər; örtüklər və müstəqil dəstlər; güclü əlaqə

V diqraflar; Markov zəncir qrafikinin təhlili; qrafiklərdə ən qısa yolların tapılması alqoritmləri; Hamilton dövrü axtarış problemi

V qrafik; səyahət edən satıcı problemi; qrafiklərin və xəritələrin sadalanması; ekstremal vəzifələr; optimallaşdırma problemləri; universal vəzifələr; budaq və bağlama üsulu; və həmçinin yuxarıda göstərilən anlayışlardan istifadə etmək üçün praktiki bacarıqları inkişaf etdirin.

Kursun məqsədi təbiətşünaslıq və texnologiyada proses və hadisələrin modelləşdirilməsi sahəsində tələbələrin nəzəri biliklərini, praktiki bacarıq və vərdişlərini inkişaf etdirməkdir.

ke, informasiya təhlükəsizliyi sahəsində rəsmi fəaliyyəti yüksək peşəkar səviyyədə həyata keçirmək üçün zəruri olan obyektlərin kəmiyyət və keyfiyyət əlaqələrini ifadə etmək üçün riyazi simvollardan istifadə etmək bacarığı ilə.

Bu məqsədə çatmaq üçün aşağıdakı vəzifələr xidmət edir:

qrafik nəzəriyyəsi anlayışlarının mümkün olan ən geniş spektrini öyrənmək;

tədris və praktiki problemlərin həllində bacarıqlar əldə etmək;

optimallaşdırma üsullarını mənimsəmək;

məlumat problemlərinin qoyulması və həlli, qrafiklərdən istifadə edərək məlumatın modelləşdirilməsi və təhlili bacarıqlarını inkişaf etdirmək.

“Diskret Riyaziyyat” fənni tətbiqi riyazi fənlərdən biridir. O, tələbələrin “Cəbr” və “Riyazi məntiq və alqoritmlər nəzəriyyəsi” fənlərini öyrənərkən əldə etdikləri biliklərə əsaslanır. Tədris zamanı “Diskret riyaziyyat” fənninin öyrənilməsi zamanı əldə edilmiş bilik və bacarıqlardan istifadə olunur. ümumi peşəkar və xüsusi fənlər.

1. QRAF NƏZƏRİYYƏNİN ƏSAS KONSEPSİYASI.

1.1. Qrafik nəzəriyyəsinin problemləri.

Qrafik nəzəriyyə, əlaqə anlayışı ilə olduğu kimi müxtəlif obyektlər arasındakı əlaqə sistemlərini öyrənən riyaziyyatın bir sahəsidir. Bununla belə, qrafikin müstəqil tərifi nəzəriyyənin təqdimatını asanlaşdırır və onu daha başa düşülən və əyani edir.

Qrafik nəzəriyyəsinin ilk problemləri əyləncə məsələləri və tapmacaların həlli ilə bağlı idi.

İlk tapşırıq. Köniqsberq körpüləri problemi 1786-cı ildə Eyler tərəfindən qoyulmuş və həll edilmişdir. Şəhər Preqolya çayının sahilində və iki adasında yerləşirdi. Adalar şəkildə göstərildiyi kimi bir-biri ilə sahillər arasında yeddi körpü ilə birləşirdi.

Sual yarandı: hər körpüdən düz bir dəfə keçərək evdən çıxıb geri qayıtmaq olarmı?

İkinci tapşırıq. Üç ev və üç quyunun problemi. Üç ev və üç quyu var.

Yolların kəsişməməsi üçün hər evdən hər quyuya cığır çəkmək tələb olunur. Tapşırıq idi

Pontryagin və ondan müstəqil olaraq Kuratovski tərəfindən həll edilmişdir

Üçüncü tapşırıq. Təxminən dörd rəng. Təyyarədə hər hansı bir xəritəni dörd rənglə rəngləyin ki, heç bir iki bitişik sahə eyni rəngə boyanmasın.

Qrafik nəzəriyyəsinin bir çox nəticələri elm və texnologiyada praktiki məsələlərin həlli üçün istifadə olunur. Beləliklə, 19-cu əsrin ortalarında Kirchhoff mürəkkəb elektrik dövrələrini hesablamaq üçün qrafik nəzəriyyəsindən istifadə etdi. Lakin riyazi bir fən kimi qrafik nəzəriyyəsi yalnız 20-ci əsrin 30-cu illərində formalaşmışdır. Bu halda qrafiklər bəzi abstrakt riyazi obyektlər kimi qəbul edilir. Onlar sxemlərin və sistemlərin təhlili və sintezində, şəbəkənin planlaşdırılması və idarə edilməsində, əməliyyat tədqiqatlarında, proqramlaşdırmada, orqanizmin həyatının modelləşdirilməsində və digər sahələrdə istifadə olunur.

1.2. Əsas təriflər.

Qrafik G= (V,E) iki dəstdən - boş olmayan V təpələri çoxluğundan və nizamsız və nizamlı cütlər E təpələrindən ibarət topludur. Bundan sonra biz sonlu qrafikləri nəzərdən keçirəcəyik, yəni. sonlu təpə dəsti və sonlu cüt ailəsi olan qrafiklər. Düzəldilməmiş təpə cütü kənar adlanır, nizamlı cütə isə qövs deyilir.

Tipik olaraq, qrafik diaqramla təmsil olunur: təpələr nöqtələr (və ya dairələr), kənarlar ixtiyari konfiqurasiya xətləridir. Bir ox əlavə olaraq qövsdə onun istiqamətini göstərir. Qeyd edək ki, qrafiki təsvir edərkən daşıyıcı

qabırğaların həndəsi xüsusiyyətləri (uzunluq, əyrilik), eləcə də nisbi mövqe müstəvidə təpələr.

Heç bir kənara (qövsə) aid olmayan təpələr təcrid adlanır. Bir kənar və ya qövslə birləşdirilmiş təpələr bitişik adlanır. Kənar (qövs) və onun iki təpəsindən hər hansı biri insident adlanır.

Deyirlər ki, kənar (u,v) u və v təpələrini birləşdirir və qövs (u,v) u təpəsindən başlayıb v təpəsində bitir, u ilə bu qövsün başlanğıcı, v isə sonu deyilir.

Bir cüt təpə iki və ya daha çox kənar (eyni istiqamətdə qövslər) ilə birləşdirilə bilər. Belə kənarlar (qövslər) çoxlu adlanır. Qövs (və ya kənar) eyni təpədə başlaya və ya bitə bilər. Belə bir qövs (kənar) döngə adlanır. Döngələri olan qrafikə psevdoqrafik deyilir. Çox kənarları (qövsləri) olan qrafik multiqraf adlanır.

Döngələr və ya çox kənarları olmayan qrafik sadə adlanır. Sadə qrafik o zaman tam adlanır ki, onun təpələrinin hər hansı bir cütü üçün onları birləşdirən kənar (qövs) varsa. N təpələri olan tam qrafik K n ilə işarələnir. Məsələn, bunlar qrafiklərdir

Bir təcrid olunmuş təpədən (K 1) ibarət olan qrafikə trivial deyilir.

G qrafikinin tamamlayıcısı G qrafiki ilə eyni təpələrə malik olan və tam qrafik əldə etmək üçün G qrafikinə əlavə edilməli olan kənarları ehtiva edən G qrafikidir.

Diqraf olmayan hər kəsə kanonik olaraq uyğun gəlir hər bir kənarın eyni təpələrə düşən və əks istiqamətlərə malik iki qövslə əvəz olunduğu eyni təpələr dəsti ilə istiqamətlənmiş qrafik.

1.3. Qrafik təpələrinin dərəcələri.

Sadə G qrafikinin v təpəsinin dərəcəsi (valentlik) (d (v) və ya dərəcə (v)) verilmiş v təpəsinə düşən kənarların və ya qövslərin sayıdır. Psevdoqrafın təpələrinin valentliyini hesablayarkən hər bir döngə iki dəfə hesablanmalıdır.

Əgər n-qrafiyanın bütün təpələrinin dərəcələri k-yə bərabərdirsə, o zaman qrafik adlanır müntəzəm (vahid) dərəcə k. Əgər təpənin dərəcəsi 0-dırsa, o, təcrid olunur. Əgər təpənin dərəcəsi 1-dirsə, o zaman təpəyə son təpə (asma, çıxılmaz nöqtə) deyilir.

Diqraf üçün v təpəsindən çıxan qövslərin sayı deyilir

dəyişir nəticənin yarı dərəcəsi				(v) və gələnlər - yarım addım-

yeni zəng d			(v), Bu halda d (v)= münasibəti

	(v)+	(v).

Eyler teoremi: Qrafikin təpələrinin dərəcələrinin cəmidir

qabırğaların sayını iki dəfə artırın, yəni.

d(vi)



			(v)

Burada n təpələrin sayıdır; m - nömrə

qabırğalar (tağlar). Bu ifadə onunla sübut olunur ki, təpələrin dərəcələrinin cəmi hesablanarkən hər bir kənar iki dəfə - kənarın bir ucu və digəri üçün nəzərə alınır.

1.4. Qrafik izomorfizmi.

Qrafik təpələri bir-birindən müəyyən mənada fərqlənirsə, etiketlənmiş (və ya yenidən nömrələnmiş) adlanır.

etiketlər (nömrələr). Hesab nəzərə alınır tamamilə ciddi mənada verilir, əgər onun təpələri və kənarlarının nömrələnməsi sabitdirsə. Bu halda, G 1 və G 2 qrafikləri bərabər adlanır (təyinatı G 1 = G 2), əgər onların təpələri və kənarları dəstləri üst-üstə düşürsə. İki qrafik və ya psevdoqraf G 1 = (V 1 , E 1 ) və G 2 = (V 2 , E 2 ) adlanır

	izomorf (G qeydi	əgər onlar varsa

	tək-tək xəritələr: 1)	: V 1 V 2
: E 1 E 2 elə olsun ki, qrafikdə istənilən iki u, v təpəsi üçün
	((u, v)) ((u), (v)) münasibəti etibarlıdır.

	İki sadə qrafik (döngülər və çoxlu kənarlar olmadan) G 1		və G 2

qarşılıqlı eynilik varsa, izomorf olur

dəyər xəritəsi

: V 1 V 2

Bəs nə?

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

Beləliklə, yalnız təpə və kənarların nömrələnməsinə görə fərqlənən qrafiklər izomorfdur. Qrafik izomorfizmi ekvivalentlik əlaqəsidir, çünki o, aşağıdakı xüsusiyyətlərə malikdir:

Reflektorluq -

G1,

və bijeksiya

eyni funksiyadır.

Simmetriya.

bijeksiya ilə

Keçidlilik.

G 1 G 2

bijeksiya

1,a

bijeksiya ilə

sonra G G

bijeksiya ilə

2 (1 ) .

Qrafik nəzəriyyə, məsələn, coğrafi informasiya sistemlərində (GIS) tətbiq tapır. Mövcud və ya yeni layihələndirilmiş evlər, tikililər, məhəllələr və s. təpələr, onları birləşdirən yollar, kommunal şəbəkələr, elektrik xətləri və s. kənarlar hesab edilir. Belə bir qrafik üzrə aparılan müxtəlif hesablamaların istifadəsi, məsələn, ən qısa yol marşrutunu və ya ən yaxın ərzaq mağazasını tapmağa və ya optimal marşrutu planlaşdırmağa imkan verir.

Qrafik nəzəriyyə çoxlu sayda həll edilməmiş problemi və hələ də sübut olunmamış fərziyyələri ehtiva edir.

Qrafik nəzəriyyəsinin əsas tətbiq sahələri:

Kimyada (strukturları, mürəkkəb reaksiyaların yollarını təsvir etmək üçün faza qaydası qrafik nəzəriyyəsi problemi kimi də şərh edilə bilər); Hesablama kimyası qrafik nəzəriyyəsinin tətbiqinə əsaslanan nisbətən gənc kimya sahəsidir. Qrafik nəzəriyyəsi kimyainformatikanın riyazi əsasıdır. Qrafik nəzəriyyə karbohidrogenlərdə və digər üzvi birləşmələrdə nəzəri mümkün izomerlərin sayını dəqiq müəyyən etməyə imkan verir;

İnformatika və proqramlaşdırma üzrə (alqoritmin qrafik diaqramı);

Rabitə və nəqliyyat sistemlərində. Xüsusilə, İnternetdə məlumatların marşrutlaşdırılması üçün;

İqtisadiyyatda;

Logistika sahəsində;

Dövrə dizaynında (çaplı elektron lövhədə və ya mikrosxemdə elementlərin qarşılıqlı əlaqəsinin topologiyası qrafik və ya hiperqrafdır).

Xüsusi bir qrafik növü var, ağac.Ağac bağlı asiklik qrafikdir. Əlaqəlilik hər hansı bir təpə cütü arasında yolların olması, acyclicity dövrlərin olmaması və təpə cütləri arasında yalnız bir yolun olması deməkdir. Aktiv Şəkil 1.3 təqdim etdi ikili ağac.

İkili ağac- hər node ikidən çox olmayan ağac məlumat strukturu nəsilləri(uşaqlar). Tipik olaraq birincisi adlanır ana qovşaq, və uşaqlar çağırılır sol Və hüququ varislər.

Qrafiklərin matris təsviri. Hadisə matrisi.

Qrafiklərin xassələrinin təhlili üçün alqoritmik yanaşmaların inkişafı praktiki hesablamalar üçün, o cümlədən kompüterdən istifadə etmək üçün daha uyğun olan qrafiklərin təsviri üçün müəyyən üsullar tələb edir. Qrafikləri təmsil etməyin ən çox yayılmış üç yoluna baxaq.

Fərz edək ki, istiqamətləndirilməmiş qrafikin bütün təpələri və bütün kənarları və ya istiqamətləndirilmiş qrafikin bütün təpələri və bütün qövsləri (döngülər daxil olmaqla) birdən başlayaraq nömrələnir. Qrafik (istiqamətsiz və ya yönəldilmiş) tipli bir matris kimi təqdim edilə bilər, burada təpələrin sayı və kənarların (və ya qövslərin) sayıdır. İstiqamətsiz qrafik üçün bu matrisin elementləri aşağıdakı kimi müəyyən edilir:

İstiqamətləndirilmiş qrafik üçün matrisin elementləri aşağıdakı kimi müəyyən edilir:

Bu şəkildə müəyyən edilmiş tipli matris adlanır hadisə matrisi.

Hadisə matrisinin əldə edilməsinə nümunə. Aşağıda göstərilən qrafik üçün ( düyü. 2.1 aŞəkil 2.1 b).

Şəkil 2.1 a Şək. 2.1 b

Qonşuluq matrisi.

Qrafikin insident matrisi şəklində təqdim edilməsi nəzəri tədqiqatlarda çox mühüm rol oynamasına baxmayaraq, praktikada bu üsul çox səmərəsizdir. Hər şeydən əvvəl, matrisin hər bir sütunda yalnız iki sıfırdan fərqli elementi var ki, bu da çox sayda təpələr olduqda qrafiki təmsil etməyin bu üsulunu qənaətsiz edir. Bundan əlavə, bir hadisə matrisindən istifadə edərək praktiki problemlərin həlli çox əmək tələb edir.

Məsələn, insidans matrisindən istifadə edərək istiqamətləndirilmiş bir qrafikdə belə sadə bir problemin həlli üçün vaxt xərclərini qiymətləndirək: müəyyən bir təpə üçün onun "mühitini" tapın - təpənin davamçıları və sələfləri dəsti, yəni. birbaşa əldə edilə bilən bütün təpələrin çoxluğu və birbaşa əldə edilə bilən bütün təpələrin çoxluğu.

İstiqamətləndirilmiş qrafikin insident matrisində bu problemi həll etmək üçün sıfırdan fərqli element (+1 və ya –1) görünənə qədər nömrə ilə cərgə boyunca getməlisiniz. +1 aşkar edilərsə, müvafiq sütunda –1 rəqəminin yazıldığı sətri tapmaq lazımdır. Bu nömrənin göründüyü sətrin nömrəsi bu təpədən birbaşa əldə edilə bilən təpənin nömrəsini verir. -1 aşkar edilərsə, sütunda 1-dən ibarət olan cərgəni tapmalı və bu təpənin birbaşa əlçatan olduğu təpənin nömrəsini almalısınız. Bütün "mühiti" əldə etmək üçün bütün sıfır olmayan elementlər üçün göstərilən axtarışı etməlisiniz k-ci xətt. Ən çox vaxt aparan prosedur sütunda sıfırdan fərqli element tapmaqdır. Belə axtarış prosedurlarının sayı təpənin dərəcəsinə bərabərdir. Bu halda deyəcəyik ki, təpənin mühitinin təhlili alqoritminin mürəkkəbliyi (sifarişdir).

Göründüyü kimi, bütün təpələrin "mühitinin" axtarılması, yönəldilmiş qrafikin təpələrinin sayının bütün təpələrin dərəcələrinin cəminə hasilinin sırasına görə vaxt aparacaq, bu da göstərilə bilər. istiqamətləndirilmiş qrafikin qövslərinin sayına mütənasibdir. Beləliklə, "mühit" axtarış alqoritminin mürəkkəbliyi , yəni. axtarış təpələrin sayının və qövslərin sayının hasilinin sırasına görə vaxt tələb edir.

Qrafiki təmsil edən daha səmərəli matris strukturudur təpə bitişiklik matrisi, və ya Boolean matrisi qrafik. Bu, B sıralı kvadrat matrisdir n, elementləri aşağıdakı kimi müəyyən edilir:

istiqamətsiz qrafik üçün:

istiqamətləndirilmiş qrafik üçün:

Aşağıda göstərilən qrafik üçün ( düyü. 2.2 a) insident matrisi (-də təqdim olunan matris olacaq) Şəkil 2.2 b).

Əsərin mətni şəkillər və düsturlar olmadan yerləşdirilib.
Tam versiya iş PDF formatında "İş Faylları" sekmesinde mövcuddur

GİRİŞ

“Riyaziyyatda düsturlar deyil, düşünmə prosesi yadda saxlanılmalıdır...”

E. I. İqnatyev

Qrafik nəzəriyyə hazırda riyaziyyatın intensiv inkişaf edən bir sahəsidir. Bu, sosial həyatın normal fəaliyyəti üçün çox vacib olan bir çox obyekt və vəziyyətlərin qrafik modellər şəklində təsvir edilməsi ilə izah olunur. Məhz bu amil onların daha ətraflı öyrənilməsinin aktuallığını müəyyən edir. Ona görə də bu işin mövzusu kifayət qədər aktualdır.

Hədəf tədqiqat işi: müxtəlif bilik sahələrində və məntiqi məsələlərin həllində qrafik nəzəriyyəsinin tətbiqi xüsusiyyətlərini öyrənin.

Məqsəd aşağıdakıları müəyyənləşdirdi tapşırıqlar:

qrafik nəzəriyyəsinin tarixi ilə tanış olmaq;

qrafik nəzəriyyəsinin əsas anlayışlarını və qrafiklərin əsas xarakteristikalarını öyrənmək;

qrafik nəzəriyyəsinin müxtəlif bilik sahələrində praktiki tətbiqini göstərmək;

Qrafiklərdən istifadə edərək problemləri həll etməyin yollarını nəzərdən keçirin və öz problemlərinizi yaradın.

Obyekt tədqiqat: qrafik metodunun tətbiqi üçün insan fəaliyyətinin sahəsi.

Maddə Tədqiqat: riyaziyyatın “Qrafik nəzəriyyəsi” bölməsi.

Hipoteza. Biz fərz edirik ki, qrafik nəzəriyyəsini öyrənmək tələbələrə riyaziyyatda məntiq problemlərini həll etməyə kömək edə bilər ki, bu da onların gələcək maraqlarını formalaşdıracaq.

Metodlar tədqiqat işi:

Araşdırmamız zamanı aşağıdakı üsullardan istifadə edilmişdir:

1) Müxtəlif məlumat mənbələri ilə işləmək.

2) Materialın təsviri, toplanması, sistemləşdirilməsi.

3) Müşahidə, təhlil və müqayisə.

4) Tapşırıqların hazırlanması.

Nəzəri və praktik əhəmiyyəti Bu iş onunla müəyyən edilir ki, nəticələr informatika, riyaziyyat, həndəsə, rəsm və sinif saatları, həmçinin bu mövzu ilə maraqlanan geniş oxucu kütləsi üçün. Tədqiqat işi aydın praktiki istiqamətə malikdir, çünki əsərdə müəllif bir çox bilik sahələrində qrafiklərdən istifadəyə dair çoxsaylı nümunələr təqdim edir və öz vəzifələrini tərtib edir. Bu materialdan seçmə riyaziyyat dərslərində istifadə oluna bilər.

FƏSİL I. TƏDQİQAT MÖVZUSUNDA MATERİALIN NƏZƏRİ İCARƏSİ

Riyaziyyatda “qrafik” xətlərlə birləşdirilən bir sıra nöqtələri əks etdirən şəkil kimi təsvir edilə bilər. "Count" latınca "graphio" sözündəndir - tanınmış nəcib titulu kimi yazıram.

Riyaziyyatda qrafikin tərifi aşağıdakı kimi verilir:

Riyaziyyatda "qrafik" termini aşağıdakı kimi müəyyən edilir:

Qrafik - bu sonlu nöqtələr dəstidir - zirvələri, xətlərlə birləşdirilə bilən - qabırğalar .

Qrafiklərə misal olaraq çoxbucaqlıların təsvirləri, elektrik sxemləri, hava yollarının, metroların, yolların sxematik təsvirləri və s. Ailə ağacı həm də qrafikdir, burada təpələr qəbilə üzvləridir və qohumluq əlaqələri qrafikin kənarları kimi çıxış edir.

düyü. 1 Qrafik nümunələri

Bir təpəyə aid olan kənarların sayı deyilir qrafikin təpə dərəcəsi . Əgər təpənin dərəcəsi tək ədəddirsə, təpəyə deyilir - qəribə . Əgər təpənin dərəcəsi cüt ədəddirsə, təpəyə deyilir hətta.

düyü. 2 qrafikin təpəsi

Null qrafik yalnız kənarlarla bağlanmayan təcrid olunmuş təpələrdən ibarət qrafikdir.

Tam qrafik hər bir təpə cütünün kənar ilə birləşdirildiyi qrafikdir. Bütün diaqonalların çəkildiyi N-qonaqlı tam qrafikə nümunə ola bilər.

Əgər qrafikdə başlanğıc və son nöqtələrin üst-üstə düşdüyü yol seçsəniz, belə bir yol adlanır qrafik dövrü . Qrafikin hər bir təpəsi ən çox bir dəfə keçərsə, o zaman dövrüçağırdı sadə .

Qrafikdə hər iki təpə bir kənar ilə bağlıdırsa, bu bağlıdır qrafik. Qrafik adlanır əlaqəsiz , ən azı bir cüt əlaqəsiz təpələri ehtiva edərsə.

Qrafik bağlıdırsa, lakin dövrlər yoxdursa, belə bir qrafik adlanır ağac .

Qrafın yolu ümumi təpəni paylaşan hər iki bitişik kənarın yalnız bir dəfə baş verdiyi ardıcıllıqdır.

Ən qısa təpə zəncirinin uzunluğu a və b adlanır məsafə zirvələr arasında a və b.

Vertex Açağırdı mərkəz qraf, təpələr arasındakı məsafədirsə A və hər hansı digər təpə mümkün olan ən kiçikdir. Belə bir məsafə var radius qrafik.

Qrafikin istənilən iki təpəsi arasında mümkün olan maksimum məsafə deyilir diametri qrafik.

Qrafiklərin rənglənməsi və tətbiqi.

Coğrafi xəritəyə diqqətlə baxsanız, qrafiklər olan dəmir və ya magistral yolları görə bilərsiniz. Bundan əlavə, xəritədə ölkələr (rayonlar, rayonlar) arasındakı sərhədlərdən ibarət qrafik var.

1852-ci ildə ingilis tələbəsi Frensis Qutriyə Böyük Britaniyanın xəritəsini rəngləndirmək, hər bir qraflığı ayrıca rənglə vurğulamaq tapşırığı verildi. Boyaların kiçik seçimi səbəbindən Guthrie onları təkrar istifadə etdi. O, rəngləri elə seçdi ki, haşiyənin ümumi hissəsini paylaşan əyalətlər mütləq müxtəlif rənglərə boyansın. Sual yarandı ki, müxtəlif xəritələri rəngləmək üçün minimum boya nə qədər lazımdır. Francis Guthrie, sübut edə bilməsə də, dörd rəngin kifayət edəcəyini təklif etdi. Bu problem tələbə dairələrində qızğın müzakirə olundu, lakin sonradan unudulub.

"Dörd rəng məsələsi" artan maraq doğurdu, lakin heç vaxt, hətta görkəmli riyaziyyatçılar tərəfindən də həll edilmədi. 1890-cı ildə ingilis riyaziyyatçısı Percy Heawood sübut etdi ki, istənilən xəritəni rəngləmək üçün beş rəng kifayətdir. Və yalnız 1968-ci ildə onlar qırxdan az ölkənin təsvir olunduğu xəritəni rəngləmək üçün 4 rəngin kifayət edəcəyini sübut edə bildilər.

1976-cı ildə bu problem iki amerikalı riyaziyyatçı Kenneth Appel və Wolfgangt Haken tərəfindən kompüter vasitəsilə həll edildi. Bunu həll etmək üçün bütün kartlar 2000 növə bölündü. Dörd rəngin rəngləmək üçün kifayət etməyəcəyi kartları müəyyən etmək üçün bütün növləri araşdıran bir kompüter proqramı yaradılmışdır. Kompüter yalnız üç növ xəritəni öyrənə bilmədi, ona görə də riyaziyyatçılar onları təkbaşına öyrəndilər. Nəticədə məlum olub ki, 2000 növ kartın hamısını rəngləmək üçün 4 rəng kifayət edəcək. Dörd rəng probleminin həllini elan etdilər. Həmin gün Appel və Hakenin işlədiyi universitetin poçt şöbəsi bütün markaların üzərinə “Dörd rəng kifayətdir” sözləri yazılmış möhür vurub.

Dörd rəng problemini bir az fərqli təsəvvür edə bilərsiniz.

Bunun üçün ixtiyari xəritəni nəzərdən keçirək, onu qrafik şəklində təqdim edək: dövlətlərin baş hərfləri qrafikin təpələridir, qrafikin kənarları isə dövlətlərinin ümumi sərhədi olan təpələri (başlıqları) birləşdirir. Belə bir qrafiki əldə etmək üçün aşağıdakı məsələ tərtib edilir: dörd rəngdən istifadə edərək qrafiki rəngləmək lazımdır ki, ümumi kənarı olan təpələri müxtəlif rənglərlə rənglənsin.

Eyler və Hamilton qrafikləri

1859-cu ildə ingilis riyaziyyatçısı Uilyam Hamilton bir tapmaca buraxdı - iyirmi təpəsi dirəklərlə işarələnmiş taxta dodekaedr (dodecahedron). Hər zirvədə dünyanın ən böyük şəhərlərindən birinin adı vardı - Kanton, Dehli, Brüssel və s. Tapşırıq hər bir təpəyə yalnız bir dəfə baş çəkərək çoxhərlinin kənarları boyunca gedən qapalı yolu tapmaq idi. Yolu qeyd etmək üçün dırnaqlara bağlanan bir kordon istifadə edildi.

Hamilton dövrü, yolu qrafikin bütün təpələrindən bir dəfə keçən sadə bir dövr olan bir qrafikdir.

Kalininqrad (keçmiş Koenigsberg) şəhəri Pregel çayı üzərində yerləşir. Çay bir-birinə və sahillərə körpülərlə bağlanan iki adanı yuyurdu. Köhnə körpülər artıq yoxdur. Onların xatirəsi ancaq şəhərin xəritəsində qalıb.

Bir gün bir şəhər sakini dostundan soruşdu ki, bütün körpüləri keçmək, hər birinə yalnız bir dəfə baş çəkmək və gəzinti başladığı yerə qayıtmaq olarmı? Bu problem bir çox şəhər sakinlərini maraqlandırdı, lakin heç kim həll edə bilmədi. Bu məsələ bir çox ölkələrin alimlərinin marağına səbəb olub. Məsələnin həlli riyaziyyatçı Leonhard Euler tərəfindən əldə edilmişdir. Bundan əlavə, o, bu cür problemlərin həllinə ümumi bir yanaşma formalaşdırdı. Bunun üçün o, xəritəni qrafikə çevirib. Bu qrafikin təpələri quru, kənarları isə onu birləşdirən körpülər idi.

Köniqsberq körpüsü məsələsini həll edərkən Eyler qrafiklərin xassələrini formalaşdırmağa müvəffəq oldu.

Qrafikin bütün təpələri cüt olduqda, bir təpədən başlayıb eyni təpədə bir vuruşla bitirməklə (eyni xətt üzrə iki dəfə çəkmədən və qələmi kağızdan qaldırmadan) qrafik çəkmək mümkündür.

İki tək təpəsi olan qrafik varsa, onun təpələri də bir vuruşla birləşdirilə bilər. Bunu etmək üçün birindən başlamaq və digərində, hər hansı bir tək təpədə bitirmək lazımdır.

Əgər ikidən çox tək təpəsi olan qrafik varsa, onda qrafiki bir vuruşla çəkmək olmaz.

Bu xassələri körpülər məsələsinə tətbiq etsək, görərik ki, tədqiq olunan qrafikin bütün təpələri təkdir, yəni bu qrafiki bir vuruşla bağlamaq olmaz, yəni. Bütün körpüləri bir dəfə keçib səyahəti başladığı yerdə bitirmək mümkün deyil.

Əgər qrafikin bütün kənarlarını bir dəfə ehtiva edən dövrə (mütləq sadə deyil) varsa, belə dövrə deyilir. Eyler dövrü . Eyler zənciri (yol, dövr, kontur) qrafikin bütün kənarlarını (qövslərini) bir dəfə ehtiva edən zəncirdir (yol, dövr, kontur).

II FƏSİL. TƏDQİQATIN TƏSVİRİ VƏ ONUN NƏTİCƏLƏRİ

2.1. Tədqiqatın mərhələləri

Fərziyyəni yoxlamaq üçün tədqiqat üç mərhələdən ibarət idi (Cədvəl 1):

Tədqiqat mərhələləri

Cədvəl 1.

		İstifadə olunan üsullar
Problemin nəzəri öyrənilməsi	Təhsil və elmi ədəbiyyatı öyrənin və təhlil edin.	- müstəqil düşünmə;  informasiya mənbələrinin öyrənilməsi; - lazımi ədəbiyyatı axtarın.
Case study problemlər	Sahələri nəzərdən keçirin və təhlil edin praktik tətbiq qrafiklər;	- müşahidə; - təhlil; - müqayisə; - sorğu.
Mərhələ 3. Nəticələrin praktiki istifadəsi	Öyrənilən məlumatları ümumiləşdirin;	- sistemləşdirmə;  məruzə (şifahi, yazılı, materialların nümayişi ilə)	Sentyabr 2017

2.2. Qrafiklərin praktik tətbiqi sahələri

Qrafiklər və məlumatlar

İnformasiya nəzəriyyəsi ikili ağacların xüsusiyyətlərindən geniş istifadə edir.

Məsələn, müəyyən sayda mesajları sıfırların və müxtəlif uzunluqların müəyyən ardıcıllığı şəklində kodlaşdırmaq lazımdırsa. Orta söz uzunluğu digər ehtimal paylamaları ilə müqayisədə ən kiçikdirsə, kod verilmiş kod söz ehtimalı üçün ən yaxşı hesab olunur. Bu problemi həll etmək üçün Huffman kodun axtarış nəzəriyyəsi çərçivəsində ağac-qrafik kimi təqdim edildiyi bir alqoritm təklif etdi. Hər bir təpə üçün bir sual təklif olunur, cavabı "bəli" və ya "yox" ola bilər - bu təpədən çıxan iki kənara uyğundur. Belə bir ağacın tikintisi tələb olunanları qurduqdan sonra tamamlanır. Bundan bir neçə nəfərlə müsahibə zamanı istifadə oluna bilər, əvvəlki sualın cavabı əvvəlcədən məlum olmayanda, müsahibə planı ikili ağac kimi təqdim olunur.

Qrafiklər və kimya

A.Ceyley molekulları düsturla verilmiş doymuş (və ya doymuş) karbohidrogenlərin mümkün strukturları məsələsini də nəzərdən keçirdi:

CnH 2n+2

Bütün karbohidrogen atomları 4 valentli, bütün hidrogen atomları 1 valentlidir. Struktur formullarƏn sadə karbohidrogenlər şəkildə göstərilmişdir.

Hər bir doymuş karbohidrogen molekulu bir ağac şəklində təmsil oluna bilər. Bütün hidrogen atomları çıxarıldıqda, qalan karbohidrogen atomları dərəcələri dörddən çox olmayan ucları olan bir ağac əmələ gətirir. Bu o deməkdir ki, mümkün arzu olunan strukturların sayı (müəyyən maddənin homoloqları) təpə dərəcələri 4-dən çox olmayan ağacların sayına bərabərdir. Bu problem müəyyən bir növ ağacların sadalanması problemini azaldır. D.Polya bu problemi və onun ümumiləşdirmələrini nəzərdən keçirdi.

Qrafiklər və biologiya

Bakteriyaların çoxalması prosesi bioloji nəzəriyyədə tapılan budaqlanma proseslərinin növlərindən biridir. Hər bir bakteriya müəyyən müddətdən sonra ya ölsün, ya da ikiyə bölünsün. Buna görə də, bir bakteriya üçün onun nəslinin çoxalmasının ikili ağacını alırıq. Problemin sualı belədir: o, neçə haldan ibarətdir? k nəsilləri n-ci nəsil bir bakteriya? Biologiyada bu əlaqə Galton-Watson prosesi adlanır ki, bu da tələb olunan halların tələb olunan sayını ifadə edir.

Qrafiklər və Fizika

Hər hansı bir radio həvəskarı üçün çətin və yorucu bir iş çap sxemlərinin yaradılmasıdır (dielektrik - izolyasiya materialı və metal zolaqlar şəklində həkk olunmuş izlər). Yolların kəsişməsi müəyyən qaydalara uyğun olaraq yalnız müəyyən nöqtələrdə (triodların, rezistorların, diodların və s. Yerlərdə) baş verir. Nəticədə, alim təpələri daxil olan düz bir qrafik çəkmək vəzifəsi ilə üzləşir

Beləliklə, yuxarıda göstərilənlərin hamısı qrafiklərin praktik dəyərini təsdiqləyir.

İnternet riyaziyyatı

İnternet informasiyanın saxlanması və ötürülməsi üçün bir-biri ilə əlaqəli kompüter şəbəkələrinin ümumdünya sistemidir.

İnternet qrafik kimi təqdim oluna bilər, burada qrafikin təpələri İnternet saytları, kənarları isə bir saytdan digərinə gedən keçidlərdir (hiperlinklər).

Milyarlarla təpələri və kənarları olan veb qrafiki (İnternet) daim dəyişir - saytlar kortəbii olaraq əlavə olunur və yox olur, keçidlər yox olur və əlavə olunur. Bununla belə, İnternet riyazi quruluşa malikdir, qrafik nəzəriyyəsinə tabedir və bir neçə "sabit" xüsusiyyətlərə malikdir.

Veb qrafiki seyrəkdir. O, təpələrdən bir neçə dəfə çox kənarları ehtiva edir.

Seyrək olmasına baxmayaraq, internet çox sıxdır. 5 - 6 kliklə bağlantılardan istifadə edərək bir saytdan digərinə keçə bilərsiniz (məşhur "altı əl sıxma" nəzəriyyəsi).

Bildiyimiz kimi, qrafikin dərəcəsi təpənin aid olduğu kənarların sayıdır. Veb qrafikinin təpələrinin dərəcələri müəyyən bir qanuna uyğun olaraq paylanır: çox sayda keçid (kənar) olan saytların (təpələrin) nisbəti kiçikdir və az sayda keçid olan saytların payı böyükdür. Riyazi olaraq belə yazmaq olar:

burada müəyyən dərəcədə təpələrin nisbəti, təpənin dərəcəsi, veb-qrafikdəki təpələrin sayından asılı olmayan sabitdir, yəni. saytların (təpələrin) əlavə edilməsi və ya çıxarılması prosesi zamanı dəyişmir.

Bu güc qanunu mürəkkəb şəbəkələr üçün universaldır - biolojidən banklararası.

İnternet bütövlükdə saytlara təsadüfi hücumlara davamlıdır.

Saytların məhv edilməsi və yaradılması müstəqil və eyni ehtimalla baş verdiyindən, ehtimalı 1-ə yaxın olan veb-qrafik öz bütövlüyünü saxlayır və məhv edilmir.

İnterneti öyrənmək üçün təsadüfi qrafik modeli qurmaq lazımdır. Bu model real İnternetin xüsusiyyətlərinə malik olmalı və çox mürəkkəb olmamalıdır.

Bu problem hələ tam həll olunmayıb! Bu problemin həlli - İnternetin yüksək keyfiyyətli modelinin qurulması bizə informasiya axtarışını təkmilləşdirmək, spamları müəyyən etmək və məlumatı yaymaq üçün yeni alətlər hazırlamağa imkan verəcək.

Bioloji və iqtisadi modellərin qurulması İnternetin riyazi modelini qurmaq tapşırığından xeyli əvvəl başladı. Bununla belə, İnternetin inkişafı və öyrənilməsi sahəsində irəliləyişlər bütün bu modellərlə bağlı bir çox suallara cavab verməyə imkan yaratmışdır.

İnternet riyaziyyatı bir çox mütəxəssis tərəfindən tələb olunur: bioloqlar (bakteriya populyasiyasının artımını proqnozlaşdıran), maliyyəçilər (böhran riskləri) və s. Belə sistemlərin öyrənilməsi tətbiqi riyaziyyatın və informatikanın mərkəzi sahələrindən biridir.

Qrafikdən istifadə edərək Murmansk.

İnsan yeni bir şəhərə gəldikdə, bir qayda olaraq, ilk arzu əsas görməli yerləri ziyarət etməkdir. Ancaq eyni zamanda, vaxtın miqdarı çox vaxt məhduddur və işgüzar səfərdə çox azdır. Buna görə də görməli yerləri əvvəlcədən planlaşdırmaq lazımdır. Və qrafiklər marşrutunuzun qurulmasında böyük kömək olacaq!

Nümunə olaraq, ilk dəfə hava limanından Murmansk şəhərinə gəlmək üçün tipik bir hadisəni nəzərdən keçirək. Aşağıdakı görməli yerləri ziyarət etməyi planlaşdırırıq:

1. Su üzərində Xilaskarın Dəniz Pravoslav Kilsəsi;

2. Müqəddəs Nikolay Katedrali;

3. Okeanarium;

4. Pişik Semyonun abidəsi;

5. "Lenin" nüvə buzqıran gəmisi;

6. Murmanskın Park İşıqları;

7. Park Vadisi Rahatlıq;

8. Kola körpüsü;

9. Murmansk Gəmiçiliyinin Tarix Muzeyi;

10. Beş Künc Meydanı;

11. Dəniz ticarət limanı

Əvvəlcə xəritədə bu yerlərin yerini müəyyən edək və görməli yerlərin yeri və məsafəsinin vizual təsvirini əldə edək. Yol şəbəkəsi kifayət qədər inkişaf edib və avtomobillə getmək çətin olmayacaq.

Xəritədə attraksionlar (solda) və nəticədə olan qrafik (sağda) ƏLAVƏ №1-də müvafiq şəkildə göstərilmişdir. Beləliklə, yeni gələn əvvəlcə Kola körpüsünün yanından keçəcək (və istəsən, onu irəli-geri keçə bilər); sonra Murmansk parkının İşıqlarında və Rahatlıq Vadisində dincələcək və yoluna davam edəcək. Nəticədə, optimal marşrut olacaq:

Qrafikdən istifadə edərək, rəy sorğularının keçirilməsi sxemini də vizual olaraq görə bilərsiniz. Nümunələr 2 nömrəli əlavədə verilmişdir. Verilən cavablardan asılı olaraq respondentə müxtəlif suallar verilir. Məsələn, 1 saylı sosioloji sorğuda respondent riyaziyyatı elmlərin ən vacibi hesab edirsə, ondan fizika dərslərində özünü inamlı hiss edib-etmədiyi soruşulacaq; əksini düşünürsə, ikinci sual tələblə bağlı olacaq humanitar elmlər. Belə bir qrafikin təpələri suallar, kənarları isə cavab variantlarıdır.

2.3. Problemin həllində qrafik nəzəriyyəsinin tətbiqi

Qrafik nəzəriyyəsi bir çox fənn sahələrinə aid problemləri həll etmək üçün istifadə olunur: riyaziyyat, biologiya, informatika. Qrafik nəzəriyyəsindən istifadə edərək problemlərin həlli prinsipini öyrəndik və tədqiqat mövzusunda öz problemlərimizi yaratdıq.

Tapşırıq №1.

Beş sinif yoldaşı orta məktəb görüşündə əl sıxdı. Neçə əl sıxıldı?

Həlli: Sinif yoldaşlarını qrafikin təpələri ilə işarə edək. Gəlin hər təpəni digər dörd təpəyə xətlərlə birləşdirək. 10 sətir alırıq, bunlar əl sıxmadır.

Cavab: 10 əl sıxma (hər sətir bir əl sıxma deməkdir).

Tapşırıq № 2.

Nənəmin kəndində, evinin yaxınlığında 8 ağac bitir: qovaq, palıd, ağcaqayın, alma ağacı, larch, ağcaqayın, çəmən və şam. Rowan karaçamdan hündür, alma ağacı ağcaqayından hündürdür, palıd ağcaqayından aşağıdır, lakin şamdan hündürdür, şam rowandan yüksəkdir, ağcaqayın qovaqdan alçaqdır, larch alma ağacından yüksəkdir. Ağaclar hündürlükdə ən hündürdən ən qısaya doğru hansı ardıcıllıqla düzüləcək?

Həlli:

Ağaclar qrafikin təpələridir. Onları dairənin ilk hərfi ilə qeyd edək. Gəlin alçaq ağacdan daha hündür ağaca oxlar çəkək. Deyirlər ki, çəyirtkədən hündürdür, sonra oxunu qaraçana qoyuruq, ağcaqayın qovaqdan alçaqdır, sonra qovaqdan oxu qoyuruq və s. Ən qısa ağacın ağcaqayın, sonra alma, larch, rowan, şam, palıd, ağcaqayın və qovaq olduğunu görə biləcəyimiz bir qrafik alırıq.

Cavab: ağcaqayın, alma, larch, rowan, şam, palıd, ağcaqayın və qovaq.

Tapşırıq №3.

Ananın 2 zərfi var: adi və hava, və 3 marka: kvadrat, düzbucaqlı və üçbucaq. Ana ataya məktub göndərmək üçün neçə yolla zərf və möhür seçə bilər?

Cavab: 6 yol

Tapşırıq № 4.

Arasında yaşayış məntəqələri A, B, C, D, E yolları çəkilir. Uzunluğunu müəyyən etmək lazımdır ən qısa yol A və E nöqtələri arasında. Siz yalnız uzunluğu şəkildə göstərilən yollarla səyahət edə bilərsiniz.

Tapşırıq № 5.

Üç sinif yoldaşı - Maksim, Kirill və Vova idmanla məşğul olmaq qərarına gəldilər və idman bölmələrinin seçimindən keçdilər. Məlum olub ki, basketbol bölməsinə 1 oğlan müraciət edib, üç nəfər isə xokkey oynamaq istəyib. Maksim yalnız 1-ci bölməyə, Kirill hər üç bölməyə, Vova isə 2-ci bölməyə seçildi. Oğlanlardan hansı idman bölməsi üçün seçildi?

Həlli: Problemi həll etmək üçün qrafiklərdən istifadə edəcəyik

Basketbol Maksim

Futbol Kirill

Xokkey Vova

ildən basketbol yalnız bir ox gedir, sonra Kirill bölməyə seçildi basketbol. Onda Kirill oynamayacaq xokkey içində deməkdir xokkey bölmə yalnız bu bölmə üçün dinləmələrdən keçmiş Maksim tərəfindən seçildi, sonra Vova olacaq futbolçu.

Tapşırıq № 6.

Bəzi müəllimlərin xəstəliyi ilə əlaqədar olaraq, məktəbin baş müəllimi aşağıdakı halları nəzərə alaraq ən azı bir günlük dərs cədvəlinin fraqmentini tərtib etməlidir:

1. Həyat təhlükəsizliyi müəllimi yalnız sonuncu dərsi verməyə razıdır;

2. Coğrafiya müəllimi istər ikinci, istərsə də üçüncü dərs verə bilər;

3. Riyaziyyatçı ya yalnız birinci, ya da ikinci dərsi verməyə hazırdır;

4. Fizika müəllimi birinci, ikinci və ya üçüncü dərsləri verə bilər, ancaq bir sinifdə.

Məktəbin baş müəllimi hansı qrafiki yarada bilər ki, bütün müəllimləri qane etsin?

Həll yolu: Bu problemi hər şeydən keçməklə həll etmək olar mümkün variantlar, lakin qrafiki çəksəniz daha asan olar.

1. 1) fizika 2. 1) riyaziyyat 3. 1) riyaziyyat

2) riyaziyyat 2) fizika 2) coğrafiya

3) coğrafiya 3) coğrafiya 3) fizika

4) OBZH 4) OBZH 4) OBZH

Nəticə

Bu tədqiqat işində qrafik nəzəriyyəsi ətraflı tədqiq edilmiş, qrafiklərin öyrənilməsinin məntiqi məsələlərin həllinə kömək edə biləcəyi fərziyyəsi sübuta yetirilib, bundan əlavə, müxtəlif elm sahələrində qrafik nəzəriyyəsi nəzərdən keçirilib və 7 məsələ tərtib edilib.

Tələbələrə problemlərin həlli yollarını öyrətərkən qrafiklərdən istifadə şagirdlərə qrafik bacarıqlarını təkmilləşdirməyə və bəziləri xətlərlə bağlanmış sonlu nöqtələr toplusunun xüsusi dilində mülahizələrini çatdırmağa imkan verir. Bütün bunlar şagirdlərə düşünməyi öyrətmək işinə kömək edir.

Səmərəlilik təhsil fəaliyyəti təfəkkürün inkişafında riyazi məsələlərin həlli zamanı şagirdlərin yaradıcılıq fəallığının dərəcəsindən çox asılıdır. Buna görə də məktəblilərin zehni fəaliyyətini aktivləşdirəcək riyazi tapşırıq və məşqlərə ehtiyac var.

Məktəbdə seçmə dərslərdə tapşırıqların tətbiqi və qrafik nəzəriyyəsi elementlərindən istifadə şagirdlərin əqli fəaliyyətinin aktivləşdirilməsi məqsədini dəqiq qarşıya qoyur. Hesab edirik ki, tədqiqatımıza dair praktiki material seçmə riyaziyyat dərslərində faydalı ola bilər.

Beləliklə, tədqiqat işinin məqsədinə nail olunmuş, problemlər öz həllini tapmışdır. Gələcəkdə biz qrafik nəzəriyyəsini öyrənməyə davam etməyi və öz marşrutlarımızı inkişaf etdirməyi planlaşdırırıq, məsələn, ZATO Aleksandrovskda məktəb avtobusu üçün muzeylərə və muzeylərə ekskursiya marşrutu yaratmaq üçün qrafikdən istifadə edərək. yaddaqalan yerlər Murmansk.

İSTİFADƏ EDİLDİ ƏDƏBİYYAT SİYAHISI

Berezina L. Yu. "Qrafiklər və onların tətbiqi" - M.: "Maarifləndirmə", 1979

Qardner M. “Riyazi asudə vaxt”, M. “Mir”, 1972

Gardner M." Riyaziyyat bulmacaları və əyləncə”, M. “Mir”, 1971

Qorbaçov A. “Olimpiada problemləri toplusu” - M. MTsNMO, 2005

Zıkov A. A. Qrafik nəzəriyyəsinin əsasları. - M.: “Universitet kitabı”, 2004. - S. 664

Kasatkin V. N. “Riyaziyyatın qeyri-adi problemləri”, Kiyev, “Radianska məktəbi”, 1987

Riyazi komponent / Redaktorlar və tərtibçilər N.N. Andreev, S.P. Konovalov, N.M. Panyuşkin. - M.: "Riyazi etüdlər" fondu 2015 - 151 s.

Melnikov O. I. "Qrafik nəzəriyyəsində əyləncəli problemlər", Mn. "TetraSystems", 2001

Melnikov O.I. Saylar ölkəsində bilmirəm: Tələbələr üçün dərslik. Ed. 3-cü, stereotipik. M.: KomKniga, 2007. - 160 s.

Olehnik S. N., Nesterenko Yu V., Potapov M. K. "Köhnə əyləncəli problemlər", M. "Elm", 1988.

Cövhər O. “Qrafiklər və onların tətbiqi”, M. “Mir”, 1965

Harari F. Qrafik nəzəriyyəsi / İngilis dilindən tərcümə. və ön söz V. P. Kozyreva. Ed. G. P. Gavrilova. Ed. 2-ci. - M.: Redaksiya URSS, 2003. - 296 s.

ƏLAVƏ № 1

Əsas görməli yerləri ziyarət etmək üçün optimal marşrutun tərtib edilməsi

Qrafikdən istifadə edərək Murmansk.

Optimal marşrut belə olacaq:

8. Kola körpüsü6. Murmanskın Park İşıqları7. Park Vadisi Rahatlıq 2. Müqəddəs Nikolay Katedrali10. Beş künc meydanı5. Nüvə buzqıran gəmisi Lenin9. Murmansk Gəmiçiliyi Tarixi Muzeyi11. Dəniz ticarət limanı 1. Suda Xilaskarın Dəniz Pravoslav Kilsəsi4. Pişik Semyonun abidəsi3. Okeanarium.

MURMANSK ATTRAKSİYALARI ÜÇÜN BƏLÇƏK

ƏLAVƏ № 2

1, 2 nömrəli sosioloji sorğular

Qrafik metodu nədir?

“Qrafik” sözü riyaziyyatda bir neçə nöqtə çəkilmiş, bəziləri xətlərlə birləşdirilən şəkil deməkdir. Əvvəla, onu deməyə dəyər ki, müzakirə olunacaq sayların keçmiş dövrlərin aristokratları ilə heç bir əlaqəsi yoxdur. "Qrafiklərimiz" yunanca "yazıram" mənasını verən "grapho" sözündəndir. Eyni kök “qrafik”, “bioqrafiya” sözlərindədir.

Riyaziyyatda qrafik tərifi aşağıdakı kimi verilir: qrafik bəziləri xətlərlə birləşdirilən sonlu nöqtələr toplusudur. Nöqtələrə qrafikin təpələri, birləşdirən xətlərə isə kənarlar deyilir.

"Təcrid olunmuş" təpələrdən ibarət qrafik diaqramı deyilir sıfır qrafik. (Şəkil 2)

Bütün mümkün kənarların qurulmadığı qrafiklər deyilir natamam qrafiklər. (Şəkil 3)

Bütün mümkün kənarların qurulduğu qrafiklər deyilir tam qrafiklər. (Şəkil 4)

Hər təpənin hər bir digər təpənin kənarına bağlandığı qrafikə deyilir tam.

Qeyd edək ki, tam qrafikin n təpəsi varsa, onda kənarların sayı bərabər olacaqdır

n(n-1)/2

Həqiqətən, n təpəsi olan tam qrafikdə kənarların sayı qrafikin bütün n kənar nöqtəsindən ibarət düzülməmiş cütlərin sayı, yəni 2-nin n elementinin birləşmələrinin sayı kimi müəyyən edilir:

Tamamlanmayan bir qrafik, çatışmayan kənarları əlavə etməklə eyni təpələrlə tamamlana bilər. Məsələn, Şəkil 3-də beş təpəsi olan natamam qrafik göstərilir. Şəkil 4-də qrafiki tam qrafikə çevirən kənarlar fərqli rəngdə təsvir edilmişdir.

Təpələrin dərəcələri və kənarların sayının hesablanması.

Qrafikin təpəsindən çıxan kənarların sayı deyilir təpə dərəcəsi. Qrafikin tək dərəcəyə malik təpəsi deyilir qəribə və hətta dərəcə - hətta.

Qrafikin bütün təpələrinin dərəcələri bərabərdirsə, o zaman qrafik adlanır homojen. Beləliklə, istənilən tam qrafik homojendir.

Şəkil 5

Şəkil 5-də beş təpəsi olan bir qrafik göstərilir. A təpəsinin dərəcəsi St.A ilə işarələnəcəkdir.

Şəkildə: St.A = 1, St.B = 2, St.B = 3, St.G = 2, St.D = 0.

Gəlin müəyyən qrafiklərə xas olan bəzi qanunauyğunluqları formalaşdıraq.

Nümunə 1.

Tam qrafikin təpələrinin dərəcələri eynidir və onların hər biri bu qrafikin təpələrinin sayından 1 azdır.

Sübut:

Bu nümunə hər hansı tam qrafiki nəzərdən keçirdikdən sonra aydın görünür. Hər bir təpə özündən başqa hər təpə ilə bir kənar ilə birləşdirilir, yəni n təpəsi olan qrafikin hər bir təpəsindən n-1 kənarları çıxır ki, bu da sübut edilməli olan şeydir.

Nümunə 2.

Qrafikin təpələrinin dərəcələrinin cəmi, qrafikin kənarlarının sayının iki qatına bərabər olan cüt ədəddir.

Bu nümunə yalnız tam qrafik üçün deyil, həm də istənilən qrafik üçün doğrudur. Sübut:

Həqiqətən, qrafikin hər bir kənarı iki təpəni birləşdirir. Bu o deməkdir ki, qrafikin bütün təpələrinin dərəcələrinin sayını əlavə etsək, kənarların sayını iki dəfə 2R alacağıq (R - qrafikin kənarlarının sayıdır), çünki hər bir kənar iki dəfə hesablanmışdır, bu, lazım olan şeydir. sübut olunsun

İstənilən qrafikdə tək təpələrin sayı cütdür. Sübut:

İxtiyari G qrafikini nəzərdən keçirək. Bu qrafikdə dərəcəsi 1 olan təpələrin sayı K1-ə bərabər olsun; dərəcəsi 2 olan təpələrin sayı K2-yə bərabərdir; ...; dərəcəsi n olan təpələrin sayı Kn-ə bərabərdir. Onda bu qrafikin təpələrinin dərəcələrinin cəmini belə yazmaq olar
K1 + 2K2 + ZK3 + ...+ nKn.
Digər tərəfdən: qrafikin kənarlarının sayı R-dirsə, 2-ci qanundan məlum olur ki, qrafikin bütün təpələrinin dərəcələrinin cəmi 2R-ə bərabərdir. Sonra bərabərliyi yaza bilərik
K1 + 2K2 + ZK3 + ... + nKn = 2R. (1)
Gəlin bərabərliyin sol tərəfində qrafikin tək təpələrinin sayına bərabər bir məbləğ seçək (K1 + K3 + ...):
K1 + 2K2 + ZK3 + 4K4 + 5K5 + ... + nK = 2R,
(K1 + K3 + K5 +...) + (2K2 + 2X3 +4K4 + 4K5 + ...)=2R
İkinci mötərizə cüt ədədlərin cəmi kimi cüt ədəddir. Nəticədə cəmi (2R) cüt ədəddir. Deməli (K1 + K3 + K5 +...) cüt ədəddir.

İndi qrafiklərdən istifadə edərək həll olunan problemləri nəzərdən keçirək:

Tapşırıq. Sinif birinciliyi . Stolüstü tennis sinfi çempionatında 6 iştirakçı var: Andrey, Boris, Viktor, Qalina, Dmitri və Yelena. Çempionat dairəvi sistem üzrə keçirilir - hər bir iştirakçı digərləri ilə bir dəfə oynayır. Bu günə kimi bəzi oyunlar artıq oynanılıb: Andrey Boris, Qalina və Elena ilə oynayıb; Boris, artıq qeyd edildiyi kimi, Andrey və Qalina ilə birlikdədir; Viktor - Qalina, Dmitri və Yelena ilə; Qalina Andrey və Boris ilə; Dmitri - Viktor və Yelena ilə - Andrey və Viktor ilə. İndiyədək neçə oyun keçirilib və neçəsi qalıb?

Müzakirə. Gəlin bu tapşırıqları diaqram şəklində təsvir edək. İştirakçıları nöqtələr kimi təsvir edəcəyik: Andrey - A nöqtəsi, Boris - B nöqtəsi və s. Əgər iki iştirakçı artıq bir-biri ilə oynayıbsa, onda biz onları təmsil edən nöqtələri seqmentlərlə birləşdirəcəyik. Nəticə Şəkil 1-də göstərilən diaqramdır.

A, B, C, D, D, E nöqtələri qrafikin təpələri, onları birləşdirən seqmentlər isə qrafikin kənarlarıdır.

Qeyd edək ki, qrafikin kənarlarının kəsişmə nöqtələri onun təpələri deyil.

İndiyə qədər oynanan oyunların sayı kənarların sayına bərabərdir, yəni. 7.

Çaşqınlığın qarşısını almaq üçün qrafikin təpələri çox vaxt nöqtələr kimi deyil, kiçik dairələr şəklində təsvir olunur.

Oynanmalı olan oyunların sayını tapmaq üçün eyni təpələri olan başqa bir qrafik quracağıq, lakin kənarları ilə hələ bir-biri ilə oynamamış iştirakçıları birləşdirəcəyik (Şəkil 2). 8 kənar, yəni 8 oyun qalıb: Andrey - Viktor və Dmitri ilə; Boris - Viktor, Dmitri və Yelena ilə və s.

Aşağıdakı məsələdə təsvir olunan vəziyyət üçün qrafik qurmağa çalışaq:

Tapşırıq . Lyapkin - Tyapkin rolunu kim oynayır? Məktəbin dram klubu Qoqolun “Baş müfəttiş” əsərini səhnələşdirmək qərarına gəlib. Və sonra qızğın mübahisə başladı. Hər şey Lyapkin - Tyapkin ilə başladı.

Lyapkin - Mən Tyapkin olacağam! – Gena qətiyyətlə bildirdi.

Xeyr, mən Lyapkin olacağam - Tyapkin, Dima etiraz etdi - Mən uşaqlıqdan bu obrazı səhnədə canlandırmaq arzusunda idim.

Yaxşı, yaxşı, əgər mənə Xlestakovu oynamağa icazə versələr, bu roldan imtina edəcəm”, - Gena səxavət göstərdi.

“...Və mənim üçün - Osipa,” Dima səxavətlə ona boyun əymədi.

"Mən Çiyələk və ya Bələdiyyə Başçısı olmaq istəyirəm" dedi Vova.

Yox, mən mer olacağam”, – deyə Aliklə Borya bir ağızdan qışqırdılar. - Və ya Xlestakov, -

Rolları elə paylamaq mümkün olacaqmı ki, ifaçılar razı qalsın?

Müzakirə. Gəlin yuxarı cərgədə dairələrlə gənc aktyorları təsvir edək: A - Alik, B - Boris, C - Vova, G - Gena, D - Dima və oynayacaqları rollar - ikinci sırada dairələrlə (1 - Lyapkin - Tyapkin, 2 - Xlestakov, 3 - Osip, 4 - Çiyələk, 5 - Mer). Sonra hər bir iştirakçıdan seqmentlər çəkəcəyik, yəni. qabırğa, oynamaq istədiyi rollara. On təpəsi və on kənarı olan bir qrafik alacağıq (şək. 3)

Problemi həll etmək üçün ümumi təpələri olmayan on kənardan beş kənarı seçməlisiniz. Bunu etmək asandır. Qeyd etmək kifayətdir ki, bir kənar müvafiq olaraq D və B təpələrindən 3 və 4-cü təpələrə aparır. Bu o deməkdir ki, Osipi (ilk 3-lük) Dima (daha kim?), Zemlyaniçkanı isə Vova oynamalıdır. Vertex 1 - Lyapkin - Tyapkin - G və D-yə kənarları ilə bağlanır. Edge 1 - D imtina edir, çünki Dima artıq məşğuldur, 1 - G qalır, Lyapkina - Tyapkina Gena tərəfindən oynanmalıdır. A və B təpələrini Xlestakov və Gorodnichy rollarına uyğun gələn 2 və 5 təpələri ilə birləşdirmək qalır. Bu iki yolla edilə bilər: ya kənar A -5 və B - 2, ya da A -2 və B -5 kənarını seçin. Birinci halda Alik meri, Borya isə Xlestakovu, ikinci halda isə əksinə, oynayacaq. Qrafikdən göründüyü kimi problemin başqa həlli yoxdur.

Aşağıdakı məsələni həll edərkən eyni qrafik alınacaq:

Tapşırıq. Qəzəbli qonşular. Beş evin sakinləri bir-biri ilə mübahisə etdilər və quyularda görüşməmək üçün onları (quyuları) bölmək qərarına gəldilər ki, hər evin sahibi "öz" yolu ilə "öz" quyusuna getsin. Onlar bunu bacaracaqlarmı?

Sual yaranır:müzakirə olunan problemlərdə qrafiklərə həqiqətən ehtiyac var idimi? Məgər sırf məntiqi vasitələrlə həllə gəlmək olmazmı? Bəli, edə bilərsiniz. Amma qrafiklər şərtləri daha aydınlaşdırdı, həlli sadələşdirdi və iki məsələni birinə çevirərək problemlərin oxşarlığını ortaya qoydu və bu o qədər də az deyil. İndi qrafikləri 100 və ya daha çox təpəyə malik olan problemləri təsəvvür edin. Ancaq müasir mühəndislər və iqtisadçılar məhz belə problemləri həll etməlidirlər. Burada qrafiklər olmadan edə bilməzsiniz.

III. Eyler qrafikləri.

Qrafik nəzəriyyəsi nisbətən gənc bir elmdir: Nyutonun dövründə belə bir elm hələ mövcud deyildi, baxmayaraq ki, qrafiklərin növləri olan “ailə ağacları” istifadə olunurdu. Qrafik nəzəriyyəsi üzrə ilk əsər Leonhard Eulerə məxsusdur və o, 1736-cı ildə Sankt-Peterburq Elmlər Akademiyasının nəşrlərində dərc edilmişdir. Bu iş aşağıdakı problemi nəzərə alaraq başladı:

A) Köniqsberq körpüləri ilə bağlı problem. Koenigsberg (indiki Kalininqrad) şəhəri Pregel çayının (Pregoli) sahillərində və iki adada yerləşir, şəkildə göstərildiyi kimi şəhərin müxtəlif hissələri yeddi körpü ilə birləşirdi. Bazar günləri vətəndaşlar şəhərdə gəzintiyə çıxırlar. Elə bir marşrut seçmək olarmı ki, hər körpüdən bir dəfə keçib, sonra başlanğıc nöqtəsinə qayıtsan?
Bu problemin həllini nəzərdən keçirməzdən əvvəl biz “konseptini təqdim edirik. Eyler qrafikləri.

Şəkil 4-də göstərilən qrafiki dairəyə çəkməyə çalışaq bir vuruşla, yəni qələmi vərəqdən qaldırmadan və xəttin eyni hissəsindən bir dəfədən çox keçmədən.

Görünüşünə görə bu qədər sadə olan bu rəqəmin maraqlı bir xüsusiyyəti olduğu ortaya çıxır. Əgər B təpəsindən irəliləməyə başlasaq, o zaman mütləq uğur qazanacağıq. A təpəsində hərəkət etməyə başlasaq nə olacaq? Bu vəziyyətdə xətti izləyə bilməyəcəyimizi görmək asandır: biz həmişə keçilməmiş kənarlarımız olacaq, artıq çatmaq mümkün deyil.

Şəkildə. Şəkil 5, yəqin ki, bir vuruşla necə çəkəcəyinizi bildiyiniz bir qrafiki göstərir. Bu bir ulduzdur. Belə çıxır ki, əvvəlki qrafikdən xeyli mürəkkəb görünsə də, onu istənilən təpədən başlayaraq izləmək olar.

Şəkil 6-da çəkilmiş qrafikləri qələmin bir vuruşu ilə də çəkmək olar.

İndi çəkməyə çalışın bir vuruşlaŞəkil 7-də göstərilən qrafik

Bunu bacarmadınız! Niyə? Axtardığınız təpəni tapa bilmirsiniz? Xeyr! Məsələ bunda deyil. Bu qrafiki qələmin bir vuruşu ilə ümumiyyətlə çəkmək olmaz.

Gəlin bizi buna inandıracaq mülahizə aparaq. A düyününə nəzər salın. Ondan üç təpə çıxır. Bu təpədən qrafiki çəkməyə başlayaq. Bu kənarların hər biri ilə getmək üçün onlardan biri boyunca A təpəsindən çıxmalıyıq, bir anda ikincisi boyunca ona qayıtmalı və üçüncü boyunca çıxmalıyıq. Ancaq bir daha daxil ola bilməyəcəyik! Bu o deməkdir ki, A təpəsindən çəkməyə başlasaq, orada bitirə bilməyəcəyik.

İndi fərz edək ki, A təpəsi başlanğıc deyil. Sonra, rəsm prosesində onu kənarlardan biri boyunca daxil etməli, digəri boyunca çıxmalı və üçüncüsü boyunca yenidən qayıtmalıyıq. Və ondan çıxa bilmədiyimiz üçün bu halda A zirvəsi son olmalıdır.

Beləliklə, A təpəsi rəsmin başlanğıcı və ya sonu qovşağı olmalıdır.

Ancaq eyni şeyi qrafikimizin digər üç təpəsi haqqında da demək olar. Ancaq rəsmin başlanğıc zirvəsi yalnız bir təpə ola bilər və son təpə də yalnız bir təpə ola bilər! Bu o deməkdir ki, bu qrafiki bir vuruşla çəkmək mümkün deyil.

Kağızdan qələmi qaldırmadan çəkilə bilən qrafik adlanır eulerian (Şəkil 6).

Bu qrafiklər alim Leonhard Eulerin adını daşıyır.

Nümunə 1. (nəzərdən keçirdiyimiz teoremdən irəli gəlir).

Tək sayda tək təpələri olan qrafik çəkmək mümkün deyil.
Nümunə 2.

Əgər qrafikin bütün təpələri bərabərdirsə, onda siz bu qrafiki qələminizi kağızdan qaldırmadan (“bir vuruşla”) çəkə bilərsiniz, hər kənarı yalnız bir dəfə hərəkət etdirə bilərsiniz. Hərəkət istənilən təpədən başlaya və eyni təpədə bitə bilər.
Nümunə 3.

Qələmi kağızdan qaldırmadan yalnız iki tək təpəsi olan qrafiki çəkmək olar və hərəkət bu tək təpələrdən birində başlayıb, ikincisində bitməlidir.
Nümunə 4.

İkidən çox tək təpəsi olan qrafiki “bir vuruş” ilə çəkmək olmaz.
Kağızdan qələmi qaldırmadan çəkmək mümkün olan fiqur (qrafik) unikursal adlanır.

Qrafik adlanır ardıcıl, onun hər hansı iki təpəsini bir cığırla, yəni hər biri əvvəlkinin sonundan başlayan kənarlar ardıcıllığı ilə birləşdirə bilsə.

Qrafik adlanır uyğunsuz, bu şərt yerinə yetirilmədikdə.

Şəkil 7 Şəkil 8

Şəkil 7 açıq şəkildə əlaqəsiz bir qrafiki göstərir. Məsələn, şəkildəki D və E təpələri arasında bir kənar çəksəniz, qrafik birləşdiriləcəkdir. (Şəkil 8)

Qrafik nəzəriyyəsində belə bir kənar (çıxarıldıqdan sonra bağlı olandan qrafik ayrılmış birinə çevrilir) adlanır. körpü.

Şəkil 7-dəki körpülərə misal olaraq hər biri qrafikin “təcrid olunmuş” hissələrinin təpələrini birləşdirəcək DE, A3, VZH və s. kənarları ola bilər (şək. 8).

Əlaqəsi kəsilmiş qrafik bir neçə "parçadan" ibarətdir. Bu "parçalar" adlanır əlaqə komponentləri qrafik. Hər bir əlaqəli komponent, əlbəttə ki, əlaqəli bir qrafikdir. Nəzərə alın ki, əlaqəli qrafikdə bir əlaqəli komponent var.
TEOREM.

Qrafik yalnız və yalnız bir-birinə bağlı olduqda və ən çoxu iki tək təpə nöqtəsinə malik olduqda Eyler qrafikidir.

Sübut:

Başlanğıc və son nöqtələr istisna olmaqla, hər bir təpə üçün qrafik çəkərək, ondan çıxdığımız zaman eyni sayda daxil edəcəyik. Buna görə də, ikidən başqa bütün təpələrin dərəcələri cüt olmalıdır, yəni Eyler qrafikinin ən çox iki tək təpəsi var.

İndi Köniqsberq körpüləri probleminə qayıdaq.

Problemin müzakirəsi . Şəhərin müxtəlif hissələrini A, B, C, D hərfləri ilə, körpüləri isə a, b, c, d, e, f, g hərfləri ilə qeyd edək - şəhərin müvafiq hissələrini birləşdirən körpülər. Bu problemdə yalnız körpülər üzərində keçidlər var: hər hansı bir körpüdən keçməklə, biz həmişə şəhərin bir hissəsindən digərinə keçirik və əksinə, şəhərin bir hissəsindən digərinə keçərək, əlbəttə ki, bir körpüdən keçəcəyik. Odur ki, şəhər planını qrafik şəklində təsvir edək, onun təpələri A, B, C, D (şək. 8) şəhərin ayrı-ayrı hissələrini, kənarları isə a, b, c, d, e-ni təsvir edir. , f, g şəhərin müvafiq hissələrini birləşdirən körpülərdir. Tez-tez kənarları düz seqmentlər kimi deyil, əyri olanlar - "qövslər" kimi təsvir etmək daha rahatdır.

Əgər məsələnin şərtlərini ödəyən bir marşrut olsaydı, bu qrafikin hər kənarından bir dəfə keçən qapalı davamlı keçidi olardı. Başqa sözlə, bu qrafiki bir vuruşla çəkmək lazımdır. Ancaq bu mümkün deyil - ilkin olaraq hansı təpəni seçməyimizdən asılı olmayaraq, qalan təpələrdən və eyni zamanda hər bir "gələn" kənardan (şəhərin bu hissəsinə girdiyimiz körpüdən) keçməli olacağıq. "çıxan" kənara uyğun olacaq, körpüdən istifadə edərək şəhərin bu hissəsini tərk edirik): hər bir təpəyə daxil olan kənarların sayı onu tərk edən kənarların sayına bərabər olacaq, yəni. ümumi sayı hər bir təpədə birləşən kənarlar bərabər olmalıdır. Qrafikimiz bu şərti təmin etmir və buna görə də tələb olunan marşrut mövcud deyil.