Ang mga graph ay nagsisilbi, una sa lahat, bilang isang paraan ng kumakatawan sa mga molekula. Sa topological na paglalarawan ng isang molekula, ito ay inilalarawan bilang isang molecular graph (MG), kung saan ang mga vertices ay tumutugma sa mga atomo, at ang mga gilid ay tumutugma sa mga kemikal na bono (graph-theoretic na modelo ng isang molekula). Karaniwan, ang mga skeletal atom lamang ang isinasaalang-alang sa representasyong ito, halimbawa, mga hydrocarbon na may "binura" na mga atomo ng hydrogen.

Ang lakas ng mga elemento ng kemikal ay nagpapataw ng ilang mga paghihigpit sa mga antas ng vertices. Ang mga puno ng alkane (mga konektadong graph na walang mga cycle) ay may vertex degrees (r) na hindi maaaring lumampas sa apat (r = 1, 2, 3, 4).

Maaaring tukuyin ang mga graph sa matrix form, na maginhawa kapag nagtatrabaho sa kanila sa isang computer.

Ang vertex adjacency matrix ng isang simpleng graph ay isang square matrix A = [aσχ] na may mga elemento aσχ = 1 kung ang vertex σ at χ ay konektado sa pamamagitan ng isang gilid, at σχ = 0 kung hindi man. Ang distance matrix ay isang square matrix D = na may mga elementong dσχ na tinukoy bilang ang pinakamababang bilang ng mga gilid (ang pinakamaikling distansya) sa pagitan ng mga vertices σ at χ. Minsan ginagamit din ang adjacency at edge distance matrice (A e at D e).

Ang uri ng mga matrice A at D (A e at D e) ay depende sa paraan ng pagbibilang ng mga vertice (o mga gilid), na nagdudulot ng abala kapag hinahawakan ang mga ito. Upang makilala ang isang graph, ginagamit ang mga invariant ng graph - mga topological index (TI).

Bilang ng mga landas ng isang haba

pi = xcc 0 = m = n-1

Bilang ng mga landas na may haba na dalawa

Bilang ng triplets ng mga katabing gilid (na may karaniwang vertex)

Ang numero ng Wiener (W), na tinukoy bilang kalahating kabuuan ng mga elemento ng distance matrix ng graph na isinasaalang-alang:

atbp.

Kasama sa pamamaraan para sa pag-aaral ng ugnayang "structure-property" sa pamamagitan ng topological index sa graph-theoretic approach ang mga sumusunod na hakbang.

Pagpili ng mga bagay ng pag-aaral (sample ng pagsasanay) at pagsusuri ng estado ng numerical data sa property P para sa isang partikular na hanay ng mga compound.

Pagpili ng mga TI na isinasaalang-alang ang kanilang kakayahang makita ang kaibhan, kakayahang makipag-ugnayan sa mga katangian, atbp.

Ang pag-aaral ng mga graphical na dependency na "Property P - TI ng graph ng molekula", halimbawa, P on n - ang bilang ng mga skeletal atoms, P on W - ang Wiener number, atbp.

Pagtatatag ng functional (analytical) dependence P = _DTI), halimbawa,

P \u003d a (TI) + b,

P \u003d aln (TI) + b,

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

atbp. Narito ang a, b, c ay ilang mga parameter (hindi dapat ipagkamali sa mga parameter ng mga additive circuit.) upang matukoy.

Mga numerical na kalkulasyon ng Р, paghahambing ng mga kinakalkula na halaga sa mga pang-eksperimentong.

Paghula ng mga katangian ng mga compound na hindi pa napag-aaralan o kahit na nakuha (sa labas ng sample na ito).

Ang mga topological na indeks ay ginagamit din sa pagbuo ng mga additive na pagkalkula at mga scheme ng pagtataya. Magagamit ang mga ito sa pagbuo ng mga bagong gamot, sa pagtatasa sa aktibidad ng carcinogenic ng ilang mga kemikal, sa paghula ng kamag-anak na katatagan ng mga bagong (hindi pa synthesize) na mga compound, atbp.

Gayunpaman, dapat tandaan na ang pagpili ng TI ay madalas na random; maaaring hindi ito sumasalamin sa mahahalagang katangian ng istruktura ng mga molekula o duplicate na impormasyon (nakuha sa tulong ng iba pang mga indeks), at ang mga scheme ng pagkalkula ay maaaring walang matatag na teoretikal na pundasyon at mahirap bigyang-kahulugan sa pisikal na kemikal.

Ang pangkat ng Department of Physical Chemistry ng TvSU ay nagsasagawa ng computational-theoretical na pag-aaral sa problemang "Relasyon sa pagitan ng mga katangian ng mga sangkap at istraktura ng mga molekula: pagmomolde ng matematika (computer)" sa loob ng maraming taon. Ang pokus ay sa target na paghahanap para sa mga bagong istruktura, mga algorithm para sa paglutas ng isang bilang ng mga graph-theoretical at combinatorial na mga problema na lumitaw sa kurso ng pagkolekta at pagproseso ng impormasyon tungkol sa istraktura at mga katangian ng mga sangkap, paglikha ng mga dalubhasang sistema ng pagkuha ng impormasyon at mga database, pagbuo quantitative na paraan ng pagkalkula at pagtataya.

Nakagawa kami ng mga additive scheme at nakahanap ng analytical dependences ng form na P = Y(TI) para sa isang bilang ng mga organic at iba pang molecule. Ayon sa nakuha na mga formula, ang mga numerical na kalkulasyon ng mga katangian ng physicochemical ng mga compound na isinasaalang-alang ay isinagawa, s.

Bibliograpiya

1. Vinogradova M.G., Papulov Yu.G., Smolyakov V.M. Dami ng mga ugnayan ng "pag-aari ng istruktura" ng mga alkanes. Additive na mga scheme ng pagkalkula. Tver, 1999. 96 p.
2. Mga Chemical Application ng Topology at Graph Theory / Ed. R. Hari. M.: Mir, 1987. 560 p.
3. Paglalapat ng Graph Theory sa Chemistry / Ed. N.S. Zefirov at S.I. Kuchanova. Novosibirsk: Nauka, 1988. 306 p.
4. Stankevich M.I., Stankevich I.V., Zefirov N.S. Topological index sa organic chemistry // Uspekhi khimii. 1988. V.57, No. 3, S.337-366.
5. Vinogradova M.G., Saltykova M.N. Graph-theoretic approach sa pag-aaral ng relasyon sa pagitan ng structure at properties ng alkylsilanes.// Fundamental Research, 2009. No. 1. pp. 17-19.
6. Vinogradova M.G., Saltykova M.N., Efremova A.O., Malchevskaya O.A. Ang ugnayan sa pagitan ng istraktura at mga katangian ng alkylsilanes // Mga tagumpay ng modernong natural na agham, No. 1, 2010. P. 136-137.
7. Vinogradova M.G., Saltykova M.N., Efremova A.O. Mga Kaugnayan "Istruktura - pag-aari" ng alkylsilanes: graph-theoretic approach // Mga tagumpay ng modernong natural na agham, No. 3, 2010. P.141-142.

Bibliographic na link

• Specialty HAC RF02.00.03
• Bilang ng mga pahina 410

Pamagat ng disertasyon Doktor ng Chemistry Vonchev, Danail Georgiev

Kalahati ng isang siglo na ang nakalilipas, ipinahayag ni Paul Dirac ang opinyon na, sa prinsipyo, ang lahat ng kimika ay nakapaloob sa mga batas ng quantum mechanics, ngunit sa katotohanan, ang hindi malulutas na mga paghihirap sa matematika ay lumitaw sa mga praktikal na kalkulasyon. Ang teknolohiyang electronic computing ay nakatulong upang mabawasan ang distansya sa pagitan ng mga posibilidad at ang pagpapatupad ng quantum mechanical approach. Gayunpaman, ang mga kalkulasyon ng mga molekula na may malaking bilang ng mga electron ay kumplikado at hindi sapat na tumpak, at sa ngayon ay kakaunti lamang ang mga katangian ng molekular na maaaring kalkulahin sa ganitong paraan. Sa kabilang banda, sa organikong kimika may mga mahahalagang problema sa istruktura na hindi pa ganap na nalutas, at higit sa lahat, ito ang problema ng relasyon sa pagitan ng istraktura at mga katangian ng mga molekula. Sa teoretikal na kimika, mayroong isang katanungan ng pagsukat ng mga pangunahing katangian ng istruktura ng mga molekula - ang kanilang pagsasanga at cyclicity. Ang tanong na ito ay mahalaga, dahil ang isang quantitative analysis ng mga pangkalahatang regularidad sa istraktura ng branched at cyclic molecule ay maaaring sa isang malaking lawak ay mailipat sa kanilang iba pang mga katangian. Sa ganitong paraan, posibleng mahulaan ang pagkakasunud-sunod ng isang pangkat ng mga isomeric compound ayon sa mga halaga ng mga katangian tulad ng katatagan, reaktibiti, parang multo at thermodynamic na mga katangian, atbp. Ito ay maaaring mapadali ang paghula ng mga katangian ng hindi pa na-synthesize. klase ng mga compound at ang paghahanap para sa mga istruktura "na may paunang natukoy na mga katangian. Sa kabila ng makabuluhang pagsisikap ay bukas pa rin at ang tanong ng rational coding ng kemikal na impormasyon para sa layunin ng mahusay na pag-iimbak at paggamit nito ng mga computer. Ang pinakamainam na solusyon ng isyung ito ay magkakaroon ng epekto sa pagpapabuti ng klasipikasyon at katawagan ng parehong mga organikong compound at ang mga mekanismo ng mga reaksiyong kemikal. sa mga dami na nagpapakita ng elektronikong istraktura na mas mahusay kaysa sa ordinal na numero ng elemento.

Bilang isang resulta, sa mga huling dekada, ang pagbuo ng mga bagong teoretikal na pamamaraan sa kimika, na pinagsama sa ilalim ng pangalan ng mathematical chemistry, ay pinasigla. Ang pangunahing lugar sa loob nito ay inookupahan ng mga topological na pamamaraan, na sumasalamin sa pinaka-pangkalahatang istruktura at geometriko na mga katangian ng mga molekula. Ang isa sa mga sangay ng topology, ang teorya ng graph, ay nag-aalok ng isang maginhawang wikang matematika para sa chemist upang ilarawan ang molekula, dahil ang mga pormula ng istruktura ay mahalagang mga graph ng kemikal. Ang mga kalamangan na inaalok ng teorya ng graph sa pananaliksik sa kemikal ay batay sa posibilidad ng direktang paggamit ng mathematical apparatus nito nang hindi gumagamit ng computer, na mahalaga para sa mga eksperimentong chemist. Ang teorya ng graph ay nagbibigay-daan sa isa na magsaliksik nang simple sa mga katangian ng istruktura ng mga molekula. Ang mga resultang nakuha ay pangkalahatan at maaaring bumalangkas bilang theorems o mga panuntunan at sa gayon ay maaaring ilapat sa anumang katulad na kemikal (at hindi kemikal) na mga bagay.

