Õppeväljaanne

Yujukin Nikolai Aleksejevitš

LR nr. Allkirjastatud pitsatile

Uh. Ed. l.. , .

Voroneži Riiklik Tehnikaülikool

394026 Voronež, Moskva prospekt. 14

MAGNETKETA KATALOOG

osakond kõrgem matemaatika ning füüsiline ja matemaatiline modelleerimine

N.A. Yuyukin

DISKREETNE MATEMAATIKA 1. osa. Graafiteooria elemendid

Õpetus

N.A. 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 - Infoturve telekommunikatsioonisüsteemid.

Distsipliin “Diskreetne matemaatika” tagab riigile, üldharidusstandardile vastavate teadmiste ja oskuste omandamise ning aitab samal ajal kaasa selle 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 õpilastes areneda teoreetilised teadmised, praktilised oskused loodusteaduste ja -tehnoloogia protsesside ja nähtuste modelleerimise valdkonnas

ke, tarbimisvõimalusega matemaatilised sümbolid väljendada kõrgel professionaalsel tasemel infoturbe valdkonna ametitegevuse teostamiseks vajalike 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;

arendada sõnastamis- ja otsustusoskust teabeülesanded, teabe modelleerimine ja analüüs 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." Õ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. Siiski sõltumatu määramine Graafik 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 silla 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üüsimisel ja sünteesil võrgu planeerimine ja juhtimine, operatsioonide uurimine, programmeerimine, keha ja muude valdkondade elutähtsate funktsioonide modelleerimine.

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

riiklikud geomeetrilised omadused ribid (pikkus, kumerus), samuti suhteline positsioon 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, samas kui u nimetatakse alguseks ja v on selle kaare lõpp.

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

GraafiG komplement on graafG, millel on samad tipud kui graafilG ja mis sisaldab neid servi, mis tuleb graafileG saamiseks lisada täielik graafik.

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ähis 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) kraadik. Kui tipu aste on 0, siis on see isoleeritud. Kui tipu aste on võrdne 1-ga, siis nimetatakse tippu lõpuks (rippuv, tupik).

Digraafi puhul nimetatakse tipust v väljuvate kaarede arvu

varieerub tulemuse poolkraad										(v) ja sissetulevad on poolastmelised
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 on 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 1V 2
: E 1 E 2 nii, et graafiku mis tahes kahe tipu u , v korral
	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 1V 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 -

G 1,

ja bijektsioon

on identne funktsioon.

Sümmeetria.

bijektsiooniga

bijektsiooniga

Transitiivsus.

G 1G 2

bijektsioon

1,a

bijektsiooniga

siis G G

bijektsiooniga

2 (1) .

VLADIMIRI RIIKPEDAGOOGIAÜLIKOOL

KOKKUVÕTE

"GRAAFIDE TEOORIA"

Lõpetatud:

Zudina T.V.

Vladimir 2001

1. Sissejuhatus

2. Graafiteooria ajalugu

3. Graafiteooria põhidefinitsioonid

4. Graafiteooria põhiteoreemid

5. Graafiteooria rakendamise ülesanded

6. Graafiteooria rakendamine aastal koolikursus matemaatikud

7. Graafiteooria rakendamine erinevaid valdkondi teadus ja tehnoloogia

8. Viimased saavutused graafikuteooria

§1. GRAAFITEOORIA VÄLJUMISE AJALUGU.

Graafiteooria rajajaks peetakse matemaatik Leonhard Eulerit (1707-1783). Selle teooria ajalugu saab jälgida suure teadlase kirjavahetuse kaudu. Siin on tõlge Ladina tekst, mis on võetud Euleri kirjast Itaalia matemaatikule ja insenerile Marinonile, mis saadeti Peterburist 13. märtsil 1736 [vt. lk 41–42]:

“Kunagi küsiti minult Königsbergi linnas asuva saare kohta, mida ümbritseb seitse silda. Küsimus on selles, kas keegi saab neist pidevalt ümber sõita, läbides vaid korra Teavitasin, et keegi pole siiani suutnud seda teha, kuid keegi pole tõestanud, et see on võimatu. See küsimus, kuigi triviaalne, tundus mulle tähelepanu vääriv, sest ei geomeetriast, algebrast ega kombinatoorsest kunstist ei piisa. lahenda see... Pärast pikka mõtlemist leidsin lihtne reegel, tuginedes täiesti veenvale tõestusele, mille abil on kõigi sedalaadi ülesannete puhul võimalik kohe kindlaks teha, kas sellist möödasõitu saab teha suvalise arvu ja suvalise arvu sildade kaudu või mitte. Koenigsbergi sillad asetsevad nii, et neid saab kujutada järgmisel joonisel[joon.1] , mille peal A tähistab saart ja B , C ja D - mandri osad, mis on üksteisest jõeharudega eraldatud. Seitse silda on tähistatud tähtedega a , b , c , d , e , f , g ".

(JOONIS 1.1)

Seoses meetoditega, mille ta avastas sedalaadi probleemide lahendamiseks, kirjutas Euler [vt. lk 102–104]:

"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 on vaja kaasata, on matemaatikale omased seadused. Niisiis, ma ei tea, kuidas selgub, et matemaatikud lahendavad tõenäolisemalt küsimusi, millel on matemaatikaga vähe pistmist.

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 on selles, kas on võimalik kõigist neist seitsmest sillast ümber sõita, mõlemast ainult korra läbides või mitte. Minu reegel viib selleni, et järgmine otsus see küsimus. Kõigepealt tuleb vaadata, kui palju on veega eraldatud alasid – neid, mille juurest ei pääse muul viisil kui silla kaudu. IN selles näites selliseid piirkondi on neli - A , B , C , D . Järgmisena tuleb eristada, kas nendele üksikutele lõikudele viivate sildade arv on paaris või paaritu. Niisiis viib meie puhul viis silda A lõiguni ja kolm silda ülejäänuteni, st üksikute lõikudeni viivate sildade arv on veider ja sellest üksi piisab probleemi lahendamiseks. Kui see on kindlaks määratud, rakendame järgmist reeglit: kui sildade arv, mis viib iga eraldi ala, oli paaris, siis ümbersõit mille kohta me räägime, oleks võimalik ja samal ajal oleks võimalik seda möödasõitu alustada mis tahes saidilt. Kui kaks neist arvudest oleksid paaritud, kuna ainult üks ei saa olla paaritu, siis ka siis võiks üleminek toimuda, nagu ette nähtud, kuid kindlasti tuleb võtta ainult ümbersõidu algus ühest kahest lõigust, kuhu pole juhet. . paarisarv sillad. Kui lõpuks oleks rohkem kui kaks lõiku, kuhu viib paaritu arv sildu, siis on selline liikumine üldiselt võimatu ... kui siia saaks tuua muid, tõsisemaid probleeme, võib sellest meetodist veelgi rohkem kasu olla 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õeharu lõigul ei ole rohkem kui kaks ala, kuhu viib paaritu arv sildu. 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. Avame näiteks N.Ya toimetatud matemaatika kooliõpiku. Vilenkina kuuendasse klassi. Sellest leiame leheküljel 98 tähelepanelikkuse ja intelligentsuse arendamise pealkirja alt probleemi, mis on otseselt seotud sellega, mille Euler kunagi lahendas.

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

