Praktična primjena teorije grafova. Što je metoda grafa? Zaključci poglavlja

Teorija grafova- jedan od najopsežnijih odjeljaka diskretne matematike, široko se koristi u rješavanju ekonomskih i upravljačkih problema, u programiranju, kemiji, dizajnu i proučavanju električnih krugova, komunikologiji, psihologiji, psihologiji, sociologiji, lingvistici i drugim područjima znanja. Teorija grafova sustavno i dosljedno proučava svojstva grafova, za koje možemo reći da se sastoje od skupova točaka i skupova linija, odražavajući veze između tih točaka. Utemeljiteljem teorije grafova smatra se Leonard Euler (1707-1882), koji je 1736. riješio problem Konigsberških mostova, poznatih u to vrijeme.

Izrada grafikona kako bi se prikazale relacije na skupovima. Na primjer, neka skup A = {a1 , a 2 , ... a n)- puno ljudi, a svaki element će biti prikazan kao točka. Gomila B = {b1 , b 2 , ... b m)- skup veziva (ravne linije, lukovi, segmenti - još nije važno). Na setu A dat je odnos poznanstva između ljudi iz ovog skupa. Izgradnja grafa iz točaka i snopova. Ligamenti će povezati parove ljudi koji su međusobno upoznati. Naravno, broj poznanika nekih ljudi može se razlikovati od broja poznanika drugih ljudi, a neki možda nisu ni s kim upoznati (takvi će elementi biti točke koje nisu povezane ni s jednim drugim). Dakle, dobili smo graf!

Ono što smo prvo nazvali "točke" treba zvati vrhovima grafa, a ono što smo nazvali "veznicima" - rubovima grafa.

Teorija grafova zanemaruje specifičnu prirodu skupova A i B... Postoji veliki broj vrlo različitih specifičnih problema, pri rješavanju kojih se može privremeno zaboraviti na specifičan sadržaj skupova i njihovih elemenata. Ova specifičnost ni na koji način ne utječe na tijek rješavanja problema, bez obzira na njegovu težinu! Na primjer, kada se odlučuje je li moguće iz točke a prijeđi na stvar e, krećući se samo po linijama koje spajaju točke, nije bitno radi li se o ljudima, gradovima, brojevima itd. Ali kada je problem riješen, dobivamo rješenje koje je ispravno za svaki sadržaj koji je modeliran kao graf. Stoga ne čudi da je teorija grafova jedan od najtraženijih alata za stvaranje umjetne inteligencije: uostalom, Umjetna inteligencija sa sugovornikom može razgovarati i o pitanjima ljubavi, i o pitanjima glazbe ili sporta, i o pitanjima rješavanja raznih problema, a to čini bez ikakvog prijelaza (prebacivanja), bez kojeg u takvim slučajevima čovjek ne može.

A sada za rigorozne matematičke definicije grafa.

Definicija 1.Graf se zove sustav objekata proizvoljne prirode (vrhova) i snopova (brova) koji povezuju neke parove tih objekata.

Definicija 2. Neka V- (neprazan) skup vrhova, elemenata v∈V- vrhovi. Grafikon G = G(V) s mnogo vrhova V postoji neka obitelj parova oblika: e = (a, b) , gdje a,b∈V , što pokazuje koji vrhovi ostaju povezani. Svaki par e = (a, b) je rub grafa. Gomila U- mnogo rubova e graf. Vrhovi a i b- krajnje točke rebra e .

Grafovi kao struktura podataka.Široka primjena teorije grafova u informatici i informacijskoj tehnologiji posljedica je dodavanja gornjim definicijama pojma grafa kao strukture podataka. U informatici i informacijskoj tehnologiji graf se definira kao nelinearna struktura podataka. Što je onda linearna struktura podataka i po čemu se grafovi razlikuju od njih? Linearne strukture podataka odlikuju se činjenicom da povezuju elemente s odnosima tipa "jednostavnog susjedstva". Linearne strukture podataka su, na primjer, nizovi, tablice, popisi, redovi, stogovi, nizovi. Nasuprot tome, nelinearne strukture podataka su one u kojima se elementi nalaze na različitim razinama hijerarhije i dijele se u tri tipa: izvorne, generirane i slično. Dakle, graf je nelinearna struktura podataka.

Riječ count je grčkog porijekla, od riječi "pišem", "opisujem". S početka ovog članka znamo što točno graf opisuje: opisuje odnos. To jest, svaki graf opisuje odnos. I obrnuto: svaki odnos se može opisati kao graf.

Osnovni pojmovi teorije grafova

Koncept incidencije također je neophodan u razvoju algoritama za rješavanje mnogih praktičnih problema s grafovima. Na primjer, možete vidjeti implementaciju softvera prijelaz u dubinu grafa predstavljen matricom incidencije... Ideja je jednostavna: možete se kretati samo kroz vrhove povezane bridovima. A ako su neke vrijednosti dodijeljene rubovima ("skale", najčešće u obliku brojeva, takvi se grafovi nazivaju ponderirani ili označeni), tada možete riješiti složene primijenjene probleme, od kojih su neki spomenuti u završnom odlomku ove lekcije.

Klasični problemi teorije grafova i njihova rješenja

Jedan od prvih objavljenih primjera rada na teoriji grafova i korištenju grafova je "Problem Königsberškog mosta" iz 1736. godine od strane eminentnog matematičara Leonarda Eulera iz 18. stoljeća. U zadatku vam je data rijeka, otoci koje ova rijeka pere i nekoliko mostova. Pitanje problema: je li moguće, nakon napuštanja određene točke, proći svaki most samo jednom i vratiti se na početnu točku? (slika ispod)

Zadatak se može modelirati na sljedeći način: jedna točka je pričvršćena na svaki komad zemlje, a dvije točke su povezane linijom ako i samo ako su odgovarajuće kopnene površine povezane mostom (slika ispod, linije spajanja su iscrtane isprekidanim linijama ). Dakle, graf je konstruiran.

Eulerov odgovor na problemsko pitanje je sljedeći. Kada bi ovaj problem imao pozitivno rješenje, tada bi rezultirajući graf imao zatvorenu stazu koja prolazi duž bridova i sadržava svaki brid samo jednom. Ako takav put postoji, tada svaki vrh mora imati samo paran broj bridova. Ali rezultirajući graf ima vrhove s neparnim brojem bridova. Stoga problem nema pozitivno rješenje.

Prema ustaljenoj tradiciji, Eulerov graf je graf u kojemu je moguće prijeći sve vrhove i, u isto vrijeme, samo jednom prijeći jedan brid. U njemu svaki vrh mora imati samo paran broj bridova. Problem prosječne težine za Eulerove grafove - u materijalu "Osnovne vrste grafova".

Godine 1847. Kirchhoff je razvio teoriju stabala za rješavanje zajedničkog sustava linearnih algebarskih jednadžbi, koja omogućuje pronalaženje vrijednosti struje u svakom vodiču (luku) i u svakom krugu električnog kruga. Apstrahirajući od električnih krugova i sklopova koji sadrže otpore, kondenzatore, induktivne prigušnice itd., on je razmatrao odgovarajuće kombinatorne strukture koje sadrže samo vrhove i spojeve (rubove ili lukove), a za spojeve nije potrebno uzeti u obzir koje vrste električnih elemenata odgovaraju.... Tako je Kirchhoff svaki električni krug zamijenio odgovarajućim grafom i pokazao da za rješavanje sustava jednadžbi nije potrebno posebno razmatrati svaki ciklus grafa električnog kruga.

Cayley je 1858. godine, baveći se čisto praktičnim problemima organske kemije, otkrio važnu klasu grafova zvanih stabla. Pokušao je navesti izomere zasićenih ugljikovodika, s određenim brojem ugljikovih atoma. Cayley je prije svega formulirao problem apstraktno: pronađite broj svih stabala s str vrhove, od kojih svaki ima vrhove sa stupnjevima 1 i 4. Nije mogao odmah riješiti ovaj problem, te je počeo mijenjati njegovu formulaciju na način da je bilo moguće riješiti novi problem nabrajanja:

• ukorijenjena stabla (u kojima je odabran jedan od vrhova);
• sva stabla;
• stabla s stupnjevima vrhova koji ne prelaze 4;
• stabla sa stupnjevima vrhova jednakim 1 i 4 (postavka zadatka iz kemije).

Grafički zadaci za učvršćivanje osnovnih pojmova

Primjer 1. Neka A- skup brojeva 1, 2, 3: A= (1, 2, 3). Napravite grafikon za prikaz odnosa "

Riješenje. Očito, brojevi 1, 2, 3 trebaju biti predstavljeni kao vrhovi grafa. Tada svaki par vrhova mora biti spojen jednim bridom. Rješavajući ovaj problem, došli smo do takvih osnovnih pojmova teorije grafova kao što su usmjereni i neusmjereni grafovi... Neusmjereni grafovi su oni čiji rubovi nemaju smjer. Ili, kako još češće kažu, redoslijed dvaju krajeva brida nije bitan. Uistinu, graf izgrađen na samom početku ove lekcije i koji prikazuje odnos poznanstva između ljudi ne zahtijeva rubne smjerove, budući da se može tvrditi da je "osobi broj 1" poznato i "osoba broj 2", kao i "osoba". broj 2" sa "osobom broj 1". U našem trenutnom primjeru, jedan broj je manji od drugog, ali ne i obrnuto. Stoga, odgovarajući rub grafa mora imati smjer koji pokazuje koji je broj manji od drugog. To jest, redoslijed krajeva ruba je bitan. Takav graf (s rubovima usmjerenim u smjeru) naziva se usmjereni graf ili digraf.

Dakle, u našem setu A broj 1 je manji od broja 2 i broja 3, a broj 2 manji je od broja 3. Ova činjenica je prikazana rubovima koji imaju smjer, što je prikazano strelicama. Dobivamo sljedeći graf:

Primjer 2. Neka A- skup brojeva 2, 4, 6, 14: A= (2, 4, 6, 14). Postavite graf za prikaz odnosa "djeljivo sa" na ovaj skup.

Riješenje. U ovom primjeru će neki rubovi imati smjer, a neki neće, odnosno gradimo mješoviti graf... Nabrojimo odnose na skupu: 4 je u cijelosti djeljivo s 2, 6 je djeljivo s 2, 14 je djeljivo s 2, a svaki broj iz ovog skupa djeljiv je u potpunosti sam sa sobom. Taj omjer, odnosno kada se broj podijeli u potpunosti sam od sebe, bit će prikazan u obliku bridova koji povezuju vrh sa samim sobom. Takvi rubovi se nazivaju petlje... U ovom slučaju nije potrebno dati smjer petlji. Dakle, u našem primjeru postoje tri pravilna usmjerena ruba i četiri petlje. Dobivamo sljedeći graf:

Primjer 3. Zadani setovi A= (α, β, γ) i B= (a, b, c). Napravite graf za prikaz odnosa "Kartezijanski proizvod skupova".

Riješenje. Kao što je poznato iz definicije kartezijanski proizvod skupova, ne sadrži uređene skupove elemenata istog skupa. To jest, u našem primjeru ne možete kombinirati grčka slova s ​​grčkim i latinica s latinicom. Ova činjenica je prikazana u obrascu bipartitni graf, odnosno onaj u kojem su vrhovi podijeljeni na dva dijela tako da vrhovi koji pripadaju istom dijelu nisu međusobno povezani. Dobivamo sljedeći graf:

Primjer 4. Agencija za nekretnine zapošljava menadžere Igora, Sergeja i Petra. Servisiraju se objekti O1, O2, O3, O4, O5, O6, O7, O8. Izgradite grafikon za prikaz odnosa "Igor radi s objektima O4, O7", "Sergei radi s objektima O1, O2, O3, O5, O6", "Petar radi s objektom O8".

