Povijest nastanka i razvoja teorije grafova. Teorija grafova: osnovni pojmovi i zadaci

Povijest nastanka i razvoja teorije grafova 1736., Leonard Euler, problem konigsberških mostova (G. Konigsberg se nalazi na obali rijeke Pregel, u gradu postoji 7 mostova. jednom?) o Sredinom 19. stoljeća , G. Kirchhoff, opis korištenjem grafova električnih krugova, A. Cayley kemijskih shema o Kako je nastala matematička disciplina sredinom 30-ih. XX. stoljeće (1936, objavljeno o

Područja primjene teorije grafova skup objekata i veza između njih. Na primjer, putokaz - kao veza između naselja, raznih veza i odnosa među ljudima, događajima, državama i općenito između bilo kojih objekata Brojne zagonetke i igre na

o Zagonetke u kojima je potrebno ocrtati određenu figuru bez prekidanja ili ponavljanja redaka, na primjer ili Muhamedove sablje

Osnovne definicije o o o Graf je unija konačnog broja točaka i pravaca koji povezuju neke od točaka. Točke se nazivaju vrhovima grafa, a linije koje ih povezuju se nazivaju bridovima. Broj bridova koji izlaze iz vrha naziva se stupanj ovog vrha

Primjeri grafova o o Kostur bilo kojeg poliedra u prostoru Shema linija u metrou Strukturne formule molekule obiteljsko stablo

Primjeri zadataka riješenih uz pomoć grafikona 1. Putnici o U turističkom uredu izrađuju rutu za putnike koji žele putovati od grada A do grada B, nakon što su vidjeli sve atrakcije koje se nalaze u gradovima C, D, E, F, G, H usput, K, M. Potrebno je sastaviti itinerar putovanja na način da turisti obiđu sve naznačene gradove i svaki od njih obiđu točno jednom.

o Prema uvjetu problema, putovanje treba započeti u točki A i završiti u točki B. Imajte na umu da postoje samo dvije ceste koje vode do gradova D i F. To znači da će putnici sigurno proći tim cestama. Označimo ih podebljanom linijom. Ovo definira dio CDEFG rute. To znači da turisti neće prolaziti cestama AE, AG, EM (inače će točku E posjetiti dva puta). Prekrižimo ove ceste. Označimo dionicu AC podebljanom linijom, jer je od A ostala samo ova cesta. Prekrižimo CM (već smo bili na C). Kroz M su ostale nepređene dvije ceste: MH i MB, što znači da će njima ići turisti. Označimo ih podebljanom linijom. Ostao je samo jedan način da dođete od G do H

o Tako smo pronašli pravi put. U tome nam je pomogao raspored gradova i cesta, koji je zapravo graf s 10 vrhova i 17 bridova. Vrhovi A, D, F su stupnja dva, vrhovi C i K su stupnja tri, H, M, B su vrhovi četvrtog stupnja, a G i E su stupnja pet.

2. Izlasci o Može li se dogoditi da u društvu od 8 ljudi svi znaju točno još dvoje ljudi?

2. Poznanici (rješenje) o o Spojimo članove društva s vrhovima grafa, povežimo dva vrha bridom, ako su odgovarajuće dvije osobe međusobno poznate. Da bi svi bili upoznati s točno dvije osobe, svaki vrh grafa mora imati stupanj 2. Primjeri takvih grafova: Budući da takvi grafovi postoje, onda je moguća situacija opisana u problemu.

3. Šahovski turnir o Neka n šahista sudjeluje na turniru, svi moraju odigrati jedni s drugima točno jednu partiju. Dodijelimo svakom sudioniku vrh grafa, a svakom odigranom pariji rub grafa koji povezuje odgovarajuće vrhove

Kompletan graf o o o Prije početka turnira graf se sastoji samo od bodova, nema niti jedan rub. Takvi grafovi se nazivaju null-grafovi.Na kraju turnira svaki je sudionik igrao s bilo kojim drugim, a svaki par vrhova je povezan bridom. Takav graf se naziva potpunim. U potpunom grafu s n vrhova, stupanj svakog vrha je (n-1) Nepotpun graf se može pretvoriti u potpun graf dodavanjem bridova koji nedostaju. Na sl. debela linija predstavlja graf s 5 vrhova, koji nije potpun. Dodavanjem

Usmjereni graf ooo Često veze između objekata karakterizira određena orijentacija (šema jednosmjernih puteva, podređenost ili senioritet u odnosima među ljudima, rezultati susreta među timovima u sportu) Graf šahovskog turnira koji smo prikazali čini ne dati informacije o tome tko je pobijedio u svakoj igri. Moguće je staviti strelicu na svaki rub od vrha A do vrha B ako je šahist A izgubio od šahista B, odnosno orijentirati bridove pokazujući im smjer Graf na kojem je označen smjer svakog brida je pozvao

o Graf koji sadrži i usmjerene i neusmjerene bridove naziva se mješovitim (na primjer, graf šahovskog turnira u kojem su neke partije završile neriješenim rezultatom. Neriješenom rezultatu povezujemo rub bez strelice)

Ruta grafa o o o Ruta duljine m proizvoljnog grafa je niz od m bridova (ne nužno različitih) u kojima se granični vrhovi dvaju susjednih bridova podudaraju. Duljina rute - broj bridova (ako hodamo duž ruba 2 puta, tada brojimo ovaj rub 2 puta) Ruta je zatvorena ako joj se početni i konačni vrh podudaraju Lanac je otvorena ruta u kojoj su svi rubovi različiti Jednostavni lanac je lanac u kojem su svi vrhovi različiti (primjer - zadatak 1. (O putnicima)

Petlje, povezani grafovi o o o Petlja je zatvorena ruta u kojoj su svi bridovi različiti. Jednostavan ciklus je ciklus u kojem su svi vrhovi različiti (npr. problem datiranja. Prvi graf sadrži jedan jednostavan ciklus, drugi i treći - po dva jednostavna ciklusa) Graf se naziva povezanim ako postoji ruta s bilo kojeg njegovog vrha na bilo koji drugi, a na drugi način isključen (na primjer, problem poznanstava, prvi graf je povezan, svaka osoba može upoznati ostatak preko svojih poznanika, drugi i treći su nepovezani, stranci će ostati u tvrtka)

o o o o B-D-A-C-D-A - otvoren ruta A-C-D-A-B-D-A- zatvorena ruta A-C-D-E-F-D-B - lanac A-B-G-H - jednostavan lanac A-C-D-E-F-D-A - ciklus D-E-F-D- jednostavan ciklus Izračunajte duljinu ovih ruta Odredite vrstu ruta A-B-D-F-E-D-C-A; A-D-E; D-E-F-D; A-C-D-B-A;

Stabla o o Stablo je povezani graf koji nema cikluse Obiteljsko stablo, datotečni sustav itd.

Zadatak 4. Podjela na dijelove o Izrežite list papira na 3 dijela. Dio dobivenih listova ponovno prerežite na 3 dijela. Neki od izrezanih listova - opet na tri dijela, itd. Koliko će se pojedinačnih listova dobiti ako se napravi k rezova?

Zadatak 4. Podjela na dijelove (rješenje) o o Listovi papira na vrhu grafikona. Zasjenjeni vrhovi odgovaraju rezanim listovima, neobojeni - neobrezani. Kada se izreže jedan list, broj listova se povećava za 2. Ako je ukupno odrezano k listova, tada će se broj listova povećati za 2 k. Prvotno smo imali jedan list. , pa nakon k rezova dobijete (2 k + 1) listova. Grafikon ilustrira slučaj kada je k = 6. (2 k + 1) = 13

Teorem o zbroju stupnjeva vrhova grafa o o Neka graf Γ ima N vrhova i M bridova. Svaki i-ti vrh ima stupanj di Budući da svaki brid povezuje dva vrha, on dodaje dva zbroju stupnjeva vrhova grafa, pa je zbroj stupnjeva vrhova jednak dvostrukom broju bridova

Problem 5. Broj cesta o Može li država s točno 3 ceste napustiti svaki grad imati točno 100 cesta?

Zadatak 5. Broj cesta (rješenje) o Pretpostavimo da je takva situacija moguća. U državi postoji N gradova, iz svakog grada izlaze 3 ceste. Dakle, imamo graf s N vrhova, od kojih svaki ima stupanj 3. Dakle, zbroj stupnjeva vrhova je 3 N, a broj bridova je 3 N / 2. Ovaj broj je uvjetno jednak 100. To jest, 3 N / 2 = 100 ili 3 N = 200. Ne postoji takav prirodni broj. To znači da u ovoj državi ne može biti 100 cesta.

Samostalno o U određenom kraljevstvu, kralj je izdao dekret: izgraditi 7 gradova i povezati ih cestama tako da iz svakog grada izlaze 3 ceste. Hoće li se takva naredba poštivati? Hoće li to biti izvedivo ako iz svakog grada napuste 4 ceste?

Zadatak 6. O mostovima u Konigsbergu o G. Konigsberg se nalazi na obali rijeke Pregel, u gradu 7 mostova. Je li moguće prošetati da izađete iz kuće i vratite se natrag, prelazeći svaki most samo jednom?

Rješenje zadatka konigsberških mostova o o o Označimo dijelove grada A, B, C, D. To će biti vrhovi grafa. Mostovi koji povezuju dijelove grada su rubovi grafa. Euler je pokazao da problem nema rješenja, odnosno ne postoji ciklus koji prolazi duž svih bridova točno jednom. Uostalom, da postoji takav ciklus, tada bi u svakom vrhu grafa bilo onoliko bridova koji ulaze u njega koliko i izlaze iz njega, odnosno na svakom vrhu grafa bio bi paran broj bridova (koji bi ušli u vrh jedan rub po jedan, moramo izaći iz njega uz drugi rub). Međutim, ovaj uvjet očito nije zadovoljen za graf koji predstavlja Königsberg grafikon. Provjerite to određivanjem stupnja svakog vrha grafa.

Eulerov graf o o Nakon što je iznio rješenje problema Königsbergovih mostova, Euler se u svom radu osvrnuo na sljedeći opći problem teorije grafova: na kojim se grafovima može pronaći ciklus koji sadrži sve bridove grafa, i svaki brid točno jednom? Takav ciklus naziva se Eulerov pravac ili Eulerov ciklus, a graf s Eulerovom linijom naziva se Eulerov graf. Dakle, Eulerov graf se može u potpunosti prijeći prelaskom svakog ruba samo jednom. Stoga se Eulerovi grafovi mogu konstruirati bez podizanja olovke s papira i bez povlačenja iste linije dvaput.

Neophodan i dovoljan uvjet za postojanje Eulerovog grafa o o o Da bi graf imao Eulerovu liniju, mora biti povezan. Kao iu problemu Königsbergovih mostova, jasno je da svaki Eulerov pravac mora ulaziti i izlaziti iz svakog vrha isti broj puta, tj. stupnjevi svih vrhova grafa moraju biti parani. To znači da bi graf bio Euler, potrebna su dva uvjeta: povezanost grafa i ravnomjernost stupnjeva svih njegovih vrhova. Euler je dokazao da su i ovi uvjeti dovoljni: povezani graf s parnim stupnjevima svih vrhova ima Eulerovu liniju.

Sami o Odredite jesu li ovi grafovi Eulerovi? (da li ih je moguće zaokružiti jednim potezom olovke, bez prekidanja ili ponavljanja linija, i vratiti se na točku od koje ste krenuli) Ako jeste, pronađite u njima Eulerove cikluse (pokažite kako se to radi)

Eulerov put o o Eulerov put je put kada se svi bridovi prijeđu jednom, ali bez povratka na početnu točku. Ako graf nema Eulerov ciklus, onda možemo postaviti problem pronalaženja Eulerove staze

Dovoljan uvjet za postojanje Eulerove staze o o Ako graf Γ ima Eulerovu stazu s krajevima A i B (A se ne poklapa s B), tada je graf Γ povezan i A i B su njegovi jedini neparni vrhovi. Doista, povezanost grafa proizlazi iz definicije Eulerove staze. Ako put počinje u A i završava na drugom vrhu B, tada su i A i B neparni, čak i ako je put više puta prošao kroz A i B. Ostali vrhovi moraju biti parni.

Neophodan uvjet za postojanje Eulerove staze oo Vrijedi i obrnuto: ako je graf Γ povezan, a A i B su njegovi jedini neparni vrhovi, tada graf Γ ima Eulerovu stazu s krajevima A i B. Vrhovi A i B mogu biti povezani bridom u grafu, ili mogu biti i nisu povezani. U svakom slučaju dodajte ili dodatni ili novi brid (A, B), tada će svi njegovi vrhovi postati parni. Novi graf, prema gornjem konstruktivnom dokazu dovoljnog uvjeta za postojanje Eulerovog grafa, ima Eulerov ciklus koji može započeti duž bilo kojeg ruba. Počinjemo Eulerov ciklus od vrha A duž dodanog ruba (A, B) i završavamo ga na vrhu A. Ako sada uklonimo

Primjena teorema Eulerovog puta o o Dakle, svaki zatvoreni lik s točno dva neparna vrha može se nacrtati jednim potezom bez ponavljanja, počevši na jednom od neparnih vrhova i završavajući na drugom. U skladu s ovim teoremom ne postoji Eulerova staza preko Königsbergovih mostova, budući da iako je odgovarajući graf povezan, stupnjevi svih njegovih vrhova su neparni, a samo dva vrha moraju biti neparni, a ostali parni za Eulerovu stazu do postojati

Sami o U skladu s teoremom Eulerovog puta odredite: postoji li Eulerova staza u grafovima? (da li je moguće crtati jednim potezom bez ponavljanja, počevši od jednog vrha i završivši na drugom). Ako postoji, pronađi ga (pokaži kako)

Zadatak 7. 2. O mostovima u Konigsbergu za zamišljeni grad (samostalno) o Slika prikazuje plan zamišljenog grada koji je Euler ilustrirao u svom djelu. Nacrtajte graf za Eulerov plan i odredite postoji li u njemu Eulerov ciklus? A Eulerov način? Ako je tako, pronađite ga.

Zadatak 8. Zoološki vrt (sam po sebi) o Na slici je prikazan dijagram zoološkog vrta (vrhovi grafa su ulaz, izlaz, raskrižja, skretanja, slijepe ulice, rubne staze duž kojih se nalaze stanice). Pronađite rutu kojom bi vodič mogao voditi posjetitelje, pokazujući im sve životinje i ne prolazeći ni jedan dio puta više puta, odnosno pronađite Eulerovu stazu.

Teorija grafova- poglavlje diskretna matematikaproučavanje svojstava grafovima ... U općem smislu, graf je predstavljen kao skup vrhova (čvorova) povezanih bridovima. U strogoj definiciji, takav se par skupova naziva graf. G = (V, E), gdje je V podskup bilo kojeg prebrojivog skupa, a E je podskup od V × V.

Povijest nastanka teorije grafova
Osnivač teorije grafova je Leonard Euler. Godine 1736. u jednom od svojih pisama formulira i predlaže rješenje problema sedam konigsberških mostova, koji je kasnije postao jedan od klasičnih problema u teoriji grafova.
Prvi problemi teorije grafova bili su povezani s rješavanjem matematičkih problema i zagonetki. Evo prepričavanja ulomka iz pisma Euleru od 13. ožujka 1736.: “Ponuđen mi je problem otoka koji se nalazi u gradu Königsbergu i okružen rijekom preko koje je bačeno 7 mostova. Pitanje je može li ih netko kontinuirano zaobilaziti, prolazeći samo jednom kroz svaki most. I tada sam dobio informaciju da to još nitko nije 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 nisu dovoljni za njegovo rješenje. Nakon dugog razmišljanja, pronašao sam jednostavno pravilo, temeljeno na potpuno uvjerljivom dokazu, uz pomoć kojeg je u svim problemima ove vrste moguće odmah utvrditi može li se takav obilazni put ostvariti kroz bilo koji broj i proizvoljno lociranih mostova ili ne ." Konigsberški mostovi mogu se shematski prikazati na sljedeći način:
Eulerovo pravilo:

1. U grafu koji nema vrhove neparnih stupnjeva, postoji obilazak svih bridova (i svaki brid se prijeđe točno jednom) s početkom u bilo kojem vrhu grafa.
2. U grafu koji ima dva i samo dva vrha s neparnim stupnjevima, postoji prijelaz koji počinje na jednom vrhu s neparnim stupnjem i završava na drugom.
3. U grafu s više od dva vrha s neparnim stupnjem, takav prijelaz ne postoji.

Postoji još jedna vrsta problema putovanja grafom. Riječ je o problemima u kojima je potrebno pronaći put koji prolazi kroz sve vrhove, a ne više od jednom kroz svaki. Ciklus koji prolazi kroz svaki vrh jednom i samo jednom naziva se Hamiltonov pravac (u čast Williama Rowana Hamiltona, poznatog irskog matematičara prošlog stoljeća, koji je prvi počeo proučavati takve linije). Nažalost, još nije pronađen opći kriterij po kojem bi se moglo odlučiti je li dati graf Hamiltonov i, ako jest, pronaći sve Hamiltonove linije na njemu.
Formulirano sredinom 19. stoljeća. problem četiri boje također izgleda kao zabavan problem, ali pokušaji njegovog rješavanja doveli su do pojave nekih studija grafova koji imaju teorijsku i primijenjenu vrijednost. Problem s četiri boje formuliran je na sljedeći način: "Može li se područje bilo koje ravne karte obojiti s četiri boje tako da su bilo koja dva susjedna područja obojana različitim bojama?" Sredinom 19. stoljeća formulirana je hipoteza da je odgovor potvrdan. Godine 1890. dokazana je slabija tvrdnja, naime da je svaka ravna karta obojena u pet boja. U usporedbi s bilo kojom plosnatom zemljovidom njezina dual flat graf, dobiti ekvivalentnu formulaciju problema u terminima grafova: Je li istina da je kromatski broj bilo kojeg ravnog grafa manji ili jednak četiri? Brojni pokušaji rješavanja problema utjecali su na razvoj brojnih područja teorije grafova. Godine 1976. najavljeno je pozitivno rješenje problema pomoću računala.

Osnivač teorije grafova je Leonard Euler. Godine 1736. u jednom od svojih pisama formulira i predlaže rješenje problema sedam konigsberških mostova, koji je kasnije postao jedan od klasičnih problema u teoriji grafova.

Prvi problemi teorije grafova bili su povezani s rješavanjem matematičkih problema i zagonetki. Evo prepričavanja ulomka iz pisma Euleru od 13. ožujka 1736.: “Ponuđen mi je problem otoka koji se nalazi u gradu Königsbergu i okružen rijekom preko koje je bačeno 7 mostova. Pitanje je može li ih netko kontinuirano zaobilaziti, prolazeći samo jednom kroz svaki most. I tada sam dobio informaciju da to još nitko nije 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 nisu dovoljni za njegovo rješenje. Nakon dugog promišljanja, pronašao sam jednostavno pravilo utemeljeno na potpuno uvjerljivom dokazu, uz pomoć kojeg je u svim problemima ove vrste moguće odmah utvrditi može li se takav prelazak izvršiti kroz bilo koji broj i proizvoljno lociranih mostova ili ne. " Konigsberški mostovi mogu se shematski prikazati na sljedeći način:

Eulerovo pravilo:

1. U grafu koji nema vrhove neparnih stupnjeva, postoji obilazak svih bridova (i svaki brid se prijeđe točno jednom) s početkom u bilo kojem vrhu grafa.

2. U grafu koji ima dva i samo dva vrha s neparnim stupnjevima, postoji prijelaz koji počinje na jednom vrhu s neparnim stupnjem i završava na drugom.

3. U grafu s više od dva vrha s neparnim stupnjem, takav prijelaz ne postoji.

Postoji još jedna vrsta problema putovanja grafom. Riječ je o problemima u kojima je potrebno pronaći put koji prolazi kroz sve vrhove, a ne više od jednom kroz svaki. Ciklus koji prolazi kroz svaki vrh jednom i samo jednom naziva se Hamiltonovom linijom (u čast Williama Rowana Hamiltona, poznatog irskog matematičara prošlog stoljeća, koji je prvi počeo proučavati takve linije). Nažalost, još nije pronađen opći kriterij po kojem bi se moglo odlučiti je li dati graf Hamiltonov i, ako jest, pronaći sve Hamiltonove linije na njemu.

Formulirano sredinom 19. stoljeća. problem četiri boje također izgleda kao zabavan problem, ali pokušaji njegovog rješavanja doveli su do pojave nekih studija grafova koji imaju teorijsku i primijenjenu vrijednost. Problem s četiri boje formuliran je na sljedeći način: "Može li se područje bilo koje ravne karte obojiti s četiri boje tako da su bilo koja dva susjedna područja obojana različitim bojama?" Sredinom 19. stoljeća formulirana je hipoteza da je odgovor potvrdan. Godine 1890. dokazana je slabija tvrdnja, naime da je svaka ravna karta obojena u pet boja. Uspoređujući bilo koji ravni grafikon s njegovim dvostrukim ravnim grafom, dobivamo ekvivalentnu formulaciju problema u terminima grafova: Je li istina da je kromatski broj bilo kojeg ravnog grafa manji ili jednak četiri? Brojni pokušaji rješavanja problema utjecali su na razvoj brojnih područja teorije grafova. Godine 1976. najavljeno je pozitivno rješenje problema pomoću računala.

Još jedan stari topološki problem koji je prkosio rješenju posebno dugo vremena i koji je uzbuđivao umove ljubitelja zagonetki poznat je kao "problem opskrbe električnom energijom, plinom i vodom". Godine 1917. Henry E. Dudeny mu je dao ovu formulaciju. Svaka od tri kuće prikazane na slici mora biti opskrbljena plinom, strujom i vodom.

Teorija grafova. jedan

Povijest nastanka teorije grafova. jedan

Eulerovo pravilo. jedan

Književnost

1. Belovljeva teorija grafova, Moskva, "Znanost", 1968.

2. Nove pedagoške i informacijske tehnologije E.S. Polat , Moskva, "Akademia" 1999 godina

3. Kuznetsov OP, Adelson-Velsky GM Diskretna matematika za inženjera. - M .: Energoatomizdat, 1988.

4. Cook D., Base G. Računalna matematika. - M .: Znanost, 1990.

5. Nefedov V.N., Osipova V.A. Diskretni tečaj matematike. - M .: Izdavačka kuća MAI, 1992.

6. Ore O. Teorija grafova. - M .: Znanost, 1980.

7. Ismagilov R.S., Kalinkin A.V. Materijali za praktičnu nastavu na kolegiju: Diskretna matematika

OPĆINSKA AUTONOMNA OBRAZOVNA USTANOVA SREDNJA OBRAZOVNA ŠKOLA № 2

Pripremljeno

Legkoonets Vladislav, učenik 10A razreda

Praktična upotreba Teorija grafova

Nadglednik

L.I. Noskova, profesorica matematike

Bryukhovetskaya stanica

2011. r.

1.Uvod ……………………………………………………………………………………………… .3

2. Povijest nastanka teorije grafova ………………………………………. ……… ..4

3. Osnovne definicije i teoremi teorije grafova ………………………………. ……… 6

4. Zadaci riješeni pomoću grafikona …………………………… .. …………………… ..8

4.1 Značajni zadaci …………………………………. ……………………… ... 8

4.2 Neki zanimljivi zadaci …………………………………………….…………… ..9

5.Primjena grafova u raznim područjima života ljudi ................... 11

6.Rješavanje zadataka …………………………………………………………………………………… ... 12

7. Zaključak …………………………………………………………………………………………… .13

8. Reference …………. ……………………………………………………………………… 14

9. Dodatak ……………………………………………………………………………… 15

Uvod

Rođen na rješavanju zagonetki i zabavne igre, teorija grafova je sada postala jednostavan, pristupačan i moćan alat za rješavanje problema vezanih uz širok raspon problema. Grafovi su doslovno sveprisutni. U obliku grafikona možete, na primjer, tumačiti sheme cesta i električni krugovi, geografske karte i molekule kemijski spojevi, komunikacija između ljudi i grupa ljudi. Tijekom posljednja četiri desetljeća teorija grafova postala je jedna od najbrže razvijajućih grana matematike. To je potaknuto zahtjevima 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. Tako relevantnost Tema je zaslužna, s jedne strane, zbog popularnosti grafova i srodnih istraživačkih metoda, a s druge strane zbog nerazvijenog, holističkog sustava za njegovu implementaciju.

Rješenje mnogih životnih problema zahtijeva duge izračune, a ponekad ti proračuni ne donose uspjeh. Ovo je istraživački problem... Postavlja se pitanje: je li moguće pronaći jednostavno, racionalno, kratko i elegantno rješenje za njihovo rješavanje. Je li lakše rješavati probleme ako koristite grafove? To je odredilo moja tema istraživanja: "Praktična primjena teorije grafova"

Svrha istraživanje je koristilo grafove kako bi naučilo kako brzo riješiti praktične probleme.

Istraživačka hipoteza. Metoda grafa vrlo je važna i ima široku primjenu u raznim područjima znanosti i ljudskog života.

Ciljevi istraživanja:

1. Proučiti literaturu i internetske izvore o ovom problemu.

2. Provjerite učinkovitost graf metode u rješavanju praktičnih zadataka.

3. Donesite zaključak.

Praktični značaj studije je da će rezultati nesumnjivo potaknuti zanimanje mnogih ljudi. Nije li netko od vas pokušao izgraditi obiteljsko stablo za svoju obitelj? Kako to učiniti ispravno? Čelnik prijevozničke tvrtke vjerojatno mora riješiti problem isplativijeg korištenja prijevoza pri prijevozu robe od odredišta do nekoliko naselja. Svaki se školarac suočio s logičkim problemima s transfuzijom. Pokazalo se da se oni mogu lako riješiti pomoću grafova.

U radu se koriste sljedeće metode: promatranje, traženje, odabir, analiza.

Povijest 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 me pitali problem otoka koji se nalazi u gradu Königsbergu i okružen rijekom preko koje je prebačeno sedam mostova.

[Dodatak slika 1] Pitanje je može li ih netko kontinuirano zaobilaziti, prolazeći samo jednom kroz svaki most. I tada sam dobio informaciju da to još nitko nije 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 nisu 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 obilazni put ostvariti kroz bilo koji broj i proizvoljno lociranih mostova ili ne. Mostovi u Konigsbergu smješteni su tako da se mogu prikazati na sljedećoj slici [Dodatak slika 2], na kojem A označava otok, a B, C i D - dijelove kontinenta, odvojene jedan od drugog ograncima rijeke

O načinu na koji je otkrio rješavanje problema ove vrste, Euler je napisao:

„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 odsječka Da su dva od ovih brojeva bila bi neparna, jer postoji samo jedan ne može biti neparan, onda se i tada mogao dogoditi prijelaz, kako je propisano, ali se svakako mora uzeti 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 dovesti drugi, ozbiljniji problemi, ova metoda bi mogla donijeti još veću korist i ne bi trebala biti zanemaren"...

Osnovne definicije i teoremi teorije grafova

Teorija grafova je matematička disciplina nastala trudom matematičara, stoga njezino predstavljanje uključuje potrebne rigorozne definicije. Dakle, prijeđimo na organizirano upoznavanje s osnovnim pojmovima ove teorije.

Definicija 1. 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.

Ova se definicija može drugačije formulirati: graf je neprazan skup točaka (vrhova) i segmenata (brova), čija oba kraja pripadaju danom skupu točaka

U nastavku će vrhovi grafa biti označeni latiničnim slovima A, B, C, D. Ponekad će cijeli graf biti označen jednim veliko slovo.

Definicija 2. Vrhovi grafa koji ne pripadaju niti jednom bridu nazivaju se izolirani.

Definicija 3. Graf koji se sastoji samo od izoliranih vrhova naziva se nula - računati .

Oznaka: O "- graf s vrhovima bez bridova

Definicija 4. Graf u kojem je svaki par vrhova povezan bridom naziva se potpun.

Oznaka: U " – graf koji se sastoji od n vrhova i bridova koji povezuju sve moguće parove tih vrhova. Takav graf se može predstaviti kao n-kut u kojem su nacrtane sve dijagonale

Definicija 5. Stupanj vrha je broj bridova kojima vrh pripada.

Definicija 6. Graf čiji su stupnjevi svih k vrhova isti naziva se homogenim grafom stupnja k .

Definicija 7. Komplement ovog grafa je graf koji se sastoji od svih bridova i njihovih krajeva, koji se moraju dodati izvornom grafu kako bi se dobio potpun graf.

Definicija 8. Graf koji se na ravnini može prikazati na način kada mu se bridovi sijeku samo u vrhovima naziva se ravan.

Definicija 9. Poligon planarnog grafa koji u sebi ne sadrži vrhove ili bridove grafa naziva se njegovo lice.

Koncepti ravnog grafa i lica grafa koriste se za rješavanje problema o "ispravnom" bojanju raznih karata.

Definicija 10. Put od A do X je niz bridova koji vode od A do X tako da svaka dva susjedna brida imaju zajednički vrh, a niti jedan brid se ne pojavljuje više od jednom.

Definicija 11. Ciklus je put u kojem se početna i krajnja točka podudaraju.

Definicija 12. Jednostavan ciklus je ciklus koji ne prolazi ni kroz jedan vrh grafa više od jednom.

Definicija 13. Dug put , položen na petlju , je broj bridova ove staze.

Definicija 14. Dva vrha A i B u grafu nazivaju se povezanim (nepovezanim) ako u njemu postoji (ne postoji) put koji vodi od A do B.

Definicija 15. Graf se naziva povezanim ako su svaka dva njegova vrha povezana; ako graf sadrži barem jedan par nepovezanih vrhova, tada se graf naziva nepovezanim.

Definicija 16. Stablo je povezani graf koji ne sadrži cikluse.

Trodimenzionalni model grafa stabla je, na primjer, pravo stablo sa svojom zamršeno razgranatom krošnjom; rijeka i njezine pritoke također čine stablo, ali već ravno - na površini zemlje.

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

Definicija 18. Stablo sa svih n vrhova numeriranih od 1 do n naziva se stablo s promijenjenim brojevima vrhova.

Dakle, razmotrili smo osnovne definicije teorije grafova, bez kojih bi bilo nemoguće dokazati teoreme, a time i riješiti probleme.

Zadaci rješavani pomoću grafova

Poznati zadaci

Problem trgovačkog putnika

Problem trgovačkog putnika jedan je od poznatih problema u teoriji kombinatorike. Postavljena je 1934. godine, a najbolji matematičari su oko toga izbili zube.

Izjava problema je sljedeća.
Putujući trgovac (putujući trgovac) mora napustiti prvi grad, posjetiti gradove 2,1,3..n jednom nepoznatim redoslijedom i vratiti se u prvi grad. Udaljenosti između gradova su poznate. Kojim redoslijedom treba ići po gradovima da zatvoreni put (obilazak) trgovačkog putnika bude najkraći?

Metoda za rješavanje problema trgovačkog putnika

Pohlepni algoritam “Idite u najbliži (u koji još niste ušli) grad”.
Ovaj algoritam se naziva "pohlepnim" jer je u zadnjim koracima potrebno platiti visoku cijenu za pohlepu.
Razmotrimo, na primjer, mrežu na slici [Dodatak slika 3] koji predstavlja uski romb. 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.

Problem Königsberških mostova.

Problem je formuliran na sljedeći način.
Grad Konigsberg nalazi se na obalama rijeke Pregel i dva otoka. Različiti dijelovi grada bili su povezani sa sedam mostova. Nedjeljom su se građani šetali gradom. Pitanje je: je li moguće prošetati na način da se, napuštajući kuću, vratite, hodajući točno jednom na svakom mostu.
Mostovi preko rijeke Pregel nalaze se kako je prikazano[Dodatak sl.1].

Razmotrimo graf koji odgovara shemi mosta [Dodatak slika 2].

Za odgovor na pitanje problema dovoljno je saznati je li graf Euler. (Paran broj mostova mora izlaziti iz barem jednog vrha). Ne možete, hodajući gradom, jednom proći kroz sve mostove i vratiti se.

Nekoliko zanimljivih zadataka

1. "Rute".

Problem 1

Kao što se sjećate, lovac na mrtve duše Čičikov je po jednom posjetio slavne zemljoposjednike. Posjetio ih je sljedećim redoslijedom: Manilov, Korobochka, Nozdrev, Sobakevich, Plyushkin, Tentetnikov, General Betrishchev, Petukh, Konstazholgo, Pukovnik Koshkarev. Pronađen je dijagram na kojem je Čičikov skicirao relativni položaj posjeda i seoskih cesta koje ih povezuju. Utvrdite koje imanje pripada kome, ako Čičikov nije prošao nijednu od cesta više puta [Dodatak slika 4].

Riješenje:

Prema karti puta vidi se da je Čičikov svoje putovanje započeo posjedom E, a završio posjedom O. Napominjemo da samo dva puta vode do posjeda B i C, pa je Čičikov morao voziti tim cestama. Označimo ih podebljanom linijom. Određene su dionice trase koja prolazi kroz A: AC i AB. Čičikov nije vozio cestama AE, AK i AM. Prekrižimo ih. Označimo podebljanom linijom ED; precrtati DK. Prekrižimo MO i MN; označiti podebljanom linijom MF; precrtati FO; označavamo podebljanom linijom FH, NK i KO. Nađimo jedini mogući put pod ovim uvjetom. I dobivamo: imanje E - pripada Manilovu, D - Korobochki, C - Nozdrev, A - Sobakevič, B - Pljuškin, M - Tentetnikov, F - Betrishchev, N - Pijetao, K - Konstazholgo, O - Koshkarev [Dodatak slika 5].

Zadatak 2

Slika prikazuje dijagram područja [Dodatak slika 6].

Možete se kretati samo u smjeru strelica. Svaku točku možete posjetiti najviše jednom. Na koliko načina možete doći od točke 1 do točke 9? Koja je ruta najkraća, a koja najduža.

Riješenje:

Uzastopno "slojeviti" shemu u stablo, počevši od vrha 1 [Dodatak slika 7]... Dobijamo drvo. Broj mogućih načina dobivanja od 1 do 9 jednak je broju "visećih" čvorova stabla (ima ih 14). Očito je najkraći put 1-5-9; najduži je 1-2-3-6-5-7-8-9.

2 "Grupe, poznanici"

Problem 1

Sudionici glazbenog festivala, nakon susreta, razmijenili su kuverte s adresama. Dokaži to:

a) ukupno je prenesen paran broj kuverti;

b) broj sudionika koji su razmijenili kuverte neparan broj puta je paran.

