Номер 16, страница 9, часть 2 - гдз по алгебре 7-9 класс учебник Высоцкий, Ященко

16 Будет ли связным граф, который получится из дерева, если из него удалить:

а) ребро, связывающее две неконцевые вершины;

б) концевую вершину вместе с выходящим из неё ребром?

а) ребро, связывающее две неконцевые вершины;

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

Пусть $T = (V, E)$ — исходное дерево. Удалим из него ребро $e = (u, v)$, где $u$ и $v$ — неконцевые вершины (то есть их степень больше единицы: $\text{deg}(u) > 1$ и $\text{deg}(v) > 1$). Получим новый граф $T' = (V, E \setminus \{e\})$.

В исходном дереве $T$ между вершинами $u$ и $v$ был уникальный путь, состоящий из одного ребра $e$. После удаления этого ребра в графе $T'$ путь между $u$ и $v$ исчезает. Если бы существовал какой-то другой путь между $u$ и $v$ в $T'$, то этот путь существовал бы и в исходном графе $T$. Тогда в $T$ было бы как минимум два различных пути между $u$ и $v$: один по ребру $e$, а другой — альтернативный. Наличие двух путей означало бы существование цикла, что противоречит определению дерева.

Таким образом, после удаления ребра $e$ вершины $u$ и $v$ оказываются в разных компонентах связности. Это означает, что граф $T'$ становится несвязным. Он распадается на два подграфа (два меньших дерева). Условие, что вершины неконцевые, этого факта не меняет.

Ответ: нет, не будет.

б) концевую вершину вместе с выходящим из неё ребром?

Пусть $T = (V, E)$ — исходное дерево. Концевая вершина (или лист) — это вершина, степень которой равна 1. Обозначим эту вершину как $l$, а единственное инцидентное ей ребро как $e = (l, u)$, где $u$ — смежная с $l$ вершина. Мы удаляем вершину $l$ и ребро $e$, получая новый граф $T' = (V \setminus \{l\}, E \setminus \{e\})$.

Чтобы проверить связность графа $T'$, нужно показать, что между любыми двумя его вершинами существует путь. Возьмём две произвольные различные вершины $x$ и $y$ из множества вершин графа $T'$. Эти вершины также принадлежат и исходному дереву $T$.

Поскольку $T$ — связный граф, в нём существует уникальный простой путь $P$, соединяющий вершины $x$ и $y$. Этот путь не может проходить через вершину $l$, так как $l$ — концевая вершина ($\text{deg}(l)=1$). Любой путь, содержащий вершину $l$, должен либо начинаться, либо заканчиваться в ней. Он не может "пройти сквозь" $l$, так как для этого вершина должна иметь степень не менее двух.

Поскольку ни $x$, ни $y$ не являются вершиной $l$, путь $P$ между ними в графе $T$ не содержит ни вершину $l$, ни инцидентное ей ребро $e$. Это означает, что весь путь $P$ состоит из вершин и рёбер, которые не были удалены и остались в графе $T'$.

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

Ответ: да, будет.