Graafikud on ennekõike molekulide esitamise vahendid. Molekuli topoloogilises kirjelduses on seda kujutatud molekulaargraafikuna (MG), kus tipud vastavad aatomitele, servad aga keemilistele sidemetele (molekuli graafiteoreetiline mudel). Tavaliselt võetakse selles esituses arvesse ainult skeleti aatomeid, näiteks "kustutatud" vesinikuaatomitega süsivesinikke.

Keemiliste elementide valentsus seab teatud piirangud tippude astmetele. Alkaanipuudel (ühendatud graafikutel, millel pole tsükleid) on tipu kraadid (r), mis ei tohi ületada nelja (r = 1, 2, 3, 4).

Graafikuid saab määrata maatriks kujul, mis on mugav nendega arvutis töötamisel.

Lihtsa graafi tipu naabrusmaatriks on ruutmaatriks A = [aσχ] elementidega aσχ = 1, kui tipud σ ja χ on ühendatud servaga ja σχ = 0 muidu. Kaugusmaatriks on ruutmaatriks D = koos elementidega dσχ, mis on määratletud kui minimaalne servade arv (lühim vahemaa) tippude σ ja χ vahel. Mõnikord kasutatakse ka naabrus- ja servakaugusmaatriksit (A e ja D e).

Maatriksite A ja D (A e ja D e) tüüp sõltub tippude (või servade) nummerdamise meetodist, mis põhjustab nende käsitlemisel ebamugavusi. Graafi iseloomustamiseks kasutatakse graafi invariante – topoloogilisi indekseid (TI).

Üks pikkuste radade arv

pi = xcc 0 = m = n-1

Kahe pikkusega radade arv

Külgnevate servade kolmikute arv (ühise tipuga)

Wieneri arv (W), mis on määratletud vaadeldava graafiku kaugusmaatriksi elementide poolsummana:

jne.

"Struktuuri ja omaduse" seose uurimise metoodika topoloogiliste indeksite kaudu graafiteoreetilises lähenemisviisis sisaldab järgmisi samme.

Uuritavate objektide (koolitusnäidis) valik ja arvandmete seisu analüüs omaduse P kohta antud ühendite vahemiku kohta.

TI-de valik, võttes arvesse nende eristamisvõimet, korrelatsioonivõimet omadustega jne.

Graafiliste sõltuvuste uurimine "Molekuli graafiku omadus P - TI", näiteks P on n - skeleti aatomite arv, P on W - Wieneri arv jne.

Näiteks funktsionaalse (analüütilise) sõltuvuse P = _DTI tuvastamine,

P \u003d a (TI) + b,

P \u003d aln (TI) + b,

P \u003d a (TI) 1 + b (TI) 2 + ... + n (TI) n + c

jne. Siin on a, b, c mõned parameetrid (mitte segi ajada liiteahelate parameetritega.), mis tuleb määrata.

Р arvulised arvutused, arvutatud väärtuste võrdlemine eksperimentaalsetega.

Nende ühendite omaduste ennustamine, mida pole veel uuritud või isegi saadud (väljaspool seda proovi).

Topoloogilisi indekseid kasutatakse ka liitarvutus- ja prognoosiskeemide koostamisel. Neid saab kasutada uute ravimite väljatöötamisel, teatud kemikaalide kantserogeense toime hindamisel, uute (veel sünteesimata) ühendite suhtelise stabiilsuse ennustamisel jne.

Siiski tuleb meeles pidada, et TI valik on sageli juhuslik; need ei pruugi peegeldada molekulide olulisi struktuurseid iseärasusi ega dubleerida informatsiooni (saadud teiste indeksite abil) ning arvutusskeemidel ei pruugi olla kindlat teoreetilist alust ning neid on raske füüsikalis-keemiliselt tõlgendada.

TvSU füüsikalise keemia osakonna meeskond on juba aastaid viinud läbi arvutus-teoreetilist uuringut probleemil “Ainete omaduste seos molekulide struktuuriga: matemaatiline (arvuti)modelleerimine”. Fookuses on uute struktuuride, algoritmide sihipärane otsimine mitmete graafiteoreetiliste ja kombinatoorsete probleemide lahendamiseks, mis tekivad ainete struktuuri ja omaduste kohta teabe kogumise ja töötlemise käigus, ekspertteabe otsingusüsteemide ja andmebaaside loomisel, arendamisel. kvantitatiivsed arvutus- ja prognoosimeetodid.

Oleme koostanud liitskeeme ja leidnud analüütilised sõltuvused kujul P = Y(TI) mitmete orgaaniliste ja muude molekulide jaoks. Saadud valemite järgi viidi läbi vaadeldavate ühendite füüsikalis-keemiliste omaduste arvulised arvutused, s.

Bibliograafia

1. Vinogradova M.G., Papulov Yu.G., Smolyakov V.M. Alkaanide "struktuuriomaduste" kvantitatiivsed korrelatsioonid. Liitarvutusskeemid. Tver, 1999. 96 lk.
2. Topoloogia ja graafikuteooria keemilised rakendused / Toim. R. King. M.: Mir, 1987. 560 lk.
3. Graafiteooria rakendamine keemias / Toim. N.S. Zefirova ja S.I. Kuchanova. Novosibirsk: Nauka, 1988. 306 lk.
4. Stankevitš M.I., Stankevitš I.V., Zefirov N.S. Topoloogilised indeksid orgaanilises keemias // Uspekhi khimii. 1988. V.57, nr 3, S.337-366.
5. Vinogradova M.G., Saltõkova M.N. Graafikteoreetiline lähenemine alküülsilaanide struktuuri ja omaduste seoste uurimisel.// Fundamental Research, 2009. Nr 1. lk 17-19.
6. Vinogradova M.G., Saltõkova M.N., Efremova A.O., Maltševskaja O.A. Alküülsilaanide struktuuri ja omaduste seos // Kaasaegsete loodusteaduste edusammud, nr 1, 2010. Lk 136-137.
7. Vinogradova M.G., Saltõkova M.N., Efremova A.O. Alküülsilaanide "Struktuur - omadus" seosed: graafiteoreetiline lähenemine // Kaasaegsete loodusteaduste edusammud, nr 3, 2010. Lk.141-142.

Bibliograafiline link

• Eriala HAC RF02.00.03
• Lehtede arv 410

Väitekirja pealkiri Keemiadoktor Vonchev, Danail Georgiev

Pool sajandit tagasi avaldas Paul Dirac arvamust, et põhimõtteliselt sisaldub kogu keemia kvantmehaanika seadustes, kuid tegelikkuses tekivad praktilistes arvutustes ületamatud matemaatilised raskused. Elektrooniline arvutustehnoloogia on aidanud vähendada distantsi võimaluste ja kvantmehaanilise lähenemise rakendamise vahel. Ometi on suure elektronide arvuga molekulide arvutused keerulised ja mitte piisavalt täpsed ning seni saab sel viisil arvutada vaid üksikuid molekulaarseid omadusi. Teisest küljest on orgaanilises keemias olulisi struktuuriprobleeme, mis ei ole täielikult lahendatud, ja eelkõige on see molekulide struktuuri ja omaduste vahelise seose probleem. Teoreetilises keemias on küsimus molekulide põhiliste struktuuriomaduste – nende hargnevuse ja tsüklilisuse – kvantifitseerimises. See küsimus on oluline, kuna hargnenud ja tsükliliste molekulide struktuuri üldiste seaduspärasuste kvantitatiivset analüüsi saab suurel määral üle kanda nende muudele omadustele. Sel viisil oleks võimalik ennustada isomeersete ühendite rühma järjestust selliste omaduste väärtuste järgi nagu stabiilsus, reaktsioonivõime, spektraalsed ja termodünaamilised omadused jne. See võib hõlbustada veel sünteesimata ainete omaduste ennustamist. ühendite klassid ja "ettemääratud omadustega struktuuride otsimine. Vaatamata märkimisväärsetele jõupingutustele on endiselt lahtine küsimus keemilise teabe ratsionaalse kodeerimise kohta, et seda tõhusalt salvestada ja arvutites kasutada. Selle probleemi optimaalne lahendus avaldaks mõju nii orgaaniliste ühendite klassifikatsiooni ja nomenklatuuri kui ka keemiliste reaktsioonide mehhanismide täiustamise kohta.Enne keemiliste elementide perioodilise sys-4 teooriat tõstatab ka küsimuse keemiliste elementide omaduste perioodilisuse terviklikust ja kvantitatiivsest tõlgendamisest. suurustel, mis peegeldavad elektroonilist struktuuri paremini kui elemendi järgarv.

