58.Задання графа за допомогою матриці інцидентності

Матриця інцидентності визначається вершинами та ребрами графа. Вершини – рядки, ребра – стовпці. Для неорієнтованих графів елемент а_ij = 1, тоді якщо е_i інцидентна V_j. Для орієнтованих графів: а_ij = -1, якщо V_і – початок дуги е_і ; а_ij = 1, якщо V_і – кінець дуги е_і ; а_ij = 0, якщо не інцидентні.У випадку петлі елемент матриці інциденції дорівнює будь – якому відмінному числу, що не дорівнює 1,0,-1 (степеню виходу ребер з вершини)

59.Задання графа за допомогою матриці суміжності

Дана матриця буде квадратна. а_ij = 1, якщо є ребро з вершини i в j; 0 – в протилежному випадку.

60.Задання графа за допомогою матриці Кірхгофа.

Дана матриця існує тільки для неорієнтованих графів.

а_ij = -1, якщо V_і та V_j – суміжні; а_ij = 0, якщо не суміжні; а_ij = степеню виходу, коли i = j.

61. Локальні степені вершини графа.

Локальним степенем вершини графа називається кількість інцидент них йому ребер. Петля збільшує степінь на 2. В довільному графі сума степенем вершин парна, бо рівна подвоєному добутку його ребер. Степінь вершини в повному графі рівна кількості вершин без одної. |Е|-1. якщо степінь вершини = 0, то вершина є ізольованою, якщо ж степінь = |Е|-1, то ця вершина з’єднана з усіма іншими, відповідно не може бути, щоб в одному графі зустрічалися вершини зі степенем 0 і|Е|-1. в будь-якому графі з кількістю вершин більше рівне 2 є принаймні дві вершини з однаковим степенем. Лема про “рукостискання” Сума степенів вершин графа дорівнює подвоєній кількості його ребер; повний граф з n – вершинами має n(n-1)/2; в будь – якому графі кількість вершин, степінь в непарна – парна.

62. Локальні степені вершини орграфа.

В орієнтованих графах окрім простої степені вершини виокремлено ще степінь входу і степінь виходу. Відповідно якщо дуга напрямлена в вершину, або з неї.

64. Операції над частинами графа.

До графів визначають дві специфічні операції: 1)вилучення ребра. Результатом цієї операції буде G-е = {V,E-{e}}. 2)вилучення вершини: G-v = {V-{v},E(V-{v})⁽²⁾} 3)доповнення до графа. Доповненням графа G називається ¬G, який визначається наступним чином: ¬G=(V,(V⁽²⁾-E)). Доповненням до графа G буде ¬G. Для довільного графа об’єднання G та ¬G буде повний граф. Якщо в графі G з n – вершинами, степінь вершини дорівнює k, то в графі ¬G доповненням степінь цієї вершини буде n-k-1.

65. Маршрути, ланцюги, цикли.

Маршрут називається ланцюгом, якщо всі його ребра попарно різні. Цикл – це замкнений ланцюг (послідовність ребер або дуг). В графі з n – вершинами степінь вершини можна позначити від 0 до n-1. Маршрутом в графі G називається послідовність вершин та ребер:(V₀,e₁,V₁e₂,…,e_n,V_n). Ребра з індексом у е_і+1 називаються сусідніми і мають одну спільну вершину. Число n називається довжиною маршрутом. Маршрут називається тривіальним, який складається тільки з однієї вершини та множини n.

66. Ознаки зв’язності

Неограф назив. зв’язним, якщо будь-які його 2 неспівпадаючі вершини пов’язані маршрутом. Граф назив. сильнозв’язним, якщо для кожної пари різних вершин А та В є маршрут з А в В і з В в А. Будь-який максимальний за включенням сильно зв’язаний підграф даного графа назив. його компонентою зв’язності.