Detyrat e teorisë së grafikut në Word. Teoria e grafikut

Institucion arsimor buxhetor komunal

Shkolla e mesme Oktyabrskaya

Punim kërkimor në matematikë

“Teoria e grafikut në zgjidhjen e ndryshme

llojet e detyrave"

E përfunduar:
Nxënëse e klasës së 7-të
Makshun Alexey

Mbikëqyrësi:

mësues i matematikës

Moshkovo 2011

1. Prezantimi.

1. 1. Rëndësia e temës së zgjedhur.

Një ditë hasa në një problem të përshkruar nga Lewis Carroll. “Tre njerëz jetonin në tre shtëpi, jo larg tyre kishte tre puse: njëri me ujë, tjetri me vaj dhe i treti me reçel, dhe ata ecën drejt tyre nëpër shtigjet e treguara në foto. Një ditë këta njerëz u grindën dhe vendosën të nxjerrin shtigje nga shtëpitë e tyre deri te puset, që këto shtigje të mos kryqëzoheshin”.

Unë u përpoqa ta zgjidh këtë problem, por asgjë nuk funksionoi. Pas kësaj, iu drejtova mësuesit tim dhe ata më shpjeguan se këtë problem mund ta zgjidhja vetëm duke studiuar teorinë e grafikëve. Por përpara se të gjeja përgjigjen e pyetjes sime, pashë se teoria e grafikut ndihmon për të thjeshtuar zgjidhjen e shumë problemeve. Grafikët më interesuan për shkak të aftësisë së tyre për të ndihmuar në zgjidhjen e enigmave të ndryshme, problemeve matematikore dhe logjike.

Synimi:

Tregoni zbatimin e teorisë së grafikëve për zgjidhjen e llojeve të ndryshme të problemeve.

Detyrat:

· Të studioj elemente të teorisë së grafikëve për zgjidhjen e problemeve që më interesojnë.

· Analizoni zgjidhjet e llojeve të ndryshme të problemeve.

· Përmirësimi i kulturës matematikore.

1.2. Historia e shfaqjes së teorisë së grafikut.

Data e lindjes së teorisë së grafikëve konsiderohet të jetë viti 1736, kur Leonhard Euler zgjidhi problemin e urave të Königsberg. Degët e lumit Pregel, në brigjet e të cilit ndodhet qyteti i Königsberg, formuan dy ishuj. Në këtë epokë, katër pjesët e formuara të tokës (bregu i djathtë dhe i majtë dhe dy ishujt) lidheshin me shtatë ura siç tregohet në figurë. Banorët e qytetit, duke ecur nëpër qytet, u përpoqën të krijonin një rrugë në mënyrë që ajo të kalonte çdo urë saktësisht një herë. Ata nuk arritën ta bënin këtë, por Euler vërtetoi se kjo ishte thelbësisht e pamundur. Termi "graf" u prezantua për herë të parë në vitin 1936 nga matematikani hungarez Dénes König. Teoria e grafikut është zhvilluar gjerësisht që nga vitet 50 të shekullit të 20-të në lidhje me shfaqjen e kibernetikës dhe zhvillimin e teknologjisë kompjuterike.

Fjala "graf" në matematikë do të thotë një figurë me disa pika të vizatuara, disa prej të cilave janë të lidhura me vija. Ato lidhen me titullin fisnik "count" nga një origjinë e zakonshme nga fjala latine "graphio" - shkruaj unë.

Shembujt e grafikëve përfshijnë diagrame të linjave ajrore, metro, rrugë, qarqe elektrike dhe vizatime të poligoneve.

Skema e metrosë së Novosibirsk.

Përdor numërimin dhe fisnikërinë. Për shembull, në një pemë familjare, kulmet janë anëtarë të klanit, dhe segmentet që i lidhin ato janë marrëdhënie farefisnore.

Pema e familjes.

Me ndihmën e grafikëve, zgjidhja e problemeve të formuluara në fusha të ndryshme të njohurive shpesh thjeshtohet: në automatizim, elektronikë, fizikë, kimi. Grafikët ndihmojnë në zgjidhjen e problemeve matematikore dhe ekonomike.

2. Pjesa kryesore.

2.1. Konceptet bazë të teorisë së grafikëve. Zbatimi i tij në zgjidhjen e problemeve logjike.

Në matematikë, përkufizimi i një grafiku jepet si më poshtë:

Grafiku është një grup i kufizuar pikash, disa prej të cilave janë të lidhura me vija. Pikat quhen kulme të grafikut, kurse linjat lidhëse quhen skaje.

Një diagram grafik i përbërë nga kulme "të izoluara" quhet grafiku zero. (Fig. 2)

Grafikët në të cilët nuk janë ndërtuar të gjitha skajet e mundshme quhen grafikë jo të plotë. (Fig. 3)

Grafikët në të cilët janë ndërtuar të gjitha skajet e mundshme quhen grafikët e plotë. (Fig. 4)

Numri i skajeve që lënë një kulm të grafikut quhet shkallë kulmore. Një kulm i një grafi që ka një shkallë tek quhet i çuditshëm, madje edhe diplomë - madje.

Nëse gradat e të gjitha kulmeve të një grafi janë të barabarta, atëherë thirret grafiku homogjene. Kështu, çdo grafik i plotë është homogjen.

Figura 5 tregon një grafik me pesë kulme. Shkalla e kulmit A do të shënohet me Art. A. Në foto: Art. A = 1, St. B = 2, St. B = 3, St. G= 2, St. D= 0.

Detyra nr. 1.

