Страница 21 номер 41, ГДЗ по математике за 7, 8 и 9 класс к учебнику Высоцкого 2 часть. Углубленный уровень
Существует ли плоский связный граф, в котором: а) \(v = 7\), \(e = 9\) и \(f = 4\); б) \(v = 7\), \(e = 10\) и \(f = 4\); в) \(v = 5\), \(e = 7\) и \(f = 4\); г) \(v = 5\), \(e = 10\) и \(f = 7\)?
а) \(v - e + f = 7 - 9 + 4 = 2\). Пример: шестиугольник, центр которого соединён с тремя его вершинами, взятыми через одну. Изобразим этот граф и пронумеруем его области. В нём \(v = 7\) вершин, \(e = 6 + 3 = 9\) рёбер и \(f = 4\) области: три четырёхугольные внутри шестиугольника и внешняя. Такой граф существует.
б) \(v - e + f = 7 - 10 + 4 = 1\), а не 2. Формула Эйлера не выполняется, поэтому такого графа нет.
в) \(v - e + f = 5 - 7 + 4 = 2\). Пример: квадрат, центр которого соединён с тремя его вершинами. В нём \(v = 5\) вершин, \(e = 4 + 3 = 7\) рёбер и \(f = 4\) области: две треугольные, одна четырёхугольная и внешняя. Такой граф существует.
г) \(v - e + f = 5 - 10 + 7 = 2\). Без кратных рёбер и петель такого графа нет: каждая из пяти вершин была бы соединена не больше чем с четырьмя другими, сумма степеней вершин была бы не больше \(5 \cdot 4 = 20\), а рёбер — не больше \(20 : 2 = 10\). Рёбер ровно 10, только если каждые две вершины соединены, а это граф пяти площадей — он не планарный. Поэтому в примере есть кратные рёбра: пятиугольник, у которого каждые две соседние вершины соединены двумя рёбрами. В нём \(v = 5\) вершин, \(e = 5 \cdot 2 = 10\) рёбер и \(f = 7\) областей: пять областей между кратными рёбрами, область внутри пятиугольника и внешняя. Такой граф существует.
Ответ: а) существует; б) не существует; в) существует; г) существует.
Существует ли плоский связный граф, в котором: а) \(v = 7\), \(e = 9\) и \(f = 4\); б) \(v = 7\), \(e = 10\) и \(f = 4\); в) \(v = 5\), \(e = 7\) и \(f = 4\); г) \(v = 5\), \(e = 10\) и \(f = 7\)?
Для любого конечного связного плоского графа выполняется формула Эйлера \(v - e + f = 2\). Если данные числа ей не удовлетворяют, такого графа нет. Если удовлетворяют, этого ещё мало: существование графа доказывает только пример.
а) \(v - e + f = 7 - 9 + 4 = 2\). Пример: шестиугольник, центр которого соединён с тремя его вершинами, взятыми через одну. Изобразим этот граф и пронумеруем его области. В нём \(v = 7\) вершин, \(e = 6 + 3 = 9\) рёбер и \(f = 4\) области: три четырёхугольные внутри шестиугольника и внешняя. Такой граф существует.
б) \(v - e + f = 7 - 10 + 4 = 1\), а не 2. Формула Эйлера не выполняется, поэтому такого графа нет.
в) \(v - e + f = 5 - 7 + 4 = 2\). Пример: квадрат, центр которого соединён с тремя его вершинами. В нём \(v = 5\) вершин, \(e = 4 + 3 = 7\) рёбер и \(f = 4\) области: две треугольные, одна четырёхугольная и внешняя. Такой граф существует.
г) \(v - e + f = 5 - 10 + 7 = 2\). Без кратных рёбер и петель такого графа нет: каждая из пяти вершин была бы соединена не больше чем с четырьмя другими, сумма степеней вершин была бы не больше \(5 \cdot 4 = 20\), а рёбер — не больше \(20 : 2 = 10\). Рёбер ровно 10, только если каждые две вершины соединены, а это граф пяти площадей — он не планарный. Поэтому в примере есть кратные рёбра: пятиугольник, у которого каждые две соседние вершины соединены двумя рёбрами. В нём \(v = 5\) вершин, \(e = 5 \cdot 2 = 10\) рёбер и \(f = 7\) областей: пять областей между кратными рёбрами, область внутри пятиугольника и внешняя. Такой граф существует.
Ответ: а) существует; б) не существует; в) существует; г) существует.