Matapos ang paglalathala ng mga pangunahing gawa ni Shannon at Wiener sa teorya ng impormasyon at cybernetics, ang interes sa impormasyon-teoretikong pamamaraan ng pananaliksik ay patuloy ding tumaas. Ang orihinal na kahulugan ng terminong "impormasyon" ay nauugnay sa impormasyon, mga mensahe at kanilang paghahatid. Ang konseptong ito ay mabilis na umalis sa mga limitasyon ng teorya ng komunikasyon at cybernetics at tumagos sa iba't ibang mga agham ng buhay at walang buhay na kalikasan, lipunan at katalusan. Ang proseso ng pagbuo ng information-theoretic approach sa agham ay mas kumplikado kaysa sa pormal na paglipat ng cybernetic na kategorya ng impormasyon sa ibang mga lugar ng kaalaman. Ang diskarte sa impormasyon ay hindi lamang isang pagsasalin mula sa hindi gaanong karaniwang mga wika sa isang metalanguage. Nag-aalok ito ng ibang view ng mga system at phenomena at nagbibigay-daan sa iyong makakuha ng mga bagong resulta. Sa pamamagitan ng pagpapalawak ng mga koneksyon sa pagitan, mabuti, iba't ibang mga disiplinang pang-agham, ginagawang posible ng pamamaraang ito na makahanap ng mga kapaki-pakinabang na pagkakatulad at karaniwang mga pattern sa pagitan ng mga niches. Ang pag-unlad, modernong agham ay may posibilidad sa isang mas mataas na antas ng paglalahat, sa pagkakaisa. Kaugnay nito, ang teorya ng impormasyon ay isa sa mga pinaka-promising na lugar.

Ang isang mahalagang lugar sa prosesong ito ay inookupahan ng aplikasyon ng teorya ng impormasyon sa kimika at iba pang natural na agham - physics, biology, atbp. Sa mga agham na ito, ang mga pamamaraan ng teorya ng impormasyon ay ginagamit sa pag-aaral at paglalarawan ng mga katangian ng mga bagay at proseso. na nauugnay sa istraktura, kaayusan, mga sistema ng organisasyon "Ang pagiging kapaki-pakinabang ng diskarte sa impormasyon sa kimika ay nakasalalay sa katotohanan na ang mga bagong posibilidad ay inaalok para sa dami ng pagsusuri ng iba't ibang aspeto ng mga istrukturang kemikal - mga atomo, molekula, kristal, atbp. Sa mga ito mga kaso, ang mga konsepto ng "istruktura" na impormasyon at "nilalaman ng impormasyon" ng mga atomo at molekula.

Kaugnay ng mga nabanggit, ang pangunahing layunin ng gawaing disertasyon ay maipakita ang pagiging mabunga ng graph-theoretic at information-theoretic approach sa mga problemang istruktural sa c. kimika, mula sa mga atomo at molekula hanggang sa mga polimer at kristal, ang pagkamit ng layuning ito ay kinabibilangan, bilang magkakahiwalay na mga hakbang:

