Графи

1. Основни понятия

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

Математическо определение за граф

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

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

Степен на връх броя на върховете пряко свързани с върха.

Пълен граф граф с пълен брой дъги. Степента на всеки връх тогава е n-1 за неориентиран и n за ориентиран, а общия брой дъги е=n*(n-1)/2 за неориентиран и e=n² за ориентиран.

Граф с тегла на всеки възел и/или дъга съответства някаква стойност.

Път в граф списък от върхове (v1, v2, ..., vn), всеки два съседни от които са свързани с дъга. Казваме, че пътят започва от v1 и завършва в vn или, че има път от v1 до vn. Дължината на път в граф без тегла е равна на броя ребра, през които той минава и за пътя (v1, v2, ..., vn) е равна на n-1. За граф с тегладължината на пътя (v1, v2, ..., vn) е равна на сумата от теглата на ребрата, през които преминава пътя.

Прост път път, в който няма повтарящи се върхове.

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

Ацикличен граф граф, който няма цикли.

За неориентирани графи се използват и следните понятия:

Свързана компонента на граф G=(V, E) е подграф G1=(V1, E1), така че между всеки два върха от V1 има път, който се състои от ребра е на Е1 и няма път между които и да е два върха, единия от които принадлежи на V1, а другия не принадлежи.

Свързан граф в него ива път между всяка двойка върхове, състои се от една компонента.

Многосвързан граф състои се от две или повече свързани компоненти.

2. Представяне