Освен това през последните 12 години от живота си Ойлер е тежко болен, ослепява и въпреки тежкото заболяване продължава да работи и твори.

Статистическите изчисления показват, че Ойлер е правил средно едно откритие на седмица.

Трудно е да се намери математически проблем, който да не е засегнат в произведенията на Ойлер.

Всички математици от следващите поколения са учили с Ойлер по един или друг начин и не напразно известният френски учен P.S. Лаплас е казал: „Четете Ойлер, той е учител на всички нас.

Лагранж казва: „Ако наистина обичате математиката, прочетете Ойлер; изложението на неговите произведения се отличава с удивителна яснота и точност“. Наистина, елегантността на изчисленията е доведена до най-висока степен от него. Кондорсе завърши речта си в академията в памет на Ойлер със следните думи: „И така, Ойлер спря да живее и смята!“ Да живееш, за да смяташ - колко скучно изглежда отвън! Прието е да си представяме математиката като суха и глуха за всичко светско, за това, от което се интересуват обикновените хора.

С името на Ойлер е проблемът за три къщи и три кладенеца.

ТЕОРИЯ НА ГРАФИТЕ

Един от клоновете на топологията. Графиката е геометрична диаграма, която е система от линии, свързващи някои дадени точки. Точките се наричат върхове, а линиите, които ги свързват, се наричат ръбове (или дъги). Всички проблеми на теорията на графовете могат да бъдат решени както в графична, така и в матрична форма. В случай на запис в матрична форма, възможността за предаване на съобщение от даден връх към друг се обозначава с единица, а липсата му се обозначава с нула.

Произходът на теорията на графите през 18 век. свързано с математически пъзели, но особено силен тласък на развитието му е даден през 19 век. и главно през 20 в., когато са открити възможностите за практическото му приложение: за изчисляване на радиоелектронни схеми, решаване на т.нар. транспортни задачи и пр. От 50-те години. Теорията на графите все повече се използва в социалната психология и социология.

В областта на теорията на графите трябва да се посочат трудовете на Ф. Хари, Дж. Кемени, К. Фламент, Дж. Снел, Дж. Френч, Р. Норман, О. Ойзер, А. Бейвелас, Р. Вайс и др. В СССР според Т. г. работа Φ. М. Бородкин и др.

Езикът на теорията на графите е много подходящ за анализ на различни видове структури и прехвърляне на състояния. В съответствие с това можем да разграничим следните видове социологически и социално-психологически проблеми, решавани с помощта на теорията на графите.

Формализиране и изграждане на общ структурен модел на социален обект на различни ниванеговата сложност. Например организационни схеми, социограми, сравнение на системите за родство в различните общества, анализ на ролевата структура на групите и т.н. Можем да приемем, че ролевата структура включва три компонента: лица, длъжности (в опростен вариант - длъжности) и задачи, изпълнявани на тази позиция. Всеки компонент може да бъде представен като графика:

Възможно е да се комбинират и трите графики за всички позиции или само за една, като в резултат получаваме ясна представа за специфичната структура на к.л. тази роля. И така, за ролята на позиция P5 имаме графика (фиг.). Вплитането на неформални отношения в посочената формална структура значително ще усложни графиката, но ще бъде повече точно копиереалност.

2) Анализ на получения модел, избор на структурни единици (подсистеми) в него и изследване на техните взаимоотношения. По този начин, например, подсистемите в големите организации могат да бъдат разделени.

3) Изучаване на нивата на структурата на йерархичните организации: броя на нивата, броя на връзките, преминаващи от едно ниво на друго и от едно лице на друго. Въз основа на това се решават следните задачи:

а) количества. оценка на тежестта (статуса) на дадено лице в йерархична организация. Една от възможните опции за определяне на състоянието е формулата:

където r (p) е статусът на определено лице p, k е стойността на нивото на подчинение, определено като най-малкия брой стъпки от дадено лице до неговия подчинен, nk е броят на лицата на дадено ниво k . Например в организацията, представена от следното. броя:

тегло а=1 2+2 7+3 4=28; 6=1 3+2 3=9 и т.н.

б) определяне на лидера на групата. Лидерът обикновено се характеризира с по-голяма връзка с други членове на групата от останалите. Както в предишния проблем, тук могат да се използват различни методи за избор на лидера.

Най-простият начин се дава с формулата: r=Σdxy/Σdqx, т.е. коефициентът на разделянето на сумата от всички разстояния на всеки до всички останали на сумата от разстоянията на индивида до всички останали.

4) Анализ на ефективността на тази система, който включва и такива задачи като намиране на оптимална структура на организацията, повишаване на груповата сплотеност, анализиране на социалната система от гледна точка на нейната стабилност; изследване на информационните потоци (предаване на съобщения при решаване на проблеми, влиянието на членовете на групата един върху друг в процеса на групово обединяване); с помощта на TG решават проблема с намирането на оптимална комуникационна мрежа.

Приложено към теорията на графиките, както и към всеки математически апарат, е вярно твърдението, че основните принципи за решаване на проблем се задават от теорията на съдържанието (в случая социологията).

Задача : Трима съседи делят три кладенеца. Възможно ли е да се начертаят непресичащи се пътеки от всяка къща до всеки кладенец. Пътеките не могат да минават през кладенци и къщи (фиг. 1).

Ориз. 1. По проблема с къщите и кладенците.

За да разрешим този проблем, използваме теоремата, доказана от Ойлер през 1752 г., която е една от основните в теорията на графовете. Първата работа по теория на графите принадлежи на Леонхард Ойлер (1736), въпреки че терминът "граф" е въведен за първи път през 1936 г. от унгарския математик Денеш Кьониг. Графите се наричаха схеми, състоящи се от точки и свързващи тези точки с линейни сегменти или криви.

Теорема. Ако един многоъгълник е разделен на краен брой многоъгълници по такъв начин, че всеки два многоъгълника от дяла или нямат общи точки, или имат общи върхове, или имат общи ръбове, тогава равенството

V - P + G = 1, (*)

където B е общият брой върхове, P е общият брой ръбове, G е броят на многоъгълниците (лица).

Доказателство. Нека докажем, че равенството не се променя, ако начертаем диагонал в някакъв многоъгълник на даденото дял (фиг. 2, а).

а) б)

Всъщност, след начертаване на такъв диагонал, новият дял ще има B върхове, P + 1 ръбове и броят на многоъгълниците ще се увеличи с един. Следователно имаме

B - (P + 1) + (G + 1) \u003d B - P + G.

Използвайки това свойство, ние начертаваме диагонали, разделящи входящите многоъгълници на триъгълници, а за полученото дял показваме, че релацията е изпълнима.

За да направите това, ние последователно ще премахваме външните ръбове, намалявайки броя на триъгълниците. В този случай са възможни два случая:

за да премахнете триъгълника ABC, трябва да премахнете два ръба, в нашия случай AB и BC;

за да премахнете триъгълник MKN, единият ръб трябва да бъде премахнат, в нашия случай MN.