Arkady, Boris. Vladimir, Grigory dhe Dmitry shtrënguan duart kur u takuan (secili shtrëngoi duart me njëri-tjetrin një herë). Sa shtrëngime duarsh janë bërë?

Zgjidhja:

Secili nga pesë të rinjtë le t'i korrespondojë një pike të caktuar në aeroplan, të emërtuar me shkronjën e parë të emrit të tij, dhe lëreni që shtrëngimi i duarve të jetë një segment ose pjesë e një kurbë që lidh pika - emra të veçantë.

Detyra nr. 2.

Katër miq jetojnë në të njëjtin oborr. Vadimi dhe shoferi janë më të vjetër se Sergei, Nikolai dhe mekaniku po boksojnë, elektricisti është më i riu nga miqtë e tij.

Në mbrëmje, Andrei dhe rrotulluesi luajnë domino kundër Sergeit dhe elektricistit.

Përcaktoni profesionin e secilit prej miqve tuaj.

Zgjidhje.

Le të bëjmë një grafik me 4 shokë dhe 4 profesione. Vijat me pika tregojnë lidhje të pamundura dhe vijat e forta tregojnë korrespondencën midis emrit dhe profesionit. Nëse ka 3 vija me pika që vijnë nga çdo kulm, atëherë rreshti i katërt duhet të jetë i fortë.

V S N A

W S T E

Detyra nr. 3.

Pesë miq jetojnë në një qytet të vogël: Ivanov, Petrenko, Sidorchuk, Grishin dhe Kapustin. Profesionet e tyre janë të ndryshme: njëri prej tyre është piktor, tjetri mullixhi, i treti marangoz, i katërti postier dhe i pesti parukier.

Petrenko dhe Grishin nuk mbanin kurrë një furçë bojë në duar.

Ivanov dhe Grishin do të vizitojnë mullirin ku punon miku i tyre. Petrenko dhe Kapustin jetojnë në të njëjtën shtëpi me postierin.

Sidorchuk kohët e fundit ishte një nga dëshmitarët në zyrën e gjendjes civile kur Petrenko dhe vajza e floktarit ishin martuar ligjërisht. Ivanov dhe Petrenko luajnë qytete të vogla me një marangoz dhe një piktor çdo të diel.

Grishin dhe Kapustin takohen gjithmonë të shtunave në parukeri ku punon shoku i tyre. Postieri preferon të rruhet vetë. Kush është kush?

Zgjidhje.

Ivanov Petrenko Sidorchuk Grishin Kapustin

piktor mulliri marangoz postier parukier

2.2. Shtigjet e Euler-it. Ndërtimi i një figure me një goditje.

Le të formulojmë disa rregullsi të natyrshme në grafikë të caktuar.

Modeli 1.

Shkallët e kulmeve të një grafi të plotë janë të njëjta dhe secila prej tyre është 1 më pak se numri i kulmeve të këtij grafiku.

Dëshmi:

Ky model është i dukshëm pas shqyrtimit të çdo grafiku të plotë. Çdo kulm lidhet nga një skaj me çdo kulm, përveç vetes, d.m.th., nga çdo kulm i një grafi që ka n kulme, dalin n-1 skaje, gjë që duhej vërtetuar.

Modeli 2.

Shuma e shkallëve të kulmeve të një grafi është një numër çift i barabartë me dyfishin e numrit të skajeve të grafikut.

Ky model është i vërtetë jo vetëm për një grafik të plotë, por edhe për çdo grafik.

Dëshmi:

Në të vërtetë, çdo skaj i grafikut lidh dy kulme. Kjo do të thotë se nëse shtojmë numrin e shkallëve të të gjitha kulmeve të grafikut, do të marrim dyfishin e numrit të skajeve 2R (R është numri i skajeve të grafikut), pasi çdo skaj është numëruar dy herë, që ishte ajo që duhej të të vërtetohet.

Numri i kulmeve tek në çdo grafik është çift. Dëshmi:

Konsideroni një graf arbitrar G. Le të jetë i barabartë me K1 numri i kulmeve në këtë grafik, shkalla e të cilit është 1; numri i kulmeve shkalla e të cilave është 2 është e barabartë me K2; ...; numri i kulmeve shkalla e të cilave është n është e barabartë me Kn. Atëherë shuma e shkallëve të kulmeve të këtij grafiku mund të shkruhet si
K1 + 2K2 + ZK3 + ...+ nKn.
Nga ana tjetër: nëse numri i skajeve të grafikut është R, atëherë nga ligji 2 dihet se shuma e shkallëve të të gjitha kulmeve të grafikut është e barabartë me 2R. Atëherë mund të shkruajmë barazinë
K1 + 2K2 + ZK3 + ... + nKn = 2R.
Le të zgjedhim në anën e majtë të barazisë një shumë të barabartë me numrin e kulmeve tek të grafikut (K1 + K3 + ...):
K1 + 2K2 + ZK3 + 4K4 + 5K5 + ... + nKn = 2R,
(K1 + K3 + K5 +...) + (2K2 + 2K3 +4K4 + 4K5 + ...)=2R
Kllapa e dytë është një numër çift si shuma e numrave çift. Shuma që rezulton (2R) është një numër çift. Prandaj (K1 + K3 + K5 +...) është një numër çift.

Q.E.D.

Detyra nr 4.

A është e mundur të lidhni 25 pajisje me tela në mënyrë që secila pajisje të lidhet saktësisht me pesë të tjera?

Zgjidhje.

E pamundur. Një grafik i tillë do të kishte një numër tek kulmesh me shkallë tek.

