Graafiteooria rakendamine erinevates tegevusvaldkondades. Graafikute rakendamine

Graafiteooria alguseks loetakse üksmeelselt 1736. aastat, mil L. Euler lahendas tol ajal populaarse Königsbergi sildade probleemi. See tulemus jäi aga enam kui sajaks aastaks ainsaks graafiteooria tulemuseks. Alles 19. sajandi keskel töötas elektriinsener G. Kirchhoff välja puude teooria elektriahelate uurimiseks ja matemaatik A. Cayley lahendas seoses süsivesinike ehituse kirjeldamisega kolmele loendusülesandeid. puude liigid.

Mõistatuste lahendamisest ja meelelahutuslikest mängudest (probleemid malerüütliga, kuningannadega, ümbermaailmareisimine, pulmade ja haaremitega seotud probleemid jne) sündinud graafiteooriast on nüüdseks saanud lihtne, kättesaadav ja võimas vahend seotud probleemide lahendamisel. paljudele probleemidele. Graafikud on sõna otseses mõttes kõikjal. Graafikute kujul saate tõlgendada näiteks teekaarte ja elektriskeeme, geograafilisi kaarte ja molekule keemilised ühendid, seosed inimeste ja inimrühmade vahel. Viimase nelja aastakümne jooksul on graafiteooriast saanud üks kiiremini arenevaid matemaatika harusid. Selle põhjuseks on kiiresti laieneva rakendusvaldkonna nõudmised. Seda kasutatakse integraallülituste ja juhtlülituste projekteerimisel, automaatide, loogiliste lülituste, programmide plokkskeemide uurimisel, majanduses ja statistikas, keemias ja bioloogias, sõiduplaani teoorias. Suurel määral tungivad matemaatilised meetodid nüüd läbi graafiteooria teadusesse ja tehnoloogiasse.

Selles artiklis ei käsitleta mitte graafiteooria õigeid probleeme, vaid seda, kuidas seda kasutatakse kooli geomeetriakursustes.

Seetõttu tuleneb uurimisteema aktuaalsus ühelt poolt graafikute ja nendega seotud uurimismeetodite populaarsusest, mis orgaaniliselt läbivad erinevad tasemed peaaegu kogu kaasaegne matemaatika ja teisest küljest ei ole välja töötatud terviklik süsteem selle rakendamiseks geomeetria kursusel.

Õppetöö eesmärk on uurida graafikute kasutamist kooligeomeetria kursusel.

Objektiks on geomeetria õpetamise protsess.

Õppeaine – tunni- ja klassiväline töö

Eesmärgid: 1) selgitada välja graafikute kasutamise olemus ja sisu kooli geomeetria kursusel;

2) töötada välja PMC geomeetriatundide läbiviimiseks 7.-9.

Juhtivaks teemaks on geomeetriliste teoreemide tõestamise graafikumudeli koostamine.

Teoreetiline alus:

1. Graafiteooria, mis tekkis 1736. aastal (Leonard Euler (1708-1783), sai kiire arengu ja on endiselt aktuaalne, sest a. Igapäevane eluÜha enam kasutatakse graafilisi illustratsioone, geomeetrilisi kujutisi ja muid visualiseerimise tehnikaid ja meetodeid.

1. Graafiteooriat kasutatakse kaasaegse matemaatika erinevates valdkondades ja selle arvukates rakendustes (Lipatov E. P.)

2. Graafiteooriat kasutatakse sellistes matemaatika valdkondades nagu matemaatiline loogika, kombinatoorika jne.

Töö teoreetiline tähendus seisneb:

Graafiteooria rakendusvaldkondade väljaselgitamine;

Graafiteooria kasutamine geomeetriliste teoreemide ja probleemide uurimiseks;

Töö praktiline tähendus seisneb graafikute kasutamises geomeetriliste teoreemide tõestamisel ja ülesannete lahendamisel.

Selle töö tulemusena loodi järgmine:

Tarkvara ja metoodiline kompleks geomeetriatundide läbiviimiseks 7.-9.

Kõige keerulisem probleemile lahenduse leidmisel on loogiliste tagajärgede ahela loomine, mis viib tõestatud väiteni. Loogiliselt pädevaks arutlemiseks on vaja arendada sellise mõtlemise oskusi, mis aitaksid loogilistesse seostesse ehitada lahknevaid geomeetrilisi fakte.

Mõttekultuuri oskuste arendamiseks mängivad erilist rolli õpilaste kirjaliku kõne vormid. Kirjalikud töövormid on olulisim tegevusliik, mis arendab teoreemide tõestamisel ja ülesannete lahendamisel stabiilseid loogilise mõtlemise oskusi. Ülesande tingimuste fikseerimise vorm, mõistlikud lühendid ja tähistused arvutustes ja probleemide tõestustes distsiplineerivad mõtlemist ja soodustavad geomeetrilist nägemist. Nagu teate, sünnitab nägemine mõtlemise. Tekib probleem: kuidas luua loogilisi seoseid erinevate geomeetriliste faktide vahel ja kuidas neid ühtseks tervikuks vormida. Graafikdiagrammide meetod võimaldab näha teoreemide tõestamise ja ülesannete lahendamise edenemist, mis muudab tõestuse visuaalsemaks ning võimaldab lühidalt ja täpselt esitada teoreemide tõestused ja ülesannete lahendamise.

Selleks kasutatakse puugraafikut.

“Puu” tipud (teoreemi või ülesande tingimused ja loogiliste konnektiivide jada) on kujutatud ristkülikutega, millesse on paigutatud teave, mis ühendatakse seejärel nooltega. Graafikuskeemi lõpus on tõestatav väide. Kirjeldatud teoreemide tõestamise ja ülesannete lahendamise vorm on õpilastele kasulik ja mugav, kuna võimaldab hõlpsasti tuvastada teoreemide tõestamise ja ülesande lahendamise põhietapid.

Uurimistöö osa.

1. jagu. Graafiteooria tekkeloo uurimine.

Graafiteooria rajajaks peetakse matemaatik Leonhard Eulerit (1707-1783). Selle teooria ajalugu saab jälgida suure teadlase kirjavahetuse kaudu. Siin on ladinakeelse teksti tõlge, mis on võetud Euleri kirjast Itaalia matemaatikule ja insenerile Marinonile, mis saadeti Peterburist 13. märtsil 1736. aastal.

"Kunagi esitati mulle probleem Königsbergi linnas asuva saare kohta, mida ümbritseb jõgi, millest üle viskab seitse silda. Küsimus on selles, kas keegi saab neist pidevalt ümber sõita, läbides iga silla ainult korra. Ja siis ma olin teatati, et keegi ei saa seda ikka veel teha, kuid keegi pole ka tõestanud, et see on võimatu.. See küsimus, kuigi triviaalne, tundus mulle siiski tähelepanu vääriv, kuna ei geomeetriast, algebrast ega kombinatoorsest kunstist ei piisa lahendamiseks. Pärast pikka mõtlemist leidsin täiesti veenval tõendil põhineva lihtsa reegli, mille abil saab kõigi sedalaadi probleemide puhul kohe kindlaks teha, kas sellist ümbersõitu saab teha läbi suvalise arvu sildasid, mis asuvad nii või mitte. Nii et neid saab kujutada järgmisel joonisel, kus A tähistab saart ning B, C ja D mandri osi, mis on üksteisest jõe harudega eraldatud.Seitse silda on tähistatud tähed a, b, c, d, e, f, g".

Euler kirjutas meetodi kohta, mille ta avastas sedalaadi probleemide lahendamiseks

"Sellel lahendusel on oma olemuselt ilmselt vähe pistmist matemaatikaga ja ma ei saa aru, miks peaks seda lahendust ootama pigem matemaatikult kui üheltki teiselt inimeselt, sest seda otsust toetab ainult arutluskäik ja seda pole Selle lahenduse leidmiseks tuleb kaasata kõik matemaatikale omased seadused. Niisiis, ma ei tea, kuidas selgub, et küsimusi, millel on matemaatikaga väga vähe pistmist, lahendavad tõenäolisemalt matemaatikud kui teised."

Kas siis on võimalik Königsbergi sildadest ümber sõita, läbides neist sildadest ainult üks kord? Vastuse leidmiseks jätkame Euleri kirjaga Marinonile:

"Küsimus seisneb selles, kas kõigist neist seitsmest sillast on võimalik mööda minna, läbides iga ühe korra või mitte. Minu reegel viib sellele küsimusele järgmise lahenduseni. Kõigepealt tuleb vaadata, kui palju alasid seal on. on veega eraldatud - sellised , millel pole muud läbipääsu ühest teise, välja arvatud silla kaudu.Selles näites on neli sellist jaotist - A, B, C, D. Järgmiseks peate eristama, kas number Nendele üksikutele lõikudele viivate sildade arv on paaris või paaritu. Nii et meie puhul viib viis silda sektsiooni A ja kolm silda ülejäänud osani, st üksikute lõikudeni viivate sildade arv on paaritu ja sellest üksi piisab Kui see on kindlaks tehtud, rakendame järgmist reeglit: kui igale eraldi lõigule viivate sildade arv oleks paaris, oleks kõnealune ümbersõit võimalik ja samal ajal oleks võimalik seda alustada ümbersõit mis tahes lõigult.Kui aga kaks neist numbritest olid paaritud, sest ainult üks ei saa olla paaritu, siis ka siis võiks ülemineku lõpule viia, nagu ette nähtud, kuid kindlasti tuleb võtta ainult ümbersõidu algus üks neist kahest sektsioonist, kuhu viib paaritu arv sildu. Kui lõpuks oleks rohkem kui kaks lõiku, kuhu viib paaritu arv sildu, siis oleks selline liikumine üldse võimatu; kui siia tuuakse muid, tõsisemaid probleeme, oleks sellest meetodist veelgi suurem kasu ja ei tohi tähelepanuta jätta."

Eeltoodud reegli põhjenduse võib leida L. Euleri sama aasta 3. aprilli kirjast oma sõbrale Ehlerile. Allpool jutustame uuesti väljavõtte sellest kirjast.

Matemaatik kirjutas, et üleminek on võimalik, kui jõe hargnemiskohas, kuhu viib paaritu arv sildu, pole rohkem kui kaks ala. Et seda oleks lihtsam ette kujutada, kustutame jooniselt juba läbitud sillad. Lihtne on kontrollida, et kui hakkame liikuma vastavalt Euleri reeglitele, ületame ühe silla ja kustutame selle, siis on joonisel lõik, kus jällegi pole rohkem kui kaks ala, kuhu viib paaritu arv sildu ja kui on paaritu arvu sildadega alad, kus me asume ühes neist. Niimoodi edasi liikudes läbime kõik sillad ühe korra.

Königsbergi linna sildade lool on tänapäevane jätk.

Ülesanne Järvel on seitse saart, mis on omavahel ühendatud, nagu on näidatud joonisel 2. Millisele saarele peaks paat reisijaid viima, et nad saaksid ületada iga silla ja ainult ühe korra? Miks ei saa reisijaid saarele A transportida?

Lahendus. Kuna see ülesanne on sarnane Königsbergi sildade probleemiga, siis kasutame selle lahendamisel ka Euleri reeglit. Selle tulemusena saame järgmise vastuse: paat peab viima reisijad saarele E või F, et nad saaksid iga silla korra ületada. Samast Euleri reeglist järeldub, et nõutav ümbersõit on võimatu, kui see algab saarelt A.

Seejärel töötasid graafikute kallal Koenig (1774-1833), Hamilton (1805-1865) ja kaasaegsed matemaatikud C. Berge, O. Ore, A. Zykov.

Ajalooliselt tekkis graafiteooria rohkem kui kakssada aastat tagasi mõistatuste lahendamise protsessis. Väga pikka aega oli ta teadusliku uurimistöö põhisuundade kõrval, matemaatika kuningriigis oli ta Tuhkatriinu positsioonil, kelle anded ilmnesid täielikult alles siis, kui ta leidis end üldise tähelepanu keskpunktist.

Esimene graafiteooria alane teos, mis kuulus kuulsale Šveitsi matemaatikule L. Eulerile, ilmus aastal 1736. Graafiteooria sai tõuke arenguks 19. ja 20. sajandi vahetusel, mil ilmus tööde hulk topoloogia ja kombinatoorika vallas. , millega see on tihedalt seotud, järsult suurenenud sugulus. Graafe hakati kasutama elektriskeemide ja molekulaarahelate koostamisel. Eraldi matemaatilise distsipliinina esitleti graafiteooriat esimest korda Ungari matemaatiku Koenigi töös 20. sajandi 30. aastatel.

Viimasel ajal on graafikud ja nendega seotud uurimismeetodid orgaaniliselt läbinud peaaegu kogu kaasaegse matemaatika erinevatel tasanditel. Graafiteooriat peetakse üheks topoloogia haruks; see on otseselt seotud ka algebra ja arvuteooriaga. Graafikuid kasutatakse tõhusalt planeerimise ja kontrolli teoorias, ajakava teoorias, sotsioloogias, matemaatilises lingvistikas, majanduses, bioloogias, meditsiinis ja geograafias. Graafikuid kasutatakse laialdaselt sellistes valdkondades nagu programmeerimine, lõplike olekumasinate teooria, elektroonika, tõenäosuslike ja kombinatoorsete probleemide lahendamisel, lühima vahemaa jne. Matemaatiline meelelahutus ja mõistatused on samuti osa graafiteooriast. Graafiteooria areneb kiiresti ja leiab uusi rakendusi.

Jaotis 2. Graafikute põhitüübid, mõisted ja struktuur.

Graafiteooria on matemaatikute jõupingutustega loodud matemaatiline distsipliin, mistõttu selle esitlus sisaldab vajalikke rangeid määratlusi.

Graaf on kogum piiratud arvust punktidest, mida nimetatakse graafi tippudeks, ja joontest, mis ühendavad mõnda neist tippudest paarikaupa, mida nimetatakse graafi servadeks või kaaredeks.

Nr Graafi nimi Määratlus Joonis Näide seda tüüpi graafiku kasutamisest

1 Nullgraaf Graafi mittekuuluvad tipud Ülesanne: Arkadi, Boriss. Vladimir, Grigori ja Dmitri vahetasid kohtumisel kätt, mõlemad surusid üksteisega korra kätt. Kui palju servi on, nimetatakse isoleeritud. käepigistused tehti? Olukord, mis vastab hetkele, mil käepigistused pole veel tehtud, on joonisel kujutatud täppmuster.

Graafi, mis koosneb ainult isoleeritud tippudest, nimetatakse nullgraafiks.

Tähistus: O" – tippude ja servadeta graaf

2 Täielikud graafikud Graaf, milles iga tipupaar Pane tähele, et kui tervel graafil on n tippu, siis on servade arv Kõik käepigistused on lõpetatud.

Tähis: U" – n 10-st koosnev graafik.

tipud ja servad, mis ühendavad nende tippude kõiki võimalikke paare. Sellist graafikut saab kujutada n-nurgana, kuhu on joonistatud kõik diagonaalid

3 Mittetäielikud graafikud Graafe, millel kõik käepigistused pole veel lõpetatud, käepigistused A ja B, A ja D, D ja võimalikud servad on raputatud, nimetatakse mittetäielikuks G, C ja D.

4 Tee graafikus. Tsükkel. Tee graafikul ühest tipust teise Punktis A on garaaž lumesaha jaoks. Pildil kujutatud linnaosa tänavatelt kutsuti lund koristama auto juht. Kas tal võib olla äärte jada, mida mööda ta saab oma tööd lõpetada ristmikul, kus asub garaaž, kui autojuht saab oma linnaosas mööda iga tänavat nende tänavate vahel läbida ainult ühe korra?

tipud.

Sel juhul ei tohiks ükski marsruudi serv ilmuda rohkem kui üks kord. Tipp, alates See on võimatu, kuna suletud tee, mis kulgeb mööda graafi kõiki servi ja mida mööda kulgeb marsruut, eksisteerib iga serva jaoks ainult üks kord, kui graafi kõigi tippude astmed on paaris.

tee algus, tipp marsruudi lõpus -

tee lõpp. Jalgratas on tee, millel joonisel on graafiku abil kujutatud asustatud alade vaheliste teede skeem, mille algus ja lõpp langevad kokku. Lihtsates punktides.

tsükkel on tsükkel, mis ei läbi.Näiteks punktist A (graafiku tipp) punkti H saab jõuda erinevatel marsruutidel: ADGH, AEH, AEFCEH, ABCEH.

graafiku ühe tipu kaudu rohkem kui üks Mille poolest erineb marsruut AEH marsruudist AEFCEH?

korda. Sest teisel marsruudil käisime kaks korda punktis E “ristteel”.

See marsruut on pikem kui AEH. AEH marsruudi saab marsruudilt

Kui tsükkel sisaldab kõiki servi AEFCEH, "kriipsutatakse" FCE marsruut viimasest läbi.

graafik ükshaaval, siis selline tsükkel Route AEH on tee graafikus, aga marsruut AEFCEH ei ole tee.

nimetatakse Euleri jooneks.

Ühendatud ja lahtiühendatud graafikud. Määramine 1: kas 12 dm pikkusest traadist on võimalik teha raami servapikkusega kuubist

Kas graafi kaks tippu, mida nimetatakse 1 dm, on ühendatud ilma traati tükkideks purustamata?

kui graafis on tee, mille otsad on nendes tippudes. Kui sellist teed ei eksisteeri, öeldakse, et tipud ei ole ühendatud.

Kuna tee, mis kulgeb mööda graafiku kõiki servi ja piki igat serva ainult üks kord, eksisteerib ainult järgmistel juhtudel:

1) kui iga tipu aste on paaris (tee on suletud)

2) kui paaritu astmega tippe on ainult kaks.

Definitsioon 2:

Graafi nimetatakse ühendatuks, kui mõni selle tippude paar on ühendatud.

Graafi nimetatakse lahtiühendatuks, kui sellel on vähemalt üks lahtiühendatud tippude paar.

6 Puud Puu on mis tahes ühendatud graafik, lisa nr 1. Zholmurzaeva Tomirise sugupuu.

topsid. Täielikult puudest koosnevat lahtiühendatud graafikut nimetatakse metsaks.

7 isomorfset graafikut. Joonisel näidatud graafikud annavad sama teavet. Selliseid graafikuid nimetatakse isomorfseteks (identseteks).

8 Tasapinnalise graafi mõiste Graaf, mida saab esitada ülesandel. Kolm lennukit elavad kolmes erinevas majas ja naabrid on omavahel tülli läinud. Nende majadest mitte kaugel, kus selle ribid ristuvad, on kolm kaevu. Kas on võimalik ainult ülaosast, mida nimetatakse iga maja lamedaks iga kaevu külge. tee nii, et kaks neist ei ristuks?

Lahendus: Pärast kaheksa raja joonistamist saate veenduda, et ei ole võimalik joonistada üheksandat, mis ei ristuks ühegi varem joonistatud teega.

Koostame graafi, mille tipud

A, B, C, 1, 2, 3

ülesande tingimused vastavad majadele ja kaevudele ning proovime tõestada, et üheksandat rada - graafiku serva, mis ei ristu teiste servadega - ei saa joonestada.

Joonisel graafikule tõmmatud servad

A1, A2, A3 ja B1, B2, VZ (vastab radadele majadest A ja B kõikidesse kaevudesse).

Konstrueeritud graafik jagas tasapinna kolmeks piirkonnaks: X, Y, Z. Tipp B, olenevalt selle asukohast tasapinnal, langeb ühte neist kolmest piirkonnast. Kui võtta arvesse kõiki kolme tipu "löömise" juhtu

B ühele alale X, Y või Z, seejärel veenduge, et iga kord, kui üks graafi tippudest on 1, 2 või 3

(üks kaevudest) on tipu B jaoks “ligipääsmatu” (st ei ole võimalik joonistada ühte servadest B1, B2 või B3, mis ei lõikuks graafikul juba olemasolevaid servi).

Vastus probleemküsimusele on: "Ei!"

Suunatud graafikud Graafi serva nimetatakse suunatud servaks, kui ühte selle tippu peetakse selle serva alguseks ja teist selle serva lõpuks.

Graafi, mille kõik servad on suunatud, nimetatakse suunatud graafiks.

Niisiis vaatasin üle graafiteooria põhimõisted, ilma milleta oleks võimatu teoreeme tõestada ja järelikult ka probleeme lahendada.

Järeldus tehtud töö kohta:

Õppisin kogu infomaterjali tabeliks struktureerima;

Kokkulepe teoreetiline materjal aidata visuaalselt mõista graafikutüüpe ja nende rakendamist;

Töötasin näidetega graafiteooria kasutamisest oma sugupuu koostamisel.

Lisa nr 1.

GENEOLOOGILINE PUU

Ehitage Zholmurzaeva Tomirise sugupuu.

Lahenduse meetod.

Graafiline viis probleemi lahendamiseks.

Graafiline viis probleemi lahendamiseks on "loogiliste tingimuste puu" joonistamine. "Puu" väljendab lihtsa joonise kujul sugulaste vahelisi loogilisi suhteid. Iga põlvkond puul vastab ühele oksale.

Võtsin eeskujuks oma sugupuu.

Jaotis 3. Graafiteooria rakendamine.

Me kohtame graafikuid sagedamini kui esmapilgul võimalik. Graafideks on näiteks mis tahes teekaart, elektriskeem, hulknurkade joonistamine jne. Pikka aega arvati, et graafiteooriat kasutatakse peamiselt loogikaülesannete lahendamisel. Loogikaülesannete lahendamisel on sageli raske meeles pidada ülesandes antud arvukaid tingimusi ja luua nende vahel seoseid, selliseid ülesandeid aitavad lahendada graafikud, mis võimaldavad visuaalselt kujutada ülesande andmete vahelisi seoseid. Graafiteooriat ennast peeti geomeetria osaks. Kuid kahekümnendal sajandil leiti graafiteooria laialdasi rakendusi majanduses, bioloogias, keemias, elektroonikas, võrgu planeerimine, kombinatoorika ja muud teaduse ja tehnoloogia valdkonnad. Selle tulemusena hakkas see kiiresti arenema ja muutus iseseisvaks hargnenud teooriaks.Paljude matemaatikaülesannete lahendamine on lihtsustatud, kui on võimalik kasutada graafikuid. Andmete esitamine graafikuna muudab selle selgemaks. Paljud tõendid on ka lihtsustatud ja muutuvad veenvamaks, kui kasutada graafikuid.

3. 1. Graafikute rakendamine geomeetrilistes ülesannetes ja teoreemides.

Graafikute abil saate hõlpsasti luua loogiliste tagajärgede ahelaid, mis viivad väite tõestamiseni. Esitage lühidalt ja täpselt teoreemi tõestus ja ülesande lahendus.

Tõesta, et võrdhaarse kolmnurga korral on aluse tippudest tõmmatud poolitajad võrdsed.

Lahenduste meetodid.

Probleemi tõendamine arutluskäigu abil.

Olgu ABC võrdhaarne kolmnurk

B1 A1 alus AB ja poolitajad AA1 ja BB1.

Vaatleme ∆АВВ1 ja ∆ВАА1. Neil on ∟В1АВ=

∟A1BA kui nurgad võrdhaarse kolmnurga ∆ABC põhjas. ∟АВВ1= ∟А1АВ

A B kuna AA1 ja BB1 on võrdhaarse kolmnurga aluse nurkade poolitajad. AB on ühine pool. Tähendab

∆АВВ1 = ∆ВАВ1 piki külge ja kahte külgnevat nurka. Kolmnurkade võrdsusest järeldub, et nende küljed AA1 ja BB1 on võrdsed.

Probleemi tõendamine graafiku abil.

Tõesta: AA=BB

Arutlemiseks kasutame graafikut. Graafi tipud on teoreemi või ülesande tingimused ja tõestuse etapid.

Graafi servad on loogilised tagajärjed. Graafiku diagrammi lõpp on tõestatav väide.

Värvi kasutatakse komponentide esiletõstmiseks. Teoreem ja ülesande tingimused on sinised. Tõestatav väide on punane. Tõestamise etapid - must.

Kirjeldatud teoreemide tõestamise ja ülesannete lahendamise vorm on õpilastele kasulik ja mugav, kuna võimaldab välja tuua teoreemide tõestamise ja ülesande lahendamise põhietapid.

3. 2. Tarkvara ja metoodiline kompleks.

a) Õpetaja käsiraamat.

Kavandatav käsiraamat on koostatud vastavalt A. V. Pogorelovi 7.–9. klasside geomeetria õpikule. Selle põhieesmärk on varustada geomeetria õppimise protsessi vajalike visuaalsete abivahenditega, abistada õpetajat geomeetria õpetamisel: hõlbustada teoreemide tõestamise protsessi, teoreetilise materjali valdamist ülesannete lahendamise protsessis. Graafikdiagrammid on oma olemuselt mitmetahulised ning olenevalt klasside eesmärkidest ja vormidest kasutatavad erineval viisil: näitlikuna, eesmärgiga suurendada selgust uue teoreetilise materjali selgitamisel, uue materjali üldistamisel ja süstematiseerimisel (teoreemidega graafiku diagrammid); kaartidena, mida kasutatakse individuaal- ja frontaaluuringute läbiviimisel (graafiku diagrammid ülesannetega). Selle juhendiga on kaasas õpilase töövihik. Korraldamiseks saab kasutada töövihikut iseseisev tööõpilased koolitundide ajal ja pärast seda.

b) Töövihik õpilastele.

Juhend on tehtud töövihiku kujul. Käsiraamat sisaldab 28 graafiku diagrammi koos teoreemidega ja 28 graafiku diagrammi ülesannetega. Graafikuskeemid sisaldavad põhilist programmimaterjali, mis on esitatud vajaliku selgusega ja kujutab endast lahenduse raamistikku. Õpilased täidavad tühjad lahtrid järjestikku teabega, mis moodustab probleemi lahenduse.

Värvi kasutatakse komponentide esiletõstmiseks. Teoreemi ja ülesande tingimused on sinised, tõestatav väide on punane, tõestuse etapid on mustad.

Käsiraamat on kasulik 7.-9. klassi õpilastele.

c) Elektrooniline käsiraamat.

Töö tulemused ja nende arutelu. Projekt on kaheaastase koolimatemaatikakursuse graafikute kasutamise uuringu tulemus.

Programmiline loomine – metoodiline kompleks ja selle rakendamine viidi läbi:

Tundide läbiviimine Aristotelese klubis teemal “Loogikaülesannete lahendamine graafikute abil”.

Graafikute rakendused geomeetriliste teoreemide ja ülesannete tõestamisel

Geomeetria tundides 8. ja 9. klassis.

Esitlused projektiga koolis teaduslik ja praktiline konverentsid.

KOKKUVÕTE.

Võttes kokku kooli geomeetriakursuse graafikute kasutamise uuringu tulemused, jõudsin järgmisele järeldusele:

1. Teoreemide ja ülesannete lahendamise graafilise tõestamise eeliseks traditsioonilise ees on teoreemide ja ülesannete tõestamise dünaamika illustreerimine.

2. Sissejuhatus geomeetriliste teoreemide ja graafilise skeemi meetodi ülesannete tõestamise protsessi aitab tugevdada õpilaste oskusi tõestuse koostamisel.

3. Töötatud välja tarkvara ja metoodiline kompleks geomeetria õppimiseks 7.-9.klassis: a) õpetaja käsiraamat; b) töövihik õpilastele; c) elektrooniline käsiraamat on kasulik 7.-9. klassi õpilastele.

Õppeväljaanne

Yujukin Nikolai Aleksejevitš

LR nr. Allkirjastatud pitsatile

Uh. Ed. l.. , .

Voroneži Riiklik Tehnikaülikool

394026 Voronež, Moskovski p. 14

MAGNETKETA KATALOOG

Kõrgema matemaatika ning füüsikalise ja matemaatilise modelleerimise osakond

ON. Yuyukin

DISKREETNE MATEMAATIKA 1. osa. Graafiteooria elemendid

Õpetus

ON. Yuyukin

DISKREETNE MATEMAATIKA 1. osa. Graafiteooria elemendid

Õpetus

Voronež 2004

SISSEJUHATUS

Seda käsiraamatut saavad kursusel “Diskreetne matemaatika” kasutada VSTU üliõpilased, kes õpivad järgmistel erialadel:

090102 – Arvutiturve;

090105 – Automatiseeritud süsteemide infoturbe igakülgne pakkumine;

090106 - Telekommunikatsioonisüsteemide infoturve.

Distsipliin “Diskreetne matemaatika” tagab riigile, üldharidusstandardile vastavate teadmiste ja oskuste omandamise ning samas aitab kaasa omandamisele. põhiharidus, maailmavaate kujunemine ja loogilise mõtlemise arendamine.

Graafiteooria on tõhus vahend diskreetsete objektidega seotud kaasaegsete inseneriprobleemide vormistamiseks. Seda kasutatakse integraallülituste ja juhtlülituste projekteerimisel, automaatsete masinate ja loogikalülituste uurimisel, süsteemi analüüs, automatiseeritud tootmisjuhtimine, arvuti- ja infovõrkude arenduses, vooluringide projekteerimises ja projekteerimis-topoloogilises projekteerimises jne.

IN õpik toob välja graafiteooria põhialused, põhimeetodid ja algoritmid. Siin esitame n-graafikud ja digraafid; isomorfismid; puud; Euleri graafikud; tasapinnalised graafikud; katted ja iseseisvad komplektid; tugev ühenduvus

V digraafid; Markovi ahelgraafiku analüüs; algoritmid lühimate teede leidmiseks graafikutest; Hamiltoni tsükli otsimise probleem

V graafik; reisiva müüja probleem; graafikute ja kaardistuste loendamine; ekstreemsed ülesanded; optimeerimisprobleemid; universaalsed ülesanded; haru ja seotud meetod; ning arendada ka praktilisi oskusi ülaltoodud mõistete kasutamisel.

Kursuse eesmärk on arendada õpilaste teoreetilisi teadmisi, praktilisi oskusi ja vilumusi loodusteaduste ja -tehnoloogia protsesside ja nähtuste modelleerimise valdkonnas.

ke, oskusega kasutada matemaatilisi sümboleid, et väljendada kõrgel professionaalsel tasemel infoturbe valdkonna ametlikuks tegevuseks vajalikke objektide kvantitatiivseid ja kvalitatiivseid seoseid.

Selle eesmärgi saavutamiseks aitavad järgmised ülesanded:

uurida võimalikult laia valikut graafiteooria kontseptsioone;

omandada oskused hariduslike ja praktiliste probleemide lahendamisel;

valdama optimeerimise meetodeid;

kujundada oskusi infoprobleemide püstitamisel ja lahendamisel, teabe modelleerimisel ja analüüsimisel graafikute abil.

Distsipliin “Diskreetne matemaatika” on üks rakenduslikest matemaatikadistsipliinidest. See põhineb teadmistel, mille õpilased on omandanud erialade "Algebra" ja "Matemaatiline loogika ja algoritmide teooria" õppimisel. Õppetöös kasutatakse distsipliini “Diskreetne matemaatika” õppes omandatud teadmisi ja oskusi. üldprofessionaal ja eridistsipliinid.

1. GRAAFISTEOORIA PÕHIMÕISTED.

1.1. Graafiteooria probleemid.

Graafiteooria on matemaatika haru, mis uurib erinevate objektide vahelisi seoste süsteeme, nagu seda tehakse seose mõistega. Graafiku iseseisev definitsioon aga lihtsustab teooria esitamist ning muudab selle arusaadavamaks ja visuaalsemaks.

Graafiteooria esimesed probleemid olid seotud meelelahutusülesannete ja mõistatuste lahendamisega.

Esimene ülesanne. Königsbergi sildade probleemi püstitas ja lahendas Euler 1786. aastal. Linn asus Pregolya jõe kaldal ja kahel saarel. Saared olid omavahel ja kallaste vahel ühendatud seitsme sillaga, nagu joonisel näha.

Tekkis küsimus: kas on võimalik majast lahkuda ja tagasi pöörduda, ületades iga silda täpselt ühe korra?

Teine ülesanne. Kolme maja ja kolme kaevu probleem. Seal on kolm maja ja kolm kaevu.

Igast majast iga kaevu juurde tuleb tõmmata tee, et teed ei ristuks. Ülesanne oli

aastal lahendas Pontrjagin ja temast sõltumatult Kuratovski

Kolmas ülesanne. Umbes neli värvi. Värvige kõik tasapinnal olevad kaardid nelja värviga nii, et kaks külgnevat ala ei oleks värvitud sama värviga.

Paljusid graafiteooria tulemusi kasutatakse teaduse ja tehnoloogia praktiliste probleemide lahendamiseks. Nii kasutas Kirchhoff 19. sajandi keskel keeruliste elektriahelate arvutamiseks graafiteooriat. Graafiteooria kujunes matemaatilise distsipliinina välja aga alles 20. sajandi 30. aastatel. Sel juhul käsitletakse graafikuid kui abstraktseid matemaatilisi objekte. Neid kasutatakse ahelate ja süsteemide analüüsil ja sünteesil, võrkude planeerimisel ja juhtimisel, operatsioonide uurimisel, programmeerimisel, organismi eluea modelleerimisel ja muudes valdkondades.

1.2. Põhimääratlused.

Graaf G= (V,E) on kogum kahest hulgast – mittetühjast tippude hulgast V ning järjestamata ja järjestatud tippude paaridest E. Järgnevalt käsitleme lõplikke graafe, s.o. graafikud lõpliku tippude hulga ja paaride lõpliku perekonnaga. Järjestamata tippude paari nimetatakse servaks ja järjestatud paari nimetatakse kaareks.

Tavaliselt kujutatakse graafikut diagrammina: tipud on punktid (või ringid), servad on suvalise konfiguratsiooniga jooned. Nool näitab lisaks selle suunda kaarel. Pange tähele, et graafiku kujutamisel kandja

ribide geomeetrilised omadused (pikkus, kumerus), samuti vastastikune kokkulepe tipud tasapinnal.

Neid tippe, mis ei kuulu ühegi serva (kaare külge), nimetatakse isoleeritud. Serva või kaarega ühendatud tippe nimetatakse külgnevateks. Serva (kaar) ja mis tahes selle kahest tipust nimetatakse intsidendiks.

Nad ütlevad, et serv (u,v) ühendab tippe u ja v ning kaar (u,v) algab tipust u ja lõpeb tipuga v, kusjuures u nimetatakse selle kaare alguseks ja v lõpuks.

Tippude paari saab ühendada kahe või enama servaga (samasuunalised kaared). Selliseid servi (kaaresid) nimetatakse mitmekordseks. Kaar (või serv) võib alata või lõppeda samas tipus. Sellist kaare (serva) nimetatakse silmuseks. Silmust sisaldavat graafikut nimetatakse pseudograafiks. Graafi, millel on mitu serva (kaared), nimetatakse multigraafiks.

Graafi ilma silmusteta või mitme servata nimetatakse lihtsaks. Lihtsat graafi nimetatakse täielikuks, kui mis tahes selle tippude paari jaoks on neid ühendav serv (kaar). Täielikku n tipuga graafikut tähistatakse K n-ga. Näiteks on need graafikud

Graafi, mis koosneb ühest isoleeritud tipust (K 1), nimetatakse triviaalseks.

Graafi G komplement on graaf G, millel on samad tipud kui graafil G ja mis sisaldab neid servi, mis tuleb graafile G lisada, et saada täielikku graafi.

Igale mittedigraafile kanooniliselt ühtib sama tippude komplektiga suunatud graaf, milles iga serv on asendatud kahe kaarega, mis langevad samadele tippudele ja millel on vastassuunad.

1.3. Graafi tippude astmed.

Lihtsa graafi G tipu v aste (valents) (tähistus d (v) või kraad (v)) on antud tipuga v langevate servade või kaarede arv. Pseudograafi tippude valentsi arvutamisel tuleks iga silmus lugeda kaks korda.

Kui n-graafi kõigi tippude astmed on võrdsed k-ga, siis kutsutakse graafi tavaline (ühtlane) aste k. Kui tipu aste on 0, siis on see isoleeritud. Kui tipu aste on 1, siis nimetatakse tippu lõpptipuks (rippuv, tupik).

Digraafi puhul nimetatakse tipust v väljuvate kaarede arvu

varieerub tulemuse poolkraad				(v) ja sissetulevad – poolsamm-

uus kõne d			(v), Sel juhul seos d (v)=

	(v)+	(v).

Euleri teoreem: Graafi tippude astmete summa on

kahekordne ribide arv, st.

d(vi)



			(v)

kus n on tippude arv; m – arv

ribid (kaared). Seda väidet tõestab tõsiasi, et tippude astmete summa arvutamisel võetakse iga serv arvesse kaks korda - ühe serva ja teise otsa jaoks.

1.4. Graafiline isomorfism.

Graafi nimetatakse märgistatuks (või ümber nummerdatuks), kui selle tipud erinevad üksteisest millegi poolest.

sildid (numbrid). Arvestus loetakse ranges mõttes täiesti antud, kui selle tippude ja servade nummerdamine on fikseeritud. Graafe G 1 ja G 2 nimetatakse sel juhul võrdseteks (tähistus G 1 = G 2), kui nende tippude ja servade hulgad langevad kokku. Kaks graafikut või pseudograafi G 1 = (V 1 ,E 1 ) ja G 2 = (V 2 ,E 2 ) nimetatakse

	isomorfne (tähistus G	kui need on olemas

	üks-ühele kaardistamine: 1)	: V 1 V 2
: E 1 E 2 nii, et graafiku mis tahes kahe tipu korral on u, v
	seos ((u, v)) ((u), (v)) kehtib.

	Kaks lihtsat graafikut (ilma silmuste ja mitme servata) G 1		ja G2

osutuvad isomorfseteks, kui need on identsed

väärtuste kaardistamine

: V 1 V 2

Mis siis?

(u , v ) ((u ), (v )) .

Seega on graafid, mis erinevad ainult tippude ja servade nummerdamise poolest, isomorfsed. Graafiline isomorfism on ekvivalentsuhe, kuna sellel on järgmised omadused:

Peegeldusvõime -

G1,

ja bijektsioon

on identne funktsioon.

Sümmeetria.

bijektsiooniga

Transitiivsus.

G 1 G 2

bijektsioon

1,a

bijektsiooniga

siis G G

bijektsiooniga

2 (1 ) .

Graafiteooria leiab rakendust näiteks geograafilistes infosüsteemides (GIS). Tippudena käsitletakse olemasolevaid või äsja projekteeritud maju, rajatisi, plokke jms ning servadena neid ühendavaid teid, tehnovõrke, elektriliine jms. Erinevate sellisel graafikul tehtavate arvutuste kasutamine võimaldab näiteks leida lühima ümbersõidutee või lähima toidupoe või planeerida optimaalse marsruudi.

Graafiteooria sisaldab suurt hulka lahendamata probleeme ja seni tõestamata hüpoteese.

Graafiteooria peamised rakendusvaldkonnad:

Keemias (struktuure, keeruliste reaktsioonide radade kirjeldamiseks võib faasireeglit tõlgendada ka graafiteooria probleemina); Arvutuskeemia on suhteliselt noor keemiavaldkond, mis põhineb graafiteooria rakendamisel. Graafiteooria on kemoinformaatika matemaatiline alus. Graafiteooria võimaldab täpselt määrata teoreetiliselt võimalike isomeeride arvu süsivesinikes ja teistes orgaanilistes ühendites;

Arvutiteaduses ja programmeerimises (algoritmi graafik);

Side- ja transpordisüsteemides. Eelkõige andmete Internetis marsruutimiseks;

Majanduses;

Logistikas;

Skeemikujunduses (trükkplaadil või mikroskeemil olevate elementide omavaheliste ühenduste topoloogia on graafik või hüpergraaf).

On olemas spetsiaalne graafik, puu.Puu on ühendatud atsükliline graaf. Ühendus tähendab teede olemasolu mis tahes tipupaari vahel, atsüklilisus tähendab tsüklite puudumist ja asjaolu, et tipupaaride vahel on ainult üks tee. Peal Joonis 1.3 esitati kahendpuu.

Binaarne puu- puu andmestruktuur, milles igal sõlmel ei ole rohkem kui kaks järeltulijad(lapsed). Tavaliselt nimetatakse esimest vanemsõlm, ja lapsed kutsutakse vasakule Ja õiged pärijad.

Graafikute maatriksesitus. Juhtumimaatriks.

Graafi omaduste analüüsi algoritmiliste lähenemisviiside väljatöötamine eeldab graafikute kirjeldamiseks teatud meetodeid, mis sobivad paremini praktilisteks arvutusteks, sealhulgas arvuti kasutamiseks. Vaatame kolme levinumat graafikute esitamise viisi.

Oletame, et kõik suunamata graafi tipud ja kõik servad või suunatud graafi kõik tipud ja kaared (kaasa arvatud tsüklid) on nummerdatud alates ühest. Graafi (suunamata või suunatud) saab esitada maatriksina, mille tüüp on , kus on tippude arv ja servade (või kaare) arv. Suunamata graafiku jaoks on selle maatriksi elemendid määratletud järgmiselt:

Suunatud graafiku jaoks määratakse maatriksi elemendid järgmiselt:

Sel viisil määratletud tüüpi maatriksit nimetatakse juhtumimaatriks.

Juhtumimaatriksi saamise näide. Allpool näidatud graafiku jaoks ( Riis. 2.1 aJoonis 2.1 b).

Joon. 2.1 a Joon. 2.1 b

Külgnevusmaatriks.

Vaatamata sellele, et graafiku esitamine esinemismaatriksi kujul mängib teoreetilises uurimistöös väga olulist rolli, on praktikas see meetod väga ebaefektiivne. Esiteks on maatriksis igas veerus ainult kaks nullist erinevat elementi, mis muudab selle graafi kujutamise meetodi ebaökonoomseks, kui tippe on palju. Lisaks on praktiliste probleemide lahendamine juhtumimaatriksi abil väga töömahukas.

Hinnakem näiteks sellise lihtsa ülesande lahendamise ajakulusid suunatud graafis, kasutades esinemismaatriksit: antud tipu jaoks leidke selle “keskkond” - tipu järglaste ja eelkäijate hulk, s.t. kõigi tippude hulk, millest on otse juurdepääsetav, ja kõigi tippude hulk, kust see on otse kättesaadav.

Selle ülesande lahendamiseks suunatud graafiku esinemismaatriksil peate liikuma mööda rida numbriga, kuni ilmub nullist erinev element (+1 või –1). Kui tuvastatakse +1, tuleb vastavast veerust leida rida, kuhu on kirjutatud arv –1. Rea number, millel see arv esineb, annab selle tipu numbri, mis on sellest tipust otse kättesaadav. Kui tuvastatakse -1, peate leidma veerust rea, mis sisaldab 1, ja hankima selle tipu numbri, kust sellele tipule on otse juurdepääs. Kogu "keskkonna" saamiseks peate tegema määratud otsingu kõigi nullist erinevate elementide jaoks k-s rida. Kõige aeganõudvam protseduur on nullist erineva elemendi leidmine veerust. Selliste otsinguprotseduuride arv on võrdne tipu astmega. Sel juhul ütleme, et tipu keskkonna analüüsimise algoritmi keerukus on (järjekord).

Näha on, et kõikide tippude “keskkonna” otsimine võtab aega järjestuses, mis korrutatakse suunatud graafi tippude arvu kõigi tippude astmete summaga, mis, nagu näha, on võrdeline suunatud graafiku kaarte arvuga. Seega on “keskkonna” otsingualgoritmi keerukus , s.t. otsimine võtab aega tippude arvu ja kaarede arvu korrutise järjekorras.

Tõhusam graafikut esindav maatriksstruktuur on tipu naabrusmaatriks, või Boole'i maatriks graafik. See on ruutmaatriks järku B n, mille elemendid on määratletud järgmiselt:

suunamata graafiku jaoks:

suunatud graafiku jaoks:

Allpool näidatud graafiku jaoks ( Riis. 2.2 a) esinemismaatriks on maatriks, mis on esitatud ( Joonis 2.2 b).

Töö tekst postitatakse ilma piltide ja valemiteta.
Täisversioon töö on PDF-vormingus saadaval vahekaardil "Tööfailid".

SISSEJUHATUS

"Matemaatikas ei pea meeles pidama valemeid, vaid mõtlemisprotsessi..."

