Окіл (теорія графів)
З Вікіпедії, безкоштовно encyclopedia
В теорії графів суміжною вершиною вершини v називається вершина, поєднана з v ребром. Околом вершини v в графі G називається породжений підграф графа G, що складається з усіх вершин, сполучених з v і всіх ребер, що з'єднують дві таких вершини. Наприклад, малюнок показує граф з 6 вершинами і 7 ребрами. Вершина 5 суміжна вершинам 1, 2, і 4, але не суміжна вершинам 3 і 6. Окіл вершини 5 — це граф з трьома вершинами 1, 2, і 4, і одним ребром, що з'єднує вершини 1 і 2.
Окіл часто позначається як NG(v) або (якщо відомо, про який граф йде мова) N(v). Те ж саме позначення околу може використовуватися для посилання на множину суміжних вершин, а не на відповідний породжений підграф. Окіл, описаний вище не включає саму вершину v і про цей окіл говорять як про відкритий окіл вершини v. Можна визначити окіл, що включає v. У цьому випадку окіл називається замкненим та позначається як NG[v]. Якщо не вказано явно, то окіл є відкритим.
Околи можна використовувати для представлення графів в комп'ютерних алгоритмах через список суміжності[en] та матрицю суміжності. Околи використовуються також в коефіцієнті кластеризації графа, який вимірює середню густину його околів. До того ж, багато важливих класів графів можна визначити властивостями його околи або взаємною симетрією околів.
Ізольована вершина не має суміжних вершин. Степінь вершини дорівнює числу суміжних вершин. Спеціальним випадком є петля, що з'єднує вершину з тією ж самою вершиною. Якщо таке ребро існує, вершина належить власному околу.