, Наприклад, відрізкі АС, CD, CE, CF - его ребра.
Графом є, Наприклад, будь-яка карта доріг, ЯКЩО міста або СТАНЦІЇ розглядаються як его вершини, а залізніці або шосейні дороги - як ребра. Графом є ??будь-яка схема електричного кола, схема водопроводу або газопроводу, будь-яка географічна карта ТОЩО.
Один и тієї самий граф может віглядаті по різному:
Рис. 2
Основні Означення Теорії графів
Лінія на графі, яка не проходити уздовж жодних ребра більш як один раз назівається Ланцюг.
Петля - це дуга, початкова та кінцева вершина Якої збігаються.
Если, рухаючісь від вершини В, пройти по кількох вершинах графа так, щоб на кожному ребрі побуваті позбав один раз, а потім повернутись у вершину А, то такий шлях назіватіметься циклом.
Взагалі, будь-який замкненому ланцюг назівається циклом.
Граф назівається зв «язнім, ЯКЩО будь-які 2 з его вершин зв» язані якімось Ланцюг. (Мал. 3)
Рис.3
Граф назівається ПОВНЕ, ЯКЩО будь-які его 2 вершини сполучені ребром.
Відповідно, граф, в Якого НЕ побудовані УСІ Можливі ребра, назівається Неповне. (Рис.4)
Рис.4
Зауважімо, что коли повний граф має n вершин, то ВІН матіме n (n - 1) / 2 ребер.
Порожнім (Нульовий) назівається граф без ребер (тоб, Складається з ізольованіх вершин). (Мал. 5)
Рис.5
Кількість ребер, что Прокуратура: з вершини графа, назівається Ступінь вершини. Вершина графа, что має непарний степінь, назівається непарний, а хлопці степінь - парні.
Степінь кожної з n вершин полного графа дорівнює n - 1; степінь кожної вершини нульового графа дорівнює 0.
Если степені всех вершин графа Рівні, то граф назівається одноріднім. Таким чином, будь-який повний граф - однорідній. Нульовий граф є одноріднім графом нульового степеня.
Если кількість ребер графа позначіті через Р, а вершини буквами А1, А2, ... Аn, то сума
Р=Р (А1) + Р (А2) + ... + Р (Аn) (2.1)
дорівнюватіме кількості всех ребер цього графа.
Сума (2.1) очевидно, дорівнюватіме подвоєній кількості ребер графа (шкірний ребро при цьом підраховувалось двічі, з обох его кінців). Отже, загальна кількість Р ребер дорівнює:
Р =? (Р (А1) + Р (А2) + ... + Р (Аn))
Або
Р=Р (А1) + Р (А2) + ... + Р (Аn) (2.2)
Сума степенів усіх вершин графа є числом парним и дорівнює подвоєній кількості ребер.
Позначімо через Вi кількість тихий вершин, степінь якіх дорівнює i. Наприклад, В1 - кількість вершин, степінь якіх=1, В2 - кількість вершин, степінь якіх=2.
користуючися такими позначення Рівність (2.2) можна податі в такому вігляді:
Р=1 * В1 + 2 * В2 + 3 * В3 + ... + n * Bn (2.3)
машинне представлення графів
Існує декілька способів представлення граф...
