Teorija grafova: osnovni pojmovi i zadaci. Grafovi kao struktura podataka. Praktična primjena teorije grafova. Primijenjeni značaj teorije grafova

1736., Koenigsberg. Kroz grad teče rijeka Pregelya. U gradu postoji sedam mostova koji su smješteni kao što je prikazano na gornjoj slici. Od davnina su se stanovnici Königsberga borili sa zagonetkom: je li moguće prijeći sve mostove, prelazeći svaki samo jednom? Taj je problem riješen kako teoretski, na papiru, tako i praktično, u šetnjama - prolazeći upravo ovim mostovima. Nitko nije uspio dokazati da je to nemoguće, ali nitko nije mogao izvesti tako “misteriozan” hod preko mostova.

Poznati matematičar Leonhard Euler uspio je riješiti problem. Štoviše, on je riješio ne samo ovaj specifičan problem, već je došao do opće metode za rješavanje sličnih problema. Rješavajući problem königsberških mostova, Euler je postupio na sljedeći način: zemljište je "sabio" u točke, a mostove "razvukao" u linije. Takva figura, koja se sastoji od točaka i linija koje povezuju te točke, zove se RAČUNATI.

Graf je zbirka nepraznog skupa vrhova i veza između vrhova. Krugovi se nazivaju vrhovi grafa, linije sa strelicama su lukovi, a linije bez strelica su bridovi.

Vrste grafikona:

1. Usmjereni graf(kratko digraf) - čijim je bridovima dodijeljen smjer.

2. Neusmjereni graf je graf u kojem nema smjera linija.

3. Ponderirani graf– lukovi ili rubovi imaju težinu (dodatne informacije).

Rješavanje problema pomoću grafikona:

Zadatak 1.

Rješenje: Označimo znanstvenike kao vrhove grafa i povucimo linije od svakog vrha do četiri druga vrha. Dobivamo 10 redaka, koji će se smatrati rukovanjem.

Zadatak 2.

Na području škole raste 8 stabala: jabuka, topola, breza, oskoruša, hrast, javor, ariš i bor. Oskoruša je viša 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 oskoruše, breza je niža od topole, a ariš je viši od jabuke. Rasporedite stabla od najnižeg prema najvišem.

Riješenje:

Vrhovi grafa su stabla, označena prvim slovom imena stabla. Postoje dva odnosa u ovom zadatku: "biti niži" i "biti viši". Razmotrite relaciju "biti niži" i nacrtajte strelice od nižeg stabla prema višem. Ako problem kaže da je planinski jasen viši od ariša, tada stavljamo strelicu od ariša do planinskog pepela itd. Dobivamo grafikon koji pokazuje da je najkraće stablo javor, a slijede jabuka, ariš, oskoruša, bor, hrast, breza i topola.

Zadatak 3.

Nataša ima 2 koverte: običnu i zračnu i 3 marke: pravokutnu, kvadratnu i trokutastu. Na koliko načina Nataša može odabrati kuvertu i marku za slanje pisma?

Riješenje:

U nastavku je pregled zadataka.

OPĆINSKA SAMOSTALNA OBRAZOVNA USTANOVA SREDNJA ŠKOLA BR. 2

Pripremljeno

Legkokonets Vladislav, učenik 10A razreda

Praktična primjena teorije grafova

Nadglednik

L.I. Noskova, učiteljica matematike

Art Bryukhovetskaya

2011

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

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

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

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

4.1 Poznati problemi………………………………….………………………...8

4.2 Nekoliko zanimljivih problema………………………………….……………..9

5. Primjena grafikona u različitim područjima života ljudi………………………………...11

6. Rješavanje problema…………………………………………………………………………………………...12

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

8. Popis literature………….………………………………………………………………14

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

Uvod

Rođena iz rješavanja zagonetki i zabavnih igara, teorija grafova sada je postala jednostavan, pristupačan i moćan alat za rješavanje pitanja vezanih uz širok raspon problema. Grafikoni su doslovno sveprisutni. U obliku grafikona možete, primjerice, interpretirati cestovne karte i električne krugove, geografske karte i molekule kemijskih spojeva, veze među ljudima i skupinama ljudi. Tijekom posljednja četiri desetljeća teorija grafova postala je jedna od grana matematike koja se najbrže razvija. To je potaknuto zahtjevima polja primjene koje se brzo širi. Koristi se u dizajnu integriranih krugova i upravljačkih krugova, u proučavanju automata, logičkih sklopova, programskih blok dijagrama, u ekonomiji i statistici, kemiji i biologiji, u teoriji rasporeda. Zato relevantnost Tema je određena, s jedne strane, popularnošću grafova i srodnih istraživačkih metoda, as druge strane, nerazvijenim, holističkim sustavom za njihovu primjenu.

Rješavanje mnogih životnih problema zahtijeva duge kalkulacije, a ponekad ni te kalkulacije ne donose uspjeh. To je što problem istraživanja. Postavlja se pitanje je li moguće pronaći jednostavno, racionalno, kratko i elegantno rješenje za njihovo rješavanje. Je li rješavanje problema lakše ako koristite grafikone? Ovo je odredilo tema mog istraživanja: “Praktična primjena teorije grafova”

Svrha Istraživanje je trebalo koristiti grafikone kako bi naučili kako brzo riješiti praktične probleme.

Hipoteza istraživanja. Metoda grafova vrlo je važna i široko korištena u raznim područjima znanosti i ljudske djelatnosti.

Ciljevi istraživanja:

1. Proučite literaturu i internetske izvore o ovoj temi.

2.Provjeriti učinkovitost graf metode u rješavanju praktičnih problema.

3. Izvedite zaključak.

Praktični značaj studije je da će rezultati nedvojbeno pobuditi interes mnogih ljudi. Zar nitko od vas nije pokušao izgraditi svoje obiteljsko stablo? Kako to učiniti ispravno? Voditelj prijevozničkog poduzeća vjerojatno mora riješiti problem isplativijeg korištenja prijevoza prilikom prijevoza robe od odredišta do nekoliko naselja. Svaki se školarac susreo s logičnim problemima transfuzije. Ispostavilo se da ih je lako riješiti pomoću grafova.

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

Povijest teorije grafova

Utemeljiteljem teorije grafova smatra se matematičar Leonhard Euler (1707-1783). Povijest ove teorije može se pratiti kroz korespondenciju velikog znanstvenika. Ovdje je prijevod latinskog teksta, koji je preuzet iz Eulerovog pisma talijanskom matematičaru i inženjeru Marinoniju, poslanog iz Sankt Peterburga 13. ožujka 1736. godine.

“Jednom sam dobio problem o otoku koji se nalazi u gradu Königsbergu i okružen je rijekom sa sedam mostova preko nje.

[Dodatak sl.1] Pitanje je može li ih netko u kontinuitetu obilaziti, prolazeći samo jednom preko svakog mosta. A onda su me obavijestili da to još nitko nije uspio, ali nitko nije dokazao da je to nemoguće. Ovo pitanje, iako trivijalno, činilo mi se ipak vrijednim pažnje jer ni geometrija, ni algebra, ni kombinatorika nisu dovoljni da ga riješe. Nakon dugog razmišljanja, pronašao sam jednostavno pravilo, temeljeno na potpuno uvjerljivom dokazu, uz pomoć kojeg je moguće u svim problemima ove vrste odmah utvrditi može li se takav obilazak napraviti kroz bilo koji broj i bilo koji broj mostova koji se nalaze ili ne. Koenigsberški mostovi su smješteni na takav način da se mogu prikazati na sljedećoj slici [Dodatak sl.2], u kojem A označava otok, a B, C i D - dijelove kontinenta odvojene jedan od drugog riječnim ograncima

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

“Ovo rješenje, po svojoj prirodi, očito ima malo veze s matematikom i ne razumijem zašto bi se ovo rješenje trebalo očekivati od matematičara, a ne od bilo koje druge osobe, jer je ova odluka potkrijepljena samo rezoniranjem, a nema potrebno je uključiti sve zakone koji su svojstveni matematici da bi se pronašlo ovo rješenje. Dakle, ne znam kako ispada da će pitanja koja imaju vrlo malo veze s matematikom vjerojatnije riješiti matematičari nego drugi."

Dakle, je li moguće zaobići Königsberške mostove prolaskom samo jednom preko svakog od ovih mostova? Kako bismo pronašli odgovor, nastavimo Eulerovo pismo Marinoniju:

