Число пересечений K (9, 9)
Я изучаю теорию графов и не могу понять, как решить эту проблему. Я не очень хорошо разбираюсь в графиках, и мне довольно сложно решать такие задачи. Буду очень признателен, если вы дадите мне какое-нибудь объяснение. Заранее спасибо!
Вопрос: Верно ли, что каждое k-связное ($k>1$) граф, не имеющий гамильтонова цикла, имеет цикл, содержащий $k$независимые вершины и их соседи? Известно, что это верно для$k = 2$ и $3$. Например, график справа 3-связный, но не гамильтоновый. И показанный пунктирный цикл содержит$3$независимые вершины (три вершины более светлого цвета) и их соседи. Чтобы увидеть, что это не гамильтонов, обратите внимание, что этот граф - просто полный двудольный граф$K(3,4)$.
Ответы
Давайте сначала подумаем о случае, когда $G$подключен. Если$|V| < k$, то мы, конечно, не можем разделить $V$ в $k$ непустые подмножества, поэтому предположим $|V| \geq k$.
Я утверждаю, что в этом случае есть подходящая перегородка. Чтобы это показать, достаточно найти подмножество$V' \subseteq V$ с участием $|V'| = k-1$ такой, что $G - V'$ связано: тогда мы можем взять $V_1$ быть $V - V'$ и мы можем $V'$ в наборы по одному элементу в каждом, чтобы получить $V_2,\dots,V_k$. Как мы находим такой$V'$? Интуитивно возьмем остовное дерево$G$ и «отрываем» листья один за другим, пока мы не оторвем $k-1$. Формально мы можем пройти$G$по какому-то алгоритму (например, DFS). Позволять$v_1, \dots, v_n$- порядок, в котором мы посещаем вершины во время этого обхода. Тот факт, что мы смогли пройти по вершинам в этом порядке, показывает, что первые$n-(k-1)$ вершины индуцируют связный подграф $G$, так что мы можем взять $V'$ быть последним $k-1$ вершины.
Что если $G$не подключено? Хорошо, если у него больше связанных компонентов, чем$k$, то такого раздела быть не может (почему?). В противном случае (при условии, что$|V| \geq k$) мы можем использовать, по сути, ту же идею: возьмите покрывающий лес $G$ и отщепляйте листья до тех пор, пока количество отрезанных листьев плюс количество оставшихся связанных компонентов не будет $k$. Опять же, это можно сделать, используя порядок обхода, только в этом случае нужно подумать, чтобы определить, сколько листьев нам нужно оторвать.