E. I. Ignatjev

Graafiteooria on praegu intensiivselt arenev matemaatika haru. Seda seletatakse asjaoluga, et paljusid objekte ja olukordi kirjeldatakse graafimudelite kujul, mis on ühiskonnaelu normaalseks toimimiseks väga oluline. Just see tegur määrab nende üksikasjalikuma uuringu asjakohasuse. Seetõttu on selle töö teema üsna aktuaalne.

Sihtmärk uurimistöö: selgitada välja graafiteooria rakendamise tunnused erinevates teadmisvaldkondades ja loogikaülesannete lahendamisel.

Eesmärk tuvastas järgmise ülesanded:

tutvuda graafiteooria ajalooga;

uurida graafiteooria põhimõisteid ja graafide põhiomadusi;

näidata graafiteooria praktilist rakendamist erinevates teadmisvaldkondades;

Mõelge probleemide lahendamise viisidele graafikute abil ja looge oma probleemid.

Objekt uurimistöö: inimtegevuse valdkond graafimeetodi rakendamiseks.

Üksus Uurimistöö: matemaatika sektsioon “Graafiteooria”.

Hüpotees. Oletame, et graafiteooria õppimine võib aidata õpilastel lahendada matemaatika loogikaülesandeid, mis kujundavad nende tulevikuhuve.

meetodid uurimistöö:

Uuringu käigus kasutasime järgmisi meetodeid:

1) Töötamine erinevate teabeallikatega.

2) Materjali kirjeldamine, kogumine, süstematiseerimine.

3) Vaatlus, analüüs ja võrdlemine.

4) Ülesannete koostamine.

Teoreetiline ja praktiline tähendus Selle töö määrab asjaolu, et tulemusi saab kasutada arvutiteaduses, matemaatikas, geomeetrias, joonistamises ja klassitunnid, aga ka laiale hulgale sellest teemast huvitatud lugejatele. Uurimistöö on selge praktilise suunitlusega, kuna töös toob autor hulgaliselt näiteid graafide kasutamisest paljudes teadmisvaldkondades ning on koostanud oma ülesanded. Seda materjali saab kasutada matemaatika valikainete tundides.

I PEATÜKK. TEOREETILINE ÜLEVAADE UURIMISTEEMALISTE MATERJALILE

Matemaatikas saab “graafikut” kujutada pildina, mis kujutab rida joontega ühendatud punkte. "Krahv" tuleb ladinakeelsest sõnast "graphio" - ma kirjutan, nagu tuntud aadlitiitel.

Matemaatikas on graafiku definitsioon antud järgmiselt:

Mõistet "graafik" matemaatikas määratletakse järgmiselt:

Graafik - see on piiratud punktide kogum - tipud, mida saab joontega ühendada - ribid .

Graafikute näideteks on hulknurkade joonised, elektriahelad, lennufirmade, metroode, teede jms skemaatilised kujutised. Sugupuu on ka graaf, mille tipud on klanni liikmed ja sugulussidemed toimivad graafi servadena.

Riis. 1 Graafiku näited

Nimetatakse ühte tippu kuuluvate servade arvu graafiku tipu aste . Kui tipu aste on paaritu arv, nimetatakse tippu - kummaline . Kui tipu aste on paarisarv, siis nimetatakse tippu isegi.

Riis. 2 graafiku tipp

Nullgraafik on graaf, mis koosneb ainult eraldatud tippudest, mis pole servadega ühendatud.

Täielik graafik on graaf, milles iga tipupaar on ühendatud servaga. N-nurk, kuhu on joonistatud kõik diagonaalid, võib olla tervikliku graafiku näide.

Kui valida graafikus tee, kus algus- ja lõpp-punkt langevad kokku, siis sellist teed nimetatakse graafiku tsükkel . Kui graafi iga tipp läbida kõige rohkem üks kord, siis tsükkel helistas lihtne .

Kui graafi iga kaks tippu on ühendatud servaga, siis see ühendatud graafik. Graafikut nimetatakse mitteseotud , kui see sisaldab vähemalt ühte paari ühendamata tippe.

Kui graaf on ühendatud, kuid ei sisalda tsükleid, siis nimetatakse sellist graafikut puu .

Krahvi tee on jada, milles iga kaks külgnevat serva, millel on ühine tipp, esinevad ainult üks kord.

Lühima tippude ahela pikkus a ja b nimetatakse vahemaa tippude vahel a ja b.

Tipp A helistas Keskus graafik, kui tippude vaheline kaugus A ja mis tahes muu tipp on väikseim võimalik. Selline vahemaa on olemas raadius graafik.

Nimetatakse maksimaalset võimalikku kaugust graafi mis tahes kahe tipu vahel läbimõõt graafik.

Graafiku värvimine ja pealekandmine.

Kui vaatate tähelepanelikult geograafilist kaarti, näete raudteed või kiirteid, mis on graafikud. Lisaks on kaardil graafik, mis koosneb riikide (rajoonide, piirkondade) vahelistest piiridest.

1852. aastal sai inglise tudeng Francis Guthrie ülesandeks värvida Suurbritannia kaart, tuues iga maakonna eraldi värviga esile. Väikese värvivaliku tõttu kasutas Guthrie neid uuesti. Ta valis värvid nii, et need maakonnad, millel oli ühine piirilõik, värviti tingimata eri värvidega. Tekkis küsimus, milline on minimaalne värvikogus erinevate kaartide värvimiseks. Francis Guthrie soovitas, kuigi ta ei suutnud tõestada, et neljast värvist piisaks. Seda probleemi arutati üliõpilasringkondades tuliselt, kuid hiljem unustati.

"Nelja värvi probleem" äratas üha suuremat huvi, kuid seda ei lahendatud kunagi, isegi väljapaistvate matemaatikute poolt. 1890. aastal Inglise matemaatik Percy Heawood tõestas, et iga kaardi värvimiseks piisab viiest värvist. Alles 1968. aastal suutsid nad tõestada, et 4 värvist piisaks, et värvida kaart, millel on kujutatud vähem kui nelikümmend riiki.

1976. aastal lahendasid selle ülesande arvuti abil kaks Ameerika matemaatikut Kenneth Appel ja Wolfgangt Haken. Selle lahendamiseks jagati kõik kaardid 2000 tüüpi. Loodi arvutiprogramm, mis uuris kõiki tüüpe, et tuvastada kaarte, mille värvimiseks neljast värvist ei piisa. Arvuti ei suutnud uurida ainult kolme tüüpi kaarte, mistõttu matemaatikud uurisid neid omal käel. Selle tulemusena leiti, et kõigi 2000 kaarditüübi värvimiseks piisaks 4 värvist. Nad teatasid nelja värvi probleemi lahendusest. Sellel päeval pandi ülikooli postkontor, kus Appel ja Haken töötasid, kõikidele markidele templi kirjaga: "Neljast värvist piisab."

Võite ette kujutada nelja värvi probleemi veidi erinevalt.

Selleks vaatleme suvalist kaarti, esitades selle graafi kujul: olekute pealinnad on graafi tipud ja graafi servad ühendavad neid tippe (suurtähti), mille olekutel on ühine piir. Sellise graafiku saamiseks sõnastatakse järgmine ülesanne: on vaja graafik värvida nelja värviga nii, et tipud, millel on ühine serv, värvitakse erinevate värvidega.

Euleri ja Hamiltoni graafikud

1859. aastal lasi inglise matemaatik William Hamilton välja pusle – puidust dodekaeedri (dodekaeedri), mille kakskümmend tippu olid tähistatud naastudega. Igal tipul oli ühe maailma suurima linna nimi – Canton, Delhi, Brüssel jne. Ülesandeks oli leida suletud rada, mis kulgeb mööda hulktahuka servi, külastades iga tippu vaid korra. Tee tähistamiseks kasutati nööri, mis haakiti naelte külge.

Hamiltoni tsükkel on graaf, mille teekond on lihtne tsükkel, mis läbib ühe korra kõik graafiku tipud.

Kaliningradi linn (endine Koenigsberg) asub Pregeli jõe ääres. Jõgi uhtus kaks saart, mis olid omavahel ja kallastega ühendatud sildadega. Vanu sildu enam pole. Mälestus neist jääb vaid linna kaardile.

Ühel päeval küsis linnaelanik oma sõbralt, kas on võimalik kõndida üle kõigi sildade, külastada iga silda ainult korra ja naasta kohta, kust jalutuskäik algas. See probleem huvitas paljusid linlasi, kuid keegi ei suutnud seda lahendada. See teema on äratanud huvi paljude riikide teadlastes. Ülesande lahenduse sai matemaatik Leonhard Euler. Lisaks sõnastas ta üldise lähenemisviisi selliste probleemide lahendamiseks. Selleks muutis ta kaardi graafikuks. Selle graafiku tipud olid maa ja servad seda ühendavad sillad.

Königsbergi sillaülesannet lahendades suutis Euler sõnastada graafide omadused.

Graafi on võimalik joonestada, alustades ühest tipust ja lõpetades ühe joonega sama tipuga (ilma kaks korda sama joont mööda joonistamata ja pliiatsit paberilt tõstmata), kui kõik graafiku tipud on paaris.

Kui on kahe paaritu tipuga graaf, siis saab ka selle tipud ühendada ühe tõmbega. Selleks peate alustama ühest ja lõpetama teises, mis tahes paaritu tipuga.

Kui on rohkem kui kahe paaritu tipuga graaf, siis ei saa graafikut ühe tõmbega joonistada.

Kui rakendada need omadused sildade probleemile, siis näeme, et kõik uuritava graafi tipud on paaritud, mis tähendab, et seda graafikut ei saa ühendada ühe tõmbega, s.t. Kõiki sildu on võimatu korra ületada ja teekonda lõpetada kohas, kust see algas.

Kui graafikul on tsükkel (mitte tingimata lihtne), mis sisaldab kõiki graafiku servi ühe korra, siis sellist tsüklit nimetatakse Euleri tsükkel . Euleri ahel (tee, tsükkel, kontuur) on ahel (tee, tsükkel, kontuur), mis sisaldab ühekordselt kõiki graafi servi (kaare).

II PEATÜKK. UURINGU JA SELLE TULEMUSTE KIRJELDUS

2.1. Uuringu etapid

Hüpoteesi kontrollimiseks hõlmas uuring kolme etappi (tabel 1):

Uurimise etapid

Tabel 1.

		Kasutatud meetodid
Probleemi teoreetiline uurimine	Uurida ja analüüsida õppe- ja teaduskirjandust.	- iseseisev mõtlemine;  teabeallikate uurimine; - otsima vajalikku kirjandust.
Juhtumiuuring Probleemid	Vaadake ja analüüsige valdkondi praktilise rakendamise graafikud;	- vaatlus; - analüüs; - võrdlus; - küsitlus.
3. etapp. Tulemuste praktiline kasutamine	Tehke uuritud teabest kokkuvõte;	- süstematiseerimine;  aruanne (suuline, kirjalik, materjalide tutvustamisega)	september 2017

2.2. Graafikute praktilise kasutuse valdkonnad

Graafikud ja teave

Infoteooria kasutab laialdaselt kahendpuude omadusi.