Selle tulemusena on viimastel aastakümnetel ärgitatud uute keemia teoreetiliste meetodite väljatöötamist, mis on koondatud matemaatilise keemia nime alla. Peamise koha selles hõivavad topoloogilised meetodid, mis kajastavad molekulide kõige üldisemaid struktuurseid ja geomeetrilisi omadusi. Üks topoloogia harudest, graafiteooria, pakub keemikule mugavat matemaatilist keelt molekuli kirjeldamiseks, kuna struktuurivalemid on oma olemuselt keemilised graafikud. Graafiteooria pakutavad eelised keemiauuringutes põhinevad selle matemaatilise aparatuuri otsesel rakendamisel ilma arvutit kasutamata, mis on oluline eksperimentaalkeemikutele. Graafiteooria võimaldab üsna lihtsalt süveneda molekulide struktuuriomadustesse. Saadud tulemused on üldised ja neid saab sõnastada teoreemide või reeglitena ning seega saab neid rakendada mis tahes sarnaste keemiliste (ja mittekeemiliste) objektide puhul.

Pärast Shannoni ja Wieneri infoteooriat ja küberneetikat käsitlevate fundamentaaltööde avaldamist on pidevalt kasvanud ka huvi infoteoreetiliste uurimismeetodite vastu. Mõiste "teave" algne tähendus on seotud teabe, sõnumite ja nende edastamisega. See kontseptsioon väljus kiiresti kommunikatsiooniteooria ja küberneetika piiridest ning tungis erinevatesse elus- ja eluta looduse, ühiskonna ja tunnetuse teadustesse. Infoteoreetilise lähenemise arendamise protsess teaduses on keerulisem kui küberneetilise teabekategooria formaalne ülekandmine teistele teadmiste valdkondadele. Informatiivne lähenemine ei ole lihtsalt tõlge vähem levinud keeltest metakeelde. See pakub teistsugust vaadet süsteemidele ja nähtustele ning võimaldab saada uusi tulemusi. Laiendades seoseid erinevate teadusharude vahel, võimaldab see meetod leida kasulikke analoogiaid ja ühiseid mustreid niššide vahel. Arenev kaasaegne teadus kaldub üha suuremale üldistusele, ühtsusele. Selles osas on infoteooria üks paljutõotavamaid valdkondi.

Oluline koht selles protsessis on infoteooria rakendamisel keemias ja teistes loodusteadustes – füüsikas, bioloogias jne. Nendes teadustes kasutatakse objektide ja protsesside omaduste uurimisel ja kirjeldamisel infoteooria meetodeid. mis on seotud struktuuri, korrastatuse, organiseerimissüsteemidega "Infokäsitluse kasulikkus keemias seisneb eelkõige selles, et pakutakse uusi võimalusi keemiliste struktuuride erinevate aspektide – aatomite, molekulide, kristallide jne kvantitatiivseks analüüsiks. juhtudel aatomite ja molekulide "struktuurilise" teabe ja "teabe sisu" mõisted.

Seoses eelnevaga on lõputöö põhieesmärk näidata struktuuriprobleemide graafiteoreetilise ja infoteoreetilise käsitluse viljakust c. keemias, aatomitest ja molekulidest polümeeride ja kristallideni, hõlmab selle eesmärgi saavutamine eraldi etappidena:

1. Suuruste süsteemi määratlus (informatsioon ja topoloogilised indeksid; aatomite, molekulide, polümeeride ja kristallide kvantitatiivseks iseloomustamiseks).

2. Nende omaduste, geomeetrilise ja elektroonilise struktuuri vahelise seose küsimusele uue üldisema lähenemise väljatöötamine selle põhjal. Mõnede orgaaniliste ühendite, polümeeride ja mittesünteesitud transaktiniidide nMx elementide omaduste ennustamine.

Kristallide kasvu modelleerimise meetodite loomine ja kristallide vakantsused.

3. Molekulide üldistatud topoloogiline iseloomustamine, väljendades nende hargnemise ja tsüklilisuse olemust matemaatiliselt tõestatud struktuurireeglites, ning nende reeglite kaardistamise uurimine erinevate molekulaarsete omaduste järgi.

4. Uute tõhusate meetodite loomine keemiliste ühendite ja keemiliste reaktsioonide mehhanismide kodeerimiseks seoses nende klassifikatsiooni ja nomenklatuuri täiustamisega, eriti aga seoses arvutite kasutamisega keemilise informatsiooni töötlemisel.

PEATÜKK 2. UURIMISMEETOD 2L. TEOREEGIOÕPETUSE MEETOD 2.1.1 "Sissejuhatus

Informatsioon on tänapäeva teaduse üks fundamentaalsemaid mõisteid, mis ei ole vähem üldine kui mateeria ja energia mõisted. See seisukoht leiab õigustuse juba teabe määratlustes. Wieneri sõnul ei ole informatsioon ei mateeria ega energia.

Ashby vaatleb teavet kui "mitmekesisuse mõõdet antud süsteemis". Gluškovi sõnul on "informatsioon ruumi ja aja jaotuse ebahomogeensuse mõõt". Sellest lähtuvalt tunnustatakse tänapäeval üha enam tõsiasja, et lisaks materiaalsele ja energeetilisele loodusele on looduses ja tehnikas esinevatel objektidel ja nähtustel ka informatsioonilised omadused. Mõned prognoosid lähevad kaugemale, ennustades, et teadusuuringute fookus nihkub üha enam protsesside informatsioonilisele olemusele, millest saab 21. sajandil peamine uurimisobjekt. Need prognoosid põhinevad sisuliselt süsteemide ja protsesside optimaalse juhtimise võimalusel teabe kaudu, mis tegelikult? on teabe põhifunktsioon küberneetikas. Tulevikus võivad need ideed viia tehnoloogiate loomiseni, kus iga aatomit ja molekuli juhib informatsioon – see võimalus on leidnud teostuse seni vaid eluslooduses.

Infoteooria esilekerkimine viitab tavaliselt 1948. aastale, mil Claude Shannon avaldas oma põhiteose. Idee informatsioonist kui entroopiaga seotud suurusest on aga palju vanem. Aastal 1894 tegi Boltzmann kindlaks, et mis tahes teavet, mis on saadud antud süsteemi kohta, seostatakse selle võimalike olekute arvu vähenemisega ja seetõttu tähendab entroopia suurenemine "teabe kadumist". 1929. aastal

Szilard töötas selle idee välja üldise teabe kohta füüsikas. tema CP

Hiljem üldistas Vrilluin entroopia ja teabe vahelise seose idee oma mittegentroopilises põhimõttes kujul, mis hõlmab ka nähtuste informatiivset külge. Küsimustele infoteooria ja termodünaamika seostest ning eelkõige entroopia ja informatsiooni vahelistest suhetest on endiselt palju tähelepanu (üksikasjalik loetelu selle valdkonna publikatsioonidest on toodud ülevaates 58). Numbri viimasest arengust tuleb eriti esile tõsta Kobozevi tööd mõtlemise termodünaamikast, milles on põhjendatud tees mõtteprotsesside antientroopilisusest.