Riješenje. Graf koji prikazuje ove relacije također će biti bipartitan, budući da upravitelj ne radi s upraviteljem, a objekt ne radi s objektom. Međutim, za razliku od prethodnog primjera, graf će biti orijentiran. Doista, na primjer, Igor radi s objektom O4, ali objekt O4 ne radi s Igorom. Često, kada je takvo svojstvo odnosa očito, potreba da se daju smjernice rubovima može se činiti kao "matematička tupost". Ali ipak, a to proizlazi iz stroge prirode matematike, ako je odnos jednostran, onda morate dati smjernice rubovima. U primjenama relacija ta se strogost isplati, na primjer, u programima namijenjenim planiranju, gdje se koriste i grafovi, a ruta duž vrhova i bridova mora proći strogo u zadanom smjeru. Dakle, dobivamo sljedeći usmjereni bipartitni graf:

I opet na primjere s brojevima.

Primjer 5. Neka skup C = {2, 3, 5, 6, 15, 18} ... Izgradite graf realizirajući relaciju koja definira sve parove brojeva a i b mnoštva C, za koji, dijeljenjem drugog elementa s prvim, dobivamo kvocijent, koji je cijeli broj veći od 1.

Riješenje. Graf koji prikazuje ove relacije bit će orijentiran, budući da uvjet sadrži spominjanje drugog i prvog elementa, odnosno rub će biti usmjeren od prvog elementa prema drugom. Iz ovoga je nedvosmisleno jasno koji je element prvi, a koji drugi. Dodajmo malo terminologije: orijentirani bridovi obično se nazivaju lukovi. Naš graf će imati 7 lukova: e1 = (3, 15) , e2 = (3, 18) , e3 = (5, 15) , e4 = (3, 6) , e5 = (2, 18) , e6 = (6, 18) , e7 = (2, 6) ... U ovom primjeru, rubovi (lukovi) grafa jednostavno su numerirani, ali redni brojevi nisu jedina stvar koja se može dodijeliti luku. Luk se također može pripisati ljestvicama koje znače, na primjer, trošak otpreme robe s jedne točke na drugu. Ali s težinama lukova ćemo se upoznati kasnije i detaljnije. Dakle, dobivamo sljedeći usmjereni graf:

Kao što već znamo iz teoretskog uvoda, teorija grafova ne uzima u obzir specifičnost skupova, te se pomoću istog grafa mogu definirati relacije na skupovima vrlo različitog sadržaja. Odnosno, moguće je apstrahirati upravo od tog sadržaja prilikom modeliranja zadatka. Prijeđimo na primjere koji ilustriraju ovo prekrasno svojstvo teorije grafova.

Primjer 6. Na komadu šahovske ploče dimenzija 3 X 3 nalaze se dva bijela viteza i dva crna viteza kao što je prikazano na donjoj slici.

Je li moguće premjestiti vitezove u stanje prikazano na sljedećoj slici, imajući na umu da dvije figure ne mogu biti na istom polju?

Riješenje. U grafu koji se konstruira, parovi vrhova bit će povezani relacijom "poteza viteza". To jest, jedan vrh je onaj iz kojeg je vitez otišao, a drugi je onaj u koji je došao, a međućelija slova "g" bit će izvan ovog odnosa. Dobivamo sljedeći graf:

A ipak se dizajn pokazao glomaznim. U njemu su vidljive ćelije šahovske ploče, a mnogi rubovi grafa se sijeku. Je li moguće apstrahirati od fizičkog izgleda šahovske ploče i lakše zamisliti odnos? Ispostavilo se da možete. U novom grafu susjedni vrhovi bit će oni koji su povezani odnosom "potez viteza", a ne oni susjedni na šahovskoj ploči (slika ispod).

Sada je lako vidjeti da je odgovor na pitanje ovog problema negativan. U početnom stanju nema crnog viteza između dva bijela viteza, ali u konačnom bi ovaj crni vitez trebao biti. Rubovi grafa postavljeni su tako da dva susjedna viteza ne mogu preskočiti jedan drugoga.

Primjer 7. Problem je oko vuka, koze i kupusa. S jedne strane rijeke nalaze se čovjek (H), čamac, vuk (V), koza (Kz) i kupus (Kp). U čamcu se može istovremeno nalaziti jedna osoba i najviše jedan od prevoženih predmeta. Osoba mora prevesti sve predmete na drugu stranu, poštujući stanje: vuk se ne može ostaviti bez nadzora s kozom i koza sa kupusom.

Riješenje. U grafu koji se konstruira, vrhovi su konfiguracije, a bridovi su odnos "jednog putovanja brodom" između konfiguracija. Konfiguracija znači položaj objekata na izvornoj i na suprotnoj obali. Svaka konfiguracija je prikazana kao ( A|B) , gdje A- objekti koji se nalaze na izvornoj obali, i B- objekti koji se nalaze na suprotnoj obali. Početna konfiguracija je dakle - (PMKpKz| ) ... Na primjer, nakon prelaska koze na drugu stranu, konfiguracija će biti (VKp|ChKz) ... Konačna konfiguracija je uvijek ( |PMKpKz) ... Sada možemo izgraditi graf, već znajući što znače vrhovi i bridovi:

Vrhove grafa postavljamo tako da se bridovi ne sijeku, a vrhovi koji su povezani relacijom na grafu su susjedni. Tada će biti puno lakše vidjeti odnos (za uvećanje slike kliknite na nju lijevom tipkom miša):

Kao što možete vidjeti, postoje dva različita kontinuirana puta od početne konfiguracije do konačne. Dakle, problem ima dva različita rješenja (i oba su točna).

Teorija grafova i najvažniji suvremeni primijenjeni problemi

Na temelju teorije grafova razvijene su metode za rješavanje primijenjenih problema u kojima se vrlo složeni sustavi modeliraju u obliku grafova. U ovim modelima čvorovi sadrže pojedinačne komponente, a rubovi predstavljaju odnose između komponenti. Obično se ponderirani grafovi koriste za modeliranje transportnih mreža, sustava čekanja i planiranja mreže. Već smo govorili o njima, to su grafovi u kojima su težine dodijeljene lukovima.

Grafovi stabla koriste se, na primjer, za izgradnju stabla odluka(koristi se za analizu rizika, analizu mogućih akvizicija i gubitaka u uvjetima neizvjesnosti). Koristeći teoriju grafova, razvio i drugi brojni matematički modeli za rješavanje problema u određenim predmetnim područjima.

Grafovi i problem toka

Formulacija problema. Postoji sustav vodovodnih cijevi, prikazan grafikonom na donjoj slici.

Svaki luk u grafu predstavlja cijev. Brojevi iznad lukova (skala) predstavljaju propusnost cijevi. Čvorovi su spojevi cijevi. Voda kroz cijevi teče samo u jednom smjeru. Čvor S- izvor vode, čvor T- dionica. Potrebno je maksimalno povećati volumen vode koja teče od izvora do odvoda.

Da biste riješili problem tokova, možete koristiti Ford-Fulkersonovu metodu. Ideja metode: potraga za maksimalnim protokom izvodi se korak po korak. Na početku algoritma se pretpostavlja da je protok jednak nuli. U svakom sljedećem koraku povećava se vrijednost protoka, za što se traži komplementarni put, duž kojeg ulazi dodatni protok. Ovi se koraci ponavljaju sve dok postoje dodatni putovi. Problem se uspješno primjenjuje u različitim distribuiranim sustavima: sustavu napajanja, komunikacijskoj mreži, željezničkom sustavu i dr.

Grafovi i planiranje mreže

Ponderirani grafovi poznati kao PERT mreže (PERT) naširoko se koriste u zadacima planiranja za složene procese koji se sastoje od mnogih poslova, od kojih se neki izvode paralelno, a neki serijski.

PERT - Program (Project) Evaluation and Review Technique - tehnika za evaluaciju i analizu programa (projekata), koja se koristi u upravljanju projektima.

PERT mreža je ponderirani aciklički usmjereni graf, u kojem svaki luk predstavlja radnju (radnju, operaciju), a težina luka je vrijeme potrebno za njegovo dovršenje.

Ako mreža ima lukove ( a, b) i ( b, c), zatim rad predstavljen lukom ( a, b), mora biti dovršen prije početka izvođenja posla predstavljenog lukom ( b, c). Svaki vrh ( vi) predstavlja trenutak u vremenu do kojeg bi sav posao trebao biti dovršen, određen lukovima koji završavaju na vrhu ( vi).

U kolumni poput ove:

• jedan vrh koji nema prethodnike određuje vrijeme početka rada;
• jedan vrh koji nema sljedbenika odgovara trenutku završetka radnog paketa.

Put najveće duljine između ovih vrhova grafa (od početka do kraja procesa obavljanja rada) naziva se kritični put. Kako bi se skratilo vrijeme izvođenja cjelokupnog kompleksa radova, potrebno je pronaći radove koji leže na kritičnom putu i smanjiti njihovo trajanje npr. privlačenjem dodatnih izvođača, mehanizama i novih tehnologija.

Cijeli blok "Teorija grafova"

Što je metoda grafa?

Riječ "graf" u matematici označava sliku na kojoj je nacrtano nekoliko točaka, od kojih su neke povezane linijama. Prije svega, treba reći da grafovi, o kojima će biti riječi, nemaju nikakve veze s aristokratima prošlosti. Naši "grafovi" imaju korijene u grčkoj riječi "grapho", što znači "pišem". Isti korijen u riječima "grafika", "biografija".

U matematici definicija grafa je zadan kako slijedi: graf je konačan skup točaka, od kojih su neke povezane linijama. Točke se nazivaju vrhovima grafa, a vezne linije nazivaju se bridovima.

Poziva se dijagram grafa koji se sastoji od "izoliranih" vrhova nulti grafikon. (sl. 2)

Zovu se grafovi u kojima nisu izgrađeni svi mogući bridovi nepotpuni grafovi. (sl. 3)

Zovu se grafovi u kojima su konstruirani svi mogući bridovi potpuni grafovi. (sl. 4)

Zove se graf čiji je svaki vrh povezan s bridom bilo kojeg drugog vrha potpuni.

Imajte na umu da ako cijeli graf ima n vrhova, tada će broj bridova biti jednak

n (n-1) / 2

Doista, broj bridova u cjelovitom grafu s n vrhova definiran je kao broj neuređenih parova sastavljenih od svih n točaka-brova grafa, tj. kao broj kombinacija od n elemenata, po 2:

Graf koji nije potpun može se dovršiti da bude potpun s istim vrhovima dodavanjem bridova koji nedostaju. Na primjer, slika 3 prikazuje nepotpun graf s pet vrhova. Na slici 4, bridovi koji graf pretvaraju u potpun graf prikazani su drugom bojom; skup vrhova grafa s tim bridovima naziva se komplement grafa.

Stupnjevi vrhova i broj bridova.

Broj bridova koji izlaze iz vrha grafa naziva se stupanj vrha... Zove se vrh grafa koji ima neparan stupanj neparan, i jednak stupanj - čak.

Ako su stupnjevi svih vrhova grafa jednaki, tada se graf naziva homogena... Dakle, svaki potpuni graf je homogen.

sl. 5

Slika 5 prikazuje graf s pet čvorova. Stupanj vrha A označit ćemo sa St.A.

Na slici: sv. A = 1, sv. B = 2, sv. B = 3, sv. G = 2, sv. D = 0.

Formulirajmo neke obrasce svojstvene određenim grafovima.

Uzorak 1.

Stupnjevi vrhova potpunog grafa su isti, a svaki od njih je za 1 manji od broja vrhova ovog grafa.

Dokaz:

Ovaj obrazac je očigledan nakon razmatranja bilo kojeg cjelovitog grafikona. Svaki je vrh povezan bridom sa svakim vrhom, osim sa samim sobom, odnosno iz svakog vrha grafa s n vrhova proizlazi n-1 bridova, prema potrebi.

Uzorak 2.

Zbroj stupnjeva vrhova grafa je paran broj jednak dvostrukom broju bridova u grafu.