Vini re se nëse një grafik i plotë ka n kulme, atëherë numri i skajeve do të jetë i barabartë me n(n-1)/2. Në të vërtetë, numri i skajeve në një grafik të plotë me n kulmet përkufizohen si numri i çifteve të parenditura të përbërë nga të gjitha n pika-skajet e grafikut, d.m.th., si numri i kombinimeve të n elementet e 2:
Një grafik që nuk është i plotë mund të plotësohet për të qenë i plotë me të njëjtat kulme duke shtuar skajet që mungojnë. Për shembull, Figura 3 tregon një grafik jo të plotë me pesë kulme. Në figurën 4, skajet që transformojnë grafikun në një grafik të plotë janë paraqitur me një ngjyrë të ndryshme; koleksioni i kulmeve të grafikut me këto skaje quhet plotësimi i grafikut.

Detyra nr 5.

Ka 6 pjesëmarrës në kampionatin e klasës së pingpongut: Andrey, Boris Victor, Galina, Dmitry dhe Elena. Kampionati zhvillohet në një sistem të rrumbullakët - secili pjesëmarrës luan me secilin nga të tjerët një herë. Deri më sot, disa lojëra janë luajtur tashmë: Andrey luajti me Boris, Galina, Elena; Boris - me Andrey, Galina; Victor - me Galina, Dmitry, Elena; Galina - me Andrey, Victor dhe Boris. Sa ndeshje janë luajtur deri më tani dhe sa kanë mbetur?

Zgjidhja:

Le të ndërtojmë një grafik. I shënojmë lojërat e luajtura me vija blu dhe shtojmë vija të kuqe për të plotësuar grafikun. Marrim se janë luajtur 7 lojëra dhe kanë mbetur 8. Mund të kontrolloni: në grafik janë 6 kulme, pastaj janë gjithsej 6*5/2=15 skaje (7+8).

Grafikët e Euler-it.

Një shteg i Euler-it është një shteg në një grafik që kalon në çdo skaj saktësisht një herë.

Grafiku që mund të vizatohet pa e hequr lapsin nga letra quhet Eulerian.(Fig. 6) Këta grafikë janë emëruar sipas shkencëtarit Leonhard Euler.

Fig.6 (grafikët Eulerian)

Rregullsia 3 (rrjedh nga teorema që kemi shqyrtuar).
Është e pamundur të vizatosh një grafik me një numër tek kulmeve tek.
Modeli 4.

Nëse të gjitha kulmet e grafikut janë të njëtrajtshme, atëherë mund ta vizatoni këtë grafik pa e hequr lapsin nga letra ("me një goditje"), duke lëvizur përgjatë çdo skaji vetëm një herë. Lëvizja mund të fillojë nga çdo kulm dhe të përfundojë në të njëjtin kulm.
Modeli 5.

Një grafik me vetëm dy kulme teke mund të vizatohet pa hequr lapsin nga letra, dhe lëvizja duhet të fillojë në njërën prej këtyre kulmeve tek dhe të përfundojë në të dytin prej tyre.
Modeli 6.

Një grafik me më shumë se dy kulme teke nuk mund të vizatohet me "një goditje".

Një figurë (grafik) që mund të vizatohet pa e hequr lapsin nga letra quhet unikursal.

Detyrë № 6 në lidhje me urat e Königsberg.

Degët e lumit Pregel, në brigjet e të cilit ndodhet qyteti i Königsberg, formuan dy ishuj. Në këtë epokë, katër pjesët e formuara të tokës (bregu i djathtë dhe i majtë dhe dy ishujt) lidheshin me shtatë ura siç tregohet në figurë. Banorët e qytetit, duke ecur nëpër qytet, u përpoqën të krijonin një rrugë në mënyrë që ajo të kalonte çdo urë saktësisht një herë.

Zgjidhje.

Ky problem u zgjidh nga Leonhard Euler. Ai ndërtoi grafikun e mëposhtëm dhe zbuloi se të katër kulmet janë tek, domethënë është e pamundur të kalosh një herë të gjitha urat dhe të përfundosh shtegun aty ku është nisur.

Detyra nr 7.

Të katër ishujt janë të lidhur me njëri-tjetrin dhe me brigjet e lumit nga 14 ura, siç tregohet në figurë. A është e mundur të rrotullohen të gjitha këto ura me një shëtitje, duke vizituar secilën prej tyre një herë?

Zgjidhje. Le të ndërtojmë një grafik. Janë dy majat teke B dhe C. Prandaj, në një shëtitje mund të ecësh rreth të gjitha urave, duke vizituar secilën prej tyre një herë. Në këtë rast, shëtitja duhet të fillojë nga ishulli B dhe të përfundojë në ishullin C ose anasjelltas.

Detyra nr 8.

A është e mundur të vizatoni grafikët e paraqitur në foto pa hequr lapsin nga letra dhe duke e vizatuar secilën skaj saktësisht një herë?

Zgjidhja:

1) Është e mundur, sepse ka vetëm 2 kulme tek.

2) Është e pamundur, sepse ka 4 kulme tek.

Detyra nr. 9.

Ata thonë se Muhamedi, në vend që të firmoste (ai ishte analfabet), përshkroi me një goditje shenjën e përbërë nga dy brirët e hënës, të paraqitur në vizatim. A është e mundur?

Zgjidhje. Po, sepse në këtë rast kemi të bëjmë me kulme të rendit çift.

Detyra nr 10. Fluturoni në një kavanoz.