"Pitanje je utvrditi je li moguće zaobići svih tih sedam mostova, prolazeći kroz svaki samo jednom, ili ne. Moje pravilo vodi do sljedećeg rješenja ovog pitanja. Prije svega, morate pogledati koliko područja ima su, odvojeni vodom - takvi , koji nemaju drugog prolaza od jednog do drugog, osim preko mosta. U ovom primjeru, postoje četiri takva odjeljka - A, B, C, D. Zatim, trebate razlikovati je li broj Broj mostova koji vode do tih pojedinačnih dionica je paran ili neparan. Dakle, u našem slučaju pet mostova vodi do dionice A, a po tri mosta do ostalih, tj. broj mostova koji vode do pojedinih dionica je neparan i samo ovo je dovoljno kako bismo riješili problem. Nakon što se to utvrdi, primjenjujemo sljedeće pravilo: ako je broj mostova koji vode do svake zasebne dionice paran, tada bi dotično obilaženje bilo moguće, au isto vrijeme bilo bi moguće pokrenuti ovaj zaobilaznica iz bilo kojeg odsječka. Ako su pak dva od ovih brojeva bila neparna, jer samo jedan ne može biti neparan, tada bi se čak i tada prijelaz mogao dovršiti, kako je propisano, ali svakako se mora uzeti samo početak obilaznice od jedan od ona dva dijela do kojih vodi neparan broj mostova. Kad bi, konačno, postojalo više od dvije dionice do kojih vodi neparan broj mostova, onda je takvo kretanje općenito nemoguće ... ako bi se ovdje mogli dovesti neki drugi, ozbiljniji problemi, ova bi metoda mogla biti od još veće koristi i trebala bi ne smije se zanemariti."

Osnovne definicije i teoremi teorije grafova

Teorija grafova je matematička disciplina nastala radom matematičara, stoga njezino izlaganje uključuje potrebne stroge definicije. Dakle, prijeđimo na organizirano upoznavanje osnovnih pojmova ove teorije.

Definicija 1. Graf je zbirka konačnog broja točaka, koje se nazivaju vrhovi grafa, i parova linija koje povezuju neke od tih vrhova, koje se nazivaju bridovi ili lukovi grafa.

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

U nastavku ćemo vrhove grafa označavati latiničnim slovima A, B, C, D. Ponekad će se graf kao cjelina označiti jednim velikim slovom.

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 null - računati .

Oznaka: O "– graf s vrhovima koji nema bridova

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

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

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

Definicija 6. Graf čiji su stupnjevi svih k vrhova isti naziva se homogeni graf stupnjeva .

Definicija 7. Komplement zadanog grafa je graf koji se sastoji od svih bridova i njihovih krajeva koji se moraju dodati izvornom grafu da bi se dobio potpuni graf.

Definicija 8. Graf koji se može prikazati na ravnini tako da mu se bridovi sijeku samo u vrhovima naziva se ravninski.

Definicija 9. Poligon planarnog grafa koji ne sadrži vrhove ili bridove grafa naziva se njegovim licem.

Koncepti planarnog grafa i lica grafa koriste se pri rješavanju 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 staza u kojoj se početna i završna točka podudaraju.

Definicija 12. Jednostavan ciklus je ciklus koji ne prolazi ni jednim vrhom grafa više od jednom.

Definicija 13. Duljina staze , položen na petlju , zove se broj bridova ove staze.

Definicija 14. Dva vrha A i B u grafu nazivamo povezanima (nepovezanima) ako 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, stvarno stablo sa svojom zamršeno razgranatom krošnjom; rijeka i njezini pritoci također tvore 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 u kojem je svih n vrhova označeno brojevima od 1 do n naziva se stablo s prenumeriranim vrhovima.

Dakle, ispitali smo osnovne definicije teorije grafova, bez kojih bi bilo nemoguće dokazati teoreme, a time i rješavati probleme.

Zadaci riješeni pomoću grafikona

Poznati problemi

Problem trgovačkog putnika

Problem trgovačkog putnika jedan je od poznatih problema u teoriji kombinatorike. Iznesena je 1934. godine i na njoj su najbolji matematičari lomili zube.

Izjava problema je sljedeća.
Putujući trgovački putnik (lutajući trgovac) mora napustiti prvi grad, jednom posjetiti gradove 2,1,3..n nepoznatim redoslijedom i vratiti se u prvi grad. Poznate su udaljenosti između gradova. Kojim redom treba obilaziti gradove da zatvoreni put (obilazak) trgovačkog putnika bude najkraći?

Metoda rješavanja problema trgovačkog putnika

Pohlepni algoritam “idite do najbližeg (u koji još niste ušli) grada.”
Ovaj algoritam se naziva "pohlepan" jer u posljednjim koracima morate ozbiljno platiti za pohlepu.
Razmotrite na primjer mrežu na slici [Dodatak sl.3], koji predstavlja uski romb. Neka trgovački putnik krene iz grada 1. Algoritam "idi do najbližeg grada" odvest će ga u grad 2, zatim 3, zatim 4; na posljednjem koraku morat ćete platiti za svoju pohlepu, vraćajući se duž duge dijagonale dijamanta. Rezultat neće biti najkraća, već najduža tura.

Problem oko Königsberških mostova.

Problem je formuliran na sljedeći način.
Grad Koenigsberg nalazi se na obalama rijeke Pregel i dva otoka. Različite dijelove grada povezivalo je sedam mostova. Nedjeljom su građani šetali gradom. Pitanje: da li je moguće šetati na način da se, kada izađete iz kuće, vratite nazad hodajući točno jednom preko svakog mosta?
Mostovi preko rijeke Pregel nalaze se kao na slici[Dodatak sl.1].

Razmotrite graf koji odgovara dijagramu mosta [Dodatak Slika 2].

Za odgovor na pitanje problema dovoljno je saznati je li graf Eulerov. (Paran broj mostova mora se protezati iz najmanje jednog vrha). Ne možete prošetati gradom i jednom prijeći sve mostove pa se vratiti.

Nekoliko zanimljivih zadataka

1. "Rute".

Problem 1

Kao što se sjećate, lovac na mrtve duše Čičikov jednom je posjetio poznate veleposjednike. Posjetio ih je sljedećim redom: Manilov, Korobočka, Nozdrjov, Sobakevič, Pljuškin, Tentetnikov, general Betriščev, Petuh, Konstanžolgo, pukovnik Koškarev. Pronađen je dijagram na kojem je Čičikov skicirao međusobne položaje imanja i seoskih cesta koje ih povezuju. Odredi kome pripada koje imanje ako Čičikov nijednom cestom nije vozio više puta [Dodatak Slika 4].

Riješenje:

Putokaz pokazuje da je Čičikov započeo svoje putovanje od imanja E, a završio na imanju O. Napominjemo da samo dvije ceste vode do imanja B i C, pa je Čičikov morao putovati tim cestama. Označimo ih masnom linijom. Identificirane su dionice trase koje prolaze kroz A: AC i AB. Čičikov nije putovao cestama AE, AK i AM. Prekrižimo ih. Označimo masnom crtom ED; Precrtajmo DK. Prekrižimo MO i MN; Označimo masnom crtom MF; prekrižiti FO; Označimo FH, NK i KO podebljanom linijom. Pronađimo jedini mogući put pod ovim uvjetom. I dobivamo: imanje E - pripada Manilovu, D - Korobochka, C - Nozdryov, A - Sobakevich, B - Plyushkin, M - Tentetnikov, F - Betrishchev, N - Petukh, K - Konstanzholgo, O - Koshkarev [Dodatak sl.5].

Problem 2

Na slici je prikazana karta 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 ruta je najkraća, a koja najduža.

Riješenje:

Sekvencijalno "stratificiramo" krug u stablo, počevši od vrha 1 [Dodatak sl.7]. Uzmimo drvo. Broj mogućih načina da dođete od 1 do 9 jednak je broju "visećih" vrhova stabla (ima ih 14). Očito je najkraći put 1-5-9; najduža je 1-2-3-6-5-7-8-9.

2 "Grupe, spojevi"

Problem 1

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

a) predan je paran broj koverti;

b) paran je broj sudionika koji su neparan broj puta izmijenili koverte.

Rješenje: Neka su sudionici festivala A 1, A 2, A 3. . . , A n su vrhovi grafa, a bridovi povezuju parove vrhova koji predstavljaju tipove koji razmjenjuju omotnice [Dodatak sl. 8]

Riješenje:

a) stupanj svakog vrha A i pokazuje broj koverti koje je sudionik A i dao svojim prijateljima. Ukupan broj odaslanih ovojnica N jednak je zbroju stupnjeva svih vrhova grafa N = stupanj. Korak 1+. A 2 + + . . . + korak. A n -1 + stupanj. I n, N =2p, gdje je p broj rubova grafa, tj. N – parno. Slijedom toga, uručen je paran broj omotnica;

b) u jednakosti N = stupanj. Korak 1+. A 2 + + . . . + korak. A n -1 + stupanj. 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 neparan broj puta razmijenili kuverte paran.

Problem 2

