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

редактировать
Граф с 6 вершинами и 7 ребрами где вершина номер 6 в крайнем левом углу является вершиной листа или висячей вершиной

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

С точки зрения теории графов, вершины рассматриваются как неделимые объекты без признаков, хотя они могут иметь дополнительную структуру в зависимости от приложения, из которого возникает граф; например, семантическая сеть - это граф, в котором вершины представляют концепции или классы объектов.

Две вершины, образующие ребро, называются конечными точками этого ребра, а ребро инцидентно вершинам. Вершина w называется смежной с другой вершиной v, если в графе есть ребро (v, w). окрестность вершины v - это индуцированный подграф графа, образованный всеми вершинами, смежными с v.

Содержание
  • 1 Типы вершин
  • 2 См. также
  • 3 Ссылки
  • 4 Внешние ссылки
Типы вершин
Небольшой пример сеть с 8 вершинами и 10 ребрами. Пример сети с 8 вершинами (из которых одна изолирована) и 10 ребрами.

степень вершина, обозначенная 𝛿 (v) в графе, - это количество инцидентных ей ребер. Изолированная вершина - это вершина нулевой степени; то есть вершина, которая не является конечной точкой какого-либо ребра (пример изображения иллюстрирует одну изолированную вершину). Листовая вершина (также подвесная вершина ) - это вершина со степенью один. В ориентированном графе можно отличить исходящую степень (количество исходящих ребер), обозначенную 𝛿 (v), от степени (количество входящих ребер), обозначенную 𝛿 (v); исходная вершина - это вершина с нулевой степенью, а приемная вершина - это вершина с нулевой степенью выхода. Симплициальная вершина - это вершина, соседи которой образуют клику : каждые два соседа являются смежными. Универсальная вершина - это вершина, смежная с любой другой вершиной в графе.

A вырезанная вершина - вершина, удаление которой разъединит оставшийся граф; разделитель вершин - это набор вершин, удаление которых разъединит оставшийся граф на маленькие части. граф, связанный с k вершинами, - это граф, в котором удаление менее k вершин всегда оставляет оставшийся граф связным. Независимое множество - это набор вершин, две из которых не являются смежными, а вершинное покрытие - это набор вершин, который включает по крайней мере одну конечную точку каждого ребра в графе. пространство вершин графа - это векторное пространство, имеющее набор базисных векторов, соответствующих вершинам графа.

Граф является вершинно-транзитивным, если он имеет симметрии, которые отображают любую вершину в любую другую вершину. В контексте перечисления графов и изоморфизма графов важно различать помеченные вершины и немаркированные вершины . Помеченная вершина - это вершина, которая связана с дополнительной информацией, которая позволяет отличить ее от других помеченных вершин; два графа можно считать изоморфными, только если соответствие между их вершинами объединяет вершины с одинаковыми метками. Непомеченная вершина - это вершина, которая может быть заменена любой другой вершиной только на основе ее смежностей в графе, а не на основе какой-либо дополнительной информации.

Вершины в графах аналогичны, но не совпадают с вершинами многогранников : каркас многогранника образует граф, вершинами которого являются вершины многогранника, но вершины многогранника имеют дополнительную структуру (их геометрическое расположение), которая, как предполагается, не присутствует в теории графов. вершинная фигура вершины многогранника аналогична окрестности вершины в графе.

См. Также
Ссылки
  • Галло, Джорджио; Паллотино, Стефано (1988). «Алгоритмы кратчайшего пути». Анналы исследований операций. 13 (1): 1–79. doi : 10.1007 / BF02288320. CS1 maint: ref = harv (ссылка )
  • Берж, Клод, Théorie des graphes et ses applications. Коллекция Universitaire de Mathématiques, II Dunod, Paris, 1958, viii + 277 стр. (Английское издание, Wiley 1961; Methuen Co, New York 1962; русский, Москва, 1961; испанский, Мексика, 1962; румынский, Бухарест, 1969; китайский, Шанхай, 1963; Второе издание первого английского издания 1962 года. Довер, Нью-Йорк, 2001)
  • Чартранд, Гэри (1985). Введение в теорию графов. Нью-Йорк: Довер. ISBN 0-486-24775-9.
  • Биггс, Норман; Ллойд, EH; Уилсон, Робин Дж. (1986). Теория графов, 1736-1936 гг.. Оксфорд [Оксфордшир]: Clarendon Press. ISBN 0-19-853916-9.
  • Harary, Frank (1969). Теория графов. Reading, Mass.: Addison-Wesley Publishing. ISBN 0-201-41033-8.
  • Харари, Фрэнк; Палмер, Эдгар М. (1973). Графическое перечисление. Нью-Йорк, Academic Press. ISBN 0-12- 324245-2.
Внешние ссылки
Последняя правка сделана 2021-06-18 11:48:27
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте