Dom Fizika Grafovi u istraživačkom radu arhitekture. Istraživački rad "pronalaženje najkraćeg puta"

Grafovi u istraživačkom radu arhitekture. Istraživački rad "pronalaženje najkraćeg puta"

Sadržaj:

I. Uvod ………………………………………………………………… 2

II. Glavni dio.

1.Povijest nastanka teorije grafova ……………………………………………… .4

2. Osnovni pojmovi teorije grafova ………………………………………… ..5

3.Neki problemi teorije grafova …………………………………………… 6

3.1 Zadaci crtanja figura jednim potezom ……………………… ..8

3.2 Zadaci s labirintima …………………………………………………………… ..10

3.3 Logički zadaci …………………………………………………………………… 12

4. Primjena teorije grafova u raznim područjima djelatnosti ………… ..15

4.1. Grafovi i povijest ……………………………………………………………………… 17

4.2. Grafovi i kemija …………………………………………………………… 18

4.3. Grafovi i fizika …………………………………………………………………… .19

III. Zaključak ……………………………………………………………………… ..20

IV. Literatura …………………………………………………………………… 21

Dodatak 1 ………………………………………………………………………… .22

Dodatak 2 ………………………………………………………………………… .25

Dodatak 3 ………………………………………………………………………… ..26

I. Uvod

Svi znaju zabavnu zagonetku o otvorenoj omotnici: "Nacrtajte oblik bez podizanja olovke s papira ili crtanja bilo koje linije dvaput."

Ove godine sudjelovao sam na olimpijadi iz matematike na daljinu. Predložio je sljedeći problem:

“Poštar Pečkin je raznosio poštu u sve kuće u selu, nakon čega je otišao do strica Fjodora da popije mlijeko. Na slici su prikazani svi putevi kojima je Pečkin prošao, a kako se pokazalo, nijednom od njih nije prošao dvaput. Kojim je putem krenuo poštar Pečkin? U kojoj kući živi ujak Fjodor?"

Analizirajući rješenje ovog problema, postavio sam si pitanje: "Je li moguće riješiti te probleme ne grubom silom, već na drugačiji, brži način?"

Nakon toga sam se obratio svom učitelju, a oni su mi objasnili da ovaj problem mogu riješiti proučavanjem teorije grafova. Ali prije nego što sam pronašao odgovor na svoje pitanje, vidio sam da teorija grafova pomaže pojednostavniti rješavanje mnogih problema. Grafovi su me zainteresirali svojom sposobnošću da pomognu u rješavanju raznih zagonetki, matematičkih i logičkih problema.

Cilj:

pokazati primjenu teorije grafova za rješavanje raznih vrsta problema.

Zadaci:

Istražite elemente teorije grafova.

Analizirajte rješenja raznih vrsta problema.

Naučite o korištenju grafova u znanosti iu raznim područjima djelovanja.

Metode istraživanja:

Pretraga i analiza informacija u literaturi.

Pretraživanje i proučavanje informacija u internetskim izvorima.

Modeliranje.

II Glavni dio

1. Povijest nastanka teorije grafova.

Datumom rođenja teorije grafova smatra se 1736. godina, kada je Leonard Euler riješio problem mostova u Konigsbergu (Prilog 1.).

R
rijeka ukava Pregel, na čijoj se obali nalazi grad Königsberg, formirala je dva otoka. Tijekom tog razdoblja nastala su četiri kopnena područja (desna i lijeva obala i dva otoka) koja su povezivala sedam mostova kao što je prikazano na slici. Građani su, šetajući gradom, pokušavali iscrtati trasu tako da svaki most prođe točno jednom. Nisu uspjeli, a Euler je dokazao da je to u principu nemoguće.

Pojam "broj" prvi je uveo 1936. godine mađarski matematičar Denesh Koenig. Teorija grafova naširoko je razvijena 50-ih godina 20. stoljeća u vezi s nastankom kibernetike i razvojem računalne tehnologije.

Riječ "graf" u matematici označava sliku na kojoj je nacrtano nekoliko točaka, od kojih su neke povezane linijama. Uz plemićku titulu "grof" povezuje ih zajedničko porijeklo od latinske riječi "grapio" - pišem.

2. Osnovni pojmovi teorije grafova.

U matematici se definicija grafa daje na sljedeći način: „Graf je konačan skup točaka, od kojih su neke povezane linijama. Točke se zovu vrhovi grafa, a povezne linije nazivaju se bridovi."

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)

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.

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

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

sl. 5

3. Neki problemi u teoriji grafova.

Eulerov put je put u grafu koji prolazi kroz svaki rub točno jednom.

Zove se graf koji se može nacrtati bez podizanja olovke s papira Euler.(Sl. 6) Ovi grafovi su nazvani po znanstveniku Leonardu Euleru.

Slika 6 (Eulerovi grafovi)

Uzorak 1.

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 2.

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.
Uzorak 3.

Graf s više od dva neparna vrha ne može se nacrtati jednim potezom.

Zove se lik (graf) koji se može nacrtati bez podizanja olovke s papira jednoznačni .

Algoritam za rješavanje

Iz prethodnog obrazloženja dobivamo opće rješenje svaki takav problem mosta:

pretvoriti crtež u graf (definirati njegove vrhove i bridove);

odrediti stupanj svakog vrha;

donijeti zaključke:

a) zadani obilaz je moguć ako

Svi vrhovi su parni (može se pokrenuti iz bilo kojeg vrha);

Dva vrha su neparna (mora se krenuti od jednog od neparnih vrhova);

b) dano obilaženje je nemoguće ako ima više od dva neparna vrha;

označavaju početak i kraj puta.

Proučivši ove zaključke, odlučio sam ih provjeriti na primjerima problema iz odjeljka teorije grafova.

3.1. Rješavanje problema crtanja oblika jednim potezom

Zadatak broj 1 (Na Konigsberškim mostovima).

H Četiri formirana kopnena područja (desna i lijeva obala i dva otoka) povezuju sedam mostova kao što je prikazano na slici. Građani su pokušali iscrtati trasu tako da preko svakog mosta prođe točno jednom.

Riješenje.

Ovaj problem je riješio Leonard Euler. Napravio je sljedeći graf i dobio da su sva četiri vrha neparna, odnosno da ne možete jednom prijeći preko svih mostova i završiti put gdje je započet.

Problem broj 2.

Je li moguće nacrtati grafikone prikazane na slikama bez podizanja olovke s papira i crtanja svakog ruba točno jednom?

R riješenje:

Moguće je jer postoje samo 2 neparna vrha.

To je nemoguće, jer postoje 4 neparna vrha.

Z problem broj 3.

Kažu da je Muhamed umjesto potpisa (bio je nepismen) jednim potezom opisao znak dvaju mjesečevih roga prikazanih na slici. Je li moguće?

Riješenje. Da, jer u ovom slučaju imamo posla s vrhovima parnog reda.

Problem broj 4. (Leti u banku).

Muha se popela u konzervu šećera. Tegla je u obliku kocke. Može li muha dosljedno prijeći svih 12 bridova kocke, a da ne ide dvaput duž jednog ruba? Skakanje i letenje s mjesta na mjesto nije dopušteno.

Riješenje.

Rubovi i vrhovi tvore graf čijih je svih 8 vrhova stupnja 3, te je stoga traženo obilaženje nemoguće.

Problem broj 5. (Pečkinov put)

Riješenje. U uvjetu problema postoje dva neparna vrha - pošta i dom, tako da ruta može započeti i završiti samo na tim čvorovima. Poštar Pečkin počinje dostavljati pisma iz pošte, pa bi njegova ruta mogla završiti u kući 5, gdje živi stric Fjodor. Na primjer, ruta može biti: mail-1-3-2-1-7-mail-3-4-5-7-6-5.

1. Problemi s labirintom

Uz probleme tipa "jednog poteza", dobivenom metodom moguće je rješavati probleme s labirintom.

Podrijetlo problema s labirintom seže u antičko doba i izgubljeno je u tami vremena. Riječ "labirint" (grčki) znači "podzemni prolazi". Rješenju problema labirinta prethode povijesne informacije - da se pokaže interes za ovaj problem i da se vizualno predstavi postojeći i postojeći labirinti.

Problem prolaska labirinta dobiva praktičan interes, budući da se izvode dalekovodi, kanalizacijski sustavi, cestovne mreže, kanali itd. - sve su to manje-više složeni labirinti. Rješenje pitanja postojanja beznadnih labirinta inicirao je Euler.

Nakon što su nacrtali graf koji odgovara labirintu, koriste metodu prelaska svih rubova kako bi pronašli izlaz.

Rješenje (tj. ruta koja vodi do cilja) svakog labirinta može se pronaći jednom od tri relativno jednostavne metode.

Prva metoda je METODA POKUŠANJA I POGREŠKE. Odaberite bilo koji put i ako vas odvede u slijepu ulicu, onda se vratite i počnite ispočetka.

Druga metoda je METODA BLOKIRANJA. Počnimo dosljedno precrtavati slijepe ulice, t.j. rute koje nemaju grana i završavaju particijom. Dio koridora koji nije prekrižen bit će izlaz ili trasa od ulaza do izlaza ili do centra.

Treća metoda je PRAVILO JEDNE RUKE. Sastoji se od činjenice da se morate kretati po labirintu bez podizanja jedne ruke (desne ili lijeve) od zida.

Smatrati zadatak opći pogled:

M
Je li moguće zaobići sve te sobe, proći kroz svaka vrata točno jednom i izaći van kroz sobu 1 ili 10? Od koje sobe trebate početi?

Riješenje:

Slično razmišljajući, možete riješiti sve probleme s labirintima, ulazima i izlazima, tamnicama itd.

3.3 Logički zadaci

Problem broj 1.

Arkadij, Boris. Vladimir, Grigorij i Dmitrij na sastanku su se rukovali (svaki se rukovao sa svakim po jednom). Koliko je ukupno rukovanja napravljeno?

Riješenje:

P Usta svakog od petero mladih ljudi odgovaraju određenoj točki na ravnini, nazvanoj prvim slovom njegovog imena, a nastali stisak ruke je segment ili dio krivulje koji povezuje određene točke - imena.

Problem broj 2.

V
selo ima 10 kuća, a od svake od njih vodi 7 staza do drugih kuća. Koliko staza ima između kuća?

Riješenje.

Neka su kuće vrhovi grafa, putevi bridovi. Prema uvjetu, iz svake kuće (vrteksa) izlazi 7 putova (brova), tada je stupanj svakog vrha 7, zbroj stupnjeva vrhova je 7 × 10 = 70, a broj bridova je 70: 2 = 35. Dakle, između kuća ima 35 staza.

Odgovor. 35 staza

Problem broj 3.

Četiri prijatelja žive u istom dvorištu. Vadim i vozač stariji su od Sergeja, Nikolaj i bravar boksaju, električar je najmlađi prijatelj.

Navečer Andrej i tokar igraju domine protiv Sergeja i električara.

Odredite zanimanje svakog svog prijatelja.

Riješenje.

Napravimo graf od 4 prijatelja i 4 profesije. Isprekidane linije označavaju nemoguće veze, a pune linije označavaju podudarnost između naziva i zanimanja. Ako iz svakog vrha izlaze 3 isprekidane crte, onda bi četvrta linija trebala biti puna.

B S N A

SH S T E

Problem broj 4.

Pet prijatelja živi u malom gradu: Ivanov, Petrenko, Sidorchuk, Grishin i Kapustin. Različita su im zanimanja: jedan je slikar, drugi mlinar, treći stolar, četvrti poštar, a peti frizer.

Petrenko i Grishin nikada nisu držali kist u rukama.

Ivanov i Grišin idu u posjet mlinu u kojem radi njihov prijatelj. Petrenko i Kapustin žive u istoj kući s poštarom.

Sidorchuk je nedavno bio jedan od svjedoka u matičnom uredu kada su Petrenko i frizerova kći bili zakonski vjenčani. Ivanov i Petrenko svake nedjelje igraju po gradovima sa stolarom i slikarom.

Grishin i Kapustin sastaju se subotom u frizeru gdje radi njihov prijatelj. Poštar se radije brije. Tko je tko?

Riješenje.

Ivanov Petrenko Sidorčuk Grišin Kapustin

Slikar mlinar stolar poštar frizer

4. Primjena teorije grafova u raznim područjima djelovanja.

H

Što sam više proučavao teoriju grafova, to sam više bio zadivljen raznolikošću primjena ove teorije.

T
Tipični grafikoni na gradskim kartama su obrasci gradskog prometa, slike željeznice, dijagrami zrakoplovnih prijevoznika koji se često prikazuju u zračnim lukama. Sustav gradskih ulica također je graf. Vrhovi su mu trgovi i raskrižja, a rubovi ulice, a grafikoni su i na kartama zvjezdanog neba.

Uz pomoć grafova često se pojednostavljuje rješavanje problema formuliranih u različitim područjima znanja: u automatizaciji, elektronici, fizici, kemiji. Grafovi pomažu u rješavanju matematičkih i ekonomskih problema.

Teorija grafova sada jedan od najrazvijenijih dijelova matematike, budući da modernog života zahtijeva nastanak novih profesija. Jedan od njih - Specijalist za logistiku ... (Prilog 3.) Voditelj logistike se bavi isporukom robe, tereta, planira transportne rute, obračunava troškove prijevoza, organizira skladištenje robe, tereta i sl. Jedan od glavnih zadataka stručnjaka za logistiku je analizirati situaciju, pa mora znati dobro računati, biti vješt u teoriji grafova.

Inženjer crta dijagrame električnih krugova.

Kemičar crta strukturne formule kako bi pokazao kako su atomi u složenoj molekuli međusobno povezani pomoću valentnih veza.

povjesničarka prati genealoške veze na obiteljskom stablu.

vojskovođe kartira komunikacijsku mrežu duž koje se pojačanja dopremaju od stražnjih prema prednjim postrojbama.

Sociolog na složenom dijagramu pokazuje kako su različiti odjeli jedne ogromne korporacije međusobno podređeni.

Grafovi se koriste u raznim granama znanosti. Posljednjih desetljeća teorija grafova našla je nova područja primjene (fizika, kemija, genetika, psihologija, sociologija, ekonomija, lingvistika, elektronika, teorija planiranja i upravljanja). Upravo zahtjevi prakse doprinose intenzivnom razvoju teorije grafova.

4.1 Grafovi i povijest.

Koristi grafikone i povijest. Na primjer, u obiteljskom stablu vrhovi su članovi roda, a segmenti koji ih povezuju su odnosi srodstva.

Obiteljsko stablo A.S. Puškin.

Moje obiteljsko stablo

4.1 Grafovi i kemija.

Teorija grafova u kemiji se koristi za rješavanje raznih teorijskih i primijenjenih problema. Primjena teorije grafova temelji se na konstrukciji i analizi različitih klasa kemijskih i kemijsko-tehnoloških grafova, koji se nazivaju i topologija, t.j. modeli koji uzimaju u obzir samo prirodu povezanosti vrhova. Rubovi i vrhovi ovih grafova prikazuju kemijske i kemijsko-tehnološke pojmove, pojave, procese ili objekte i, sukladno tome, kvalitativne i kvantitativne odnose ili određene odnose među njima.

P Kada se grafički prikazuju formule tvari, slijed rasporeda atoma u molekuli je naznačen takozvanim valentnim potezima (izraz "valentni potez" predložio je 1858. A. Cooper za označavanje kemijskih sila prianjanja atoma ), inače zvano valentno svojstvo (svako valentno svojstvo, ili valentno prvo mjesto, ekvivalentno je jednom paru elektrona u kovalentnim spojevima ili jednom elektronu koji sudjeluje u formiranju ionske veze).

Kemijski grafovi omogućuju predviđanje kemijskih transformacija, objašnjavaju bit i sistematiziraju neke od osnovnih pojmova kemije.

Molekularni grafovi koji se koriste u stereokemiji i strukturnoj topologiji, kemiji klastera, polimera itd., su neusmjereni grafovi koji predstavljaju strukturu molekula. Vrhovi i bridovi ovih grafova odgovaraju atomima i kemijske veze između njih.

M
molekularni grafovi i stabla: a, b - multigrafi etilena i formaldehida; β-molekule izomera pentana.

4.3 Grafovi i fizika

E

Donedavno, jedan od najtežih i najzamornijih zadataka za radioamatere bio je dizajn tiskanih sklopova.

Tiskanim krugom se naziva ploča izrađena od neke vrste dielektrika (izolacijskog materijala), na kojoj se u obliku metalnih traka.

urezane staze. Tragovi se mogu križati samo na određenim mjestima gdje su ugrađeni potrebni elementi; njihovo sjecište na drugim mjestima će uzrokovati zatvaranje električnog kruga.

Prilikom rješavanja ovog problema potrebno je nacrtati ravan graf s vrhovima u naznačenim točkama.

Proučavajući ovo gradivo, upoznao sam područja primjene teorije grafova i zaključio da je ova grana matematike jedna od najvažnijih, koja se često neopaženo koristi u našem svakodnevnom životu.

III Zaključak.

Da bih pronašao odgovor na problem koji me zanima, morao sam se upoznati s novim dijelom matematike "Teorija grafova", koji se ne izučava u školskom kolegiju, ali olakšava rješavanje mnogih zadataka, naučio sam puno, shvatio da je matematika zanimljiva, ali i teška.

Grafovi su prekrasni matematički objekti s kojima možete rješavati matematičke, logičke i ekonomske probleme. Mnoge matematičke probleme lakše je riješiti kada možete koristiti grafove. Prikaz podataka u obliku grafikona čini ih jasnim i jednostavnim. Mnogi matematički dokazi također su pojednostavljeni i postaju uvjerljivi ako koristite grafove. Također možete riješiti razne zagonetke i pojednostaviti uvjete problema u fizici, kemiji, elektronici, automatizaciji. Grafovi se koriste u kartiranju i obiteljskim stablima.

IV. Književnost.

1. Alkhova Z.N., Makeeva A.V. Izvannastavne aktivnosti iz matematike. - Saratov: "Licej", 2002

2. Perelman Ya.I. Jednim potezom. - Lenjingrad, 1940

3. Bashmakov MI Matematika u džepu "Klokan". - M .: Drfa, 2010.

4. Ignatiev EI Matematička pamet. - M.: "Omega", 1994.

5. Priprema školaraca za matematičke olimpijade. 5-6 razredi / komp. Grigorieva G.I. - M.: "Globus", 2009

Prilog 1.

Leonard Euler i Königsberški mostovi