Një mizë u fut në një kavanoz sheqeri. Kavanoza ka formën e një kubi. A mundet një mizë të lëvizë në mënyrë sekuenciale rreth të 12 skajeve të një kubi pa kaluar dy herë mbi të njëjtin skaj? Kërcimi dhe fluturimi nga një vend në tjetrin nuk lejohet.

Zgjidhje.

Skajet dhe kulmet formojnë një grafik, të 8 kulmet e të cilit janë të shkallës 3, dhe për këtë arsye kalimi i kërkuar nuk është i mundur.

Detyra nr. 11.

Mundohuni t'i ndërtoni këto figura me një goditje.

2.3. Grafikët planarë.

Problemi i "tre shtëpive dhe tre puseve" që më interesoi, nxiti zhvillimin e teorisë së grafikëve. Një grafik që mund të vizatohet në një rrafsh në mënyrë që skajet e tij të mos kryqëzohen askund përveç kulmeve quhet banesë ose planare.

Euler vërtetoi një teoremë që i jep një përgjigje negative pyetjes së këtij problemi.

Teorema e Euler-it.

Nëse një graf me n kulme dhe m skaj është i rrafshët, atëherë barazia n-m+p=2 është e vërtetë, ku p është numri i pjesëve të shkëputura (ato quhen faqe) në të cilat ky grafik ndan rrafshin.

Dëshmi.

Grafiku “tre shtëpi dhe tre puse” ka gjashtë kulme dhe nëntë skaje. Nëse është e sheshtë, numri i skajeve p duhet të jetë i barabartë me p = n – m + 2 = 9 - 6 + 2 = 5. Por meqenëse nuk ka dy shtëpi ose dy puse të lidhura me njëra-tjetrën, çdo faqe ka të paktën katër skajet . Marrim pabarazinë 2n ≥ 4p (çdo skaj numërohet dy herë), nga i cili fitojmë mosbarazimin e rremë 18 ≥ 20. Po kështu, vërtetohet se një graf i plotë me pesë kulme gjithashtu nuk mund të jetë planar.

Teorema Pontryagin–Kuratowski.

Një grafik është i sheshtë nëse dhe vetëm nëse nuk përmban një grafik shtëpi-pus me gjashtë kulme dhe një grafik të plotë me pesë kulme.

3. konkluzioni.

Për të gjetur përgjigjen e problemit që më interesonte, më duhej të njihesha me një degë të re të matematikës, "Teoria e Grafikut", e cila nuk studiohet në kursin e shkollës, por e bën më të lehtë zgjidhjen e shumë problemeve. Mësova shumë. e gjërave të reja, dhe kuptoi se matematika është interesante, por edhe e vështirë.

Grafikët janë objekte të mrekullueshme matematikore që mund të përdoren për të zgjidhur probleme matematikore, logjike dhe ekonomike. Zgjidhja e shumë problemeve matematikore bëhet më e lehtë nëse mund të përdorni grafikët. Paraqitja e të dhënave në formën e një grafiku e bën atë më të qartë dhe më të thjeshtë. Shumë prova matematikore thjeshtohen dhe bëhen më bindëse nëse përdoren grafikët. Ju gjithashtu mund të zgjidhni enigma të ndryshme dhe të thjeshtoni kushtet e problemeve në fizikë, kimi, elektronikë dhe automatizim. Grafikët përdoren në përpilimin e hartave dhe pemëve familjare.

4. Letërsia.

3. zgjuarsi Ignatiev. - M.: "Omega", 1994.

5. “Matematika” – suplement i gazetës “I Shtatori i Parë” nr.7, 2005.

6. Fjalor Enciklopedik i një Matematikani të Ri / Komp. A.P. Savin.- M.: Pedagogji, 1989.

Ne kemi përdorur gjithashtu të dhëna nga faqet e mëposhtme:

Fjalor Enciklopedik i një Matematikani të Ri / Komp. A.P. Savin.- M.: Pedagogji, 1989.

Këpucët në xhepin e Kangurit. - M.: Bustard, 2010.

Http:infometronovosibirsk_metro_map. htm

http://www. /indeks. php? cnt=4

Revista e fizikës dhe matematikës "Kvant", nr. 6, 1994.

Përgatitja e nxënësve për olimpiadat e matematikës. 5-6 klasa/përmbledhje. – M.: “Globe”, 2009.

Puna e Makeeva në matematikë. - Saratov: "Lyceum", 2002

“Matematika” – suplement i gazetës “I Shtatori i Parë” Nr.7, 2005.

Revista e fizikës dhe matematikës "Kvant", nr. 6, 1994.

Këpucët në xhepin e Kangurit. - M.: Bustard, 2010.

Revista e fizikës dhe matematikës "Kvant", nr. 6, 1994.

Përgatitja e nxënësve për olimpiadat e matematikës. 5-6 klasa/përmbledhje. – M.: “Globe”, 2009.

Revista e fizikës dhe matematikës "Kvant", nr. 6, 1994.

Këpucët në xhepin e Kangurit. - M.: Bustard, 2010.

Puna e Makeeva në matematikë. - Saratov: "Lyceum", 2002

Puna e Makeeva në matematikë. - Saratov: "Lyceum", 2002

Zgjuarsia e Ignatiev. - M.: "Omega", 1994.

Puna e Makeeva në matematikë. - Saratov: "Lyceum", 2002

Përgatitja e nxënësve për olimpiadat e matematikës. 5-6 klasa/përmbledhje. – M.: “Globe”, 2009.

Këpucët në xhepin e Kangurit. - M.: Bustard, 2010.