Rješenje: Neka sudionici festivala A 1, A 2, A 3. ... ... , I n su vrhovi grafa, a bridovi povezuju parove vrhova koji predstavljaju dečke koji su razmijenili omotnice [Dodatak slika 8]

Riješenje:

a) stupanj svakog vrha A i pokazuje broj omotnica koje je sudionik A i predao svojim prijateljima. Ukupni broj odaslanih ovojnica N jednak je zbroju stupnjeva svih vrhova grafa N = korak. A 1 + korak. A 2 + +. ... ... + korak. I n -1 + korak. I n, N = 2p, gdje je p broj bridova u grafu, tj. N je paran. Stoga je prebačen paran broj omotnica;

b) u jednakosti N = korak. A 1 + korak. A 2 + +. ... ... + korak. I n -1 + korak. I n zbroj neparnih članova mora biti paran, a to može biti samo ako je broj neparnih članova paran. To znači da je broj sudionika koji su razmijenili kuverte neparan broj puta, paran.

Zadatak 2

Jednom su se Andrei, Boris, Volodya, Dasha i Galya dogovorili da idu u kino navečer. O izboru kina i sjednice odlučili su se dogovoriti telefonski. Također je odlučeno da će se, ako nije moguće nazvati nekoga, odlazak u kino otkazati. Navečer se nisu svi okupili u kinu, pa je posjet kinu bio frustriran. Sutradan su počeli otkrivati ​​tko koga zove. Ispostavilo se da je Andrej zvao Boris i Volodja, Volodja je zvao Boris i Daša, Boris je zvao Andrej i Daša, Daša je zvao Andrej i Volodja, a Galja zvala Andrej, Volodja i Boris. Tko je propustio nazvati pa stoga nije došao na sastanak?

