Граф (математика): Разлика между версии

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

 

Граф G=(V, E) се състои от крайно, непразно множество на върховете V, и множество на ребрата Е. n е броя на върховете V, а е – броя на ребрата Е. ако ребрата са представени във вид на подредени двойки (v, w), то графа се нарича ориентиран, v е начало, а w – край на дъгата (v, w). Ако ребрата не са наредени двойки, а множества от два елемента, то граф се нарича

неориентиран. (заб. В ориентирания граф може да има ребро (а, а), а в неориентирания – не).

Максималния породен свързан граф, съдържащ даден

възел.

 

== Източници ==