ає двох різніх ребер, что сполучають одну и ту ж пару вершин.
Малюнок 1.4 -Псевдограф
Ребро е и вершина v назіваються інцідентнімі одна одному, если вершина v є одним з кінців ребра е.тБудь-якому ребру інцідентно Рівно две вершини, а вісь вершіні может буті інцідентно довільна Кількість ребер, це Кількість и візначає міра вершини. Ізольована вершина Взагалі НЕ має інцідентніх нею ребер (ее міра дорівнює 0).
Дві вершини назіваються суміжнімі, если смороду є різнімі кінцямі одного ребра (іншімі словами, ЦІ вершини інцідентні одному ребру). Аналогічно, два ребра назіваються суміжнімі, если смороду інцідентні одній вершіні.
Шлях в графі це послідовність вершин (без повторень), в Які будь-які две сусідні вершини суміжні. Например, в графові, збережений на малюнку 1.2, є дві Різні шляхи з вершини a у вершину з: adbc та abc. Вершина v досяжна з вершини u, если існує шлях, что почінається в u та що закінчується в v. Граф назівається зв'язного, если усі его вершини взаємно досяжні.
Компонента зв язності - це максимальний зв язній підграф. У загально випадка граф может складатіся з довільної кількості компонент зв язності. Помітімо, что будь-яка ізолірованнаявершіна є ОКРЕМЕ компонентів зв язності. На малюнку 1.5 збережений граф, что складається з чотірьох компонент зв язності: [abhk], [gd], [c] и [f].
Довжина шляху - Кількість ребер, з якіх цею шлях складається. Например, довжина Вже згаданіх Шляхів adbc и abc (див. Рис. 1.2) - 3 і 2 відповідно.
Малюнок 1.5 - незва язній граф
Говорять, что вершина v Належить k -му рівню відносно вершини u, если існує шлях з u в v Довжина Рівно k ребер. Одна и та ж вершина может відносітіся до різніх рівнів. Например, в графові, збережений на малюнку 1.2, відносно вершини a існує 4 Рівні:
) a;
) b, d;
) b, d, c (шляхи adb, abd, abc);
) c (шлях adbc).
Відстань между вершинами u и v - це довжина найкоротшого шляху від u до v. З цього визначення видно, что відстань между вершинами a и c в на малюнку 1.2 рівне 2.
Цикл - це замкнутість шлях. Усі вершини в ціклі, окрім Першої и останньої, мают буті Різні. Например, циклом є шлях abda в графі на малюнку 1.2.
Ейлера граф - це граф, в якому існує шлях або цикл, что містіть усі ребра графа (вершини могут повторюватіся). Например, граф на малюнку 1.6 є Ейлеровим: шуканімШляхом в нім буде dbacfbcd.
Малюнок 1.6 - Граф Ейлера
Гамільтоновій граф - це граф, в якому існує шлях або цикл (без повторення ребер), что містіть усі вершини графа. Например, на малюнку 1.6 шуканій цикл: abdfca.
Існує й достатньо ровері число різноманітніх способів представлення графів. Проти ми вікладемо тут только найкорісніші з точки зору програмування.
Матриця суміжності Sm - це квадратна матриця розміром NxN (N - Кількість вершин в графі), Заповнена Одиниця и нулями за Наступний правилом: если в графі є ребро, что сполучає вершини u и v, то Sm [ u, v]=1, інакше Sm [u, v]=0.
Помітімо, что це визначення Підходить як орієнтованім, так и неорієнтованім графам: матриця суміжності для неорієнтованого графа буде симетричним відносно своєї головної діагоналі, а для орграфа - несіметрічною.
Задати зваження граф помощью матриці суміжності теж можливо. Необходимо лишь внести невеликі зміну до визначення: если в графі є ребро e, что сполучає вершини u и v, то Sm [u, v]=ves (e), інакше Sm [u, v]=0. Таким чином, незваженій граф можна інтерпретуваті як зваження, усі ребра которого мают однаково Вагу 1. невелика ускладнене вінікне у тому випадка, если в графі дозволяються ребра з вагою 0. Тоді придется зберігаті дві масивов: один з нулями и Одиниця, Які службовців Показники наявності ребер, а другий -з вагамі ціх ребер.
Зручність матриці суміжності Полягає в наочності и прозорості алгоритмів, засновання на ее вікорістанні. А незручність - в Дещо завіщеній вимозі до пам'яті: если граф далекий від полного, то в масиві, что зберігає матрицю суміжності, віявляється много порожніх Місць (нулів). Крім того, для спілкування з користувачем цею способ представлення графів НЕ занадто Зручний: его краще застосовуваті только для внутрішнього представлення даних.
Інший способ Завдання графів Полягає у вікорістанні списку ребер. Цей способ Завдання графів найбільш Зручний для зовнішнього представлення вхідних даних. Зазвічай его представляються у виде: lt; номер_початкової_вершіні gt; lt; номер_кінцевої_вершіні gt; [ lt; вага_ребр...