L Eonard Euler rođen je u švicarskom gradu Baselu, gdje je diplomirao na sveučilištu sa 15 godina, a magistrirao sa 17 godina. Dok je studirao na sveučilištu, Euler je podučavao jednog od najpoznatijih matematičara tog vremena Johanna Bernoullija i sprijateljio se s njegovim sinovima Danielom i Nikolaijem, koji su pozvani da rade u novostvorenoj Akademiji znanosti u Sankt Peterburgu. Godinu dana kasnije, na njihovu preporuku, tamo je pozvan i dvadesetogodišnji Euler. Ovaj izbor se pokazao jednim od najuspješnijih za Rusiju. Nema područja matematike gdje Euler nije rekao svoju riječ. Radio je danonoćno u bilo kojem ambijentu, objavio oko 850 djela. Lako je otkrivao nove probleme i metode njihovog rješavanja. Čak se i povijest nastanka teorije grafova može pratiti kroz korespondenciju velikog znanstvenika.

Evo prijevoda latinskog teksta preuzetog iz Eulerovog pisma talijanskom matematičaru i inženjeru Marinoniju, poslanog iz Petersburga 13. ožujka 1736.:

"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 dovoljni su 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 bilo kojim broja i proizvoljno lociranih mostova ili ne."

U svom pismu Marinoniju, Euler je detaljno iznio svoje razmišljanje:

"Konigsberški mostovi su locirani tako da se mogu prikazati na slici, gdje A označava otok, a B, C i D - dijelove kontinenta, odvojene jedan od drugog ograncima rijeke. Sedam mostova je označeno slova a, b, c, d, e, f, g".

Dakle, je li moguće zaobići sve Königsberške mostove, proći samo jednom kroz svaki od tih mostova?

Čini se da je jednostavan način rješavanja problema sljedeći: napravite sve moguće testove takvih prijelaza, odnosno navedite sve moguće putove, a zatim razmotrite koji ili koji od njih zadovoljavaju uvjete pitanja. Ali očito je, čak i sa samo sedam mostova, previše takvih testova za napraviti. A s povećanjem broja mostova takvo je rješenje gotovo potpuno nezamislivo. Da, osim toga, kod istog broja mostova problem se mijenja ovisno o položaju tih mostova.

Stoga, da bismo pronašli odgovor, nastavimo Eulerovo pismo i vidjeti koje je pravilo pronašao. Tako,

"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."

Napredak rješavanja problema predstavljamo u obliku računati, gdje vrhovima- otoci i obale, i rebra- mostovi.

"Dalje, trebate razlikovati je li broj mostova koji vode do tih pojedinačnih dionica paran ili neparan. Dakle, u našem slučaju postoji pet mostova koji vode do dionice A, a svaki po tri mosta do ostalih."

Odnosno, moramo odrediti stupanj svakog vrha (broj bridova koji konvergiraju na vrhu) i saznati koji čak i vrhove i koje neparan... Potpišimo stupnjeve vrhova u krugovima. I izbrojimo broj neparnih vrhova. Neparni vrhovi: A, B, C, D.

"Kada se to utvrdi, primjenjujemo sljedeće pravilo: ako svi vrhovi imaju paran stupanj, tada je dotično obilaženje moguće, a to se obilaženje može započeti iz bilo kojeg presjeka. Ako su dva od ovih vrhova neparna, tada prijelaz može biti napravljen , kako je propisano, ali samo početak obilaska se svakako mora uzeti na jednom od ova dva vrha, a kraj obilaska svakako mora biti na drugom neparnom vrhu. Ako, konačno, postoji više od dva neparna vrha , onda je takav pokret općenito nemoguć..." ...

Dodatak 2

Različiti zadaci crtanja jednim potezom

Dodatak 3

Logistička profesija

O
struka pisanje:

Ovo je stručnjak koji koordinira kretanje robe na putu od proizvodnje do prodajnih mjesta.

Naziv profesije dolazi od engleska riječ logistika - opskrba, materijalna i tehnička podrška.

U suvremenim uvjetima, svaki proizvod, prije nego što dođe do potrošača, prevlada prilično težak put, koji uključuje mnoge poveznice (osobito kada su u pitanju isporuke iz inozemstva).

Lanac može izgledati, na primjer, ovako: kupnja robe od stranog dobavljača - njihovo osiguranje - prijevoz - carinjenje (prolazak carinske kontrole, plaćanje carina) - skladištenje - pakiranje i/ili isporuka naljepnica i dokumentacije na ruskom jeziku - distribucija veleprodajnim trgovačkim bazama - prodaja u maloprodajnim mrežama.

Kako bi proizvod na vrijeme stigao do potrošača i ostvario profit, sve karike u ovom lancu moraju funkcionirati kao dobro podmazan mehanizam. A kada se broj isporučenih artikala robe mjeri u desecima tisuća (na primjer, u lancu supermarketa), otklanjanje pogrešaka u takvim lancima vrlo je težak zadatak, a svaki neuspjeh prepun je gubitaka.

Primjerice, uneseno je previše proizvoda - uzalud zatrpa skladište i može postati neupotrebljiv. I neki drugi proizvod koji bi trebao biti donesen do točno određenog datuma (npr. božićna drvca za Novu godinu ili cvijeće do 8. ožujka), zbog neispravno izrađenih popratnih dokumenata, zaglaviće u carinskom skladištu i prekasno krenuti u prodaju , kada već postoji nitko nije potreban.

Zadaća logističara je otkloniti takve incidente i organizirati sustav dostave i distribucije robe na način da se sve isporuči tamo gdje je potrebno, u pravoj količini i na vrijeme, a da se pritom minimiziraju režijski troškovi povezani s transport i skladištenje. Sukladno tome, takvi stručnjaci su potrebni u svim organizacijama čije su aktivnosti vezane uz opskrbu robom: u specijaliziranim tvrtkama koje pružaju usluge u području prijevoza robe, u velikim trgovačkim lancima, u onim industrijama u kojima postoji velika količina sirovina i komponenti. se isporučuju itd.

Sadržaj rada logistike vrlo je raznolik: analizira informacije i na temelju njih smišlja načine i uvjete isporuke robe, izračunava troškove prijevoza, koordinira rad prijevoznika, komunicira s dobavljačima, skladišnim radnicima, carinske službe itd.

Općinska obrazovna proračunska ustanova -

srednja škola broj 51

Orenburg.

Projekt na:

nastavnik matematike

Egorčeva Victoria Andreevna

2017

Hipoteza : Ako se teorija grafova približi praksi, tada se mogu dobiti najkorisniji rezultati.

Cilj: Upoznajte se s pojmom grafova i naučite ih primijeniti u rješavanju raznih problema.

Zadaci:

1) Proširiti znanje o tome kako graditi grafikone.

2) Odaberite vrste zadataka za čije rješavanje je potrebna upotreba teorije grafova.

3) Istražite korištenje grafova u matematici.

"Euler je bez ikakvog vidljivog napora izračunao kako osoba diše ili kako orao lebdi iznad zemlje."

Dominic Arago.

ja Uvod. str.

II ... Glavni dio.

1. Pojam grafa. Problem Königsberških mostova. str.

2. Svojstva grafova. str.

3. Problemi primjene teorije grafova. str.

Sh. Zaključak.

Značenje grafova. str.

IV... Bibliografija. str.

ja . UVOD

Teorija grafova je relativno mlada znanost. "Brojevi" su ukorijenjeni u grčkoj riječi "grapho", što znači "pišem". Isti korijen u riječima "grafika", "biografija".

U svom radu razmatram kako se teorija grafova koristi u različitim područjima ljudskog života. Svaki nastavnik matematike i gotovo svaki učenik zna koliko teško može biti rješavanje geometrijskih zadataka, kao i riječnih zadataka iz algebre. Istražujući mogućnost primjene teorije grafova u školskoj matematici, došao sam do zaključka da ova teorija uvelike pojednostavljuje razumijevanje i rješavanje problema.

II ... GLAVNI DIO.

1. Pojam grafa.

Prvi rad o teoriji grafova pripada Leonardu Euleru. Pojavio se 1736. godine u publikacijama Petrogradske akademije znanosti i započeo ispitivanjem problema mostova u Konigsbergu.

Vjerojatno znate da postoji takav grad Kalinjingrad, nekada se zvao Konigsberg. Kroz grad protiče rijeka Pregolja. Dijeli se u dva kraka i obilazi otok. U 17. stoljeću u gradu je bilo sedam mostova, raspoređenih kako je prikazano na slici.

Priča se da je jednom stanovnik grada pitao svog prijatelja može li prijeći sve mostove kako bi svaki od njih mogao posjetiti samo jednom i vratiti se na mjesto odakle je šetnja počela. Mnogi građani bili su zainteresirani za ovaj zadatak, ali nitko nije mogao doći do rješenja. Ovo pitanje je privuklo pozornost znanstvenika iz mnogih zemalja. Poznati matematičar Leonard Euler uspio je riješiti problem. Leonard Euler, rodom iz Basela, rođen je 15. travnja 1707. godine. Eulerova znanstvena dostignuća su golema. Utjecao je na razvoj gotovo svih grana matematike i mehanike, kako u području fundamentalnih istraživanja tako i u njihovoj primjeni. Leonard Euler ne samo da je riješio ovaj poseban problem, već je također smislio opću metodu za rješavanje ovih problema. Euler je učinio sljedeće: "stisnuo" je zemlju u točke, a mostove "razvukao" u liniju. Rezultat je slika prikazana na slici.

Takav lik, koji se sastoji od točaka i linija koje spajaju te točke, naziva seračunati... Točke A, B, C, D nazivaju se vrhovi grafa, a linije koje spajaju vrhove su bridovi grafa. Na slici od vrhova B, C, D 3 ruba izlaze van, i to odozgo A - 5 rebara. Zovu se vrhovi iz kojih izlazi neparan broj bridovaneparni vrhovi, a vrhovi iz kojih izlazi paran broj bridova sučak.

2. Svojstva grafa.