(JOONIS 1.2)

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 reisijad saarele toimetama 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 .

Kokkuvõtteks märgime, et Königsbergi sildade probleem ja sarnased probleemid koos nende uurimismeetodite kogumiga on väga olulised. praktilises mõttes matemaatika haru, mida nimetatakse graafiteooriaks. Esimene töö graafikute kohta kuulus L. Eulerile ja ilmus 1736. aastal. Seejärel töötasid graafikute kallal Koenig (1774-1833), Hamilton (1805-1865) ja kaasaegsed matemaatikud C. Berge, O. Ore, A. Zykov.

§2. GRAAFITEOORIA PÕHITEOREEMID

Graafiteooria, nagu eespool mainitud, on matemaatikute jõupingutustega loodud matemaatiline distsipliin, mistõttu selle esitlus sisaldab vajalikke rangeid määratlusi. Niisiis, jätkame selle teooria põhimõistete organiseeritud sissejuhatusega.

Definitsioon 2.01. Count nimetatakse komplektiks lõplik arv punktid kutsutud tipud graafik, ja paarisjooni, mis ühendavad mõnda neist tippudest, nn ribid või kaared graafik.

Seda määratlust saab sõnastada erinevalt: loendama nimetatakse mittetühjaks punktide komplektiks ( tipud) ja segmendid ( ribid), mille mõlemad otsad kuuluvad antud punktide hulka (vt joonis 2.1).

(JOONIS 2.1)

Järgnevalt tähistame graafi tippe ladina tähtedega A , B ,C ,D. Mõnikord tähistame graafikut tervikuna ühega suur täht.

Definitsioon 2.02. Graafi tippe, mis ei kuulu ühtegi serva, nimetatakse isoleeritud .

Definitsioon 2.03. Graafi, mis koosneb ainult isoleeritud tippudest, nimetatakse null - loendama .

Nimetus: O " – tippudega graaf, millel pole servi (joonis 2.2).

(JOONIS 2.2)

Definitsioon 2.04. Nimetatakse graafi, mille iga tippude paar on ühendatud servaga täielik .

Nimetus: U " – graafik, mis koosneb n tipud ja servad, mis ühendavad nende tippude kõiki võimalikke paare. Sellist graafikut saab esitada kui n– kolmnurk, millesse on tõmmatud kõik diagonaalid (joonis 2.3).

(JOONIS 2.3)

Definitsioon 2.05. Kraad tipud on servade arv, kuhu tipp kuulub.

Nimetus: lk (A) – tipu aste A . Näiteks joonisel 2.1: lk (A)=2, lk (B)=2, lk (C)=2, lk (D)=1, lk (E)=1.

Definitsioon 2.06. Loend, kõigi kraadid k mille tipud on identsed, nimetatakse homogeenne loendama kraadid k .

Joonistel 2.4 ja 2.5 on kujutatud teise ja kolmanda astme homogeensed graafikud.

(JOONIS 2.4 ja 2.5)

Definitsioon 2.07. Täiendus antud graafik on graaf, mis koosneb kõigist servadest ja nende otstest, mis tuleb täieliku graafiku saamiseks lisada algsele graafikule.

Joonis 2.6 näitab algset graafikut G , koosneb neljast tipust ja kolmest segmendist ning joonisel 2.7 - selle graafiku täiend - graaf G " .

(JOONIS 2.6 ja 2.7)

Näeme, et joonisel 2.5 on ribid A.C. Ja BD lõikuvad punktis, mis ei ole graafiku tipp. Kuid on juhtumeid, kus antud graafik tuleb esitada tasapinnal nii, et selle servad lõikuvad ainult tippudes (seda küsimust käsitletakse üksikasjalikumalt lõigus 5).

Definitsioon 2.08. Graafi, mida saab tasapinnal esitada nii, et selle servad lõikuvad ainult tippudes, nimetatakse tasane .

Näiteks joonisel 2.8 on kujutatud tasapinnaline graafik, mis on isomorfne (võrdne) joonisel 2.5 oleva graafikuga. Kuid pange tähele, et mitte iga graaf ei ole tasapinnaline, kuigi see on vastupidine, see tähendab, et iga tasapinnalist graafikut saab esitada tavalisel kujul.

(JOONIS 2.8)

Definitsioon 2.09. Kutsutakse tasapinnalise graafi hulknurka, mis ei sisalda graafi tippe ega servi serv .

Graafikud on lõbus, rahuldust pakkuv ja hirmutav teema. Graafiteooria – "Tudengi õudus". Graafikalgoritmid on nende avastanud inimeste hämmastavad meeled.

Mis on graafik? Sellele küsimusele oma lugejate jaoks vastamiseks kirjeldan teemat veidi teisiti.
Graafik on objektide kogum.
Enamiku probleemide puhul on tegemist sama tüüpi objektidega. (Paljud linnu või palju maju või palju inimesi või palju muid sama tüüpi asju)

Sellise komplektiga seotud probleemide lahendamiseks peate selle komplekti iga objekti millekski määrama. Üldtunnustatud on nimetada just seda asja graafi tippudeks.

Graafikuid ja põhimääratlusi on mugav kirjeldada piltidega, seega peavad selle lehe lugemiseks olema pildid.

Nagu ma varem kirjutasin, on graafik objektide kogum. Need objektid on tavaliselt sama tüüpi. Lihtsaim viis näidet tuua on linnades. Igaüks meist teab, mis on linn ja mis on tee. Igaüks meist teab, et linna teed võivad olla või mitte. Üldiselt võib mis tahes objektide kogumit iseloomustada graafikuna.

