Вершина (теорія графів)

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Граф з 6 вершинами і 7 ребрами, в якому вершина з номером 6 у лівому верхньому куті — лист, або висяча вершина

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

З точки зору теорії графів, вершини розглядаються як позбавлені характерних рис неподільні об'єкти, хоча вони можуть представляти деякі структури, залежні від проблеми, з якої пов'язаний граф. Наприклад, семантична мережа — це граф, в якому вершини представляють поняття класу об'єктів.

Дві вершини, що утворюють ребро називаються кінцевими вершинами ребра, і кажуть, що ребро інцидентне цим вершинам. Кажуть, що вершина w суміжна іншій вершині v, якщо існує граф, що містить ребро (v, w). Околом вершини v називається породжений підграф, утворений усіма вершинами, суміжними v.

Типи вершин[ред. | ред. код]

Степенем вершини графа називається число ребер, інцидентних їй. Вершина називається ізольованою, якщо її ступінь дорівнює нулю. Тобто, це вершина, яка не є кінцевою ні для якого ребра. Вершина називається листом (або висячою), якщо вершина має степінь одиниця. В орієнтованому графі розрізняють напівстепені виходу (число вихідних дуг) і напівстепені заходу (число вхідних ребер). Джерелом називається вершина з нульовим напівстепенем заходу, а вершина з нульовим степенем виходу називається стоком. Вершина називається симпліціальною, якщо всі сусідні їй вершини утворюють кліку: кожні два сусіди з'єднані. Універсальна вершина з'єднана з будь-якою вершиною графу.

Розділяючою вершиною або шарніром називається вершина, видалення якої приводить до збільшення кількості компонент зв'язності графа. Вершинним сепаратором[en] називається набір вершин, видалення яких призводить до збільшення компонент зв'язності графа. Вершинно k-зв'язний граф — це граф, в якому видалення менш ніж k вершин завжди залишає граф зв'язним. незалежною множиною називається множина вершин, ніякі дві з яких не є суміжними, а вершинним покриттям називається множина вершин, яка включає хоча б одну кінцеву вершину будь-якого ребра графа. Векторним простором вершин[en] графа називається векторний простір, що має як базис вектори, що відповідають вершинам графа (над полем чисел {0, 1}).[1][2]

Граф називається вершинно-транзитивним[en], якщо він має симетрії, які переводять будь-яку вершину в будь-яку іншу вершину. У контексті перерахування графу[en] та ізоморфізму графів важливо розрізняти помічені вершини і непомічені вершини. Помічена вершина — це пов'язана з вершиною додаткова інформація, яка дозволяє відрізнити її від інших помічених вершин. Два графа можна вважати ізоморфними тільки тоді, коли ізоморфізм переводить вершини в вершини, що мають однакові мітки. Непомічені вершини можуть при цьому переводитися в інші вершини, ґрунтуючись тільки на суміжності і не використовуючи додаткову інформацію.

Вершини графа аналогічні вершинам багатогранника, але це не те ж саме — кістяк багатогранника утворює граф, вершини якого є вершинами багатогранника, але вершини багатогранника мають додаткову структуру (геометричне місце розташування), яка ігнорується в теорії графів. Вершина фігури[en] багатогранника аналогічна околу вершини графа.

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. М. Свами, К. Туласимаран. Графы, сети и алгоритмы. — Москва : Мир, 1984. — С. 62-76. глава 4
  2. Рейнгард Дистель. Теория графов. — Новосибирск : Издательство Института Математики, 2002. — С. 35.

Посилання[ред. | ред. код]