"Spetsiaalse suhtlusteooriana" esile kerkinud teabeteooria ületas kiiresti oma algsed piirid ja leidis rakendust erinevates teaduse ja tehnika valdkondades: keemias, bioloogias, meditsiinis, lingvistikas, psühholoogias, esteetikas jne. Info roll esiteks tunnustati bioloogiat. Kas olete lahendanud elusorganismides teabe säilitamise, töötlemise ja edastamisega seotud olulisi küsimusi, sealhulgas geneetilise teabe kodeerimise 60-7? spontaanse spontaanse elu tekke võimaluse hindamine Maal^, bioloogilise termodünaamika põhiseaduste sõnastamine^, bioenergia küsimuste analüüs jne. Kvantitatiivse kriteeriumina kasutati objektide infosisu

A A A evolutsioon ". Tõstatati küsimus toitumisprotsesside informatiivse olemuse kohta ^®^^.

Infoteooria tungib endiselt aeglaselt keemiasse ja füüsikasse, kuigi viimastel aastatel on selles vallas tehtud mõningaid edusamme, tõstatati küsimus keemiliste reaktsioonide infobilansi võimaliku olemasolu kohta. Hinnati bioorgaaniliste molekulide infovõimet ja selle põhjal pakuti välja nende ühendite uus klassifikatsioon ning hinnati ka keemiliste reaktsioonide spetsiifilisust.

Levin, Bernstein ja teised on rakendanud infoteooriat molekulaardünaamikas, et kirjeldada tasakaalust kaugel olevate molekulaarsüsteemide käitumist. Selle lähenemisviisi olemus seisneb "üllatuse" kontseptsioonis, mis on kõrvalekalle sellest, mida mikrokanoonilise jaotuse põhjal oodatakse. Välja on pakutud erinevaid rakendusi, sealhulgas laserite jõudluse uurimine, konkureerivate reaktsiooniteede hargnemissuhte määramine (eeldades, et kõige tõenäolisem on Shannoni funktsiooni maksimumile vastav tee) ja nii edasi.

Dodel jt tegid ettepaneku jagada molekulaarsüsteemi poolt hõivatud ruum mitmeks üksteist välistavaks alamruumiks, mida nimetatakse loožideks. Parimad lokaliseeritud elektronide rühmi sisaldavad öömajad leitakse teabefunktsiooni minimeerides. Sears jt leidsid seose kvantmehaaniliste kineetiliste energiate ja informatsiooniliste suuruste vahel. Selle tulemuse tulemusena saab kvantmehaanika variatsiooniprintsiibi sõnastada minimaalse teabe põhimõttena. op os

Kobozev jt seostasid katalüsaatorite selektiivsust ja aktiivsust nende informatsioonilise sisuga. Nad koostasid ka optimaalsed teabetingimused katalüütiliste omaduste iseloomustamiseks ja ennustamiseks. Krisi teke ja kasv

Oeh. rp oo tall peeti infoprotsessiks”. Rakov allutas infoanalüüsile katalüsaatori pindade töötlemise erinevate keemiliste ainetega.

Kaasaegses analüütilises keemias on kasvav trend optimaalse katsetamise suunas, et saada minimaalse arvu katsete põhjal maksimaalset teavet.

Need uued ideed põhinevad infoteoorial, mänguteoorial ja süsteemiteoorial. Teised autorid on rakendanud infoteooriat analüüsivea ja -aja minimeerimiseks, suurema selektiivsuse saavutamiseks, analüüsimeetodite efektiivsuse hindamiseks jne. Sedalaadi uurimistöö hõlmab ka füüsikalisi meetodeid analüütilises keemias, sealhulgas gaasikromatograafiat, aatomiemissiooni spektraalanalüüsi jne.

Infoteoreetilised meetodid on osutunud kasulikuks ka geokeemias keemiliste ühendite sagedusjaotuse iseloomustamisel geokeemilistes süsteemides,170 keerukuse astme hindamisel ja nende süsteemide klassifitseerimisel.

Insenerikeemias saab infoanalüüsi abil lahendada selliseid keemilis-tehnoloogiliste süsteemide probleeme nagu optimaalsete töötingimuste valik, juhtimisnõuete kehtestamine jne.101.

Näited infoteooria edukast rakendamisest keemias näitavad taas, et ka looduses ja tehnoloogias leiduvatel süsteemidel on informatsiooniline iseloom. Samuti näitab see, et teabepõhine lähenemine toimib universaalse keelena süsteemide ja eriti mis tahes tüüpi keemiliste struktuuride kirjeldamiseks, millega ta seostab teatud teabefunktsiooni ja numbrilise mõõdu. See laieneb. infoteooria võimalike rakenduste valdkond keemias.

Infokäsitluse kasulikkus keemias seisneb eelkõige selles, et see pakub võimalust keemiliste struktuuride erinevate aspektide kvantitatiivseks analüüsiks. Nende struktuuride keerukuse astet, nende korraldust ja spetsiifilisust saab võrrelda ühel kvantitatiivsel skaalal. See võimaldab uurida keemiliste struktuuride mõningaid kõige üldisemaid omadusi, nagu nende hargnevus ja tsüklilisus, uurida ja võrrelda organiseerituse astet erinevates keemiliste ühendite klassides, bioloogiliselt aktiivsete ainete ja katalüsaatorite spetsiifilisust ning võimaldab läheneda kahe keemilise objekti sarnasuse ja erinevuse astme küsimusele.

Informatiivne lähenemine sobib väga hästi isiklike klassifitseerimisprobleemide lahendamiseks. Nendel juhtudel on võimalik tuletada üldised teabevõrrandid klassifikatsiooniobjektide põhirühmade jaoks (rühmad ja perioodid keemiliste elementide perioodilises süsteemis, keemiliste ühendite homoloogsed jadad, isomeersete ühendite jada jne) *

Teabemeetodite suurt eristusvõimet keerukate struktuuride (isomeerid, isotoobid jne) suhtes saab kasutada keemilise teabe arvutipõhisel töötlemisel ja salvestamisel. Need meetodid on kasulikud mitte ainult erinevate struktuuride vahel, vaid ka alternatiivsete hüpoteeside ja lähenduste vahel, mis pakub huvi kvantkeemia jaoks. Uute infoteoorial põhinevate hüpoteeside püstitamise võimalused on aga piiratumad, kuna see teooria kirjeldab muutujate vahelisi seoseid, kuid ei kirjelda ühegi neist käitumist.

Probleem. Struktuuri ja omaduste vaheline seos on veel üks infoteooria lähenemisviisi eduka rakendamise valdkond keemias. Selle lähenemisviisi tõhusust näidatakse doktoritöös keemia kvalitatiivselt erinevate struktuuritasemete puhul - aatomite, molekulide, polümeeride, kristallide ja isegi aatomituumade elektronkestad^»^. Seda saab rakendada nii kvalitatiivses kui ka kvantitatiivses aspektis. Esimesel juhul saab teabe alusel määratleda erinevaid struktuurireegleid, mis peegeldavad kahe või enama struktuuriteguri vastastikust mõju. Samuti on võimalik saada kvantitatiivseid korrelatsioone infoindeksite ja omaduste vahel?®. Samas pakuvad infoindeksid põhimõtteliselt paremaid korrelatsioone võrreldes teiste indeksitega, kuna kajastavad paremini keemiliste struktuuride tunnuseid. Edukad korrelatsioonid on võimalikud mitte ainult entroopiaga otseselt seotud suurustega, vaid ka selliste suurustega nagu sidumisenergia, mille seos teabega pole kaugeltki ilmne. Siin on eraldiseisva molekuli või aatomina kaasatud omadused, aga ka nende suured agregaadid, st omadused, mis sõltuvad molekulide ja aatomite vastastikmõjust, mitte ainult nende sisestruktuurist. Lisaks võivad protsessid keemias olla ka teabeanalüüsi subjekt, mis põhineb teabeindeksite muutumisel interaktsioonide käigus.

