Страница 5 номер 1, ГДЗ по математике за 7, 8 и 9 класс к учебнику Высоцкого 2 часть. Углубленный уровень
Какие из графов на рисунке 5 являются деревьями?
а) Каждая вершина соединена ребром с центральной, поэтому любые две вершины соединены путём через центральную — граф связный. Циклов нет: у каждого ребра один конец — вершина степени 1, а через вершину степени 1 цикл пройти не может. Значит, граф а) — дерево.
б) Каждая вершина степени 1 соединена ребром с одной из двух центральных вершин, а центральные вершины соединены между собой — граф связный. Все рёбра, кроме ребра между центральными вершинами, ведут к вершинам степени 1 и в цикл входить не могут, а одно ребро между двумя вершинами цикла не образует. Значит, циклов нет, и граф б) — дерево.
в) Граф — цепь из трёх вершин, а цепь — дерево: она связна и циклов в ней нет.
г) Граф состоит из двух частей, и ни одна вершина одной части не соединена путём ни с одной вершиной другой: граф несвязный, поэтому он не дерево, хотя циклов в нём нет.
д) Замкнутая линия из девяти вершин — цикл, поэтому граф не дерево, хотя он и связный.
Ответ: деревья — графы а), б) и в).
Какие из графов на рисунке 5 являются деревьями?
Дерево — связный граф без циклов, поэтому у каждого графа проверяем оба условия.
а) Каждая вершина соединена ребром с центральной, поэтому любые две вершины соединены путём через центральную вершину — граф связный. Циклов нет: у каждого ребра один конец — вершина степени 1, а через вершину степени 1 цикл пройти не может (войти в неё можно, а выйти по другому ребру нельзя). Значит, граф а) — дерево.
б) Каждая вершина степени 1 соединена ребром с одной из двух центральных вершин, а центральные вершины соединены между собой — граф связный. Все рёбра, кроме ребра между центральными вершинами, ведут к вершинам степени 1 и в цикл входить не могут, а одно ребро между двумя вершинами цикла не образует. Значит, циклов нет, и граф б) — дерево.
в) Граф — цепь из трёх вершин, а цепь — дерево: она связна и циклов в ней нет.
г) Граф состоит из двух частей, и ни одна вершина одной части не соединена путём ни с одной вершиной другой. Граф несвязный, поэтому он не дерево, хотя циклов в нём нет.
д) Замкнутая линия из девяти вершин — цикл. Граф с циклом деревом не является, хотя он и связный.
Ответ: деревья — графы а), б) и в).