И в двата случая равенството няма да се промени. Например, в първия случай, след премахване на триъгълника, графиката ще се състои от B-1 върхове, P-2 ръбове и G-1 многоъгълник:

(B - 1) - (P + 2) + (G -1) \u003d B - P + G.

По този начин премахването на един триъгълник не променя равенството.

Продължавайки този процес на премахване на триъгълници, в крайна сметка ще получим дял, състоящ се от един триъгълник. За такъв дял B = 3, P = 3, Γ = 1 и следователно,

Това означава, че равенството важи и за първоначалното дял, откъдето накрая получаваме, че отношението е валидно за даденото дял на многоъгълника.

Забележете, че отношението на Ойлер не зависи от формата на многоъгълниците. Многоъгълниците могат да бъдат деформирани, увеличени, намалени или дори огънати страните си, стига страните да не се счупят. Отношението на Ойлер не се променя.

Сега пристъпваме към решаването на проблема с три къщи и три кладенеца.

Решение. Да предположим, че може да се направи. Маркираме къщите с точки D1, D2, D3, а кладенците с точки K1, K2, K3 (фиг. 1). Свързваме всяка точка-къща с всяка точка-кладенец. Получаваме девет ръба, които не се пресичат по двойки.

Тези ръбове образуват многоъгълник в равнината, разделен на по-малки многоъгълници. Следователно за това разделяне трябва да е изпълнено отношението на Ойлер B - P + G = 1.

Нека добавим към разглежданите лица още една - външната част на равнината по отношение на многоъгълника. Тогава отношението на Ойлер ще приеме формата B - P + G = 2, с B = 6 и P = 9.

Следователно Г = 5. Всяко от петте лица има поне четири ръба, тъй като според условието на задачата нито една от пътищата не трябва да свързва директно две къщи или два кладенеца. Тъй като всеки ръб лежи точно в две лица, броят на ръбовете трябва да бъде най-малко (5 4)/2 = 10, което противоречи на условието техният брой да е 9.

Полученото противоречие показва, че отговорът в задачата е отрицателен. - невъзможно е да се начертаят непресичащи се пътища от всяка къща до всяка колона

Теория на графите в химията

Прилагането на теорията на графите за изграждане и анализ на различни класове химични и химико-технологични графи, които се наричат още топология, модели, т.е. модели, които отчитат само естеството на връзката на върховете. Дъгите (ребрата) и върховете на тези графики отразяват химични и химико-технологични понятия, явления, процеси или обекти и съответно качествена и количествена връзка или определена връзка между тях.

Теоретични задачи. Химическите графики позволяват да се предскажат химични трансформации, да се обясни същността и да се систематизират някои основни понятия от химията: структура, конфигурация, потвърждения, квантово механични и статистико-механични взаимодействия на молекули, изомерия и др. Химичните графики включват молекулярни, двустранни и сигнални графики на кинетичните уравнения на реакциите. Молекулните графики, използвани в стереохимията и структурната топология, химията на клъстерите, полимерите и т.н., са ненасочени графики, които показват структурата на молекулите. Върховете и ръбовете на тези графики съответстват на съответните атоми и химичните връзки между тях.

В стереохимия орг. c-c най-често използват молекулярни дървета - обхващащи дървета от молекулярни графики, които съдържат само всички върхове, съответстващи на атомите.Съставянето на набори от молекулярни дървета и установяване на техния изоморфизъм ви позволява да определите молекулярните структури и да намерите общия брой изомери на алкани, алкени и алкини . Молекулните графики позволяват да се сведат проблемите, свързани с кодирането, номенклатурата и структурните характеристики (разклоняване, цикличност и т.н.) на молекулите на различни съединения, до анализа и сравнението на чисто математически характеристики и свойства на молекулярните графики и техните дървета, както и като съответните им матрици. За идентифициране на броя на корелациите между структурата на молекулите и физикохимичните (включително фармакологични) свойства на съединенията са използвани повече от 20 т.нар. Топологични индекси на молекули (Wiener, Balaban, Hosoyya, Plat, Randich и др.), които се определят с помощта на матрици и числени характеристики на молекулярните дървета. Например, индексът на Wiener W = (m3 + m) / 6, където m е броят на върховете, съответстващи на C атоми, корелира с молекулярни обеми и пречупвания, енталпии на образуване, вискозитет, повърхностно напрежение, хроматографски константи на съединенията, октанови числа на въглеводородите и дори физиол. лекарствена активност. Важни параметри на молекулярните графики, използвани за определяне на тавтомерните форми на дадено вещество и тяхната реактивност, както и при класификацията на аминокиселини, нуклеинови киселини, въглехидрати и други сложни природни съединения, са средният и пълен (H) информационен капацитет . Анализът на молекулярните графики на полимери, чиито върхове съответстват на мономерни единици, а ръбовете на химичните връзки между тях, дава възможност да се обяснят, например: ефектите от изключения обем, водещи до качества. промени в прогнозираните свойства на полимерите. С помощта на теорията на графите и принципите на изкуствения интелект е разработен софтуер за информационно-извличащи системи в химията, както и автоматизирани системи за идентифициране на молекулярни структури и рационално планиране на органичния синтез. За практическото изпълнение на компютър на операции за избор на рационални начини на хим. трансформациите, базирани на ретросинтетични и синтонични принципи, използват многостепенни разклонени графи за търсене на решения, чиито върхове съответстват на молекулярните графики на реагентите и продуктите, а дъгите представляват трансформации.

За решаване на многоизмерни задачи на анализ и оптимизация на химико-технологичните системи (ХТС) се използват следните химико-технологични графики: поток, информационно-поточен, сигнален и надежден график. За обучение по хим. физика на смущенията в системи, състоящи се от голям брой частици, използват т.нар. Диаграмите на Файнман са графики, чиито върхове съответстват на елементарните взаимодействия на физическите частици, ръбовете на техните пътища след сблъсъци. По-специално, тези графики позволяват да се изследват механизмите на осцилаторните реакции и да се определи стабилността на реакционните системи. върховете на графиките съответстват на устройства, в които се променят топлинните разходи на физическите потоци, и освен това на източниците и поглъщателите на топлинната енергия на системата; дъгите отговарят на физически и фиктивни (физико-химично преобразуване на енергията в апарати) топлинни потоци, а теглата на дъгите са равни на енталпиите на потоците. Материални и термични графики се използват за съставяне на програми за автоматизирано разработване на алгоритми за решаване на системи от уравнения на материални и топлинни баланси на сложни CTS. Графиките на информационните потоци показват логико-информационната структура на системите от уравнения мат. модели XTS; се използват за разработване на оптимални алгоритми за изчисляване на тези системи. Двустранният информационен граф е ненасочен или насочен граф, чиито върхове съответстват на респ. уравнения fl -f6 и променливи q1 - V, а клоновете отразяват връзката им. Информационна графика - орграф, изобразяващ реда на решаване на уравнения; върховете на графиката съответстват на тези уравнения, източниците и приемниците на XTS информацията и клоновете на информацията. променливи. Сигналните графики съответстват на линейни системи от уравнения на математически модели на химико-технологични процеси и системи. Графиките за надеждност се използват за изчисляване на различни показатели за надеждност X.

Препратки:

1. Берж К., Т. г. и приложението му, превод от френски, М., 1962;

2. Kemeny J., Snell J., Thompson J., Въведение в крайната математика, прев. от английски, 2-ро изд., М., 1963;

3.Опе О., Графики и тяхното приложение, прев. от английски, М., 1965;

4. О. В. Белих, Е. В. Беляев, Възможности за използване на Т. г. в социологията, в: Човекът и обществото, кн. 1, [L.], 1966;

5. Количествени методи в социологическите изследвания, М., 1966; Беляев Е. В., Проблеми на социологическото измерване, "VF", 1967, № 7; Бавелас. Модели на комуникация в групи, ориентирани към задачи, в книгата. Lerner, D., Lasswell H., Policy sciences, Stanford, 1951;

6. Kemeny J. G., Snell J., Математически модели в социалните науки, N. Y., 1962; Filament C., Приложения на теорията на графовете към груповата структура, N. Y., 1963; Oeser Ο. A., Hararu F., Ролеви структури и описание от гледна точка на теорията на графите, в Viddle B., Thomas E. J., Role theory: concepts and research, N. Y., 1966. E. Belyaev. Ленинград.

Страница 8, като неорганични, ... омъжена за авантюрист Право >> Исторически личности

На главницата задачи теориимерки и ергодични теории(в теориинамалява ... в областта на физиката, химия, физиология или медицина, ... Максимален поток Нека има графика(с ориентирани ръбове), ... оставащ дълго време нерешен. Елипсоидният метод има...

ОБЩИНСКА АВТОНОМНА ОБЩО ОБРАЗОВАТЕЛНА ИНСТИТУЦИЯ СРЕДНО ОБРАЗОВАТЕЛНО УЧИЛИЩЕ № 2

Подготвени

Легкоконец Владислав, 10А ученик

Практическа употребаГрафични теории

Ръководител

L.I. Носкова, учител по математика

ул.Брюховецкая

2011 г

1.Въведение……………………………………………………………………………………….………….3

2. Историята на възникването на теорията на графите………………………………………………………………..4

3.Основни дефиниции и теореми на теорията на графовете………………………………….………6

4. Задачи, решени с помощта на графики………………………………………..……………………..8

4.1 Известни задачи………………………………….…………………………………...8

4.2 Някои интересни задачи…………………………………………………………..9

5. Прилагане на графики в различни области от живота на хората…………………………………………11

6. Решаване на проблеми………………………………………………………………………………………………………...12

7. Заключение…………………………………………………………………………………………………….13

8. Списък на литературата……………………………………………………………………………………………………………………… ……………………………………………………………………………………………………………………………………………………………… …………………………………………………………………………………………………………………………………………………….

9.Приложение………………………………………………………………………………………………15

Въведение

Родена в решаването на пъзели и забавни игри, теорията на графите вече стана проста, достъпна и мощен инструментрешаване на проблеми, свързани с широк кръг от проблеми. Графиките са буквално повсеместни. Под формата на графики може например да се интерпретират пътни диаграми и електрически вериги, географски карти и молекули на химични съединения, връзки между хора и групи хора. През последните четири десетилетия теорията на графите се превърна в един от най-бързо развиващите се клонове на математиката. Това се дължи на изискванията на бързо разширяваща се област на приложение. Използва се при проектирането на интегрални схеми и схеми за управление, при изследване на автомати, логически схеми, блокови схемипрограми, по икономика и статистика, химия и биология, по теория на планирането. Така уместностТемата се дължи, от една страна, на популярността на графиките и свързаните с тях изследователски методи, а от друга страна на неразвитата, интегрална система за нейното прилагане.

Решаването на много житейски проблеми изисква дълги изчисления и понякога тези изчисления не носят успех. Ето какво се състои изследователски проблем. Възниква въпросът: възможно ли е да се намери просто, рационално, кратко и елегантно решение за тяхното решение. По-лесно ли е да решавате проблеми, ако използвате графики? То определи тема на моето изследване: "Практическо приложение на теорията на графите"

целизследванията бяха с помощта на графики, за да се научат как бързо да решават практически проблеми.

Изследователска хипотеза.Графичният метод е много важен и широко използван в различни области на науката и човешкия живот.

Цели на изследването:

1. Да проучи литературата и интернет ресурси по този въпрос.

2. Проверете ефективността на графичния метод при решаване на практически задачи.

3. Направете заключение.

Практическа значимост на изследванетое, че резултатите несъмнено ще предизвикат интереса на много хора. Никой от вас не се е опитвал да изгради родословно дърво на семейството си? И как да го направя правилно? Ръководителят на транспортна фирма вероятно трябва да реши проблема с по-изгодното използване на транспорта при превоз на стоки от дестинация до няколко населени места. Всеки ученик се изправи пред логически задачи за трансфузия. Оказва се, че лесно се решават с помощта на графики.

В работата се използват следните методи: наблюдение, търсене, подбор, анализ.

Историята на възникването на теорията на графите

Математикът Леонхард Ойлер (1707-1783) се счита за основоположник на теорията на графите. Историята на възникването на тази теория може да бъде проследена чрез кореспонденцията на великия учен. Ето превод на латински текст, който е взет от писмото на Ойлер до италианския математик и инженер Маринони, изпратено от Санкт Петербург на 13 март 1736 г.

„Веднъж ми поставиха проблем за остров, разположен в град Кьонигсберг и заобиколен от река, през която са прехвърлени седем моста.

[Приложение Фиг.1]Въпросът е дали някой може да ги заобикаля непрекъснато, минавайки само веднъж през всеки мост. И тогава ме информираха, че никой все още не е успял да направи това, но никой не е доказал, че е невъзможно. Този въпрос, макар и банален, ми се стори обаче достоен за внимание, защото нито геометрията, нито алгебрата, нито комбинаторното изкуство са достатъчни за неговото разрешаване. След дълго мислене открих едно лесно правило, базирано на напълно убедително доказателство, с помощта на което при всички задачи от този вид може веднага да се определи дали такъв кръг може да се направи през произволно брой и произволно разположени мостове или не. Кьонигсбергските мостове са разположени така, че да могат да бъдат представени на следващата фигура [Приложение Фиг.2], където A означава остров, а B, C и D са части от континента, разделени една от друга с речни разклонения

По отношение на метода, който е открил за решаване на проблеми от този вид, Ойлер пише:

„Това решение по своята същност изглежда няма много общо с математиката и не ми е ясно защо това решение трябва да се очаква от математик, а не от който и да е друг човек, тъй като това решение се поддържа само от разума и няма нужда да се включват, за да се намери това решение, каквито и да било закони, присъщи на математиката. Така че не знам как се оказва, че въпросите, които имат много малко общо с математиката, е по-вероятно да бъдат разрешени от математиците, отколкото от други."

Така че възможно ли е да заобиколите мостовете на Кьонигсберг, като преминете само веднъж през всеки от тези мостове? За да намерим отговора, нека продължим писмото на Ойлер до Маринони:

„Въпросът е да се определи дали е възможно да се заобиколят всички тези седем моста, минавайки през всеки само веднъж, или не. Моето правило води до следното решение на този въпрос. Първо, трябва да погледнете колко отсечки са разделени от вода - такива, които нямат друг преход от един към друг, освен през моста. В този пример има четири такива секции - A, B, C, D. След това трябва да различите дали броят на мостовете, водещи до тези отделни участъци, е четно или нечетно. Така че в нашия случай пет моста водят до участък А, а три моста до останалите, т.е. решаване на проблема. Когато това е определено, ние прилагаме следното правило: ако броят на мостовете, водещи до всеки отделен участък, е четен, тогава въпросното отклонение би било възможно и в същото време би било възможно да започне това отклонение от всяка секция би било нечетно, защото само едно е n ако не може да бъде четно, тогава и тогава преходът би могъл да се осъществи, както е предписано, но само началото на обхода със сигурност трябва да се вземе от един от тези два участъка, до които води нечетен брой мостове. Ако в крайна сметка имаше повече от два участъка, до които води нечетен брой мостове, тогава такова движение като цяло е невъзможно ... ако тук могат да се цитират други, по-сериозни проблеми, този метод може да бъде още по-полезен и не трябва бъде пренебрегван“.

Основни дефиниции и теореми на теорията на графовете

Теорията на графите е математическа дисциплина, създадена с усилията на математиците, така че нейното представяне включва необходимите строги дефиниции. И така, нека преминем към организираното въвеждане на основните понятия на тази теория.

Определение 1.Графът е съвкупност от краен брой точки, наречени върхове на графиката и свързващи по двойки някои от тези върхове на линии, наречени ръбове или дъги на графиката.

Тази дефиниция може да бъде формулирана по различен начин: графиката е непразен набор от точки (върхове) и сегменти (ръба), и двата края на които принадлежат на даден набор от точки

В бъдеще ще обозначаваме върховете на графиката с латински букви A, B, C, D. Понякога графиката като цяло ще бъде обозначена с една главна буква.

Определение 2.Върховете на графа, които не принадлежат на нито един ръб, се наричат изолирани.

Определение 3.Граф, състоящ се само от изолирани върхове, се нарича нула - броя .

Обозначение: O "- графика с върхове и без ръбове

Определение 4.Граф, в който всяка двойка върхове е свързана с ръб, се нарича пълна.

Обозначение: U" – граф, състоящ се от n върха и ребра, свързващи всички възможни двойки от тези върхове. Такава графика може да бъде представена като n-ъгълник, в който са начертани всички диагонали

Определение 5.Степента на върха е броят на ръбовете, на които принадлежи върхът.

Определение 6.Граф, чиито степени на всички k върхове са еднакви, се нарича хомогенен график от степен k .

Определение 7.Допълнението на тази графика е графиката, състояща се от всички ръбове и техните краища, които трябва да бъдат добавени към оригиналната графика, за да се получи пълна графика.

Определение 8.Граф, който може да бъде представен в равнина по такъв начин, че ръбовете му да се пресичат само във върховете, се нарича планарен.

Определение 9.Многоъгълник на планарен граф, който не съдържа върхове или ръбове на графа вътре, се нарича негово лице.

Понятията за плоска графика и графични лица се използват при решаване на задачи за "правилното" оцветяване на различни карти.

Определение 10.Път от A до X е поредица от ръбове, водещи от A до X, така че всеки два съседни ръба да имат общ връх и нито един ръб не се среща повече от веднъж.

Определение 11.Цикълът е път, при който началната и крайната точки са еднакви.

Определение 12.Прост цикъл е цикъл, който не преминава през нито един от върховете на графа повече от веднъж.

Определение 13.дълъг път , положени на примка , е броят на ръбовете на този път.

Определение 14.Два върха A и B в графа се наричат свързани (несвързани), ако в него съществува (не съществува) път, водещ от A до B.

Определение 15.Графът се нарича свързан, ако всеки два негов върха са свързани; ако графът съдържа поне една двойка несвързани върхове, тогава графът се нарича несвързан.

Определение 16.Дървото е свързана графика, която не съдържа цикли.

Триизмерен модел на граф-дърво е, например, истинско дърво с неговата сложно разклонена корона; реката и нейните притоци също образуват дърво, но вече плоско - на повърхността на земята.

Определение 17.Несвързана графа, състояща се само от дървета, се нарича гора.

Определение 18.Дърво, чиито n върхове са номерирани от 1 до n, се нарича дърво с преномерирани върхове.

И така, разгледахме основните дефиниции на теорията на графовете, без които би било невъзможно да се доказват теореми и следователно да се решават проблеми.

Проблеми, решени с помощта на графики

Известни предизвикателства

Проблемът с пътуващия продавач

Проблемът с пътуващия продавач е един от известните проблеми в теорията на комбинаториката. Поставен е през 1934 г. и най-добрите математици си счупиха зъбите за него.

Постановката на проблема е следната.
Пътуващият търговец (пътуващ търговец) трябва да напусне първия град, да посети градове 2,1,3..n веднъж в неизвестен ред и да се върне в първия град. Разстоянията между градовете са известни. В какъв ред трябва да се изминат градовете, така че затвореният път (обиколка) на продавача да е най-кратък?

Метод за решаване на проблема с продавача

Алчен алгоритъм „Отидете до най-близкия (в който все още не сте влезли) град.“
Този алгоритъм се нарича „алчен“, защото в последните стъпки трябва да плащате скъпо за алчността.
Да разгледаме например мрежата на фигура [приложение фиг.3]представляващ тесен ромб. Нека продавачът започне от град 1. „Отиди към най-близкия град” ще го отведе до град 2, след това 3, след това 4; на последната стъпка ще трябва да платите за алчност, връщайки се по дългия диагонал на ромба. Резултатът не е най-кратката, а най-дългата обиколка.

Проблемът с Кьонигсбергските мостове.

Задачата е формулирана по следния начин.
Град Кьонигсберг е разположен на брега на река Прегел и два острова. Различни части на града бяха свързани със седем моста. В неделя жителите на града се разхождаха из града. Въпрос: възможно ли е да се разхождате по такъв начин, че след като излезете от къщата, да се върнете, минавайки точно веднъж през всеки мост.
Мостовете над река Прегел са разположени както на снимката[Приложение Фиг.1].

Помислете за графика, съответстваща на мостовата схема [приложение фиг.2].

За да се отговори на въпроса за задачата, е достатъчно да се установи дали графиката е Ойлерова. (Поне един връх трябва да има четен брой мостове). Невъзможно е, разхождайки се из града, да минеш през всичките мостове веднъж и да се върнеш.

Няколко интересни предизвикателства

1. „Маршрути“.

Задача 1

Както си спомняте, ловецът мъртви душиЧичиков посещава известни земевладелци по веднъж. Той ги посети в следния ред: Манилов, Коробочка, Ноздрев, Собакевич, Плюшкин, Тентетников, генерал Бетрищев, Петух, Констанжолго, полковник Кошкарев. Намерена е диаграма, на която Чичиков скицира относителното положение на имотите и селски пътищасвързвайки ги. Определете кое имение на кого принадлежи, ако Чичиков не е минал нито един от пътищата повече от веднъж [приложение фиг.4].

Решение:

По пътната карта се вижда, че Чичиков е започнал пътуването си с имението Е, а завършва с имението О. Забелязваме, че само два пътя водят до имотите В и В, така че Чичиков трябваше да кара по тези пътища. Нека ги отбележим с получер линии. Определят се участъците от маршрута, преминаващ през А: AC и AB. Чичиков не е пътувал по пътищата AE, AK и AM. Да ги зачеркнем. Нека отбележим с дебела линия ED ; зачертайте DK . Зачертайте MO и MN; маркирайте с удебелена линия MF ; зачертавам FO ; маркираме FH , NK и KO с удебелена линия. Нека намерим единствения възможен маршрут при даденото условие. И получаваме: имението E - принадлежи на Манилов, D - Коробочка, C - Ноздрев, A - Собакевич, V - Плюшкин, M - Тентетников, F - Бетрищев, N - Петух, K - Констанжолго, O - Кошкарев [приложение фиг.5].

Задача 2

Фигурата показва карта на района [приложение фиг.6].

Можете да се движите само в посоката на стрелките. Всяка точка може да се посети не повече от веднъж. По колко начина можете да стигнете от точка 1 до точка 9? Кой маршрут е най-краткият и кой най-дълъг.

Решение:

Последователно "стратифицирайте" схемата в дърво, започвайки от връх 1 [приложение фиг.7]. Да вземем дърво. номер възможни начинихитове от 1 до 9 е равно на броя на "висящите" върхове на дървото (има 14 от тях). Очевидно най-краткият път е 1-5-9; най-дългият е 1-2-3-6-5-7-8-9.

2 "Групи, запознанства"

Задача 1

Участниците в музикалния фестивал, след като се срещнаха, си размениха пликове с адреси. Докажи това:

а) общо са изпратени четен брой пликове;