Para se të filloni të studioni vetë algoritmet, duhet të keni njohuri bazë për vetë grafikët dhe të kuptoni se si ato përfaqësohen në një kompjuter. Të gjitha aspektet e teorisë së grafikut nuk do të përshkruhen në detaje këtu (kjo nuk kërkohet), por vetëm ato, injoranca e të cilave do të komplikojë ndjeshëm asimilimin e kësaj fushe të programimit.

Disa shembuj do të japin një skicë të vogël të grafikut. Pra, një grafik tipik është një hartë metroje ose ndonjë rrugë tjetër. Në veçanti, programuesi është i njohur me një rrjet kompjuterik, i cili është gjithashtu një grafik. Gjëja e zakonshme këtu është prania e pikave të lidhura me linja. Pra, në një rrjet kompjuterik, pikat janë serverë individualë, dhe linjat janë lloje të ndryshme të sinjaleve elektrike. Në metro, e para janë stacionet, e dyta janë tunelet e vendosura midis tyre. Në teorinë e grafikëve, pikat quhen majat (nyjet), dhe linjat janë brinjët (harqe). Kështu, grafikuështë një koleksion kulmesh të lidhura me skaje.

Matematika nuk vepron me përmbajtjen e gjërave, por me strukturën e tyre, duke e abstraguar atë nga gjithçka që jepet në tërësi. Duke përdorur pikërisht këtë teknikë, mund të konkludojmë se disa objekte janë grafikë. Dhe duke qenë se teoria e grafikut është pjesë e matematikës, nuk ka absolutisht asnjë ndryshim për të se çfarë është në parim një objekt; e vetmja gjë e rëndësishme është nëse është grafik, pra nëse ka vetitë e kërkuara për grafikët. Prandaj, para se të japim shembuj, ne theksojmë në objektin në shqyrtim vetëm atë që mendojmë se do të na lejojë të tregojmë një analogji, ne kërkojmë atë që është e zakonshme.

Le të kthehemi te rrjeti kompjuterik. Ai ka një topologji të caktuar dhe mund të përshkruhet në mënyrë konvencionale në formën e një numri të caktuar kompjuterësh dhe shtigjeve që i lidhin ato. Figura më poshtë tregon një topologji të lidhur plotësisht si shembull.

Në thelb është një grafik. Pesë kompjuterët janë kulmet, dhe lidhjet (shtigjet e sinjalit) ndërmjet tyre janë skajet. Duke zëvendësuar kompjuterët me kulme, marrim një objekt matematikor - një grafik, i cili ka 10 skaje dhe 5 kulme. Kulmet mund të numërohen në çfarëdo mënyre, dhe jo domosdoshmërisht siç tregohet në figurë. Vlen të përmendet se ky shembull nuk përdor një lak të vetëm, domethënë një skaj që lë një kulm dhe hyn menjëherë në të, por sythe mund të shfaqen në probleme.

Këtu janë disa shënime të rëndësishme të përdorura në teorinë e grafikëve:

• G=(V, E), këtu G është grafiku, V janë kulmet e tij dhe E janë skajet e tij;
• |V| – renditja (numri i kulmeve);
• |E| – madhësia e grafikut (numri i skajeve).

Në rastin tonë (Fig. 1) |V|=5, |E|=10;

Kur çdo kulm tjetër është i aksesueshëm nga çdo kulm, atëherë quhet një graf i tillë i paorientuar grafiku i lidhur (Fig. 1). Nëse grafiku është i lidhur, por ky kusht nuk plotësohet, atëherë quhet graf i tillë i orientuar ose digrafi (Fig. 2).

Grafikët e drejtuar dhe të padrejtuar kanë konceptin e shkallës së kulmit. Shkalla e lartëështë numri i skajeve që e lidhin me kulme të tjera. Shuma e të gjitha shkallëve të një grafiku është e barabartë me dyfishin e numrit të të gjitha skajeve të tij. Për figurën 2, shuma e të gjitha fuqive është 20.

Në një digraf, ndryshe nga një grafik i padrejtuar, është e mundur të lëvizësh nga kulmi h në kulmin s pa kulme të ndërmjetme, vetëm kur një skaj del nga h dhe hyn në s, por jo anasjelltas.

Grafikët e drejtuar kanë shënimin e mëposhtëm:

G=(V, A), ku V janë kulme, A janë tehe të drejtuara.

Lloji i tretë i grafikëve është të përziera grafikët (Fig. 3). Ata kanë skaje të drejtuara dhe jo të drejtuara. Formalisht, një grafik i përzier shkruhet kështu: G=(V, E, A), ku secila nga shkronjat në kllapa nënkupton të njëjtën gjë që i ishte caktuar më parë.

Në grafikun në figurën 3, disa harqe janë të drejtuar [(e, a), (e, c), (a, b), (c, a), (d, b)], të tjerët janë të padrejtuar [(e, d), (e, b), (d, c)…].

Në pamje të parë, dy ose më shumë grafikë mund të duken të ndryshëm në strukturë, gjë që lind për shkak të paraqitjes së tyre të ndryshme. Por nuk është gjithmonë kështu. Le të marrim dy grafikë (Fig. 4).

Ato janë ekuivalente me njëra-tjetrën, sepse pa ndryshuar strukturën e një grafi, mund të ndërtoni një tjetër. Grafikët e tillë quhen izomorfe, d.m.th., duke pasur vetinë që çdo kulm me një numër të caktuar skajesh në një graf të ketë një kulm identik në një tjetër. Figura 4 tregon dy grafikë izomorfikë.

