МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
|||||||
Основні визначенняРебро в графі G може бути орієнтованим і мати почало|розпочало,зачало| і кінець. Таке ребро називається дугою, а граф, що містить|утримує| дуги, називається орієнтованим, або орграфом|. На малюнку дуга зображається|змальовується| стрілкою. Багато понять, введених|запроваджених| для неографов|, для орграфов| набувають|придбавають| іншого визначення. Матриця відстаней для орграфа| несиметрична, і ексцентриситет вершини залежить від того, як вибирається максимум. Якщо максимум шукається в рядку, то ексцентриситет вершини називається числом зовнішнього розділення|поділу|, а якщо в стовпці – числом внутрішнього розділення|поділу|. Відповідно визначаються зовнішній і внутрішній центри. Підстава|основа,заснування| орграфа| – неограф| з|із| тими ж вершинами, але|та| ребрами замість відповідних дуг. Маршрут в орграфе| – послідовність вершин, сполучених|з'єднаних| дугами, направленими|спрямованими| в один бік. Маршрут, в якому всі дуги різні, є шлях|колія,дорога|. Шлях|колія,дорога|, в якому почало|розпочало,зачало| і кінець співпадають|збігаються|, є контур. Довжина шляху|колії,дороги| вимірюється числом вхідних в нього дуг, а для зваженого орграфа| – це сума ваги дуг. У орграфе| два локальні ступені|міри| вершини v: – число дуг, що входять в v, і – число дуг, що виходять з|із| v. Лема про рукостискання для орграфа| має вигляд|вид| , (13.1) де підсумовування проводиться|виробляється,справляється| по всіх вершинах графа. Множина вершин v, утворюючих дугу [v, u] з|із| вершиною u, називається множиною попередників вершини u, а множина вершин u, утворюючих дугу [v, u] з|із| вершиною v, називається множиною наступників|спадкоємців| вершини v. Потужності цих множин|безлічі| відповідно рівні:, . Надалі під графом розумітимемо як неограф|, так і орграф|.
13.2. Маршрути в орграфе| Завдання|задачі|, пов'язані з маршрутами в орграфе|, мають велике практичне значення, що і дає стимул до розвитку і вдосконалення методів їх рішення|розв'язання,вирішення,розв'язування|. Найчастіше встає питання про мінімальні і максимальні відстані, про число маршрутів певної довжини. Приклад|зразок| 13.1. Заданий орграф| (мал. 13.1). Скільки в ньому маршрутів завдовжки 3? Мал. 13.1
Рішення|розв'язання,вирішення,розв'язування|. Використовуємо алгебраїчний метод рішення задачі, на підставі теореми 12.4. Запишемо матрицю суміжності. Матриця суміжності орграфа| – несиметрична. , . Піднесемо цю матрицю до ступеня 3. Підсумовуючи всі елементи одержаної|отриманої| матриці, знаходимо|находимо|, що число маршрутів завдовжки 3 рівне восьми. Три одиниці, що стоять по діагоналі, показують, що сюди входить 3 помічених|позначених| контури. Очевидно, що це контури: 1–4–3, 4–3–1, 3–1–4.
Читайте також:
|
||||||||
|