б) броят на участниците, разменили пликове нечетен брой пъти, е четен.

Решение: Нека участниците във фестивала са A 1 , A 2 , A 3 . . . , И n са върховете на графиката, а ръбовете свързват двойки върхове, представляващи момчета, които са разменили пликове [Приложение Фиг.8]

решение:

а) степента на всеки връх A i показва броя на пликовете, които участник A i е дал на приятелите си. Общият брой на предадените обвивки N е равен на сумата от степените на всички върхове на графа N = стъпка. A 1 + стъпка. A 2 + +. . . + стъпка. И n -1 + стъпка. И n , N =2p , където p е броят на ръбовете на графа, т.е. N е четно. Поради това бяха изпратени четен брой пликове;

б) в равенството N = стъпка. A 1 + стъпка. A 2 + +. . . + стъпка. И n -1 + стъпка. И n сумата от нечетните членове трябва да е четна, а това може да бъде само ако броят на нечетните членове е четен. А това означава, че броят на участниците, разменили пликове нечетен брой пъти, е четен.

Задача 2

Веднъж Андрей, Борис, Володя, Даша и Галя се съгласиха да отидат на кино вечер. Решиха да се договорят за избора на киното и сесията по телефона. Също така беше решено, че ако не е възможно да се обади на някого, тогава пътуването до киното ще бъде отменено. Вечерта не всички се събраха в киното и затова посещението на киното пропадна. На следващия ден започнаха да откриват кой на кого се е обадил. Оказа се, че Андрей се обади на Борис и Володя, Володя вика Борис и Даша, Борис се обади на Андрей и Даша, Даша се обади на Андрей и Володя, а Галя се обади на Андрей, Володя и Борис. Кой не можа да се обади и следователно не дойде на срещата?

решение:

Да начертаем пет точки и да ги обозначим с буквите A, B, C, D, E. Това са първите букви на имената. Нека свържем онези точки, които съответстват на имената на момчетата, които са се обадили.

[приложение фиг.9]

От снимката се вижда, че всяко от момчетата - Андрей, Борис и Володя - се обади на всички останали. Затова тези момчета дойдоха на кино. Но Галя и Даша не успяха да се обадят (точки D и D не са свързани с сегмент) и следователно, в съответствие със споразумението, те не дойдоха на кино.

Използването на графики в различни области от живота на хората

В допълнение към дадените примери, графиките намират широко приложение в строителството, електротехниката, управлението, логистиката, географията, машиностроенето, социологията, програмирането, автоматизацията на технологичните процеси и индустрии, психологията и рекламата. И така, от всичко казано по-горе, неоспоримо следва практическата стойност на теорията на графите, доказателството на което беше целта това учение.

Във всяка област на науката и технологиите се срещате с графики. Графиките са прекрасни математически обекти, с които можете да решавате математически, икономически и логически задачи, различни пъзели и да опростявате условията на задачи по физика, химия, електроника, автоматизация. Удобно е да се формулират много математически факти на езика на графиките. Теорията на графите е част от много науки. Теорията на графите е една от най-красивите и визуални математически теории. AT последните временаТеорията на графите намира все повече приложения в приложните проблеми. Появи се дори компютърната химия – сравнително млада област на химията, базирана на приложението на теорията на графите.

Молекулни графики, използвани в стереохимията и структурната топология, химията на клъстерите, полимерите и др., са ненасочени графики, които показват структурата на молекулите [приложение фиг.10]. Върховете и ръбовете на тези графики съответстват на съответните атоми и химически връзкимежду тях.

Молекулни графики и дървета: [приложение фиг.10] a, b - мултиграфи респ. етилен и формалдехид; in-mol. изомери на пентан (дървета 4, 5 са изоморфни на дърво 2).

В стереохимията на организмите най-много често се използват молекулярни дървета - основните дървета на молекулярните графики, които съдържат само всички върхове, съответстващи на C атоми. дърветата и установяването на техния изоморфизъм ви позволяват да определите кея. структури и намерете общия брой изомери на алкани, алкени и алкини

Протеинови мрежи

Протеинови мрежи - групи от физически взаимодействащи протеини, които функционират в клетката съвместно и по координиран начин, контролирайки взаимосвързаните процеси, протичащи в тялото [приложение фиг. единадесет].

Йерархична системна графиканаречено дърво. Отличителна чертана едно дърво е, че има само един път между всеки два от неговите върха. Дървото не съдържа цикли и цикли.

Обикновено дърво, представляващо йерархична система, има един главен връх, който се нарича корен на дървото. Всеки връх на дървото (с изключение на корена) има само един предшественик - обозначеният от него обект принадлежи към един клас от най-високо ниво. Всеки връх на дървото може да генерира няколко потомци - върхове, съответстващи на класове от по-ниско ниво.

