Граф (математика): Разлика между версии
Изтрито е съдържание Добавено е съдържание
Редакция без резюме |
Gborisov90 (беседа | приноси) мРедакция без резюме |
||
Ред 1:
{{към пояснение|Граф|Граф (пояснение)}}
[[Картинка:6n-graf.svg|мини|Диаграма на неориентиран граф със шест върха и седем ребра]]
'''''Графът е нелинейна, динамична структура от данни, изградена от възли (върхове) и връзки между тях наречени ребра (дъги).'''''
В този смисъл графът се дефинира като съвкупност от две
множества – множеството на възлите '''V''' и
множеството на ребрата '''Е''': '''G(V,E)''' .
'''Е''' може да се
представи като множество от двойки '''(x,y)''', където '''x''' и '''y''' принадлежат на '''V. x''' и '''y''' се наричат съседни възли'''.''' Когато двойката е наредена, т.е. '''(x,y)≠ (y,x)''', то реброто се нарича '''ориентирано'''. Когато двойката е ненаредена, т.е. '''(x,y)= (y,x)''', то реброто се нарича '''неориентирано'''. Всяко неориентирано ребро може да се представи като съвкупност от две
ориентирани ребра с различни посоки.
*
<!-- Раграничението на графите на [[ориентиран граф|ориентирани]] и [[неориентиран граф|неориентирани]] е от голямо теоретично значение, … -->
== Определение ==
Граф, множеството от чиито върхове е [[празно множество|празното множество]], се нарича ''нулев граф''. Естествено, за него и множеството от ребрата също е празното множество. Друг тривиален случай е налице, когато множеството от върховете на графа се състои само от един елемент. И в този случай множеството на ребрата е празно.
Line 35 ⟶ 42:
== Формули ==
Ако от степента на всеки връх е n, то броя на ребрата в този граф е �1�. -->== Понятия, свързани с графи<br> ==
== Видове графи ==
'''Неориентиран''' –
'''Ориентиран''' –
'''Пълен граф''' – граф, за който има ребра между всеки два върха, където n е броя на възлите.
'''Празен граф''' – граф на който всички възли са висящи (няма нито един клон) G(V,E), E – празно множество.Брой ребра = 0
'''Допълнителен граф''' – Възлите на основния и допълнителния граф съвпадат. Ако в основния граф има път между два възела, то в допълнителния няма и обратно. е допълнителен за G(V,E) ако V<sub>1</sub>ºV и Е<sub>1</sub> Ç Е = празно множество.
'''Регулярен граф''' –всички възли са от еднаква степен. (Пълният граф е регулярен със степен = n-1.)
'''Теглови граф''' – на възлите и/или на клоните са присвоени тегла.
'''Равнинен граф''' – може да се изобрази в равнината без да се пресичат
ребра.
'''Двудялов граф''' –
всички възли са разделени на две подмножества – и V<sub>1</sub> и V<sub>2</sub>
и всеки възел има свързващи ребра само към възли от другото подмножество.
'''Свързан граф''' – граф за който между всички възли има път.
'''Несвързан граф''' –граф, за който съществуват възли без път между тях. Всеки несвързан граф може да се представи като съвкупност от
краен брой свързани графи, наречени компоненти.
'''Компонента''' – максималния породен свързан граф, съдържащ даден
възел.
== Източници ==
| |||