Вершина (теорія графів)
Вершиною в теорії графів називається базовий елемент, який використовується при побудові графа: неорієнтований граф складається з множини вершин і множини ребер (невпорядкованих пар вершин), в той час як орієнтований граф складається з множин вершин і множин дуг (впорядкованих пар вершин). На малюнках, що представляють граф, вершина зазвичай представляється кружком з міткою, а ребро представляється лінією (дугою-стрілкою), що з'єднує вершини.
З точки зору теорії графів, вершини розглядаються як позбавлені характерних рис неподільні об'єкти, хоча вони можуть представляти деякі структури, залежні від проблеми, з якої пов'язаний граф. Наприклад, семантична мережа — це граф, в якому вершини представляють поняття класу об'єктів.
Дві вершини, що утворюють ребро називаються кінцевими вершинами ребра, і кажуть, що ребро інцидентне цим вершинам. Кажуть, що вершина w суміжна іншій вершині v, якщо існує граф, що містить ребро (v, w). Околом вершини v називається породжений підграф, утворений усіма вершинами, суміжними v.
Типи вершин[ред. | ред. код]
Степенем вершини графа називається число ребер, інцидентних їй. Вершина називається ізольованою, якщо її ступінь дорівнює нулю. Тобто, це вершина, яка не є кінцевою ні для якого ребра. Вершина називається листом (або висячою), якщо вершина має степінь одиниця. В орієнтованому графі розрізняють напівстепені виходу (число вихідних дуг) і напівстепені заходу (число вхідних ребер). Джерелом називається вершина з нульовим напівстепенем заходу, а вершина з нульовим степенем виходу називається стоком. Вершина називається симпліціальною, якщо всі сусідні їй вершини утворюють кліку: кожні два сусіди з'єднані. Універсальна вершина з'єднана з будь-якою вершиною графу.
Розділяючою вершиною або шарніром називається вершина, видалення якої приводить до збільшення кількості компонент зв'язності графа. Вершинним сепаратором[en] називається набір вершин, видалення яких призводить до збільшення компонент зв'язності графа. k-вершинно-зв'язний граф — це граф, в якому видалення менш ніж k вершин завжди залишає граф зв'язним. незалежною множиною називається множина вершин, ніякі дві з яких не є суміжними, а вершинним покриттям називається множина вершин, яка включає хоча б одну кінцеву вершину будь-якого ребра графа. Векторним простором вершин[en] графа називається векторний простір, що має як базис вектори, що відповідають вершинам графа (над полем чисел {0, 1}).[1][2]
Граф називається вершинно-транзитивним, якщо він має симетрії, які переводять будь-яку вершину в будь-яку іншу вершину. У контексті перерахування графу та ізоморфізму графів важливо розрізняти помічені вершини і непомічені вершини. Помічена вершина — це пов'язана з вершиною додаткова інформація, яка дозволяє відрізнити її від інших помічених вершин. Два графа можна вважати ізоморфними тільки тоді, коли ізоморфізм переводить вершини в вершини, що мають однакові мітки. Непомічені вершини можуть при цьому переводитися в інші вершини, ґрунтуючись тільки на суміжності і не використовуючи додаткову інформацію.
Вершини графа аналогічні вершинам багатогранника, але це не те ж саме — кістяк багатогранника утворює граф, вершини якого є вершинами багатогранника, але вершини багатогранника мають додаткову структуру (геометричне місце розташування), яка ігнорується в теорії графів. Вершина фігури[en] багатогранника аналогічна околу вершини графа.
Див. також[ред. | ред. код]
Примітки[ред. | ред. код]
Посилання[ред. | ред. код]
- Gallo, Giorgio; Pallotino, Stefano (1988). Shortest path algorithms. Annals of Operations Research 13 (1): 1–79. doi:10.1007/BF02288320.
- К. Берж[en]. Теория графов и её применение. — Москва, 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.