Riješenje:

Nacrtajmo pet točaka i označimo ih slovima A, B, C, D, D. Ovo su prva slova imena. Spojimo točkice koje odgovaraju imenima momaka koji su telefonirali.

[Dodatak slika 9]

Na slici se vidi da je svaki od momaka - Andrej, Boris i Volodja - nazvao sve ostale. Zato su ovi momci i došli u kino. A Galya i Dasha nisu uspjele nazvati jedna drugu (točke G i D nisu povezane segmentom) i stoga, u skladu s dogovorom, nisu došle u kino.

Korištenje grafova u različitim područjima ljudskog života

Osim navedenih primjera, grafovi se široko koriste u građevinarstvu, elektrotehnici, menadžmentu, logistici, geografiji, strojarstvu, sociologiji, programiranju, automatizaciji tehnoloških procesa i proizvodnje, psihologiji, oglašavanju. Dakle, iz svega navedenog nepobitno proizlazi praktična vrijednost teorije grafova, čiji je dokaz i bila svrha ovog istraživanja.

U bilo kojem području znanosti i tehnologije susrećete se s grafovima. Grafovi su prekrasni matematički objekti s kojima možete rješavati matematičke, ekonomske i logičke probleme, razne zagonetke i pojednostaviti uvjete zadataka iz fizike, kemije, elektronike, automatike. Mnoge matematičke činjenice prikladno su formulirane jezikom grafova. Teorija grafova je dio mnogih znanosti. Teorija grafova jedna je od najljepših i najintuitivnijih matematičkih teorija. U posljednje vrijeme teorija grafova nalazi sve više primjena u primijenjenim pitanjima. Pojavila se čak i računalna kemija, relativno mlado područje kemije koje se temelji na primjeni teorije grafova.

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