Kur çdo skaj i grafikut shoqërohet me një vlerë të caktuar që quhet pesha e skajit, atëherë një grafik i tillë pezulluar. Në detyra të ndryshme, lloje të ndryshme matjesh mund të veprojnë si pesha, për shembull, gjatësitë, çmimet, rrugët, etj. Në paraqitjen grafike të një grafiku, vlerat e peshës tregohen, si rregull, pranë skajeve.

Në cilindo nga grafikët që kemi shqyrtuar, është e mundur të zgjidhni një shteg dhe, për më tepër, më shumë se një. Rrugëështë një sekuencë kulmesh, secila prej të cilave është e lidhur me tjetrën përmes një skaji. Nëse kulmi i parë dhe i fundit përputhen, atëherë një shteg i tillë quhet cikël. Gjatësia e një shtegu përcaktohet nga numri i skajeve që e përbëjnë atë. Për shembull, në figurën 4.a rruga është sekuenca [(e), (a), (b), (c)]. Ky shteg është një nëngraf, pasi për të vlen përkufizimi i këtij të fundit, përkatësisht: grafiku G'=(V', E') është nëngraf i grafikut G=(V, E) vetëm nëse V' dhe E' i përkasin V, E.

Përcaktohet një lidhje incidence midis elementeve të grupit të kulmeve dhe grupit të skajeve. Një skaj e thuhet se është incident me kulmet v1, v2 nëse i lidh këto kulme dhe anasjelltas, secila nga kulmet v1, v2 është përplasje me skajin e.

Le të shohim paraqitjen grafike të grafikëve në Tabelën 1.

Tabela 1. Paraqitja grafike e grafikëve

Shumë rezultate të marra për grafikë të thjeshtë mund të transferohen lehtësisht në objekte më të përgjithshme në të cilat dy kulme mund të lidhen me më shumë se një skaj. Përveç kësaj, shpesh është e përshtatshme të hiqet kufizimi që një skaj duhet të lidhë dy kulme të ndryshme dhe të lejojë ekzistencën e sytheve. Objekti që rezulton, i cili mund të ketë skaje dhe sythe të shumta, quhet grafik (pseudograf). Një pseudograf pa sythe quhet multigraf

Le të shohim disa lloje të rëndësishme grafikësh.

Përkufizimi. Një grafik, skajet e të cilit janë bosh, quhet graf plotësisht i shkëputur (ose bosh). Një grafik plotësisht i shkëputur shënohet me N

Vini re se në një grafik krejtësisht të shkëputur të gjitha kulmet janë të izoluara

Përkufizimi. Një graf i thjeshtë në të cilin çdo dy kulme janë ngjitur quhet i plotë. Grafiku i plotë shënohet me K

Vini re se grafiku i plotë plotëson barazinë

ku m është numri i skajeve, n është numri i kulmeve të grafikut.

Përkufizimi. Një grafik në të cilin të gjitha kulmet kanë të njëjtën shkallë lokale n quhet i rregullt (ose homogjen) i shkallës n.

Grafikët e rregullt të shkallës 3 quhen kub (ose trevalent).

Një shembull i famshëm i një grafi kub është grafiku Peterson

Në mesin e grafikëve të rregullt, të ashtuquajturat grafikë platonikë janë veçanërisht interesantë - grafikë të formuar nga kulmet dhe skajet e pesë shumëkëndëshave të rregullt - trupat e ngurtë platonike: katërkëndësh, kubi, tetëkëndësh, dodekaedron dhe ikozaedron.Figura 6 tregon një grafik që i korrespondon një kub.

Përkufizimi. Le të supozojmë se bashkësia e kulmeve të një grafi G mund të ndahet në dy nëngrupe të shkëputura V1 dhe V2 në mënyrë që secila skaj në G të lidhë një kulm nga V1 me një kulm nga V2, atëherë ky grafik quhet bipartit.

Një grafik bipartit mund të përcaktohet edhe në një mënyrë tjetër - në kuptimin e ngjyrosjes së kulmeve të tij me dy ngjyra, le të themi të kuqe dhe blu. Një graf quhet bipartit nëse secila kulme e tij mund të jetë me ngjyrë të kuqe ose blu në mënyrë që çdo skaj të ketë një skaj të kuq dhe tjetrin blu.

Përkufizimi. Nëse në një graf bipartit çdo kulm nga V1 është i lidhur me çdo kulm nga V2, atëherë grafiku quhet bipartit i plotë.

Vini re se grafiku Km. n ka saktësisht m + n kulme dhe mn skaje.

Përkufizimi. Bashkimi i grafikëve

quhet grafik

Përkufizimi. Nga kryqëzimi i grafikëve

quhet grafik

Përkufizimi. Lidhja e grafikëve G1 dhe G2 është një grafik i ri i të cilit

dhe grupi i skajeve janë të gjitha skajet e grafikut të parë dhe të dytë dhe skajet që lidhin çdo kulm të grafikut të parë me kulmin e parë të grafikut të dytë.

Përkufizimi. Një graf quhet i lidhur nëse nuk mund të paraqitet si bashkim i dy grafikëve dhe shkëputet ndryshe.

Natyrisht, çdo graf i shkëputur mund të përfaqësohet si një bashkim i një numri të kufizuar grafikësh të lidhur - secili prej grafëve të tillë të lidhur quhet një komponent i lidhur i grafikut.

Përkufizimi. Një graf i rregullt i lidhur i shkallës 2 quhet graf ciklik. Shënuar me Cn.

Përkufizimi. Lidhja e grafikëve N1 dhe Cn-1 (n3) quhet rrotë me n kulme. Shënuar me Wn (Figura 10)