Samuti tuleks meeles pidada mõningaid informatiivse lähenemisviisi piiranguid. Kuigi teabe kvantitatiivsed mõõdud on .tonni, on need suhtelised, mitte absoluutsed. Need on ka statistilised tunnused ja viitavad agregaatidele, kuid mitte nende üksikutele elementidele. Teabeindekseid saab määratleda aatomite ja molekulide erinevate omaduste jaoks, kuid nendevaheline seos on sageli keeruline ja kaudne.

Teisest küljest võib ühe struktuuri kohta mitme teabeindeksi olemasolu põhjustada vastakaid tundeid. Siiski tuleb meeles pidada, et kõik need indeksid on seaduslikud. Siin on õige küsimus, millised neist kogustest on kasulikud ja mil määral.

Selles peatükis tutvustatakse esmakordselt infoteoreetilisi indekseid:, / mis iseloomustavad aatomite elektronstruktuuri, aga ka uusi infoindekseid molekulide sümmeetria, topoloogia ja elektronstruktuuri kohta. Nende struktuuriomaduste rakendamist käsitletakse III peatüki jaotistes IV.2 ja V 1.

2.1.2. Vajalik info infoteooriast

Infoteooria pakub kvantitatiivseid meetodeid teabe hankimise, säilitamise, edastamise, teisendamise ja kasutamise uurimiseks. Nendes meetodites on põhikohal teabe kvantitatiivne mõõtmine.Informatsioonihulga mõiste määratlemine eeldab laialt levinud, kuid ebaselgete ideede tagasilükkamist teabe kui agregaadi, faktide, teabe, teadmiste kohta.

Infohulga mõiste on tihedalt seotud entroopia kui määramatuse mõõdu mõistega. 1923. aastal iseloomustas Hartley n erineva tulemusega katse määramatust arvuga ¿od n. Shannoni 1948. aastal avaldatud statistilises teabeteoorias on teabe hulk defineeritud tõenäosuse mõiste kaudu. On teada, et seda mõistet kasutatakse olukorra kirjeldamiseks, kus teatud hulgast ühe või mitme elemendi (tulemuse) valikuga kaasneb ebakindlus. Shannoni järgi tulemuse X/katse X määramatuse mõõt tõenäosusega p(X¡) -¿Oy(X)) . Täieliku katse X keskmise mõõtemääramatuse mõõt Xt, X2, ♦ võimalike tulemustega, vastavalt tõenäosustega p(X4), p(X2). chp(Xn), on kogus

H(x) = - pcx,) Log p(Xi) cg>

Statistilise informatsiooni teoorias nimetatakse H(X) tõenäosusjaotuse entroopiaks. Viimased moodustavad /7 erineva tulemuse korral lõpliku tõenäosusskeemi, s.t.

Tõenäosuse mõistet saab defineerida hulgateooria seisukohalt üldisemalt. Olgu lõplik hulk A jaotus /T) klassiks, milles /\ on disjunktsed hulgad; mõne ekvivalentsusrelatsiooni järgi X * Ekvivalentsusklasside hulk

R/X = (2,2; nimetatakse X-i tegurite hulgaks R

Kolmogorovi tõenäosusfunktsioon (tõenäosuslik vastavus) p allub kolmele tingimusele:

Arvurida PfXf) , P(X2) , ., P(XGG)) nimetatakse partitsiooni A jaotuseks ja valemi (2.1) Shannoni funktsioon H(X) väljendab partitsiooni X entroopiat.

Tuleb meeles pidada, et entroopia mõiste infoteoorias on üldisem kui termodünaamiline entroopia. Viimane, mida peetakse aatom-molekulaarsete liikumiste korral esineva häire mõõdupuuks, on üldisema mõiste entro-! Välismaised otseinvesteeringud on mis tahes häire, ebakindluse või mitmekesisuse mõõt.

Teabe hulka X väljendatakse lahutatud määramatuse väärtusega. Siis on antud sündmuse keskmine entroopia paljude võimalike tulemustega võrdne keskmise teabehulgaga, mis on vajalik mis tahes sündmuse X valimiseks hulgast ^ ,X^,. ja määratakse Shannoni valemiga (y-e 2.1):

I(x) = -K$Lp(x,-)logp(K) = Hw

Siin on K positiivne konstant, mis määrab teabe mõõtühikud. Eeldusel K \u003d 4, mõõdetakse entroopiat (vastavalt informatsiooni) kümnendühikutes. Kõige mugavam mõõtmissüsteem põhineb kahendühikutel (bittidel). Sel juhul K ~ W2 ja logaritm wur-u(2.4) võetakse kahes aluses ja \-! tähistatakse lühemalt t-ga. Üks binaarne teabeühik (või 1 bitt) on teabe hulk, mis saadakse, kui Valimine kahe võrdselt tõenäolise võimaluse vahel on teada ja entroopia ühikutes¿ .dgasG\ on teisendusteguriks Voltzmanni konstant (1.38.10 yj.gra.d~ jagatud /a?Yu.

On tõestatud, et infohulga logaritmilise funktsiooni valik ei ole juhuslik ja see on ainus funktsioon, mis rahuldab informatsiooni aktiivsuse ja mittenegatiivsuse tingimusi.

Nii üksik kui ka keskmine info on alati positiivne. See omadus on seotud asjaoluga, et tõenäosus on alati väiksem kui üks ja võrrandi (2.4) konstant võetakse alati positiivseks. E | & heliseb ^ Y, siis

13 p(x, -) = H(x, o c2,5) ja see ebavõrdsus säilib ka pärast keskmistamist.

Antud sündmuse (kogemuse) X keskmine infohulk saavutab maksimumi tõenäosuste ühtlase jaotusega p(X,) - p(X2) = . . .=p(Xn)* st. p(X)) jaoks mis tahes P jaoks:

Juhuslikult sõltuvate sündmuste X ja y paari puhul väljendatakse keskmist teabehulka ka Shannoni valemiga:

1(xy> = - р(х, yj) № pix, yj) (2,7)

Võrrandit (2.7) saab üldistada mis tahes lõpliku hulga jaoks, olenemata selle elementide olemusest:

1(xy) = -Z Z. P(X,nYj) 16P(X-,nYj) (2.8) on P kaks jagatiskomplekti kahe erineva samaväärsuse x ja y suhtes ning K/xy on tegur- X sektsioonide komplekt; ja:

Olles kirjutanud ühendtõenäosuse võrrandisse (2.7) tingimusteta ja tingimusliku tõenäosuse p(x;, y^ = p(>) korrutisena<¡)"P(Уj/x¡) , и представив логарифм в виде сумш»получается уравнение:

1(Xy) = 1(X) x – 1(y/X) (2.9), kus T(x/y) on y-s sisalduva tingimusliku teabe keskmine hulk x-i suhtes ja see on saadud:

1(y/X) = -Y p(X, y1) 1B p(Y;/X-,) (2,10)

Funktsiooni määratlemine:

1 (X, y.! = 1 (Y> - 1 (y / X)) (2-Sh ja asendades selle võrrandis (2.9):

1(xy) - 1(X) + 1(y) -1(x, y) (2.12) saab selgeks, et T(X, y) väljendab komplekssündmuse (X, y") kohta käiva informatsiooni hälvet. üksiksündmuste (tulemuste) teabe liitevõime: x ja y Seetõttu on G (X, Y) X ja y vahelise statistilise sõltuvuse (seotuse) määr. x ja y3 vaheline seos on sümmeetriline.

Üldjuhul kehtivad x ja y statistilise seose ning tingimusteta teabe keskmise hulga X või y kohta järgmised ebavõrdsused:

Võrdsus võimsuses, kui võrrandi (2.11) teine ​​liige on null, s.o. kui iga / vastab I-le, mille p(y. ¡X))=

Kui suurused X ja y on sõltumatud, s.t. kui võrrandis (2.12) T (X, y) \u003d 0, siis

1 (xy) = 1 (X)<2Л5>

See võrrand väljendab teabehulga aditiivsuse omadust ja on üldistatud sõltumatute juhuslike suuruste jaoks. tuleb meelde:

1 (xnx2,.,xn) = 11 1 (x/) (2,16)

Samuti on teada tõenäosuspõhised lähenemisviisid teabe kvantitatiivseks määramiseks. Ingarden ja Urbanich pakkusid välja aksiomaatilise / sizvdelenie-Sheini teabe ilma tõenäosusteta, piiratud Boole'i ​​rõngaste funktsiooni kujul. Märkimisväärset huvi pakub Kolmogorovi pakutud epsilon-entroopia (kombinatoorne lähenemine) ja eriti teabe hulga algoritmiline määramine. Kolmogorovi sõnul loetakse ühes objektis (komplektis) sisalduva teabe hulka teise objekti (komplekti) suhtes programmide "minimaalseks pikkuseks", mis on kirjutatud nullide ja ühtede jadana ning võimaldab üks-ühele. muutumine; esimene objekt teises:: \u003d H (X / y) \u003d W "W I (R) (2-17)

Kolmogorovi algoritmiline lähenemine pakub uut

17 keerukuse ja järjestuse mõistetel põhinevat infoteooria loogilist alust, takcha&Yn-mõisted "entroopia" ja "informatsiooni hulk" osutusid rakendatavateks üksikobjektidele.

Uskumatud meetodid infoteoorias laiendavad infohulga mõiste sisu vähendatud määramatuse hulgalt vähendatud ühtluse hulgani või mitmekesisuse hulgani vastavalt Ashby tõlgendusele. Mis tahes tõenäosuste komplekti, mis on normaliseeritud ühtsusele, võib pidada vastavaks teatud elementide hulgale, millel on mitmekesisus. Mitmekesisuse all mõistetakse hulga elementide omadust, mis seisneb nende erinevuses, mittekatsumuses mingi ekvivalentsussuhte suhtes. See @ võib olla "objektide erinevate elementide, suhete, suhete, omaduste kogum. Väikseim teabeühik, bitt, väljendab selles lähenemisviisis minimaalset erinevust, st erinevust kahe objekti vahel, mis ei ole identsed, erinevad mõne poolest vara.

Selles aspektis on infoteoreetilised meetodid rakendatavad nn. struktuurne teave on antud süsteemi struktuuris sisalduva teabe hulk. Struktuur tähendab siin igasugust lõplikku hulka, mille elemendid on jaotatud alamhulkade (ekvivalentsusklasside) vahel olenevalt teatud ekvivalentsusseost.

Sisaldagu see struktuur A/ elemente ja need jaotuvad mingi ekvivalentsuskriteeriumi järgi ekvivalentsete elementide alamhulkadesse: . See jaotus vastab tõenäosuse alamhulga ^ pn p2> lõplikule tõenäosusskeemile. . ?Rp elemendid

2.18) kus ¿T - A/"u on ühe (juhuslikult) valitud elemendi sattumise tõenäosus / - sellesse alamhulka, mille jaoks on A/,-elemendid. Selle struktuuri elementide tõenäosusjaotuse entroopia H, määratud võrrandi (2.4) järgi võib pidada / keskmise teabehulga I mõõduks, mis sisaldub struktuuri ühes elemendis: - p

1u P/ , bitti elemendi kohta (2.19)

Struktuuri üldise infosisu annab tuletisvõrrand (2.19):

1-M1-A//0/h-hnmm,<*.»>

Kirjanduses puudub üksmeel selle kohta, kuidas y-y (2.19) ja (2.20) defineeritud suurusi nimetada. Mõned autorid eelistavad nimetada neid vastavalt keskmiseks ja üldiseks teabesisuks. Seega ei ole I Moushowitzi järgi entroopia mõõt selles tähenduses, nagu seda infoteoorias kasutatakse, kuna see ei väljenda /\/ elementidest koosneva struktuuri keskmist määramatust kõigist võimalikest struktuuridest koosnevas ansamblis. on sama: elementide arv. Olen pigem vaadeldava struktuuri infosisu süsteemi muutumatuks jätvate teisenduste süsteemi suhtes. Remi järgi võrrandist (2.4) mõõdab teabe hulka pärast katset ja enne seda on H(x) katse määramatusega seotud entroopia mõõt. Meie arvates on "katse", mis vähendab keemiliste struktuuride (aatomite, molekulide jne) määramatust, ise "nende struktuuride moodustamise protsess nende mitteseotud elementidest. Teave on siin seotud kujul, see sisaldub struktuur ja seetõttu kasutatakse sageli mõistet "teabe sisu".

Struktuurse teabe kontseptsioon, mis põhineb võrrandite (2.19) ja (2.20) antud tõlgendusel1, ühtib hästi Ashby ideedega teabe hulgast kui mitmekesisuse suurusest. Kui süsteem koosneb samadest elementidest, ei ole selles mitmekesisust. Sel juhul y-s (2.19) ja (2.20)/="/

Struktuuri elementide maksimaalse mitmekesisuse korral on Λ £ = / ja struktuuri teabesisu on maksimaalne:

4 "* -N16 u, T ^ ^ vi

2.1.3. Infoteoreetilised indeksid keemiliste elementide aatomite elektronstruktuuri iseloomustamiseks

Soovitatav lõputööde loetelu erialal "Orgaaniline keemia", 02.00.03 VAK kood

• Kombinatoorse kodeerimise teooria ja infoteooria asümptootilised probleemid 2001, füüsika- ja matemaatikateaduste kandidaat Vilenkin, Pavel Aleksandrovitš2011, füüsika- ja matemaatikateaduste kandidaat Shutkin, Juri Sergejevitš

Pange tähele, et ülaltoodud teadustekstid postitatakse ülevaatamiseks ja saadakse algse väitekirja tekstituvastuse (OCR) kaudu. Sellega seoses võivad need sisaldada tuvastusalgoritmide ebatäiuslikkusega seotud vigu. Meie poolt edastatavate lõputööde ja kokkuvõtete PDF-failides selliseid vigu pole.

Graafikud on ennekõike molekulide esitamise vahendid. Molekuli topoloogilises kirjelduses on seda kujutatud molekulaargraafikuna (MG), kus tipud vastavad aatomitele, servad aga keemilistele sidemetele (molekuli graafiteoreetiline mudel). Tavaliselt võetakse selles esituses arvesse ainult skeleti aatomeid, näiteks "kustutatud" vesinikuaatomitega süsivesinikke.

Keemiliste elementide valentsus seab teatud piirangud tippude astmetele. Alkaanipuudel (ühendatud graafikutel, millel pole tsükleid) on tipu kraadid (r), mis ei tohi ületada nelja (r = 1, 2, 3, 4).

Graafikuid saab määrata maatriks kujul, mis on mugav nendega arvutis töötamisel.

Lihtsa graafi tipu naabrusmaatriks on ruutmaatriks A = [aσχ] elementidega aσχ = 1, kui tipud σ ja χ on ühendatud servaga ja σχ = 0 muidu. Kaugusmaatriks on ruutmaatriks D = koos elementidega dσχ, mis on määratletud kui minimaalne servade arv (lühim vahemaa) tippude σ ja χ vahel. Mõnikord kasutatakse ka naabrus- ja servakaugusmaatriksit (A e ja D e).

Maatriksite A ja D (A e ja D e) tüüp sõltub tippude (või servade) nummerdamise meetodist, mis põhjustab nende käsitlemisel ebamugavusi. Graafi iseloomustamiseks kasutatakse graafi invariante – topoloogilisi indekseid (TI).

Üks pikkuste radade arv

pi = xcc 0 = m = n-1

Kahe pikkusega radade arv

Külgnevate servade kolmikute arv (ühise tipuga)

Wieneri arv (W), mis on määratletud vaadeldava graafiku kaugusmaatriksi elementide poolsummana:

jne.

"Struktuuri ja omaduse" seose uurimise metoodika topoloogiliste indeksite kaudu graafiteoreetilises lähenemisviisis sisaldab järgmisi samme.

Uuritavate objektide (koolitusnäidis) valik ja arvandmete seisu analüüs omaduse P kohta antud ühendite vahemiku kohta.

TI-de valik, võttes arvesse nende eristamisvõimet, korrelatsioonivõimet omadustega jne.

Graafiliste sõltuvuste uurimine "Molekuli graafiku omadus P - TI", näiteks P on n - skeleti aatomite arv, P on W - Wieneri arv jne.

Näiteks funktsionaalse (analüütilise) sõltuvuse P = _DTI tuvastamine,

P \u003d a (TI) + b,

P \u003d aln (TI) + b,

P \u003d a (TI) 1 + b (TI) 2 + ... + n (TI) n + c

jne. Siin on a, b, c mõned parameetrid (mitte segi ajada liiteahelate parameetritega.), mis tuleb määrata.

Р arvulised arvutused, arvutatud väärtuste võrdlemine eksperimentaalsetega.

Nende ühendite omaduste ennustamine, mida pole veel uuritud või isegi saadud (väljaspool seda proovi).

Topoloogilisi indekseid kasutatakse ka liitarvutus- ja prognoosiskeemide koostamisel. Neid saab kasutada uute ravimite väljatöötamisel, teatud kemikaalide kantserogeense toime hindamisel, uute (veel sünteesimata) ühendite suhtelise stabiilsuse ennustamisel jne.

Siiski tuleb meeles pidada, et TI valik on sageli juhuslik; need ei pruugi peegeldada molekulide olulisi struktuurseid iseärasusi ega dubleerida informatsiooni (saadud teiste indeksite abil) ning arvutusskeemidel ei pruugi olla kindlat teoreetilist alust ning neid on raske füüsikalis-keemiliselt tõlgendada.

TvSU füüsikalise keemia osakonna meeskond on juba aastaid viinud läbi arvutus-teoreetilist uuringut probleemil “Ainete omaduste seos molekulide struktuuriga: matemaatiline (arvuti)modelleerimine”. Fookuses on uute struktuuride, algoritmide sihipärane otsimine mitmete graafiteoreetiliste ja kombinatoorsete probleemide lahendamiseks, mis tekivad ainete struktuuri ja omaduste kohta teabe kogumise ja töötlemise käigus, ekspertteabe otsingusüsteemide ja andmebaaside loomisel, arendamisel. kvantitatiivsed arvutus- ja prognoosimeetodid.

Oleme koostanud liitskeeme ja leidnud analüütilised sõltuvused kujul P = Y(TI) mitmete orgaaniliste ja muude molekulide jaoks. Saadud valemite järgi viidi läbi vaadeldavate ühendite füüsikalis-keemiliste omaduste arvulised arvutused, s.

Bibliograafia

1. Vinogradova M.G., Papulov Yu.G., Smolyakov V.M. Alkaanide "struktuuriomaduste" kvantitatiivsed korrelatsioonid. Liitarvutusskeemid. Tver, 1999. 96 lk.
2. Topoloogia ja graafikuteooria keemilised rakendused / Toim. R. King. M.: Mir, 1987. 560 lk.
3. Graafiteooria rakendamine keemias / Toim. N.S. Zefirova ja S.I. Kuchanova. Novosibirsk: Nauka, 1988. 306 lk.
4. Stankevitš M.I., Stankevitš I.V., Zefirov N.S. Topoloogilised indeksid orgaanilises keemias // Uspekhi khimii. 1988. V.57, nr 3, S.337-366.
5. Vinogradova M.G., Saltõkova M.N. Graafikteoreetiline lähenemine alküülsilaanide struktuuri ja omaduste seoste uurimisel.// Fundamental Research, 2009. Nr 1. lk 17-19.
6. Vinogradova M.G., Saltõkova M.N., Efremova A.O., Maltševskaja O.A. Alküülsilaanide struktuuri ja omaduste seos // Kaasaegsete loodusteaduste edusammud, nr 1, 2010. Lk 136-137.
7. Vinogradova M.G., Saltõkova M.N., Efremova A.O. Alküülsilaanide "Struktuur - omadus" seosed: graafiteoreetiline lähenemine // Kaasaegsete loodusteaduste edusammud, nr 3, 2010. Lk.141-142.

Bibliograafiline link

OMAVALITSUSE AUTONOOMNE ÜLDHARIDUSASUTUS KESKKONNAHARIDUSKOOL № 2

Valmistatud

Legkokonets Vladislav, 10A õpilane

Graafiteooria praktiline rakendamine

Juhendaja

L.I. Noskova, matemaatikaõpetaja

St.Bryukhovetskaya

2011. aastal

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

2. Graafiteooria tekkelugu……………………………………………….………..4

3. Graafiteooria põhimääratlused ja teoreemid…………………………………….………6

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

4.1 Kuulsad ülesanded……………………………………………………………8

4.2 Mõned huvitavad ülesanded………………………………….……………..9

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

6. Probleemi lahendamine……………………………………………………………………………………………………

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

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

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

Sissejuhatus

Mõistatuste lahendamises ja meelelahutuslikes mängudes sündinud graafikuteooriast on nüüdseks saanud lihtne, ligipääsetav ja võimas tööriist paljude probleemidega seotud probleemide lahendamiseks. Graafikud on sõna otseses mõttes üldlevinud. Graafikute kujul saab tõlgendada näiteks teeskeeme ja elektriskeeme, geograafilisi kaarte ja keemiliste ühendite molekule, seoseid inimeste ja inimrühmade vahel. Viimase nelja aastakümne jooksul on graafiteooriast saanud üks kiiremini arenevaid matemaatika harusid. Selle põhjuseks on kiiresti laieneva kasutusvaldkonna nõudmised. Seda kasutatakse integraallülituste ja juhtimisahelate projekteerimisel, automaatide, loogiliste lülituste, programmide vooskeemide uurimisel, majanduses ja statistikas, keemias ja bioloogias, sõiduplaani teoorias. Sellepärast asjakohasust Teema on tingitud ühelt poolt graafikute ja nendega seotud uurimismeetodite populaarsusest, teisalt aga väljatöötamata terviklikust süsteemist selle rakendamiseks.

Paljude eluprobleemide lahendamine nõuab pikki arvutusi ja mõnikord ei too need arvutused edu. Sellest see koosneb uurimisprobleem. Tekib küsimus: kas nende lahendusele on võimalik leida lihtne, ratsionaalne, lühike ja elegantne lahendus. Kas ülesandeid on lihtsam lahendada, kui kasutada graafikuid? See määras minu uurimistöö teema: "Graafiteooria praktiline rakendamine"

eesmärk uurimine toimus graafikute abil, et õppida kiiresti lahendama praktilisi probleeme.

Uurimistöö hüpotees. Graafimeetod on väga oluline ja laialdaselt kasutatav erinevates teaduse ja inimelu valdkondades.

Uuringu eesmärgid:

1. Tutvuda selleteemalise kirjanduse ja Interneti-allikatega.

2. Kontrollige graafimeetodi efektiivsust praktiliste ülesannete lahendamisel.

3. Tee järeldus.

Uuringu praktiline tähtsus on see, et tulemused äratavad kahtlemata paljudes huvi. Kas keegi teist pole proovinud oma suguvõsa sugupuud ehitada? Ja kuidas seda õigesti teha? Transpordifirma juhil tuleb ilmselt lahendada transpordi tulusama kasutamise probleem kauba vedamisel sihtkohast mitmesse asulasse. Iga õpilane seisis silmitsi loogiliste transfusiooniülesannetega. Selgub, et need lahendatakse graafikute abil lihtsalt.

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

Graafiteooria tekkelugu

Graafiteooria rajajaks peetakse matemaatik Leonhard Eulerit (1707-1783). Selle teooria tekkimise 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.

“Kord esitati mulle probleem Koenigsbergi linnas asuva saare kohta, mida ümbritseb jõgi, millest üle viskab seitse silda.

[Lisa joonis 1] Küsimus on selles, kas keegi suudab neist pidevalt ümber käia, 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 banaalne, tundus mulle siiski tähelepanu vääriv, sest selle lahendamiseks ei piisa ei geomeetriast, algebrast ega kombinatoorsest kunstist. Pärast pikka kaalumist leidsin üsna veenval tõendil põhineva lihtsa reegli, mille järgi saab kõigi sedalaadi ülesannete puhul kohe kindlaks teha, kas sellise ringi saab teha läbi suvalise arvu ja suvaliselt paigutatud sildade või mitte. Königsbergi sillad asuvad nii, et neid saab kujutada järgmisel joonisel [Lisa joonis 2], kus A tähistab saart ning B , C ja D on üksteisest jõeharudega eraldatud mandri osad

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

"Sellel lahendusel näib oma olemuselt vähe pistmist matemaatikaga ja mulle pole selge, miks peaks seda lahendust ootama pigem matemaatikult kui kelleltki teiselt, sest seda lahendust toetab ainult mõistus ja selle lahenduse leidmiseks pole vaja kaasata mingeid matemaatikale omaseid seadusi. 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 mööda pääseda, läbides iga silda ainult üks kord? Vastuse leidmiseks jätkame Euleri kirjaga Marinonile:

"Küsimus seisneb selles, kas kõigist neist seitsmest sillast on võimalik ümber sõita, läbides iga ühe korra või mitte. Minu reegel viib sellele küsimusele järgmise lahenduseni. Kõigepealt tuleb vaadata, mitu lõiku on eraldatud veega - sellised , millel pole muud üleminekut ühelt teisele, välja arvatud silla kaudu.Selles näites on neli sellist sektsiooni - A, B, C, D. Järgmiseks peate eristama, kas nendele üksikutele lõikudele viivad sillad on paaris või paaritu. Nii et meie puhul viib viis silda A lõiguni ja kolm silda ülejäänud osani, st üksikute lõikude juurde viivate sildade arv on paaritu ja sellest ühest piisab, et lahendage probleem. Kui see on kindlaks tehtud, rakendame järgmist reeglit: kui iga üksiku lõigu juurde viivate sildade arv oleks paaris, oleks kõnealune ümbersõit võimalik ja samal ajal oleks võimalik seda ümbersõitu alustada mis tahes jaotisest oleks veider, sest ainult üks oleks n kui see ei saa olla paaris, siis ka siis võiks üleminek toimuda, nagu ette nähtud, kuid kindlasti tuleb võtta ainult ümbersõidu algus ühest neist kahest lõigust, 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 siin võiks välja tuua muid, tõsisemaid probleeme, võib see meetod olla veelgi kasulikum ja ei tohiks hooletusse jätta".

Graafiteooria põhimõisted ja teoreemid

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

Definitsioon 1. Graaf on piiratud arvu punktide kogum, mida nimetatakse graafi tippudeks ja mis ühendavad paarikaupa mõnda neist joonte tippudest, mida nimetatakse graafiku 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.

Edaspidi 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. määratlus. Graafi, mis koosneb ainult isoleeritud tippudest, nimetatakse nulliks - loendama .

Tähistus: O "– tippude ja servadeta graaf

4. määratlus. 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 k astme graafikuks .

Definitsioon 7. Antud graafi täiend on graaf, mis koosneb kõigist servadest ja nende otstest, mis tuleb lisada esialgsele graafikule, et saada täielikku graafi.

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

Definitsioon 9. Tasapinnalise graafi hulknurka, mille sees ei ole graafi tippe ega servi, nimetatakse selle tahkuks.

Tasapinna ja graafi tahkude mõisteid kasutatakse erinevate kaartide "õige" värvimise ülesannete lahendamisel.

Definitsioon 10. Tee punktist A punktini 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. Jalgratas on tee, mille algus- ja lõpp-punkt on samad.

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

Definitsioon 13. pikk tee , aasa peale pandud , on selle tee servade arv.

Definitsioon 14. Graafi kahte tippu A ja B nimetatakse ühendatud (lahtiühendatuks), kui selles 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 graafikut lahtiühendatuks.

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

Graaf-puu 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. Lahtiühendatud graafikut, mis koosneb ainult puudest, nimetatakse metsaks.

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

Niisiis, oleme kaalunud graafiteooria peamisi määratlusi, ilma milleta oleks võimatu teoreeme tõestada ja järelikult ka probleeme lahendada.

Ülesanded lahendatud graafikute abil

Kuulsad väljakutsed

Reisiva müüja probleem

Rändmüüja probleem on kombinatoorika teooria üks kuulsamaid probleeme. See pandi üles 1934. aastal ja parimad matemaatikud murdsid selle pärast 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 tuleks linnad läbida, 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 kallilt maksma.
Vaatleme näiteks joonisel olevat võrku [rakenduse joonis 3] kujutab endast kitsast rombi. Laske müüjal alustada linnast 1. Algoritm "Mine lähimasse linna" viib ta linna 2, siis 3, siis 4; viimasel sammul peate maksma ahnuse eest, naastes mööda rombi pikka diagonaali. Tulemuseks pole mitte kõige lühem, vaid pikim tuur.

Königsbergi sildade probleem.

Ülesanne on sõnastatud järgmiselt.
Königsbergi linn asub Pregeli jõe ja kahe saare kaldal. Erinevaid linnaosi ühendas seitse silda. Pühapäeviti tegid linlased linnas jalutuskäike. Küsimus: kas on võimalik jalutada nii, et pärast majast lahkumist tulla tagasi, möödudes täpselt üks kord üle iga silla.
Sillad üle Pregeli jõe asuvad nagu pildil[Lisa joonis 1].

Vaatleme sillaskeemile vastavat graafikut [lisa joon.2].

Probleemi küsimusele vastamiseks piisab, kui välja selgitada, kas graafik on Euler. (Vähemalt ühes tipus peab olema paarisarv sildu). Linnas ringi jalutades on võimatu üks kord kõik sillad läbi käia ja tagasi tulla.

Mitu huvitavat väljakutset

1. "Marsruudid".

Ülesanne 1

Nagu mäletate, külastas surnud hingede jahimees Tšitšikov iga kord kuulsaid maaomanikke. Ta külastas neid järgmises järjekorras: Manilov, Korobotška, Nozdrev, Sobakevitš, Pljuškin, Tentetnikov, kindral Betrištšev, Petuhh, Konstanzholgo, kolonel Koškarev. Leiti skeem, millel Tšitšikov visandas valduste ja neid ühendavate maateede suhtelise asukoha. Tehke kindlaks, milline pärand kellele kuulub, kui Tšitšikov ei läbinud ühtegi teed rohkem kui üks kord [lisa joon.4].

Otsus:

Teekaardi järgi on näha, et Tšitšikov alustas oma teekonda E mõisaga ja lõpetas O valdusega.Märkame, et valdustesse B ja C viib ainult kaks teed, mistõttu pidi Tšitšikov sõitma neid teid pidi. Märgistame need paksude joontega. Määratakse 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 ; läbi kriipsutada DK . Kriipsutada maha MO ja MN; märgi paksu joonega MF ; läbi kriipsutada FO ; jämeda joonega märgime FH , NK ja KO. Leiame antud tingimusel ainuvõimaliku marsruudi. Ja me saame: kinnistu E - kuulub Manilovile, D - Korobochka, C - Nozdrev, A - Sobakevitš, V - Pljuškin, M - Tentetnikov, F - Betrištšev, N - Petukh, K - Konstanzholgo, O - Koshkarev [rakenduse joonis 5].

2. ülesanne

Joonisel on piirkonna kaart [lisa joon.6].

Saate liikuda ainult noolte suunas. Iga 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.

Otsus:

"Kihistage" skeem järjestikku puuks, alustades tipust 1 [rakenduse joonis 7]. Võtame puu. Võimalike viiside arv 1-st 9-ni on võrdne 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"

Ülesanne 1

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

a) kokku saadeti 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 ümbrikke vahetanud mehi [Lisa joonis 8]