Näiteks kui teil on vaja kodeerida teatud arv sõnumeid teatud erineva pikkusega nullide ja ühtede jadadena. Koodi peetakse antud koodsõnade tõenäosuse jaoks parimaks, kui keskmine sõna pikkus on teiste tõenäosusjaotustega võrreldes väikseim. Selle probleemi lahendamiseks pakkus Huffman välja algoritmi, milles kood on otsinguteooria raames esitatud puugraafikuna. Iga tipu kohta pakutakse välja küsimus, mille vastus võib olla kas “jah” või “ei” – mis vastab kahele tipust väljuvale servale. Sellise puu ehitamine lõpetatakse pärast vajaliku kindlakstegemist. Seda saab kasutada mitme inimese küsitlemisel, kui eelmisele küsimusele ei ole vastust ette teada, esitatakse intervjuuplaan kahendpuuna.

Graafikud ja keemia

A. Cayley käsitles ka küllastunud (või küllastunud) süsivesinike võimalike struktuuride probleemi, mille molekulid on antud valemiga:

CnH 2n+2

Kõik süsivesinikuaatomid on 4-valentsed, kõik vesinikuaatomid on 1-valentsed. Struktuurivalemid Kõige lihtsamad süsivesinikud on näidatud joonisel.

Iga küllastunud süsivesiniku molekuli saab kujutada puuna. Kui kõik vesinikuaatomid on eemaldatud, moodustavad allesjäänud süsivesinikuaatomid puu tippudega, mille aste ei ole kõrgem kui neli. See tähendab, et võimalike soovitud struktuuride (antud aine homoloogide) arv on võrdne puude arvuga, mille tipu astmed ei ole suuremad kui 4. See probleem taandub konkreetset tüüpi puude loendamise probleemiks. D. Polya käsitles seda probleemi ja selle üldistusi.

Graafikud ja bioloogia

Bakterite paljunemisprotsess on üks bioloogilises teoorias leitud hargnemisprotsesside liike. Las iga bakter teatud aja möödudes kas sureb või jaguneb kaheks. Seetõttu saame ühe bakteri jaoks tema järglaste sigimise kahendpuu. Probleemi küsimus on järgmine: mitu juhtumit see sisaldab? k järeltulijad sisse n-s põlvkondüks bakter? Seda seost bioloogias nimetatakse Galton-Watsoni protsessiks, mis tähistab vajalike juhtude arvu.

Graafikud ja füüsika

Iga raadioamatööri jaoks on keeruline ja tüütu ülesanne trükkskeemide (dielektrilisest isoleermaterjalist plaat ja metallribade kujul söövitatud rajad) loomine. Rööbaste ristumiskoht toimub teatud reeglite järgi ainult teatud punktides (trioodide, takistite, dioodide jne asukohad). Selle tulemusena seisab teadlane silmitsi ülesandega joonistada lame graaf, mille tipud on sissepoole

Seega kinnitab kõik ülaltoodu graafikute praktilist väärtust.

Interneti matemaatika

Internet on ülemaailmne omavahel ühendatud arvutivõrkude süsteem teabe salvestamiseks ja edastamiseks.

Internetti saab kujutada graafina, kus graafi tippudeks on Interneti-saidid ja servadeks ühelt saidilt teisele suunduvad lingid (hüperlingid).

Veebigraaf (Internet), millel on miljardeid tippe ja servi, muutub pidevalt – saite lisandub ja kaob spontaanselt, linke kaob ja lisandub. Internetil on aga matemaatiline struktuur, see järgib graafiteooriat ja sellel on mitu "stabiilset" omadust.

Veebigraafik on hõre. See sisaldab vaid paar korda rohkem servi kui tippe.

Vaatamata hõredusele on Internet väga ülerahvastatud. Saate liikuda ühelt saidilt teisele, kasutades linke 5–6 klõpsuga (kuulus kuue käepigistuse teooria).

Nagu me teame, on graafi aste servade arv, millesse tipp kuulub. Veebigraafiku tippude astmed jaotuvad kindla seaduse järgi: suure linkide (servade) arvuga saitide (tippude) osakaal on väike ja väikese linkide arvuga saitide osakaal on suur. Matemaatiliselt saab selle kirjutada nii:

kus on teatud astme tippude osakaal, on tipu aste, on veebigraafi tippude arvust sõltumatu konstant, s.t. ei muutu saitide (tippude) lisamise või eemaldamise käigus.

See jõuseadus on universaalne keerukate võrkude jaoks – bioloogilistest pankadevahelisteni.

Internet tervikuna on vastupidav juhuslikele saitide rünnakutele.

Kuna saitide hävitamine ja loomine toimub iseseisvalt ja sama tõenäosusega, säilitab veebigraafik 1-lähedase tõenäosusega oma terviklikkuse ja seda ei hävitata.

Interneti uurimiseks on vaja koostada juhuslik graafiku mudel. Sellel mudelil peaksid olema tõelise Interneti omadused ja see ei tohiks olla liiga keeruline.

See probleem pole veel täielikult lahendatud! Selle probleemi lahendamine – kvaliteetse Interneti-mudeli loomine – võimaldab meil välja töötada uusi tööriistu teabeotsingu parandamiseks, rämpsposti tuvastamiseks ja teabe levitamiseks.

Bioloogiliste ja majanduslike mudelite ehitamine algas palju varem, kui tekkis Interneti matemaatilise mudeli konstrueerimise ülesanne. Interneti arendamise ja uurimise edusammud on aga võimaldanud vastata paljudele küsimustele kõigi nende mudelite kohta.

Interneti-matemaatikat nõuavad paljud spetsialistid: bioloogid (ennustavad bakteripopulatsioonide kasvu), rahastajad (kriisioht) jne. Selliste süsteemide uurimine on rakendusmatemaatika ja arvutiteaduse üks keskseid harusid.

Murmansk graafiku abil.

Kui inimene saabub uude linna, on reeglina esimene soov külastada peamisi vaatamisväärsusi. Kuid samas on ajahulk sageli piiratud ja töölähetuse puhul väga väike. Seetõttu on vaja oma vaatamisväärsustega tutvumine ette planeerida. Ja graafikud on marsruudi koostamisel suureks abiks!

Vaatleme näiteks tüüpilist juhtumit, kus saabusime Murmanskisse esimest korda lennujaamast. Plaanime külastada järgmisi vaatamisväärsusi:

1. Mere õigeusu Päästja veekogu kirik;

2. Niguliste katedraal;

3. Okeanaarium;

4. Monument kass Semjonile;

5. Tuumajäämurdja Lenin;

6. Murmanski pargituled;

7. Park Valley of Comfort;

8. Koola sild;

9. Murmanski laevakompanii ajaloomuuseum;

10. Viie nurga väljak;

11. Merekaubandussadam

Esmalt otsime need kohad kaardil üles ja saame visuaalse ülevaate vaatamisväärsuste asukohast ja kaugusest. Teedevõrk on üsna arenenud ja autoga reisimine pole keeruline.

Vaatamisväärsused kaardil (vasakul) ja sellest tulenev graafik (paremal) on toodud LISA nr 1 vastaval joonisel. Seega läbib uustulnuk esmalt Koola silla lähedalt (ja saab soovi korral sellest edasi-tagasi ületada); siis lõõgastub ta Murmanski pargi tuledes ja mugavuse orus ning liigub edasi. Selle tulemusel on optimaalne marsruut:

Graafikut kasutades saate visualiseerida ka arvamusküsitluste läbiviimise skeemi. Näited on toodud LISAS nr 2. Olenevalt antud vastustest esitatakse vastajale erinevaid küsimusi. Näiteks kui sotsioloogilises uuringus nr 1 peab vastaja reaalainetest kõige olulisemaks matemaatikat, siis küsitakse, kas ta tunneb end füüsikatundides kindlalt; kui ta arvab teisiti, puudutab teine küsimus nõudlust humanitaarteadused. Sellise graafiku tipud on küsimused ja servad vastusevariandid.

2.3. Graafiteooria rakendamine probleemide lahendamisel

Graafiteooriat kasutatakse probleemide lahendamiseks paljudest ainevaldkondadest: matemaatika, bioloogia, informaatika. Uurisime ülesannete lahendamise põhimõtet graafiteooria abil ja koostasime oma ülesanded uurimistöö teemal.

Ülesanne nr 1.

Viis klassikaaslast surusid keskkooli kokkutulekul kätt. Mitu käepigistust tehti?

Lahendus: Tähistame klassikaaslasi graafiku tippudega. Ühendame iga tipu joontega nelja teise tipuga. Saame 10 rida, need on käepigistused.

Vastus: 10 käepigistust (iga rida tähendab ühte käepigistust).

Ülesanne nr 2.

Minu vanaemal külas tema maja lähedal kasvab 8 puud: pappel, tamm, vaher, õunapuu, lehis, kask, pihlakas ja mänd. Pihlakas on kõrgem kui lehis, õunapuu on kõrgem kui vaher, tamm on madalam kui kask, kuid kõrgem kui mänd, mänd on kõrgem kui pihlakas, kask on madalam kui pappel ja lehis on kõrgem kui õunapuu. Millises järjekorras asetsevad puud kõrgeimast lühemani?

Lahendus:

Puud on graafiku tipud. Tähistame neid ringi esimese tähega. Tõmbame nooled madalalt puult kõrgemale. Öeldakse, et pihlakas on kõrgem kui lehis, siis paneme noole lehisest pihlakale, kask on madalam kui pappel, siis paneme noole paplilt kasele jne. Saame graafiku, kus on näha, et kõige lühem puu on vaher, seejärel õun, lehis, pihlakas, mänd, tamm, kask ja pappel.

Vastus: vaher, õun, lehis, pihlakas, mänd, tamm, kask ja pappel.

Ülesanne nr 3.

Emal on 2 ümbrikut: tavaline ja õhk ning 3 marki: ruudukujuline, ristkülikukujuline ja kolmnurkne. Kui mitmel viisil saab ema valida isale kirja saatmiseks ümbriku ja templi?

Vastus: 6 võimalust

Ülesanne nr 4.

vahel asulad Ehitatakse A, B, C, D, E teed. Vajadus määrata pikkus lühim tee punktide A ja E vahel. Liikuda saab ainult teedel, mille pikkus on näidatud joonisel.

Ülesanne nr 5.

Kolm klassikaaslast - Maxim, Kirill ja Vova otsustasid sportima hakata ja läbisid spordisektsioonide valiku. Teadaolevalt kandideeris korvpalli sektsiooni 1 poiss, kellest kolm soovisid hokit mängida. Maxim osales ainult 1. sektsioonis, Kirill valiti kõigisse kolme sektsiooni ja Vova 2. sektsiooni. Kes poistest millisesse spordialasse valiti?

Lahendus: ülesande lahendamiseks kasutame graafikuid

Korvpall Maxim

Jalgpall Kirill

Hoki Vova

Alates kuni korvpalli läheb ainult üks nool, siis valiti Kirill sektsiooni korvpalli. Siis Kirill ei mängi jäähoki, mis tähendab sisse jäähoki sektsiooni valis Maxim, kes osales ainult selles sektsioonis, siis saab Vova jalgpallur.

Ülesanne nr 6.

Osade õpetajate haigestumise tõttu on kooli õppealajuhatajal vaja koostada vähemalt üheks päevaks katkend tunniplaanist, arvestades järgmisi asjaolusid:

