Страница 14 номер 26, ГДЗ по математике за 7, 8 и 9 класс к учебнику Высоцкого 2 часть. Углубленный уровень
Какие из графов, изображённых на рисунке 24, являются остовными деревьями графа, изображённого на рисунке 23?
Исходный граф — верхний на рисунке — связный: в нём 7 вершин (шесть вершин шестиугольника и его центр) и 12 рёбер (шесть сторон шестиугольника и шесть отрезков из центра). В остовном дереве все 7 вершин исходного графа и только его рёбра, а само оно — связный граф без циклов. В конечном дереве вершин на одну больше, чем рёбер, значит, в остовном дереве \(7 - 1 = 6\) рёбер.
а) Центр не соединён ребром ни с одной вершиной — граф несвязный; кроме того, стороны шестиугольника образуют цикл. Граф а) — не дерево, хотя рёбер в нём 6.
б) Все 7 вершин на месте, 6 рёбер — отрезки из центра, то есть рёбра исходного графа. Любые две вершины соединены путём через центр, поэтому граф связный. Циклов нет: через вершину, у которой одно ребро, цикл пройти не может (в вершину цикла входят по одному ребру, а выходят по другому), у всех вершин шестиугольника по одному ребру, а петли у центра нет. Граф б) — остовное дерево.
в) В графе 8 рёбер, и в нём есть циклы: например, центр, левая верхняя, левая и левая нижняя вершины шестиугольника образуют цикл-ромб. Граф с циклом — не дерево.
г) Все 7 вершин на месте, 6 рёбер — четыре стороны шестиугольника и два отрезка из центра, то есть рёбра исходного графа. Они образуют цепь через все вершины: от левой нижней вершины шестиугольника через левую, левую верхнюю, центр, правую нижнюю и правую к правой верхней. Цепь — связный граф без циклов, значит, граф г) — остовное дерево.
Ответ: остовными деревьями являются графы б) и г).
Какие из графов, изображённых на рисунке 24, являются остовными деревьями графа, изображённого на рисунке 23?
Исходный граф — верхний на рисунке — связный: в нём 7 вершин (шесть вершин шестиугольника и его центр) и 12 рёбер (шесть сторон шестиугольника и шесть отрезков, соединяющих центр с вершинами шестиугольника). Остовное дерево получается из него удалением рёбер, поэтому в остовном дереве все 7 вершин исходного графа и только его рёбра, а само оно — связный граф без циклов. В конечном дереве вершин на одну больше, чем рёбер, значит, в остовном дереве \(7 - 1 = 6\) рёбер.
а) Центр не соединён ребром ни с одной вершиной — граф несвязный; кроме того, стороны шестиугольника образуют цикл. Граф а) — не дерево, хотя рёбер в нём 6.
б) Все 7 вершин на месте, 6 рёбер — отрезки из центра, то есть рёбра исходного графа. Любые две вершины соединены путём через центр, поэтому граф связный. Циклов нет: через вершину, у которой одно ребро, цикл пройти не может (в вершину цикла входят по одному ребру, а выходят по другому), у всех вершин шестиугольника по одному ребру, а петли у центра нет. Граф б) — остовное дерево.
в) В графе 8 рёбер, и в нём есть циклы: например, центр, левая верхняя, левая и левая нижняя вершины шестиугольника образуют цикл-ромб. Граф с циклом — не дерево.
г) Все 7 вершин на месте, 6 рёбер — четыре стороны шестиугольника и два отрезка из центра, то есть рёбра исходного графа. Они образуют цепь через все вершины: от левой нижней вершины шестиугольника через левую, левую верхнюю, центр, правую нижнюю и правую к правой верхней. Цепь — связный граф без циклов, значит, граф г) — остовное дерево.
Ответ: остовными деревьями являются графы б) и г).