Otsus:

a) iga tipu A i aste näitab ümbrike arvu, mille osaleja A i oma sõpradele andis. Edastatud mähisjoonte koguarv N on võrdne graafiku N = samm kõigi tippude astmete summaga. 1 + samm. A 2++. . . + samm. Ja n -1 + samm. Ja n , N =2p , kus p on graafi servade arv, st. N on paaris. Seetõttu saadeti paarisarv ümbrikke;

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

2. ülesanne

Kord leppisid Andrei, Boriss, Volodja, Daša ja Galja õhtul kinno minema. Kino valiku ja seansi otsustati kokku leppida telefoni teel. Samuti otsustati, et kui kellelegi helistada pole võimalik, siis kinoreis jääb ära. Õhtul kõik kinno ei kogunenud ja seetõttu jäi kinokülastus katki. 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 helistada ja seetõttu ei tulnud koosolekule?

Otsus:

Joonistame viis punkti ja tähistame need tähtedega A, B, C, D, E. Need on nimede esimesed tähed. Ühendame need punktid, mis vastavad üksteisele helistanud kuttide nimedele.

[rakenduse joonis 9]

Pildilt on näha, et kõik poisid - Andrei, Boriss ja Volodya - helistasid kõigile teistele. Sellepärast need tüübid kinno tulid. Kuid Galya ja Dasha ei suutnud teineteisele helistada (punktid D ja D ei ole lõiguga ühendatud) ja seetõttu ei tulnud nad vastavalt kokkuleppele kinno.