Rješavajući problem o mostovima u Konigsbergu, Euler je utvrdio, posebno, svojstva grafa:

1. Ako su svi vrhovi grafa parni, onda graf možete nacrtati jednim potezom (tj. bez podizanja olovke s papira i bez crtanja dvaput duž iste linije). U tom slučaju, pokret može započeti s bilo kojeg vrha i završiti na istom vrhu.

2. Graf s dva neparna vrha također se može nacrtati jednim potezom. Kretanje treba započeti s bilo kojeg neparnog vrha i završiti na drugom neparnom vrhuncu.

3. Graf s više od dva neparna vrha ne može se nacrtati jednim potezom.

4. Broj neparnih vrhova grafa je uvijek paran.

5. Ako graf ima neparne vrhove, tada će najmanji broj poteza koji se može koristiti za crtanje grafa biti jednak polovini broja neparnih vrhova ovog grafa.

Na primjer, ako oblik ima četiri neparna broja, onda se može nacrtati s najmanje dva poteza.

U problemu sedam Königsbergovih mostova sva četiri vrha odgovarajućeg grafa su neparna, t.j. ne možete jednom prijeći sve mostove i završiti put gdje je započet.

3. Rješavanje zadataka pomoću grafova.

1. Zadaci za crtanje figura jednim potezom.

Pokušaji crtanja svakog od sljedećih oblika jednim potezom olovke dat će neujednačene rezultate.

Ako na slici nema neparnih točaka, onda se uvijek može crtati jednim potezom olovke, bez obzira na to gdje početi crtati. Ovo su slike 1 i 5.

Ako lik ima samo jedan par neparnih točaka, onda se takav lik može nacrtati jednim potezom, počevši od jedne od neparnih točaka (nije važno koju). Lako je shvatiti da bi crtež trebao završiti na drugoj neparnoj točki. To su slike 2, 3, 6. Na slici 6, na primjer, morate početi crtati ili od točke A ili od točke B.

Ako lik ima više od jednog para neparnih točaka, onda se uopće ne može nacrtati jednim potezom. To su slike 4 i 7, od kojih svaka sadrži dva para neparnih točaka. Rečeno je dovoljno da se nepogrešivo prepozna koje se figure ne mogu nacrtati jednim potezom, a koje mogu, kao i od koje točke treba krenuti u crtanje.

Predlažem da nacrtam sljedeće figure jednim potezom.

2. Rješavanje logičkih zadataka.

PROBLEM br. 1.

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 danas su već odigrane neke utakmice: Andrey je igrao s Borisom, Galinom, Elenom; Boris - s Andrejem, Galinom; Victor - s Galinom, Dmitrijem, Elenom; Galina - s Andrejem, Viktorom i Borisom. Koliko je utakmica do sada odigrano i koliko ih je ostalo?

RIJEŠENJE:

Napravimo graf kao što je prikazano na slici.

Odigrano 7 utakmica.

Na ovoj slici graf ima 8 bridova, dakle, preostalo je za odigrati 8 igara.

PROBLEM br. 2

U dvorištu, koje je ograđeno visokom ogradom, nalaze se tri kuće: crvena, žuta i plava. U ogradi su tri kapije: crvena, žuta i plava. Od crvene kuće vodi put do crvenih vrata, od žute kuće do žutih vrata, od plave do plave da se ti putevi ne sijeku.

RIJEŠENJE:

Rješenje problema prikazano je na slici.

3. Rješavanje riječnih zadataka.

Da biste riješili probleme pomoću metode grafa, morate poznavati sljedeći algoritam:

1. O kojem procesu problem govori?2. Koje vrijednosti karakteriziraju ovaj proces?3. Kakav je odnos između ovih veličina?4. Koliko je različitih procesa opisano u zadatku?5. Postoji li odnos između elemenata?

Odgovarajući na ova pitanja, analiziramo stanje problema i zapisujemo ga shematski.

na primjer ... Autobus je išao 2 sata brzinom od 45 km/h i 3 sata brzinom od 60 km/h. Kojom je rutom išao autobus u ovih 5 sati?

S
¹ = 90 km V ¹ = 45 km / h t ¹ = 2 h

S = VT

S ² = 180 km V ² = 60 km / h t ² = 3 h

S ¹ + S ² = 90 + 180

Riješenje:

1) 45 x 2 = 90 (km) - autobus je prošao za 2 sata.

2) 60 x 3 = 180 (km) - autobus je prošao za 3 sata.

3) 90 + 180 = 270 (km) - autobus je prošao za 5 sati.

Odgovor: 270 km.

III ... ZAKLJUČAK.

Kao rezultat rada na projektu saznao sam da je Leonard Euler bio utemeljitelj teorije grafova, rješavao probleme pomoću teorije grafova. Za sebe sam zaključio da teorija grafova nalazi primjenu u raznim područjima moderne matematike i njezinih brojnih primjena. Nema sumnje u korisnost upoznavanja nas studenata s osnovnim pojmovima teorije grafova. Mnoge matematičke probleme lakše je riješiti kada možete koristiti grafove. Prikaz podataka v oblik grafa im daje jasnoću. Mnogi se dokazi također pojednostavljuju, dobivaju uvjerljivost ako koristimo grafove. To posebno vrijedi za područja matematike kao što su matematička logika, kombinatorika.

Stoga je proučavanje ove teme od velikog općeobrazovnog, općekulturološkog i općematematičkog značaja. U svakodnevnom životu sve se više koriste grafičke ilustracije, geometrijski prikazi i druge tehnike i metode vizualizacije. U tu svrhu korisno je uvesti proučavanje elemenata teorije grafova u osnovnu i srednju školu, barem u izvannastavne aktivnosti, budući da ova tema nije uključena u nastavni plan i program matematike.

V ... BIBLIOGRAFIJA:

2008

Pregled.

Projekt na temu "Grafovi oko nas" proveo je učenik 7. "A" razreda MOU-škole br. 3, Krasny Kut Nikita Zaitsev.

Posebnost rada Nikite Zaitseva je njegova relevantnost, praktična usmjerenost, dubina teme, mogućnost korištenja u budućnosti.

Rad je kreativan, u obliku informativnog projekta. Učenik je ovu temu odabrao kako bi na primjeru rute školskog autobusa pokazao odnos teorije grafova s praksom, kako bi pokazao da se teorija grafova primjenjuje u raznim područjima moderne matematike i njezine brojne primjene, posebice u ekonomiji, matematičkoj logici, kombinatorici. . Pokazao je da je rješavanje problema uvelike pojednostavljeno ako je moguće koristiti grafove, prikaz podataka u obliku grafa daje im jasnoću, mnogi dokazi se također pojednostavljuju i postaju uvjerljivi.

Rad se bavi takvim pitanjima kao što su:

1. Pojam grafa. Problem Königsberških mostova.

2. Svojstva grafova.

3. Problemi primjene teorije grafova.

4. Značenje grafova.

5. Varijanta trase školskog autobusa.

Prilikom izvođenja svog rada, N. Zaitsev je koristio:

1. Alkhova Z.N., Makeeva A.V. "Izvannastavni rad iz matematike."

2. Časopis "Matematika u školi". Prilog "1. rujna" br.13

2008

3. Ya.I. Perelman "Zabavni zadaci i eksperimenti." - Moskva: Obrazovanje, 2000.

Rad je obavljen kompetentno, materijal ispunjava zahtjeve ove teme, priloženi su odgovarajući crteži.

Svrha studije :

Razmotriti mogućnosti korištenja grafskog aparata za rješavanje logičkih i kombinatornih problema.

Ciljevi istraživanja:

razmotriti rješavanje problema pomoću grafova;

naučiti prevoditi zadatke na jezik grafova;

usporediti tradicionalne metode rješavanja problema s metodama teorije grafova.

Relevantnost istraživanja:

Grafikoni se koriste u svim područjima našeg života. Poznavanje osnova teorije grafova potrebno je u raznim područjima vezanim uz upravljanje proizvodnjom, poslovanje (primjerice, raspored izgradnje mreže, rasporedi dostave pošte), izgradnju transportnih i dostavnih ruta te rješavanje problema. Grafovi se koriste u vezi s razvojem teorije vjerojatnosti, matematičke logike i informacijske tehnologije.

Hipoteza:

Korištenje teorije grafova čini rješavanje mnogih logičkih i kombinatornih problema manje vremena.

Sadržaj:

Uvod. Koncept grafa.

Osnovna svojstva grafa.

Osnovni pojmovi teorije grafova i njihovi dokazi.

Odabrani zadaci.

Kromatski broj grafa.

Književnost.

Uvod. Koncept grafa.

Svatko od nas je, naravno, u pravu,

Pronalaženje bez odlaganja,

Što je on ... običan grof

Od štapića i točkica.

Teorija grafova je trenutno grana diskretne matematike koja se intenzivno razvija. Grafovi i srodne metode istraživanja organski prožimaju gotovo svu modernu matematiku na različitim razinama. Jezik grafova je jednostavan, jasan i deskriptivan. Problemi s grafovima imaju niz prednosti koje im omogućuju da se koriste za razvoj razmatranja, poboljšanje logičkog razmišljanja i primjenu domišljatosti. Grafovi su prekrasni matematički objekti, uz njihovu pomoć možete riješiti mnogo različitih, naizgled različitih problema.