Ovaj uzorak vrijedi ne samo za potpuni, već i za bilo koji graf. Dokaz:

Doista, svaki rub grafa povezuje dva vrha. Dakle, ako zbrojimo broj stupnjeva svih vrhova grafa, onda ćemo dobiti udvostručeni broj bridova 2R (R je broj bridova u grafu), budući da je svaki brid dvaput brojen, što je bilo potrebno da se dokaže

Broj neparnih vrhova bilo kojeg grafa je paran. Dokaz:

Razmotrimo proizvoljan graf G. Pretpostavimo da je u ovom grafu broj vrhova stupnja 1 jednak K1; broj vrhova stupnja 2 jednak je K2; ...; broj vrhova stupnja n jednak je Kn. Tada se zbroj stupnjeva vrhova ovog grafa može zapisati kao
K1 + 2K2 + ZK3 + ... + nKn.
S druge strane: ako je broj bridova u grafu R, tada je iz pravilnosti 2 poznato da je zbroj stupnjeva svih vrhova grafa jednak 2R. Tada možemo napisati jednakost
K1 + 2K2 + ZK3 + ... + nKn = 2R. (jedan)
Izdvojimo na lijevoj strani jednakosti zbroj jednak broju neparnih vrhova grafa (K1 + K3 + ...):
K1 + 2K2 + ZK3 + 4K4 + 5K5 + ... + nK = 2R,
(K1 + K3 + K5 + ...) + (2K2 + 2X3 + 4K4 + 4K5 + ...) = 2R
Druga zagrada je paran broj kao zbroj parnih brojeva. Primljeni iznos (2R) je paran broj. Stoga je (K1 + K3 + K5 + ...) paran broj.

Razmotrimo sada zadatke riješene pomoću grafova:

Zadatak. Klasni primat . Na prvenstvu razreda stolnog tenisa nastupa 6 sudionika: Andrej, Boris, Viktor, Galina, Dmitrij i Elena. Prvenstvo se održava u kružnom sustavu - svaki od sudionika igra sa svakim od ostalih jednom. Do sada su neke igre već odigrane: Andrej je igrao s Borisom, Galinom i Elenom; Boris, kao što je već spomenuto, s Andrejem i također s Galinom; Victor - s Galinom, Dmitrijem i Elenom; Galina s Andrejem i Borisom; Dmitrij - s Viktorom i Elenom - s Andrejem i Viktorom. Koliko je utakmica do sada odigrano i koliko ih je ostalo?

Rasprava. Predstavite ove zadatke u obliku dijagrama. Sudionike ćemo predstavljati točkama: Andrej - točka A, Boris - točka B itd. Ako su dva sudionika već igrala jedan s drugim, točke koje ih predstavljaju spojit ćemo segmentima. Ispada da je krug prikazan na slici 1.

Točke A, B, C, D, D, E su vrhovi grafa, koji povezuju svoje segmente - rubove grafa.

Imajte na umu da točke presjeka bridova grafa nisu njegovi vrhovi.

Broj odigranih igara do danas jednak je broju bridova, t.j. 7.

Kako bi se izbjegla zabuna, vrhovi grafa često se ne prikazuju kao točke, već u malim krugovima.

Da bismo pronašli broj igara koje će se igrati, izgradit ćemo drugi graf s istim vrhovima, ali ćemo rubovima povezati one sudionike koji još nisu igrali jedni s drugima (slika 2) Ovaj graf ima 8 bridova, što znači da ostalo je još 8 utakmica : Andrej - s Victorom i Dmitryjem; Boris - S Viktorom, Dmitrijem i Elenom itd.

Pokušajmo napraviti graf za situaciju opisanu u sljedećem problemu:

Zadatak . Tko igra Lyapkin - Tyapkin? Školski dramski klub odlučio je postaviti Gogoljevu "Glavni inspektor". A onda je izbio žestoki spor. Sve je počelo s Lyapkin - Tyapkin.

Lyapkin - Ja ću biti Tyapkin! - odlučno je izjavio Gena.

Ne, ja ću biti Lyapkin - Tyapkin, prigovorio je Dima. - Od ranog djetinjstva sanjao sam o utjelovljivanju ove slike na pozornici.

Pa, dobro je odustati od ove uloge ako mi dopuste da igram Khlestakova, - pokazao je Gena velikodušnost.

- ... A meni - Osipa, - Dima mu nije popustio u velikodušnosti.

Želim biti Strawberry ili Guverner, - rekao je Vova.

Ne, ja ću biti guverner ”, viknu Alik i Borya u glas. - Ili Khlestakov, -

Hoćete li uspjeti rasporediti uloge tako da izvođači budu zadovoljni?

Rasprava. Oslikajmo mlade glumce krugovima u gornjem redu: A - Alik, B - Boris, C - Vova, G - Gena, D - Dima, a uloge koje će igrati su krugovi drugog reda (1 - Lyapkin - Tyapkin, 2 - Khlestakov, 3 - Osip, 4 - Jagoda, 5 - Guverner). Zatim izvlačimo segmente od svakog sudionika, t.j. rebra, na uloge koje bi želio igrati. Dobit ćemo graf s deset vrhova i deset bridova (slika 3)

Da biste riješili problem, trebate odabrati pet bridova od deset koji nemaju zajedničke vrhove. Ovo je lako učiniti. Dovoljno je primijetiti da jedan brid vodi do vrhova 3 i 4, od vrhova D i B, redom. To znači da bi Osipa (vrhunac 3) trebao glumiti Dima (tko drugi?), a Jagoda - Vova. Vertex 1 - Lyapkin - Tyapkin - spojen je bridovima s G i D. Rub 1 - D odustaje, budući da je Dima već zauzet, ostaje 1 - G, Lyapkin - Tyapkin bi trebao igrati Gena. Ostaje povezati vrhove A i B s vrhovima 2 i 5, što odgovara ulogama Khlestakova i Gorodnichyja. To se može učiniti na dva načina: ili odaberite rub A -5 i B - 2, ili rub A -2 i B -5. U prvom slučaju Alik će igrati guvernera, a Borya - Khlestakov, u drugom slučaju, obrnuto. Kao što grafikon pokazuje, problem nema drugih rješenja.

Isti graf će se dobiti rješavanjem sljedećeg problema:

Zadatak. Mrzovoljni susjedi. Stanovnici pet kuća su se međusobno posvađali i, kako se ne bi sastajali na bunarima, odlučili su ih podijeliti (bunare) kako bi vlasnik svake kuće išao do “svog” bunara “svojim” putem. Hoće li im to uspjeti?

postavlja se pitanje:jesu li grafovi doista bili potrebni u analiziranim problemima? Nije li moguće doći do rješenja na čisto logičan način? Da, možete. No, grafovi su razjasnili uvjete, pojednostavili rješenje i otkrili sličnost problema, pretvarajući dva problema u jedan, a to nije tako malo. Sada zamislite probleme s grafovima sa 100 ili više vrhova. Ali to su zadaci koje moderni inženjeri i ekonomisti moraju riješiti. Ovdje ne možete bez grafikona.

III. Eulerovi grafovi.

Teorija grafova je relativno mlada znanost: u vrijeme Newtona takva znanost još nije postojala, iako su bila u upotrebi “genealoška stabla”, koja su varijante grafova. Prvi rad o teoriji grafova pripada Leonardu Euleru, a pojavio se 1736. godine u publikacijama Petrogradske akademije znanosti. Ovaj rad je započeo razmatranjem sljedećeg problema:

a) Problem mostova u Konigsbergu. Grad Konigsberg (danas Kalinjingrad) nalazi se na obalama i dva otoka rijeke Pregel (Pregolya) Različiti dijelovi grada bili su povezani sa sedam mostova, kao što je prikazano na slici. Nedjeljom se građani šetaju gradom. Je li moguće izabrati takvu rutu kako bi se svakim mostom išlo samo jednom, a zatim se vraćalo na početnu točku puta?
Prije razmatranja rješenja ovog problema uvodimo koncept “ Eulerovi grafovi.

Pokušajmo zaokružiti graf prikazan na slici 4 u jednom potezu, odnosno bez podizanja olovke s lista papira i bez prelaska preko istog dijela linije više puta.

Ova figura, tako jednostavna izgleda, ima zanimljivu značajku. Ako krenemo s vrha B, onda ćemo sigurno uspjeti. A što će se dogoditi ako se krenemo kretati s vrha A? Lako je osigurati da u ovom slučaju ne uspijevamo zaokružiti crtu: uvijek ćemo imati rubove koji nisu prijeđeni, a do kojih više nije moguće doći.

Na sl. 5 prikazuje grafikon koji vjerojatno možete nacrtati jednim potezom. To je zvijezda. Ispada da, iako izgleda mnogo složenije od prethodnog grafa, možete ga zaokružiti počevši od bilo kojeg vrha.

Grafikoni prikazani na slici 6 također se mogu nacrtati jednim potezom olovke.

Sada pokušajte ući u trag u jednom potezu graf prikazan na slici 7

Niste uspjeli to učiniti! Zašto? Ne možete pronaći vrh koji tražite? Ne! Ovo nije poanta. Općenito, ovaj se grafikon ne može pratiti jednim potezom olovke.

Provedimo razmišljanje koje će nas u to uvjeriti. Razmotrimo čvor A. Iz njega izlaze tri vrha. Počnimo crtati graf iz ovog vrha. Da bismo prošli duž svakog od ovih bridova, moramo ostaviti vrh A duž jednog od njih, u nekom trenutku se moramo vratiti na njega duž drugog i izaći uz treći. Ali više nećemo moći ući! To znači da ako krenemo crtati iz vrha A, tada nećemo moći završiti u njemu.

Pretpostavimo sada da vrh A nije početak. Zatim, u procesu crtanja, moramo ući u njega uz jedan od rubova, izaći uz drugi i ponovno se vratiti uz treći. A budući da iz toga ne možemo izaći, onda vrh A u ovom slučaju mora biti kraj.

Dakle, vrh A mora biti ili početak ili krajnji čvor crtanja.

Ali isto se može reći i za ostala tri vrha našeg grafa. Ali uostalom, u početnom tjemenu crtanja može biti samo jedan vrh, a konačni vrh također može biti samo jedan vrh! To znači da je nemoguće nacrtati ovaj graf jednim potezom.

Zove se graf koji se može nacrtati bez podizanja olovke s papira Euler (sl. 6).

Ovi grafovi su nazvani po znanstveniku Leonardu Euleru.

Pravilnost 1. (slijedi iz teorema koji smo razmatrali).

Nije moguće nacrtati graf s neparnim brojem neparnih vrhova.
Uzorak 2.

Ako su svi vrhovi grafa parni, onda bez podizanja olovke s papira ("jednom potezom"), crtajući ovaj graf duž svakog ruba samo jednom. Pokret može započeti iz bilo kojeg vrha i završiti na istom vrhu.
Uzorak 3.

Graf sa samo dva neparna vrha može se nacrtati bez podizanja olovke s papira, dok kretanje mora početi od jednog od tih neparnih vrhova i završiti u drugom od njih.
Obrazac 4.

Graf s više od dva neparna vrha ne može se nacrtati jednim potezom.
Lik (graf) koji se može nacrtati bez podizanja olovke s papira naziva se unikurzalan.

Graf se zove povezan, ako se bilo koja dva njegova vrha mogu povezati putem, odnosno nizom bridova, od kojih svaki sljedeći počinje na kraju prethodnog.

Graf se zove nesuvisla, ako ovaj uvjet nije ispunjen.

sl. 7 sl. 8

Slika 7 očito prikazuje nepovezani graf. Ako se, na primjer, povuče brid između vrhova D i E na slici, tada će graf postati povezan. (sl. 8)

Takav rub u teoriji grafova (nakon uklanjanja kojeg graf iz povezanog prelazi u nepovezani) naziva se most.

Primjeri mostova na slici 7 mogu biti bridovi DE, A3, VZh itd., od kojih bi svaki povezivao vrhove "izoliranih" dijelova grafa. (Slika 8.)