Molekularni grafovi i stabla: [Dodatak sl.10] a, b - multigrafi prema. etilen i formaldehid; u pristaništu. izomeri pentana (stabla 4, 5 su izomorfna stablu 2).

U stereokemiji je organizama najviše. Često se koriste molekularna stabla - osnovna stabla molekularnih grafova, koja sadrže samo sve vrhove koji odgovaraju C atomima. stabla i uspostavljanje njihovog izomorfizma omogućuju vam da odredite mol. strukturirati i pronaći ukupan broj izomera alkana, alkena i alkina

Proteinske mreže

Proteinske mreže su skupine proteina koji međusobno djeluju u fizičkom smislu koji funkcioniraju u stanici zajednički i na koordiniran način, kontrolirajući međusobno povezane procese u tijelu [Dodatak sl. jedanaest].

Graf hijerarhijskog sustava zove drvo. Posebnost stabla je da postoji samo jedan put između bilo koja dva njegova vrha. Stablo ne sadrži petlje ili petlje.

Obično, stablo koje predstavlja hijerarhijski sustav ima jedan glavni vrh, koji se zove korijen stabla. Svaki čvor stabla (osim korijena) ima samo jednog pretka - objekt koji je njime označen uključen je u jednu klasu najviše razine. Svaki čvor stabla može iznjedriti nekoliko potomaka - čvorova koji odgovaraju klasama niže razine.

