Skip to main content

Теория на графите История | Дефиниции | Приложения на графите | Навигацияредактирате

Multi tool use
Multi tool use

Теория на графите


математикатаграфитемножествоОйлерКьонигсбергските мостове1736математикатадърветатаАнглияКьониг19361912












Теория на графите




от Уикипедия, свободната енциклопедия






Направо към навигацията
Направо към търсенето





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



Фиг. 1



Фиг. 2


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



История |


Първата работа по теория на графите е статията на Ойлер за Кьонигсбергските мостове (1736). Тя обаче остава единствена в течение на 100 години. Интересът към този клон от математиката и към частния случай – дърветата, се възражда около средата на 19 век и е съсредоточен главно в Англия. Върху развитието на Теорията на графите оказват забележимо влияние естествените науки, тъй като тя има приложения в различни области – при изследването на електрическите вериги, моделите на кристалите, структурата на молекулите, в теорията на игрите и програмирането, в биологията и психологията и т.н.


Терминът е употребен най-напред в статия на Кьониг, а след това и в монографията му „Theorie der endlichen und unendlichen Graphen“ („Теория на крайните и безкрайните графи“, 1936), но самият Кьониг го е заимствал от статия на Шур (1912), в която граф се нарича фигура, състояща се от няколко числа или точки, някои двойки от които са съединени помежду си.



Дефиниции |


Видове графи:


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

  • неориентиран

  • претеглен (тегловен) – на всяко ребро е присвоена някаква стойност – тегло.


  • мултиграф – възможно е повече от едно ребро да свързва два върха (при ориентиран граф – възможно е тези ребра, освен това, да са ориентирани еднакво).


Приложения на графите |



Фиг. 3 – Пример за графи, използвани в графовата база от данни Neo4j.


В практическите задачи, графите представляват модел на реален обект. Ето няколко класически примера за реални обекти представяни чрез граф:


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

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

  • компютърна мрежа – компютрите (върхове) и свързващите ги информационни канали (ребра).

  • в графови бази от данни – като Neo4j (вижте фиг. 3).









Взето от „https://bg.wikipedia.org/w/index.php?title=Теория_на_графите&oldid=8333663“.










Навигация



























(window.RLQ=window.RLQ||[]).push(function()mw.config.set("wgPageParseReport":"limitreport":"cputime":"0.048","walltime":"0.091","ppvisitednodes":"value":99,"limit":1000000,"ppgeneratednodes":"value":0,"limit":1500000,"postexpandincludesize":"value":5073,"limit":2097152,"templateargumentsize":"value":164,"limit":2097152,"expansiondepth":"value":5,"limit":40,"expensivefunctioncount":"value":0,"limit":500,"unstrip-depth":"value":0,"limit":20,"unstrip-size":"value":0,"limit":5000000,"entityaccesscount":"value":0,"limit":400,"timingprofile":["100.00% 63.106 1 -total"," 90.32% 56.996 1 Шаблон:Без_източници"," 82.65% 52.155 1 Шаблон:Ambox"," 9.47% 5.975 1 Шаблон:Математика-мъниче"," 5.34% 3.367 1 Шаблон:Шаблон_на_мъниче"],"scribunto":"limitreport-timeusage":"value":"0.016","limit":"10.000","limitreport-memusage":"value":794841,"limit":52428800,"cachereport":"origin":"mw1257","timestamp":"20190415065425","ttl":2592000,"transientcontent":false););"@context":"https://schema.org","@type":"Article","name":"u0422u0435u043eu0440u0438u044f u043du0430 u0433u0440u0430u0444u0438u0442u0435","url":"https://bg.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%BD%D0%B0_%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%82%D0%B5","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":"u0424u043eu043du0434u0430u0446u0438u044f u0423u0438u043au0438u043cu0435u0434u0438u044f","logo":"@type":"ImageObject","url":"https://www.wikimedia.org/static/images/wmf-hor-googpub.png","datePublished":"2004-08-03T20:11:11Z","dateModified":"2018-01-12T08:25:51Z","image":"https://upload.wikimedia.org/wikipedia/commons/5/5b/6n-graf.svg"(window.RLQ=window.RLQ||[]).push(function()mw.config.set("wgBackendResponseTime":145,"wgHostname":"mw1242"););CLFangLbR4yGdksDxZ87vuSNTM9egpRqt9fm KcWDCws7R DFPFK,JC47nMl9h1RaNFsjxb,Wi7BVi3Vrg9PmGv6f4v,n,c16XDXv
UrY ZY,8g

Popular posts from this blog

Aidahas Turinys Geografija | Klimatas | Istorija | Demografija | Religija | Ekonomika | Galerija | Naršymo meniuidaho.gov

Creating centerline of river in QGIS? The 2019 Stack Overflow Developer Survey Results Are In Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)Finding centrelines from polygons in QGIS?Splitting line into two lines with GRASS GIS?Centroid of the equator and a pointpostgis: problems creating flow direction polyline; not all needed connections are drawnhow to make decent sense from scattered river depth measurementsQGIS Interpolation on Curved Grid (River DEMs)How to create automatic parking baysShortest path creation between two linesclipping layer using query builder in QGISFinding which side of closest polyline point lies on in QGIS?Create centerline from multi-digitized roadway lines Qgis 2.18Getting bathymetric contours confined only within river banks using QGIS?

Typsetting diagram chases (with TikZ?) Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)How to define the default vertical distance between nodes?Draw edge on arcNumerical conditional within tikz keys?TikZ: Drawing an arc from an intersection to an intersectionDrawing rectilinear curves in Tikz, aka an Etch-a-Sketch drawingLine up nested tikz enviroments or how to get rid of themHow to place nodes in an absolute coordinate system in tikzCommutative diagram with curve connecting between nodesTikz with standalone: pinning tikz coordinates to page cmDrawing a Decision Diagram with Tikz and layout manager