Graafikute kasutamine inimeste elu erinevates valdkondades

Lisaks toodud näidetele kasutatakse graafikuid laialdaselt ehituses, elektrotehnikas, juhtimises, logistikas, geograafias, masinaehituses, sotsioloogias, programmeerimises, tehnoloogiliste protsesside ja tööstusharude automatiseerimises, psühholoogias ja reklaamis. Niisiis tuleneb kõigest eelnevast vaieldamatult graafiteooria praktiline väärtus, mille tõestamine oli käesoleva uurimuse eesmärk.

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, automaatikas. Graafikute keeles on mugav sõnastada paljusid matemaatilisi fakte. Graafiteooria on osa paljudest teadustest. Graafiteooria on üks ilusamaid ja visuaalsemaid matemaatilisi teooriaid. Graafiteooria on viimasel ajal leidnud rakendusküsimustes üha enam rakendusi. Tekkinud on isegi arvutikeemia – suhteliselt noor keemiavaldkond, mis põhineb graafiteooria rakendamisel.

Molekulaargraafikud, mida kasutatakse stereokeemias ja struktuuritopoloogias, klastrite, polümeeride jne keemias, on suunamata graafikud, mis kuvavad molekulide struktuuri [rakenduse joonis 10]. Nende graafikute tipud ja servad vastavad vastavatele aatomitele ja nendevahelistele keemilistele sidemetele.