Za svaki par vrhova stabla postoji jedan put koji ih povezuje. Ovo svojstvo se koristi pri pronalaženju svih predaka, na primjer, u muškoj liniji, bilo koje osobe čije je podrijetlo predstavljeno u obliku obiteljskog stabla, koje je "stablo" u smislu teorije grafova.

Primjer obiteljskog stabla moje obitelji [Dodatak slika 12].

Još jedan primjer. Slika prikazuje biblijsko obiteljsko stablo [Dodatak slika 13].

Rješavanje problema

1.Problem prijevoza... Neka postoji baza sa sirovinama u gradu Krasnodaru, koju treba razrijediti u gradovima Krimsk, Temryuk, Slavyansk-on-Kuban i Timashevsk u jednom putovanju, trošeći što manje vremena i goriva i vraćajući se nazad u Krasnodar.

Riješenje:

Najprije napravimo graf svih mogućih putnih ruta [Dodatak sl.14], uzimajući u obzir stvarne prometnice između ovih naselja i udaljenost između njih. Da bismo riješili ovaj problem, moramo sastaviti drugi graf, nalik stablu [Dodatak slika 15].

Radi praktičnosti rješenja, označavamo gradove brojevima: Krasnodar - 1, Krymsk - 2, Temryuk - 3, Slavyansk - 4, Timashevsk - 5.

