Урок 19. Плоские графы Задание 1 Укажите, сколько вершин, рёбер и граней: а) у графа на рисунке 2; 6) графа на рисунке 5; в) дерева, у которого 10 вершин; г) дерева, у которого 100 вершин. Задание 2. Изобразите пять различных плоских графов с различным количеством вершин. Вычислите для каждого количество вершин (В), рёбер (Р) и граней (Г). Задание 3. Докажите, что для плоского графа, у которого более трёх рёбер, верно неравенство 2P > ЗГ. Задание 4. Выпишите результаты задания 1 и задания 2 в виде таблицы следующего вида. B 4 8 P 6 11 Г 4 5 Попробуйте отыскать связь между этими тремя величинами, которая будет выполняться для каждой строки вашей таблицы. Если нужно, рассмотрите ещё несколько примеров плоских графов с небольшим количеством вершин. Задание 5. Вычислите величину В Р+Г для произвольного дерева. Задание 6. В парке десять небольших озёр, соединённых между собой семнадцатью непересекающимися каналами, причём от каждого озера можно доплыть до любого другого. Сколько в этом парке островов? Задание 7. Изобразите граф, в котором пять вершин и все вершины соединены друг с другом. а) Сколько в таком графе рёбер? б) Является ли он планарным? Задание 8. Рассмотрим граф, вершины которого можно разбить на две части так, что каждое ребро соединяет вершину из одной части с вершиной другой части. Такие графы называются двудольными. а) Докажите, что для двудольного планарного графа, в котором больше двух рёбер, выполнено условие: 2P ≥ 4Г. 6) Докажите, что граф на рисунке 7 не является планарным. Задания для самостоятельного решения Задание 9. Внутри квадрата отметили 33 точки и соединили их непересекающимися отрезками друг с другом и вершинами квадрата так, что квадрат разбился на треугольники. Сколько провели отрезков и сколько получилось треугольников? Задание 10. В старом средневековом городе шесть площадей. Каждая площадь соединена прямыми улицами ровно с тремя другими площадями. Никакие две улицы в городе не пересекаются. Начертите возможный план такого города. Задание 11. В старом саду есть 6 больших деревьев, которые нужно соединить между собой прямыми дорожками, причём от каждого дерева должно выходить 4 дорожки. Можно ли нарисовать схему таких дорожек, чтобы они не пересекались? Задание 12. Докажите, что в планарном графе есть вершина, степень которой не превосходит 5.