1. Граф - це система деяких об'єктів разом з деякими парами цих об'єктів, що зображає відносини зв'язку між ними. Неорієнтовані граф (відповідно орієнтований граф, або орграф) G - система G = (V, E, Г), що складається з безлічі елементів V =, званих вершинами графа, безлічі елементів Е =, званих ребрами, і відображення, що ставить у відповідність кожному елементу неупорядковану (відповідно впорядковану) пару елементів званих кінцями ребра е.
Для неорієнтованого графа значення V1 і V2 може бути довільним. Для орієнтованого - V1 - початок шляху, V2 - кінець.
утворює безліч елементів графа; при цьому передбачається, що
Відображення Г визначає ставлення инцидентности ребра з кожним зі своїх кінців. Для графа G = (V, Е, Р) вживається також більш короткий позначення G = (V, Е) без вказівки Інцидентне, які визначаються контекстом.
Якщо - упорядкована парапрі v1- v2), то ребро е називається орієнтованої дугою, що виходить із вершіниv1і входить в вершину; називається початком, а кінцем дуги е. Якщо - невпорядкована пара, то ребро е називається неорієнтованим.
Всякому графу G можна поставити у відповідність співвіднесений неорієнтовані граф з тими ж множинами V і Е і інцидентності, але все пари невпорядковані.
Вершина, що не инцидентная жодному ребру, називається ізольованою. Вершина, инцидентная рівно одному ребру, і саме це ребро називаються кінцевими, або висячими.
Ребро з співпадаючими кінцями називається петлею.
Дві вершини, інцидентні одному і тому ж ребру, називаються сусідніми (або суміжними). Два ребра, інцидентні одній і тій же вершині, називаються суміжними.
Ребра, яким поставлена у відповідність одна і та ж пара вершин, називаються кратними, або паралельними.
2. Графи можуть відрізнятися і не відрізнятися. Зазвичай це пов'язують з поняттям ізоморфізму графів.
Два графа називаються ізоморфними, якщо існують взаємно однозначні відображення зберігають инцидентность, тобто е Є E1
3. Існує кілька способів завдання графів:
1) Перерахування (список) ребер графа із зазначенням їх кінців і додаванням списку ізольованих вершин.
2) Матриця інціденцій графа з b вершинами і p ребрами - прямокутна матриця з b рядками і p стовпцями, рядки якої відповідають вершинам графа, а стовпці - ребрах, причому j для неорієнтованого графа елемент матриці дорівнює 1, якщо вершінаі ребро інцидентні, і дорівнює 0 в іншому випадку. Для орієнтованого графаесліявляется початком дуги = +1, якщо v. - кінець дуги В кожному стовпці матриці інціденцій -два ненульових елемента, якщо ребро - НЕ петля. Петлі відповідає елемент, рівний 2.
3) Матриця сусідства (суміжності) вершин графа з b вершинами - квадратна матріцаразмерності Ь, рядки і стовпці якої відповідають вершинам графа, причому невід'ємні елементравен числу ребер, що йдуть з вершини вершину (не дорівнює, взагалі кажучи,, однак для неорієнтованих графів матриця сусідства - симетрична). Для несуміжних вершин відповідний елемент матриці дорівнює 0.
4) Для наочності граф часто представляють у вигляді геометричного об'єкта: вершин відповідають різні виділені точки в просторі (на площині), ребрах - відрізки кривих, що зв'язують відповідні точки і не проходять через виділені точки, відмінні від їх кінців.
5. Граф називається подграфом графа позначення: есліі для множин зберігаються інціденцій графа G. При цьому, очевидно, кожне ребро з Е 'входить в підграф Н разом зі своїми кінцями.
Зазвичай розглядаються тільки підграфи без ізольованих вершин або тільки підграфи, що містять всі вершини графа (і тільки частина ребер); такі підграфи повністю визначаються безліччю своїх ребер. У цих випадках можна природним чином визначити теоретико-множинні операції над подграфа: перетин, об'єднання, симметрическую різницю (звану також сумою по модулю 2 або просто сумою), додаток до всього графа.
Подграфом, натягнутим на безліч вершінграфа
G, називається підграф, що містить вершини з V і все ребра графа G, що з'єднують пари вершин з
Подграф, що складається з усіх ребер, інцидентних вершині називається зіркою вершини
Для графів без петель степеньвершіни # 945; є число ребер в зірці Z # 945 ;. Очевидно, що сума ступенів усіх вершин графа без петель дорівнює подвоєному числу ребер.
Всі теми даного розділу:
N, n) -Розміщення без повторенійназиваются n-перестановками, або перестановками з n елементів.
Невпорядковані (n, К) -виборкі називаються сполученнями: з повтореніяміілі без повтореній.Заметім, що (n, k) -Поєднання без повторень - це k-елементне підмножин
Це правило суми, або правило альтернатив.
Якщо об'єкт х Є X може бути обраний n способами і після кожного з таких виборів об'єкт у Є Y може бути обраний m способами, то вибір впорядкованої пари (х, у) може бути здійснений m n способами.
конфігурацій.
1. Число (n, k) -Розміщення без повторенійможет бути визначено за допомогою правила твори.
§2.2. Ланцюги. Цикли. Можливості підключення.
1. Послідовність вершин і ребер графа G називається шляхом
§2.3. Дерева.
1. Ребро е довільного графа G називається циклічним, якщо воно належить хоча б одному елементарному циклу в графі, і ациклічним
§2.5. Цикломатичне число.
1. Будемо розглядати підграфи, які можуть бути незв'язними, але містять всі вершини графа. Нехай G - граф, що містить p занумерованих ребер (e1, e
§3.1. Подання інформації.
Кодування - представлення інформації у вигляді сигналів і їх характеристик. Декодування - зворотний процес. Сигнал може представляти інформацію у вигляді своїх хара
§3.3. Перешкодостійкі надлишкові коди.
У ненадлишкових довічних кодах, в кодах Грея і в кодах, побудованих на картах Карно всяка помилка полягає в спотворенні будь-якого символу або розряду коду
§3.4. Коди з перевіркою на парність.
Мають великий ефективністю і малої надмірністю. Коди з перевіркою на парність будуються таким чином, щоб до кодової комбінації додавався один розряд, який робить число одиниць кодової до
§3.5. Код Хеммінга.
Код Хеммінга відноситься до кодів, які дозволяють не тільки виявляти а й виправляти поодинокі помилки. Виправляє здатність коду досягається за рахунок багаторазових перевірок на четнос