To je rezultiralo 24 rješenja, ali nam trebaju samo najkraći putovi. Od svih rješenja samo dva zadovoljavaju, ovo je 350 km.

Slično, moguće je i, mislim, potrebno je izračunati stvarni prijevoz iz jednog naselje drugima.

Logički problem s transfuzijom. 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 jednako u kantu i veliku posudu.

Riješenje:

Situacija u svakom trenutku može se opisati s tri broja [Dodatak sl.16].

Kao rezultat dobivamo dva rješenja: jedno u 7 poteza, drugo u 8 poteza.

Zaključak

Dakle, da biste naučili rješavati probleme, morate razumjeti što su, kako su raspoređeni, od kojih se sastavnih dijelova sastoje, koji su alati pomoću kojih se rješavaju problemi.

Rješavajući praktične probleme uz pomoć teorije grafova, postalo je jasno da je u svakom koraku, u svakoj fazi njihovog rješavanja potrebno primijeniti kreativnost.

Od samog početka, u prvoj fazi, sastoji se u tome da morate znati analizirati i kodirati stanje problema. Druga faza je shematski zapis, koji se sastoji od geometrijskog prikaza grafova, a u ovoj fazi vrlo je važan element kreativnosti jer je daleko od lakog pronalaženja korespondencije između elemenata uvjeta i odgovarajućih elemenata grafa. .