Kui rääkida graafikust kui linnadest, siis linnade vahele saab teed ehitada või kuhugi ära lõhkuda, mitte ehitada või linn asub üldiselt saarel, silda pole ja huvi pakuvad vaid kõvakattega teed. . Vaatamata sellele, et sellisesse linna ei vii ühtegi teed, võib selle linna kaasata paljude analüüsitud objektide hulka ning kõik objektid kokku moodustavad objektide kogumi või lihtsamalt öeldes graafiku.

Kindlasti olete lugenud õpikuid ja näinud seda tähistust G(V,E) või midagi sarnast. Niisiis, V on mingi üks objekt kogu objektide hulgast. Meie puhul on objektide kogumiks linnad, seega on V konkreetne linn. Kuna objektid ei pruugi olla linnad ja sõna objekt võib segadust tekitada, võib sellist komplekti kuuluvat objekti nimetada punktiks, punktiks või millekski muuks, kuid enamasti nimetatakse seda graafi tipuks ja tähistatakse tähega. V.
Programmeerimisel on selleks tavaliselt kahemõõtmelise massiivi veerg või rida, kus massiivi nimetatakse kas naabrusmaatriksiks või esinemismaatriksiks.

Kirjanduses, Internetis ja üldiselt kõikjal, kus graafikute kohta midagi kirjutatakse, kohtate selliseid mõisteid nagu kaared ja servad. Sellel joonisel on kujutatud graafiku servad. Need. need on kolm serva E1, E2 ja E3.

Kaar ja serv erinevad selle poolest, et serv on kahesuunaline ühendus. Ta tahtis seda, ta läks oma naabri juurde, ta tahtis seda, ta naasis naabri juurest. Kui see pole väga selge, siis võite ette kujutada maja, lennuvälja, lendavat lennukit ja langevarjurit. Langevarjuhüppaja võib minna oma kodust lennuväljale, kuid lennuväljale jõudes pidage meeles, et ta unustas oma õnneliku langevarju koju, siis pöörduge tagasi koju ja võtke langevari. — Tee, mida mööda saab edasi-tagasi kõndida, nimetatakse servaks.
Kui langevarjur on lennukis ja hüppab lennukist, kuid langevarjur unustas lennukisse oma õnneliku langevarju selga panna, siis kas langevarjur saab üles korjata selle, mille ta unustas? Teekonda, mis kulgeb ainult ühes suunas, nimetatakse kaareks. Tavaliselt ütleme, et serv ühendab kahte tippu ja kaar läheb ühest tipust teise.

Sellel joonisel on graafikul ainult kaared. Kaared graafikul on tähistatud nooltega, sest ligipääsetav suund on nii selge. Kui graafik koosneb ainult sellistest kaaredest, siis nimetatakse sellist graafikut suunatud.

Sageli puutute kokku külgnevuse ja esinemissageduse mõistetega. Joonisel on punasega märgitud kaks serva, mis lähevad ühte punkti. Selliseid servi, nagu ülalkirjeldatud tippe, nimetatakse ka külgnevateks.

Palju pole kirjeldatud, kuid see teave võib kedagi aidata.

VALLA AUTONOOMNE HARIDUSASUTUS KESKOOL nr 2

Valmistatud

Legkokonets Vladislav, 10A klassi õpilane

Praktiline rakendus Graafiteooriad

Juhendaja

L.I. Noskova, matemaatikaõpetaja

Art

2011. aastal

1. Sissejuhatus…………………………………………………………………………………….………….3

2. Graafiteooria tekkimise ajalugu……………………………………………….………..4

3. Graafiteooria põhidefinitsioonid ja teoreemid…………………………………………6

4. Graafikute abil lahendatud ülesanded……………………………..…………………………..8

4.1 Kuulsad probleemid………………………………………………………………8

4.2 Mitu huvitavaid ülesandeid………………………………….……………..9

5. Graafikute rakendamine inimeste elu erinevates valdkondades……………………………………………

6. Probleemide lahendamine…………………………………………………………………………12

7. Järeldus………………….……………………………………………………………….13

8. Viidete loetelu………….………………………………………………………………14

9. Lisa………………………………………………………………………………….…………15

Sissejuhatus

Sündinud mõistatusi lahendades ja meelelahutuslikud mängud Graafikuteooriast on nüüdseks saanud lihtne, ligipääsetav ja võimas tööriist paljude probleemidega seotud küsimuste lahendamiseks. Graafikud on sõna otseses mõttes kõikjal. Graafiku kujul saate tõlgendada näiteks teekaarte ja elektriskeeme, geograafilised kaardid ja molekulid 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. Sellepärast asjakohasust teema on ühelt poolt määratud graafikute ja nendega seotud uurimismeetodite populaarsuse ning teiselt poolt arendamata, täielik süsteem selle rakendamine.

Paljude lahendus eluülesanded nõuab pikki arvutusi ja mõnikord pole need arvutused edukad. See on mis uurimisprobleem. Tekib küsimus: kas nende lahendamiseks on võimalik leida lihtne, ratsionaalne, lühike ja elegantne lahendus. Kas probleemide lahendamine on lihtsam, kui kasutate graafikuid? See määras minu uurimistöö teema: "Graafiteooria praktiline rakendamine"

Eesmärk Uurimistöö eesmärk oli kasutada graafikuid, et õppida kiiresti lahendama praktilisi probleeme.

Uurimistöö hüpotees. Graafikumeetod on väga oluline ning seda kasutatakse laialdaselt erinevates teadus- ja inimtegevuse valdkondades.

Uuringu eesmärgid:

1. Uurige selleteemalist kirjandust ja Interneti-ressursse.

2.Kontrolli graafikumeetodi efektiivsust praktiliste ülesannete lahendamisel.

3. Tee järeldus.

Praktiline tähtsus uurimine on see, et tulemused äratavad kahtlemata paljudes huvi. Kas keegi teist pole proovinud oma sugupuud ehitada? Kuidas seda õigesti teha? Tõenäoliselt tuleb transpordiettevõtte juhil lahendada transpordi tulusama kasutamise probleem kauba vedamisel sihtkohast mitmesse asulasse. Iga koolilaps on kokku puutunud loogiliste vereülekande probleemidega. Selgub, et neid saab lihtsalt graafikute abil lahendada.

Töö kasutab järgmisi meetodeid: vaatlus, otsing, valik, analüüs.

Graafiteooria ajalugu

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 küsiti minult probleemi Königsbergi linnas asuva saare kohta, mida ümbritseb seitse silda ületava jõega.