1. Eluohutuse õpetaja on nõus andma ainult viimast tundi;

2. Geograafiaõpetaja võib anda kas teise või kolmanda tunni;

3. Matemaatik on valmis andma kas ainult esimest või ainult teist tundi;

4. Füüsikaõpetaja võib anda kas esimese, teise või kolmanda tunni, kuid ainult ühes klassis.

Millise ajakava saab kooli õppealajuhataja koostada, et see kõiki õpetajaid rahuldaks?

Lahendus: selle probleemi saab lahendada, kui lähete kõik läbi võimalikud variandid, kuid see on lihtsam, kui joonistate graafiku.

1. 1) füüsika 2. 1) matemaatika 3. 1) matemaatika

2) matemaatika 2) füüsika 2) geograafia

3) geograafia 3) geograafia 3) füüsika

4) OBZH 4) OBZH 4) OBZH

Järeldus

Käesolevas uurimistöös uuriti üksikasjalikult graafiteooriat, tõestati hüpotees, et graafide uurimine võib aidata loogikaülesannete lahendamisel, lisaks käsitleti graafiteooriat erinevates teadusvaldkondades ning koostati 7 ülesannet.

Graafikute kasutamine õpilastele probleemidele lahenduste leidmise õpetamisel võimaldab õpilastel parandada oma graafilisi oskusi ja edastada arutlusi piiratud punktide komplekti erikeeles, millest osa on ühendatud joontega. Kõik see aitab kaasa õpilaste mõtlema õpetamise tööle.

Tõhusus haridustegevus mõtlemise arengus sõltub suuresti õpilaste loomingulise aktiivsuse määr matemaatikaülesannete lahendamisel. Seetõttu on vaja matemaatilisi ülesandeid ja harjutusi, mis aktiveeriksid koolilaste vaimset tegevust.

Ülesannete rakendamine ja graafiteooria elementide kasutamine koolis valikainete tundides taotleb täpselt õpilaste vaimse tegevuse aktiveerimise eesmärki. Usume, et meie uurimistöö praktiline materjal võib olla kasulik matemaatika valikainete tundides.

Seega on uurimistöö eesmärk saavutatud, probleemid lahendatud. Tulevikus plaanime jätkata graafikuteooria õppimist ja oma marsruutide väljatöötamist, näiteks luua graafiku abil koolibussile ZATO Aleksandrovski ekskursioonimarsruut muuseumidesse ja meeldejäävad kohad Murmansk.

KASUTATUD VIIDATUTE LOETELU

Berezina L. Yu. "Graafik ja nende rakendus" - M.: "Valgustus", 1979

Gardner M. “Matemaatiline vaba aeg”, M. “Mir”, 1972

Gardner M." Matemaatika mõistatused ja meelelahutus", M. "Mir", 1971

Gorbatšov A. “Olümpiaadiülesannete kogu” – M. MTsNMO, 2005

Zykov A. A. Graafiteooria alused. - M.: "Ülikooliraamat", 2004. - Lk 664

Kasatkin V. N. “Matemaatika ebatavalised probleemid”, Kiiev, “Radianska kool”, 1987

Matemaatiline komponent / Toimetajad ja koostajad N.N. Andrejev, S.P. Konovalov, N.M. Panjuškin. - M.: Sihtasutus "Matemaatilised etüüdid" 2015 - 151 lk.

Melnikov O. I. “Meelelahutuslikud probleemid graafiteoorias”, Mn. "TetraSystems", 2001

Melnikov O.I. Ei tea krahvide maal: käsiraamat õpilastele. Ed. 3., stereotüüpne. M.: KomKniga, 2007. - 160 lk.

Olehnik S. N., Nesterenko Yu. V., Potapov M. K. "Vanad meelelahutuslikud probleemid", M. "Teadus", 1988

Ore O. “Graafik ja nende rakendused”, M. “Mir”, 1965

Harari F. Graafiteooria / Tõlge inglise keelest. ja eessõna V. P. Kozyreva. Ed. G. P. Gavrilova. Ed. 2. - M.: Juhtkiri URSS, 2003. - 296 lk.

LISA nr 1

Peamiste vaatamisväärsuste külastamiseks optimaalse marsruudi koostamine

Murmansk graafiku abil.

Optimaalne marsruut on:

8. Koola sild6. Murmanski pargituled7. Parki mugavuse org2. Niguliste katedraal10. Viie nurga väljak5. Tuumajäämurdja Lenin9. Murmanski laevakompanii ajaloomuuseum11. Merekaubandussadam1. Mere õigeusu Päästja veekogu kirik4. Monument kass Semjonile3. Okeanaarium.

MURMANSKI VAATAMISVÄÄRSUSTE JUHEND

LISA nr 2

Sotsioloogilised küsitlused nr 1, 2

Mis on graafiku meetod?

Sõna "graaf" tähendab matemaatikas pilti, millele on joonistatud mitu punkti, millest osa on ühendatud joontega. Kõigepealt tasub öelda, et krahvidel, millest räägitakse, pole mingit pistmist möödunud aegade aristokraatidega. Meie "graafikud" on juurdunud kreeka sõnast "grapho", mis tähendab "ma kirjutan". Sama juur on sõnades “graafik”, “biograafia”.

Matemaatikas graafiku määratlus on antud järgmiselt: graaf on punktide lõplik kogum, millest osa on ühendatud joontega. Punkte nimetatakse graafi tippudeks ja ühendusjooni servadeks.

Graafiku diagrammi, mis koosneb "eraldatud" tippudest, nimetatakse null graafik. (Joon.2)

Kutsutakse graafikuid, millel pole konstrueeritud kõiki võimalikke servi mittetäielikud graafikud. (Joon.3)

Kutsutakse graafikuid, millel on konstrueeritud kõik võimalikud servad täielikud graafikud. (Joon.4)

Nimetatakse graafi, mille iga tipp on ühendatud iga teise tipu servaga täielik.

Pange tähele, et kui tervel graafil on n tippu, on servade arv võrdne

n(n-1)/2

Tõepoolest, n tipuga tervikliku graafi servade arv on defineeritud kui järjestamata paaride arv, mis koosnevad graafi kõigist n-st servapunktist, st 2 n elemendi kombinatsioonide arvuna:

Mittetäieliku graafiku saab täiendada samade tippudega, lisades puuduvad servad. Näiteks joonisel 3 on kujutatud mittetäielik viie tipuga graafik. Joonisel 4 on servad, mis muudavad graafi terviklikuks graafiks, kujutatud erineva värviga, nende servadega graafi tippude kogumit nimetatakse graafi komplemendiks.

Tippude astmed ja servade arvu arvestamine.

Graafi tipust väljuvate servade arvu nimetatakse tipu aste. Graafi tippu, millel on paaritu aste, nimetatakse kummaline ja isegi kraad - isegi.

Kui graafi kõigi tippude astmed on võrdsed, siis kutsutakse graafi homogeenne. Seega on iga täielik graafik homogeenne.

Joonis 5

Joonisel 5 on kujutatud viie tipuga graafik. Tipu A aste tähistatakse tähega St.A.

Joonisel: St.A = 1, St.B = 2, St.B = 3, St.G = 2, St.D = 0.

Sõnastagem mõned teatud graafikutele omased seaduspärasused.

Muster 1.

Tervikgraafiku tippude astmed on samad ja igaüks neist on 1 võrra väiksem selle graafi tippude arvust.

Tõestus:

See muster on ilmne pärast täielikku graafikut. Iga tipp on servaga ühendatud iga tipuga, välja arvatud ta ise, st graafi igast tipust, millel on n tippu, väljub n-1 serva, mida oli vaja tõestada.

Muster 2.

Graafi tippude astmete summa on paarisarv, mis võrdub kahekordse graafi servade arvuga.

See muster kehtib mitte ainult terve graafiku, vaid ka mis tahes graafiku kohta. Tõestus:

Tõepoolest, iga graafi serv ühendab kahte tippu. See tähendab, et kui liidame graafi kõigi tippude astmete arvu, saame kaks korda rohkem servi 2R (R on graafi servade arv), kuna iga serv loendati kaks korda, mis on vajalik olema tõestatud

Iga graafi paaritute tippude arv on paaris. Tõestus:

Vaatleme suvalist graafi G. Olgu selle graafiku tippude arv, mille aste on 1, võrdne K1-ga; tippude arv, mille aste on 2, on võrdne K2-ga; ...; tippude arv, mille aste on n, on võrdne Kn-ga. Siis saab selle graafi tippude astmete summa kirjutada järgmiselt
K1 + 2K2 + ZK3 + ...+ nKn.
Teisest küljest: kui graafi servade arv on R, siis seadusest 2 on teada, et graafi kõigi tippude astmete summa on võrdne 2R-ga. Siis saame kirjutada võrdsuse
K1 + 2K2 + ZK3 + ... + nKn = 2R. (1)
Valime võrrandi vasakult küljelt summa, mis võrdub graafi paaritute tippude arvuga (K1 + K3 + ...):
K1 + 2K2 + ZK3 + 4K4 + 5K5 + ... + nK = 2R,
(K1 + K3 + K5 +...) + (2K2 + 2X3 +4K4 + 4K5 + ...)=2R
Teine sulg on paarisarv paarisarvude summana. Saadud summa (2R) on paarisarv. Seega (K1 + K3 + K5 +...) on paarisarv.

Vaatleme nüüd graafikute abil lahendatud probleeme:

Ülesanne. klassi meistrivõistlused . Lauatennise klassi meistrivõistlustel on 6 osalejat: Andrey, Boris, Victor, Galina, Dmitri ja Jelena. Meistrivõistlused peetakse ringmängu põhimõttel – iga osaleja mängib iga teisega ühe korra. Tänaseks on mõned mängud juba mängitud: Andrei mängis koos Borisi, Galina ja Jelenaga; Boriss, nagu juba mainitud, on koos Andreiga ja ka Galinaga; Victor - koos Galina, Dmitri ja Jelenaga; Galina koos Andrei ja Borisiga; Dmitri - koos Viktori ja Jelenaga - koos Andrei ja Viktoriga. Mitu mängu on praeguseks mängitud ja kui palju on jäänud?

Arutelu. Kujutame neid ülesandeid diagrammi kujul. Osalejaid kujutame punktidena: Andrey - punkt A, Boris - punkt B jne. Kui kaks osalejat on juba omavahel mänginud, siis ühendame neid esindavad punktid segmentidega. Tulemuseks on joonisel 1 näidatud diagramm.

Punktid A, B, C, D, D, E on graafi tipud ja neid ühendavad lõigud on graafi servad.

Pange tähele, et graafiku servade lõikepunktid ei ole selle tipud.

Seni mängitud geimide arv võrdub servide arvuga, s.o. 7.

Segaduse vältimiseks on graafiku tipud sageli kujutatud mitte punktidena, vaid väikeste ringidena.

Mängimist vajavate mängude arvu leidmiseks koostame teise samade tippudega graafiku, kuid servadega ühendame need osalejad, kes pole veel omavahel mänginud (joonis 2) Sel graafikul selgus, et 8 servi, mis tähendab, et mängida on jäänud 8 mängu : Andrey - Viktori ja Dmitriga; Boriss - koos Viktori, Dmitri ja Jelenaga jne.