Rješavajući transportni problem ili problem sastavljanja obiteljskog stabla, zaključio sam da je metoda grafa svakako zanimljiva, lijepa i vizualna.

Uvjerio sam se da se grafovi naširoko koriste u ekonomiji, menadžmentu, tehnologiji. Teorija grafova se također koristi u programiranju, o čemu se u ovom radu nije govorilo, ali mislim da je to samo pitanje vremena.

U ovom znanstvenom radu razmatraju se matematički grafovi, njihova područja primjene, nekoliko problema rješava se pomoću grafova. Poznavanje osnova teorije grafova potrebno je u raznim područjima vezanim uz upravljanje proizvodnjom, poslovanje (primjerice, raspored izgradnje mreže, rasporedi dostave pošte). Osim toga, radeći na znanstvenom radu, savladao sam rad na računalu u uređivaču teksta WORD. Dakle, zadaci znanstveni rad dovršeno.

Dakle, iz svega navedenog nepobitno proizlazi praktična vrijednost teorije grafova, čiji je dokaz i bila svrha ovog rada.

Književnost

Berge K. Teorija grafova i njezine primjene. -M .: IIL, 1962.

Kemeny J., Snell J., Thompson J. Uvod u konačnu matematiku. -M .: IIL, 1963.

Ore O. Grafovi i njihove primjene. -M .: Mir, 1965.

Harari F. Teorija grafova. -M .: Mir, 1973.

A. A. Zykov Teorija konačnih grafova. -Novosibirsk: Nauka, 1969.

Berezina L.Yu. Grafovi i njihove primjene. -M .: Prosvjeta, 1979.-144 str.

"Soros edukativni časopis" br. 11 1996 (članak "Pravi grafovi");

Gardner M. "Matematička dokolica", M. "Mir", 1972. (35. poglavlje);

Olekhnik SN, Nesterenko Yu. V., Potapov MK "Drevni zabavni zadaci", M. "Znanost", 1988 (dio 2, odjeljak 8; dodatak 4);

dodatak

dodatak

P

Riža. 6

Riža. 7

Riža. osam

dodatak

dodatak

dodatak

dodatak

P

Riža. 14

dodatak

dodatak

Račun za 2016 Godina

1. Uvod

2. Povijest nastanka teorije grafova

3. Osnovni pojmovi teorije grafova

4. Osnovni teoremi teorije grafova

5. Načini predstavljanja grafova u računalu

6. Pregled problema u teoriji grafova

7. Zaključak

8. Literatura

Uvod

U posljednje vrijeme istraživanja u područjima koja su tradicionalno povezana s diskretnom matematikom postaju sve istaknutija. Uz takve klasične grane matematike kao što su matematička analiza, diferencijalne jednadžbe, u nastavni planovi i programi specijalnosti "Primijenjena matematika" i mnogih drugih specijalnosti pojavile su se sekcije o matematičkoj logici, algebri, kombinatorici i teoriji grafova. Razloge za to nije teško razumjeti, jednostavno ocrtavajući niz problema koji se rješavaju na temelju ovog matematičkog aparata.

Povijest nastanka teorije grafova.

1. Problem Königsberških mostova. Na sl. 1 prikazuje shematski plan središnjeg dijela grada Konigsberga (danas Kalinjingrad), uključujući dvije obale rijeke Pergole, dva otoka na njoj i sedam spojnih mostova. Zadatak je zaobići sva četiri dijela kopna, jednom proći preko svakog mosta i vratiti se na početnu točku. Ovaj problem je riješio (pokazalo da rješenje ne postoji) Euler 1736. godine.

riža. jedan