[Lisa joonis 1] Küsimus on selles, kas keegi suudab neist pidevalt ümber sõita, läbides iga silla vaid korra. Ja siis teatati mulle, et keegi pole veel suutnud seda teha, kuid keegi pole tõestanud, et see on võimatu. See küsimus, kuigi triviaalne, tundus mulle siiski tähelepanu vääriv, sest selle lahendamiseks ei piisa ei geomeetriast, algebrast ega kombinatoorsest kunstist. Pärast pikka mõtlemist leidsin täiesti veenval tõendil põhineva lihtsa reegli, mille abil on kõigi sedalaadi ülesannete puhul võimalik kohe kindlaks teha, kas sellist ümbersõitu saab teha läbi suvalise arvu ja suvalise arvu sildade või mitte. Koenigsbergi sillad asetsevad nii, et neid saab kujutada järgmisel joonisel [Lisa joonis 2], milles A tähistab saart ning B, C ja D - üksteisest jõeharudega eraldatud mandri osi

Seoses meetoditega, mille ta avastas seda tüüpi probleemide lahendamiseks, kirjutas Euler:

"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 on vaja kaasata, on matemaatikale omased seadused. Niisiis, ma ei tea, kuidas selgub, et matemaatikud lahendavad tõenäolisemalt küsimusi, millel on matemaatikaga vähe pistmist.

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 üleminekut ühelt teisele, välja arvatud silla kaudu. Selles näites on neli sellist jaotist - A, B, C, D. Järgmiseks peate eristama, kas arv Nendele üksikutele lõikudele viivate sildade arv on paaris või paaritu. Niisiis, meie puhul viib viis silda sektsiooni A ja kolm silda ülejäänud osani, st üksikute lõikudeni viivate sildade arv on paaritu ja see on üksi. Probleemi lahendamiseks piisab, kui rakendame järgmist reeglit: kui igale üksikule lõigule viivate sildade arv oleks paaris, oleks kõnealune ümbersõit võimalik ja samal ajal oleks võimalik. alustada seda ümbersõitu suvalisest lõigust Kui kaks neist numbritest oleks 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 on selline liikumine üldiselt võimatu ... kui siia saaks tuua muid, tõsisemaid probleeme, võib sellest meetodist veelgi rohkem kasu olla ja ei tohi tähelepanuta jätta."

Graafiteooria põhimõisted ja teoreemid

Graafiteooria on matemaatikute jõupingutustega loodud matemaatiline distsipliin, mistõttu selle esitlus sisaldab vajalikke rangeid määratlusi. Niisiis, jätkame selle teooria põhimõistete organiseeritud sissejuhatusega.

Definitsioon 1. Graaf on kogum piiratud arvust punktidest, mida nimetatakse graafi tippudeks, ja mõnda neist tippudest ühendavatest paarisjoontest, mida nimetatakse graafi servadeks või kaaredeks.

Seda definitsiooni saab sõnastada erinevalt: graafik on mittetühi punktide (tippude) ja lõikude (servade) kogum, mille mõlemad otsad kuuluvad antud punktide hulka.

Järgnevalt tähistame graafi tippe ladina tähtedega A, B, C, D. Mõnikord tähistatakse graafikut tervikuna ühe suure tähega.

2. definitsioon. Graafi tippe, mis ei kuulu ühtegi serva, nimetatakse isoleeritud.

3. definitsioon. Graafi, mis koosneb ainult isoleeritud tippudest, nimetatakse nulliks - loendama .

Tähistus: O "– tippudega graaf, millel pole servi

4. definitsioon. Graafi, milles iga tipupaar on ühendatud servaga, nimetatakse täielikuks.

Nimetus: U" – graaf, mis koosneb n tipust ja servast, mis ühendavad nende tippude kõiki võimalikke paare. Sellist graafikut saab kujutada n-nurgana, kuhu on joonistatud kõik diagonaalid

Definitsioon 5. Tipu aste on servade arv, millesse tipp kuulub.

Definitsioon 6. Graafi, mille kõigi k tipu astmed on ühesugused, nimetatakse homogeenseks astmegraafikuks .

Definitsioon 7. Antud graafi komplement on graaf, mis koosneb kõigist servadest ja nende otstest, mis tuleb lisada esialgsele graafikule tervikliku graafi saamiseks.

Definitsioon 8. Graafi, mida saab tasapinnal esitada nii, et selle servad lõikuvad ainult tippudes, nimetatakse tasapinnaliseks.

Definitsioon 9. Tasapinnalise graafi hulknurka, mis ei sisalda graafi tippe ega servi, nimetatakse selle tahkuks.

Tasapinnalise graafiku ja graafiku näo mõisteid kasutatakse “õige” värvimise ülesannete lahendamisel erinevaid kaarte.

Definitsioon 10. Tee A kuni X on servade jada, mis viib punktist A punkti X, nii et igal kahel külgneval serval on ühine tipp ja ükski serv ei esine rohkem kui üks kord.

Definitsioon 11. Tsükkel on tee, mille algus- ja lõpp-punkt langevad kokku.

Definitsioon 12. Lihttsükkel on tsükkel, mis ei läbi graafiku ühtegi tippu rohkem kui üks kord.

Definitsioon 13. Tee pikkus , aasa peale pandud , nimetatakse selle tee servade arvu.

Definitsioon 14. Graafi kahte tippu A ja B nimetatakse ühendatud (lahtiühendatuks), kui on olemas (ei ole olemas) tee, mis viib punktist A punkti B.

Definitsioon 15. Graafi nimetatakse seotuks, kui selle kõik kaks tippu on ühendatud; kui graafik sisaldab vähemalt ühte paari lahtiühendatud tippe, siis nimetatakse graafi lahtiühendatuks.

Definitsioon 16. Puu on ühendatud graafik, mis ei sisalda tsükleid.

Puugraafiku kolmemõõtmeline mudel on näiteks päris puu oma keeruka harulise võraga; jõgi ja selle lisajõed moodustavad samuti puu, kuid juba tasase - maapinnal.

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

Definitsioon 18. Puud, mille kõik n tippu on nummerdatud 1-st n-ni, nimetatakse ümber nummerdatud tippudega puuks.

Niisiis oleme uurinud graafiteooria põhimääratlusi, ilma milleta oleks võimatu teoreeme tõestada ja järelikult ka probleeme lahendada.

Ülesanded lahendatud graafikute abil

Kuulsad probleemid