Përkufizimi. Komplementi i një grafi të thjeshtë G është një graf i thjeshtë me një grup kulmesh V(G) në të cilin dy kulme janë ngjitur nëse dhe vetëm nëse nuk janë ngjitur në grafikun origjinal.

Emërtimi. Me fjalë të tjera, plotësuesi i një grafi është një grafik që përmban të gjitha kulmet e grafikut origjinal dhe vetëm ato skaje që i mungojnë grafikut origjinal për ta bërë atë të plotë.

Përkufizimi. Një nëngraf i një grafi G është një graf, të gjitha kulmet dhe skajet e të cilit gjenden midis kulmeve dhe skajeve të grafikut G. Një nëngraf quhet i duhur nëse është i ndryshëm nga vetë grafiku.

Grafikët janë një temë argëtuese, shpërblyese dhe e frikshme. Teoria e grafikut – “Tmerri i nxënësit”. Algoritmet e grafikut janë mendjet e mahnitshme të njerëzve që i zbuluan ato.

Çfarë është një grafik? Për t'iu përgjigjur kësaj pyetjeje për lexuesit e mi, unë do ta përshkruaj temën pak më ndryshe.
Një grafik është një grup objektesh.
Në shumicën e problemeve këto janë objekte të të njëjtit lloj. (Shumë qytete, ose shumë shtëpi, ose shumë njerëz, ose shumë gjëra të tjera të të njëjtit lloj)

Për të zgjidhur problemet me një grup të tillë, duhet të caktoni çdo objekt nga ky grup si diçka. Në përgjithësi pranohet ta quajmë këtë gjë kulmet e grafikut.

Është i përshtatshëm për të përshkruar grafikët dhe përkufizimet bazë me fotografi, kështu që fotografitë duhet të përfshihen për të lexuar këtë faqe.

Siç shkrova më herët, një grafik është një grup objektesh. Këto objekte janë zakonisht të të njëjtit lloj. Mënyra më e lehtë për të dhënë një shembull është në qytete. Secili prej nesh e di se çfarë është një qytet dhe çfarë është një rrugë. Secili prej nesh e di se mund të ketë ose jo rrugë për në qytet. Në përgjithësi, çdo grup objektesh mund të karakterizohet si grafik.

Nëse flasim për grafikun si për qytete, atëherë mund të ndërtohen rrugë midis qyteteve, ose mund të shkatërrohet diku, të mos ndërtohet, ose qyteti përgjithësisht ndodhet në një ishull, nuk ka urë dhe vetëm rrugët e asfaltuara janë me interes. . Pavarësisht se nuk ka rrugë për në një qytet të tillë, ky qytet mund të përfshihet në shumë objekte të analizuara dhe të gjitha objektet e marra së bashku përbëjnë një koleksion objektesh ose, më thjesht, një grafik.

Me siguri keni lexuar libra shkollorë dhe keni parë këtë shënim G(V,E) ose diçka të ngjashme. Pra, V është një objekt nga i gjithë grupi i objekteve. Në rastin tonë, grupi i objekteve janë qytete, prandaj, V është një qytet specifik. Meqenëse objektet nuk janë domosdoshmërisht qytete, dhe fjala objekt mund të jetë konfuze, një objekt i tillë nga grupi mund të quhet pikë, pikë ose diçka tjetër, por më së shpeshti quhet kulmi i grafikut dhe shënohet me shkronjën. V.
Në programim, kjo zakonisht është ose një kolonë ose rresht i një grupi dydimensional, ku grupi quhet ose një matricë fqinjësie ose një matricë incidence.

Në literaturë, në internet dhe përgjithësisht kudo që shkruhet diçka për grafikët, do të hasni koncepte të tilla si harqet dhe skajet. Kjo figurë tregon skajet e grafikut. ato. këto janë tre skajet E1, E2 dhe E3.

Një hark dhe një skaj ndryshojnë në atë që një skaj është një lidhje dydrejtimëshe. E donte, shkoi te fqinji, deshi, u kthye nga fqinji. Nëse nuk është shumë e qartë, atëherë mund të imagjinoni një shtëpi, një fushë ajrore, një aeroplan fluturues dhe një parashutist. Një parashutë mund të shkojë nga shtëpia e tij në aeroport, por kur arrin në aeroport, kujton se e ka harruar parashutën e tij me fat në shtëpi, pastaj kthehet në shtëpi dhe merr parashutën. - Një rrugë përgjatë së cilës mund të ecësh përpara dhe mbrapa quhet skaj.
Nëse një parashutë është në aeroplan dhe po kërcen nga avioni, por parashutisti ka harruar të veshë parashutën e tij me fat në aeroplan, a do të mundet ai që të marrë atë që ka harruar? Një rrugë që shkon vetëm në një drejtim quhet hark. Zakonisht themi se një skaj lidh dy kulme dhe një hark shkon nga një kulm në tjetrin.

Në këtë figurë, grafiku ka vetëm harqe. Harqet në grafik tregohen me shigjeta, sepse drejtimi i arritshëm është shumë i qartë. Nëse një grafik përbëhet vetëm nga harqe të tillë, atëherë një graf i tillë quhet i drejtuar.

Shpesh do të hasni konceptet e afërsisë dhe incidencës. Në figurë, dy skajet që shkojnë në një pikë janë shënuar me të kuqe. Skajet e tilla, si kulmet e përshkruara më sipër, quhen gjithashtu ngjitur.

Nuk përshkruhet shumë, por ky informacion mund të ndihmojë dikë.

