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

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

Граф з 6 вершинами і 7 ребрами, в якому вершина з номером 6 у лівому верхньому куті — лист, або висяча вершина

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

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

Типи вершин

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

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

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

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

Див. також

• Теорія графів
• Словник термінів теорії графів
• Універсальна множина точок

Посилання

• Gallo, Giorgio; Pallotino, Stefano (1988). Shortest path algorithms. Annals of Operations Research. 13 (1): 1—79. doi:10.1007/BF02288320.
• К. Берж. Теория графов и её применение. — М. : издательство Иностранной литературы, 1962.
• Chartrand, Gary (1985). Introductory graph theory. New York: Dover. ISBN 0-486-24775-9.
• Biggs, Norman; Lloyd, E. H.; Wilson, Robin J. (1986). Graph theory, 1736-1936. Oxford [Oxfordshire]: Clarendon Press. ISBN 0-19-853916-9.
• Harary, Frank (1969). Graph theory. Reading, Mass.: Addison-Wesley Publishing. ISBN 0-201-41033-8.
• Harary, Frank; Palmer, Edgar M. (1973). Graphical enumeration. New York, Academic Press. ISBN 0-12-324245-2.
• Weisstein, Eric W. Graph Vertex(англ.) на сайті Wolfram MathWorld.