2. Problem je oko tri kuće i tri bunara. Postoje tri kuće i tri bunara, nekako smješteni u avionu. Nacrtajte put od svake kuće do svakog bunara tako da se putevi ne sijeku (slika 2). Taj je problem riješio (pokazuje se da rješenje ne postoji) Kuratovsky 1930. godine.

riža. 2

3. Problem četiri boje. Podjela na ravnini na područja koja se ne sijeku naziva se zemljovidom. Područja na karti nazivaju se susjednim ako imaju zajednička granica... Zadatak je obojiti kartu na način da nijedna dva susjedna područja nisu obojana istom bojom (slika 3). Od kraja 19. stoljeća poznata je hipoteza da su za to dovoljne četiri boje. 1976. Appel i Heiken objavili su rješenje za problem četiri boje, koje se temeljilo na kompjuterski potpomognutoj iteraciji opcija. Rješenje ovog problema "programski" bio je presedan koji je izazvao burnu raspravu, koja nikako nije gotova. Bit objavljenog rješenja je nabrojati veliki, ali konačan broj (oko 2000) tipova potencijalnih protuprimjera teoremu o četiri boje i pokazati da nijedan slučaj nije protuprimjer. Ovu pretragu program je obavio u oko tisuću sati rada superračunala. Dobiveno rješenje nemoguće je provjeriti "ručno" - obujam nabrajanja daleko nadilazi okvire ljudskih mogućnosti. Mnogi matematičari postavljaju pitanje: može li se takav "programirani dokaz" smatrati valjanim dokazom? Uostalom, u programu može biti grešaka ... Metode formalnog dokaza ispravnosti programa nisu primjenjive na programe takve složenosti kao što je ovaj o kojem se raspravlja. Testiranje ne može jamčiti izostanak pogrešaka, au ovom slučaju uopće nije moguće. Stoga se ostaje osloniti se na programerske kvalifikacije autora i vjerovati da su sve učinili kako treba.

Riža. 3

Osnovni pojmovi teorije grafova

1) Po grafu G (V, E) je skup od dva skupa - nepraznog skupa V (skup vrhova) i skupa E dvoelementnih podskupova skupa V (E je skup bridova).

2) Orijentiran naziva se graf u kojem je skup uređenih parova vrhova oblika (x, y), gdje se x naziva početak, a y kraj luka. Luk (x, y) se često piše kao. Također kažu da luk vodi od vrha x do vrha y, i vrha y susjedni s vrhom x.

3) Ako element skupa E može biti par isto(nerazličitih) elemenata od V, onda se takav element skupa E zove omča a graf se zove graf s petljama(ili pseudo-graf).

4) Ako E nije skup, ali skupa koji sadrže nekoliko identičnih elemenata, onda se ti elementi nazivaju više rubova a graf se zove multigraf.

5) Ako elementi skupa E nisu nužno dvoelementni, bilo koji podskupovi skupa V, tada se takvi elementi skupa E nazivaju hiper-lukovi a graf se zove hipergraf.

6) Ako je funkcija postavljena Ž: V → M i/ili Ž: E → M, zatim skup M nazvan skupom bilješke a graf se zove označeno(ili natovaren). Slova ili cijeli brojevi obično se koriste kao skup bilješki. Ako je funkcija F je injektivan, odnosno različiti vrhovi (brdovi) imaju različite oznake, tada se graf naziva numerirani.

7) Podgraf naziva se graf G ′ (V ′, E ′), gdje je i / ili.

a) Ako je V ′ = V, tada se zove G ′ okosnica podgraf G.

b) Ako, tada se zove graf G vlastiti podgraf grafa G.

c) Podgraf G ′ (V ′, E ′) naziva se regularnim podgrafom grafa G (V, E) ako G ′ sadrži sve moguće bridove G.

8) Stupanj (valencija) vertices je broj bridova koji su incidentni ovom vrhu (broj vrhova koji su mu susjedni).

9) Putem u grafu se naziva izmjenični niz vrhova i bridova, u kojem su bilo koja dva susjedna elementa incidenti.

a) Ako, onda ruta zatvoreno, inače otvorena.

b) Ako su svi bridovi različiti, tada se ruta zove lanac.

c) Ako su svi vrhovi (a time i bridovi) različiti, tada se ruta naziva jednostavan lanac.

d) Zatvoreni strujni krug naziva se ciklus.

e) Zove se zatvoreni jednostavni lanac jednostavan ciklus.

f) Zove se graf bez ciklusa aciklički.

g) Za digrafe se zove lanac putem a ciklus je obris.

riža. 4. Rute, lanci, ciklusi

Primjer

Na grafikonu čiji je dijagram prikazan na slici 4:

1. v 1, v 3, v 1, v 4 - ruta, ali ne i lanac;

2. v 1, v 3, v 5, v 2, v 3, v 4 - lanac, ali ne i jednostavan lanac;

3. v 1, v 4, v 3, v 2, v 5 - jednostavan lanac;

4. v 1, v 3, v 5, v 2, v 3, v 4, v 1 - ciklus, ali ne i jednostavan ciklus;

5. v 1, v 3, v 4, v 1 je jednostavan ciklus.

10) Ako graf ima ciklus (ne nužno jednostavan) koji sadrži sve rubove grafa jednom, tada se takav ciklus naziva Euler ciklus.

11) Ako graf ima jednostavan ciklus koji sadrži sve vrhove grafa (jednom), tada se takav ciklus naziva Hamiltonov ciklus.

12) Drvo naziva se povezani graf bez ciklusa.

13) Kostur naziva se stablo koje sadrži sve vrhove grafa.

14) Podudaranje je skup bridova u kojem nema dva susjedna.

15) Podudaranje se zove maksimum ako niti jedan njegov nadskup nije neovisan.

16) Dva vrha u grafu povezani ako postoji jednostavan lanac koji ih povezuje.

17) Zove se graf u kojem su svi vrhovi povezani povezani.

18) Zove se graf koji se sastoji samo od izoliranih vrhova prilično nesuvislo.

19) Duljina rute naziva se brojem rebara u njemu (s ponavljanjima).

20) Udaljenost između vrhova u i v je duljina najkraćeg puta, a sam najkraći put se naziva geodetske.

21) Promjer grafa G naziva se duljina najduže geodetske.

22) Ekscentričnost vrh v u povezanom grafu G (V, E) je najveća udaljenost od vrha v do ostalih vrhova grafa G.

23) Radius graf G naziva se najmanji od ekscentriciteta vrhova.

24) Zove se vrh v središnji ako se njegov ekscentricitet poklapa s polumjerom grafa.

25) Skup središnjih vrhova se zove centar graf.

riža. 5 Ekscentriciteti vrhova i središta grafa (označeno).

Slične informacije.