За всяка двойка върхове на дървото има уникален път, който ги свързва. Това свойство се използва при намиране на всички предци, например по мъжка линия, на всяко лице, чието родословно дърво е представено под формата на родословно дърво, което е „дърво” и в смисъла на теорията на графите.

Пример за моето родословно дърво [приложение фиг.12].

Още един пример. Фигурата показва библейското родословно дърво [приложение фиг.13].

Разрешаване на проблем

1. Транспортна задача. Нека има база със суровини в град Краснодар, която трябва да бъде засадена в градовете Кримск, Темрюк, Славянск-на-Кубан и Тимашевск наведнъж, като същевременно харчите възможно най-малко време и гориво и се връщате обратно до Краснодар.

решение:

Първо, нека създадем графика на всички възможни маршрути. [приложение фиг.14], като се вземат предвид реалните пътища между тези населени места и разстоянието между тях. За да решим този проблем, трябва да създадем друга графика, дърво [приложение фиг.15].

За удобство на решението обозначаваме градовете с числа: Краснодар - 1, Кримск - 2, Темрюк - 3, Славянск - 4, Тимашевск - 5.

Това доведе до 24 решения, но имаме нужда само от най-кратките пътища. От всички решения само две са доволни, това са 350 км.

По същия начин е възможно и според мен е необходимо да се изчисли реалния транспорт от един местностна другите.

Логическа задача за трансфузия.В една кофа има 8 литра вода, като има две тенджери с вместимост 5 и 3 литра. необходимо е да се излеят 4 литра вода в петлитрова тенджера и да се оставят 4 литра в кофа, тоест да се налее вода по равно в кофа и голяма тенджера.

решение:

Ситуацията във всеки един момент може да се опише с три числа [приложение фиг.16].

В резултат получаваме две решения: едното на 7 хода, другото на 8 хода.

Заключение

Така че, за да се научите как да решавате проблеми, трябва да разберете какви са те, как са подредени, от какво съставни частите се състоят от това какви инструменти се използват за решаване на проблеми.

Решавайки практически задачи с помощта на теорията на графите, стана ясно, че на всяка стъпка, на всеки етап от тяхното решаване е необходимо да се прилага креативност.

От самото начало, на първия етап, се крие във факта, че трябва да можете да анализирате и кодирате състоянието на проблема. Вторият етап е схематична нотация, която се състои в геометрично представяне на графики, като на този етап елементът на творчеството е много важен, тъй като далеч не е лесно да се намерят съответствия между елементите на условието и съответните елементи на графиката .

При решаване на транспортна задача или задача за съставяне на родословно дърво, стигнах до извода, че графичният метод със сигурност е интересен, красив и визуален.

Бях убеден, че графиките се използват широко в икономиката, управлението и технологиите. Теорията на графите се използва и в програмирането.Това не беше обсъждано в тази статия, но мисля, че това е само въпрос на време.

В тази научна работа се разглеждат математическите графики, техните области на приложение, няколко проблема се решават с помощта на графики. Познаването на основите на теорията на графите е необходимо в различни области, свързани с управлението на производството, бизнеса (например диаграма на строителната мрежа, графици за доставка на поща). Освен това, докато работех върху научен труд, усвоих работата на компютър в текстов редактор на WORD. И така, задачи научна работазавършен.

И така, от всичко казано по-горе, неоспоримо следва практическата стойност на теорията на графите, доказателството на което беше целта на тази работа.

литература

Бердж К.Теория на графите и нейните приложения. -М.: ИИЛ, 1962г.

Кемени Дж., Снел Дж., Томпсън Дж.Въведение в крайната математика. -М.: ИИЛ, 1963г.

Оре О.Графики и тяхното приложение. -М.: Мир, 1965.

Харари Ф.Теория на графите. -М.: Мир, 1973.

Зиков А.А.Теория на крайните графики. -Новосибирск: Наука, 1969.

Березина Л.Ю.Графики и тяхното приложение. -М.: Образование, 1979. -144 с.

„Образователно списание Сорос” № 11 1996 г. (статия „Плоски графики”);

Гарднър М. "Математическо свободно време", М. "Мир", 1972 (глава 35);

Олехник С. Н., Нестеренко Ю. В., Потапов М. К. "Стари забавни проблеми", М. "Наука", 1988 (част 2, раздел 8; приложение 4);

Приложение

Ориз. 6

Ориз. 7

Ориз. осем

Приложение

Ориз. четиринадесет

Приложение

Освен това през последните 12 години от живота си Ойлер беше тежко болен, сляп и въпреки тежко заболяванепродължи да работи и твори. Статистическите изчисления показват, че Ойлер е правил средно едно откритие на седмица. Трудно е да се намери математически проблем, който да не е засегнат в произведенията на Ойлер. Всички математици от следващите поколения са учили с Ойлер по един или друг начин и не напразно известният френски учен P.S. Лаплас е казал: „Четете Ойлер, той е учител на всички нас. Лагранж казва: „Ако наистина обичате математиката, прочетете Ойлер; изложението на неговите произведения се отличава с удивителна яснота и точност“. Наистина, елегантността на изчисленията е доведена до най-висока степен от него. Кондорсе завърши речта си в академията в памет на Ойлер със следните думи: „И така, Ойлер спря да живее и смята!“ Да живееш, за да смяташ - колко скучно изглежда отвън! Прието е да си представяме математиката като суха и глуха за всичко светско, за това, от което се интересуват обикновените хора. С името на Ойлер е проблемът за три къщи и три кладенеца.

ТЕОРИЯ НА ГРАФИТЕ

1) Формализиране и изграждане на общ структурен модел на социален обект на различни нива на неговата сложност. Например организационни схеми, социограми, сравнение на системите за родство в различните общества, анализ на ролевата структура на групите и т.н. Можем да приемем, че ролевата структура включва три компонента: лица, длъжности (в опростен вариант - длъжности) и задачи, изпълнявани на тази позиция. Всеки компонент може да бъде представен като графика:

тегло а=1 2+2 7+3 4=28; 6=1 3+2 3=9 и т.н.

Задача : Трима съседи делят три кладенеца. Възможно ли е да се начертаят непресичащи се пътеки от всяка къща до всеки кладенец. Пътеките не могат да минават през кладенци и къщи (фиг. 1).

Ориз. 1. По проблема с къщите и кладенците.

V - P + G = 1, (*)

където B е общият брой върхове, P е общият брой ръбове, G е броят на многоъгълниците (лица).

б)

B - (P + 1) + (G + 1) \u003d B - P + G.

за да премахнете триъгълника ABC, трябва да премахнете два ръба, в нашия случай AB и BC;

за да премахнете триъгълник MKN, единият ръб трябва да бъде премахнат, в нашия случай MN.

(B - 1) - (P + 2) + (G -1) \u003d B - P + G.

По този начин премахването на един триъгълник не променя равенството.

Сега пристъпваме към решаването на проблема с три къщи и три кладенеца.