Jednog dana Andrej, Boris, Volodja, Daša i Galja dogovorili su se da navečer odu u kino. Odabir kina i projekcije odlučili su uskladiti telefonski. Odlučeno je i da se odlazak u kino, ako se s nekim ne može kontaktirati telefonom, otkazuje. Navečer se nisu svi okupili u kinu, pa je posjet kinu otkazan. Sutradan su počeli otkrivati tko je koga zvao. Ispostavilo se da je Andrej nazvao Borisa i Volodju, Volodja Borisa i Dašu, Boris Andreja i Dašu, Daša Andreja i Volodju, a Galja Andreja, Volodju i Borisa. Tko se nije mogao javiti na telefon i zbog toga 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 zvali.

[Dodatak sl.9]

Sa slike je jasno da su svi momci - Andrej, Boris i Volodja - telefonirali svima ostalima. Zato su ovi momci došli u kino. Ali Galya i Dasha nisu uspjele razgovarati (točke G i E nisu spojene crtom) i stoga, u skladu s dogovorom, nisu došle u kino.

Primjena grafova u različitim područjima života ljudi

Osim navedenih primjera, grafovi imaju široku primjenu u građevinarstvu, elektrotehnici, menadžmentu, logistici, geografiji, strojarstvu, sociologiji, programiranju, automatizaciji tehnoloških procesa i proizvodnje, psihologiji i oglašavanju. Dakle, iz svega navedenog nepobitno proizlazi praktična vrijednost teorije grafova, čije je dokazivanje i bio cilj ovog rada.

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 problema u fizici, kemiji, elektronici i automatizaciji. Mnoge matematičke činjenice mogu se zgodno formulirati jezikom grafikona. Teorija grafova dio je mnogih znanosti. Teorija grafova jedna je od najljepših i najzornijih matematičkih teorija. Teorija grafova u posljednje vrijeme nalazi sve više primjena u primijenjenim problemima. Pojavila se čak i računalna kemija - relativno mlado polje 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 prikazuju strukturu molekula [Dodatak sl. 10]. Vrhovi i rubovi ovih grafova odgovaraju odgovarajućim atomima i kemijskim vezama među njima.

Molekularni grafikoni i stabla: [Dodatak sl. 10] a, b - multigrafi, redom. etilen i formaldehid; oni kažu izomeri pentana (stabla 4, 5 su izomorfna stablu 2).

U stereokemiji organizama najviše. Često se koriste molekularna stabla - glavna stabla molekularnih grafova, koja sadrže samo sve vrhove koji odgovaraju atomima C. Kompilacija skupova mol. stabla i utvrđivanje njihove izomorfnosti omogućuju utvrđivanje da kažu. strukture i pronaći ukupan broj izomera alkana, alkena i alkina

Proteinske mreže

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

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

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

Za svaki par vrhova stabla postoji jedinstvena staza koja ih povezuje. Ovo se svojstvo koristi kada se pronalaze svi preci, na primjer, po muškoj liniji, bilo koje osobe čije je podrijetlo predstavljeno u obliku obiteljskog stabla, koje je "stablo" u smislu teorije grafova.

Primjer mog obiteljskog stabla [Dodatak sl. 12].

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

Rješavanje problema

1.Prometni zadatak. Neka u gradu Krasnodaru bude baza sa sirovinama koje treba distribuirati u gradove Krymsk, Temryuk, Slavyansk-on-Kuban i Timashevsk u jednom putovanju, trošeći što manje vremena i goriva i vraćajući se natrag u Krasnodar .

Riješenje:

Najprije napravimo grafikon svih mogućih ruta putovanja [Dodatak sl.14], uzimajući u obzir realne prometnice između ovih naselja i njihovu udaljenost. Da bismo riješili ovaj problem, moramo napraviti još jedan graf, nalik stablu [Dodatak sl.15].

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

Rezultat su 24 rješenja, ali trebaju nam samo najkraći putevi. Od svih rješenja samo su dva zadovoljavajuća, ovo je 350 km.

Slično tome, moguće je i, mislim, potrebno izračunati stvarni prijevoz s jednog mjesta na drugo.

Logičan problem koji uključuje transfuziju. Kanta sadrži 8 litara vode, a tu su i dvije posude od 5 i 3 litre. potrebno je u posudu od pet litara uliti 4 litre vode i ostaviti 4 litre u kanti, odnosno uliti vode jednako u kantu i veliku tepsiju.

Riješenje:

Stanje se u svakom trenutku može opisati s tri brojke [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 oni, kako su strukturirani, od kojih se komponenti sastoje, koji su alati pomoću kojih se problemi rješavaju.

Rješavajući praktične probleme pomoću 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, leži u činjenici da morate biti u stanju analizirati i kodirati stanje problema. Druga faza je shematski zapis, koji se sastoji od geometrijskog prikaza grafova, au ovoj fazi element kreativnosti je vrlo važan jer je daleko od lakog pronalaženja podudarnosti između elemenata uvjeta i odgovarajućih elemenata uvjeta. graf.

Rješavajući transportni problem ili zadatak sastavljanja obiteljskog stabla, došao sam do zaključka da je metoda grafikona svakako zanimljiva, lijepa i vizualna.

Uvjerio sam se da se grafikoni široko koriste u ekonomiji, menadžmentu i tehnologiji. Teorija grafova također se koristi u programiranju. O tome se nije raspravljalo u ovom radu, ali mislim da je samo pitanje vremena.

Ovaj znanstveni rad ispituje matematičke grafove, područja njihove primjene, te rješava nekoliko problema pomoću grafova. Poznavanje osnova teorije grafova potrebno je u raznim područjima vezanim uz upravljanje proizvodnjom i poslovanjem (primjerice, raspored izgradnje mreže, raspored dostave pošte). Osim toga, radeći na znanstvenom radu, savladao sam rad na računalu koristeći uređivač teksta WORD. Time su ciljevi znanstvenog rada ispunjeni.

Dakle, iz svega navedenog nepobitno proizlazi praktična vrijednost teorije grafova, čije je dokazivanje i bio cilj 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 njihova primjena. -M.: Mir, 1965.

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

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

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

"Soros Educational Journal" broj 11 1996 (članak "Flat graphs");

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

Olehnik S. N., Nesterenko Yu. V., Potapov M. K. “Stari zabavni problemi”, M. “Znanost”, 1988 (dio 2, odjeljak 8; dodatak 4);

Primjena

Riža. 6

Riža. 7

Riža. 8

primjena

Primjena

Riža. 14

primjena

Primjena

Među problemima povezanim s rješavanjem logičkih problema, veliku pozornost istraživača posljednjih godina privuklo je pitanje primjene teorije grafova na ovu vrstu problema.

Teorija grafova trenutno je grana diskretne matematike koja se intenzivno razvija. To se objašnjava činjenicom da su mnogi objekti i situacije opisani u obliku grafičkih modela: komunikacijske mreže, sklopovi električnih i elektroničkih uređaja, kemijske molekule, odnosi među ljudima i još mnogo toga.

Grafički zadaci imaju niz prednosti koje omogućuju njihovu upotrebu za razvoj mašte i poboljšanje logičkog razmišljanja. Problemi s grafikonima mogu se predstaviti u zabavnom, razigranom obliku.

Predmet istraživanja u ovom radu je rješavanje logičkih problema pomoću grafova.

Svrha studije: primijeniti graf aparat za rješavanje logičkih problema.

Hipoteza: Po našem mišljenju, rješavanje mnogih logičkih problema bit će manje radno intenzivno; za to ćemo koristiti teoriju grafova.

Ciljevi istraživanja:

razmotriti rješavanje problema pomoću grafikona;

naučiti prevesti probleme u jezik grafikona;

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

Godine 1736. veliki matematičar Leonhard Euler pronašao je rješenje zagonetke zvane Königsberški problem mosta. Rijeka Pregel, koja protječe kroz Kalinjingrad (prije se grad zvao Königsberg) ispire dva otoka (Slika 1 Slika 1). U Eulerovo vrijeme obale rijeke i otoke povezivali su mostovi kao što je prikazano na slici. Zagonetka je zahtijevala pronalaženje rute koja jednom prolazi kroz sve četiri kopnene mase, a kraj i početak puta moraju se podudarati.

Slika 1

L. Euler je dokazao da ne postoji put koji bi zadovoljio uvjete zagonetke i razvio teoriju za rješavanje ove vrste zagonetke. Poznavajući gradivo iz uvodnog dijela kolegija “Uvod u grafove” nije teško reproducirati ideju rezoniranja L. Eulera. Da biste to učinili, prvo morate zamijeniti sliku 1 dijagramom prikazanim na slici 2, gdje su otoci i obale predstavljeni točkama.

Slika 2

Dijagram prikazan na slici 2 nije, strogo govoreći, graf: ima više rubova. Međutim, godina 1736., kada je ova zagonetka riješena, općenito se smatra godinom rođenja teorije grafova.

Više od sto godina kasnije, 1874. godine, njemački znanstvenik G. Kirchhoff razvio je učinkovitu metodu za određivanje vrijednosti struje u električnom krugu, koristeći metode i koncepte koji su kasnije dobili građanska prava u teoriji grafova. Još 10 godina kasnije engleski matematičar A. Keli (majka mu je bila Ruskinja, govorio je ruski i pratio rusku matematičku literaturu; bio je među onim rijetkim matematičarima koji su od samog početka razumjeli i podržavali ideje N. I. Lobačevskog) razvio je teoriju stabla za prebrojavanje broja izomera zasićenih ugljikovodika sa zadanim brojem n atomi ugljika.

U matematici, graf je konačna zbirka točaka koje se nazivaju vrhovi; koji su od njih međusobno povezani linijama koje se nazivaju rubovi grafa.

Graf je skup točaka prikazanih na ravnini (list papira, ploča), od kojih su neki parovi povezani linijama. Točke se nazivaju vrhovi grafa, linije se nazivaju bridovi. Stupanj vrha je broj bridova koji izlaze iz vrha.

Kad pogledate geografsku kartu, željeznička mreža odmah upada u oči. Ovo je tipičan graf: krugovi predstavljaju stanice koje su vrhovi grafa, a staze koje ih povezuju predstavljaju rubove.

Slika 3

Graf na slici. Slika 3 prikazuje dijagram cesta između sela M, A, B, C i D. Ovdje su svaka dva vrha povezana rubom. Takav se graf naziva potpunim. Brojevi na slici označavaju udaljenosti između sela duž ovih cesta. Neka postoji poštanski ured u selu M i poštar mora dostavljati pisma u ostala četiri sela. Postoji mnogo različitih ruta putovanja. Kako odabrati najkraći? Najlakši način je analizirati sve opcije. U tome će vam pomoći novi grafikon koji olakšava pregled mogućih ruta. Vrh M na vrhu je početak smjerova. Odatle možete započeti putovanje na četiri različita načina: do A, do B, do C ili do D. Nakon posjeta jednom od sela, postoje tri opcije za nastavak rute, zatim dvije, zatim cestom do posljednjeg sela i opet na M. Ukupno 43 21  24 načina.

Slični problemi često se javljaju pri pronalaženju najboljih opcija za distribuciju robe u trgovine i materijala na gradilišta.

Razmotrite jedan od najjednostavnijih problema: „Crvena, plava, žuta i zelena olovka su u četiri kutije, jedna po jedna. Boja olovke razlikuje se od boje kutije. Poznato je da je zelena olovka u plavoj kutiji, ali crvena nije u žutoj. U kojoj kutiji svaka olovka dolazi?”

Označimo olovke i kutije točkama. Puna linija označava da je olovka u odgovarajućem okviru, a isprekidana linija označava da nije. Zatim, uzimajući u obzir problem, imamo G 1 (Sl. Slika 4).

Slika 4

Zatim dovršavamo grafikon prema sljedećem pravilu: budući da u kutiji može ležati točno jedna olovka, tada bi iz svake točke trebala izaći jedna puna linija i tri točkaste. Rezultat je grafikon G 2 , koji daje rješenje problema.

Pri rješavanju problema koji se u znanstveno-popularnoj i metodičkoj literaturi obično nazivaju logičkim, u pravilu se značajnije ne oslanjaju na školska znanja i vještine. U tom smislu, tradicionalno se smatraju mjerilom domišljatosti, pokazateljem razine matematičkih sposobnosti, oštrine mišljenja, sposobnosti korištenja pamćenja, a često se o njima raspravlja u školskim matematičkim klubovima.

Rješavanje mnogih logičkih problema pomoću grafikona sasvim je dostupno mlađim učenicima. Da bi to učinili, dovoljno im je samo intuitivno razumijevanje grafova i njihovih najočitijih svojstava.

Pogledajmo primjere korištenja grafova za rješavanje nekih dobro poznatih problema. U ovom slučaju objekte ćemo prikazati točkama, a odnose među njima segmentima (položaji točaka i duljine segmenta su proizvoljni).

Pojašnjenje strukture logičkih problema sa stajališta primijenjenih metoda rješavanja omogućuje izdvajanje određenih klasa takvih problema.

Zadatak 1. Razgovaraju tri prijatelja: Belokurov, Černov i Rižov. Brineta je rekla Belokurovu: "Zanimljivo je da je jedna od nas plavuša, druga brineta, treća crvena, ali nikome boja kose ne odgovara prezimenu." Koju boju kose ima svaka tvoja prijateljica?

Dajmo detaljno rješenje. Konstruirajmo graf odnosa navedenog u tvrdnji problema. Da bismo to učinili, prije svega, istaknimo puno prezimena M i mnoge boje kose DO,čiji će elementi biti označeni točkama. Postavite točke M nazovimo ih slovima B, Ch, R (Belokurov, Chernov i Ryzhov); bodovi drugog seta - b, br, p (plavuša, brineta, crvena). Ako točka iz jednog skupa odgovara točki iz drugog, spojit ćemo ih punom linijom, a ako ne odgovara, spojit ćemo ih isprekidanom linijom. Stanje problema ukazuje samo na nedosljednosti, pa bi se prvo trebao pojaviti grafikon prikazan na slici 5.

Slika 5

Iz uvjeta zadatka proizlazi da za svaku točku iz skupa M postoji jedna i samo jedna tonka od mnogih DO, koja odgovara prvoj i obrnuto svakoj točki iz skupa DO odgovara jednoj i samo jednoj točki iz skupa M. Zadatak se svodi na pronalaženje te jedine moguće korespondencije među elementima skupova M I DO, tj. do pronalaženja tri pune linije koje povezuju odgovarajuće točke skupova.

Princip rješavanja problema je jednostavan. Ako je neka točka spojena s dvije točke drugog skupa isprekidanim crtama, tada mora biti povezana sa svojom trećom točkom punom linijom. Stoga je grafikon na slici 5. dopunjen punim linijama koje povezuju točke B i p, P i b (slika 6.).

Slika 7

Dakle, na grafikonu ove figure automatski čitamo odgovor: Belokurov je crvenokos, Chernov je plavuša, Ryzhov je brineta. Ista tehnika se može koristiti za rješavanje, na primjer, problema 2 i 3.

Zadatak 2. Za Vanju, Kolju i Mišu pekle su se pite: jedna s kupusom, druga s rižom, treća s jabukama. Miša ne voli pitu od jabuka i ne jede je sa kupusom. Vanja ne voli pitu od kupusa. Tko jede kakvu pitu?

Zadatak 3. Tri prijatelja rade u istoj tvornici: mehaničar, tokar i zavarivač. Prezivaju se Borisov, Ivanov i Semenov. Bravar nema braće ni sestara, on je najmlađi od svojih prijatelja. Semenov, oženjen Borisovljevom sestrom, stariji je od tokara. Kako se zovu mehaničar, tokar i zavarivač?

Navedeni problemi mogu se uspješno riješiti pomoću tablica. Ova metoda ili njezine modifikacije preporučuju se i raspravljaju u mnogim znanstveno-popularnim knjigama i nastavnim pomagalima. Moguće je, međutim, naznačiti klase problema u kojima se korištenje grafova predstavljenih točkama i segmentima pokazuje prikladnijim i opravdanijim. Korištenje metode tablica kao što su turnirske tablice ili njihove generalizacije u odlukama prisiljavaju da se važan dio obrazloženja provodi “usmeno”. U isto vrijeme, morate se opetovano vraćati na uvjete problema, na međurezultate, zapamtiti puno i koristiti informacije primljene u pravo vrijeme. Ova vrsta problema uključuje probleme s tri ili više skupova objekata koji se razmatraju.

Zadatak 4. Tri druga - Ivan, Dmitrij i Stepan - predaju razne predmete (kemiju, biologiju, fiziku) u školama u Moskvi, Lenjingradu i Kijevu. Znan:

1. Ivan ne radi u Moskvi, a Dmitrij ne radi u Lenjingradu;

2. Moskvič ne predaje fiziku;

3. Onaj koji radi u Lenjingradu predaje kemiju;

4. Dmitrij ne predaje biologiju.

Koji predmet i u kojem gradu svaki od drugova predaje?

Riješenje. Razlikujemo tri skupa: skup imena, skup objekata i skup gradova. Element svakog od skupova na slici 4 zadan je vlastitom točkom (slova na ovoj slici su prva slova odgovarajućih riječi). Ako dvije točke iz različitih skupova karakteriziraju karakteristike različitih ljudi, tada ćemo takve točke spojiti isprekidanom linijom. Ako dvije točke iz različitih skupova odgovaraju osobinama jedne osobe, tada ćemo takve točke u parove spojiti punim crtama. Važno je da, prema uvjetima problema, za svaku točku bilo kojeg skupa u svakom od ostalih skupova postoji jedna i samo jedna točka koja mu odgovara.

Slika 8

Dakle, graf na slici 8 sadrži sve elemente skupova navedenih u uvjetu i odnose među njima. Problem u jeziku grafova svodi se na pronalaženje tri "puna" trokuta s vrhovima u različitim skupovima.

Razmotrimo graf na slici 8. Crtkani segment XD sugerira sam sebe. Doista, A odgovara X i, u isto vrijeme, A ne odgovara D, tj. X ne može odgovarati D. Dakle, tipična operacija grafa za ovo koristi se vrsta problema: ako trokut s vrhovima u tri različita skupa, jedna stranica je puna, druga je isprekidana, tada treća mora biti isprekidana. Iz uvjeta zadatka proizlazi da je još jedna operacija na grafu uniformna: ako je neka točka spojena isprekidanim segmentima s dvije točke u drugom skupu, tada treba biti povezana s trećom točkom tog skupa punim segmentom. Tako se crta kontinuirani segment DF-a. Zatim nacrtajte isprekidani segment DM (u trokutu DFM stranica DF je puna, a FM je isprekidana), DK je pun (DM i DL su isprekidani), Sada povezujemo točke F i K punim segmentom. Ako su u trokutu s vrhovima u različitim skupovima dvije strane čvrste, tada će i treća biti čvrsta. Pronađen je prvi "puni" trokut DFK. Dakle, bez vraćanja na tekst zadatka, vođeni samo prirodnim operacijama na gore opisanom grafu, nalazimo rješenje (slika 9).

Slika 9

Zabilježimo redoslijed kojim su segmenti izvedeni: HD, DF, DM, DK, FC, MS, IL, CI, BM, BS. Vrhovi svakog od tri dobivena "puna" trokuta određuju odgovor na problem: Ivan predaje kemiju u Lenjingradu, Dmitrij predaje fiziku u Kijevu, a Stepan predaje biologiju u Moskvi.

U sljedećem problemu korištenje grafova pomaže u otkrivanju prisutnosti dva rješenja.

Zadatak 5. Masha, Lida, Zhenya i Katya znaju svirati različite instrumente (violončelo, klavir, gitara i violina), ali svaka samo na jednom.Također govore različite strane jezike (engleski, francuski, njemački i španjolski), ali svaka samo na jednom . Poznato je :

1. djevojka koja svira gitaru govori španjolski;

2. Lida ne svira violinu ni violončelo i ne zna engleski;

3. Maša ne svira violinu ni violončelo i ne zna engleski;

4. djevojka koja govori njemački ne svira violončelo;

5. Zhenya zna francuski, ali ne svira violinu.

Tko svira koji instrument i koji strani jezik zna?

Uvjeti problema odgovaraju grafikonu prikazanom na slici 10.

Slika 10

Oznaka i princip rješenja ovdje su isti kao u problemu 4. Nacrtajmo redom sljedeće čvrste segmente: KS, VZH, VF, AK (slika 11).

Slika 11

Tako se formiraju dva "čvrsta" trokuta ZHVF i KSA. Obavljamo još jedan kontinuirani segment rakete-nosača. Sada smo uvjereni da uvjeti problema ne osiguravaju jednoznačan izbor treće točke za svaki od parova RN i GI. Moguće su sljedeće opcije za "pune" trokute: MGI i OSR ili LGI i MRN. Dakle, problem ima dva rješenja.

Predstavimo problem u kojem graf omogućuje prilično lako otkrivanje redundancije uvjeta.

Zadatak 6. U šahovskom turniru sudjelovalo je šest partnera različitih zanimanja: tokar, strojar, strojar, učitelj, liječnik i vozač. Znan:

1. u prvom kolu igrao je Andrejev s doktorom, učitelj s Borisovim, a Grigorjev s Evdokimovim;

2. u drugom kolu Dmitrijev je igrao s prevrtačem, a doktor s Borisovim;

3. u trećem kolu Evdokimov je igrao s inženjerom;

4. na kraju turnira mjesta su bila ovako raspoređena - Borisovjamjesto, dijelili su Grigoriev i inženjerIIIIIImjesta, Dmitrijev je zauzeoIVmjesto, a Zolotarev i mehaničar su podijelili peto i šesto mjesto.

Koja su zanimanja imali Grigoriev, Dmitriev i Evdokimov?

Tekst rada je objavljen bez slika i formula.
Puna verzija rada dostupna je u kartici "Radne datoteke" u PDF formatu

UVOD

“U matematici ne treba pamtiti formule, nego proces razmišljanja...”

E. I. Ignatiev

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

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

Cilj je identificirao sljedeće zadaci:

upoznati se s poviješću teorije grafova;

proučavati temeljne pojmove teorije grafova i glavne karakteristike grafova;

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

Razmotrite načine rješavanja problema pomoću grafikona i izradite vlastite probleme.

Objekt istraživanje: sfera ljudske djelatnosti za primjenu metode grafa.

Artikal Istraživanje: odjel matematike “Teorija grafova”.

Hipoteza. Pretpostavljamo da učenje teorije grafova može pomoći učenicima u rješavanju logičkih problema u matematici, što će oblikovati njihove buduće interese.

Metode istraživački rad:

Tijekom našeg istraživanja korištene su sljedeće metode:

1) Rad s različitim izvorima informacija.