Reisimüüja probleem

Rändmüüja probleem on kombinatoorika teooria üks kuulsamaid probleeme. See esitati 1934. aastal ja parimad matemaatikud murdsid selle peale hambad.

Probleemi avaldus on järgmine.
Rändmüüja (rändkaupmees) peab lahkuma esimesest linnast, külastama teadmata järjekorras ühe korra linnu 2,1,3..n ja pöörduma tagasi esimesse linna. Linnadevahelised kaugused on teada. Millises järjekorras peaks linnades ringi käima, et rändmüüja suletud tee (tuur) oleks kõige lühem?

Meetod rändmüüja probleemi lahendamiseks

Ahne algoritm "mine lähimasse (kuhu te pole veel sisenenud) linna."
Seda algoritmi nimetatakse "ahneks", kuna viimastel sammudel peate ahnuse eest tõsiselt maksma.
Vaatleme näiteks joonisel olevat võrku [Lisa joonis 3], mis kujutab endast kitsast rombi. Laske reisival müüjal alustada linnast 1. Algoritm “Mine”. lähim linn” viib ta linna 2, siis 3, siis 4; Viimasel etapil peate maksma oma ahnuse eest, naastes mööda teemandi pikka diagonaali. Tulemuseks pole mitte kõige lühem, vaid pikim ringreis.

Probleem Königsbergi sildadega.

Probleem on sõnastatud järgmiselt.
Koenigsbergi linn asub Pregeli jõe ja kahe saare kaldal. Erinevaid linnaosi ühendas seitse silda. Pühapäeviti jalutasid linlased linnas ringi. Küsimus: kas on võimalik jalutada nii, et pärast majast lahkumist naasete tagasi, kõndides igal sillal täpselt ühe korra.
Sillad üle Pregeli jõe asuvad nagu pildil[Lisa joonis 1].

Vaatleme silladiagrammile vastavat graafikut [Lisa joonis 2].

Ülesande küsimusele vastamiseks piisab, kui välja selgitada, kas graafik on Euleri. (Paariarv sildu peab ulatuma vähemalt ühest tipust). Sa ei saa linnas ringi jalutada, kõiki sildu korra ületada ja tagasi tulla.

Mitu huvitavat ülesannet

1. "Marsruudid".

Probleem 1

Nagu mäletate, jahimees surnud hinged Tšitšikov külastas kuulsaid maaomanikke üks kord. Ta külastas neid järgmises järjekorras: Manilov, Korobotška, Nozdrjov, Sobakevitš, Pljuškin, Tentetnikov, kindral Betrištšev, Petuhh, Konstanzholgo, kolonel Koškarev. Leiti skeem, millel Tšitšikov visandas valduste suhtelise asukoha ja maateed, ühendades need. Tehke kindlaks, milline pärand kellele kuulub, kui Tšitšikov ei sõitnud ühelgi teel rohkem kui korra [Lisa joonis 4].

Lahendus:

Teekaardilt on näha, et Tšitšikov alustas oma teekonda kinnistust E ja lõpetas kinnistuga O. Märgime, et kinnistuteni B ja C viib ainult kaks teed, mistõttu pidi Tšitšikov neid teid mööda sõitma. Märgistame need paksu joonega. Selgitatud on A läbivad trassi lõigud: AC ja AB. Tšitšikov ei sõitnud teedel AE, AK ja AM. Teeme need maha. Märgistame paksu joonega ED; Tõmmake DK läbi. Tõmbame läbi MO ja MN; Märgistame paksu joonega MF; läbi kriipsutada FO; Märgime FH, NK ja KO paksu joonega. Leiame selle tingimuse juures ainuvõimaliku marsruudi. Ja me saame: kinnisvara E - kuulub Manilovile, D - Korobochka, C - Nozdryov, A - Sobakevitš, B - Pljuškin, M - Tentetnikov, F - Betrištšev, N - Petukh, K - Konstanzholgo, O - Koškarev [Lisa joonis 5].

Probleem 2

Joonisel on piirkonna kaart [Lisa joonis 6].

Saate liikuda ainult noolte suunas. Igat punkti saab külastada mitte rohkem kui üks kord. Mitmel viisil pääsete punktist 1 punkti 9? Milline marsruut on lühim ja milline pikim.

Lahendus:

"Kihistame" ahela järjestikku puuks, alustades tipust 1 [Lisa joonis 7]. Võtame puu. Number võimalikud viisid tabamused 1 kuni 9 on võrdsed puu “rippuvate” tippude arvuga (neid on 14). Ilmselgelt on lühim tee 1-5-9; pikim on 1-2-3-6-5-7-8-9.

2 "Rühmad, tutvumine"

Probleem 1

Kohtunud muusikafestivalil osalejad vahetasid ümbrikke aadressidega. Tõesta, et:

a) üle anti paarisarv ümbrikke;

b) paaritu arv kordi ümbrikke vahetanud osalejate arv on paaris.

Lahendus: Olgu festivalil osalejad A 1, A 2, A 3. . . , Ja n on graafi tipud ja servad ühendavad tippude paare, mis esindavad ümbrikuid vahetavaid mehi [Lisa joonis 8]

Lahendus:

a) iga tipu A i aste näitab ümbrike arvu, mille osaleja A i oma sõpradele andis. Koguarv edastatavate mähisjoonte N on võrdne graafiku kõigi tippude astmete summaga N = kraad. 1 + samm. A 2++. . . + samm. A n -1 + kraad. Ja n, N =2p, kus p on graafi servade arv, st. N – isegi. Järelikult anti üle paarisarv ümbrikke;

b) võrdsuses N = aste. 1 + samm. A 2++. . . + samm. A n -1 + kraad. Ja n paaritute liikmete summa peab olema paaris ja see saab olla ainult siis, kui paaritute liikmete arv on paaris. See tähendab, et paaritu arv kordi ümbrikke vahetanud osalejate arv on paaris.

Probleem 2

Ühel päeval nõustusid Andrei, Boriss, Volodja, Daša ja Galja õhtul kinno minema. Kino ja etenduse valiku otsustati kooskõlastada telefoni teel. Samuti otsustati, et kui kellegagi telefoni teel ühendust saada ei õnnestu, siis kinoreis jääb ära. Õhtul kõik kinno ei kogunenud ja seetõttu jäi filmikülastus ära. Järgmisel päeval hakkasid nad uurima, kes kellele helistas. Selgus, et Andrei kutsus Borisiks ja Volodjaks, Volodjat kutsus Boriss ja Dašaks, Boriss kutsus Andreiks ja Dašaks, Daša kutsus Andreiks ja Volodjaks ning Galja kutsus Andreiks, Volodjaks ja Boriss. Kes ei saanud telefoni ja seetõttu ei tulnud koosolekule?