"Një mënyrë tjetër emocionuese për të zgjidhur problemet" (metoda e grafikut) Autor: Maria Pyrkova, nxënëse e klasës së 7-të në shkollën me konvikt nr. 9 të Hekurudhave Ruse, Kinel, Rajoni i Samaras Mbikëqyrëse: Olga Alekseevna Stepanova, mësuese e matematikës e kategorisë më të lartë. Kinel, 2015

Rëndësia e rolit vendimtar të problemeve në mësimdhënien e matematikës; hyrje në kursin shkollor të rubrikave "Kombinatorika", "Logjika", "Probabiliteti"; gjetja e mënyrave për zgjidhjen e problemeve jo standarde.

Qëllimi i studimit: të studiojë konceptin e “grafit” dhe elementeve të tij; zbatohen gjatë zgjidhjes së llojeve të ndryshme të problemeve.

Objekti i studimit: grafik LËNDA E KËRKIMIT historia e matematikës, llojet e problemave, metodat e zgjidhjes së problemave.

Metodat kryesore të kërkimit: kërkimi; përdorni në praktikë. përpunimi i të dhënave kompjuterike; klasifikimi dhe analiza e materialit të mbledhur; përzgjedhje matematikore.

Koncepti matematikor i "grafit". Në matematikë, një grafik është një grup i kufizuar pikash, disa prej të cilave janë të lidhura me vija. Pikat quhen kulme të grafikut, kurse linjat lidhëse quhen skaje. një grafik zero është një graf jo i plotë. grafiku i plotë.

Fusha e zbatimit të grafikëve

Pjesa praktike

Algoritmi për përpilimin e grafikut Diskutoni për çfarë procesi po flasim? Cilat sasi e karakterizojnë këtë proces? Si lidhen këto sasi? Sa procese përshkruhen në problem? A ka lidhje midis elementeve? Nëse përgjigjet e këtyre pyetjeve janë shkruar në mënyrë skematike, atëherë ky diagram do të jetë një grafik rrjeti.

"Sa krerë bagëti keni në tufën tuaj?" Pyetjes së udhëtarit: bariu u përgjigj: “Nëse do të shtoja një lopë në tufën time, atëherë një e treta e gjithë tufës do të përbëhej nga dele dhe dhi. Nëse do t'i shtonim një dele deleve dhe dhive ekzistuese, atëherë pjesa e shtatë e tyre do të ishte dhi, nga të cilat pjesa e tretë është vetëm një kec i vogël.” Sa krerë bagëti kishte në tufë? Zgjidhja: Le të krijojmë një grafik bazuar në kushtet e problemit. Le të vendosim përsëri. Përgjigje: ka 59 krerë bagëti në tufë.

Detyrat e lëvizjes. Makina e përshkroi pjesën e parë të rrugës për 3 orë, dhe seksionin e dytë për 2 orë. Gjatësia e të dy seksioneve së bashku është 267 km. Me çfarë shpejtësie po shkonte makina në secilin seksion, nëse shpejtësia në seksionin e dytë ishte 8.5 km/h më e madhe se në të parën? Le të ndërtojmë një grafik rrjeti. Le të V 1 = x km/h, pastaj V 2 = x+ 8,5 km/h, S 1 = 3x km, S 2 = 2(x+8,5) km Le të krijojmë ekuacionin: 3x + 2(x+8,5 ) = 267 Përgjigje: 50 km/h

Probleme kombinuese. Detyra "Cila është më e lartë?" Në terrenin e shkollës rriten 8 pemë: mollë, plepi, thupër, rowan, lisi, panje, larsh dhe pisha. Rowan është më i lartë se larshi, pema e mollës është më e lartë se panja, lisi është më e ulët se thupra, por më e lartë se pisha, pisha është më e lartë se rowan, thupra është më e ulët se plepi dhe larshi është më i lartë se pema e mollës. Rregulloni pemët nga më e shkurtra tek më e larta. Përgjigje: panja është pema më e shkurtër.

Sondazhi i shokëve të klasës

Përfundim "Herët a vonë, çdo ide e saktë matematikore gjen zbatim në një gjë ose në një tjetër." (A.N. Krylov) Grafikët janë objekte të mrekullueshme matematikore me të cilat mund të zgjidhni probleme matematikore, ekonomike dhe logjike. Grafikët ju lejojnë të përfaqësoni vizualisht kushtet e një problemi, të mbani në kujtesë fakte të shumta dhe për këtë arsye të thjeshtoni ndjeshëm zgjidhjen e tij. Krijon interes për të mësuar matematikën dhe për të arritur rezultate të mira.

Referenca Fjalori Enciklopedik i një Matematikani të Ri. \ Komp. A.P.Savin - M.: Pedagogji, 1989 Kuanti Nr. 6 1994 M. Gardner “Mathematical leisure” M.: Mir, 1972 Berge K. Teoria e grafikut dhe zbatimi i saj. IL, 1962. Matematika, tekst mësimor për klasën e V. / N.Ya.Vilenkin, V.I.Zhokhov dhe të tjerët - M: Edukimi, 2011 Matematikë, tekst shkollor për klasën e 6-të. / N.Ya.Vilenkin, V.I.Zhokhov dhe të tjerët - M: Edukimi, 2011 Algjebra: tekst shkollor për klasën e 7-të. / Yu.N. Makarychev et al., redaktuar nga S.A. Telyakovsky.-M.: Edukimi, 2011 Kurse zgjedhore "Zgjidhja e problemeve duke përdorur grafikët" / autor - L.N. Kharlamov. - Volgograd: Mësues, 2007.

Faleminderit per vemendjen!