Nepovezani graf sastoji se od nekoliko "komada". Ti se "komadi" zovu komponente povezivanja graf. Svaka povezana komponenta je, naravno, povezani graf. Imajte na umu da povezani graf ima jednu povezanu komponentu.
TEOREMA.

Graf je Euler ako i samo ako je povezan i ima najviše dva neparna vrha.

Dokaz:

Crtanjem grafa za svaki vrh, osim za početak i kraj, ući ćemo isti broj puta koliko smo ga napustili. Stoga stupnjevi svih vrhova moraju biti parni, osim dva, što znači da Eulerov graf ima najviše dva neparna vrha.

Vratimo se sada problemu konigsberških mostova.

Rasprava o zadatku ... Označimo različite dijelove grada slovima A, B, C, D, a mostove - slovima a, b, c, d, e, f, g - mostove koji povezuju odgovarajuće dijelove grada. U ovom zadatku postoje samo prijelazi preko mostova: prelazeći bilo koji most, uvijek dolazimo iz jednog dijela grada u drugi, i obrnuto, idući iz jednog dijela grada u drugi, sigurno ćemo ići preko mosta. Stoga ćemo plan grada prikazati u obliku grafa čiji vrhovi A, B, C, D (slika 8) predstavljaju zasebne dijelove grada, a rubovi a, b, c, d, e , f, g su mostovi koji povezuju pripadajuće dijelove grada ... Često je prikladnije prikazati rubove ne ravnim segmentima, već zakrivljenim - "lukovima".

Ako postoji ruta koja zadovoljava uvjet problema, tada bi postojao zatvoreni kontinuirani obilazak ovog grafa, prolazeći jednom duž svakog ruba. Drugim riječima, ovaj graf treba nacrtati jednim potezom. Ali to je nemoguće - bez obzira koji vrh odaberemo kao početni, morat ćemo proći kroz ostale vrhove, a istovremeno i svaki “dolazni” rub (most kroz koji smo ušli u ovaj dio city) odgovarat će “odlaznom” rubu, mostu koji koristimo i zatim njime napuštamo ovaj dio grada): broj bridova koji ulaze u svaki vrh bit će jednak broju bridova koji ga napuštaju, tj. ukupan broj bridova koji konvergiraju na svakom vrhu mora biti paran. Naš graf ne zadovoljava ovaj uvjet, pa stoga tražena ruta ne postoji.

Tekst rada postavljen je bez slika i formula.
Puna verzija rad je dostupan u kartici "Datoteke rada" u PDF formatu

UVOD

"U matematici ne treba pamtiti formule, već proces razmišljanja..."

E. I. Ignatiev

Teorija grafova je trenutno grana matematike koja se intenzivno razvija. To je zbog činjenice da su mnogi objekti i situacije opisani u obliku grafskih modela, što je vrlo važno za normalno funkcioniranje društvenog života. Upravo taj čimbenik određuje relevantnost njihovog detaljnijeg proučavanja. Stoga je tema ovog rada prilično relevantna.

Cilj istraživački rad: saznati značajke primjene teorije grafova u različitim područjima znanja i rješavanju logičkih problema.

Cilj je identificirao sljedeće zadaci:

upoznati povijest teorije grafova;

proučavati osnovne pojmove teorije grafova i osnovne karakteristike grafova;

pokazati praktičnu primjenu teorije grafova u različitim područjima znanja;

razmotrite načine rješavanja problema pomoću grafova i kreirajte vlastite probleme.

Objekt istraživanje: područje ljudske djelatnosti za primjenu metode grafa.

Stvar istraživanje: dio matematike "Teorija grafova".

Hipoteza. Pretpostavljamo da proučavanje teorije grafova može pomoći studentima u rješavanju logičkih zadataka iz matematike, što će odrediti njihove daljnje interese.

Metode istraživački rad:

Tijekom istraživanja koristili smo metode kao što su:

1) Rad s raznim izvorima informacija.

2) Opis, prikupljanje, sistematizacija građe.

3) Promatranje, analiza i usporedba.

4) Sastavljanje zadataka.

Teorijski i praktični značaj Ovaj rad određen je činjenicom da se rezultati mogu koristiti u informatici, matematici, geometriji, crtanju i razrednim satima, kao i za širok krug čitatelja zainteresiranih za ovu tematiku. Istraživački rad ima izraženu praktičnu usmjerenost, budući da u radu autor iznosi brojne primjere korištenja grafova u mnogim područjima znanja, te sastavio vlastite zadatke. Ovaj materijal se može koristiti u izbornoj nastavi matematike.

POGLAVLJE I. TEORIJSKI PREGLED MATERIJALA NA TEMU ISTRAŽIVANJA

1. Teorija grafova. Osnovni koncepti

U matematici se "graf" može prikazati kao slika, a to je niz točaka povezanih linijama. "Grof" dolazi od latinske riječi "grapio" - pišem, poput poznate plemićke titule.

U matematici se definicija grafa daje na sljedeći način:

Pojam "graf" u matematici definiran je na sljedeći način:

Grafikon je konačan skup točaka - vrhovima, koji se mogu povezati linijama - rebra .

Primjeri grafova mogu biti crteži poligona, električnih krugova, shematski prikaz zračnih prijevoznika, podzemnih željeznica, cesta itd. Obiteljsko stablo je također graf, gdje članovi roda služe kao vrhovi, a obiteljske veze djeluju kao rubovi grafa.

Riža. jedan Primjeri grafova

Broj bridova koji pripada jednom vrhu naziva se stupanj vrha grafa . Ako je stupanj vrha neparan, vrh se naziva - neparan ... Ako je stupanj vrha paran, tada se vrh naziva čak.

Riža. 2 Vrh grafikona

Nulti graf je graf koji se sastoji samo od izoliranih vrhova koji nisu povezani bridovima.

Potpuni graf je graf čiji je svaki par vrhova spojen bridom. N-kut u kojem su nacrtane sve dijagonale može poslužiti kao primjer cjelovitog grafa.

Ako u grafu odaberemo put gdje se poklapaju početna i krajnja točka, tada se takav put naziva ciklusni graf . Ako se prolaz kroz svaki vrh grafa ne dogodi više od jednom, tada ciklus pozvao jednostavan .

Ako su svaka dva vrha u grafu povezana bridom, onda je to povezani graf. Graf se zove nepovezano ako ima barem jedan par nepovezanih vrhova.

Ako je graf povezan, ali ne sadrži cikluse, onda se takav graf naziva stablo .

1. Karakteristike grafa

Put grafa je niz u kojem se svaka dva susjedna brida s jednim zajedničkim vrhom susreću samo jednom.

Duljina najkraćeg lanca vrhova a a b se zove udaljenosti između vrhova a i b.

Vertex a pozvao centar graf ako je udaljenost između vrha a a bilo koji drugi vrh je najmanji mogući. Postoji takva udaljenost radius graf.

Naziva se najveća moguća udaljenost između bilo koja dva vrha grafa promjer graf.

Bojanje grafova i primjena.

Ako pažljivo pogledate geografsku kartu, možete vidjeti željeznice ili autoceste, što su grafikoni. Osim toga, postoji graf na katri, koji se sastoji od granica između zemalja (okruga, regija).

Godine 1852. engleski student Francis Guthrie dobio je zadatak da naslika kartu Velike Britanije, istaknuvši svaku županiju drugom bojom. Zbog malog izbora boja, Guthrie ih je ponovno upotrijebio. Boje je odabrao tako da su one županije koje imaju zajednički dio granice bile nužno obojane različitim bojama. Postavilo se pitanje koja je najmanja količina boja potrebna za bojanje različitih karata. Francis Guthrie je sugerirao, iako nije mogao dokazati, da će četiri boje biti dovoljne. O ovom problemu se žustro raspravljalo u studentskim krugovima, ali je kasnije zaboravljeno.

"Problem četiri boje" izazivao je sve veće zanimanje, ali ga nikada nisu riješili čak ni vrhunski matematičari. Godine 1890. engleski matematičar Percy Hewood dokazao je da bi pet boja bilo dovoljno za obojenje bilo koje karte. I tek 1968. uspjeli su dokazati da bi 4 boje bile dovoljne za obojenje karte na kojoj je prikazano manje od četrdeset zemalja.

Godine 1976. ovaj problem su pomoću računala riješila dva američka matematičara Kenneth Appel i Wolfgang Hacken. Kako bismo to riješili, sve su karte podijeljene u 2000 vrsta. Za računalo je napravljen program koji je ispitivao sve vrste kako bi se identificirale takve karte za bojanje kojih četiri boje ne bi bile dovoljne. Računalo nije moglo istražiti samo tri vrste karata, pa su ih matematičari sami proučavali. Kao rezultat toga, ustanovljeno je da bi 4 boje bile dovoljne za bojanje svih 2000 vrsta kartica. Najavio je rješenje problema četiri boje. Na današnji je dan pošta na sveučilištu, gdje su radili Appel i Haken, otisnula sve marke s riječima: "Četiri boje su dovoljne".

Problem četiri boje možete zamisliti na malo drugačiji način.

Da biste to učinili, razmislite o proizvoljnoj karti koja je predstavlja u obliku grafa: glavni gradovi država su vrhovi grafa, a rubovi grafa povezuju one vrhove (glavne strane), čija stanja imaju zajednička granica... Za dobivanje takvog grafa formulira se sljedeći problem – potrebno je graf obojiti s četiri boje tako da se vrhovi koji imaju zajednički rub obojaju različitim bojama.

Euler i Hamiltonov graf

Godine 1859. engleski matematičar William Hamilton objavio je slagalicu - drveni dodekaedar (dodekaedar), čiji je dvadeset vrhova bilo označeno karanfilima. Svaki vrh je dobio ime po jednom od najvećih gradova na svijetu - Kantonu, Delhiju, Bruxellesu itd. Problem je bio pronaći zatvoreni put koji ide uz rubove poliedra, nakon što je svaki vrh posjetio samo jednom. Za označavanje staze korištena je vrpca, koja je bila pričvršćena za karanfile.

Hamiltonov ciklus je graf čija je putanja jednostavan ciklus koji jednom prolazi kroz sve vrhove grafa.

Grad Kalinjingrad (bivši Konigsberg) nalazi se na rijeci Pregel. Rijeka je ispirala dva otoka, koji su međusobno i s obalama bili povezani mostovima. Starih mostova više nema. Sjećanje na njih ostalo je samo na karti grada.

Jednom je stanovnik grada upitao svog prijatelja je li moguće prijeći sve mostove, posjetiti svaki samo jednom i vratiti se na mjesto odakle je krenula šetnja. Ovaj problem je zainteresirao mnoge građane, ali ga nitko nije uspio riješiti. Ovo pitanje izazvalo je interes znanstvenika iz mnogih zemalja. Rješenje problema dobio je matematičar Leonard Euler. Osim toga, formulirao je opći pristup rješavanju takvih problema. Da bi to učinio, pretvorio je kartu u graf. Zemljište je postalo vrh ovog grafa, a mostovi koji ga povezuju postali su rubovi.

Rješavajući problem koenigsberških mostova, Euler je uspio formulirati svojstva grafova.

Moguće je nacrtati graf, počevši od jednog vrha i završavajući na istom vrhu, jednim potezom (bez crtanja dva puta duž iste linije i bez podizanja olovke s papira), ako su svi vrhovi grafa parni.

Ako postoji graf s dva neparna vrha, onda se i njegovi vrhovi mogu povezati jednim potezom. Da biste to učinili, morate započeti s jednim, a završiti na drugom bilo kojem neparnom vrhu.

Ako postoji graf s više od dva neparna vrha, tada se graf ne može nacrtati jednim potezom.

Ako ova svojstva primijenimo na problem mostova, onda možemo vidjeti da su svi vrhovi istraživanog grafa neparni, što znači da se ovaj graf ne može povezati jednim potezom, t.j. nemoguće je jednom prijeći sve mostove i završiti put na mjestu gdje je započet.