2) Opis, prikupljanje, sistematizacija građe.

3) Promatranje, analiza i usporedba.

4) Priprema zadataka.

Teorijski i praktični značaj Ovaj rad je određen činjenicom da se rezultati mogu koristiti u informatici, matematici, geometriji, crtanju i razrednoj nastavi, kao i širokom krugu čitatelja zainteresiranih za ovu tematiku. Istraživački rad ima jasnu praktičnu usmjerenost, budući da autor u radu iznosi brojne primjere uporabe grafova u mnogim područjima znanja, te je izradio 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 koja predstavlja niz točaka povezanih linijama. "Grof" dolazi od latinske riječi "graphio" - pišem, poput poznate plemićke titule.

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

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

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

Primjeri grafikona uključuju crteže poligona, električnih krugova, shematske prikaze zrakoplovnih prijevoznika, podzemnih željeznica, cesta itd. Obiteljsko stablo također je graf, gdje su vrhovi članovi klana, a obiteljske veze djeluju kao rubovi grafa.

Riža. 1 Primjeri grafikona

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

Riža. 2 vrh grafa

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

Potpuni graf je graf u kojem je svaki par vrhova povezan bridom. Kao primjer potpunog grafa može poslužiti N-kut u kojem su sve dijagonale nacrtane.

Ako odaberete put u grafu gdje se početna i završna točka podudaraju, tada se takav put zove ciklus grafa . Ako se svaki vrh grafa prođe najviše jednom, tada ciklus nazvao jednostavan .

Ako su svaka dva vrha u grafu povezana bridom, onda je ovo povezan graf. Graf se zove nepovezano , ako sadrži barem jedan par nepovezanih vrhova.

Ako je graf povezan, ali ne sadrži cikluse, tada se takav graf naziva drvo .

Grofova staza je niz u kojem se svaka dva susjedna brida koji dijele zajednički vrh pojavljuju samo jednom.

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

Vertex A nazvao centar graf, ako je udaljenost između vrhova A a svaki drugi vrh je najmanji mogući. Postoji takva udaljenost radius graf.

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

Bojanje i primjena grafova.

Ako pažljivo pogledate geografsku kartu, možete vidjeti željeznice ili autoceste, koje su grafikoni. Osim toga, na karti se nalazi grafikon koji se sastoji od granica između država (okruga, regije).

Godine 1852. engleski student Francis Guthrie dobio je zadatak da oboji kartu Velike Britanije, ističući svaku zemlju zasebnom bojom. Zbog malog izbora boja, Guthrie ih je ponovno upotrijebio. Boje je birao tako da su one županije koje su dijelile zajednički dio granice nužno bile obojane različitim bojama. Postavilo se pitanje koja je minimalna količina boje potrebna za bojanje raznih karata. Francis Guthrie je predložio, iako nije mogao dokazati, da bi četiri boje bile dovoljne. O ovom problemu se žustro raspravljalo u studentskim krugovima, ali je kasnije zaboravljen.

„Problem četiri boje“ izazivao je sve veći interes, ali nikada nije riješen, čak ni od strane eminentnih matematičara. Godine 1890. engleski matematičar Percy Heawood dokazao je da bi pet boja bilo dovoljno za bojanje svake karte. Tek su 1968. uspjeli dokazati da bi 4 boje bile dovoljne da se oboji karta koja prikazuje manje od četrdeset zemalja.

