Вершинно k-связный граф

4-связный граф: при удалении любых трёх вершин, он остаётся связным.

В теории графов говорят, что нетривиальный граф G вершинно k-связен (или k-связен), если он имеет больше чем k вершин и после удаления менее чем k любых вершин граф остаётся связным.

Вершинная связность, или просто связность, графа — это наибольшее k, для которого граф k-вершинно-связен.

Альтернативно граф, отличный от полного, имеет связность k, если k является размером наименьшего подмножества вершин, при удалении которого граф становится несвязным^[1]. Полные графы исключены из рассмотрения, поскольку их нельзя сделать несвязными путём удаления вершин. Полный граф с n вершинами имеет связность n − 1, как вытекает из первого определения.

Эквивалентное определение — если для любой пары вершин графа можно найти k непересекающихся путей, соединяющих эти вершины — см. теорему Менгера (Diestel 2005, С. 55). Это определение имеет тот же ответ: n − 1 для связности полного графа K_n^[1].

1-связный граф называется также связным, 2-связный граф называется двусвязным, 3-связный граф называется, соответственно, трисвязным.

1-скелет^[англ.] любого k-мерного выпуклого многогранника образует k-вершинно-связный граф (Теорема Балинского, Balinski, 1961). Частично обратная теорема Штейница утверждает, что любой 3-вершинно-связный планарный граф образует скелет выпуклого многогранника.

См. также

Примечания

↑ ¹ ² Schrijver. Combinatorial Optimization. — Springer.

Литература

M. L. Balinski. On the graph structure of convex polyhedra in n-space // Pacific Journal of Mathematics. — Т. 11, вып. 2. — С. 431—434.
Reinhard Diestel. Graph Theory. — 3rd. — Berlin, New York: Springer—Verlag, 2005. — ISBN 978-3-540-26183-4.

Похожие исследовательские статьи

Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:

как и геометрия, обладает наглядностью;
как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
не имеет громоздкого математического аппарата ;
имеет выраженный прикладной характер.

О́стовное де́рево графа — это дерево, подграф данного графа, с тем же числом вершин, что и у исходного графа. Неформально говоря, остовное дерево получается из исходного графа удалением максимального числа рёбер, входящих в циклы, но без нарушения связности графа. Остовное дерево включает в себя все $\text{[math]}$ вершин исходного графа и содержит $\text{[math]}$ ребро.

Связный граф — граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует как минимум один путь.

В теории графов два типа объектов обычно называются циклами.

В теории графов рёберным графом L(G) неориентированного графа G называется граф L(G), представляющий соседство рёбер графа G.

В теории графов вершинно-транзитивным графом называется граф G такой, что для любых двух вершин v₁ и v₂ графа G существует автоморфизм

\text{[math]}

В теории графов графом Халина называется некоторый вид планарного графа, который строится из дерева, имеющего по меньшей мере 4 вершины, ни одна из которых не имеет в точности двух соседей. Дерево рисуется на плоскости так, что никакие рёбра не пересекаются, затем добавляются рёбра, соединяющие все его листья в цикл. Графы Халина названы по имени немецкого математика Рудольфа Халина, изучавшего их в 1971 году, но кубические графы Халина изучались за столетие до этого английским математиком Томасом Киркманом.

<span class="mw-page-title-main">Вершина (теория графов)</span> фундаментальная единица любого графа

Вершинa графа — фундаментальное понятие теории графов. Неориентированный граф состоит из множества вершин и множества рёбер, в то время как ориентированный граф состоит из множества вершин и множества дуг. На рисунках, представляющих граф, вершина обычно обозначается кружком с меткой, ребро — линией, дуга — стрелкой, соединяющей вершины.

<span class="mw-page-title-main">Сумма по клике</span>

Сумма по клике — теоретико-графовая операция, обеспечивающая комбинацию двух графов путём склеивания их по клике, аналогично связной сумме в топологии. Если два графа $\text{[math]}$ и $\text{[math]}$ содержат клики одинакового размера, сумма по клике образуется из несвязанного объединения графов путём отождествления пар вершин из клик так, чтобы образовать одну клику, с последующим удалением некоторых рёбер. Сумма по $\text{[math]}$ -клике — это сумма по клике, содержащей не более $\text{[math]}$ вершин. Можно образовать сумму по кликам и сумму по $\text{[math]}$ -кликам более чем двух графов путём повторения операции суммы.

