джерел і споживачів у енергосистемах. <В
Частина 1
Теоретична частина до курсового проекту
В
Глава1
Теорія графів
В
Поняття графа
В
Графом G (X, U) називається сукупність двох об'єктів деякого безлічі X і відображення цієї множини в себе Г .
При геометричному поданні графа елементи безлічі Х зображуються точками площини і називаються вершинами графа. Лінії, що з'єднують будь-які пари точок x і y , з яких у є відображенням х , називаються дугами графа. Дуги графа мають напрям, позначуване стрілкою, яка спрямована вістрям від елемента х до його відображенню у .
В
Вершини і лінії графа
В
Дві вершини А і В є граничними вершинами дуги, якщо А - початок дуги, а В її кінець.
Суміжними називаються різні дуги, що мають загальну граничну точку. Дві вершини х і у суміжні, якщо вони різні й існує дуга, що йде від однієї з них до іншої. p> Вершина називається ізольованою, якщо вона не з'єднана дугами з іншими вершинами графа. p> Якщо дуга U виходить з вершини х або заходить у х , то дуга U називається инцидентной вершині х , а вершини х инцидентной дузі U . Загальне число дуг, инцидентной вершині х , є ступенем вершини х Р (х) . Вершини, ступінь яких Р (х)> 2 , називаються вузлом, а зі ступенем Р (х) <2 - антіузлом.
полустепені заходу Р + (х) вершини х - кількість дуг, що заходять у дану вершину. Полустепені результату Р - (х) - кількість дуг, що виходять з даної вершини.
Послідовність ліній на графі
В
Шлях - послідовність дуг ( U 1 , U 2 , ... U n ), в якій кінець кожної попередньої дуги збігається з початком наступної. Шлях може бути кінцевим і нескінченним. p> Шлях називається простим, якщо в ньому ніяка дуга не зустрічається двічі, і складовим, якщо будь-яка з дуг зустрічається більше одного разу.
Шлях, в якому жодна з вершин не зустрічається більше одного разу, називається елементарним шляхом.
Гамильтонов шлях - шлях проходить через всі вершини, але тільки по одному разу,
Еллер шлях - шлях містить всі дуги графа, при цьому тільки по одному разу.
Довжина шляху - число дуг послідовності ( U 1 , U 2 , ... U n ).
Гілка - шлях, в якому початкова та кінцева вершини є вузлами. Дуга (x, y) називається замикає, якщо видалення її не приводить до анулювання шляху з x в y.
Контур - кінцевий шлях, починається і закінчується в одній і тій же вершині. Контур одиничної довжини називаєть...
