МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів
Контакти
Тлумачний словник Авто Автоматизація Архітектура Астрономія Аудит Біологія Будівництво Бухгалтерія Винахідництво Виробництво Військова справа Генетика Географія Геологія Господарство Держава Дім Екологія Економетрика Економіка Електроніка Журналістика та ЗМІ Зв'язок Іноземні мови Інформатика Історія Комп'ютери Креслення Кулінарія Культура Лексикологія Література Логіка Маркетинг Математика Машинобудування Медицина Менеджмент Метали і Зварювання Механіка Мистецтво Музика Населення Освіта Охорона безпеки життя Охорона Праці Педагогіка Політика Право Програмування Промисловість Психологія Радіо Регилия Соціологія Спорт Стандартизація Технології Торгівля Туризм Фізика Фізіологія Філософія Фінанси Хімія Юриспунденкция |
|
|||||||
Основні поняття теорії графівГраф - це форма задання відношень. Граф - графічна структура, яка складається з множини елементів, що називається вершинами і множини відношень між цими елементами, які позначаються в цій структурі лініями, що називаються ребрами або дугами. Граф позначається буквою G, множина вершин V, множина відношень (дуг або ребер) – E, упорядкована пара G = (V, E). Нехай V = {v1, v2, ..., vn} і E = = {e1, e2...,em} При цьому елементи множини V зображають крапками на площині, а ребра (vi, vj ) — відрізками (прямолінійними або криволінійними), які з'єднують крапки vi та vj. Граф називається скінченним, якщо множини його вершин і ребер є скінченними. Кількість вершин графа n, а кількість ребер m. Граф, який містить n вершин та m ребер називають (n, m) - графом. Кількість вершин n(G) графа називають його порядком. Рис. 2.
Граф, який є моделлю симетричного відношення називається простим або симетричним графом, неорієнтованим графом. Граф G = (V, E), V = {v1, v2, v3 v4,, v5} і E = {e1, e2, e3, e4, e5, e6}. Ребра можуть задаватися ще послідовністю вершин E = {(v1, v5), (v1, v5), (v1, v3), (v2,,v3),(v2,v4), (v2, v5), (v4, v5)}. Граф, який показує наявність декількох відношень між однією і тією ж множиною елементів називається мультиграфом. Основна ознака мультиграфа – між деякими його вершинами існує декілька ребер або дуг. Граф, який є моделлю несиметричного відношення називається орієнтованим графом. Щоб змоделювати несиметричне відношення треба вказати направлення ребер. Направлення показують стрілочкою. Стрілочка, яка відображає несиметричне відношення називається дугою графа.
Рис. 3.
Таким чином для простого графа – граф складається з двох множин (вершин та ребер), для несиметричного графа – граф складається з двох множин (вершин та дуг). Два ребра називаються суміжними, якщо обидва вони є інцидентними одній вершині.
Рис. 4.
Якщо граф G = (V, Æ ) - множина відношень порожня (рис. 4, а). Але якщо множина вершин V - порожня, то порожньою є також множина Е. Такий граф називається порожнім. Такий граф називається нуль-графом і позначається Æ (рис. 4, b). Лінії, що зображають ребра графа, можуть перетинатися, але точки перетину не є вершинами; різні ребра можуть бути інцидентними одній і тій самій парі вершин (рис.2), такі ребра називаються кратними. Цей випадок відповідає наявності кількох однакових пар E = {(v1, v5), (v1, v5). Граф, що містить кратні ребра, називається мультиграфом. Ребро може з'єднувати деяку вершину саму з собою (рис. 5), таке ребро називається петлею. Цей випадок відповідає наявності в множині Е пар вигляду (v, v). Граф із петлями та кратними ребрами називається псевдографом. Рис. 5
Графи, які найчастіше розглядаються, є скінченними, тобто скінченні множини їхніх елементів (вершин і ребер), їх і розглядатимемо. Проте деякі поняття та результати, про які йтиметься, належать до довільних графів. Скінченний неорієнтований граф без петель і кратних ребер називається звичайним.. При зображенні орієнтованих графів напрямки ребер позначаються стрілками (рис. 3). Орієнтований граф може мати кратні ребра, петлі, а також петлі, що з'єднують ті ж самі вершини ребра, але у зворотних напрямках. Є специфічний вид ребра або дуги, які і в симетричному і в орієнтованому називається однаково петля - модель рефлексивного відношення Рис. 6.
Повний граф G = (V, E), n =_, m = _ . Кожне ребро ek Î E з’єднує пару вершин vi, vj Î V, які є його кінцями ці вершини граничні. Розрізняють початкову вершину з якої дуга виходить та кінцеву вершину , в яку дуга входить. Дві вершини (граничні вершини) які з’єднані двома або більше ребрами називаються кратними. В загальному випадку граф може містити і ізольовані вершини які не є граничними вершинами ні з одним з ребер. Кожному неорієнтованому графу можна поставити у відповідність орієнтований граф з тією самою множиною вершин, в якій кожне ребро замінено двома орієнтованими ребрами, що є інцидентними тим самим вершинам і мають зворотні напрямки. Таку відповідь будемо називати канонічною. Граф, що має як ребра, так і дуги, називається мішаним. Інцидентність. Задання графа за допомогою матриці інцидентності.
Задати граф означає задати множини його вершин і ребер, а також відношення інцидентності. Коли граф G — скінченний, тоді вершини даного графа v1 ,v2,,..., vn, а його ребра е1, е2,..., еm. Відношення інцидентності можна означити матрицею S= _, що має n рядків й т стовпців. Рядки відповідають вершинам графа, а стовпці відповідають його ребрам. Якщо вершина vi є інцидентною ребру ео, , то sij = 1, в іншому випадку sij = 0. Це матриця інцидентності звичайного графа G, яка є одним із способів його визначення (для графа на рис. 2). Sij = _
_ ;
У матриці інцидентності _ орієнтованого графа G, якщо вершина vi —початок ребра ej, то sij = 1; якщо vi: - кінець ej, то sij = -1. Кількість одиниць у рідку дорівнює степені відповідній вершині (для орграфа кількість позитивних одиниць визначає позитивну степінь, а кількість від’ємних одиниць - від’ємну степінь). Нульовий рядок відповідає ізольованій вершині, а нульовий стовпець - петлі. Треба мати на увазі, що нульовий стовпець матриці інцидентності лише вказує на присутність петлі, але не містить відомостей про те, з якою вершиною зв’язана ця петля. Sij = _
Sij = _.
Читайте також:
|
||||||||
|