Ako graf ima ciklus (ne nužno jednostavan) koji sadrži sve rubove grafa jednom, tada se takav ciklus naziva Eulerov ciklus . Eulerov lanac (put, ciklus, kontura) je lanac (put, ciklus, kontura) koji sadrži sve bridove (lukove) grafa jednom.

POGLAVLJE II. OPIS ISTRAŽIVANJA I NJEGOVIH REZULTATA

2.1. Faze istraživanja

Kako bi se testirala hipoteza, studija je uključivala tri faze (tablica 1):

Faze istraživanja

Stol 1.

		Korištene metode
Teorijsko proučavanje problema	Proučavati i analizirati spoznajnu i znanstvenu literaturu.	 neovisna refleksija;  proučavanje izvora informacija;  traženje potrebne literature.
Praktično istraživanje problema	Razmotriti i analizirati područja praktične primjene grafova;	 promatranje;  analiza;  usporedba;  ispitivanje.
3. faza. Praktična upotreba rezultata	Sažmi naučene informacije;	 sistematizacija;  izvješće (usmeno, pismeno, s demonstracijom materijala)	rujna 2017

2.2. Područja praktične primjene grafova

Grafikoni i informacije

Teorija informacija uvelike koristi svojstva binarnih stabala.

Na primjer, ako trebate kodirati određeni broj poruka u obliku određenih nizova nula i jedinica različite duljine. Kod se smatra najboljim, za danu vjerojatnost kodnih riječi, ako je prosječna duljina riječi najmanja u usporedbi s drugim distribucijama vjerojatnosti. Kako bi riješio takav problem, Huffman je predložio algoritam u kojem je kod predstavljen grafom stabla u okviru teorije pretraživanja. Za svaki vrh predlaže se pitanje čiji odgovor može biti ili "da" ili "ne" - što odgovara dvama bridima koji izlaze iz vrha. Izgradnja takvog stabla je završena nakon što se utvrdi što je bilo potrebno. Ovo se može primijeniti u intervjuiranju više osoba, kada odgovor na prethodno pitanje nije poznat unaprijed, plan intervjua se prikazuje u obliku binarnog stabla.

Grafovi i kemija

Već je A. Cayley razmatrao problem mogućih struktura zasićenih (ili zasićenih) ugljikovodika čije su molekule dane formulom:

CnH 2n + 2

Svi atomi ugljikovodika su 4-valentni, svi atomi vodika su 1-valentni. Strukturne formule najjednostavniji ugljikovodici prikazani su na slici.

Svaka molekula zasićenog ugljikovodika može se predstaviti kao stablo. Kada se uklone svi atomi vodika, preostali atomi ugljikovodika tvore stablo s vrhovima ne većim od četiri stupnja. To znači da je broj mogućih traženih struktura (homologa dane tvari) jednak broju stabala čiji stupanj vrhova nije veći od 4. Taj se problem svodi na problem nabrajanja stabala određene vrste. . D. Polya je razmatrao ovaj problem i njegove generalizacije.

Grafovi i biologija

Proces razmnožavanja bakterija jedna je od varijanti procesa grananja koja se nalazi u biološkoj teoriji. Neka svaka bakterija, nakon određenog vremena, ili umre ili se podijeli na dvije. Dakle, za jednu bakteriju dobivamo binarno stablo razmnožavanja njenog potomstva. Pitanje problema je sljedeće, koliko slučajeva sadrži k potomci u n-oj generaciji jedne bakterije? Taj se omjer u biologiji naziva Galton-Watsonov proces, što ukazuje na potreban broj potrebnih slučajeva.

Grafovi i fizika

Zamoran i zamoran zadatak za svakog radioamatera je izrada tiskanih sklopova (dielektrična ploča - izolacijski materijal i urezane staze u obliku metalnih traka). Križanje kolosijeka događa se samo na određenim točkama (mjesta gdje se postavljaju triode, otpornici, diode itd.) prema određenim pravilima. Kao rezultat toga, znanstvenik se suočava sa zadatkom crtanja ravnog grafa s vrhovima

Dakle, sve navedeno potvrđuje praktičnu vrijednost grafova.

Internet matematika

Internet je svjetski sustav međusobno povezanih računalnih mreža za pohranu i prijenos informacija.

Internet se može predstaviti kao graf, gdje su vrhovi grafa internetske stranice, a rubovi poveznice (hiperveze) s jedne stranice na drugu.

Web graf (Internet), koji ima milijarde vrhova i bridova, stalno se mijenja - stranice se spontano dodaju i nestaju, linkovi nestaju i dodaju. Međutim, internet ima matematičku strukturu, poštuje teoriju grafova i ima nekoliko "stabilnih" svojstava.

Web graf je rijedak. Sadrži samo nekoliko puta više bridova od vrhova.

Unatoč rijetkosti, internet je vrlo mali. S jedne stranice na drugu na poveznicama možete prijeći u 5 - 6 klikova (poznata teorija "šest rukovanja").

Kao što znamo, stupanj grafa je broj bridova kojima pripada vrh. Stupnjevi vrhova web grafa raspoređeni su prema određenom zakonu: udio stranica (vrhova) s velika količina veze (rubovi) su male, a stranice s malo poveznica su velike. Matematički se može napisati ovako:

gdje je udio vrhova određenog stupnja, je stupanj vrha, je konstanta neovisna o broju vrhova u web grafu, t.j. ne mijenja se u procesu dodavanja ili uklanjanja stranica (vrhova).

Ovaj zakon moći je univerzalan za složene mreže - od bioloških do međubankarskih.

Internet je u cjelini otporan na nasumične napade na web stranice.

Budući da se uništavanje i stvaranje stranica događa neovisno i s istom vjerojatnošću, onda web graf, s vjerojatnošću bliskom 1, zadržava svoj integritet i nije uništen.

Za proučavanje Interneta potrebno je izgraditi model slučajnog grafa. Ovaj model bi trebao imati svojstva pravog Interneta i ne bi trebao biti pretjerano složen.

Ovaj zadatak još nije u potpunosti riješen! Rješavanje ovog problema – izgradnja visokokvalitetnog modela interneta – omogućit će razvoj novih alata za poboljšanje pronalaženja informacija, otkrivanja neželjene pošte i širenja informacija.

Izgradnja bioloških i ekonomskih modela započela je mnogo prije nego što se pojavio problem izgradnje matematičkog modela interneta. Međutim, napredak u razvoju i proučavanju Interneta omogućio je da se odgovori na mnoga pitanja o svim ovim modelima.

Matematiku interneta traže mnogi stručnjaci: biolozi (predviđanje rasta bakterijskih populacija), financijeri (rizici od kriza) itd. Proučavanje takvih sustava jedan je od središnjih odjeljaka primijenjene matematike i informatike.

Murmansk uz pomoć grafa.

Kada čovjek dođe u novi grad za njega, u pravilu mu je prva želja posjetiti glavne atrakcije. No, u isto vrijeme, vremenska margina je često ograničena, au slučaju poslovnog putovanja vrlo je mala. Stoga je potrebno unaprijed planirati razgledavanje. A grafovi će biti od velike pomoći u izgradnji rute!

Kao primjer, razmotrite tipičan slučaj dolaska u Murmansk iz zračne luke po prvi put. Planirano je posjetiti sljedeće atrakcije:

1. Morska pravoslavna crkva Spasa na vodama;

2. Katedrala svetog Nikole;

3. Oceanarij;

4. Spomenik mačku Semjonu;

5. Nuklearni ledolomac Lenjin;

6. Park svjetla Murmansk;

7. Park dolina udobnosti;

8. Kolski most;

9. Muzej povijesti Murmanskog brodarstva;

10. Trg pet uglova;

11. Morska trgovačka luka

Prvo ćemo postaviti ta mjesta na kartu i dobiti vizualni prikaz lokacije i udaljenosti između atrakcija. Cestovna mreža je dobro razvijena, a kretanje automobilom neće biti teško.

Znamenitosti na karti (lijevo) i rezultirajući grafikon (desno) prikazani su na odgovarajućoj slici u DODATKU 1. Tako će pridošlica najprije proći u blizini mosta Kola (i, po želji, može ga prijeći naprijed-natrag); zatim će se odmoriti u parku Ogni Murmansk i Dolini utjehe i otići dalje. Kao rezultat toga, optimalna ruta bit će:

Pomoću grafa također možete vizualizirati shemu ankete. Primjeri su prikazani u DODATKU №2. Ovisno o datim odgovorima, ispitaniku se postavljaju različita pitanja. Na primjer, ako ispitanik u sociološkom istraživanju br. 1 smatra matematiku najvažnijom od znanosti, bit će upitan osjeća li se samopouzdano u nastavi fizike; ako misli drugačije, drugo pitanje će se ticati relevantnosti humanističkih znanosti. Vrhovi takvog grafa su pitanja, a bridovi su opcije odgovora.

2.3. Primjena teorije grafova u rješavanju problema

Teorija grafova koristi se za rješavanje problema iz brojnih predmetnih područja: matematike, biologije, informatike. Proučavali smo princip rješavanja problema korištenjem teorije grafova i izradili vlastite probleme na temu istraživanja.

Problem broj 1.

Pet kolega iz razreda, na sastanku bivših studenata, rukovalo se. Koliko je rukovanja napravljeno?

Rješenje: Označimo kolege iz razreda kao vrhove grafa. Spojimo svaki vrh linijama, s četiri druga vrha. Dobivamo 10 redaka, ovo je stisak ruke.

Odgovor: 10 rukovanja (svaka linija znači jedno rukovanje).

Problem broj 2.

Moja baka ima 8 stabala u selu u blizini kuće: topola, hrast, javor, jabuka, ariš, breza, planinski jasen i bor. Rowan je viši od ariša, jabuka je viša od javora, hrast je niži od breze, ali viši od bora, bor je viši od ariša, breza je niži od topole, a ariš je viši od jabuke. Kojim redoslijedom će stabla biti raspoređena po visini od najvišeg do najnižeg.

Riješenje:

Stabla su vrhovi grafa. Označimo ih prvim slovom u krugu. Nacrtajte strelice s niskog stabla na više. Kaže se da je jareb viši od ariša, pa strijelu stavimo od ariša do ariša, breza je niža od topole, zatim stavimo strijelu od topole do breze itd. Dobivamo graf gdje se vidi da je najniže stablo javor, zatim jabuka, ariš, rov, bor, hrast, breza i topola.

Odgovor: javor, jabuka, ariš, rowan, bor, hrast, breza i topola.

Problem broj 3.

Mama ima 2 omotnice: običnu i zračnu te 3 marke: kvadratnu, pravokutnu i trokutastu. Na koliko načina mama može odabrati omotnicu i marku za slanje pisma tati?

Odgovor: 6 načina

Problem broj 4.

Između naselja Izgrađene su ceste A, B, C, D, E. Potrebno je odrediti duljinu najkraćeg puta između točaka A i E. Možete se kretati samo cestama čija je duljina prikazana na slici.

Problem broj 5.

Tri kolege iz razreda - Maxim, Kirill i Vova odlučili su se baviti sportom i odabrani su za sportske sekcije. Poznato je da se 1 dječak prijavio za košarkašku sekciju, a trojica su željela igrati hokej. Maxim je bio na audiciji za samo 1 odjeljak, Kirill je odabran za sve tri sekcije, a Vova u 2. Tko je od dječaka odabran za koju sportsku sekciju?

Rješenje: Za rješavanje problema koristimo grafove

Košarkaš Maksim

Nogomet Kirill

Hokejaški Vova

Od do košarka postoji samo jedna strelica, tada je Cyril odveden na sjednicu košarka... Tada Kirill neće igrati hokej, što znači da u hokej dio je odabrao Maxim, koji je bio na audiciji samo za ovu sekciju, zatim će Vova nogometaš.

Problem broj 6.

Zbog bolesti nekih nastavnika, ravnatelj škole, dužan je izraditi isječak školskog rasporeda za najmanje jedan dan, uzimajući u obzir sljedeće okolnosti:

1. Učitelj OBZH pristaje održati samo zadnji sat;

2. Učitelj geografije može održati ili drugi ili treći sat;

3. Matematičar je spreman održati ili samo prvu ili samo drugu lekciju;

4. Učitelj fizike može držati ili prvi, ili drugi, ili treći sat, ali samo u jednom razredu.

Kakav raspored može sastaviti ravnatelj škole kako bi zadovoljio sve učitelje?

Rješenje: Ovaj se problem može riješiti razvrstavanjem svih mogućih opcija, ali je lakše ako nacrtate graf.

1.1) fizika 2.1) matematika 3.1) matematika

2) matematika 2) fizika 2) geografija

3) geografija 3) geografija 3) fizika

4) OBZH 4) OBZH 4) OBZH

Zaključak

U ovom istraživačkom radu detaljno je proučavana teorija grafova, dokazana hipoteza da proučavanje grafova može pomoći u rješavanju logičkih problema, osim toga, razmatrana je teorija grafova u različitim područjima znanosti te je sastavljeno 7 problema.

Korištenje grafova u poučavanju učenika pronalaženju rješenja problema omogućuje nam poboljšanje grafičkih vještina učenika i povezivanje zaključivanja na posebnom jeziku konačnog skupa točaka, od kojih su neke povezane linijama. Sve to pridonosi radu učenja učenika razmišljanju.

Učinkovitost odgojno-obrazovnih aktivnosti za razvoj mišljenja uvelike ovisi o stupnju kreativne aktivnosti učenika u rješavanju matematičkih zadataka. Posljedično, potrebni su matematički zadaci i vježbe koje bi aktivirale mentalnu aktivnost školaraca.

Primjena zadataka i korištenje elemenata teorije grafova u izvannastavnoj nastavi u školi upravo je usmjerena na poticanje mentalne aktivnosti učenika. Vjerujemo da praktični materijal iz našeg istraživanja može biti od koristi u izbornim predmetima iz matematike.

Time je cilj istraživačkog rada postignut, zadaci riješeni. U budućnosti planiramo nastaviti proučavati teoriju grafova i razvijati vlastite rute, na primjer, koristeći graf za izradu izletničke rute za školski autobus ZATO Aleksandrovsk do muzeja i nezaboravnih mjesta u Murmansku.

POPIS KORIŠTENE LITERATURE

Berezina L. Yu. "Grafovi i njihova primjena" - M .: "Obrazovanje", 1979.

Gardner M. "Matematička dokolica", M. "Mir", 1972

Gardner M. "Matematičke zagonetke i zabava", M. "Mir", 1971.

Gorbačov A. "Zbirka olimpijskih zadataka" - M. MTsNMO, 2005.

Zykov A.A. Osnove teorije grafova. - M .: "Sveučilišna knjiga", 2004. - Str. 664

Kasatkin V. N. "Neobični matematički problemi", Kijev, "Radianska škola", 1987.

Matematička komponenta / Urednici-sastavljači N.N. Andreev, S.P. Konovalov, N.M. Panyushkin. - M .: Fond "Matematičke etide" 2015. - 151 str.

Melnikov OI "Zabavni problemi u teoriji grafova", Mn. TetraSystems, 2001. (monografija).

Melnikov O.I. Neznam u zemlji grofova: Vodič za studente. Ed. 3., stereotipno. M .: KomKniga, 2007 .-- 160 str.

Olekhnik S. N., Nesterenko Yu. V., Potapov M. K. "Drevni zabavni zadaci", M. "Znanost", 1988.

Ore O. "Grafovi i njihove primjene", M. "Mir", 1965

Harari F. Teorija grafova / Preveo s engleskog. i predgovor. V.P. Kozyrev. Ed. G.P. Gavrilova. Ed. 2. - M .: Uredništvo URSS, 2003 .-- 296 str.

DODATAK 1

Izrada optimalne rute za obilazak glavnih atrakcija

Murmansk uz pomoć grafa.

Optimalna ruta će biti:

8. Kolski most 6. Park svjetla Murmansk 7. Park Dolina ugode 2. Katedrala svetog Nikole 10. Trg pet uglova 5. Nuklearni ledolomac Lenin9. Muzej povijesti Murmanskog brodarstva 11. Morska trgovačka luka1. Pravoslavna morska pravoslavna crkva Spasa na Vodama 4. Spomenik mačku Semjonu 3. Oceanarij.

VODIČ PO ZNAMENITOSTI MURMANSKA

DODATAK #2

Sociološka istraživanja br. 1, 2

Teorija grafova koristi se, primjerice, u geografskim informacijskim sustavima (GIS). Postojeće ili novoprojektirane kuće, objekti, kvartovi itd. smatraju se vrhovima, a ceste, inženjerske mreže, dalekovodi itd., koji ih povezuju, smatraju se rubovima. Korištenje različitih proračuna izvedenih na takvom grafu omogućuje, primjerice, pronalaženje najkraćeg obilaznog puta ili najbliže trgovine te planiranje optimalne rute.

Teorija grafova sadrži veliki broj neriješenih problema i još nedokazanih hipoteza.

Glavna područja primjene teorije grafova:

U kemiji (za opisivanje struktura, putova složenih reakcija, fazno pravilo se također može tumačiti kao problem u teoriji grafova); računalna kemija je relativno mlado područje kemije koje se temelji na primjeni teorije grafova. Teorija grafova je matematički temelj kemoinformatike. Teorija grafova omogućuje vam da točno odredite broj teoretski mogućih izomera u ugljikovodicima i drugim organskim spojevima;

U informatici i programiranju (graf-dijagram algoritma);

U komunikacijskim i transportnim sustavima. Posebno za usmjeravanje podataka na Internetu;

U ekonomiji;

U logistici;

U strujnim krugovima (topologija međusobnog povezivanja elemenata na tiskanoj pločici ili mikrosklopu je graf ili hipergraf).

Dodijelite posebnu vrstu grafikona, stablo.Drvo je povezani aciklički graf. Povezivost znači prisutnost putova između bilo kojeg para vrhova, acikličnost znači odsutnost ciklusa i činjenicu da postoji samo jedan put između parova vrhova. Na Slika 1.3 predstavio binarno stablo.

Binarno stablo- struktura podataka nalik stablu u kojoj svaki čvor ima najviše dva potomci(djeca). Obično se prvi zove roditeljski čvor a djeca se zovu lijevo i pravi nasljednici.

Matrični prikaz grafova. Matrica incidenata.

Razvoj algoritamskih pristupa analizi svojstava grafova zahtijeva određene metode opisivanja grafova, koje su prikladnije za praktična izračunavanja, uključujući korištenje računala. Pogledajmo tri najčešća načina predstavljanja grafova.

Pretpostavimo da su svi vrhovi i svi bridovi neusmjerenog grafa ili svi vrhovi i svi lukovi (uključujući petlje) usmjerenog grafa numerirani počevši od jedan. Graf (neusmjeren ili usmjeren) može se predstaviti kao matrica tipa, gdje je broj vrhova, a broj bridova (ili lukova). Za neusmjereni graf, elementi ove matrice navedeni su na sljedeći način:

Za usmjereni graf, elementi matrice su specificirani na sljedeći način:

Ovako definirana matrica tipa naziva se matrica incidenata.

Primjer dobivanja matrice incidenata. Za grafikon ispod ( Riža. 2.1 aSlika 2.1 b).

Slika 2.1 a Sl. 2.1 b

Matrica susjedstva.

Unatoč činjenici da prikaz grafa u obliku matrice incidenata igra vrlo važnu ulogu u teorijskim istraživanjima, u praksi je ova metoda vrlo neučinkovita. Prije svega, postoje samo dva različita od nula elementa u matrici u svakom stupcu, što ovaj način predstavljanja grafa čini neekonomičnim za veliki broj vrhova. Osim toga, rješavanje praktičnih problema pomoću Incident Matrixa je vrlo naporno.

Procijenimo, na primjer, vrijeme utrošeno na rješavanje tako jednostavnog problema u usmjerenom grafu pomoću matrice incidencije: za dani vrh pronađite njegovo "okruženje" - skup nasljednika i skup prethodnika vrha, t.j. skup svih vrhova iz kojih je izravno dosegljiv i skup svih vrhova iz kojih je izravno dosegljiv.

Da biste riješili ovaj problem na matrici incidencije usmjerenog grafa, morate hodati duž linije s brojem dok se ne pojavi element različit od nule (+1 ili –1). Ako se nađe +1, u odgovarajućem stupcu potrebno je pronaći red u kojem je upisan broj –1. Broj retka koji sadrži ovaj broj daje broj vrha koji je izravno dostupan iz ovog vrha. Ako se pronađe –1, u stupcu je potrebno pronaći red u kojem je upisano 1, te dobiti broj vrha iz kojeg je ovaj vrh izravno dostupan. Da biste dobili cjelokupno "okruženje", trebate izvršiti navedenu pretragu za sve elemente k-tog retka koji nisu nula. Najviše vremena oduzima postupak pronalaženje elementa različitog od nule u stupcu. Broj takvih postupaka pretraživanja jednak je stupnju vrha. U ovom slučaju, reći ćemo da je složenost algoritma za analizu okoline vrhova (reda).

Može se vidjeti da će traženje "okruženja" svih vrhova trajati vrijeme reda umnoška broja vrhova u usmjerenom grafu prema zbroju stupnjeva svih vrhova, što je, kako se može pokazati, proporcionalan je broju lukova u usmjerenom grafu. Dakle, složenost algoritma pretraživanja "okoliša" je, t.j. traženje traje vrijeme reda umnoška broja vrhova i broja lukova.

Učinkovitija matrična struktura koja predstavlja graf je matrica susjednosti vrhova, ili booleova matrica graf. Ovo je kvadratna matrica B reda n, čiji su elementi definirani kako slijedi:

za neusmjereni graf:

za usmjereni graf:

Za grafikon ispod ( Riža. 2.2 a) matrica incidencije je matrica predstavljena na ( Slika 2.2 b).

Počeci teorije grafova jednoglasno se pripisuju 1736. godini, kada je L. Euler riješio problem Koenigsberovih mostova, koji je bio popularan u to vrijeme. Međutim, ovaj je rezultat ostao jedini rezultat teorije grafova više od stotinu godina. Tek sredinom 19. st. inženjer elektrotehnike G. Kirchhoff razvio je teoriju stabala za proučavanje električnih krugova, a matematičar A. Cayley, u vezi s opisom strukture ugljikovodika, riješio je nabrajajuće probleme za tri vrste drveća.

Rođen na rješavanju zagonetki i zabavne igre(problemi o šahovskom vitezu, o kraljicama, "putovanju po svijetu", problemima o vjenčanjima i haremima itd.), teorija grafova je danas postala jednostavan, pristupačan i moćan alat za rješavanje problema vezanih uz širok spektar problema. Grafovi su doslovno sveprisutni. U obliku grafikona možete, na primjer, tumačiti sheme cesta i električnih krugova, zemljopisne karte i molekule kemijskih spojeva, veze između ljudi i skupina ljudi. Tijekom posljednja četiri desetljeća teorija grafova postala je jedna od najbrže razvijajućih grana matematike. To je potaknuto zahtjevima iz područja primjene koje se brzo širi. Koristi se u projektiranju integriranih i upravljačkih sklopova, u proučavanju automata, logičkih sklopova, dijagrama toka programa, u ekonomiji i statistici, kemiji i biologiji, u teoriji rasporeda. Prodor matematičkih metoda u znanost i tehnologiju danas se uglavnom odvija kroz teoriju grafova.

U ovom radu se ne razmatraju vlastiti problemi teorije grafova, već kako se ona koristi u školskom kolegiju geometrije.