Lahendus:

Joonistame viis punkti ja märgistame need tähtedega A, B, C, D, D. Need on nimede esimesed tähed. Ühendame punktid, mis vastavad helistanud poiste nimedele.

[Lisa joonis 9]

Pildilt on selge, et kõik poisid - Andrei, Boriss ja Volodya - helistasid kõigile teistele. Sellepärast need tüübid kinno tulid. Kuid Galya ja Dasha ei saanud omavahel telefonile (punktid G ja E ei ole liinilõiguga ühendatud) ja seetõttu ei tulnud nad vastavalt kokkuleppele kinno.

Graafikute rakendamine inimeste erinevates eluvaldkondades

Lisaks toodud näidetele kasutatakse graafikuid laialdaselt ehituses, elektrotehnikas, juhtimises, logistikas, geograafias, masinaehituses, sotsioloogias, programmeerimises, automaatikas tehnoloogilised protsessid ja tootmine, psühholoogia, reklaam. Nii et kõigest eelnevast järeldub see vaieldamatult graafiteooria praktilisest väärtusest, mille tõestamine oli eesmärk.

see uuring Igas teaduse ja tehnoloogia valdkonnas kohtate graafikuid. Graafikud on imelised matemaatilised objektid, millega saab lahendada matemaatilisi, majanduslikke ja loogilisi ülesandeid, erinevaid mõistatusi ning lihtsustada ülesannete tingimusi füüsikas, keemias, elektroonikas ja automaatikas. Paljusid matemaatilisi fakte saab mugavalt sõnastada graafikute keeles. Graafiteooria on osa paljudest teadustest. Graafiteooria on üks ilusamaid ja visuaalsemaid matemaatilised teooriad . IN graafiteooria leiab üha enam rakendusi rakendusküsimustes. Tekkinud on isegi arvutuskeemia – suhteliselt noor keemiavaldkond, mis põhineb graafiteooria rakendamisel.

Molekulaargraafikud, mida kasutatakse stereokeemias ja struktuuritopoloogias, klastrite, polümeeride jne keemias. suunamata graafikud, mis kuvab molekulide struktuuri [Lisa joonis 10]. Nende graafikute tipud ja servad vastavad vastavatele aatomitele ja keemilised sidemed nende vahel.

Molekulaargraafikud ja -puud: [Lisa joonis 10] a, b - vastavalt multigraafid. etüleen ja formaldehüüd; nad ütlevad pentaani isomeerid (puud 4, 5 on isomorfsed puuga 2).

Organismide stereokeemias kõige rohkem. Sageli kasutatakse molekulaarpuid - molekulaargraafikute põhipuid, mis sisaldavad ainult kõiki C-aatomitele vastavaid tippe. Moli komplektide koostamine. puud ja nende isomorfismi kindlakstegemine võimaldavad kindlaks teha, mida nad ütlevad. struktuure ja leida täisarv alkaanide, alkeenide ja alküünide isomeerid

Valguvõrgud

Valguvõrgud on füüsiliselt interakteeruvate valkude rühmad, mis toimivad rakus koos ja koordineeritult, kontrollides organismis toimuvaid omavahel seotud protsesse. [manuse joon. 11].

Hierarhiline süsteemigraafik nimetatakse puuks. Iseloomulik omadus puu puhul on see, et selle mis tahes kahe tipu vahel on ainult üks tee. Puu ei sisalda tsükleid ega silmuseid.

Tavaliselt on hierarhilist süsteemi esindaval puul üks põhitipp, mida nimetatakse puu juureks. Igal puu tipul (v.a juur) on ainult üks esivanem – tema poolt määratud objekt kuulub ühte tippklassi. Iga puu tipp võib genereerida mitu järeltulijat - tippe, mis vastavad madalama taseme klassidele.

Iga puutippude paari jaoks on ainulaadne tee, mis neid ühendab. Seda omadust kasutatakse kõigi esivanemate leidmisel, näiteks meessoost suguvõsast iga inimese, kelle sugupuu on esindatud sugupuu kujul, mis on graafiteooria mõistes "puu".

Minu sugupuu näide [Lisa joon. 12].

Teine näide. Pildil on piibellik sugupuu [Lisa joon. 13].

Probleemide lahendamine

1.Transpordiülesanne. Olgu Krasnodari linnas baas toorainega, mis tuleb ühe reisiga Krõmski, Temrjuki, Slavjansk-on-Kuban ja Timashevski linnadesse laiali jagada, kulutades võimalikult vähe aega ja kütust ning naastes Krasnodari. .

Lahendus:

Kõigepealt teeme kõigist graafiku võimalikud viisid reisida [Lisa Joon.14], võttes arvesse nende asulate vahelisi tegelikke teid ja nendevahelist kaugust. Selle probleemi lahendamiseks peame looma teise graafiku, puutaolise [Lisa Joon.15].

Lahenduse mugavuse huvides tähistame linnad numbritega: Krasnodar - 1, Krõmsk - 2, Temryuk - 3, Slavjansk - 4, Timashevsk - 5.

Tulemuseks on 24 lahendust, kuid vajame ainult lühimaid teid. Kõigist lahendustest on rahuldavad vaid kaks, see on 350 km.

Samamoodi on võimalik ja arvan, et ka vajalik arvutada tegelik vedu ühest kohast teise.

Loogiline probleem vereülekandega.Ämbris on 8 liitrit vett ning kaks panni mahuga 5 ja 3 liitrit. viieliitrisesse panni tuleb valada 4 liitrit vett ja ämbrisse jätta 4 liitrit, s.t. valada vett võrdselt ämbrisse ja suurde panni.

Lahendus:

Iga hetke olukorda saab kirjeldada kolme numbriga [Lisa joon. 16].

Selle tulemusena saame kaks lahendust: üks 7 käiguga, teine ​​8 käiguga.

Järeldus

Seega, et õppida probleeme lahendama, peate mõistma, mis need on, kuidas need on üles ehitatud, mida komponendid need koosnevad sellest, milliseid vahendeid kasutatakse probleemide lahendamiseks.

Graafiteooria abil praktilisi ülesandeid lahendades selgus, et igas etapis, nende lahendamise igas etapis on vaja rakendada loovust.