Proovime koostada graafiku järgmises ülesandes kirjeldatud olukorra jaoks:

Ülesanne . Kes mängib Lyapkin - Tyapkin? Kooli draamaklubi otsustas lavastada Gogoli peainspektori. Ja siis puhkes tuline vaidlus. Kõik algas Lyapkinist - Tyapkinist.

Lyapkin - minust saab Tyapkin! – teatas Gena otsustavalt.

Ei, minust saab Ljapkin - Tyapkin, vaidles Dima. - Unistasin juba varasest lapsepõlvest selle pildi laval ellu äratamisest.

Noh, okei, ma loobun sellest rollist, kui nad lasevad mul Hlestakovi mängida,” näitas Gena suuremeelsust.

“...Ja minu jaoks – Osipa,” ei andnud Dima talle suuremeelsusega järele.

"Ma tahan olla Maasikas või linnapea," ütles Vova.

Ei, minust saab linnapea,” hüüdsid Alik ja Borja ühest suust. - Või Khlestakov, -

Kas suudetakse rollid ära jagada nii, et esinejad rahule jääksid?

Arutelu. Kujutagem noori näitlejaid ringidega ülemises reas: A - Alik, B - Boris, C - Vova, G - Gena, D - Dima ja rolle, mida nad hakkavad mängima - ringidega teises reas (1 - Ljapkin - Tyapkin, 2 - Khlestakov, 3 - Osip, 4 - Maasikas, 5 - linnapea). Seejärel loosime igalt osalejalt välja lõigud, st. ribid, rollidesse, mida ta tahaks mängida. Saame kümne tipu ja kümne servaga graafi (joonis 3)

Ülesande lahendamiseks tuleb valida viis serva kümnest, millel pole ühiseid tippe. Seda on lihtne teha. Piisab, kui märkida, et üks serv viib tippudesse 3 ja 4, vastavalt tippudest D ja B. See tähendab, et Osipit (tipp 3) peaks mängima Dima (kes veel?), Zemljanichkat aga Vova. Tipp 1 - Lyapkin - Tyapkin - on servadega ühendatud G ja D-ga. Serv 1 - D loobub, kuna Dima on juba hõivatud, jääb 1 - G, Ljapkina - Tyapkina peaks mängima Gena. Jääb üle ühendada tipud A ja B tippudega 2 ja 5, mis vastavad Khlestakovi ja Gorodnitši rollidele. Seda saab teha kahel viisil: kas valida serv A -5 ja B - 2 või serv A -2 ja B -5. Esimesel juhul mängib Alik Gorodnitšit ja Borja Khlestakovi, teisel juhul vastupidi. Nagu graafik näitab, pole probleemil muid lahendusi.

Sama graafik saadakse järgmise ülesande lahendamisel:

Ülesanne. Pahurad naabrid. Viie maja elanikud tülitsesid omavahel ja, et mitte kaevude juures kohtuda, otsustasid need (kaevud) jagada nii, et iga maja omanik läheks mööda "oma" teed "oma" kaevu juurde. Kas nad saavad sellega hakkama?

Tekib küsimus:kas arutatavates probleemides oli graafikuid tõesti vaja? Kas puhtloogiliste vahenditega pole võimalik lahenduseni jõuda? Jah, sa saad. Kuid graafikud muutsid tingimused selgemaks, lihtsustasid lahendust ja paljastasid probleemide sarnasuse, muutes kaks ülesannet üheks ja seda polegi nii vähe. Kujutage nüüd ette ülesandeid, mille graafidel on 100 või enam tippu. Kuid just selliseid probleeme peavad tänapäeva insenerid ja majandusteadlased lahendama. Siin ei saa ilma graafikuteta.

III. Euleri graafikud.

Graafiteooria on suhteliselt noor teadus: Newtoni ajal sellist teadust veel ei eksisteerinud, kuigi kasutusel olid "sugupuud", mis on graafikute liigid. Esimene graafiteooria alane töö kuulub Leonhard Eulerile ja see ilmus 1736. aastal Peterburi Teaduste Akadeemia väljaannetes. See töö algas järgmise probleemiga:

A) Probleem Königsbergi sildadega. Koenigsbergi linn (praegu Kaliningrad) asub Pregeli jõe (Pregoli) kaldal ja kahel saarel.Linna erinevad osad olid ühendatud seitsme sillaga, nagu on näidatud joonisel. Pühapäeviti jalutavad kodanikud linnas ringi. Kas on võimalik valida marsruut nii, et ületad iga silla üks kord ja siis naased alguspunkti?
Enne selle probleemi lahenduse kaalumist tutvustame kontseptsiooni " Euleri graafikud.

Proovime joonisel 4 näidatud graafiku ümber teha ühe tõmbega st pliiatsit paberilehelt tõstmata ja sama jooneosa mitu korda mööda minemata.

Sellel kujundil, mis on välimuselt nii lihtne, on huvitav omadus. Kui hakkame liikuma tipust B, siis see kindlasti õnnestub. Mis juhtub, kui hakkame liikuma tipust A? On lihtne näha, et sel juhul ei saa me joont jälgida: meil on alati läbimata servad, kuhu pole enam võimalik jõuda.

Joonisel fig. Joonisel 5 on kujutatud graafik, mida ilmselt oskate ühe tõmbega joonistada. See on staar. Selgub, et kuigi see näeb välja palju keerulisem kui eelmine graafik, saate seda jälgida, alustades mis tahes tipust.

Joonisel 6 joonistatud graafikuid saab joonistada ka ühe pliiatsitõmbega.

Nüüd proovige joonistada ühe tõmbega joonisel 7 näidatud graafik

Sa ei suutnud seda teha! Miks? Kas te ei leia otsitavat tippu? Ei! Asi pole selles. Seda graafikut ei saa üldjuhul ühe pliiatsitõmbega joonistada.

Viige läbi arutluskäik, mis meid selles veenab. Vaatleme sõlme A. Sellest väljub kolm tippu. Alustame graafiku joonistamist sellest tipust. Mööda neid servi mööda minnes peame väljuma tipust A mööda ühte neist, mingil hetkel peame selle juurde tagasi pöörduma mööda teist ja väljuma mööda kolmandat. Kuid me ei saa enam siseneda! See tähendab, et kui alustame joonistamist tipust A, siis me ei jõua seal lõpuni.

Oletame nüüd, et tipp A ei ole algus. Seejärel peame joonistamise käigus sisestama selle piki ühte serva, väljuma teisest ja naasma uuesti mööda kolmandat serva. Ja kuna me ei saa sellest välja, siis tipp A peab sel juhul olema lõpp.

Seega peab tipp A olema kas joonise algus- või lõppsõlm.

Kuid sama võib öelda ka meie graafi ülejäänud kolme tipu kohta. Kuid joonistamise algustipp saab olla ainult üks tipp ja ka lõpptipp võib olla ainult üks tipp! See tähendab, et seda graafikut on võimatu ühe tõmbega joonistada.

Nimetatakse graafik, mille saab joonistada pliiatsit paberilt tõstmata Eulerian (joonis 6).

Need graafikud on nime saanud teadlase Leonhard Euleri järgi.

Muster 1. (tuleneb meie käsitletud teoreemist).

Paaritu arvu paaritute tippudega graafikut on võimatu joonistada.
Muster 2.

Kui kõik graafiku tipud on paaris, saate seda graafikut joonistada ilma pliiatsit paberilt tõstmata (“ühe tõmbega”), liikudes mööda iga serva ainult üks kord. Liikumine võib alata mis tahes tipust ja lõppeda samas tipus.
Muster 3.

Ainult kahe paaritu tipuga graafikut saab joonistada ilma pliiatsit paberilt tõstmata ning liikumine peab algama ühest neist paaritutest tippudest ja lõppema neist teisest.
Muster 4.

Rohkem kui kahe paaritu tipuga graafikut ei saa ühe joonega joonistada.
Figuuri (graafikut), mida saab joonistada ilma pliiatsit paberilt tõstmata, nimetatakse unikursaalseks.

Graafikut nimetatakse sidus, kui selle mis tahes kahte tippu saab ühendada teega, see tähendab servade jadaga, millest igaüks algab eelmise lõpust.

Graafikut nimetatakse ebaühtlane, kui see tingimus ei ole täidetud.

Joonis 7 Joonis 8

Joonis 7 näitab ilmselgelt lahtiühendatud graafikut. Kui joonisel näiteks joonisel tippude D ja E vahele serv tõmmata, muutub graaf ühendatud. (Joon.8)

Graafiteoorias nimetatakse sellist serva (mille eemaldamise järel muutub graaf ühendatud küljest lahtiühendatuks) nn. sild.

Joonisel 7 kujutatud sildade näideteks võiksid olla servad DE, A3, VZH jne, millest igaüks ühendaks graafi “isoleeritud” osade tippe (joonis 8).

Lahti ühendatud graafik koosneb mitmest "tükist". Neid "tükke" nimetatakse ühenduvuskomponendid graafik. Iga ühendatud komponent on loomulikult ühendatud graafik. Pange tähele, et ühendatud graafikul on üks ühendatud komponent.
TEOREEM.

Graaf on Euleri siis ja ainult siis, kui see on ühendatud ja sellel on maksimaalselt kaks paaritut tippu.

Tõestus:

Joonistades graafiku iga tipu jaoks, välja arvatud algus- ja lõpptipud, sisestame sama palju kordi, kui sellest väljume. Seetõttu peavad kõigi tippude astmed olema paaris, välja arvatud kaks, mis tähendab, et Euleri graafil on maksimaalselt kaks paaritut tippu.

Tuleme nüüd tagasi Königsbergi sildade probleemi juurde.

Probleemi arutelu . Tähistame erinevad linnaosad tähtedega A, B, C, D ja sillad tähtedega a, b, c, d, e, f, g - vastavaid linnaosi ühendavad sillad. Selles probleemis on ainult sildade ületamine: mis tahes silda ületades jõuame alati ühest linnaosast teise ja vastupidi, ühest linnaosast teise üle minnes ületame kindlasti silla. Seetõttu kujutame linnaplaani graafi kujul, mille tipud A, B, C, D (joon. 8) kujutavad üksikuid linnaosi ning servad a, b, c, d, e , f, g on vastavaid linnaosi ühendavad sillad . Sageli on mugavam kujutada servi mitte sirgete, vaid kõverjooneliste segmentidena - "kaaredena".

Kui oleks marsruut, mis vastaks ülesande tingimustele, siis toimuks selle graafiku suletud pidev läbimine, läbides üks kord mööda iga serva. Teisisõnu, see graafik tuleks joonistada ühe tõmbega. Kuid see on võimatu - olenemata sellest, millise tipu me esialgseks valime, peame läbima ülejäänud tipud ja samal ajal iga "sissetuleva" serva (sild, mida mööda sellesse linnaossa sisenesime) vastab "väljaminevale" servale, sillale, mille kaudu me ja seejärel kasutame seda linnaosast lahkumiseks): igasse tippu sisenevate servade arv võrdub sealt väljuvate servade arvuga, st. koguarv igas tipus koonduvad servad peavad olema ühtlased. Meie graafik ei vasta sellele tingimusele ja seetõttu pole vajalikku marsruuti olemas.