Stoga je relevantnost istraživačke teme, s jedne strane, posljedica popularnosti grafova i srodnih istraživačkih metoda, koji organski prožimaju gotovo svu modernu matematiku na različitim razinama, as druge strane, cjelovitog sustava za njegovu implementaciju u kolegij geometrije nije razvijen.

Svrha istraživanja je proučavanje korištenja grafova u školskom kolegiju geometrije.

Objekt – proces nastave geometrije.

Predmet – razredni i izvannastavni rad

Zadaci: 1) utvrditi bit i sadržaj uporabe grafova u školskom kolegiju geometrije;

2) razviti PMC za izvođenje nastave geometrije u 7-9 razredima.

Vodeća tema je izgradnja grafskog modela za dokazivanje geometrijskih teorema.

Teorijska osnova:

1. Teorija grafova nastala 1736. (Leonard Euler (1708-1783) dobila je brz razvoj, ostaje aktualna i danas, budući da je u Svakidašnjica sve se više koriste grafičke ilustracije, geometrijski prikazi i druge tehnike i metode vizualizacije.

1. Teorija grafova nalazi primjenu u raznim područjima moderne matematike i njezine brojne primjene (Lipatov E.P.)

2. Teorija grafova koristi se u područjima matematike kao što su matematička logika, kombinatorika itd.

Teorijski značaj rada leži u:

Identifikacija područja primjene teorije grafova;

Korištenje teorije grafova za proučavanje geometrijskih teorema i problema;

Praktični značaj rada leži u korištenju grafova u dokazivanju geometrijskih teorema i rješavanju zadataka.

Kao rezultat ovog rada nastalo je sljedeće:

Programski i metodički kompleks za izvođenje nastave geometrije u 7-9 razredima.

Najteže u pronalaženju rješenja problema je uspostavljanje lanca logičkih posljedica koji vodi do dokazivanja tvrdnje. Da bi se logički kompetentno zaključivalo, potrebno je razviti vještine takvog mišljenja koje bi pomoglo da se različite geometrijske činjenice ugrade u logičke međusobne veze.

Za razvoj vještina kulture mišljenja posebnu ulogu imaju oblici pisanog govora učenika. Pismeni oblici rada najvažnija su aktivnost koja formira snažne vještine logičkog zaključivanja u dokazivanju teorema i rješavanju problema. Oblik zapisa iskaza problema, razumne kratice i oznake u izračunima i dokazima problema discipliniraju razmišljanje i promiču geometrijsku viziju. Kao što znate, vizija potiče razmišljanje. Pojavljuje se problem: kako uspostaviti logičke veze između različitih geometrijskih činjenica i kako ih složiti u jedinstvenu cjelinu. Napredak dokazivanja teorema i rješavanja problema možete vidjeti metodom graf-shema, što dokaz čini vizualnijim te omogućuje sažet i precizan prikaz dokaza teorema i rješenja problema.

Za to se koristi graf stabla.

Vrhovi "stabla" (uvjet teorema ili problema i slijed logičkih spojeva) prikazani su pravokutnicima s informacijama u njima, koji su zatim povezani strelicama. Kraj grafa sheme sadrži tvrdnju koju treba dokazati. Opisani oblik dokazivanja teorema i rješavanja zadataka je koristan i prikladan za studente, jer omogućuje jednostavno prepoznavanje glavnih faza dokazivanja teorema i rješavanja problema.

Istraživački dio.

Odjeljak 1. Proučavanje povijesti nastanka teorije grafova.

Matematičar Leonard Euler (1707-1783) smatra se utemeljiteljem teorije grafova. Povijest nastanka ove teorije može se pratiti kroz korespondenciju velikog znanstvenika. Ovdje je prijevod latinskog teksta preuzetog iz Eulerovog pisma talijanskom matematičaru i inženjeru Marinoniju, poslanog iz Petersburga 13. ožujka 1736. godine.

"Jednom su mi postavili problem otoka koji se nalazi u gradu Konigsbergu i okružen rijekom preko koje je prebačeno sedam mostova. Pitanje je može li ih netko kontinuirano zaobilaziti, prolazeći samo jednom kroz svaki most. I odmah sam dobio informaciju da nitko Do sada to nisam uspio, ali nitko nije dokazao da je to nemoguće. Ovo pitanje, iako trivijalno, činilo mi se, međutim, vrijednim pažnje jer ni geometrija, ni algebra, ni kombinatorna umjetnost su dovoljni za njegovo rješenje. Nakon dugog razmišljanja, pronašao sam jednostavno pravilo, utemeljeno na potpuno uvjerljivom dokazu, uz pomoć kojeg se u svim problemima ove vrste može odmah utvrditi može li se takav zaobilazni put ostvariti kroz bilo koji broj i proizvoljno locirani mostovi ili ne, tako da se mogu prikazati na sljedećoj slici, na kojoj A označava otok, a B, C i D su dijelovi kontinenta, međusobno odvojeni ograncima rijeke. mostovi su označeni slovima a, b, c, d, e, f, g".

O metodi koju je otkrio za rješavanje problema ove vrste, napisao je Euler

„Ova odluka, po svojoj prirodi, očito nema mnogo veze s matematikom i ne razumijem zašto bi tu odluku očekivali od matematičara, a ne od neke druge osobe, jer je ta odluka potkrijepljena samo obrazloženjem i nema Za pronalaženje ovog rješenja potrebno je uključiti sve zakone svojstvene matematici. Dakle, ne znam kako ispada da pitanja koja imaju vrlo malo veze s matematikom imaju veću vjerojatnost da će riješiti matematičari nego drugi."

Dakle, je li moguće zaobići mostove u Konigsbergu prolaskom samo jednom kroz svaki od tih mostova? Da bismo pronašli odgovor, nastavimo Eulerovo pismo Marinoniju:

"Pitanje je utvrditi je li moguće zaobići svih ovih sedam mostova, prolazeći kroz svaki samo jednom, ili ne. Moje pravilo dovodi do sljedećeg rješenja ovog pitanja. Prije svega, trebate pogledati koliko dionica ima odvojeni vodom - takvi , koji nemaju drugog prijelaza iz jednog u drugi, osim preko mosta. U ovom primjeru postoje četiri takva dijela - A, B, C, D. Zatim morate razlikovati da li je broj mostova koji vodi do ovih zasebnih dionica je paran ili neparan. Dakle, u našem slučaju pet mostova vodi do dionice A, a po tri mosta do ostalih, odnosno broj mostova koji vode do pojedinih dionica je neparan, a ovaj je već dovoljno za rješavanje problema. Kada se to utvrdi, primjenjujemo sljedeće pravilo: kada bi broj mostova koji vode do svake pojedine dionice bio paran, tada bi dotični zaobilaz bio moguć, a ujedno bi bilo moguće krenuti ovo skretanje s bilo kojeg dijela. Ako su dva od ovih brojeva bila bi neparna, jer bi samo jedan bio neparan ne može, onda se i tada mogao dogoditi prijelaz, kako je propisano, ali se svakako mora uzeti samo početak obilaznice s jedne od te dvije dionice do kojih vodi neparan broj mostova. Ako je, konačno, bilo više od dvije dionice, do kojih vodi neparan broj mostova, onda je takvo pomicanje općenito nemoguće ako bi se ovdje mogli donijeti drugi, ozbiljniji problemi, ova metoda bi mogla donijeti još veću korist i ne bi se smjela zanemariti ."

Obrazloženje za navedeno pravilo može se pronaći u pismu L. Eulera njegovom prijatelju Ehleru od 3. travnja iste godine. U nastavku ćemo prepričati izvadak iz ovog pisma.

Matematičar je napisao da je prijelaz moguć ako na rukavcu rijeke nema više od dva područja u koje vodi neparan broj mostova. Kako bismo to lakše zamislili, na crtežu ćemo obrisati već pređene mostove. Lako je provjeriti da ako se počnemo kretati u skladu s Eulerovim pravilima, prijeđemo jedan most i izbrišemo ga, tada će slika prikazati dio gdje opet nema više od dva područja do kojih vodi neparan broj mostova, a u prisutnosti regija s neparnim brojem mostova nalazit ćemo se u jednoj od njih. Nastavljajući tako dalje, proći ćemo jednom kroz sve mostove.

Priča o mostovima grada Königsberga ima moderan nastavak.

Problem Na jezeru se nalazi sedam otoka koji su međusobno povezani kao što je prikazano na slici 2. Na koji otok brod treba odvesti putnike da mogu prijeći svaki most i to samo jednom? Zašto se putnici ne mogu prevesti na otok A?

Riješenje. Budući da je ovaj problem sličan problemu konigsberških mostova, za njegovo rješavanje koristit ćemo i Eulerovo pravilo. Kao rezultat dobivamo sljedeći odgovor: brod mora odvesti putnike do otoka E ili F kako bi mogli jednom prijeći svaki most. Isto Eulerovo pravilo podrazumijeva nemogućnost traženog obilaska ako se kreće s otoka A.

Kasnije su na grafovima radili Koenig (1774-1833), Hamilton (1805-1865), a među modernim matematičarima - K. Berge, O. Ore, A. Zykov.

Povijesno gledano, teorija grafova nastala je prije više od dvjesto godina upravo tijekom rješavanja zagonetki. Vrlo dugo je bila udaljena od glavnih pravaca istraživanja znanstvenika, bila je u području matematike u poziciji Pepeljuge, čiji su se talenti u potpunosti otkrili tek kada je bila u središtu opće pozornosti.

Prvi rad o teoriji grafova, koji pripada poznatom švicarskom matematičaru L. Euleru, pojavio se 1736. godine. Teorija grafova dobila je poticaj na prijelazu iz 19. u 20. stoljeće, kada se povećava broj radova iz područja topologije i kombinatorike. oštro, s kojim ga povezuju najbliže rodbinske veze. Grafovi su se počeli koristiti u izgradnji električnih krugova i molekularnih dijagrama. Kao zasebna matematička disciplina, teorija grafova je prvi put predstavljena u radu mađarskog matematičara Koeniga 1930-ih godina.

Nedavno su grafovi i srodne metode istraživanja organski prožele gotovo svu modernu matematiku na različitim razinama. Teorija grafova se smatra jednom od grana topologije; također je izravno povezana s algebrom i teorijom brojeva. Grafovi se učinkovito koriste u teoriji planiranja i upravljanja, teoriji rasporeda, sociologiji, matematičkoj lingvistici, ekonomiji, biologiji, medicini, geografiji. Grafovi se široko koriste u područjima kao što su programiranje, teorija konačnih automata, elektronika, u rješavanju probabilističkih i kombinatornih problema, najkraća udaljenost itd. Matematička zabava i zagonetke također su dio teorije grafova. Teorija grafova se brzo razvija, pronalazeći nove primjene.

Odjeljak 2. Osnovne vrste, pojmovi i struktura grafova.

Teorija grafova je matematička disciplina nastala trudom matematičara, stoga njezino predstavljanje uključuje potrebne rigorozne definicije.

Graf je skup konačnog broja točaka, koji se nazivaju vrhovi grafa, koji u paru povezuju neke od ovih vrhova pravaca, koji se nazivaju bridovi ili lukovi grafa.

br. Naziv stupca Definicija Slika Primjer korištenja ove vrste grafova

1 Nulti graf Vrhovi grafa koji ne pripadaju Problem: Arkadij, Boris. Vladimir, Grigorij i Dmitrij na sastanku su se rukovali, svaki sa svakim po jednom. Koliko se rebara naziva izolirano. rukovanje je obavljeno? Situacija koja odgovara trenutku kada rukovanje još nije obavljeno je točkasti uzorak prikazan na slici.

Graf koji se sastoji samo od izoliranih vrhova naziva se nulti graf.

Oznaka: O "- graf s vrhovima bez bridova

2 Potpuni grafovi Graf u kojem svaki par vrhova Imajte na umu da ako potpuni graf ima n vrhova, tada će broj bridova biti svih rukovanja.

Oznaka: U "- graf koji se sastoji od n 10.

vrhova i bridova koji povezuju sve moguće parove ovih vrhova. Takav graf se može predstaviti kao n-kut u kojem su nacrtane sve dijagonale

3 Nepotpuni grafovi Grafovi u kojima nisu izgrađeni svi Situacija kada još nisu obavljena sva rukovanja, ruke A i B, A i D, E i mogući bridovi su potreseni, nazivaju se nepotpuni G, C i D.

4 Put u grafikonu. Ciklus. Put u grafu od jednog vrha do drugog U točki A nalazi se garaža za snježni stroj. Rečeno je da je vozač automobila dobio instrukciju da ukloni snijeg s ulica dijela grada prikazanog na slici. Može li on imati takav slijed rubova, duž kojih će završiti svoj posao na raskrižju gdje se nalazi garaža, ako će vozač kroz svaku od ovih ulica svog dijela grada proći samo jednom?

vrhovima.

U tom se slučaju niti jedan rub rute ne smije pojaviti više od jednom. Vrh, iz To je nemoguće, budući da se zatvoreni put koji prolazi duž svih bridova grafa, duž kojih je ruta položen, poziva na svaki brid samo jednom ako su stupnjevi svih vrhova grafa parni.

početak staze, vrh na kraju rute -

kraj staze. Put se naziva ciklus. Jednostavne točke.

ciklus se naziva ciklusom koji ne prolazi. Na primjer, od točke A (vrh grafikona) do točke H može se doći različitim rutama: ADGH, AEH, AEFCEH, ABCEH.

kroz jedan od vrhova grafa više od jednog Koja je razlika između AEH rute i AEFCEH rute?

puta. Činjenica da smo drugu rutu na “križju” u točki E posjetili dva puta.

Ova ruta je duža od AEH-a. AEH ruta se može dobiti iz rute

Ako ciklus uključuje sve rubove AEFCEH, "brisanje" iz posljednje rute FCE.

graf jednom, onda je takav ciklus Ruta AEH put u grafu, ali AEFCEH nije put.

nazvan Eulerovom linijom.

Povezani i nepovezani grafovi. Definicija 1: Može li se od žice dužine 12 dm napraviti kockasti okvir s dužinom ruba

Dva vrha grafa nazivaju se povezanim, 1 dm, a da se žica ne razbije na komadiće?

ako graf sadrži put s krajevima na tim vrhovima. Ako takav put ne postoji, za vrhove se kaže da su nepovezani.

Budući da put koji prolazi duž svih rubova grafa, i duž svakog ruba samo jednom, postoji samo u sljedećim slučajevima:

1) kada je stupanj svakog vrha paran (put je zatvoren)

