![]() КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Неорієнтовані графи
Іноді граф розглядають без урахування орієнтації дуг, тоді його називають неорієнтованим графом. Поняття "дуга", "шлях" і "контур" для неорієнтованого графа заміняються поняттями "ребро", "ланцюг", "цикл". Ребро - це відрізок, що з'єднує 2 вершини. Ланцюг - послідовність ребер. Цикл - ланцюг, у якого початкова і кінцева вершини збігаються. Описати неорієнтований граф можна шляхом завдання пари множин (Х, U), де Х - множина вершин; U - множина ребер. Проте більш зручним є опис неорієнтованого графа за допомогою матриці суміжності або інцидентності, що будуються аналогічно відповідним матрицям для орієнтованих графів з тією різницею, що не робиться різниця між дугами, які входять у вершину і виходять з неї. При цьому вершини х і y називають суміжними, якщо існує ребро, що їх з'єднує, і це ребро називається інцидентним вершинам х і у.
Ступенем вершини х, що позначається deg(x) або dx, називають число ребер, інцидентних вершині х. Так, для графа на рис.2.5 маємо d1=2, d2=2, d3=3, d4=1, d5=0. Якщо dx=1, то вершину називають тупиковою; якщо dx=0 то вершину називають ізольованою.
Доказ теореми випливає з того, що кожне ребро добавляє одиницю до ступеня кожної з 2-х вершин, що воно з'єднує, тобто добавляє 2 до суми ступенів уже наявних вершин. Таким чином у кожному графі число вершин непарного ступеня парне. Для неорієнтованого графа поняття "підграф" і "частковий граф" аналогічні відповідним поняттям для орієнтованого графа. З поняттям неорієнтованого графа пов'язана важлива характеристика, що називається зв'язністю графа. Кажуть, що граф зв'язний, якщо будь-які дві його вершини можна з'єднати ланцюгом. Якщо граф G не зв'язковий, то його можна розбити на такі підграфи Gi, що усі вершини в кожному підграфі зв'язні, а вершини з різноманітних підграфів не зв'язні. Такі підграфи Gi називають компонентами зв'язності графа G. Якщо з графа (рис.2.5) виключити ізольовану вершину 5, то отриманий граф буде зв'язним. Граф на рис.2.6 не зв'язний і має дві компоненти зв'язності. Його можна перетворити в зв'язний, додавши ребро (міст), що з'єднує вершини 3 і 5 (штрихова лінія). Видалення моста перетворює зв'язний граф у незв'язний. Для того щоб визначити зв'язність орієнтованого графа, не потрібно звертати увагу на орієнтацію дуг. Граф, зображений на рис.2.6, є не зв'язним.
Деревом називають кінцевий зв'язковий неорієнтований граф, що не має циклів. Якщо дана множина вершин a, b, c,..., то дерево можна побудувати таким чином. Одну з вершин, наприклад а, приймемо за початкову і назвемо її
Дата добавления: 2014-11-29; Просмотров: 7058; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |