Вершина (теория графов)
 | Эта статья включает список общих ссылок , но в ней отсутствуют достаточные соответствующие встроенные цитаты . ( февраль 2014 г. ) |
В дискретной математике , а точнее в теории графов , вершина (множественное число вершин ) или узел — это фундаментальная единица, из которой формируются графы: неориентированный граф состоит из набора вершин и набора ребер (неупорядоченных пар вершин), а ориентированный граф состоит из набора вершин и набора дуг (упорядоченных пар вершин). На диаграмме графа вершина обычно изображается кружком с меткой, а ребро — линией или стрелкой, идущей от одной вершины к другой.
С точки зрения теории графов вершины рассматриваются как безликие и неделимые объекты , хотя они могут иметь дополнительную структуру в зависимости от приложения, из которого возникает граф; например, семантическая сеть — это граф, вершины которого представляют понятия или классы объектов.
Две вершины, образующие ребро, называются конечными точками этого ребра, а ребро называется инцидентным вершинам. вершина w Говорят, что смежна с другой вершиной v , если граф содержит ребро ( v , w ). Окрестность с вершины v — это индуцированный подграф графа, образованный всеми вершинами, смежными v .
Типы вершин
[ редактировать ]
Степень вершины, обозначаемой 𝛿(v) в графе , — это количество инцидентных ей ребер. Изолированная вершина — это вершина нулевой степени; то есть вершина, которая не является конечной точкой какого-либо ребра (пример изображения иллюстрирует одну изолированную вершину). [1] Листовая вершина (также висячая вершина ) — это вершина степени один. В ориентированном графе можно выделить исходящую степень (количество исходящих ребер), обозначаемую 𝛿 + (v), от входной степени (количества входящих ребер), обозначаемой 𝛿 − (в); исходная вершина — это вершина с нулевой степенью входа, а вершина стока — это вершина с нулевой степенью выхода. Симплициальная вершина — это вершина, соседи которой образуют клику : каждые два соседа смежны. Универсальная вершина — это вершина, смежная с любой другой вершиной графа.
Разрезанная вершина — это вершина, удаление которой отключило бы оставшийся граф; разделитель вершин — это набор вершин, удаление которых разъединило бы оставшийся граф на небольшие части. Граф с k-связностью — это граф, в котором удаление менее k вершин всегда оставляет оставшийся граф связным. Независимый набор — это набор вершин, ни одна из которых не является смежной, а вершинное покрытие — это набор вершин, который включает хотя бы одну конечную точку каждого ребра графа. Пространство вершин графа — это векторное пространство, имеющее набор базисных векторов, соответствующих вершинам графа.
Граф является вершинно-транзитивным, если он имеет симметрии, отображающие любую вершину в любую другую вершину. В контексте нумерации графов и изоморфизма графов важно различать помеченные вершины и непомеченные вершины . Помеченная вершина — это вершина, связанная с дополнительной информацией, позволяющей отличить ее от других помеченных вершин; два графа можно считать изоморфными только в том случае, если соответствие между их вершинами образует пары вершин с одинаковыми метками. Немаркированная вершина — это вершина, которую можно заменить на любую другую вершину только на основе ее смежности в графе, а не на основе какой-либо дополнительной информации.
Вершины в графах аналогичны, но не тождественны вершинам многогранников : скелет многогранника образует граф, вершины которого являются вершинами многогранника, но вершины многогранника имеют дополнительную структуру (их геометрическое расположение), т.е. не предполагается, что он присутствует в теории графов. Фигура вершины многогранника аналогична окрестностям вершины в графе.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Файл:Маленькая сеть.png ; пример изображения сети с 8 вершинами и 10 ребрами
- Галло, Джорджио; Паллотино, Стефано (1988). «Алгоритмы кратчайшего пути». Анналы исследования операций . 13 (1): 1–79. дои : 10.1007/BF02288320 . S2CID 62752810 .
- Берже, Клод , Теория графов и их приложений . Collection Universitaire de Mathématiques, II Dunod, Париж, 1958, viii+277 стр. (английское издание, Wiley, 1961; Methuen & Co, Нью-Йорк, 1962; русский, Москва, 1961; испанский, Мексика, 1962; румынский, Бухарест, 1969; китайский, Шанхай, 1963). Второе издание первого английского издания 1962 года, Дувр, Нью-Йорк, 2001 г.).
- Чартранд, Гэри (1985). Введение в теорию графов . Нью-Йорк: Дувр. ISBN 0-486-24775-9 .
- Биггс, Норман; Ллойд, Э.Х.; Уилсон, Робин Дж. (1986). Теория графов, 1736-1936 гг . Оксфорд [Оксфордшир]: Clarendon Press. ISBN 0-19-853916-9 .
- Харари, Фрэнк (1969). Теория графов . Ридинг, Массачусетс: Издательство Addison-Wesley. ISBN 0-201-41033-8 .
- Харари, Фрэнк; Палмер, Эдгар М. (1973). Графическое перечисление . Нью-Йорк, Академик Пресс. ISBN 0-12-324245-2 .