Графи математика

Графи


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=n2 за ориентиран.

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

Път в граф – списък от върхове (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. Представяне



Други реферати:
Спиридон Палаузов. Приноси в областта на бълг. история
Фактори за развитието на българската историопис през 60-те и 70-те години на 19в. (третият период)
Христианизация на Българския народ през управлението на хан(княз) Борис I Михаил (852-889)
Цар на всички българи и ромеи–Симеон І
Управление на БЗНС


Изтегли реферата



Управление на БЗНС - Facebook Image
Сайтът се поддържа от DH Studio | pomagalo1.com © 2012 | Общи условия