U matematici postoji cijeli dio - teorija grafova, koji proučava grafove, njihova svojstva i primjenu. Matematičke grafove s plemićkom titulom "grof" povezuje zajedničko podrijetlo od latinske riječi "grapio" - pišem. Tipični grafikoni su dijagrami zrakoplovnih prijevoznika koji se često objavljuju u zračnim lukama, karte metroa i željeznice na geografskim kartama. Odabrane točke grafa nazivaju se njegovim vrhovima, a linije koje ih povezuju nazivaju se bridovima. Jedan od grafova dobro je poznat Moskovljanima i gostima glavnog grada - ovo je shema moskovskog metroa: vrhovi su terminalne stanice i transfer stanice, rubovi su staze koje povezuju ove stanice. Genealoško stablo grofa L. N. Tolstoja je drugi graf. Ovdje su vrhovi preci pisca, a rubovi pokazuju odnos između njih.

sl. 1 sl. 2

Riječ "graf" u matematici označava sliku na kojoj je nacrtano nekoliko točaka, od kojih su neke povezane linijama. Prilikom prikazivanja grafa nije bitan položaj vrhova na ravnini, zakrivljenost i duljina bridova ( Slika 3). Vrhovi grafova su označeni slovima ili prirodnim brojevima. Rubovi grafa su parovi brojeva.

riža. 3

Grafovi su blok dijagrami računalnih programa, rasporedi izgradnje mreže, gdje su vrhovi događaji koji označavaju završetak rada na određenom mjestu, a rubovi koji povezuju ove vrhove su rad koji se može započeti nakon završetka jednog događaja i mora se izvesti kako bi se dovršite sljedeće.Svojstva grafova, kao i njihove slike, neće ovisiti i neće se mijenjati o tome jesu li vrhovi povezani segmentima ili zakrivljenim linijama. To omogućuje proučavanje njihovih svojstava uz pomoć jedne od mladih znanosti - topologije, iako su sami problemi teorije grafova tipični problemi kombinatorike.

Što povezuje topologiju i kombinatoriku? Teorija grafova dio je i topologije i kombinatorike. Činjenica da se radi o topološkoj teoriji proizlazi iz neovisnosti svojstava grafa od položaja vrhova i vrste linija koje ih povezuju. A pogodnost formuliranja kombinatornih problema u smislu grafova dovela je do činjenice da je teorija grafova postala jedan od najmoćnijih uređaja u kombinatorici.

Ali tko je smislio ove grafikone? Gdje se koriste? Jesu li svi isti ili postoje varijante?

Povijest nastanka teorije grafova. Klasični problem konigsberških mostova.

Temelje teorije grafova kao matematičke znanosti postavio je 1736. Leonard Euler, razmatrajući problem konigsberških mostova.“Ponuđen mi je problem o otoku koji se nalazi u gradu Königsbergu i okružen rijekom preko koje je prebačeno 7 mostova. Pitanje je može li ih netko kontinuirano zaobilaziti, prolazeći samo jednom kroz svaki most..." (Iz pisma L. Eulera talijanskom matematičaru i inženjeru Marinoniju od 13. ožujka 1736.)

Nekadašnji Konigsberg (danas Kalinjingrad) nalazi se na rijeci Pregel. Unutar gradskih granica rijeka pere dva otoka. Mostovi su bacani s obala na otoke. Stari mostovi nisu sačuvani, ali postoji karta grada na kojoj su prikazani (sl. 4). Stanovnici Konigsberga ponudili su posjetiteljima sljedeći zadatak: prijeći sve mostove i vratiti se na početnu točku, a svaki je most trebao biti obiđen samo jednom. Euleru je ponuđena i šetnja gradskim mostovima. Nakon neuspješnog pokušaja željenog zaobilaznog puta, nacrtao je pojednostavljeni dijagram mostova. Rezultat je graf čiji su vrhovi dijelovi grada odvojeni rijekom, a rubovi su mostovi (slika 5.).

riža. 4 sl. 5

Prije nego što je potkrijepio mogućnost tražene rute, Euler je razmotrio druge, složenije karte. Kao rezultat toga, dokazao je opću tvrdnju kako bi jednom mogao prijeći sve rubove grafa i vratiti se na izvorni vrh, potrebno je i dovoljno zadovoljiti sljedeća dva uvjeta:

od bilo kojeg vrha grafa mora postojati put duž njegovih bridova do bilo kojeg drugog vrha (grafovi koji zadovoljavaju ovaj zahtjev nazivaju se povezani);

iz svakog vrha mora izlaziti paran broj bridova.

“Stoga se moramo pridržavati sljedećeg pravila: ako je na bilo kojoj slici broj mostova koji vode do određenog područja neparan, tada se željeni prijelaz preko svih mostova u isto vrijeme ne može izvesti drugačije osim ako prijelaz ili počne ili završava na ovom području. A ako je broj mostova paran, iz toga ne može nastati nikakva poteškoća, jer ni početak ni kraj prijelaza u ovom slučaju nisu fiksirani. Iz ovoga slijedi sljedeće opće pravilo: ako postoji više od dva područja do kojih vodi neparan broj mostova, tada se željeni prijelaz uopće ne može napraviti. Jer čini se potpuno nemogućim da prijelaz i započne i završi u bilo kojem od ovih područja. A ako postoje samo dvije regije ove vrste (budući da se ne može dati jedna regija ove vrste ili neparan broj regija), tada se može napraviti prijelaz preko svih mostova, ali uz takav uvjet da je početak prijelaza u jednoj, a kraj u drugoj s ovih prostora. Kada se na predloženoj slici A i B nalaze područja do kojih vodi neparan broj mostova, a broj mostova koji vode do C paran, onda vjerujem da se prijelaz ili izgradnja mostova može dogoditi ako prijelaz počne bilo od A ili iz B, a ako netko želi započeti prijelaz iz C, onda nikada neće moći postići cilj. Na mjestu konigsberških mostova imam četiri područja A, B, C, D, međusobno odvojena vodom, do kojih vodi neparan broj mostova (slika 6.).

riža. 6

Slijedom toga, možete se uvjeriti, dragi mužu, da 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, za ovu odluku je podržan samo jednim obrazloženjem i nema potrebe uključivati bilo kakve zakone svojstvene matematici da bi se pronašlo ovo rješenje. Dakle, ne znam kako ispada da pitanja koja imaju vrlo malo veze s matematikom imaju veću vjerojatnost da će rješavati matematičari nego drugi [znanstvenici]. U međuvremenu, ti, najslavniji čovječe, određuješ mjesto ovog pitanja u geometriji situacije, a što se tiče ove nove znanosti, priznajem, ne znam kakvi su problemi u vezi s tim bili poželjni za Leibniza i Wolffa. Dakle, molim vas, ako mislite da sam sposoban stvoriti nešto u ovoj novoj znanosti, da se udostojite poslati mi neke konkretne zadatke u vezi s njom..."

Osnovna svojstva grafa.

Rješavajući problem o mostovima u Konigsbergu, Euler je ustanovio sljedeća svojstva grafa:

Ako su svi vrhovi grafa parni, graf možete nacrtati jednim potezom (tj. bez podizanja olovke s papira i bez crtanja dvaput duž iste linije).

Graf s dva neparna vrha također se može nacrtati jednim potezom. Kretanje treba započeti s bilo kojeg neparnog vrha, a završiti na drugom neparnom vrhuncu.

Graf s više od dva neparna vrha ne može se nacrtati jednim potezom.

Koncept Eulerovog i Hamiltonovog ciklusa.

Zatvoreni put koji jednom prolazi duž svih bridova još se naziva Eulerov ciklus.

Ako odbacimo uvjet povratka na izvorni vrh, onda možemo pretpostaviti da postoje dva vrha iz kojih izlazi neparan broj bridova. U tom slučaju, kretanje treba započeti s jednog od ovih vrhova, a završiti na drugom.

U problemu Konigsbergovih mostova sva četiri vrha odgovarajućeg grafa su neparna, što znači da je nemoguće prijeći sve mostove točno jednom i tamo završiti put.

Vrlo je lako dobiti graf na komadu papira. Trebate uzeti olovku i crtati po ovom komadu papira, bez podizanja olovke s papira i bez crtanja dvaput duž iste linije, bilo što. Označite točkama "raskrižja" te početne i krajnje točke, ako se ne poklapaju sa "raskrižjima". Dobivenu sliku možemo nazvati grafom. Ako se početna i krajnja točka slike poklapaju, tada će svi vrhovi ispasti parni, ako se početna i krajnja točka ne podudaraju, onda će ispasti neparni vrhovi, a svi ostali će biti parni.Rješenje mnogih logičkih zadataka uz pomoć grafova već je prilično dostupno mlađim učenicima. Da bi to učinili, trebaju imati samo intuitivne ideje o grafovima i njihovim najočitijim svojstvima.U mnogim dječjim zagonetkama možete pronaći takve zadatke: nacrtati lik bez podizanja olovke s papira i ne crtati dvaput duž iste linije.

riža. 7 a) b)

Slika 7 (a) ima dva vrha (donja) iz kojih izlazi neparan broj bridova. Stoga, crtež treba započeti s jednim od njih, a završiti u drugom. Na slici 7 (b) postoji Eulerov ciklus, budući da iz šest vrhova grafa izlazi paran broj bridova.

Godine 1859. Sir William Hamilton, poznati irski matematičar koji je svijetu dao teoriju kompleksnog broja i kvaterniona, predložio je neobičnu dječju zagonetku u kojoj je bilo predloženo napraviti "put oko svijeta" u 20 gradova koji se nalaze u različitim dijelovi zemaljske kugle (slika 8). U svaki vrh drvenog dodekaedra zabijen je karanfil, označen imenom jednog od poznatih gradova (Bruxelles, Delhi, Frankfurt itd.) i za jedan od njih vezan konac.Trebalo je povezati vrhove dodekaedar s tom niti tako da je prolazio uz njegove rubove, uvijajući svaki karanfil točno jedanput, i kako bi nastala trasa niti bila zatvorena (petlja).Svaki grad je bio povezan cestama s tri susjedna tako da je nastala prometna mreža 30 bridova dodekaedra, na čijim su se vrhovima nalazili gradovi a, b ... t. Preduvjet je bio da se svaki grad, s izuzetkom prvog, posjeti samo jednom.

riža. 8 sl. 9

Ako putovanje počinje iz grada a, tada posljednji gradovi moraju biti b, e ili h, inače se nećemo moći vratiti na izvornu točku a. Izravni proračun pokazuje da je broj takvih zatvorenih ruta 60. Možete zahtijevati da posjetite sve gradove točno jednom, uključujući i prvi, t.j. završetak putovanja dopušten je u bilo kojem gradu (primjerice, pretpostavlja se da će se na početnu točku moći vratiti avionom). Tada će se ukupan broj lančanih ruta povećati na 162 (slika 9).

Iste 1859. godine Hamilton je pozvao vlasnika tvornice igračaka u Dublinu da je pusti u proizvodnju. Vlasnik tvornice prihvatio je Hamiltonovu ponudu i platio mu 25 gvineja. Igračka je podsjećala na Rubikovu kocku, koja nije tako dugo bila vrlo popularna, a ostavila je zamjetan trag u matematici. Zatvorena putanja duž rubova grafa koja jednom prolazi kroz sve vrhove naziva se Hamiltonov ciklus. Za razliku od Eulerovog ciklusa, uvjeti za postojanje Hamiltonovog ciklusa na proizvoljnom grafu još nisu uspostavljeni.

Koncept cjelovitog grafa. Svojstva ravnih grafova.

Je li uvijek moguće prikazati graf na ravnini tako da mu se bridovi ne sijeku? Ispada da nije. Grafovi za koje je to moguće nazivaju se ravnim.Grafovi u kojima nisu izgrađeni svi mogući bridovi nazivaju se nepotpuni grafovi, a graf u kojem su svi vrhovi povezani na sve moguće načine naziva se potpuni graf.

riža. 10 sl. jedanaest

Slika 10 prikazuje graf s pet vrhova koji se ne uklapa u ravninu bez bridova koji sijeku. Svaka dva vrha ovog grafa povezana su bridom. Ovo je potpuni grafikon. Slika 11 prikazuje graf sa šest vrhova i devet bridova. Zove se "kuće - bunari". Dolazi iz drevne zagonetke – zagonetke. Tri prijatelja živjela su u tri kolibe. U blizini njihovih kuća bila su tri bunara: jedan sa slanom vodom, drugi sa slatkom vodom, a treći sa slatkom vodom. Ali jednom su se prijatelji posvađali, toliko da se nisu htjeli vidjeti. I odlučili su obnoviti puteve od kuća do bunara kako im se putevi ne bi križali. Kako to učiniti? Slika 12 prikazuje osam od devet putova, ali deveti više nije moguć.

sl. 12

Poljski matematičar Kazimierz Kuratovsky ustanovio je da ne postoje bitno različiti neravni grafovi. Točnije, ako graf "ne stane" u ravninu, onda barem jedan od ova dva grafa "sjedi" u njemu (potpuni graf s pet vrhova ili "kuća - bunara"), moguće s dodatnim vrhovima na rubovima .

Lewis Carroll, autor Alise u zemlji čudesa, volio je svojim prijateljima davati sljedeću zagonetku. Zamolio je da zaokruži lik prikazan na slici, bez podizanja olovke s papira i bez crtanja dvaput duž iste linije. Nakon što smo izračunali paritet vrhova, pobrinuli smo se da se ovaj problem lako riješi, a obilazak možete započeti s bilo kojeg vrha, budući da su svi parni. Međutim, on je otežao zadatak zahtijevajući da se linije ne sijeku pri maženju. S ovim problemom možete se nositi na sljedeći način. Obojite oblik tako da njegovi granični dijelovi budu različitih boja. Zatim odvajamo linije koje se sijeku tako da zasjenjeni dio bude jedan komad. Sada ostaje zaokružiti ispunjeno područje uz rub jednim potezom - to će biti željena linija (slika 13).

riža. trinaest

Osnovni pojmovi teorije grafova i njihov dokaz .

Ravni grafovi imaju mnoga zanimljiva svojstva. Dakle, Euler je otkrio jednostavan odnos između broja vrhova (B), broja bridova (P), broja dijelova (D) na koje graf dijeli ravninu

B - P + G = 2.

1. Definicija ... Broj bridova koji se protežu iz jednog vrha naziva se stupanj tog vrha.

Lema 1. Broj bridova u grafu je točno 2 puta manji od zbroja stupnjeva vrhova.

Dokaz. Svaki rub grafa povezan je s 2 vrha. Dakle, ako zbrojimo broj stupnjeva svih vrhova grafa, onda ćemo dobiti udvostručeni broj bridova, budući da svaki rub je brojen dvaput.

Lema2 . Zbroj stupnjeva vrhova grafa je paran .

Dokaz. Prema lemi 1, broj bridova u grafu je 2 puta manji od zbroja stupnjeva vrhova, pa je zbroj stupnjeva vrhova paran (djeljiv s 2).

2. Definicija ... Ako je stupanj vrha paran, tada se vrh naziva paran, ako stupanj nije paran, onda je vrh neparan.

Lema3 . Broj neparnih vrhova grafa je paran.

Dokaz. Ako graf sadržinčak ikneparnih vrhova, tada je zbroj stupnjeva parnih vrhova paran. Zbroj stupnjeva neparnih vrhova je neparan ako je broj tih vrhova neparan. Ali tada je i ukupan broj stupnjeva vrhova neparan, što ne može biti. Sredstva,kčak.

Lema 4. Ako cijeli graf ima n vrhova, tada će broj bridova biti

Dokaz. U kompletnoj kolumni sanvrhovi iz svakog vrha dolazen-1 rub. Dakle, zbroj stupnjeva vrhova jen ( n-jedan). Broj rubova je 2 puta manji, tj .

Odabrani zadaci.

Poznavajući svojstva grafa dobivenog Eulerom, sada je lako riješiti sljedeće probleme:

Problem 1. Od troje ljudi koji stoje u blizini, jedan uvijek govori istinu (ljubitelj istine), drugi uvijek laže (lažljivac), a treći, ovisno o okolnostima, govori ili istinu ili laž (diplomat). Pitali su onoga s lijeve strane: "Tko stoji do tebe?" On je odgovorio: "Istinoljubac." Čovjeku u centru postavljeno je pitanje: “Tko si ti?”, a on je odgovorio: “Ja sam diplomat”. Kada je osoba s desne strane upitana: "Ko stoji pored tebe?", rekao je: "Lažljivce." Tko je gdje stajao?

Riješenje: Ako u ovom problemu rub grafa odgovara mjestu koje zauzima ova ili ona osoba, tada nam mogu biti predstavljene sljedeće mogućnosti.

Razmotrimo prvu mogućnost. Ako je “ljubitelj istine” s lijeve strane, onda je pored njega, sudeći po njegovom odgovoru, i “ljubitelj istine”. Imamo "lažljivca". Posljedično, ovaj raspored ne zadovoljava uvjet problema. Razmotrivši sve druge mogućnosti na ovaj način, doći ćemo do zaključka da pozicija "diplomata", "lažljivca", "istinoljubca" zadovoljava zadatak. Doista, ako je "istinoljubac" s desne strane, onda je, prema njegovom odgovoru, pored njega "lažljivac", što se i ispunjava. Onaj koji stoji u sredini izjavljuje da je "diplomat" i, dakle, laže (što je moguće iz uvjeta), a laže i onaj s desne strane. Time su ispunjeni svi uvjeti problema.

Zadatak 2. U 10-znamenkastom broju svake dvije uzastopne znamenke tvore dvoznamenkasti broj koji je djeljiv s 13. Dokažite da među tim znamenkama nema znamenke 8.

Riješenje. Postoji 7 dvoznamenkastih brojeva koji su djeljivi s 13. Označimo te brojeve točkama i primijenimo definiciju grafa. Pod uvjetom, svake 2 uzastopne znamenke tvore dvoznamenkasti broj, koji su djeljivi s 13, što znači da se znamenke koje čine 10-znamenkasti broj ponavljaju. Vrhove grafa povezujemo s bridovima tako da se brojevi uključeni u ovaj graf ponavljaju.

13 65

91 39 52

Iz konstruiranih grafova se vidi da među znamenkama 10-znamenkastog broja znamenka 8 ne može biti.

Zadatak 3. U selu ima 10 kuća, a svaka od njih ima 7 staza koje vode do drugih kuća. Koliko staza ima između kuća?

Riješenje. Neka su kuće vrhovi grafa, putevi bridovi. Prema uvjetu, 7 putova (brova) napušta svaku kuću (vrh), tada je stupanj svakog vrha 7, zbroj stupnjeva vrhova je 7 × 10 = 70, a broj bridova je 70: 2 = 35. Dakle, između kuća prolazi 35 staza.

Zadatak 4: Uvedena je svemirska komunikacija između 9 planeta Sunčevog sustava. Rakete lete na rutama: Zemlja-Merkur, Pluton-Venera, Zemlja-Pluton, Pluton-Merkur, Merkur-Venera, Uran-Neptun, Neptun-Saturn, Saturn-Jupiter, Jupiter-Mars i Mars-Uran. Je li moguće doći sa Zemlje na Mars?

Riješenje. Nacrtajmo dijagram: planeti će odgovarati točkama, a rute koje ih povezuju imat će linije koje se ne sijeku.

Nakon što smo napravili skicu crteža ruta, nacrtali smo graf koji odgovara stanju problema. Može se vidjeti da su svi planeti Sunčevog sustava podijeljeni u dvije nepovezane skupine. Zemlja pripada jednoj skupini, a Mars drugoj. Nemoguće je letjeti sa Zemlje na Mars.

Klasični "problem trgovačkog putnika". Pohlepni algoritmi.

Jedan od klasičnih problema u teoriji grafova naziva se "problem trgovačkog putnika" ili "problem trgovačkog putnika". Zamislite prodavača koji mora posjetiti nekoliko gradova i vratiti se nazad. Poznato je koje ceste povezuju ove gradove i kolike su udaljenosti ovih gradova uz te prometnice. Morate odabrati najkraći put. Ovo nije "igrački" zadatak. Na primjer, vozač poštanskog automobila koji preuzima pisma iz poštanskih sandučića volio bi znati najkraći put, kao i vozač kamiona koji dostavlja robu na kioske. I prilično je teško riješiti ovaj problem, jer je broj vrhova u grafu vrlo velik. I ovdje je još jedan problem, u određenom smislu suprotan problemu trgovačkog putnika. Planira se izgradnja željeznice koja će povezati nekoliko velikih gradova. Za bilo koji par gradova poznata je cijena izgradnje staze između njih. Potrebno je pronaći najjeftiniju opciju gradnje. Zapravo, algoritam za pronalaženje optimalne opcije konstrukcije prilično je jednostavan. Pokažimo to na primjeru ceste koja povezuje pet gradova A, B, C,Di E. Trošak polaganja puta između svakog para gradova prikazan je u tablici (slika 14), a položaj gradova na karti (slika 15)

1,5

2,5

1,5

1,2

0,8

1,2

1,1

0,9

1,1

2,7

2,5 5

je, a položaj gradova svakog paroida A, B C kamiona, različit

0,8

0,9

2,7

A A

D D

sl. 14 sl. 15

Prvo, gradimo cestu koja ima najnižu cijenu. Ovo je put B → E. Sada ćemo pronaći najjeftiniju liniju koja povezuje B ili E s bilo kojim od gradova. Ovo je put između E i C. Uključujemo ga u dijagram. Dalje, radimo isto - tražimo najjeftiniji put koji povezuje jedan od gradova B, C, E s jednim od preostalih - A iliD... Ovo je cesta između C i A. Ostaje spojiti grad na željezničku mrežuD.

Najjeftiniji način je spojiti ga na S. Dobivamo mrežu željezničkih kolosijeka (slika 16.).

riža. šesnaest

Ovaj algoritam za pronalaženje optimalne opcije za izgradnju željeznice spada u kategoriju "pohlepnih": na svakom koraku rješavanja ovog problema biramo najjeftiniji nastavak puta. Za ovaj zadatak savršeno odgovara. Ali u problemu trgovačkog putnika, "pohlepni" algoritam neće dati optimalno rješenje. Ako od samog početka odaberete "najjeftinije" elemente, t.j. najkraće udaljenosti, moguće je da ćete na kraju morati koristiti vrlo "skupe" - duge, a ukupna duljina rute bit će znatno veća od optimalne.

Dakle, da biste riješili neke probleme, možete koristiti metodu ili algoritam koji se zove "pohlepan". "Greedy" algoritam - algoritam za pronalaženje najkraće udaljenosti odabirom najkraćeg, još neodabranog ruba, pod uvjetom da ne čini ciklus s već odabranim rubovima. Ovaj algoritam se naziva “gramzivim” jer je u posljednjim koracima potrebno skupo platiti pohlepu. Pogledajmo kako se pohlepni algoritam ponaša pri rješavanju problema trgovačkog putnika. Ovdje će se pretvoriti u strategiju “idi u najbliži (koji još nije ušao) grad”. Pohlepni algoritam je očito nemoćan u ovom zadatku. Razmotrimo, na primjer, mrežu na slici 17, koja je uski dijamant. Neka trgovački putnik krene od grada 1. Algoritam "idi u najbliži grad" odvest će ga u grad 2, zatim 3, pa 4; na posljednjem koraku morat ćete platiti za pohlepu vraćanjem duž duge dijagonale romba. Rezultat nije najkraći, već najduži krug. Međutim, u nekim situacijama "pohlepni" algoritam ipak određuje najkraći put.

4 3

riža. 17

Postoji još jedan način rješavanja slični zadaci- brute force metoda (ponekad kažu brute force method, podrazumijevajući brute force nabrajanje - to nije sasvim točno, budući da brute force pretraga možda nije potpuna), koja se sastoji u nabrajanju svih mogućih kombinacija točaka (odredišta). Kao što je poznato iz matematike, broj takvih permutacija je n !, gdje je n broj točaka. Budući da se u problemu trgovačkog putnika obično pretpostavlja da je polazna točka ista (prva točka), dovoljno nam je nabrojati preostale, t.j. broj permutacija bit će (n – 1) !. Ovaj algoritam gotovo uvijek daje točno rješenje za problem trgovačkog putnika, ali trajanje takvih izračuna može biti pretjerano dugo. Poznato je da za vrijednosti n> 12 moderno računalo nije moglo riješiti problem trgovačkog putnika čak ni tijekom cijelog postojanja svemira. Postoje i drugi algoritmi za rješavanje problema trgovačkog putnika, koji su puno točniji od "pohlepnog" algoritma i puno brži od metode grube sile. Međutim, razmatramo grafove, a ove metode nisu povezane s teorijom grafova.

Kromatski broj grafa.

Problem bojanja geografske karte

Daje se zemljopisna karta koja prikazuje zemlje razdvojene granicama. Kartu je potrebno obojiti tako da zemlje sa zajedničkim rubnim dijelovima budu obojane različitim bojama, te da se koristi minimalan broj boja.

Koristeći ovu kartu, gradimo graf na sljedeći način. Stavimo u korespondenciju sa zemljama karte vrhove grafa. Ako neke dvije zemlje imaju zajednički granični dio, tada odgovarajuće vrhove povezujemo bridom, inače - ne. Lako je vidjeti da boja karte odgovara ispravnom bojanju vrhova rezultirajućeg grafa, a minimalni broj potrebnih boja jednak je kromatskom broju ovog grafa.

Kromatski broj grafa je najmanji broj boja koji se može koristiti za bojanje vrhova grafa tako da se bilo koja dva vrha povezana bridom obojaju različitim bojama. Dugo vremena matematičari nisu mogli riješiti takav problem: jesu li četiri boje dovoljne da obojaju proizvoljnu geografsku kartu tako da bilo koje dvije zemlje koje imaju zajednička granica bili obojeni različitim bojama? Ako zemlje prikažemo točkama - vrhovima grafa, povezujući bridovima one vrhove za koje graniče odgovarajuće zemlje (slika 18), onda će se problem svesti na sljedeće: je li istina da kromatski broj bilo kojeg graf koji se nalazi na ravnini nije veći od četiri? Pozitivan odgovor na ovo pitanje tek je nedavno dobiven uz pomoć računala.

riža. osamnaest

Igra "četiri boje"

Stephen Barr je predložio papirnatu slagalicu za dva igrača pod nazivom Četiri boje. Riječima Martina Gardnera - "Ne znam bolji način da shvatim poteškoće na koje se susreću na putu rješavanja problema četiri boje od jednostavnog igranja ove neobične igre"

Ova igra zahtijeva četiri olovke u boji. Prvi igrač započinje igru crtanjem proizvoljnog praznog područja. Drugi igrač ga boji bilo kojom od četiri boje i zauzvrat crta svoje prazno područje. Prvi igrač boji područje drugog igrača i dodaje novo područje, i tako dalje - svaki igrač boji protivničko područje i dodaje svoje. U tom slučaju, područja koja imaju zajedničku granicu trebaju biti obojana različitim bojama. Onaj tko će na svoj red biti prisiljen uzeti petu boju gubi.

Kombinatorski i logički problemi.

Godine 1936. njemački matematičar D. Koenig prvi je proveo istraživanje takvih shema i predložio da se takve sheme nazovu "grafovima" i sustavno proučavaju njihova svojstva. Dakle, kao zasebna matematička disciplina, teorija grafova je predstavljena tek 30-ih godina dvadesetog stoljeća zbog činjenice da su u upotrebu ušli takozvani "veliki sustavi", t.j. sustavi s velikim brojem objekata međusobno povezanih različitim omjerima: željezničke i zračne mreže, telefonski centri za više tisuća pretplatnika, sustavi tvornica - potrošača i poduzeća - dobavljača, radio krugovi, velike molekule itd. itd. Postalo je jasno da je nemoguće razumjeti funkcioniranje takvih sustava bez proučavanja njihovog dizajna, njihove strukture. Tu je teorija grafova dobro došla. Sredinom 20. stoljeća problemi teorije grafova počeli su se javljati i u čistoj matematici (u algebri, topologiji, teoriji skupova). Da bi se teorija grafova mogla primijeniti na tako raznolika područja, ona mora biti visoko apstraktna i formalizirana. Danas doživljava eru brzog preporoda. Grafovi se koriste: 1) u teoriji planiranja i upravljanja, 2) u teoriji rasporeda, 3) u sociologiji, 4) u matematičkoj lingvistici, 5) u ekonomiji, 6) u biologiji , 7) kemija, 8) medicina , 9) u područjima primijenjene matematike kao što su teorija automata, elektronika, 10) u rješavanju probabilističkih i kombinatornih problema itd. Najbliži grafovima su topologija i kombinatorika.