Полиэдральный граф — неориентированный граф, образованный из вершин и рёбер выпуклого многогранника, или, в контексте теории графов — вершинно 3-связный планарный граф.

Теорема Штайница — это комбинаторное описание неориентированных графов, образованных рёбрами и вершинами трёхмерного выпуклого многогранника — они в точности являются (простыми) вершинно 3-связными планарными графами. То есть любой выпуклый многогранник образует 3-связный планарный граф, и любой 3-связный планарный граф может быть представлен как выпуклый многогранник. По этой причине 3-связные планарные графы называют также полиэдральными.

Комбинаторика многогранников — это область математики, принадлежащая комбинаторике и комбинаторной геометрии и изучающая вопросы подсчёта и описания граней выпуклых многогранников.

Минор в теории графов — граф $\text{[math]}$ для заданного графа $\text{[math]}$ , который может быть образован из $\text{[math]}$ удалением рёбер и вершин и стягиванием рёбер.

Теорема Фляйшнера — утверждение в теории графов, дающее достаточное условие, чтобы граф содержал гамильтонов цикл: если граф $\text{[math]}$ является вершинно 2-связным графом, то квадрат графа $\text{[math]}$ гамильтонов. Названа именем Герберта Фляйшнера, опубликовавшего доказательство теоремы в 1974 году.

<span class="mw-page-title-main">Ребро (геометрия)</span> отрезок, соединяющий две вершины политопа

Ребро в геометрии — отрезок, соединяющий две вершины многоугольника или многогранника. В многоугольниках ребро является отрезком, лежащим на границе и чаще называется стороной многоугольника. В трёхмерных многогранниках и в многогранниках большей размерности ребро — это отрезок, общий для двух граней. Отрезок, соединяющий две вершины и проходящий через внутренние или внешние точки, ребром не является и называется диагональю.

Вложение Татта простого вершинно 3-связного планарного графа — вложение без пересечений с рёбрами в виде отрезков с дополнительными свойствами, что внешняя грань имеет выпуклый многоугольник в качестве границы и что каждая внутренняя вершина является геометрическим центром соседей. Если внешний многоугольник фиксирован, это условие на внутренние вершины определяет их положения однозначно как решение системы линейных уравнений. Решение уравнений даёт планарное вложение. Теорема Татта «о резиновой укладке» утверждает, что в единственном решении никогда нет пересечений рёбер и, что более строго, что любая грань получающегося планарного вложения выпукла. Вложение называется «резиновым», поскольку такое вложение может быть найдено как равновесное положение системы пружин или резиновых ремней, представляющих рёбра графа.

Фактор графа G — это остовный подграф, то есть подграф, имеющий те же вершины, что и граф G. k-фактор графа — это остовный k-регулярный подграф, а k-факторизация разбивает рёбра графа на непересекающиеся k-факторы. Говорят, что граф G k-факторизуем, если он позволяет k-разбиение. В частности, множество рёбер 1-фактора — это совершенное паросочетание, а 1-разложение k-регулярного графа — это рёберная раскраска k цветами. 2-фактор — это набор циклов, которые покрывают все вершины графа.

Экстремальная теория графов — это ветвь теории графов. Экстремальная теория графов изучает экстремальные свойства графов, удовлетворяющих определённым условиям. Экстремальность может относиться к различным инвариантам графов, таким как порядок, размер или обхват. В более абстрактном смысле теория изучает, как глобальные свойства графа влияют на локальные подструктуры графа.

<span class="mw-page-title-main">Теорема Балинского</span>

Теорема Балинского — это утверждение относительно структуры графа многогранника размерности 3 и выше. Теорема утверждает, что если образовать неориентированный граф из вершин и рёбер выпуклого d-мерного многогранника, то полученный граф по меньшей мере вершинно d-связен — удаление любого набора из d − 1 вершин оставляет связный подграф. Например, для трёхмерного многогранника, если удалить две вершины, для любой пары вершин существует путь, соединяющий эту пару.

Ориентация неориентированного графа — это назначение направлений каждому ребру, что превращает исходный граф в ориентированный граф.

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.