Molekulaargraafikud ja -puud: [rakenduse joonis 10] a, b - multigraafid resp. etüleen ja formaldehüüd; in-mol. pentaani isomeerid (puud 4, 5 on isomorfsed puuga 2).

Organismide stereokeemias kõige rohkem kasutavad sageli molekulaarpuid - molekulaargraafikute põhipuid, mis sisaldavad ainult kõiki C-aatomitele vastavaid tippe. puud ja nende isomorfismi tuvastamine võimaldavad muuli määrata. struktuure ja leida alkaanide, alkeenide ja alküünide isomeeride koguarv

Valguvõrgud

Valguvõrgud - füüsiliselt interakteeruvate valkude rühmad, mis toimivad rakus ühiselt ja koordineeritult, kontrollides organismis toimuvaid omavahel seotud protsesse. [rakenduse joon. üksteist].

Hierarhiline süsteemigraafik nimetatakse puuks. Puu eripäraks on see, et selle kahe tipu vahel on ainult üks tee. Puu ei sisalda tsükleid ja 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. Puu suvaline tipp võib genereerida mitu järeltulijat – madalama taseme klassidele vastavaid tippe.

Iga puutippude paari jaoks on ainulaadne tee, mis neid ühendab. Seda omadust kasutatakse kõigi esivanemate leidmisel, näiteks meesliinist iga inimese, kelle sugupuu on esindatud sugupuuna, mis on ka graafiteooria mõistes “puu”.

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

Üks näide veel. Joonisel on kujutatud piibli sugupuu [lisa joon.13].

Probleemi lahendamine

1. Transpordiülesanne. Olgu Krasnodari linnas toorainega baas, mis tuleb korraga istutada Krõmski, Temrjuki, Kubani Slavjanski ja Timashevski linnadesse, kulutades samal ajal võimalikult vähe aega ja kütust ning naasta tagasi. Krasnodari.

Otsus:

Kõigepealt koostame kõigi võimalike marsruutide graafiku. [rakenduse joonis 14], võttes arvesse nende asulate vahelisi tegelikke teid ja nendevahelist kaugust. Selle probleemi lahendamiseks peame looma teise graafiku, puu [rakenduse joonis 15].

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

Selle tulemuseks oli 24 lahendust, kuid vajame ainult lühimaid teid. Kõigist lahendustest on rahul vaid kaks, need on 350 km.

Samamoodi on võimalik ja arvan, et on vaja arvutada reaalne vedu ühest paikkonnast teise.

Loogiline ülesanne vereülekandeks.Ämbris on 8 liitrit vett ja kaks potti mahuga 5 ja 3 liitrit. viieliitrisesse kastrulisse tuleb valada 4 liitrit vett ja ämbrisse jätta 4 liitrit, s.t. valada vett võrdselt ämbrisse ja suurde kastrulisse.

Otsus:

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

Nii et probleemide lahendamise õppimiseks peate mõistma, mis need on, kuidas need on paigutatud, millistest komponentidest koosnevad, millised on vahendid, mida probleemide lahendamiseks kasutatakse.

Graafiteooria abil praktilisi ülesandeid lahendades sai selgeks, et igal sammul, 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 seisneb graafikute geomeetrilises esitamises ja selles etapis on loovuse element väga oluline, kuna tingimuse elementide ja graafiku vastavate elementide vahel pole sugugi lihtne leida vastavusi. .

Transpordiülesannet või sugupuu koostamise ülesannet lahendades jõudsin järeldusele, et graafikumeetod on kindlasti huvitav, ilus ja visuaalne.

Olin veendunud, et graafikuid kasutatakse laialdaselt majanduses, juhtimises ja tehnoloogias. Graafiteooriat kasutatakse ka programmeerimises, seda selles artiklis ei käsitletud, kuid arvan, et see on ainult aja küsimus.

Käesolevas teadustöös käsitletakse matemaatilisi graafikuid, nende kasutusvaldkondi, lahendatakse mitmeid ülesandeid graafikute abil. Graafiteooria aluste tundmine on vajalik erinevates tootmisjuhtimise, ettevõtlusega seotud valdkondades (näiteks ehitusvõrgu skeem, posti kohaletoimetamise graafikud). Lisaks õppisin teadusliku töö kallal töötades arvutis töötamist WORD-tekstiredaktoris. Seega on teadusliku töö ülesanded täidetud.

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.

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

Zykov A.A. Lõplike graafikute teooria. -Novosibirsk: Nauka, 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. "Mir", 1972 (35. peatükk);

Olehnik S. N., Nesterenko Yu. V., Potapov M. K. "Vanad meelelahutuslikud probleemid", M. "Nauka", 1988 (2. osa, 8. jagu; lisa 4);

Rakendus

Rakendus

P

Riis. 6

Riis. 7

Riis. kaheksa

Rakendus

Rakendus

Rakendus

P

Riis. neliteist

Rakendus