1. Kahulugan ng isang sistema ng mga dami (impormasyon at topological na indeks; para sa quantitative characterization ng mga atomo, molekula, polimer at kristal.

2. Pag-unlad sa batayan na ito ng isang bago, mas pangkalahatang diskarte sa tanong ng ugnayan sa pagitan ng kanilang mga katangian, geometriko at elektronikong istraktura. Paghula ng mga katangian ng ilang mga organikong compound, polimer at hindi na-synthesize na mga elemento ng transactinide nMx.

Paglikha ng mga pamamaraan para sa pagmomodelo ng paglago ng mga kristal at mga bakante sa kristal.

3. Pangkalahatang topological na katangian ng mga molekula sa pamamagitan ng pagpapahayag ng kakanyahan ng kanilang pagsasanga at cyclicity sa isang serye ng mathematically proven na mga tuntuning istruktura, at ang pag-aaral ng pagmamapa ng mga panuntunang ito sa pamamagitan ng iba't ibang mga katangian ng molekular.

4. Paglikha ng mga bago, epektibong pamamaraan para sa pag-coding ng mga compound ng kemikal at mga mekanismo ng mga reaksiyong kemikal na may kaugnayan sa pagpapabuti ng kanilang pag-uuri at katawagan, at lalo na may kaugnayan sa paggamit ng mga computer para sa pagproseso ng impormasyong kemikal.

KABANATA 2. PARAAN NG PANANALIKSIK 2L. THEOREGIO-INSTRUCTION PARAAN 2.1.1 "Introduksyon

Ang impormasyon ay isa sa mga pinakapangunahing konsepto sa modernong agham, isang konsepto na hindi gaanong pangkalahatan kaysa sa mga konsepto ng bagay at enerhiya. Ang pananaw na ito ay nakakahanap ng katwiran sa mismong mga kahulugan ng impormasyon. Ayon kay Wiener, "ang impormasyon ay hindi bagay o enerhiya".

Tinitingnan ni Ashby ang impormasyon bilang isang "sukatan ng pagkakaiba-iba sa isang partikular na sistema". Ayon kay Glushkov, "ang impormasyon ay isang sukatan ng inhomogeneity sa pamamahagi ng espasyo at oras." Sa batayan na ito, ang katotohanan na bilang karagdagan sa likas na materyal at enerhiya, ang mga bagay at phenomena sa kalikasan at teknolohiya ay mayroon ding mga katangian ng impormasyon ay lalong kinikilala ngayon. Ang ilang mga pagtataya ay lumalabas nang higit pa, na hinuhulaan na ang pokus ng siyentipikong pananaliksik ay lalong lilipat patungo sa pagiging impormasyon ng mga proseso, na magiging pangunahing layunin ng pananaliksik sa ika-21 siglo. Ang mga pagtataya na ito ay mahalagang batay sa posibilidad ng pinakamainam na kontrol ng mga sistema at proseso sa pamamagitan ng impormasyon, ano, sa katunayan? ay ang pangunahing tungkulin ng impormasyon sa cybernetics. Sa hinaharap, ang mga ideyang ito ay maaaring humantong sa paglikha ng mga teknolohiya kung saan ang bawat atom at molekula ay makokontrol ng impormasyon, isang posibilidad na nakatagpo ng pagsasakatuparan sa ngayon lamang sa buhay na kalikasan.

Ang paglitaw ng teorya ng impormasyon ay karaniwang tumutukoy sa 1948, nang inilathala ni Claude Shannon ang kanyang pangunahing gawain. Ang ideya ng impormasyon, gayunpaman, bilang isang dami na nauugnay sa entropy, ay mas matanda. Noong 1894, itinatag ni Boltzmann na ang anumang impormasyong nakuha tungkol sa isang partikular na sistema ay nauugnay sa pagbaba sa bilang ng mga posibleng estado nito at, samakatuwid, ang pagtaas sa entropy ay nangangahulugang "pagkawala ng impormasyon." Noong 1929

Binuo ni Szilard ang ideyang ito para sa pangkalahatang kaso ng impormasyon sa pisika. ang CP niya

Nang maglaon, si Vrilluin ay "nag-generalize ng ideya ng relasyon sa pagitan ng entropy at impormasyon sa kanyang non-gentropic na prinsipyo sa isang form na sumasaklaw din sa informational side ng phenomena. Ang mga tanong tungkol sa koneksyon sa pagitan ng teorya ng impormasyon at thermodynamics, at, sa partikular, tungkol sa relasyon sa pagitan ng entropy at impormasyon, ay pinagtutuunan pa rin ng pansin (isang detalyadong listahan ng mga publikasyon sa lugar na ito ay ibinigay sa pagsusuri 58). Mula sa pinakahuling pag-unlad ng isyu, ang gawain ni Kobozev sa thermodynamics ng pag-iisip ay dapat na lalo na napapansin, kung saan ang thesis tungkol sa antientropic na kalikasan ng mga proseso ng pag-iisip ay napatunayan.

Ang teorya ng impormasyon na lumitaw bilang isang "espesyal na teorya ng komunikasyon" ay mabilis na lumampas sa orihinal na mga limitasyon nito at natagpuan ang aplikasyon sa iba't ibang larangan ng agham at teknolohiya: sa kimika, biology, medisina, linggwistika, sikolohiya, aesthetics, atbp. Ang papel ng impormasyon sa ang biology ay kinilala una sa lahat. Nalutas mo ba ang mahahalagang isyu na may kaugnayan sa pag-iimbak, pagproseso at paghahatid ng impormasyon sa mga buhay na organismo, kabilang ang coding ng genetic na impormasyon 60-7? pagtatasa ng posibilidad ng kusang pagbuo ng buhay sa Earth^, pagbabalangkas ng mga pangunahing batas ng biological thermodynamics^, pagsusuri ng mga isyu sa bioenergy, atbp. Ang nilalaman ng impormasyon ng mga bagay ay ginamit bilang isang quantitative criterion

A A A evolution ". Itinaas ang tanong tungkol sa likas na impormasyon ng mga proseso ng nutrisyon ^®^^.

Ang teorya ng impormasyon ay dahan-dahan pa ring tumagos sa kimika at pisika, bagama't may ilang pag-unlad sa larangang ito sa mga nakalipas na taon. Ang tanong ay itinaas tungkol sa posibleng pagkakaroon ng balanse ng impormasyon ng mga reaksiyong kemikal. Ang isang pagtatasa ay ginawa ng kapasidad ng impormasyon ng mga bioorganic na molekula at, sa batayan na ito, ang isang bagong pag-uuri ng mga compound na ito ay iminungkahi, at ang pagtitiyak ng mga reaksiyong kemikal ay nasuri din.

Sina Levin, Bernstein, at iba pa ay naglapat ng teorya ng impormasyon sa molecular dynamics upang ilarawan ang pag-uugali ng mga molecular system na malayo sa equilibrium. Ang kakanyahan ng diskarteng ito ay ang konsepto ng isang "sorpresa", isang paglihis mula sa inaasahan batay sa microcanonical distribution. Ang iba't ibang mga aplikasyon ay iminungkahi, kabilang ang pag-aaral ng pagganap ng mga laser, ang pagpapasiya ng sumasanga na ratio ng mga nakikipagkumpitensya na mga landas ng reaksyon (ipagpalagay na ang landas na tumutugma sa maximum ng Shannon function bilang ang pinaka-malamang), at iba pa.

Iminungkahi ni Dodel et al. na ipamahagi ang espasyong inookupahan ng isang molecular system sa isang bilang ng magkahiwalay na mga subspace na tinatawag na lodge. Ang pinakamahusay na mga lodge na naglalaman ng mga naisalokal na grupo ng mga electron ay matatagpuan sa pamamagitan ng pagliit ng function ng impormasyon. Nakahanap si Sears et al ng koneksyon sa pagitan ng quantum mechanical kinetic energies at mga dami ng impormasyon. Bilang kinahinatnan ng resultang ito, ang variational na prinsipyo ng quantum mechanics ay maaaring mabalangkas bilang prinsipyo ng minimum na impormasyon. op os

Iniuugnay ni Kobozev et al ang selectivity at aktibidad ng mga catalyst sa kanilang nilalamang impormasyon. Bumalangkas din sila ng pinakamainam na kondisyon ng impormasyon para sa pagkilala at paghula ng mga katangian ng catalytic. Pagbuo at paglaki ng kris

Ouch. rp oo tall ay itinuturing bilang isang proseso ng impormasyon”. Sumailalim si Rakov sa pagsusuri ng impormasyon sa paggamot ng mga ibabaw ng katalista na may iba't ibang mga ahente ng kemikal.

Sa modernong analytical chemistry, mayroong tumataas na kalakaran patungo sa pinakamainam na eksperimento upang makakuha ng maximum na impormasyon mula sa pinakamababang bilang ng mga eksperimento.

Ang mga bagong ideyang ito ay batay sa teorya ng impormasyon, teorya ng laro at teorya ng system. Ang ibang mga may-akda ay naglapat ng teorya ng impormasyon upang mabawasan ang error sa pagsusuri at oras, upang makamit ang mas mataas na pagpili, upang suriin ang pagiging epektibo ng mga pamamaraan ng analitikal, at iba pa. Kasama rin sa pananaliksik sa ganitong uri ang mga pisikal na pamamaraan sa analytical chemistry, kabilang ang gas chromatography, atomic emission spectral analysis, atbp.

Ang mga pamamaraang teoretikong impormasyon ay napatunayang kapaki-pakinabang din sa geochemistry para sa pagkilala sa dalas ng pamamahagi ng mga kemikal na compound sa mga geochemical system,170 para sa pagtatasa ng antas ng pagiging kumplikado at para sa pag-uuri ng mga sistemang ito.

Sa engineering chemistry, ang pagsusuri ng impormasyon ay maaaring gamitin upang malutas ang mga problema ng kemikal-teknolohiyang sistema bilang pagpili ng pinakamainam na kondisyon sa pagpapatakbo, ang pagtatatag ng mga kinakailangan sa kontrol, atbp.101.

Ang mga halimbawa ng matagumpay na aplikasyon ng teorya ng impormasyon sa kimika ay muling nagpapahiwatig na ang mga sistema sa kalikasan at teknolohiya ay mayroon ding likas na impormasyon. Ipinapakita rin nito na ang diskarte sa impormasyon ay gumaganap bilang isang unibersal na wika para sa paglalarawan ng mga sistema, at, sa partikular, mga istrukturang kemikal ng anumang uri, kung saan iniuugnay nito ang isang tiyak na function ng impormasyon at isang numerical na sukat. Lumalawak ito. larangan ng mga posibleng aplikasyon ng teorya ng impormasyon sa kimika.

Ang pagiging kapaki-pakinabang ng diskarte sa impormasyon sa kimika ay pangunahin na nag-aalok ito ng posibilidad ng quantitative analysis ng iba't ibang aspeto ng mga istrukturang kemikal. Ang antas ng pagiging kumplikado ng mga istrukturang ito, ang kanilang organisasyon at pagtitiyak ay maihahambing sa isang solong sukat ng dami. Nagbibigay-daan ito sa isang tao na pag-aralan ang ilan sa mga pinaka-pangkalahatang katangian ng mga istrukturang kemikal, tulad ng pagsasanga at paikot ng mga ito, upang siyasatin at ihambing ang antas ng organisasyon sa iba't ibang klase ng mga compound ng kemikal, ang pagtitiyak ng mga biologically active substance at catalyst, at pinapayagan ang isa na lapitan ang tanong ng antas ng pagkakapareho at pagkakaiba sa pagitan ng dalawang bagay na kemikal.

Ang diskarte sa impormasyon ay napaka-angkop para sa paglutas ng mga problema sa personal na pag-uuri. Sa mga kasong ito, posibleng makakuha ng mga pangkalahatang equation ng impormasyon para sa mga pangunahing pagpapangkat ng mga bagay ng pag-uuri (mga grupo at panahon sa Periodic system ng mga elemento ng kemikal, homologous na serye ng mga kemikal na compound, serye ng mga isomeric compound, atbp.) *

Ang mahusay na pagkilala sa kakayahan ng mga pamamaraan ng impormasyon na may paggalang sa mga kumplikadong istruktura (isomer, isotopes, atbp.) ay maaaring gamitin sa computerized processing at storage ng kemikal na impormasyon. Ang mga pamamaraan na ito ay kapaki-pakinabang hindi lamang kapag pumipili sa pagitan ng iba't ibang mga istraktura, kundi pati na rin sa pagitan ng mga alternatibong hypotheses at mga pagtatantya, na interesado para sa quantum chemistry. Ang mga posibilidad ng paglalagay ng mga bagong hypotheses batay sa teorya ng impormasyon, gayunpaman, ay mas limitado, dahil ang teoryang ito ay naglalarawan ng relasyon sa pagitan ng mga variable, ngunit hindi naglalarawan ng pag-uugali ng alinman sa mga ito.

Problema. Ang relasyon na umiiral sa pagitan ng istraktura at mga katangian ay isa pang lugar ng matagumpay na aplikasyon ng diskarte sa teorya ng impormasyon sa kimika. Ang pagiging epektibo ng diskarteng ito ay ipapakita sa isang dissertation work para sa qualitatively different structural levels sa chemistry - mga electron shell ng atoms, molecules, polymers, crystals at kahit atomic nuclei^»^. Maaari itong ipatupad sa parehong mga aspeto ng husay at dami. Sa unang kaso, ang iba't ibang mga patakaran sa istruktura ay maaaring tukuyin sa batayan ng impormasyon, na sumasalamin sa magkaparehong impluwensya ng dalawa o higit pang mga kadahilanan sa istruktura. Posible rin na makakuha ng quantitative correlations sa pagitan ng mga indeks ng impormasyon at mga katangian?®. Kasabay nito, sa prinsipyo, ang mga indeks ng impormasyon ay nagbibigay ng mas mahusay na mga ugnayan kumpara sa iba pang mga indeks, dahil mas ganap nilang sinasalamin ang mga tampok ng mga istrukturang kemikal. Ang mga matagumpay na ugnayan ay posible hindi lamang sa mga dami na direktang nauugnay sa entropy, kundi pati na rin sa mga dami tulad ng nagbubuklod na enerhiya, na ang kaugnayan sa impormasyon ay malayo sa halata. Dito, ang mga katangian ay kasama bilang isang hiwalay na molekula "o atom, ngunit gayundin ang kanilang malalaking pinagsama-samang, ibig sabihin, mga katangian na nakasalalay sa pakikipag-ugnayan sa pagitan ng mga molekula at mga atomo, at hindi lamang sa kanilang panloob na istraktura. Bilang karagdagan., Ang mga proseso sa kimika ay maaari ding maging ang paksa ng pagsusuri ng impormasyon batay sa mga pagbabago sa mga indeks ng impormasyon sa panahon ng mga pakikipag-ugnayan.

Ang ilang mga limitasyon ng diskarte sa impormasyon ay dapat ding isaisip. Bagama't ang mga ito ay .ton, ang mga sukat ng dami ng impormasyon ay kamag-anak, hindi ganap. Ang mga ito ay mga istatistikal na katangian din at tumutukoy sa mga pinagsama-samang, ngunit hindi sa mga indibidwal na elemento ng mga ito. Ang mga indeks ng impormasyon ay maaaring tukuyin para sa iba't ibang katangian ng mga atomo at molekula, ngunit ang ugnayan sa pagitan ng mga ito ay kadalasang kumplikado at implicit.

Sa kabilang banda, ang pagkakaroon ng maramihang mga index ng impormasyon para sa isang istraktura ay maaaring magdulot ng magkahalong damdamin. Gayunpaman, dapat tandaan na ang alinman sa mga index na ito ay legal. Ang tamang tanong dito ay kung alin sa mga dami na ito ang kapaki-pakinabang at hanggang saan.

Sa kabanatang ito, sa unang pagkakataon, ipinakilala ang mga indeks ng teoretikal na impormasyon:, / na nagpapakilala sa elektronikong istruktura ng mga atomo, pati na rin ang mga bagong indeks ng impormasyon tungkol sa simetrya, topolohiya, at elektronikong istruktura ng mga molekula. Ang paglalapat ng mga katangiang ito sa istruktura ay tinalakay sa kabanata III, mga seksyon IV.2 at V 1.

2.1.2. Mga kinakailangang impormasyon mula sa teorya ng impormasyon

Ang teorya ng impormasyon ay nag-aalok ng quantitative na pamamaraan para sa pag-aaral ng pagkuha, pag-iimbak, paghahatid, pagbabago at paggamit ng impormasyon. Ang pangunahing lugar sa mga pamamaraang ito ay inookupahan ng dami ng pagsukat ng impormasyon.Ang kahulugan ng konsepto ng dami ng impormasyon ay nangangailangan ng pagtanggi sa laganap, ngunit hindi malinaw na mga ideya tungkol sa impormasyon bilang isang pinagsama-samang, katotohanan, impormasyon, kaalaman.

Ang konsepto ng dami ng impormasyon ay malapit na nauugnay sa konsepto ng entropy bilang isang sukatan ng kawalan ng katiyakan. Noong 1923, inilarawan ni Hartley ang kawalan ng katiyakan ng isang eksperimento na may n magkakaibang kinalabasan sa pamamagitan ng bilang na ¿od n. Sa istatistikal na teorya ng impormasyon ni Shannon, na inilathala noong 1948, ang dami ng impormasyon ay tinukoy sa pamamagitan ng konsepto ng posibilidad. Ito ay kilala na ang konseptong ito ay ginagamit upang ilarawan ang isang sitwasyon kung saan may kawalang-katiyakan na nauugnay sa pagpili ng isa o higit pang mga elemento (kinalabasan) mula sa isang tiyak na hanay. Kasunod ni Shannon, ang sukat ng kawalan ng katiyakan ng kinalabasan X/eksperimento X na may posibilidad na p(X¡) -¿Oy(X)) . Isang sukat ng average na kawalan ng katiyakan ng kumpletong eksperimento X na may Xt, X2, ♦ posibleng mga resulta, na may probabilities p(X4), p(X2), ayon sa pagkakabanggit. chp(Xn), ay ang dami

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

Sa statistical information theory H(X) ay tinatawag na entropy ng probability distribution. Ang huli, sa kaso ng /7 iba't ibang mga kinalabasan, ay bumubuo ng isang may hangganang probabilistic scheme, i.e.

Ang konsepto ng probabilidad ay maaaring tukuyin sa isang mas pangkalahatang paraan mula sa punto ng view ng set theory. Hayaang ang isang finite set ay isang partition ng A sa isang /T) class kung saan ang /\ ay magkahiwalay na set; sa pamamagitan ng ilang equivalence relation X * Set ng equivalence classes

R/X = (2.2; ay tinatawag na factor set R sa X

Ang probability function ng Kolmogorov (probabilistic correspondence) p ay napapailalim sa tatlong kundisyon:

Ang serye ng numero na PfXf) , P(X2) , ., P(XGG)) ay tinatawag na pamamahagi ng partition A, at ang Shannon function na H(X) mula sa Eq. (2.1) ay nagpapahayag ng entropy ng partition X

Dapat itong isipin na ang konsepto ng entropy sa teorya ng impormasyon ay mas pangkalahatan kaysa sa thermodynamic entropy. Ang huli, na itinuturing bilang isang sukatan ng kaguluhan sa atomic-molecular motions, ay isang espesyal na kaso ng isang mas pangkalahatang konsepto ng entro-! Ang FDI ay ang sukatan ng anumang kaguluhan o kawalan ng katiyakan o pagkakaiba-iba.

Ang halaga ng impormasyon X ay ipinahayag ng halaga ng hiwalay na kawalan ng katiyakan. Pagkatapos, ang average na entropy ng isang partikular na kaganapan na may maraming posibleng resulta ay katumbas ng average na dami ng impormasyong kailangan upang pumili ng anumang kaganapan X mula sa set ^ ,X^,. at tinutukoy ng formula ng Shannon (y-e 2.1):

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

Narito ang K ay isang positibong pare-pareho na tumutukoy sa mga yunit ng pagsukat ng impormasyon. Sa pag-aakalang K \u003d 4, ang entropy (ayon sa pagkakabanggit, impormasyon) ay sinusukat sa mga yunit ng decimal. Ang pinaka-maginhawang sistema ng pagsukat ay batay sa mga binary unit (bit). Sa kasong ito, Ang K ~ W2 at ang logarithm wur-u(2.4) ay kinuha sa base two at ang \-! ay tinutukoy ng t para sa maikli. Ang isang binary unit ng impormasyon (o 1 bit) ay ang dami ng impormasyon na nakukuha kapag ang resulta ng ang pagpili sa pagitan ng dalawang magkatulad na posibilidad ay alam, at sa mga yunit ng entropy,¿ .dgasG\ ang conversion factor ay ang Voltzmann constant (1.38.10 yj.gra.d~divided by /a?Yu.

Ito ay pinatunayan na ang pagpili ng logarithmic function para sa dami ng impormasyon ay hindi random, at ito ang tanging function na nakakatugon sa mga kondisyon ng aktibidad at non-negatibiti ng impormasyon.

Parehong single at average na impormasyon ay palaging positibo. Ang pag-aari na ito ay nauugnay sa katotohanan na ang posibilidad ay palaging mas mababa sa isa, at ang pare-pareho sa equation (2.4) ay palaging itinuturing na positibo. E | & ring ^ Y, pagkatapos

13 p(x, -) = H(x, o c2.5) at ang hindi pagkakapantay-pantay na ito ay napanatili kahit na matapos ang pag-average.

Ang average na dami ng impormasyon para sa isang naibigay na kaganapan (karanasan) X ay umabot sa maximum na may pare-parehong distribusyon ng mga probabilidad p(X,) - p(X2) = . . .=p(Xn)* i.e. para sa p(X)) para sa anumang P:

Para sa isang pares ng random na umaasa na mga kaganapan X at y, ang average na dami ng impormasyon ay ipinahayag din ng formula ng Shannon:

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

Ang equation (2.7) ay maaaring gawing pangkalahatan para sa anumang finite set, anuman ang katangian ng mga elemento nito:

1(xy) = -Z Z. Ang P(X,nYj) 16P(X-,nYj) (2.8) ay dalawang quotient set ng P na may kinalaman sa dalawang magkaibang equivalence relations x at y, at ang K/xy ay isang factor- hanay ng mga seksyon ng X; at:

Ang pagkakaroon ng nakasulat na magkasanib na probabilidad sa equation (2.7) bilang produkto ng unconditional at conditional probabilities p(x;, y^ = p(><¡)"P(Уj/x¡) , и представив логарифм в виде сумш»получается уравнение:

1(Xy) = 1(X) x - 1(y/X) (2.9) kung saan ang T(x/y) ay ang average na dami ng conditional na impormasyon na nilalaman sa y kaugnay ng x, at ibinibigay ng:

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

Pagtukoy sa isang function:

1 (X, y.! = 1 (Y> - 1 (y / X)) (2-Sh at pinapalitan ito sa equation (2.9):

1(xy) - 1(X) + 1(y) -1(x, y) (2.12) nagiging malinaw na ang T(X, y) ay nagpapahayag ng paglihis ng impormasyon tungkol sa kumplikadong kaganapan (X, y") mula sa ang additivity ng impormasyon tungkol sa mga indibidwal na kaganapan (mga kinalabasan): x at y. Samakatuwid, ang G (X, Y) ay isang sukatan ng antas ng statistical dependence (koneksyon) sa pagitan ng X at y. Ang relasyon sa pagitan ng x at y3 ay simetriko.

Sa pangkalahatang kaso, para sa isang istatistikal na relasyon sa pagitan ng x at y at ang average na dami ng walang kondisyong impormasyon tungkol sa X o y, ang mga sumusunod na hindi pagkakapantay-pantay ay nananatili:

Pagkakapantay-pantay sa kapangyarihan kapag ang pangalawang termino sa equation (2.11) ay zero, i.e. kapag ang bawat / ay tumutugma sa I kung saan p(y. ¡X))=

Kung ang mga dami ng X at y ay independyente, i.e. kung sa equation (2.12) T (X, y) \u003d 0, kung gayon

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

Ang equation na ito ay nagpapahayag ng pag-aari ng additivity ng dami ng impormasyon at ito ay pangkalahatan para sa mga independiyenteng random na variable. pumapasok sa isip ko:

1(xnx2,.,xn) = 11 1(x/) (2.16)

Ang mga probabilistic approach sa quantitative determination ng impormasyon ay kilala rin. Ingarden at Urbanich ay nagmungkahi ng isang axiomatic/sizvdelenie-Shein na impormasyon na walang probabilidad, sa anyo ng isang function ng mga may hangganang Boolean ring. Ang malaking interes ay ang epsilon-entropy (combinatorial approach) na iminungkahi ni Kolmogorov^^ at lalo na ang algorithmic na pagpapasiya ng dami ng impormasyon. Ayon kay Kolmogorov, ang dami ng impormasyon na nakapaloob sa isang bagay (set) na may kaugnayan sa isa pang bagay (set) ay itinuturing na "minimum na haba" ng mga programa, na nakasulat bilang isang pagkakasunud-sunod ng mga zero at isa, at pinapayagan ang isa-sa-isa. pagbabagong-anyo; ang unang bagay sa pangalawa:: \u003d H (X / y) \u003d W "W I (R) (2-17)

Ang algorithmic na diskarte ng Kolmogorov ay nag-aalok ng bago

17 lohikal na pundasyon ng teorya ng impormasyon batay sa mga konsepto ng pagiging kumplikado at pagkakasunud-sunod, ang mga takcha&Yn-concept na "entropy" at "dami ng impormasyon" ay naging naaangkop sa mga indibidwal na bagay.

Ang mga hindi kapani-paniwalang pamamaraan sa teorya ng impormasyon ay nagpapalawak ng nilalaman ng konsepto ng dami ng impormasyon mula sa halaga ng nabawasang kawalan ng katiyakan hanggang sa halaga ng nabawasang pagkakapareho o sa dami ng pagkakaiba-iba alinsunod sa interpretasyon ni Ashby. Anumang hanay ng mga probabilidad na na-normalize sa pagkakaisa ay maaaring ituring na tumutugma sa isang tiyak na hanay ng mga elemento na nagtataglay ng pagkakaiba-iba. Ang pagkakaiba-iba ay nauunawaan bilang isang katangian ng mga elemento ng isang set, na binubuo sa kanilang pagkakaiba, hindi nagkataon na may paggalang sa ilang kaugnayan ng pagkakapareho. Ito @ ay maaaring isang set ng "iba't ibang elemento, relasyon, relasyon, katangian ng mga bagay. Ang pinakamaliit na yunit ng impormasyon, medyo, sa diskarteng ito ay nagpapahayag ng pinakamababang pagkakaiba, ibig sabihin, ang pagkakaiba sa pagitan ng dalawang bagay na hindi magkapareho, naiiba sa ilang ari-arian.

Sa aspetong ito, ang mga pamamaraang teoretikong impormasyon ay naaangkop sa kahulugan ng tinatawag na. structural information ay ang dami ng impormasyong nakapaloob sa istruktura ng isang ibinigay na sistema. Ang istraktura dito ay nangangahulugang anumang finite set na ang mga elemento ay ipinamamahagi sa mga subset (equivalence classes) depende sa isang partikular na equivalence relation.

Hayaang maglaman ang istrukturang ito ng mga elementong A/ at ang mga ito ay ibinahagi ayon sa ilang pamantayan ng katumbas sa mga subset ng mga katumbas na elemento: . Ang distribusyon na ito ay tumutugma sa isang finite probabilistic scheme ng probability subset ^ pn p2> . . ?Rp elemento

2.18) kung saan ang ¿T - A/"u ay ang posibilidad ng isang (random) na napiling elemento na mahulog sa / - na subset kung saan A/,-mga elemento. Ang entropy H ng probability distribution ng mga elemento ng istrukturang ito, ay tinutukoy sa pamamagitan ng equation (2.4), maaaring isaalang-alang / bilang isang sukatan ng average na dami ng impormasyon, I, na nakapaloob sa isang elemento ng istraktura: - p

1u P/ , mga bit bawat elemento (2.19)

Ang pangkalahatang impormasyon na nilalaman ng istraktura ay ibinibigay ng derivative equation (2.19):

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

Walang pinagkasunduan sa panitikan tungkol sa kung paano pangalanan ang mga dami na tinukoy ng y-y (2.19) at (2.20). Mas gusto ng ilang may-akda na tukuyin ang mga ito bilang karaniwan at pangkalahatang nilalaman ng impormasyon, ayon sa pagkakabanggit. Kaya, ayon kay Moushowitz, hindi ako isang sukatan ng entropy sa diwa kung saan ito ginagamit sa teorya ng impormasyon, dahil hindi nito ipinapahayag ang karaniwang kawalan ng katiyakan ng isang istraktura na binubuo ng /\/ mga elemento sa isang grupo ng lahat ng posibleng mga istruktura na may pareho: ang bilang ng mga elemento. Ako ay sa halip ang nilalaman ng impormasyon ng istraktura na isinasaalang-alang kaugnay sa sistema ng mga pagbabagong-anyo na nag-iiwan sa system na walang pagbabago. Ayon kay Rem mula sa equation (2.4) sinusukat ang dami ng impormasyon pagkatapos ng eksperimento, at bago nito ang H(x) ay isang sukatan ng entropy na nauugnay sa kawalan ng katiyakan ng eksperimento. Sa aming opinyon, ang isang "eksperimento" na nagbabawas sa kawalan ng katiyakan ng mga istrukturang kemikal (mga atomo, molekula, atbp.) ay mismong "ang proseso ng pagbuo ng mga istrukturang ito mula sa kanilang mga hindi nauugnay na elemento. Ang impormasyon ay narito sa isang konektadong anyo, ito ay nakapaloob sa isang istraktura, at samakatuwid ay madalas ang terminong "nilalaman ng impormasyon" ng istraktura ay ginagamit.

Ang konsepto ng istrukturang impormasyon batay sa ibinigay na interpretasyon1 ng mga equation (2.19) at (2.20) ay lubos na sumasang-ayon sa mga ideya ni Ashby tungkol sa dami ng impormasyon bilang dami ng pagkakaiba-iba. Kapag ang isang sistema ay binubuo ng parehong mga elemento, walang pagkakaiba-iba dito. Sa kasong ito, sa y-s (2.19) at (2.20)/="/

Sa maximum na iba't ibang mga elemento sa istraktura, Λ £ = /, at ang nilalaman ng impormasyon ng istraktura ay maximum:

4 "* -N16 u, T ^^ vi

2.1.3. Impormasyon-teoretikal na mga indeks para sa pagkilala sa elektronikong istraktura ng mga atomo ng mga elemento ng kemikal

Inirerekomendang listahan ng mga disertasyon sa espesyalidad na "Organic Chemistry", 02.00.03 VAK code

• Asymptotic na problema ng combinatorial coding theory at information theory 2001, Kandidato ng Physical at Mathematical Sciences Vilenkin, Pavel Alexandrovich2011, kandidato ng pisikal at matematikal na agham Shutkin, Yuri Sergeevich

Pakitandaan na ang mga siyentipikong teksto na ipinakita sa itaas ay nai-post para sa pagsusuri at nakuha sa pamamagitan ng orihinal na dissertation text recognition (OCR). Kaugnay nito, maaaring maglaman ang mga ito ng mga error na nauugnay sa di-kasakdalan ng mga algorithm ng pagkilala. Walang ganoong mga error sa mga PDF file ng mga disertasyon at abstract na inihahatid namin.

Ang mga graph ay nagsisilbi, una sa lahat, bilang isang paraan ng kumakatawan sa mga molekula. Sa topological na paglalarawan ng isang molekula, ito ay inilalarawan bilang isang molecular graph (MG), kung saan ang mga vertices ay tumutugma sa mga atomo, at ang mga gilid ay tumutugma sa mga kemikal na bono (graph-theoretic na modelo ng isang molekula). Karaniwan, ang mga skeletal atom lamang ang isinasaalang-alang sa representasyong ito, halimbawa, mga hydrocarbon na may "binura" na mga atomo ng hydrogen.

Ang lakas ng mga elemento ng kemikal ay nagpapataw ng ilang mga paghihigpit sa mga antas ng vertices. Ang mga puno ng alkane (mga konektadong graph na walang mga cycle) ay may vertex degrees (r) na hindi maaaring lumampas sa apat (r = 1, 2, 3, 4).

Maaaring tukuyin ang mga graph sa matrix form, na maginhawa kapag nagtatrabaho sa kanila sa isang computer.

Ang vertex adjacency matrix ng isang simpleng graph ay isang square matrix A = [aσχ] na may mga elemento aσχ = 1 kung ang vertex σ at χ ay konektado sa pamamagitan ng isang gilid, at σχ = 0 kung hindi man. Ang distance matrix ay isang square matrix D = na may mga elementong dσχ na tinukoy bilang ang pinakamababang bilang ng mga gilid (ang pinakamaikling distansya) sa pagitan ng mga vertices σ at χ. Minsan ginagamit din ang adjacency at edge distance matrice (A e at D e).

Ang uri ng mga matrice A at D (A e at D e) ay depende sa paraan ng pagbibilang ng mga vertice (o mga gilid), na nagdudulot ng abala kapag hinahawakan ang mga ito. Upang makilala ang isang graph, ginagamit ang mga invariant ng graph - mga topological index (TI).

Bilang ng mga landas ng isang haba

pi = xcc 0 = m = n-1

Bilang ng mga landas na may haba na dalawa

Bilang ng triplets ng mga katabing gilid (na may karaniwang vertex)

Ang numero ng Wiener (W), na tinukoy bilang kalahating kabuuan ng mga elemento ng distance matrix ng graph na isinasaalang-alang:

atbp.

Kasama sa pamamaraan para sa pag-aaral ng ugnayang "structure-property" sa pamamagitan ng topological index sa graph-theoretic approach ang mga sumusunod na hakbang.

Pagpili ng mga bagay ng pag-aaral (sample ng pagsasanay) at pagsusuri ng estado ng numerical data sa property P para sa isang partikular na hanay ng mga compound.

Pagpili ng mga TI na isinasaalang-alang ang kanilang kakayahang makita ang kaibhan, kakayahang makipag-ugnayan sa mga katangian, atbp.

Ang pag-aaral ng mga graphical na dependency na "Property P - TI ng graph ng molekula", halimbawa, P on n - ang bilang ng mga skeletal atoms, P on W - ang Wiener number, atbp.

Pagtatatag ng functional (analytical) dependence P = _DTI), halimbawa,

P \u003d a (TI) + b,

P \u003d aln (TI) + b,

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

atbp. Narito ang a, b, c ay ilang mga parameter (hindi dapat ipagkamali sa mga parameter ng mga additive circuit.) upang matukoy.

Mga numerical na kalkulasyon ng Р, paghahambing ng mga kinakalkula na halaga sa mga pang-eksperimentong.

Paghula ng mga katangian ng mga compound na hindi pa napag-aaralan o kahit na nakuha (sa labas ng sample na ito).

Ang mga topological na indeks ay ginagamit din sa pagbuo ng mga additive na pagkalkula at mga scheme ng pagtataya. Magagamit ang mga ito sa pagbuo ng mga bagong gamot, sa pagtatasa sa aktibidad ng carcinogenic ng ilang mga kemikal, sa paghula ng kamag-anak na katatagan ng mga bagong (hindi pa synthesize) na mga compound, atbp.

Gayunpaman, dapat tandaan na ang pagpili ng TI ay madalas na random; maaaring hindi ito sumasalamin sa mahahalagang katangian ng istruktura ng mga molekula o duplicate na impormasyon (nakuha sa tulong ng iba pang mga indeks), at ang mga scheme ng pagkalkula ay maaaring walang matatag na teoretikal na pundasyon at mahirap bigyang-kahulugan sa pisikal na kemikal.

Ang pangkat ng Department of Physical Chemistry ng TvSU ay nagsasagawa ng computational-theoretical na pag-aaral sa problemang "Relasyon sa pagitan ng mga katangian ng mga sangkap at istraktura ng mga molekula: pagmomolde ng matematika (computer)" sa loob ng maraming taon. Ang pokus ay sa target na paghahanap para sa mga bagong istruktura, mga algorithm para sa paglutas ng isang bilang ng mga graph-theoretical at combinatorial na mga problema na lumitaw sa kurso ng pagkolekta at pagproseso ng impormasyon tungkol sa istraktura at mga katangian ng mga sangkap, paglikha ng mga dalubhasang sistema ng pagkuha ng impormasyon at mga database, pagbuo quantitative na paraan ng pagkalkula at pagtataya.

Nakagawa kami ng mga additive scheme at nakahanap ng analytical dependences ng form na P = Y(TI) para sa isang bilang ng mga organic at iba pang molecule. Ayon sa nakuha na mga formula, ang mga numerical na kalkulasyon ng mga katangian ng physicochemical ng mga compound na isinasaalang-alang ay isinagawa, s.

Bibliograpiya

1. Vinogradova M.G., Papulov Yu.G., Smolyakov V.M. Dami ng mga ugnayan ng "pag-aari ng istruktura" ng mga alkanes. Additive na mga scheme ng pagkalkula. Tver, 1999. 96 p.
2. Mga Chemical Application ng Topology at Graph Theory / Ed. R. Hari. M.: Mir, 1987. 560 p.
3. Paglalapat ng Graph Theory sa Chemistry / Ed. N.S. Zefirov at S.I. Kuchanova. Novosibirsk: Nauka, 1988. 306 p.
4. Stankevich M.I., Stankevich I.V., Zefirov N.S. Topological index sa organic chemistry // Uspekhi khimii. 1988. V.57, No. 3, S.337-366.
5. Vinogradova M.G., Saltykova M.N. Graph-theoretic approach sa pag-aaral ng relasyon sa pagitan ng structure at properties ng alkylsilanes.// Fundamental Research, 2009. No. 1. pp. 17-19.
6. Vinogradova M.G., Saltykova M.N., Efremova A.O., Malchevskaya O.A. Ang ugnayan sa pagitan ng istraktura at mga katangian ng alkylsilanes // Mga tagumpay ng modernong natural na agham, No. 1, 2010. P. 136-137.
7. Vinogradova M.G., Saltykova M.N., Efremova A.O. Mga Kaugnayan "Istruktura - pag-aari" ng alkylsilanes: graph-theoretic approach // Mga tagumpay ng modernong natural na agham, No. 3, 2010. P.141-142.

Bibliographic na link

MUNICIPAL AUTONOMOUS GENERAL EDUCATIONAL INSTITUTION SECONDARY EDUCATIONAL SCHOOL № 2

Inihanda

Legkokonets Vladislav, 10A na estudyante

Praktikal na aplikasyon ng Graph Theory

Superbisor

L.I. Noskova, guro ng matematika

st.Bryukhovetskaya

2011

1. Panimula…………………………………………………………………………………….3

2. Ang kasaysayan ng pag-usbong ng teorya ng graph………………………………………………………………..4

3. Mga pangunahing kahulugan at teorema ng teorya ng graph………………………………………….……6

4. Nalutas ang mga gawain sa tulong ng mga graph……………………………………………………………………..8

4.1 Mga kilalang gawain…………………………………………………………………………8

4.2 Ilang mga kawili-wiling gawain………………………………………………………..9

5. Paglalapat ng mga graph sa iba't ibang larangan ng buhay ng mga tao…………………………………………11

6. Paglutas ng problema……………………………………………………………………………………12

7. Konklusyon………………………………………………………………………………………….13

8. Listahan ng mga sanggunian…………………………………………………………………………………………………………………… ………………………………………………………………………………………………………………………………… …………………………………………………………………………………………………………….

9.Apendise…………………………………………………………………………………………15

Panimula

Ipinanganak sa paglutas ng mga puzzle at nakakaaliw na laro, ang teorya ng graph ay naging simple, naa-access at mahusay na tool para sa paglutas ng mga problemang nauugnay sa malawak na hanay ng mga problema. Ang mga graph ay literal na nasa lahat ng dako. Sa anyo ng mga graph, maaaring isa, halimbawa, bigyang-kahulugan ang mga diagram ng kalsada at mga de-koryenteng circuit, mga mapa ng heograpiya at mga molekula ng mga compound ng kemikal, mga koneksyon sa pagitan ng mga tao at grupo ng mga tao. Sa nakalipas na apat na dekada, ang teorya ng graph ay naging isa sa pinakamabilis na umuunlad na sangay ng matematika. Ito ay hinihimok ng mga pangangailangan ng isang mabilis na lumalawak na lugar ng aplikasyon. Ito ay ginagamit sa disenyo ng integrated circuits at control circuits, sa pag-aaral ng automata, logical circuits, program flowcharts, sa economics at statistics, chemistry at biology, sa scheduling theory. kaya lang kaugnayan Ang paksa ay dahil, sa isang banda, sa katanyagan ng mga graph at mga kaugnay na pamamaraan ng pananaliksik, at sa kabilang banda, isang hindi pa binuo, integral na sistema para sa pagpapatupad nito.

Ang solusyon ng maraming problema sa buhay ay nangangailangan ng mahabang kalkulasyon, at kung minsan ang mga kalkulasyong ito ay hindi nagdudulot ng tagumpay. Ito ang binubuo nito suliranin sa pananaliksik. Ang tanong ay lumitaw: posible bang makahanap ng simple, makatuwiran, maikli at eleganteng solusyon para sa kanilang solusyon. Mas madaling malutas ang mga problema kung gagamit ka ng mga graph? Natukoy ito paksa ng aking pananaliksik: "Praktikal na Paglalapat ng Teoryang Graph"

pakay pananaliksik ay sa tulong ng mga graph upang malaman kung paano mabilis na malutas ang mga praktikal na problema.

Pananaliksik hypothesis. Ang pamamaraan ng graph ay napakahalaga at malawakang ginagamit sa iba't ibang larangan ng agham at buhay ng tao.

Layunin ng pananaliksik:

1. Upang pag-aralan ang literatura at mga mapagkukunan ng Internet sa isyung ito.

2. Suriin ang bisa ng pamamaraan ng graph sa paglutas ng mga praktikal na problema.

3. Gumawa ng konklusyon.

Praktikal na kahalagahan ng pag-aaral ay na ang mga resulta ay walang alinlangan na pukawin ang interes ng maraming tao. Wala ba sa inyo ang sumubok na bumuo ng family tree ng inyong pamilya? At paano ito gagawin nang tama? Ang pinuno ng isang kumpanya ng transportasyon ay malamang na lutasin ang problema ng mas kumikitang paggamit ng transportasyon kapag nagdadala ng mga kalakal mula sa isang destinasyon patungo sa ilang mga pamayanan. Ang bawat mag-aaral ay nahaharap sa lohikal na mga gawain sa pagsasalin ng dugo. Lumalabas na ang mga ito ay nalutas sa tulong ng mga graph nang madali.

Ang mga sumusunod na pamamaraan ay ginagamit sa trabaho: pagmamasid, paghahanap, pagpili, pagsusuri.

Ang kasaysayan ng paglitaw ng teorya ng graph

Ang mathematician na si Leonhard Euler (1707-1783) ay itinuturing na tagapagtatag ng teorya ng graph. Ang kasaysayan ng paglitaw ng teoryang ito ay matutunton sa pamamagitan ng sulat ng dakilang siyentipiko. Narito ang isang pagsasalin ng tekstong Latin, na kinuha mula sa sulat ni Euler sa Italyano na matematiko at inhinyero na si Marinoni, na ipinadala mula sa St. Petersburg noong Marso 13, 1736.

"Minsan ay binigyan ako ng problema tungkol sa isang isla na matatagpuan sa lungsod ng Koenigsberg at napapaligiran ng isang ilog, kung saan pitong tulay ang itinapon.

[Appendix Fig.1] Ang tanong ay kung ang sinuman ay maaaring umikot sa kanila nang tuluy-tuloy, minsan lamang dumaan sa bawat tulay. At pagkatapos ay ipinaalam sa akin na wala pang nakakagawa nito, ngunit walang nagpatunay na imposible ito. Ang tanong na ito, bagama't karaniwan, ay tila sa akin, gayunpaman, ay karapat-dapat na bigyang pansin dahil alinman sa geometry, o algebra, o combinatorial art ay hindi sapat para sa solusyon nito. Pagkatapos ng maraming deliberasyon, nakakita ako ng isang madaling tuntunin, batay sa isang medyo nakakumbinsi na patunay, kung saan sa lahat ng mga problema ng ganitong uri ay maaaring agad na matukoy kung ang gayong pag-ikot ay maaaring gawin sa pamamagitan ng anumang numero at arbitraryong matatagpuan ang mga tulay o hindi. Ang mga tulay ng Konigsberg ay matatagpuan upang sila ay maipakita sa sumusunod na pigura [Appendix Fig.2], kung saan ang A ay tumutukoy sa isang isla, at ang B , C at D ay mga bahagi ng kontinente na pinaghihiwalay ng mga sanga ng ilog sa isa't isa

Tungkol sa paraan na natuklasan niya para sa paglutas ng mga problema ng ganitong uri, isinulat ni Euler:

"Ang solusyon na ito, ayon sa likas na katangian nito, ay tila walang gaanong kinalaman sa matematika, at hindi malinaw sa akin kung bakit ang solusyong ito ay dapat asahan mula sa isang matematiko sa halip na mula sa sinumang ibang tao, dahil ang solusyon na ito ay sinusuportahan lamang ng katwiran, at hindi na kailangang isangkot upang mahanap ang solusyon na ito, anumang mga batas na likas sa matematika. Kaya, hindi ko alam kung paano lumalabas na ang mga tanong na napakaliit na kinalaman sa matematika ay mas malamang na malutas ng mga mathematician kaysa sa iba."

Kaya posible bang makalibot sa mga tulay ng Königsberg sa pamamagitan ng isang beses lamang dumaan sa bawat isa sa mga tulay na ito? Para mahanap ang sagot, ipagpatuloy natin ang sulat ni Euler kay Marinoni:

"Ang tanong ay upang matukoy kung posible bang makalibot sa lahat ng pitong tulay na ito, na dumaan sa bawat isa nang isang beses lamang, o hindi. Ang aking panuntunan ay humahantong sa sumusunod na solusyon sa tanong na ito. Una sa lahat, kailangan mong tingnan kung gaano karaming mga seksyon ay pinaghihiwalay ng tubig - tulad , na walang ibang paglipat mula sa isa't isa, maliban sa pamamagitan ng tulay. Sa halimbawang ito, mayroong apat na mga seksyon - A, B, C, D. Susunod, kailangan mong makilala kung ang bilang ng ang mga tulay na humahantong sa mga indibidwal na seksyon na ito ay pantay o kakaiba. Kaya, sa aming kaso, limang tulay ang humahantong sa seksyon A, at tatlong tulay sa iba pa, ibig sabihin. Ang bilang ng mga tulay na humahantong sa mga indibidwal na seksyon ay kakaiba, at ang isang ito ay sapat na upang lutasin ang problema. Kapag natukoy na ito, inilalapat namin ang sumusunod na panuntunan : kung pantay ang bilang ng mga tulay na humahantong sa bawat indibidwal na seksyon, magiging posible ang detour na pinag-uusapan, at sa parehong oras posible na simulan ang detour na ito mula sa anumang seksyon. magiging kakaiba, dahil isa lang ang n kung hindi ito maging pantay, kung gayon ang paglipat ay maaaring maganap, gaya ng inireseta, ngunit ang simula lamang ng likuan ay tiyak na dadalhin mula sa isa sa dalawang seksyong iyon kung saan ang isang kakaibang bilang ng mga tulay ay humahantong. Kung, sa wakas, mayroong higit sa dalawang seksyon kung saan ang isang kakaibang bilang ng mga tulay ay humahantong, kung gayon ang gayong paggalaw ay karaniwang imposible ... kung iba pa, mas malalang problema ang maaaring mabanggit dito, ang pamamaraang ito ay maaaring maging mas kapaki-pakinabang at hindi dapat mapabayaan".

Mga pangunahing kahulugan at teorema ng teorya ng graph

Ang teorya ng graph ay isang disiplinang matematika na nilikha ng mga pagsisikap ng mga mathematician, kaya kasama sa presentasyon nito ang mga kinakailangang mahigpit na kahulugan. Kaya, magpatuloy tayo sa organisadong pagpapakilala ng mga pangunahing konsepto ng teoryang ito.

Kahulugan 1. Ang graph ay isang koleksyon ng may hangganan na bilang ng mga puntos, na tinatawag na vertices ng graph, at pairwise na nagkokonekta sa ilan sa mga vertices ng mga linyang ito, na tinatawag na mga gilid o arko ng graph.

Ang depinisyon na ito ay maaaring mabuo nang iba: ang isang graph ay isang walang laman na hanay ng mga punto (mga vertice) at mga segment (mga gilid), na ang magkabilang dulo ay kabilang sa isang ibinigay na hanay ng mga puntos

Sa hinaharap, tutukuyin natin ang mga vertex ng graph sa mga Latin na titik A, B, C, D. Minsan ang graph sa kabuuan ay ilalarawan ng isang malaking titik.

Kahulugan 2. Ang mga vertice ng graph na hindi kabilang sa anumang gilid ay tinatawag na isolated.

Kahulugan 3. Ang isang graph na binubuo lamang ng mga isolated vertices ay tinatawag na zero - bilangin .

Notasyon: O "– isang graph na may mga vertex at walang mga gilid

Kahulugan 4. Ang isang graph kung saan ang bawat pares ng vertices ay konektado sa pamamagitan ng isang gilid ay tinatawag na kumpleto.

Pagtatalaga: U" – isang graph na binubuo ng n vertices at mga gilid na nag-uugnay sa lahat ng posibleng mga pares ng mga vertices na ito. Ang ganitong graph ay maaaring ilarawan bilang isang n-gon kung saan ang lahat ng mga diagonal ay iginuhit

Kahulugan 5. Ang antas ng isang vertex ay ang bilang ng mga gilid kung saan kabilang ang vertex.

Kahulugan 6. Ang isang graph na ang mga degree ng lahat ng k vertices ay pareho ay tinatawag na isang homogenous na graph ng degree k .

Kahulugan 7. Ang complement ng isang ibinigay na graph ay isang graph na binubuo ng lahat ng mga gilid at ang kanilang mga dulo na dapat idagdag sa orihinal na graph upang makakuha ng kumpletong graph.

Kahulugan 8. Ang isang graph na maaaring ilarawan sa isang eroplano sa paraang ang mga gilid nito ay magsalubong lamang sa mga vertice ay tinatawag na planar.

Kahulugan 9. Ang isang polygon ng isang planar graph na hindi naglalaman ng anumang mga vertex o mga gilid ng graph sa loob ay tinatawag na mukha nito.

Ang mga konsepto ng isang plane graph at graph face ay ginagamit sa paglutas ng mga problema para sa "tamang" pangkulay ng iba't ibang mga mapa.

Kahulugan 10. Ang isang landas mula A hanggang X ay isang pagkakasunud-sunod ng mga gilid na humahantong mula A hanggang X upang ang bawat dalawang magkatabing gilid ay may isang karaniwang vertex at walang gilid na nangyayari nang higit sa isang beses.

Kahulugan 11. Ang isang cycle ay isang landas kung saan ang mga punto ng pagsisimula at pagtatapos ay pareho.

Kahulugan 12. Ang simpleng cycle ay isang cycle na hindi dumadaan sa alinman sa mga vertex ng graph nang higit sa isang beses.

Kahulugan 13. mahabang daan , inilatag sa isang loop , ay ang bilang ng mga gilid ng landas na ito.

Kahulugan 14. Dalawang vertices A at B sa isang graph ay tinatawag na konektado (disconnected) kung mayroong (wala) isang path na humahantong mula A hanggang B sa loob nito.

Kahulugan 15. Ang isang graph ay tinatawag na konektado kung ang bawat dalawang vertice nito ay konektado; kung ang graph ay naglalaman ng hindi bababa sa isang pares ng mga disconnected vertices, ang graph ay tinatawag na disconnected.

Kahulugan 16. Ang puno ay isang konektadong graph na hindi naglalaman ng mga cycle.

Ang isang three-dimensional na modelo ng isang graph-tree ay, halimbawa, isang tunay na puno na may masalimuot na sanga na korona; ang ilog at ang mga tributaries nito ay bumubuo rin ng isang puno, ngunit patag na - sa ibabaw ng lupa.

Kahulugan 17. Ang isang disconnected graph na binubuo lamang ng mga puno ay tinatawag na kagubatan.

Kahulugan 18. Ang isang puno, ang lahat ng n vertices ay binibilang mula 1 hanggang n, ay tinatawag na puno na may renumbered vertices.

Kaya, isinasaalang-alang namin ang mga pangunahing kahulugan ng teorya ng graph, kung wala ito ay imposibleng patunayan ang mga theorems, at, dahil dito, upang malutas ang mga problema.

Nalutas ang mga problema gamit ang mga graph

Mga Sikat na Hamon

Ang problema sa naglalakbay na tindero

Ang problema sa paglalakbay na tindero ay isa sa mga sikat na problema sa teorya ng combinatorics. Ito ay inilagay noong 1934, at ang pinakamahusay na mga matematiko ay sinira ang kanilang mga ngipin tungkol dito.

Ang pahayag ng problema ay ang mga sumusunod.
Ang naglalakbay na tindero (naglalakbay na mangangalakal) ay dapat umalis sa unang lungsod, bisitahin ang mga lungsod 2,1,3..n isang beses sa isang hindi kilalang order, at bumalik sa unang lungsod. Ang mga distansya sa pagitan ng mga lungsod ay kilala. Sa anong pagkakasunud-sunod dapat na daanan ang mga lungsod upang ang saradong landas (paglibot) ng naglalakbay na tindero ay ang pinakamaikling?

Paraan para sa paglutas ng problema sa paglalakbay na tindero

Matakaw na Algorithm "Pumunta sa pinakamalapit (na hindi mo pa napasok) lungsod."
Ang algorithm na ito ay tinatawag na "matakaw" dahil sa mga huling hakbang kailangan mong magbayad ng mahal para sa kasakiman.
Isaalang-alang halimbawa ang network sa Figure [app fig.3] kumakatawan sa isang makitid na rhombus. Hayaang magsimula ang tindero mula sa lungsod 1. Ang algorithm na "pumunta sa pinakamalapit na lungsod" ay magdadala sa kanya sa lungsod 2, pagkatapos ay 3, pagkatapos ay 4; sa huling hakbang, kailangan mong magbayad para sa kasakiman, babalik kasama ang mahabang dayagonal ng rhombus. Ang resulta ay hindi ang pinakamaikling, ngunit ang pinakamahabang tour.

Ang problema ng mga tulay ng Königsberg.

Ang gawain ay binabalangkas tulad ng sumusunod.
Ang lungsod ng Konigsberg ay matatagpuan sa pampang ng Pregel River at dalawang isla. Ang iba't ibang bahagi ng lungsod ay pinagdugtong ng pitong tulay. Tuwing Linggo, namasyal ang mga taong bayan sa lungsod. Tanong: posible bang maglakad-lakad sa paraang, pag-alis ng bahay, bumalik, eksaktong isang beses na dumadaan sa bawat tulay.
Ang mga tulay sa ibabaw ng ilog ng Pregel ay matatagpuan tulad ng nasa larawan[Appendix Fig.1].

Isaalang-alang ang isang graph na tumutugma sa bridge scheme [appendix fig.2].

Upang masagot ang tanong ng problema, sapat na upang malaman kung ang graph ay Euler. (Hindi bababa sa isang vertex ay dapat magkaroon ng pantay na bilang ng mga tulay). Imposible, naglalakad sa paligid ng lungsod, na dumaan sa lahat ng mga tulay nang isang beses at bumalik.

Maraming mga kagiliw-giliw na hamon

1. "Mga Ruta".

Gawain 1

Tulad ng naaalala mo, ang mangangaso para sa mga patay na kaluluwa na si Chichikov ay bumisita sa mga sikat na may-ari ng lupa nang isang beses bawat isa. Binisita niya sila sa sumusunod na pagkakasunud-sunod: Manilov, Korobochka, Nozdrev, Sobakevich, Plyushkin, Tentetnikov, General Betrishchev, Petukh, Konstanzholgo, Colonel Koshkarev. Ang isang diagram ay natagpuan kung saan inilarawan ni Chichikov ang kamag-anak na posisyon ng mga estates at mga kalsada ng bansa na nag-uugnay sa kanila. Tukuyin kung aling ari-arian ang pag-aari kung kanino, kung hindi dumaan si Chichikov sa alinman sa mga kalsada nang higit sa isang beses [appendix fig.4].

Desisyon:

Ayon sa road map, makikita na sinimulan ni Chichikov ang kanyang paglalakbay sa E estate, at nagtapos sa O estate. Napansin namin na dalawang kalsada lamang ang patungo sa estates B at C, kaya kinailangan ni Chichikov na magmaneho sa mga kalsadang ito. Markahan natin sila ng mga naka-bold na linya. Ang mga seksyon ng rutang dumadaan sa A ay tinutukoy: AC at AB. Hindi naglakbay si Chichikov sa mga kalsadang AE, AK at AM. I-cross out natin sila. Markahan natin ng makapal na linya ED ; ekis ang DK . I-cross out ang MO at MN; markahan ng isang naka-bold na linya MF ; ekis ang FO ; minarkahan namin ng makapal na linya ang FH , NK at KO. Hanapin natin ang tanging posibleng ruta sa ilalim ng ibinigay na kondisyon. At nakukuha namin: ang estate E - ay pag-aari ng Manilov, D - Korobochka, C - Nozdrev, A - Sobakevich, V - Plyushkin, M - Tentetnikov, F - Betrishchev, N - Petukh, K - Konstanzholgo, O - Koshkarev [app fig.5].

Gawain 2

Ang figure ay nagpapakita ng mapa ng lugar [apendise fig.6].

Maaari ka lamang lumipat sa direksyon ng mga arrow. Ang bawat punto ay maaaring bisitahin nang hindi hihigit sa isang beses. Sa ilang paraan maaari kang makakuha mula sa punto 1 hanggang sa punto 9? Aling ruta ang pinakamaikli at alin ang pinakamahaba.

Desisyon:

Sunud-sunod na "stratify" ang scheme sa isang puno, simula sa vertex 1 [app fig.7]. Kumuha tayo ng puno. Ang bilang ng mga posibleng paraan upang makakuha ng mula 1 hanggang 9 ay katumbas ng bilang ng mga "nakabitin" na vertices ng puno (mayroong 14 sa kanila). Malinaw na ang pinakamaikling landas ay 1-5-9; ang pinakamahaba ay 1-2-3-6-5-7-8-9.

2 "Mga grupo, nakikipag-date"

Gawain 1

Ang mga kalahok ng pagdiriwang ng musika, na nakilala, ay nagpalitan ng mga sobre na may mga address. Patunayan na:

a) isang pantay na bilang ng mga sobre ang ipinadala sa kabuuan;

b) ang bilang ng mga kalahok na nagpalitan ng mga sobre ng kakaibang bilang ng beses ay pantay.

Solusyon: Hayaang ang mga kalahok sa pagdiriwang ay A 1 , A 2 , A 3 . . . , At ang n ay ang mga vertice ng graph, at ang mga gilid ay nag-uugnay sa mga pares ng mga vertex na kumakatawan sa mga lalaking nagpalitan ng mga sobre [Appendix Fig.8]

Desisyon:

a) ang antas ng bawat vertex A i ay nagpapakita ng bilang ng mga sobre na ibinigay ng kalahok A i sa kanyang mga kaibigan. Ang kabuuang bilang ng mga ipinadalang sobre N ay katumbas ng kabuuan ng mga antas ng lahat ng vertices ng graph N = hakbang. Isang 1 + na hakbang. Isang 2 + + . . . + hakbang. At n -1 + hakbang. At n , N =2p , kung saan ang p ay ang bilang ng mga gilid ng graph, i.e. Ang N ay pantay. Samakatuwid, isang pantay na bilang ng mga sobre ang ipinadala;

b) sa pagkakapantay-pantay N = hakbang. Isang 1 + na hakbang. Isang 2 + + . . . + hakbang. At n -1 + hakbang. At ang kabuuan ng mga kakaibang termino ay dapat na kahit na, at ito ay maaari lamang kung ang bilang ng mga kakaibang termino ay pantay. At nangangahulugan ito na ang bilang ng mga kalahok na nagpalitan ng mga sobre sa isang kakaibang bilang ng beses ay pantay.

Gawain 2

Minsan sina Andrei, Boris, Volodya, Dasha at Galya ay sumang-ayon na pumunta sa sinehan sa gabi. Nagpasya silang sumang-ayon sa pagpili ng sinehan at sesyon sa pamamagitan ng telepono. Napagpasyahan din na kung hindi posible na tumawag sa isang tao, pagkatapos ay kanselahin ang paglalakbay sa sinehan. Sa gabi, hindi lahat ay nagtipon sa sinehan, at samakatuwid ang pagbisita sa sinehan ay natapos. Kinabukasan, sinimulan nilang alamin kung sino ang tumawag kung kanino. Napag-alaman na tinawag ni Andrey na Boris at Volodya, tinawag ni Volodya na Boris at Dasha, tinawag ni Boris na Andrey at Dasha, tinawag ni Dasha sina Andrey at Volodya, at tinawag ni Galya sina Andrey, Volodya at Boris. Sino ang hindi nakatawag at samakatuwid ay hindi pumunta sa pulong?

Desisyon:

Gumuhit tayo ng limang puntos at italaga ang mga ito sa mga titik A, B, C, D, E. Ito ang mga unang titik ng mga pangalan. Ikonekta natin ang mga tuldok na tumutugma sa mga pangalan ng mga lalaki na tumawag sa isa't isa.

[app fig.9]

Makikita mula sa larawan na ang bawat isa sa mga lalaki - sina Andrey, Boris at Volodya - ay tumawag sa iba. Iyon ang dahilan kung bakit ang mga ito ay dumating sa sinehan. Ngunit nabigo sina Galya at Dasha na tumawag sa isa't isa (ang mga punto D at D ay hindi konektado ng isang segment) at samakatuwid, alinsunod sa kasunduan, hindi sila pumunta sa sinehan.

Ang paggamit ng mga graph sa iba't ibang larangan ng buhay ng mga tao

Bilang karagdagan sa mga halimbawang ibinigay, ang mga graph ay malawakang ginagamit sa konstruksiyon, electrical engineering, pamamahala, logistik, heograpiya, mechanical engineering, sosyolohiya, programming, automation ng mga teknolohikal na proseso at industriya, sikolohiya, at advertising. Kaya, mula sa lahat ng nasa itaas, ang praktikal na halaga ng teorya ng graph ay hindi maikakaila na sumusunod, ang patunay nito ay ang layunin ng pag-aaral na ito.

Sa anumang larangan ng agham at teknolohiya, nakakatugon ka sa mga graph. Ang mga graph ay mga kahanga-hangang bagay sa matematika kung saan maaari mong malutas ang mga problema sa matematika, pang-ekonomiya at lohikal, iba't ibang mga palaisipan at pasimplehin ang mga kondisyon ng mga problema sa pisika, kimika, electronics, automation. Maginhawang bumalangkas ng maraming mathematical facts sa wika ng mga graph. Ang teorya ng graph ay bahagi ng maraming agham. Ang teorya ng graph ay isa sa pinakamagagandang at visual na teorya sa matematika. Kamakailan, ang teorya ng graph ay nakahanap ng higit pang mga aplikasyon sa mga inilapat na isyu. Kahit na ang computer chemistry ay lumitaw - isang medyo batang larangan ng chemistry batay sa aplikasyon ng teorya ng graph.

Mga molecular graph, na ginagamit sa stereochemistry at structural topology, chemistry ng mga cluster, polymer, atbp., ay mga hindi nakadirekta na graph na nagpapakita ng istruktura ng mga molekula [app fig.10]. Ang mga vertice at mga gilid ng mga graph na ito ay tumutugma sa kaukulang mga atomo at ang mga kemikal na bono sa pagitan ng mga ito.

Molecular graph at puno: [app fig.10] a, b - multigraphs resp. ethylene at formaldehyde; in-mol. isomer ng pentane (mga puno 4, 5 ay isomorphic sa puno 2).

Sa stereochemistry ng mga organismo, ang pinaka kadalasang gumagamit ng mga molekular na puno - ang mga pangunahing puno ng mga molecular graph, na naglalaman lamang ng lahat ng vertices na tumutugma sa mga C atom. Ang mga puno at ang pagtatatag ng kanilang isomorphism ay nagbibigay-daan sa iyo upang matukoy ang pier. mga istruktura at hanapin ang kabuuang bilang ng mga isomer ng alkanes, alkenes at alkynes

Mga network ng protina

Mga network ng protina - mga grupo ng mga pisikal na nakikipag-ugnayan na mga protina na gumagana sa isang cell nang magkasama at sa isang coordinated na paraan, na kinokontrol ang mga interconnected na proseso na nagaganap sa katawan [app fig. labing-isa].

Hierarchical system graph tinatawag na puno. Ang isang natatanging katangian ng isang puno ay mayroon lamang isang landas sa pagitan ng alinman sa dalawa sa mga vertice nito. Ang puno ay hindi naglalaman ng mga cycle at loop.

Karaniwan, ang isang puno na kumakatawan sa isang hierarchical system ay may isang pangunahing vertex, na tinatawag na ugat ng puno. Ang bawat tuktok ng puno (maliban sa ugat) ay may isang ninuno lamang - ang bagay na itinalaga nito ay kabilang sa isang pinakamataas na antas ng klase. Anumang vertex ng puno ay maaaring makabuo ng ilang mga inapo - mga vertex na naaayon sa mas mababang antas ng mga klase.

Para sa bawat pares ng mga vertice ng puno, mayroong isang natatanging landas na nag-uugnay sa kanila. Ginagamit ang property na ito kapag hinahanap ang lahat ng mga ninuno, halimbawa, sa linya ng lalaki, ng sinumang tao na ang family tree ay kinakatawan bilang isang family tree, na isa ring "puno" sa kahulugan ng teorya ng graph.

Isang halimbawa ng family tree ko [appendix fig.12].

Isa pang halimbawa. Ipinapakita ng figure ang biblical family tree [appendix fig.13].

Pagtugon sa suliranin

1. Gawain sa transportasyon. Hayaang magkaroon ng base na may mga hilaw na materyales sa lungsod ng Krasnodar, na kailangang itanim sa mga lungsod ng Krymsk, Temryuk, Slavyansk-on-Kuban at Timashevsk sa isang pagtakbo, habang gumugugol ng kaunting oras at gasolina hangga't maaari at bumalik pabalik papuntang Krasnodar.

Desisyon:

Una, gumawa tayo ng graph ng lahat ng posibleng ruta. [app fig.14], na isinasaalang-alang ang mga tunay na kalsada sa pagitan ng mga pamayanang ito at ang distansya sa pagitan ng mga ito. Upang malutas ang problemang ito, kailangan nating lumikha ng isa pang graph, isang puno [app fig.15].

Para sa kaginhawahan ng solusyon, tinutukoy namin ang mga lungsod na may mga numero: Krasnodar - 1, Krymsk - 2, Temryuk - 3, Slavyansk - 4, Timashevsk - 5.

Nagresulta ito sa 24 na solusyon, ngunit kailangan lang namin ng pinakamaikling landas. Sa lahat ng mga solusyon, dalawa lamang ang nasiyahan, ito ay 350 km.

Katulad nito, posible at, sa palagay ko, kinakailangang kalkulahin ang tunay na transportasyon mula sa isang lokalidad patungo sa isa pa.

Logic na gawain para sa pagsasalin ng dugo. Mayroong 8 litro ng tubig sa isang balde, at mayroong dalawang kaldero na may kapasidad na 5 at 3 litro. kinakailangang magbuhos ng 4 na litro ng tubig sa isang limang litro na kasirola at mag-iwan ng 4 na litro sa isang balde, ibig sabihin, ibuhos ang tubig nang pantay-pantay sa isang balde at isang malaking kasirola.

Desisyon:

Ang sitwasyon sa anumang sandali ay maaaring ilarawan sa pamamagitan ng tatlong numero [appendix fig.16].

Bilang resulta, nakakakuha tayo ng dalawang solusyon: isa sa 7 galaw, ang isa sa 8 galaw.

Konklusyon

Kaya, upang matutunan kung paano lutasin ang mga problema, kailangan mong maunawaan kung ano ang mga ito, kung paano sila nakaayos, kung anong mga bahagi ang kanilang binubuo, ano ang mga tool na ginagamit upang malutas ang mga problema.

Ang paglutas ng mga praktikal na problema sa tulong ng teorya ng graph, naging malinaw na sa bawat hakbang, sa bawat yugto ng kanilang solusyon, kinakailangang ilapat ang pagkamalikhain.

Sa simula pa lang, sa unang yugto, ito ay nakasalalay sa katotohanan na kailangan mong masuri at ma-encode ang kalagayan ng problema. Ang ikalawang yugto ay isang schematic notation, na binubuo ng geometric na representasyon ng mga graph, at sa yugtong ito ang elemento ng pagkamalikhain ay napakahalaga dahil malayong madaling makahanap ng mga pagsusulatan sa pagitan ng mga elemento ng kundisyon at ng kaukulang elemento ng graph. .

Kapag nilulutas ang isang problema sa transportasyon o isang problema sa pag-compile ng isang family tree, napagpasyahan ko na ang pamamaraan ng graph ay tiyak na kawili-wili, maganda at nakikita.

Kumbinsido ako na ang mga graph ay malawakang ginagamit sa ekonomiya, pamamahala, at teknolohiya. Ang teorya ng graph ay ginagamit din sa programming.Hindi ito tinalakay sa papel na ito, ngunit sa palagay ko ito ay sandali lamang.

Sa gawaing pang-agham na ito, ang mga mathematical graph, ang kanilang mga lugar ng aplikasyon ay isinasaalang-alang, maraming mga problema ang nalutas sa tulong ng mga graph. Ang kaalaman sa mga pangunahing kaalaman sa teorya ng graph ay kinakailangan sa iba't ibang mga lugar na may kaugnayan sa pamamahala ng produksyon, negosyo (halimbawa, diagram ng network ng konstruksiyon, mga iskedyul ng paghahatid ng mail). Bilang karagdagan, habang nagtatrabaho sa isang gawaing pang-agham, pinagkadalubhasaan ko ang pagtatrabaho sa isang computer sa isang WORD text editor. Kaya, ang mga gawain ng gawaing pang-agham ay natutupad.

Kaya, mula sa lahat ng nasa itaas, ang praktikal na halaga ng teorya ng graph ay hindi maikakaila na sumusunod, ang patunay nito ay ang layunin ng gawaing ito.

Panitikan

Berge K. Teorya ng graph at mga aplikasyon nito. -M.: IIL, 1962.

Kemeny J., Snell J., Thompson J. Panimula sa finite mathematics. -M.: IIL, 1963.

Ore O. Mga graph at ang kanilang aplikasyon. -M.: Mir, 1965.

Harary F. Teorya ng graph. -M.: Mir, 1973.

Zykov A.A. Teorya ng mga Finite Graph. -Novosibirsk: Nauka, 1969.

Berezina L.Yu. Mga graph at ang kanilang aplikasyon. -M.: Edukasyon, 1979. -144 p.

"Soros Educational Journal" No. 11 1996 (Artikulo "Flat Graph");

Gardner M. "Mathematical leisure", M. "Mir", 1972 (kabanata 35);

Olekhnik S. N., Nesterenko Yu. V., Potapov M. K. "Mga lumang nakakaaliw na problema", M. "Nauka", 1988 (bahagi 2, seksyon 8; apendiks 4);

Aplikasyon

Aplikasyon

P

kanin. 6

kanin. 7

kanin. walo

Aplikasyon

Aplikasyon

Aplikasyon

P

kanin. labing-apat

Aplikasyon