Godine 1976. ovaj su problem pomoću računala riješila dva američka matematičara Kenneth Appel i Wolfgangt Haken. Da bi se to riješilo, sve karte su podijeljene u 2000 vrsta. Izrađen je računalni program koji je ispitivao sve vrste kako bi identificirao karte za čije bojanje četiri boje nisu dovoljne. Računalo nije moglo proučavati samo tri vrste karata, pa su ih matematičari proučavali sami. Kao rezultat toga, utvrđeno je da bi 4 boje bile dovoljne za bojanje svih 2000 vrsta karata. Najavili su rješenje problema četiri boje. Na današnji dan pošta sveučilišta na kojem su radili Appel i Haken stavila je pečat na sve marke s riječima: “Četiri boje su dovoljne”.

Problem četiri boje možete zamisliti malo drugačije.

Da biste to učinili, razmotrite proizvoljnu kartu, predstavljajući je u obliku grafa: glavni gradovi država su vrhovi grafa, a rubovi grafa povezuju one vrhove (glavne gradove) čije države imaju zajedničku granicu. Da bi se dobio takav graf, formuliran je sljedeći problem: potrebno je obojiti graf u četiri boje tako da vrhovi koji imaju zajednički brid budu obojeni različitim bojama.

Eulerov i Hamiltonov graf

Godine 1859. engleski matematičar William Hamilton izdao je zagonetku - drveni dodekaedar (dodekaedar), čijih je dvadeset vrhova bilo označeno klinovima. Svaki vrh nosio je ime jednog od najvećih gradova na svijetu - Kanton, Delhi, Bruxelles itd. Zadatak je bio pronaći zatvorenu stazu koja ide duž rubova poliedra, posjećujući svaki vrh samo jednom. Za označavanje staze korištena je uzica koja je bila zakačena na čavle.

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

Grad Kaliningrad (bivši Koenigsberg) nalazi se na rijeci Pregel. Rijeka je oplakivala dva otoka, koji su međusobno i s obalama bili povezani mostovima. Starih mostova više nema. Uspomena na njih ostala je samo na karti grada.

Jednog dana, stanovnik grada upitao je svog prijatelja je li moguće pješačiti preko svih mostova, posjetiti svaki samo jednom i vratiti se na mjesto gdje je šetnja počela. Ovaj problem zanimao je mnoge građane, ali nitko ga nije mogao riješiti. Ovo pitanje izazvalo je interes znanstvenika iz mnogih zemalja. Rješenje problema dobio je matematičar Leonhard Euler. Osim toga, formulirao je opći pristup rješavanju takvih problema. Da bi to učinio, pretvorio je kartu u grafikon. Vrhovi ovog grafa bili su zemlja, a rubovi su bili mostovi koji ga povezuju.

Rješavajući problem Königsberškog mosta, Euler je uspio formulirati svojstva grafova.

Moguće je nacrtati graf tako da se jednim potezom krene od jednog vrha i završi na istom vrhu (bez povlačenja po istoj liniji dva puta i bez podizanja olovke s papira) ako su svi vrhovi grafa parni.

Ako postoji graf s dva neparna vrha, tada se i njegovi vrhovi mogu povezati jednim potezom. Da biste to učinili, morate početi od jednog i 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, možemo vidjeti da su svi vrhovi proučavanog grafa neparni, što znači da se ovaj graf ne može povezati jednim potezom, tj. Nemoguće je jednom prijeći sve mostove i završiti putovanje tamo gdje je počelo.

Ako graf ima ciklus (ne nužno jednostavan) koji sadrži sve bridove 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 NJEZINIH REZULTATA

2.1. Faze studije

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

Faze istraživanja

Stol 1.

		Korištene metode
Teorijska studija problema	Proučavati i analizirati nastavnu i znanstvenu literaturu.	- samostalno razmišljanje;  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; - pregled.
Faza 3. Praktična upotreba rezultata	Sažmite proučene informacije;	- sistematizacija;  izvješće (usmeno, pismeno, uz demonstraciju materijala)	rujna 2017

2.2. Područja praktične primjene grafova

Grafikoni i informacije

Teorija informacija u velikoj mjeri koristi svojstva binarnih stabala.

Na primjer, ako trebate kodirati određeni broj poruka u obliku određenih nizova nula i jedinica različitih duljina. 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 ovaj problem, Huffman je predložio algoritam u kojem je kod predstavljen kao graf stabla u okviru teorije pretraživanja. Za svaki vrh je predloženo pitanje čiji odgovor može biti ili "da" ili "ne" - što odgovara dvama rubovima koji izlaze iz vrha. Izgradnja takvog stabla je završena nakon što se utvrdi što je potrebno. Ovo se može koristiti za intervjuiranje više osoba, kada je odgovor na prethodno pitanje unaprijed nepoznat, plan intervjua se prikazuje kao binarno stablo.

Grafikoni i kemija

A. Cayley također je 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 najjednostavnijih ugljikovodika prikazane su na slici.

Svaka molekula zasićenog ugljikovodika može se prikazati kao stablo. Kada se uklone svi atomi vodika, preostali atomi ugljikovodika tvore stablo s vrhovima čiji stupanj nije viši od četiri. To znači da je broj mogućih željenih struktura (homologa određene supstance) jednak broju stabala čiji vrhovi stupnjeva nisu veći od 4. Ovaj problem se svodi na problem nabrajanja stabala određene vrste. D. Polya je razmatrao ovaj problem i njegove generalizacije.

Grafovi i biologija

Proces razmnožavanja bakterija jedan je od tipova procesa grananja koji se nalaze u biološkoj teoriji. Neka svaka bakterija nakon određenog vremena ili umre ili se podijeli na dva dijela. Dakle, za jednu bakteriju dobivamo binarno stablo reprodukcije njezinih potomaka. Pitanje problema je sljedeće: koliko padeža sadrži? k potomci u n-toj generaciji jedne bakterije? Taj se odnos u biologiji naziva Galton-Watsonov proces, što označava potreban broj potrebnih slučajeva.

Grafikoni i fizika