Kombinatorika (Kombinatorna analiza) je grana matematike koja proučava diskretne objekte, skupove (kombinacije, permutacije, smještaj i nabrajanje elemenata) i odnose na njima (primjerice, djelomični red). Kombinatorika je povezana s mnogim drugim područjima matematike – algebrom, geometrijom, teorijom vjerojatnosti i ima širok raspon primjena u raznim područjima znanja (primjerice, u genetici, informatici, statističkoj fizici). Pojam "kombinatorika" u matematičku je upotrebu uveo Leibniz, koji je 1666. objavio svoje djelo "Razgovori o kombinatornoj umjetnosti".

Teorija grafova je široko razvijena od 50-ih godina. 20. stoljeće u vezi s formiranjem kibernetike i razvojem računalne tehnologije. IK. Berzh, O. Ore, A. Zykov radili su na grafovima modernih matematičara.

Grafovi se često koriste za rješavanje logičkih problema povezanih s nabrajanjem opcija. Na primjer, razmotrite sljedeći problem. U kanti je 8 litara vode, a tu su dva lonca zapremnine 5 i 3 litre. potrebno je u lonac od pet litara uliti 4 litre vode i ostaviti 4 litre u kanti, odnosno uliti vodu podjednako u kantu i veliku posudu. Situacija u svakom trenutku može se opisati s tri broja, pri čemu je A broj litara vode u kanti, B je u velikoj posudi, C je u manjoj. U početnom trenutku situacija je bila opisana trojkom brojeva (8, 0, 0), iz koje možemo prijeći u jednu od dvije situacije: (3, 5, 0), ako napunimo veliki lonac vodom, ili (5,0, 3), ako napunite manji lonac. Kao rezultat dobivamo dva rješenja: jedno u 7 poteza, drugo u 8 poteza.

Razmotrite probleme koji se lako mogu riješiti crtanjem grafa.

Problem broj 1. Andrej, Boris, Viktor i Grgur igrali su šah. Svaki je sa svakim igrao po jednu utakmicu. Koliko je utakmica odigrano?

Zadatak je riješen korištenjem cjelovitog grafa s četiri vrha A, B, C, D, označena prvim slovima imena svakog od dječaka. U punom grafu nacrtane su sve vrste bridova. U ovom slučaju, segmenti linije predstavljaju odigrane šahovske partije. Iz slike se vidi da graf ima 6 bridova, što znači da je odigrano 6 partija.

Odgovor: 6 utakmica.

Problem broj 2. Andrey, Boris, Victor i Grigory su jedni drugima poklonili svoje fotografije za uspomenu. Štoviše, svaki je dječak svakom od svojih prijatelja dao po jednu fotografiju. Koliko je fotografija ukupno donirano?

Rješenje je jednostavno ako nacrtate graf:

1 način. Strelice na rubovima kompletnog grafikona pokazuju proces razmjene fotografija. Očito, strelice su 2 puta veće od rubova, t.j. 12.

Metoda 2. Svaki od 4 dječaka dao je prijateljima po 3 fotografije, tako da su predstavljene ukupno 34 = 12 fotografija.

Odgovor: 12 fotografija.

Zadatak broj 3. Poznato je da svako od tri prezimena djevojčica počinje istim slovom kao i ime. Anyino prezime je Anisimov. Katjino prezime nije Karev, a Kirino nije Krasnova. Kako se preziva svaka od djevojaka?

Rješenje: Prema uvjetu zadatka sastavite graf čiji su vrhovi imena djevojčica. Puna linija će označavati da zadano prezime odgovara djevojci, a točkasta - što ne odgovara. Iz uvjeta zadatka jasno je da se Anya preziva Anisimov (dvije odgovarajuće točke povezujemo punom linijom). Iz ovoga proizlazi da se Katya i Kira ne prezivaju Anisimov. Budući da Katya nije Anisimova ili Kareva, znači da je Krasnova. Ostaje da se Kira preziva Karev. Odgovor: Anya Anisimova, Katya Krasnova, Kira Kareva.

Graf je skup objekata s vezama između njih. Objekti su predstavljeni kao vrhovi, ili čvorovi grafa (označeni su točkama), a veze su predstavljene kao lukovi ili bridovi. Ako je jednosmjerni odnos na dijagramu označen linijama sa strelicama, ako je dvosmjerni odnos između objekata na dijagramu označen linijama bez strelica. Glavni smjer rada s kombinatornim problemima je prijelaz s izvođenja slučajnog nabrajanja opcija na provođenje sustavnog nabrajanja. Problemi ovog tipa mogu se jasnije riješiti uz pomoć grafa.

Mnoge je logičke probleme lakše riješiti pomoću grafova. Grafovi vam omogućuju vizualni prikaz stanja problema i stoga značajno pojednostavljuju njegovo rješenje.

Zadatak broj 4. Pristupnik fizikalne matematike mora položiti tri prijemna ispita po desetbodovnom sustavu. Na koliko načina može položiti ispite za upis na sveučilište ako je prolazna ocjena te godine bila 28?

Riješenje. Za rješavanje ovog problema, kao iu mnogim drugim kombinatornim i probabilističkim problemima, pokazalo se učinkovitim organizirati elemente analiziranog skupa u obliku stabla. Iz jednog odabranog vrha izvlače se bridovi koji odgovaraju ocjeni na prvom ispitu, a zatim se na njihove krajeve dodaju novi bridovi koji odgovaraju mogućim rezultatima drugog, a zatim i trećeg ispita.

Dakle, za upis na fiziku i matematiku možete položiti prijemne ispite na 10 različitih načina.

Graf stabla je tako nazvan zbog svoje sličnosti sa stablom. Brojanje opcija puno je lakše s grafom stabla. Također je korisno nacrtati stablo varijacija kada želite zapisati sve postojeće kombinacije elemenata.

Problem broj 5. Na jednom udaljenom otoku žive dva plemena: vitezovi (koji uvijek govore istinu) i lopovi (koji uvijek lažu). Mudrac putnik ispričao je sljedeću priču. “Kada sam doplovio na otok, upoznao sam dvojicu lokalnih stanovnika i htio sam znati iz kojeg su plemena. Pitao sam prvog: "Jeste li obojica vitezovi?" Ne sjećam se je li odgovorio "da" ili "ne", ali iz njegovog odgovora nisam mogao jednoznačno odrediti tko je od njih tko. Tada sam istog stanovnika upitao: "Jeste li iz istog plemena?" Opet, ne sjećam se je li odgovorio s da ili ne, ali nakon ovog odgovora odmah sam pogodio tko je od njih tko. Koga je mudrac upoznao?

Riješenje:

Odgovor: prvi odgovor je "da", drugi odgovor je "ne" - mudrac je susreo dva lopova.

Zaključak. Primjena teorije grafova u različitim područjima znanosti i tehnologije.

Inženjer crta električne krugove.

Kemičar crta strukturne formule kako bi pokazao kako su atomi u složenoj molekuli međusobno povezani pomoću valentnih veza. Povjesničar prati genealoške veze duž obiteljskog stabla. Zapovjednik mapira komunikacijsku mrežu kroz koju se pojačanja dopremaju sa stražnje strane prema prednjim postrojbama.

Sociolog koristi složeni dijagram kako bi pokazao kako su različiti odjeli jedne velike korporacije međusobno podređeni.

Što je zajedničko svim ovim primjerima? Svaki od njih sadrži graf.

Jezikom teorije grafova formiraju se i rješavaju mnogi tehnički problemi, problemi iz područja ekonomije, sociologije, menadžmenta itd. Grafovi se koriste za vizualizaciju objekata i odnosa između njih.

Teorija grafova također uključuje niz matematičkih problema koji do danas nisu riješeni.

Književnost.

“Enciklopedija za djecu. T.11. Matematika" / Ed. M.D.Aksyonova / Izdavački centar "Avanta +", 1998.

"Iza stranica udžbenika matematike" Comp. S. A. Litvinova. 2. izd., dopunjeno. - M.: Globus, Volgograd: Panorama, 2008.

Grafovi // Kvant. -1994.- br.6.

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

A. A. Zykov Osnove teorije grafova M .: Vuzovskaya kniga, 2004.

Melnikov O.I. Zabavni problemi u teoriji grafova Izdavačka kuća: TetraSystems, 2001.

Berzh K. Teorija grafova i njezine primjene. Moskva: IL, 1962.

Materijali iz Wikipedije - slobodne enciklopedije.

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 u 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 temu. 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

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 .

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, razmotrite proizvoljnu kartu, koja je predstavlja u obliku grafa: glavni gradovi država su vrhovi grafa, a rubovi grafa povezuju one vrhove (glavne strane), čije države imaju zajedničku granicu . 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 stavio je na tržište slagalicu - drveni dodekaedar (dodecahedron), č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 željenih struktura (homologa dane tvari) jednak broju stabala čiji stupnjevi vrhova ne prelaze 4. Ovaj se problem svodi na problem nabrajanja stabala određenog tipa. 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 stvaranje tiskanih krugova (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, tada 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 bakterijske populacije), financijeri (rizici 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

Grafovi u istraživačkom radu arhitekture. Istraživački rad "pronalaženje najkraćeg puta"

I. Uvod

Ove godine sudjelovao sam na olimpijadi iz matematike na daljinu. Predložio je sljedeći problem:

1. Povijest nastanka teorije grafova.

3. Neki problemi u teoriji grafova.

Algoritam za rješavanje

Problemi s labirintom

Preporučite druge članke

Što je učenje na daljinu?

Visoka strukovna škola "Moskovia" u selu