МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів
Контакти
Тлумачний словник Авто Автоматизація Архітектура Астрономія Аудит Біологія Будівництво Бухгалтерія Винахідництво Виробництво Військова справа Генетика Географія Геологія Господарство Держава Дім Екологія Економетрика Економіка Електроніка Журналістика та ЗМІ Зв'язок Іноземні мови Інформатика Історія Комп'ютери Креслення Кулінарія Культура Лексикологія Література Логіка Маркетинг Математика Машинобудування Медицина Менеджмент Метали і Зварювання Механіка Мистецтво Музика Населення Освіта Охорона безпеки життя Охорона Праці Педагогіка Політика Право Програмування Промисловість Психологія Радіо Регилия Соціологія Спорт Стандартизація Технології Торгівля Туризм Фізика Фізіологія Філософія Фінанси Хімія Юриспунденкция |
|
|||||||
Суміжність у графах
Дві вершини та називаються суміжними, якщо вони є граничними вершинами ребра ek. Відношення суміжності на множині вершин графа дозволяє представити кожне ребро як пару суміжних вершин: для неорієнтованих графів – неупорядковану, тобто ; для орграфів – упорядковану , де та - відповідно початкова та кінцева вершина дуги ek. Якщо граф заданий множиною вершин V та відношенням суміжності між ними, то граф може бути повністю представленим матрицею суміжності. Матриця суміжності – це квадратна матриця розміром , де р – число вершин графа. Кожний елемент матриці дорівнює числу кратних ребер, з’єднуючих вершини та , а для орграфа – числу суворо паралельних дуг, направлених від вершини до вершини . Для графів(рис. 8.3 та 8.4, а) отримано матриці суміжності, що представлено відповідно на рис. 8.5
Рис. 8.5. Матриці суміжності графів
Для орієнтованого графа рядок відповідає початковій вершині дуги. Для неорієнтованого графа матриця суміжності завжди симетрична відносно головної діагоналі, а для орграфу в загальному випадку – несиметрична. При цьому кожному ребру відповідає пара ненульових елементів, симетричних відносно головної діагоналі, дузі – ненульовий елемент матриці, петлі – ненульовий елемент головної діагоналі, ізольованій вершині – порожній рядок та порожній стовпець. Для зваженого графа без кратних ребер - й елемент матриці суміжності дорівнює вазі дуги або ребра. Матриця суміжності повністю (однозначно) визначає граф без петель та кратних ребер. Матриця суміжності зваженого графу, в якому вага ребер дорівнює інтенсивності поїздопотоків, представляє відому «шахматку», що використовується при плануванні експлуатаційної роботи залізничного підрозділу.
|
||||||||
|