2) kada postoje samo dva vrha s neparnim stupnjem.

2. definicija:

Graf se naziva povezanim ako je povezan bilo koji par njegovih vrhova.

Graf se naziva nepovezanim ako ima barem jedan nepovezani par vrhova.

6 Stabla Stablo je bilo koji povezani graf, Dodatak #1. Obiteljsko stablo Zholmurzaeva Tomirisa.

vrhovima. Nepovezani graf koji se u potpunosti sastoji od stabala naziva se šuma.

7 Izomorfni grafovi. Grafikoni prikazani na slici pružaju iste informacije. Takvi se grafovi nazivaju izomorfni (identični).

8 Koncept ravnog grafa Graf koji se može prikazati na problemu. U tri različite kuće, tri aviona žive u zavađenom susjedu. Nedaleko od ovog pogleda, kada se njegova rebra sijeku od njihovih kuća, nalaze se tri bunara. Je li moguće od samo na vrhovima, zove svaku kuću položiti na svaki od bunara stan. put tako da se njih dvije ne sijeku?

Rješenje: Nakon što nacrtate osam putova, možete se uvjeriti da nije moguće nacrtati deveti, koji se ne siječe ni s jednim od prethodno nacrtanih putova.

Konstruirajmo graf čiji su vrhovi

A, B, C, 1, 2, 3

odgovaraju kućama i bunarima u stanju zadatka, a pokušat ćemo dokazati da se deveti put, brid grafa koji ne siječe ostale bridove, ne može nacrtati.

Rubovi nacrtani u grafu na slici

A1, A2, A3 i B1, B2, BZ (odgovaraju putevima od kuća A i B do svih bunara).

Konstruirani graf podijelio je ravninu na tri područja: X, Y, Z. Vrh B, ovisno o svom položaju na ravnini, spada u jedno od ova tri područja. Ako uzmete u obzir svaki od tri najbolja pogotka

B u jedno od područja X, Y ili Z, zatim provjerite je li svaki put jedan od vrhova grafa 1, 2 ili 3

(jedan od bunara) bit će "nedostupan" za vrh B (tj. neće biti moguće nacrtati jedan od bridova B1, B2 ili B3, koji ne bi sijekao bridove koji su već prisutni u grafu).

Odgovor na pitanje problema bit će: "To je nemoguće!"

Usmjereni grafovi Brid grafa naziva se usmjerenim bridom ako se jedan od njegovih vrhova smatra početkom, a drugi kraj ovog brida.

Graf u kojem su svi bridovi orijentirani naziva se usmjereni graf.

Dakle, razmatrao sam osnovne koncepte teorije grafova, bez kojih bi bilo nemoguće dokazati teoreme, a time i riješiti probleme.

Zaključak o obavljenom poslu:

Naučio sam strukturirati sav informacijski materijal u tablici;

Sastav teorijskog materijala pridonosi vizualnom prikazu vrsta grafova i njihovoj primjeni;

Razradila je primjere primjene teorije grafova u sastavljanju svog obiteljskog stabla.

Dodatak 1.

GENEOLOŠKO STABLO

Izgradite obiteljsko stablo Zholmurzaeve Tomirisa.

Metoda rješenja.

Grafički način rješavanja problema.

Grafički način rješavanja problema je crtanje „drveta logičkih uvjeta“. "Stablo" u obliku jednostavnog crteža izražava logički odnos među rođacima. Na stablu postoji jedna grana za svaku generaciju.

Za primjer sam uzeo svoje obiteljsko stablo.

Odjeljak 3. Primjena teorije grafova.

S grafovima se susrećemo češće nego što je to moguće, čini se na prvi pogled. Primjeri grafova su bilo koja karta puta, električni krug, crtanje poligona itd. Dugo se vjerovalo da se teorija grafova koristi uglavnom za rješavanje logičkih problema. Prilikom rješavanja logičkih zadataka često je teško zapamtiti brojne uvjete navedene u zadatku i uspostaviti vezu između njih. Grafovi pomažu u rješavanju takvih zadataka, omogućujući vizualni prikaz odnosa između podataka problema. Sama teorija grafova promatrana je kao dio geometrije. Međutim, u dvadesetom stoljeću pronađene su široke primjene teorije grafova u ekonomiji, biologiji, kemiji, elektronici, planiranju mreže, kombinatorici i drugim područjima znanosti i tehnologije. Kao rezultat toga, počela se ubrzano razvijati i pretvorila se u samostalnu razgranatu teoriju.Rješenje mnogih matematičkih problema se pojednostavljuje ako je moguće koristiti grafove. Prikaz podataka u obliku grafikona daje im jasnoću. Mnogi se dokazi također pojednostavljuju, dobivaju uvjerljivost ako koristimo grafove.

3. 1. Primjena grafova u geometrijskim problemima i teoremama.

Uz pomoć grafova lako se mogu uspostaviti lanci logičkih posljedica koje dovode do dokazivanja tvrdnje. Ukratko i točno navedite dokaz teorema i rješenje zadatka.

Dokaži da u jednakokračan trokut simetrale povučene iz vrhova u bazi su jednake.

Metode rješenja.

Dokaz problema pomoću obrazloženja.

Neka je ABC jednakokračan trokut s

B1 A1 s bazom AB i simetralama AA1 i BB1.

Razmotrimo ∆ABB1 i ∆BAA1. Imaju ∟V1AV =

∟A1VA kao kutovi na osnovici jednakokračnog trokuta ∆ABS. ∟AVV1 = ∟A1AV

A B budući da su AA1 i BB1 simetrale kutova na bazi jednakokračnog trokuta. AB - zajednička strana. Sredstva

∆ABB1 = ∆BAB1 duž strane i dva susjedna kuta. Iz jednakosti trokuta slijedi jednakost njihovih stranica AA1 i BB1.

Dokaz problema pomoću grafa.

Dokaži: AA = BB

Za razmišljanje koristimo graf. Vrhovi grafa - uvjeti teorema ili problema i faze dokaza.

Rubovi grafa su logički nizovi. Kraj grafske sheme je dokazana tvrdnja.

Boja se koristi za isticanje komponenti. Uvjet teorema i problema je plave boje. Tvrdnja koju treba dokazati je crvena. Faze dokaza - crna.

Opisani oblik dokazivanja teorema i rješavanja zadataka je koristan i prikladan za studente, jer omogućuje isticanje glavnih faza dokazivanja teorema i rješavanja problema.

3. 2. Programski i metodološki kompleks.

a) Priručnik za učitelje.

Predloženi priručnik sastavljen je u skladu s udžbenikom geometrije 7-9 razreda A. V. Pogorelov. Njegova glavna svrha je osigurati proces proučavanja geometrije potrebnim vizualnim pomagalima, pomoći učitelju u nastavi geometrije: olakšati proces dokazivanja teorema, usvajanje teorijskog materijala u procesu rješavanja zadataka. Grafički dijagrami su višestruki i, ovisno o ciljevima i oblicima nastave, mogu se koristiti na različite načine: kao ilustrativni, usmjereni na povećanje jasnoće pri objašnjavanju novog teorijskog gradiva, kod generaliziranja i sistematizacije novog gradiva (grafički dijagrami s teoremima); kao kartice koje se koriste u individualnim i frontalnim anketama (grafogrami sa zadacima). Uz ovaj priručnik dolazi i radna bilježnica za učenike. Radna bilježnica se može koristiti za organiziranje samostalan rad učenika u učionici i nakon nastave.

b) Radna bilježnica za učenike.

Priručnik je izrađen u obliku radne bilježnice. Priručnik sadrži 28 grafskih shema s teoremima i 28 grafskih shema s problemima. Grafički dijagrami sadrže glavni programski materijal koji je prikazan s potrebnom jasnoćom i predstavlja okvir rješenja. Učenici redom ispunjavaju prazne ćelije informacijama koje čine rješenje problema.

Boja se koristi za isticanje komponenti. Uvjet teorema i problema je plave boje, tvrdnja koja se dokazuje je crvena, faze dokaza su crne.

Priručnik je koristan za učenike 7-9 razreda.

c) Elektronički priručnik.

Rezultati rada i njihova rasprava. Projekt je rezultat dvogodišnjeg proučavanja korištenja grafova u školskom kolegiju matematike.

Kreiraj programski - metodološki kompleks a njegova provedba provedena je tijekom:

Provođenje nastave Aristotel kluba na temu "Rješavanje logičkih zadataka pomoću grafova".

Primjena grafova u dokazima geometrijskih teorema i zadataka

Na nastavi geometrije u 8.9 razredu.

Izlaganja s projektom na školskim znanstvenim i praktičnim skupovima.

ZAKLJUČAK.

Sumirajući rezultate proučavanja upotrebe grafova u školskom kolegiju geometrije, došao sam do sljedećeg zaključka:

1. Prednost dokazivanja teorema grafa i rješavanja problema u odnosu na tradicionalno je ilustracija dinamike teorema i dokazivanja problema.

2. Upoznavanje s procesom dokazivanja geometrijskih teorema i problematike metode graf-shema pomaže u jačanju vještina učenika u konstruiranju dokaza.

3. Razvijen programsko-metodički kompleks za proučavanje geometrije u 7-9 razredima: a) priručnik za učitelja; b) radna bilježnica za učenike; c) elektronički priručnik je koristan za učenike 7-9 razreda.