Изучаването на връзката между свойствата на веществата и тяхната структура е една от основните задачи на химията. Голям принос за нейното решение има структурната теория на органичните съединения, сред основателите на която е великият руски химик Александър Михайлович Бутлеров (1828-1886). Именно той за първи път установи, че свойствата на веществото зависят не само от неговия състав (молекулна формула), но и от реда, в който атомите в молекулата са взаимосвързани. Този ред беше наречен "химическа структура". Бутлеров прогнозира, че съставът C 4 Х 10 може да съответства на две вещества с различна структура - бутан и изобутан и потвърди това чрез синтезиране на последното вещество.

Идеята, че редът, в който са свързани атомите, е от ключово значение за свойствата на материята, се оказа много плодотворна. Тя се основава на представянето на молекули с помощта на графики, в които атомите играят ролята на върхове, а химическите връзки между тях са ръбовете, свързващи върховете. В графичното представяне дължините на връзките и ъглите между тях се игнорират. Молекулите С, описани по-горе 4 Х 10 са показани в следните колони:

Водородните атоми не са посочени в такива графики, тъй като тяхното местоположение може да се определи недвусмислено от структурата на въглеродния скелет. Припомнете си, че въглеродът в органичните съединения е четиривалентен, следователно в съответните графики не могат да се отклоняват повече от четири ръба от всеки връх.

Графиките са математически обекти, така че могат да се характеризират с числа. От това дойде идеята да се изрази структурата на молекулите чрез числа, които са свързани със структурата на молекулярните графики. Тези числа се наричат "топологични индекси" в химията. Чрез изчисляване на някакъв топологичен индекс за голям брой молекули може да се установи връзка между неговите стойности и свойствата на веществата и след това да се използва тази връзка, за да се предскажат свойствата на нови, все още несинтезирани вещества. Към днешна дата химици и математици са предложили стотици различни индекси, характеризиращи определени свойства на молекулите.

Методи за изчисляване на топологични индекси

Методите за изчисляване на топологични индекси могат да бъдат много разнообразни, но всички те трябва да отговарят на съвсем естествени изисквания:

1) всяка молекула има свой собствен, индивидуален индекс;

2) Молекулите с подобни свойства имат сходни индекси.

Нека да видим как се реализира тази идея на примера с наситени въглеводороди - алкани. Ключът към конструирането на много индекси е концепцията за "матрицата на разстоянията" D. Това е името на матрицата, чиито елементи показват броя на ръбовете, разделящи съответните върхове на молекулярния граф. Нека построим тази матрица за три изомерни въглеводорода от състав C 5 Х 12 . За да направим това, рисуваме техните молекулярни графики и преномерираме върховете (в произволен ред):

Диагоналните елементи на матрицата на разстоянията за въглеводороди са равни на 0. В първата колона връх 1 е свързан с връх 2 чрез един ръб, така че матричният елемент d 12 = 1. По същия начин, d 13 = 2, d 14 = 3, d 15 = 4. Първият ред в матрицата на разстоянията на нормален пентан е: (0 1 2 3 4). Пълни матрици на разстоянието за три графики:

химия на молекулите, топологичен индекс

Разстоянието между върховете не зависи от реда на тяхното изброяване, така че матриците на разстоянието са симетрични по отношение на диагонала.

Първият топологичен индекс, отразяващ структурата на молекулярна графика (G), е предложен през 1947 г. от Wiener. Определя се като сумата диагонални елементиматрица на разстояние плюс полусумата от нейните извъндиагонални елементи:

(1)

За горните графики, съответстващи на пентани C 5 Х 12 , индексът на Винер приема стойности от 20, 18 и 16. Може да се предположи, че описва степента на въглеводородно разклонение: най-големите стойности съответстват на най-малко разклонените въглеводороди. С увеличаване на дължината на въглеродния скелет индексът на Винер се увеличава, тъй като в матрицата на разстоянието има повече елементи. Статистическият анализ на примера на няколкостотин въглеводороди показа, че индексът на Винер корелира с някои физични свойства на алканите: точки на кипене, топлина на изпаряване, моларен обем.

Друг тип индекс не се основава на разстоянията между върховете, а на броя на най-близките съседи за всеки връх. Като пример, нека изчислим индекса на Randic, който се дефинира, както следва:

(2)

където vи- степента на i-тия връх, тоест броят на ръбовете, излизащи от него. За графиките по-горе индексът на Рандик е:

(3)

(4)

(5)

Този индекс също намалява с увеличаване на степента на разклоняване на въглеродния скелет и може да се използва за описание физични свойстваалкани.

Алканите са химически най-скучният вид органична молекула, тъй като не съдържат никакви "характеристики" - двойни и тройни връзки или атоми на елементи, различни от водород и въглерод (такива елементи се наричат хетероатоми). Въвеждането на хетероатоми в състава на молекулата може радикално да промени свойствата на веществото. По този начин, добавянето само на един кислороден атом превръща доста инертния газообразен етан С 2 Х 6 към течен етанол C 2 Х 5 OH, който проявява доста висока химична и биологична активност.

Следователно, в топологичните индекси на молекули, по-сложни от алканите, трябва да се вземе предвид наличието на множество връзки и хетероатоми. Това става чрез присвояване на определени числови коефициенти - "тегла" на върховете и ръбовете на графиките. Например, в матрицата на разстоянието, диагоналните елементи могат да бъдат дефинирани по отношение на ядрения заряд Zи(припомнете си, че за въглерод Z = 6):

(6)

Недиагоналните елементи се определят чрез сумиране по ръбове и всеки ръб, свързващ атоми със заряди Zии Зj, теглото е присвоено

(7)

където b е равно на реда на връзката между атомите (1 за единична връзка, 2 за двойна връзка, 3 за тройна връзка). За обикновени въглерод-въглеродни единични връзки, k = 1. Сравнете пропановите индекси на Винер C 3 Х 8 и три подобни по състав кислородсъдържащи вещества: пропилов алкохол C 3 Х 8 O, неговият изомерен изопропилов алкохол C 3 Х 8 О и ацетон С 3 Х 6 ох

За да направите това, ние изчисляваме матриците на разстоянието според посочените правила. В молекулярните графики ние обозначаваме всички атоми, с изключение на водородните атоми 1) Пропан

2) В молекулата на пропиловия алкохол кислородът е свързан с екстремния въглероден атом:

За единична C–O връзка, коефициентът на тежест е 36/(68) = 0,75. Диагонален елемент на матрицата, съответстващ на кислорода:

д 44 = 1 – 6/8 = 0.25.

За молекули, съдържащи хетероатоми, индексът на Винер престава да бъде цяло число. 3) В молекулата на изопропиловия алкохол кислородът е свързан със средния въглероден атом:

4) В ацетона редът на свързване на атомите е същият като в изопропиловия алкохол, но връзката между въглерод и кислород е двойна:

За двойната връзка C=O коефициентът на тежест е 36/(268) = 0,375

