Тэорыя графаў Гісторыя | Літаратура | Навігацыя
Тэорыя графаўДыскрэтная матэматыка
матэматыкіграфзадачы аб Кёнігсбергскіх мастахаб расстаноўцы ферзёў на шахматнай дошцызадача 4 фарбаўЛ. Эйлерэлектрычных ланцугоўхімічных рэчываўмалекулярныхграфамітапалогііалгебрытэорыі лікаўтэорыі імавернасцікібернетыківылічальнай тэхнікіБеларусіБДУІнстытуце матэматыкіІнстытуце тэхнічнай кібернетыкі
(function()var node=document.getElementById("mw-dismissablenotice-anonplace");if(node)node.outerHTML="u003Cdiv class="mw-dismissable-notice"u003Eu003Cdiv class="mw-dismissable-notice-close"u003E[u003Ca tabindex="0" role="button"u003Eне паказвацьu003C/au003E]u003C/divu003Eu003Cdiv class="mw-dismissable-notice-body"u003Eu003Cdiv id="localNotice" lang="be" dir="ltr"u003Eu003Ccenteru003Eu003Cspan class="plainlinks"u003EСачыце за Беларускай Вікіпедыяй на u003Ca href="https://www.facebook.com/be.wikipedia" rel="nofollow"u003Eu003Cimg alt="Facebook icon.svg" src="//upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Facebook_icon.svg/14px-Facebook_icon.svg.png" decoding="async" width="14" height="14" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Facebook_icon.svg/21px-Facebook_icon.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Facebook_icon.svg/28px-Facebook_icon.svg.png 2x" data-file-width="256" data-file-height="256" /u003Eu003C/au003E u003Cbu003Eu003Ca rel="nofollow" class="external text" href="https://www.facebook.com/be.wikipedia"u003EFacebooku003C/au003Eu003C/bu003E, u003Ca href="http://twitter.com/#!/be_wikipedia" rel="nofollow"u003Eu003Cimg alt="Twitter.svg" src="//upload.wikimedia.org/wikipedia/commons/thumb/d/db/Twitter.svg/14px-Twitter.svg.png" decoding="async" width="14" height="14" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/d/db/Twitter.svg/21px-Twitter.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/d/db/Twitter.svg/28px-Twitter.svg.png 2x" data-file-width="256" data-file-height="256" /u003Eu003C/au003E u003Cbu003Eu003Ca rel="nofollow" class="external text" href="http://twitter.com/#!/be_wikipedia"u003ETwitteru003C/au003Eu003C/bu003E, u003Ca href="https://www.instagram.com/be.wikipedia/" rel="nofollow"u003Eu003Cimg alt="Instagram.svg" src="//upload.wikimedia.org/wikipedia/commons/thumb/9/96/Instagram.svg/14px-Instagram.svg.png" decoding="async" width="14" height="14" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/9/96/Instagram.svg/21px-Instagram.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/9/96/Instagram.svg/28px-Instagram.svg.png 2x" data-file-width="512" data-file-height="512" /u003Eu003C/au003E u003Cbu003Eu003Ca rel="nofollow" class="external text" href="https://www.instagram.com/be.wikipedia/"u003EInstagramu003C/au003Eu003C/bu003E і u003Ca href="http://vk.com/be.wikipedia" rel="nofollow"u003Eu003Cimg alt="V Kontakte Russian V.png" src="//upload.wikimedia.org/wikipedia/commons/thumb/4/47/V_Kontakte_Russian_V.png/14px-V_Kontakte_Russian_V.png" decoding="async" width="14" height="14" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/47/V_Kontakte_Russian_V.png/21px-V_Kontakte_Russian_V.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/47/V_Kontakte_Russian_V.png/28px-V_Kontakte_Russian_V.png 2x" data-file-width="415" data-file-height="415" /u003Eu003C/au003E u003Cbu003Eu003Ca rel="nofollow" class="external text" href="http://vk.com/be.wikipedia"u003EУ Кантакцеu003C/au003Eu003C/bu003Eu003C/spanu003E! u003Cbr /u003EТаксама ёсць старонка u003Ca rel="nofollow" class="external text" href="https://www.facebook.com/groups/1645396869043051/"u003EWikimedia Community User Group Belarusu003C/au003E на u003Ca href="/wiki/Wikimedia_Community_User_Group_Belarus" title="Wikimedia Community User Group Belarus"u003Eu003Cimg alt="Facebook icon.svg" src="//upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Facebook_icon.svg/14px-Facebook_icon.svg.png" decoding="async" width="14" height="14" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Facebook_icon.svg/21px-Facebook_icon.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Facebook_icon.svg/28px-Facebook_icon.svg.png 2x" data-file-width="256" data-file-height="256" /u003Eu003C/au003E u003Cbu003Eu003Ca rel="nofollow" class="external text" href="https://www.facebook.com/groups/1645396869043051/"u003EFacebooku003C/au003Eu003C/bu003Eu003C/centeru003Enu003C/divu003Eu003C/divu003Eu003C/divu003E";());
Тэорыя графаў
Jump to navigation
Jump to search
Тэо́рыя гра́фаў — раздзел матэматыкі, які вывучае аб'екты на аснове геаметрычнага падыходу.
Асноўнае паняцце тэорыі графаў — граф: мноства пунктаў (вяршынь) і мноства сувязей (рэбраў, дуг), якія злучаюць некаторыя (або ўсе) пары вяршынь.
Напрыклад, сетка чыгунак, аўтамабільных (ці іншых) дарог з пазначэннем на дугах адлегласцей паміж населенымі пунктамі або іх прапускных здольнасцей.
Тэорыя графаў выкарыстоўваецца ў тэорыі перадачы інфармацыі, тэорыі транспартных сетак, камп'ютарнай графіцы, аўтаматызацыі праектавання і інш.
Гісторыя |
Першыя задачы тэорыі графаў былі звязаны з рашэннем галаваломак і матэматычных забаўляльных задач (напрыклад, задачы аб Кёнігсбергскіх мастахberu, аб расстаноўцы ферзёў на шахматнай дошцыberu, аб перавозках, кругасветным падарожжы, задача 4 фарбаўberu і іншыя).
Адным з першых вынікаў у тэорыі графаў быў крытэрый існавання абходу графа без паўтораў рэбраў (Л. Эйлер, 1736).
У 19 ст. з'явіліся работы, у якіх пры рашэнні практычных задач былі атрыманы важныя вынікі ў тэорыі графаў (задачы пабудавання электрычных ланцугоў, падліку хімічных рэчываў з рознымі тыпамі малекулярных злучэнняў і іншыя).
У 20 ст. задачы, звязаныя з графамі, з'явіліся ў тапалогіі, алгебры, тэорыі лікаў, тэорыі імавернасці і іншых.
Найбольшае развіццё тэорыя графаў атрымала з 1950-х гадоў у сувязі са станаўленнем кібернетыкі і развіццём вылічальнай тэхнікі.
На Беларусі даследаванні па тэорыі графаў вядуцца ў БДУ (уплыў розных параметраў на уласцівасці графаў), Інстытуце матэматыкі (розныя прадстаўленні графаў, алгарытмічныя аспекты тэорыі графаў), Інстытуце тэхнічнай кібернетыкі (графы ў задачах аптымальнага ўпарадкавання) НАН Беларусі.
Літаратура |
- Графаў тэорыя // Беларуская энцыклапедыя: У 18 т. Т. 5: Гальцы — Дагон / Рэдкал.: Г. П. Пашкоў і інш. — Мн.: БелЭн, 1997. С. 411.
- Лекции по теории графов. М., 1990.
Катэгорыі:
- Тэорыя графаў
- Дыскрэтная матэматыка
(window.RLQ=window.RLQ||[]).push(function()mw.config.set("wgPageParseReport":"limitreport":"cputime":"0.024","walltime":"0.039","ppvisitednodes":"value":513,"limit":1000000,"ppgeneratednodes":"value":0,"limit":1500000,"postexpandincludesize":"value":5413,"limit":2097152,"templateargumentsize":"value":1288,"limit":2097152,"expansiondepth":"value":6,"limit":40,"expensivefunctioncount":"value":3,"limit":500,"unstrip-depth":"value":0,"limit":20,"unstrip-size":"value":0,"limit":5000000,"entityaccesscount":"value":0,"limit":400,"timingprofile":["100.00% 23.972 1 -total"," 82.05% 19.670 3 Шаблон:Нп4"," 38.63% 9.261 6 Шаблон:Не_перакладзена_4/lang"," 16.98% 4.071 1 Шаблон:Крыніцы/БелЭн"],"cachereport":"origin":"mw1262","timestamp":"20190409091721","ttl":2592000,"transientcontent":false););"@context":"https://schema.org","@type":"Article","name":"u0422u044du043eu0440u044bu044f u0433u0440u0430u0444u0430u045e","url":"https://be.wikipedia.org/wiki/%D0%A2%D1%8D%D0%BE%D1%80%D1%8B%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%B0%D1%9E","sameAs":"http://www.wikidata.org/entity/Q131476","mainEntity":"http://www.wikidata.org/entity/Q131476","author":"@type":"Organization","name":"Contributors to Wikimedia projects","publisher":"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":"@type":"ImageObject","url":"https://www.wikimedia.org/static/images/wmf-hor-googpub.png","datePublished":"2016-02-14T11:01:16Z","dateModified":"2016-02-14T11:01:16Z"(window.RLQ=window.RLQ||[]).push(function()mw.config.set("wgBackendResponseTime":136,"wgHostname":"mw1262"););