Algusest peale, esimeses etapis, seisneb see selles, et peate suutma analüüsida ja kodeerida probleemi seisundit. Teine etapp on skemaatiline tähistus, mis koosneb geomeetriline esitus graafikud ja selles etapis on loovuse element väga oluline, sest tingimuse elementide ja graafiku vastavate elementide vahel pole sugugi lihtne leida vastavusi.

Otsustades transpordi ülesanne või sugupuu koostamise ülesandest järeldasin, et graafikumeetod on kindlasti huvitav, ilus ja visuaalne.

Veendusin, et graafikuid kasutatakse laialdaselt majanduses, juhtimises ja tehnoloogias. Graafiteooriat kasutatakse ka programmeerimises. Seda selles töös ei käsitletud, aga ma arvan, et see on ainult aja küsimus.

Selles teaduslikus töös uuritakse matemaatilisi graafikuid, nende kasutusvaldkondi ning lahendatakse graafikute abil mitmeid probleeme. Graafiteooria aluste tundmine on vajalik erinevates tootmise ja ärijuhtimisega seotud valdkondades (näiteks võrgu ehitamise ajakava, posti kohaletoimetamise graafikud). Lisaks õppisin teadusliku töö kallal töötades arvutis töötamist WORD-i tekstiredaktoriga. Seega ülesanded teaduslik töö lõpetatud.

Niisiis tuleneb kõigest eelnevast vaieldamatult graafiteooria praktiline väärtus, mille tõestamine oli käesoleva töö eesmärk.

Kirjandus

Berge K. Graafiteooria ja selle rakendused. -M.: IIL, 1962.

Kemeny J., Snell J., Thompson J. Sissejuhatus lõplikku matemaatikasse. -M.: IIL, 1963.

Maagi O. Graafikud ja nende rakendamine. -M.: Mir, 1965.

Harari F. Graafiteooria. -M.: Mir, 1973.

Zykov A.A. Lõpliku graafi teooria. -Novosibirsk: Teadus, 1969.

Berezina L. Yu. Graafikud ja nende rakendamine. -M.: Haridus, 1979. -144 lk.

"Sorose haridusajakiri" nr 11 1996 (artikkel "Lamedad graafikud");

Gardner M. "Matemaatika vaba aeg", M. "Maailm", 1972 (35. peatükk);

Olehnik S. N., Nesterenko Yu V., Potapov M. K. "Antiik meelelahutuslikud ülesanded", M. "Teadus", 1988 (2. osa, 8. jagu; lisa 4);

Rakendus

Rakendus

P

Riis. 6

Riis. 7

Riis. 8

rakendus

Rakendus

Rakendus

Rakendus

P

Riis. 14

rakendus

Rakendus

Graafiteooria põhimõisted.

Graafiteooria kasutamise näited.

Graafiteooria tekkelugu.

Sageli joonistame inimeste tähistamiseks paberitükkidele ringe, ruute ja punkte, asustatud alad, asjad, mida peame tegema, jms ning ühendame need sirgete ja katkendlike joontega, nooltega tähistame nendevahelisi seoseid, suhteid, tegevuste jada jms.

Selliseid skeeme leidub kõikjal erinevad nimed: sotsiogrammid (psühholoogias), simpleksid (topoloogias), elektriahelad (füüsikas), organisatsiooniskeemid (majanduses), sidevõrgud, sugupuud jne.

D. Koenig tegi ettepaneku nimetada selliseid skeeme "graafikuteks" ja süstemaatiliselt uurida nende omadusi.

Absoluutselt erinevad distsipliinid peame kasutama sarnaseid teoreeme; Nii tõi Kirchhoffi poolt elektriahelate uurimiseks kasutusele võetud “intsidentide maatriksi” kontseptsiooni topoloogiasse A. Poincaré oma “analüüsikoha” loomisel; sotsioloogias pikka aega tuntud liigenduspunkti mõiste ilmus hiljem elektroonikasse; Kõiki sedalaadi näiteid on võimatu loetleda. Graafiteooria rakendamiseks nii paljudes valdkondades peab see olema sisse lülitatud kõrgeim aste abstraktne ja formaliseeritud.

Tegelikult jäävad sellised põhimõisted nagu "ahel", "tee", "keskus", kuigi need on abstraktselt määratletud, samal ajal lahutamatult seotud graafilise reaalsusega ja on diagrammi koostamisel kergesti äratuntavad.

Graafiteooriat käsitledes ei ole meie eesmärk anda matemaatilist tööriista, meie ülesanne on moodustada üldine idee ennekõike selle rakendatud võimalustest juhtimiskorralduse teoorias.

Graafikuteooriat kasutatakse sellistes valdkondades nagu füüsika, keemia, kommunikatsiooniteooria, inseneriteadus arvutid, elektrotehnika, masinaehitus, arhitektuur, operatsioonide uurimine, küberneetika, üldine süsteemiteooria, üldine organisatsiooniteooria, geneetika, psühholoogia, sotsioloogia, majandus, antropoloogia ja lingvistika ning muud teadused.

See teooria on tihedalt seotud ka paljude matemaatikaharudega, sealhulgas rühmateooria, maatriksiteooria, numbrilise analüüsi, tõenäosusteooria, topoloogia ja kombinatoorse analüüsiga.

Graafiteooria teenib matemaatiline mudel iga süsteemi jaoks, mis sisaldab binaarset seost. Graafikud on kaasahaaravad ja esteetiliselt meeldivad, kuna need esitatakse diagrammina. Kuigi graafiteooria sisaldab palju elementaarseid tulemusi, sisaldab see ka tohutult palju väga peeneid kombinatoorseid probleeme.

Graafiteooriat on mitu korda iseseisvalt “avastatud”: see on olnud mõjuval põhjusel võib pidada rakendusmatemaatika haruks. Tegelikult on selle teooria varaseim teadaolev mainimine Euleri töös ja kuigi probleemi, millega ta tegeles, võib pidada tavaliseks mõistatuseks, tekkis see siiski praktikast.

Kirchhoffi ja Cayley hilisemate graafiteooria taasavastuste juured on samuti tegelikkuses. Kirchhoffi elektriahelate uurimine viis tema põhikontseptsioonide ja mitmete graafikute puid puudutavate teoreemide väljatöötamiseni. Cayley lähenes omakorda puude uurimisele, lahendades orgaaniliste isomeeride loetlemise probleemi.