Težak i zamoran zadatak za svakog radioamatera je izrada tiskanih krugova (ploča od dielektrično - izolacijskog materijala i urezane staze u obliku metalnih traka). Sjecište staza događa se samo u određenim točkama (mjesta trioda, otpornika, dioda 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 prikazati kao graf, gdje su vrhovi grafa internetske stranice, a rubovi poveznice (hiperveze) koje idu s jedne stranice na drugu.

Web graf (Internet), koji ima milijarde vrhova i rubova, neprestano se mijenja - stranice se spontano dodaju i nestaju, linkovi nestaju i dodaju se. Međutim, Internet ima matematičku strukturu, pridržava se teorije grafova i ima nekoliko "stabilnih" svojstava.

Web graf je oskudan. Sadrži samo nekoliko puta više bridova nego vrhova.

Unatoč svojoj rijetkosti, internet je vrlo prenatrpan. Možete prijeći s jedne stranice na drugu koristeći veze u 5 - 6 klikova (poznata teorija o "šest rukovanja").

Kao što znamo, stupanj grafa je broj bridova kojima vrh pripada. Stupnjevi vrhova web grafa raspoređeni su prema određenom zakonu: udio mjesta (vrhova) s velikim brojem poveznica (rubova) je mali, a udio stranica s malim brojem poveznica velik. Matematički se to može napisati ovako:

gdje je udio vrhova određenog stupnja, je stupanj vrha, konstanta neovisna o broju vrhova u web grafu, tj. ne mijenja se tijekom procesa dodavanja ili uklanjanja mjesta (vrhova).

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

Internet kao cjelina otporan je na nasumične napade na stranice.

Budući da se uništavanje i stvaranje stranica događa neovisno i s istom vjerojatnošću, web graf s vjerojatnošću blizu 1 održava svoj integritet i ne biva 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 previše složen.

Ovaj problem još uvijek nije u potpunosti riješen! Rješavanje ovog problema - izgradnja visokokvalitetnog modela Interneta - omogućit će nam da razvijemo nove alate za poboljšanje pretraživanja informacija, prepoznavanje neželjene pošte i širenje informacija.

Izgradnja bioloških i ekonomskih modela započela je puno prije nego što se pojavio zadatak konstruiranja matematičkog modela Interneta. Međutim, napredak u razvoju i proučavanju Interneta omogućio je odgovore na mnoga pitanja vezana uz sve te modele.

Internetsku matematiku traže mnogi stručnjaci: biolozi (predviđanje rasta populacija bakterija), financijeri (rizici od kriza) itd. Proučavanje takvih sustava jedna je od središnjih grana primijenjene matematike i računalne znanosti.

Murmansk pomoću grafikona.

Kad čovjek stigne u novi grad, u pravilu je prva želja posjetiti glavne atrakcije. Ali u isto vrijeme, količina vremena je često ograničena, au slučaju poslovnog putovanja vrlo mala. Stoga je potrebno unaprijed planirati razgledavanje. A grafikoni će vam biti od velike pomoći u izgradnji vaše rute!

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

1. Morska pravoslavna crkva Spasa na vodi;

2. Katedrala Svetog Nikole;

3. Oceanarij;

4. Spomenik mačku Semjonu;

5. Nuklearni ledolomac Lenjin;

6. Park svjetla Murmanska;

7. Park Dolina utjehe;

8. Kolski most;

9. Muzej povijesti Murmanske brodarske tvrtke;

10. Trg pet uglova;

11. Morska trgovačka luka

Prvo, locirajmo ta mjesta na karti i dobijmo vizualni prikaz lokacije i udaljenosti između atrakcija. Cestovna mreža je prilično razvijena, pa putovanje automobilom neće biti teško.

Atrakcije na karti (lijevo) i dobiveni grafikon (desno) prikazani su na pripadajućoj slici u PRILOGU br.1. Tako će pridošlica prvo proći pored mosta Kola (i, ako želi, može ga prijeći naprijed-nazad); zatim će se opustiti u parku Svjetla Murmanska i Dolini utjehe i krenuti dalje. Kao rezultat toga, optimalna ruta bit će:

Pomoću grafikona također možete vizualizirati shemu za provođenje anketa. Primjeri su prikazani u PRILOGU br.2. Ovisno o danim odgovorima, ispitaniku se postavljaju različita pitanja. Primjerice, ako u sociološkoj anketi br. 1 ispitanik matematiku smatra najvažnijom znanosti, pitat će ga se osjeća li se samouvjereno na nastavi fizike; ako misli drugačije, drugo pitanje će se ticati potražnje za humanističkim znanostima. Vrhovi takvog grafa su pitanja, a bridovi su opcije odgovora.

2.3. Primjena teorije grafova na rješavanje problema

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

Zadatak br. 1.

Petero kolega iz razreda rukovalo se na srednjoškolskom okupljanju. Koliko je rukovanja učinjeno?

Rješenje: Označimo prijatelje iz razreda vrhovima grafa. Povežimo svaki vrh linijama s četiri druga vrha. Dobivamo 10 redaka, ovo su rukovanja.

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

Zadatak br. 2.

U selu moje bake, u blizini njene kuće, raste 8 stabala: topola, hrast, javor, jabuka, ariš, breza, oskoruša i bor. Oskoruša je viša 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 oskoruše, breza je niža od topole, a ariš je viši od jabuke. Kojim redom će stabla biti poredana po visini od najvišeg do najnižeg?

Riješenje:

Stabla su vrhovi grafa. Označimo ih prvim slovom u krugu. Povucimo strijele od niskog stabla do višeg. Kaže se da je oskoruša viša od ariša, zatim strijelu s ariša stavljamo na oskoruš, breza je niža od topole, pa strijelu s topole na brezu, itd. Dobivamo graf gdje vidimo da je najkraće stablo javor, zatim jabuka, ariš, oskoruša, bor, hrast, breza i topola.

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

Zadatak br. 3.

Mama ima 2 koverte: običnu i zračnu i 3 marke: kvadratnu, pravokutnu i trokutastu. Na koliko načina mama može odabrati kuvertu i marku da pošalje pismo tati?

Odgovor: 6 načina

Zadatak br. 4.

Izgrađene su ceste između naselja A, B, C, D, E. Trebate odrediti duljinu najkraćeg puta između točaka A i E. Kretati se možete samo cestama čija je duljina navedena na slici.

Zadatak br. 5.

Trojica kolega iz razreda - Maxim, Kirill i Vova odlučili su se baviti sportom i prošli izbor sportskih sekcija. Poznato je da se 1 dječak prijavio u košarkašku sekciju, a trojica su željela igrati hokej. Maxim je prošao samo audiciju za odjeljak 1, Kirill je odabran za sva tri odjeljka, a Vova za odjeljak 2. Tko je od dječaka odabran za koji sportski dio?

Rješenje: Za rješavanje problema koristit ćemo se grafovima

Košarkaški Maksim

Nogomet Kiril

Hokej Vova

Od do košarka ide samo jedna strelica, a zatim je Kirill odabran u odjeljak košarka. Tada Kirill neće igrati hokej, što znači u hokej odjeljak odabrao je Maxim, koji je bio na audiciji samo za ovaj odjeljak, zatim će biti Vova nogometaš.

Zadatak br. 6.

Zbog bolesti nekih nastavnika, ravnatelj škole mora izraditi dio školskog rasporeda za najmanje jedan dan, uzimajući u obzir sljedeće okolnosti:

1. Učitelj sigurnosti života pristaje održati samo posljednju lekciju;

2. Nastavnik geografije može držati ili drugi ili treći sat;

3. Matematičar je spreman dati ili samo prvu ili samo drugu lekciju;

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

Kakav raspored može napraviti ravnatelj škole da njime budu zadovoljni svi učitelji?

Rješenje: Ovaj problem se može riješiti prolaskom kroz sve moguće opcije, ali je lakše ako nacrtate grafikon.

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 je hipoteza da proučavanje grafova može pomoći u rješavanju logičkih problema, uz to je razmatrana teorija grafova u različitim područjima znanosti i sastavljeno je 7 problema.

Korištenje grafikona pri učenju učenika kako pronaći rješenja problema omogućuje učenicima da poboljšaju svoje grafičke vještine i komuniciraju razmišljanje posebnim jezikom konačnog skupa točaka, od kojih su neke povezane linijama. Sve to pridonosi radu poučavanja učenika razmišljanju.

Učinkovitost obrazovnih aktivnosti u razvoju mišljenja uvelike ovisi o stupnju kreativne aktivnosti učenika pri rješavanju matematičkih problema. Stoga su potrebni matematički zadaci i vježbe koje bi aktivirale mentalnu aktivnost učenika.

Primjenom zadataka i korištenjem elemenata teorije grafova u izbornoj nastavi u školi ide se upravo u cilju aktiviranja mentalne aktivnosti učenika. Vjerujemo da praktični materijal o našem istraživanju može biti koristan u izbornoj nastavi matematike.

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

POPIS KORIŠTENE LITERATURE

Berezina L. Yu. “Grafovi i njihova primjena” - M.: “Prosvjetljenje”, 1979.

Gardner M. “Matematička dokolica”, M. “Mir”, 1972

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

Gorbačov A. “Zbirka olimpijadnih problema” - M. MTsNMO, 2005.

Zykov A. A. Osnove teorije grafova. - M.: “Sveučilišna knjiga”, 2004. - S. 664

Kasatkin V. N. “Neobični problemi matematike”, Kijev, “Radianska škola”, 1987.

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

Melnikov O. I. “Zabavni problemi u teoriji grafova”, Mn. "TetraSystems", 2001

Melnikov O.I. Neznalica u zemlji grofova: Priručnik za studente. ur. 3., stereotipno. M.: KomKniga, 2007. - 160 str.

Olehnik S. N., Nesterenko Yu. V., Potapov M. K. “Stari zabavni problemi”, M. “Znanost”, 1988.

Ore O. “Grafovi i njihove primjene”, M. “Mir”, 1965

Harari F. Teorija grafova / Prijevod s engleskog. i predgovor V. P. Kozyreva. ur. G. P. Gavrilova. ur. 2. - M.: Editorial URSS, 2003. - 296 str.

PRILOG br.1

Izrada optimalne rute za obilazak glavnih atrakcija

Murmansk pomoću grafikona.

Optimalna ruta će biti:

8. Kolski most6. Svjetla parka Murmansk7. Park Dolina utjehe 2. Katedrala Svetog Nikole10. Trg pet uglova5. Nuklearni ledolomac Lenjin9. Muzej povijesti Murmanske brodarske tvrtke11. Morska trgovačka luka1. Morska pravoslavna crkva Spasa na vodi4. Spomenik mačku Semjonu3. Oceanarij.

VODIČ ZA ATRAKCIJE MURMANSKA

PRILOG br.2

Sociološka istraživanja br. 1, 2

Edukativno izdanje

Jujukin Nikolaj Aleksejevič

LR br. Potpisano za pečat

uč. ur. ja.. , .

Voronješko državno tehničko sveučilište

394026 Voronjež, Moskovsky Ave. 14

IMENIK MAGNETNIH DISKOVA

Katedra za višu matematiku i fizikalno-matematičko modeliranje

NA. Yuyukin

DISKRETNA MATEMATIKA 1. dio. Elementi teorije grafova

Tutorial

NA. Yuyukin

DISKRETNA MATEMATIKA 1. dio. Elementi teorije grafova

Tutorial

Voronjež 2004

UVOD

Ovaj priručnik mogu koristiti u kolegiju "Diskretna matematika" studenti VSTU koji studiraju u sljedećim specijalnostima:

090102 – Računalna sigurnost;

090105 – Sveobuhvatno osiguranje informacijske sigurnosti automatiziranih sustava;

090106 - Informacijska sigurnost telekomunikacijskih sustava.

Disciplina “Diskretna matematika” osigurava stjecanje znanja i vještina u skladu s državnim, općeobrazovnim standardom, a ujedno potiče stjecanje temeljnog obrazovanja, formiranje svjetonazora i razvoj logičkog mišljenja.

Teorija grafova učinkovit je alat za formaliziranje suvremenih inženjerskih problema povezanih s diskretnim objektima. Koristi se u projektiranju integriranih krugova i upravljačkih krugova, proučavanju automata i logičkih sklopova, u analizi sustava, automatiziranom upravljanju proizvodnjom, u razvoju računalnih i informacijskih mreža, u projektiranju sklopova i projektno-topološkom projektiranju itd.

Vodič ocrtava osnove, osnovne metode i algoritme teorije grafova. Ovdje predstavljamo n-grafove i digrafove; izomorfizmi; drveće; Eulerovi grafovi; planarni grafovi; obloge i samostalni setovi; snažna povezanost

V digrafovi; Analiza Markovljevog lančanog grafa; algoritmi za pronalaženje najkraćih puteva u grafovima; Problem traženja Hamiltonovog ciklusa

V grafikon; problem trgovačkog putnika; nabrajanje grafova i preslikavanja; ekstremni zadaci; problemi optimizacije; univerzalni zadaci; metoda grananja i vezanja; te također razviti praktične vještine u korištenju navedenih pojmova.

Svrha kolegija je razvijanje teorijskih znanja, praktičnih vještina i sposobnosti studenata u području modeliranja procesa i pojava u prirodnim znanostima i tehnici.

ke, uz sposobnost izražavanja matematičkim simbolima kvantitativnih i kvalitativnih odnosa objekata nužnih za obavljanje službenih poslova iz područja informacijske sigurnosti na visokoj stručnoj razini.

Za postizanje ovog cilja služe sljedeći zadaci:

proučavati najširi mogući raspon koncepata teorije grafova;

steći vještine rješavanja obrazovnih i praktičnih problema;

ovladati metodama optimizacije;

razvijati vještine postavljanja i rješavanja informacijskih problema, modeliranja i analiziranja informacija pomoću grafikona.

Disciplina “Diskretna matematika” jedna je od primijenjenih matematičkih disciplina. Temelji se na znanju koje su studenti stekli izučavajući discipline “Algebra” i “Matematička logika i teorija algoritama”. U studiju se koriste znanja i vještine stečene na studiju discipline “Diskretna matematika”. opći stručni i posebne discipline.

1. OSNOVNI POJMOVI TEORIJE GRAFOVA.

1.1. Problemi teorije grafova.

Teorija grafova je grana matematike koja proučava sustave veza između različitih objekata, baš kao što se radi s konceptom relacije. Međutim, neovisna definicija grafa pojednostavljuje prezentaciju teorije i čini je razumljivijom i vizualnijom.

Prvi problemi teorije grafova bili su vezani uz rješavanje zabavnih problema i zagonetki.

Prvi zadatak. Problem königsberških mostova postavio je i riješio Euler 1786. godine. Grad se nalazio na obalama i dva otoka rijeke Pregolya. Otoci su bili međusobno povezani s obalama sa sedam mostova, kao što je prikazano na slici.

Postavilo se pitanje: je li moguće napustiti kuću i vratiti se natrag, prelazeći svaki most točno jednom?

Drugi zadatak. Problem tri kuće i tri bunara. Ima tri kuće i tri bunara.

Potrebno je nacrtati put od svake kuće do svakog bunara kako se putevi ne bi križali. Zadatak je bio

riješio Pontrjagin i neovisno o njemu Kuratovsky u

Treći zadatak. Otprilike četiri boje. Obojite bilo koju kartu na ravnini s četiri boje tako da dva susjedna područja ne budu obojana istom bojom.

Mnogi rezultati iz teorije grafova koriste se za rješavanje praktičnih problema u znanosti i tehnologiji. Tako je sredinom 19. stoljeća Kirchhoff koristio teoriju grafova za izračunavanje složenih električnih krugova. No, kao matematička disciplina, teorija grafova formirala se tek 30-ih godina 20. stoljeća. U ovom slučaju, grafovi se smatraju nekim apstraktnim matematičkim objektima. Koriste se u analizi i sintezi sklopova i sustava, u mrežnom planiranju i upravljanju, operacijskim istraživanjima, programiranju, modeliranju života organizma i drugim područjima.

1.2. Osnovne definicije.

Graf G= (V,E) je skup dva skupa - nepraznog skupa vrhova V i skupa neuređenih i uređenih parova vrhova E. U nastavku ćemo razmatrati konačne grafove, tj. grafovi s konačnim skupom vrhova i konačnom obitelji parova. Neuređeni par vrhova naziva se brid, a uređeni par luk.

Tipično, graf je predstavljen dijagramom: vrhovi su točke (ili krugovi), rubovi su linije proizvoljne konfiguracije. Strelica dodatno označava njegov smjer na luku. Imajte na umu da kada prikazujete grafikon, nosač

Bitna su geometrijska svojstva bridova (duljina, zakrivljenost), kao i relativni položaj vrhova na ravnini.

Vrhovi koji ne pripadaju niti jednom bridu (luku) nazivaju se izolirani. Vrhovi povezani bridom ili lukom nazivaju se susjednim. Brid (luk) i bilo koji od njegova dva vrha nazivaju se incidentom.

Kažu da brid (u,v) povezuje vrhove u i v, a luk (u,v) počinje u vrhu u i završava u vrhu v, pri čemu se u naziva početak, a v kraj ovog luka.

Par vrhova može biti povezan s dva ili više bridova (lukova u istom smjeru). Takvi rubovi (lukovi) nazivaju se višestruki. Luk (ili rub) može započeti ili završiti na istom vrhu. Takav luk (brid) naziva se petlja. Graf koji sadrži petlje naziva se pseudograf. Graf koji ima više bridova (lukova) naziva se multigraf.

Graf bez petlji ili više rubova naziva se jednostavnim. Jednostavan graf nazivamo potpunim ako za bilo koji par njegovih vrhova postoji brid (luk) koji ih povezuje. Potpuni graf s n vrhova označava se s K n. Na primjer, ovo su grafikoni

Graf koji se sastoji od jednog izoliranog vrha (K 1) naziva se trivijalnim.

Komplement grafa G je graf G koji ima iste vrhove kao graf G i sadrži one bridove koje je potrebno dodati grafu G da bi se dobio potpuni graf.

Svakom nedigrafistu kanonski odgovara usmjereni graf s istim skupom vrhova, u kojem je svaki brid zamijenjen s dva luka incidentna na iste vrhove i suprotnih smjerova.

1.3. Stupnjevi vrhova grafa.

Stupanj (valencija) (oznaka d (v) ili deg (v)) vrha v jednostavnog grafa G je broj bridova ili lukova koji incidentiraju danom vrhu v. Pri izračunavanju valencije vrhova pseudografa, svaku petlju treba brojati dva puta.

Ako su stupnjevi svih vrhova n-grafa jednaki k, tada se graf naziva regularan (uniformiran) stupanj k. Ako je stupanj vrha 0, tada je on izoliran. Ako je stupanj vrha 1, tada se vrh naziva terminalni vrh (viseći, slijepi).

Za digraf se naziva broj lukova koji izlaze iz vrha v

varira polustupanj ishoda				(v), a dolazni – polustepeni-

novi poziv d			(v), U ovom slučaju relacija d (v)=

	(v)+	(v).

Eulerov teorem: Zbroj stupnjeva vrhova grafa je

udvostručiti broj rebara, tj.

d(vi)



			(v)

Gdje je n broj vrhova; m – broj

rebra (lukovi). Ovu tvrdnju dokazuje činjenica da se pri izračunavanju zbroja stupnjeva vrhova svaki brid uzima u obzir dva puta - za jedan i za drugi kraj brida.

1.4. Izomorfizam grafova.

Graf se naziva označenim (ili prenumeriranim) ako se njegovi vrhovi na neki način međusobno razlikuju.

oznake (brojevi). Grof se smatra potpuno dano u strogom smislu, ako je numeriranje njegovih vrhova i bridova fiksno. U tom slučaju se grafovi G 1 i G 2 nazivaju jednakima (oznaka G 1 = G 2), ako se njihovi skupovi vrhova i bridova podudaraju. Dva grafa ili pseudografa G 1 = (V 1 ,E 1 ) i G 2 = (V 2 ,E 2 ) nazivaju se

	izomorfan (oznaka G	ako postoje

	preslikavanja jedan na jedan: 1)	: V 1 V 2
: E 1 E 2 tako da za bilo koja dva vrha u, v u grafu
	vrijedi odnos ((u, v)) ((u), (v)).

	Dva jednostavna grafa (bez petlji i više rubova) G 1		i G 2