Вопросы после параграфа §24 на странице 113, ГДЗ по алгебре за 7 класс к учебнику Высоцкого часть 1

Путь — это последовательность рёбер, по которой можно пройти по графу из одной вершины в другую: каждое следующее ребро начинается в той вершине, где закончилось предыдущее. Путь записывают буквами вершин в порядке прохождения: если в графе есть рёбра \(AC\) и \(CB\), то \(ACB\) — путь из вершины \(A\) в вершину \(B\). Вершины и рёбра в пути могут повторяться.

Ответ: путь — последовательность рёбер, идущих одно за другим, по которой можно пройти из одной вершины графа в другую.

Цепь (простой путь) — это путь, в котором не повторяются ни рёбра, ни вершины. Например, если в графе есть рёбра \(AC\), \(CB\), \(AD\) и \(DC\), то путь \(ACB\) — цепь, а путь \(ADCADCB\) — не цепь: вершины \(A\), \(D\) и \(C\) встречаются в нём дважды. Граф, который весь состоит из одной цепи, тоже называют цепью; цепью считают и граф из одной вершины без рёбер.

Ответ: цепь — путь, в котором не повторяются ни рёбра, ни вершины.

Длина пути — это число рёбер в нём; ребро, по которому путь проходит несколько раз, считается столько раз, сколько его проходят. Например, путь \(ACB\) (рёбра \(AC\) и \(CB\)) имеет длину 2, а путь \(ADCADCB\) — длину 6: по рёбрам \(AD\) и \(DC\) он проходит дважды.

Ответ: длина пути — число рёбер, из которых он состоит.

Да: рёбра в пути могут повторяться, поэтому длина пути бывает больше числа рёбер графа. Например, если \(AB\) — одно из рёбер графа, то путь \(ABABABA\) проходит по нему шесть раз, и его длина равна 6.

Ответ: да, может.

Нет. Вершины в цепи не повторяются: цепь начинается в одной вершине, и каждое следующее ребро приводит в новую вершину. Поэтому вершин в цепи на одну больше, чем рёбер: например, в цепи \(ACB\) два ребра и три вершины, а в цепи из одной вершины рёбер нет вовсе.

Ответ: нет, в цепи рёбер на одно меньше, чем вершин.

Цикл — это замкнутый путь: он начинается и заканчивается в одной и той же вершине, в нём есть хотя бы одно ребро, а промежуточные вершины не повторяются. По одному и тому же ребру цикл дважды не проходит, поэтому путь вида \(ABA\) (туда и обратно по одному ребру) — не цикл. Например, если в графе есть рёбра \(AD\), \(DC\) и \(CA\), то путь из вершины \(A\) через вершины \(D\) и \(C\) обратно в вершину \(A\) — цикл; его обозначают \(ADC\), как треугольник, и начальной можно считать любую его вершину. Простейший цикл — петля: одна вершина и одно ребро.

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

Нет. Если идти по циклу, то из каждой его вершины мы уходим ровно по одному ребру цикла — к следующей вершине, а из последней — обратно в начальную. Вершины в цикле не повторяются, а по одному и тому же ребру цикл дважды не проходит (путь \(ABA\) туда и обратно по одному ребру — не цикл), поэтому рёбер в цикле столько же, сколько вершин. Например, в цикле \(ADC\) три вершины и три ребра, а в петле — одна вершина и одно ребро.

Ответ: нет, в цикле рёбер столько же, сколько вершин.

Связным называют граф, в котором любые две вершины соединены путём. Ребра между ними может и не быть: в графе с рёбрами \(AC\) и \(CB\) вершины \(A\) и \(B\) ребром не соединены, но их соединяет путь \(ACB\), и этот граф связный. Граф из двух отдельных треугольников несвязный: из вершины одного треугольника в вершину другого пути нет.

Ответ: связным называют граф, в котором любые две вершины соединены путём.