Страница 9 номер 16, ГДЗ по математике за 7, 8 и 9 класс к учебнику Высоцкого 2 часть. Углубленный уровень
Будет ли связным граф, который получится из дерева, если из него удалить: а) ребро, связывающее две неконцевые вершины; б) концевую вершину вместе с выходящим из неё ребром?
а) Если из дерева удалить ребро, граф перестанет быть связным: будь он связным, вершины удалённого ребра соединяла бы в нём цепь, и вместе с этим ребром она образовала бы цикл в исходном дереве, а в дереве циклов нет. Это верно для любого ребра, в том числе для ребра, которое связывает две неконцевые вершины. Значит, граф будет несвязным.
б) Любые две оставшиеся вершины в дереве соединяет цепь, и удалённая концевая вершина в эту цепь не входит: концом цепи она не является, а промежуточной быть не может — в промежуточную вершину цепи входят по одному ребру и выходят по другому, а у концевой вершины ребро одно. Значит, эта цепь сохранилась, и любые две оставшиеся вершины по-прежнему соединены. Граф останется связным.
Ответ: а) нет, граф будет несвязным; б) да, граф останется связным.
Будет ли связным граф, который получится из дерева, если из него удалить: а) ребро, связывающее две неконцевые вершины; б) концевую вершину вместе с выходящим из неё ребром?
а) Если из дерева удалить ребро, граф перестанет быть связным. Действительно, будь он связным, вершины удалённого ребра соединяла бы в нём цепь, и вместе с этим ребром она образовала бы цикл в исходном дереве, а в дереве циклов нет. Это верно для любого ребра, в том числе для ребра, которое связывает две неконцевые вершины. Значит, граф будет несвязным.
б) Пусть из дерева удалили концевую вершину вместе с её ребром. Возьмём любые две оставшиеся вершины. В дереве их соединяет цепь, и удалённая вершина в эту цепь не входит: концом цепи она не является, а промежуточной быть не может — в промежуточную вершину цепи входят по одному ребру и выходят по другому, а у концевой вершины ребро одно. Значит, эта цепь сохранилась, и любые две оставшиеся вершины по-прежнему соединены. Граф останется связным.
Ответ: а) нет, граф будет несвязным; б) да, граф останется связным.