Както се вижда, добавянето на хетероатом към структурата на алканите води до увеличаване на индекса на Винер поради увеличаване на размера на матрицата на разстоянието. Добавянето на множество връзки и увеличаването на степента на разклоняване на молекулата намалява този индекс. Тези правила важат и за по-сложни молекули. Първоначално топологичните индекси са разработени само с цел прогнозиране на физикохимичните свойства на веществата. По-късно обаче те започнаха да се използват за решаване на други проблеми. Нека разгледаме някои от тях. Едно от приложенията на топологичните индекси е свързано с класификацията на органичните съединения и създаването на органични бази данни. Проблемът е да се намери такъв индекс, който едно към едно характеризира химическата структура и от който тази структура може да бъде възстановена. Необходимият индекс трябва да има добра разпознавателна способност, тоест да различава помежду си дори молекули, които са близки по структура. Тази задача е трудна, тъй като вече са известни повече от 20 милиона органични структури. Неговото решение, очевидно, ще бъде намерено в резултат на използването на съставни топологични индекси.

1 През последните десетилетия концепциите за топология и теория на графите станаха широко разпространени в теоретичната химия. Полезни са при търсене на количествени отношения "структура-свойство" и "структура-дейност", както и при решаване на графо-теоретични и комбинаторно-алгебрични задачи, които възникват в хода на събиране, съхраняване и обработка на информация за структура и свойства. вещества.

Графиките служат преди всичко като средство за представяне на молекули. В топологичното описание на молекула тя е изобразена като молекулярна графика (MG), където върховете съответстват на атоми, а ръбовете съответстват на химични връзки (теоретичен графичен модел на молекула). Обикновено в това представяне се разглеждат само скелетни атоми, например въглеводороди с "изтрити" водородни атоми.

Валентност химични елементиналага определени ограничения върху степените на върховете. Алкановите дървета (свързани графики, които нямат цикли) имат върхови степени (r), които не могат да надвишават четири (r = 1, 2, 3, 4).

Графиките могат да се задават в матричен вид, което е удобно при работа с тях на компютър.

Матрицата за съседство на върховете на прост граф е квадратна матрица A = [aσχ] с елементи aσχ = 1, ако върховете σ и χ са свързани с ръб, и σχ = 0 в противен случай. Матрицата на разстоянието е квадратна матрица D = с елементи dσχ, дефинирани като минималния брой ръбове (най-късото разстояние) между върховете σ и χ. Понякога се използват и матрици на съседство и разстояние от ръбове (A e и D e).

Видът на матриците A и D (A e и D e) зависи от метода на номериране на върховете (или ръбовете), което причинява неудобство при работа с тях. За характеризиране на графика се използват графични инварианти – топологични индекси (TI).

Брой пътеки с дължина едно

pi = xcc 0 = m = n-1

Брой пътища с дължина две

Брой тройки на съседни ръбове (с общ връх)

Числото на Винер (W), дефинирано като полусума от елементите на матрицата на разстоянията на разглежданата графика:

и т.н.

Методиката за изследване на връзката "структура-свойство" чрез топологични индекси в теоретико-графския подход включва следните стъпки.

Избор на обекти на изследване (учебна извадка) и анализ на състоянието на числените данни за свойството P за даден диапазон от съединения.

Избор на ТИ, като се вземе предвид тяхната дискриминираща способност, способност за корелация със свойства и др.

Изучаването на графичните зависимости "Свойство P - TI на графиката на молекулата", например P на n - броят на скелетните атоми, P на W - числото на Винер и т.н.

Установяване на функционална (аналитична) зависимост P = _DTI), напр.

P \u003d a (TI) + b,

P \u003d aln (TI) + b,

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

и т.н. Тук a, b, c са някои параметри (да не се бъркат с параметрите на адитивните вериги.), които трябва да бъдат определени.

Числени изчисления на Р, сравнение на изчислените стойности с експерименталните.

Прогнозиране на свойствата на съединения, които все още не са проучени или дори получени (извън тази проба).

Топологични индексисе използват и при изграждането на адитивни изчисления и схеми за прогнозиране. Те могат да се използват при разработването на нови лекарства, при оценка на канцерогенната активност на някои химични вещества, за прогнозиране на относителната стабилност на нови (все още несинтезирани) съединения и др.

Въпреки това, трябва да се помни, че изборът на TI често е случаен; те може да не отразяват важни структурни характеристики на молекулите или дублирана информация (получена с помощта на други индекси), а схемите за изчисление може да нямат солидна теоретична основа и да са трудни за интерпретация физикохимично.

Персоналът на катедрата физическа химияВ продължение на много години ТВГУ провежда изчислително и теоретично изследване по проблема „Връзка между свойствата на веществата и структурата на молекулите: математическо (компютърно) моделиране“. Фокусът е върху целенасоченото търсене на нови структури, алгоритми за решаване на редица графо-теоретични и комбинаторни проблеми, които възникват при събирането и обработката на информация за структурата и свойствата на веществата, създаването на експертни информационно-извличащи системи и бази данни, разработването на количествени методи за изчисляване и прогнозиране.

Изградихме адитивни схеми и открихме аналитични зависимости от вида P = Y(TI) за редица органични и други молекули. Съгласно получените формули са извършени числени изчисления на физикохимичните свойства на разглежданите съединения, s .

Библиография

Виноградова М.Г., Папулов Ю.Г., Смоляков В.М. Количествени корелации на "структурното свойство" на алканите. Схеми за изчисление на добавки. Твер, 1999. 96 с.
Химически приложениятопология и теория на графите / Изд. Р. Кинг. М.: Мир, 1987. 560 с.
Приложение на теорията на графите в химията / Изд. Н.С. Зефирова и С.И. Кучанова. Новосибирск: Наука, 1988. 306 с.
Станкевич М.И., Станкевич И.В., Зефиров Н.С. Топологични индекси в органичната химия // Успехи химии. 1988. Т.57, бр.3, с.337-366.
Виноградова М.Г., Салтикова М.Н. Графо-теоретичен подход при изследване на връзката между структурата и свойствата на алкилсиланите.// Фундаментални изследвания, 2009. No1. с. 17-19.
Виноградова M.G., Saltykova M.N., Efremova A.O., Malchevskaya O.A. Връзката между структурата и свойствата на алкилсиланите // Успехи на съвременните природни науки, No 1, 2010. С. 136-137.
Виноградова М.Г., Салтикова М.Н., Ефремова А.О. Съотношения "Структура - свойство" на алкилсиланите: теоретико-графски подход // Успехи на съвременните природни науки, № 3, 2010. С.141-142.

Библиографска връзка

Виноградова М.Г. ТЕОРИЯ НА ГРАФИТЕ В ХИМИЯТА // Международно списание за приложни и фундаментални изследвания. - 2010. - бр. 12. - С. 140-142;
URL: http://dev.applied-research.ru/ru/article/view?id=1031 (дата на достъп: 17.12.2019 г.). Предлагаме на вашето внимание списанията, издавани от издателство "Академия по естествена история"

Протеинови мрежи

Методи за изчисляване на топологични индекси

Библиографска връзка