Hamilton pakkus välja veel ühe mõistatusliku lähenemisviisi graafikutele. Pärast seda ilmus kuulus neljavärvi hüpotees, mis on siiani laialt tuntud.

Meie sajandil on toimunud ka erakordselt palju graafiteooria taasavastamist. Mainime lühidalt mõnda neist, järgides kronoloogilises järjekorras.

Königsbergi sildade probleem

Graafiteooria (nagu ka topoloogia) isa on Euler (1707-1782), kes 1736. aastal lahendas tol ajal laialt tuntud ülesande, mida nimetati Königsbergi sillaülesandeks.

Koenigsbergi linnas oli kaks saart, mis olid seitsme sillaga ühendatud Pregolya jõe kallaste ja üksteisega, nagu joonisel näidatud.

Ülesanne oli järgmine: leida kõigi nelja maaosa läbiv marsruut, mis algaks ükskõik millisest, lõppeks samal osal ja läbiks iga silla täpselt ühe korra.

Muidugi on lihtne proovida seda probleemi empiiriliselt lahendada, otsides läbi kõik marsruudid, kuid kõik katsed lõppevad ebaõnnestumisega.

Euleri panus selle probleemi lahendamisesse seisneb selles, et ta tõestas sellise marsruudi võimatust.

Joonis 1. Park Königsbergi linnas, 1736. a

Joonis 2. Königsbergi sildade probleemi graafik

Tõestamaks, et probleemil ei olnud lahendust, määras Euler igale maaosale punkti (tipu) ja igale sillale vastavaid punkte ühendava joone (serva).

Tulemuseks on "graafik". See graafik on näidatud joonisel 2, kus punktid on tähistatud samade tähtedega kui neli maaosa.

Väide selle probleemi "positiivse" lahenduse puudumise kohta on samaväärne väitega joonisel kujutatud graafiku erilise läbimise võimatuse kohta.

Sellest konkreetsest juhtumist lähtudes üldistas Euler probleemi sõnastuse ja leidis möödasõidutee olemasolu kriteerium (erimarsruut) selle graafiku jaoks, nimelt graaf peab olema ühendatud ja iga selle tipp peab olema (kuuluma) paarisarvu servi langev.

Joonisel kujutatud graaf on ühendatud, kuid mitte iga tipp ei lange (kuulub) paarisarvu servi.

Elektriahelad

1847. aastal arenes Kirchhoff puuteooria lahendada liigeste süsteem lineaarne algebralised võrrandid, mis võimaldab teil leida voolu väärtuse igas juhis (kaares) ja igas vaadeldava vooluringis elektriahel.

Füüsiku haridusega lähenes ta probleemide lahendamisele nagu matemaatik. Abstraheerides elektriahelatest ja vooluringidest, mis sisaldavad takistusi, kondensaatoreid, induktiive jms, käsitles ta vastavaid kombinatoorseid struktuure, mis sisaldavad ainult tippe ja ühendusi (servi või kaare) ning ühenduste puhul ei ole vaja näidata, mis tüüpi elektrielementidele need vastavad. kuni .

Seega asendas Kirchhoff tegelikkuses iga elektriahela selle vastava graafikuga ja näitas, et võrrandisüsteemi lahendamiseks ei ole vaja elektriahela graafiku iga tsüklit eraldi käsitleda.

Joonis 3. Võrk N, vastav graafik G.

Selle asemel pakkus ta välja lihtsa, kuid tõhus tehnika(millest sai hiljem standardne protseduur), mille kohaselt piisab, kui piirduda ainult iseseisvate lihtsate graafikutsüklitega, mis on defineeritud mis tahes selle “haarava puuga”. Joonisel 3 on näide elektriahelast N ja sellele vastav graafik G.

Keemilised isomeerid

Puhtalt praktiliste ülesannetega tegelemine orgaaniline keemia Cayley avastas 1857. aastal olulise graafikute klassi, mida nimetatakse puudeks.

Ta püüdis loetleda küllastunud (küllastunud) süsivesinike isomeerid KOOS n N 2 n + 2 teatud arvu n süsinikuaatomitega; Joonis 4.

Joonis 4. Isobutaan

Sotsiaalpsühholoogias.

1936. aastal psühholoog Kurt Lev Ja n pakkus välja, et indiviidi “eluruumi” saab kujutada kasutades tasapinnaline kaart 1).

Sellisel kaardil on piirkonnad esindatud erinevat tüüpi inimese tegevused, näiteks see, mida ta teeb tööl, kodus või tema hobid.

Joonis 5. Kaart ja vastav graafik.

Rõhutame, et K. Lev Ja n käsitles tegelikult graafikuid, nagu on näha jooniselt 5.

See vaatenurk viis rühmadünaamika uurimiskeskuse psühholoogid teise juurde graafi psühholoogiline tõlgendus, milles inimesed on esindatud tippudena ja nende suhted servadena. Sellised suhted on näiteks armastus, vihkamine, suhtlemine, alistumine.

Lewini oletus kehtib ainult tasapinnaliste kaartide kohta, kuna ta joonistas oma joonised alati tasapinnal. Järgnevalt arendati K. Levini ideed välja sotsiomeetrilistes protseduurides.

Organisatsiooniteoorias

Graafikuid saab esitada mitte ainult ranges klassikalises vormis. Seega on I. Adizese ettevõtte elutsükkel esitatud järgmisel kujul.

Joonis 6. Elutsükkel ettevõtted

Funktsionaalne organisatsiooniline struktuur on üles ehitatud põhimõttel jaotada funktsioonid organisatsiooni sees ja luua funktsioonide haldamiseks otsast lõpuni allstruktuurid.

Tootmisjaoskonnad

Riis. Funktsionaalne organisatsiooniline struktuur

Seega vajadus eri üldine teooria, mis on rakendatav mis tahes inimtegevuse sfääris, määrati ära praktika vajadused.

Sellest teooriast sai "Graafiteooria".

Graafiteooria põhimõisted

Alustame definitsiooniga, graafiteoorial pole üheselt mõistetavat definitsiooni, kuid on ka teisi.

Graafiteooria- diskreetse matemaatika haru, mis uurib lõplike hulkade omadusi nende elementide vahel antud seostega.

Graafiteooria- matemaatika haru, mille eripäraks on geomeetriline lähenemine objektide uurimisele

Graafiteooria- matemaatiline keel süsteemide ja protsesside struktuuride analüüsi ja sünteesiga seotud mõistete formaliseeritud määratlemiseks.