Докажите или опровергните: в связном, но неполном графе существуют три вершины a,b,c, удовлетворяющие условиям a и b, имеющие общего соседа c
Можем ли мы найти в связном графе, который не является полным, три вершины, обозначаемые a,b,c, такие, что a смежна с b, b смежна с c, но a и c не являются соседями?
Это задача теории графов из моего учебника по информатике под названием «Теория графов и алгоритм». Узнав определение разрезаемой вершины и моста, а также алгоритм Тарьяна для поиска разрезаемой вершины, мой учитель поднял эту проблему. В какой-то степени это очевидно, но формализованная проверка необходима.
Я попытался предположить обратное, что мы не можем найти такие три вершины. И тогда необходимо рассмотреть три ситуации: среди произвольных трех вершин этого графа нет или есть одна или три пары соседей. Это меня очень смутило.
Спасибо за ваше редактирование.
Ответы 2
Поскольку граф неполный, в графе есть две вершины, скажем A и Z, без ребра AZ. Поскольку граф связен, существует некоторый путь A B C … X Y Z. На этом пути есть хотя бы одна вершина с ребром в Z, поскольку Y — единица. Пусть Q — первая такая вершина. Пусть P — предыдущая вершина пути. Тогда PZ на графике нет, а PQ и QZ есть.
Спасибо за ваш ответ! Я думаю, что только когда путь самый короткий, PZ точно нет в графе. В противном случае PZ, возможно, присутствует в графе. Вы согласны со мной?
@advance: Нет. Q определяется как первая вершина пути, в которой QZ находится в графе. Поскольку P предшествует Q, PZ нет в графе.
На этом пути ПЗ нет в графе. Но может быть есть какой-то другой путь, соединяющий P и Z? Я как бы не понимаю, что означает предыдущее.
@advance: Нас не волнует, связаны ли P и Z. (Мы знаем, что это так, поскольку граф полон.) Критерий состоит в том, чтобы найти A, B и C, где AB и BC есть в графе, а AC нет. P, Q и Z удовлетворяют этому требованию, поскольку PQ и QZ присутствуют на графике, а PZ — нет.
Спасибо! «Q — первая вершина на этом пути такая, что QZ находится в графе» означает, что вершины, предшествующие Q, не смежны с Z? Как мы можем это гарантировать?
@advance: Как уже говорилось, тот факт, что граф связен, означает, что существует путь от A до Z. Мы знаем, что AZ нет в графе. Исследуйте вторую вершину на пути, чтобы увидеть, есть ли у нее ребро, ведущее к Z. Если нет, проверьте третью. Потом четвертый. И так до тех пор, пока не будет найдена вершина с ребром в Z. Она должна быть, так как предпоследняя вершина имеет ребро, ведущее к Z, и должна быть первая вершина.
ХОРОШО! Большое спасибо за ваше терпение. Я понимаю! Идея фантастическая!
Обозначение:
- Обозначим через A-B вершины A и B такие, что A смежна с B.
- Обозначим через A-B-C вершины A, B, C такие, что A смежна с B, B смежна с C, но A и C не смежны.
Обратите внимание, что в любом индуцированном подграфе S графа G, если существует A-B-C в S, то существует тот же самый A-B-C в G.
Заявление. В связном графе G, который не является полным, в G существует A-B-C.
Предположим, что утверждение неверно.
Базовый случай: рассмотрим любой индуцированный подграф S_3 связного графа G, содержащий ровно три вершины A, B, C такие, что A-B и B-C. (Очевидно, что такой подграф существует, иначе G не может быть связным.) Теперь, если A-B-C, утверждение будет истинным, поэтому это означает, что A-C. Однако S_3 теперь завершен. Таким образом, любой связный индуцированный подграф S_3 связного G, содержащий ровно три вершины, обязательно должен быть полным.
Индуктивный шаг: пусть S_(k-1) = {A, B, ..., J} — полный индуцированный строгий подграф связного G, содержащий ровно (k-1) вершин. Поскольку G связен, должен существовать связный индуцированный подграф S_k = {A, B, ..., J, K} ровно из k вершин, который имеет вышеупомянутый S_(k-1) в качестве подграфа. WLOG, произнесите KA, чтобы обеспечить связь. Более того, для любой вершины X из {B,...,J} имеем A-X. Теперь, если бы K-A-X, утверждение было бы истинным, так что это означает, что K-X. Таким образом, S_k завершен.
Очевидно, по индукции существует последовательность S_3, S_4, S_5, ..., G полных индуцированных подграфов G. Однако мы предполагали, что G не должен быть полным.
Мы пришли к противоречию, а значит, утверждение должно быть истинным.
Думаю, вы здесь употребили неправильное слово: «Однако S теперь подключен». Мы знали, что S связен, потому что он содержит AB и BC, поэтому существует путь от A до C. Я думаю, вы имеете в виду, что S является полным, то есть содержит все ребра между A, B и C.
Re «Таким образом, любой индуцированный подграф S группы G, содержащий ровно три вершины, обязательно должен быть связным, чтобы утверждение было ложным»: Вы этого не показали. Вы показали, что любой индуцированный подграф S графа G, содержащий три вершины такие, что A-B и B-C, должен быть полным (несвязным). Это не говорит о индуцированных подграфах графа G, содержащих ровно три вершины, имеющих ноль или одно ребро.
@Eric Postpischil Да, это правда. Нам нужно обсудить три вершины, которые имеют ноль или одно ребро.
@EricPostpischil Вы правы, то, что я сказал, не убедительно показывает, что G должен быть полным. Думаю, мне удалось восстановить доказательство, хотя оно и не сформулировано особенно элегантно.
Кажется правдой, судя по быстрому визуальному доказательству. Начните с трех соединенных вершин A-B-C. Если А и С не соседние, то нужно их соединить. Но теперь график завершен. Так мы соединяем еще одну вершину D-A. Но теперь Д-А-Б и Д-А-С. Итак, соединяем B-D и CD. Но теперь это полный график. Итак, соединяем еще одну вершину Е-А... До бесконечности.