Перерисуйте графы, изображённые на рисунке 59, так, чтобы их рёбра не пересекались.
Рисунок 59: а) вершины 1, 2, 3 в верхнем ряду и 4, 5, 6 в нижнем; рёбра 1–4, 1–5, 1–6, 2–4, 2–6, 3–4, 3–5, 3–6 («три домика — три колодца» без тропинки 2–5). б) Вершины 1 (вверху), 2 (справа вверху), 3 (слева), 4 (справа внизу), 5 (внизу); рёбра 1–2, 1–3, 1–4, 1–5, 2–3, 2–4, 2–5, 3–4, 3–5 — полный граф без ребра 4–5. в) 9 вершин, расположенных по кругу, и 21 ребро, многие из которых пересекаются.
Вершины 1 и 3 соединены со всеми тремя вершинами 4, 5, 6, а вершина 2 — только с 4 и 6. Нарисуем четырёхугольник 1–4–3–6–1 (рёбра 1–4, 4–3, 3–6, 6–1). Вершину 5 поместим внутри четырёхугольника и соединим с 1 и 3, вершину 2 — снаружи и соединим с 4 и 6. Все 8 рёбер проведены, пересечений нет.
Вершины 1, 2, 3 попарно соединены — нарисуем их треугольником. Вершины 4 и 5 соединены с каждой из вершин 1, 2, 3, но не друг с другом. Поместим 4 внутрь треугольника, а 5 — снаружи, и соединим каждую с тремя вершинами треугольника. Все 9 рёбер проведены без пересечений (это граф треугольной бипирамиды, «сплющенной» на плоскость).
У графа 9 вершин и 21 ребро — ровно \( 3 \cdot 9 - 6 = 21 \), наибольшее число рёбер, какое вообще может быть у планарного графа с 9 вершинами (см. упражнение 102). Значит, в правильном изображении все грани, включая внешнюю, будут треугольниками, и рисовать нужно аккуратно.
Способ. 1) Выпишите список рёбер каждой вершины по матрице смежности рисунка. 2) Найдите в графе треугольник и нарисуйте его большим — это будет внешняя грань. 3) Добавляйте вершины по одной: каждую новую вершину помещайте внутрь той грани, на границе которой лежат все уже нарисованные её соседи, и соединяйте с ними; грань разобьётся на несколько новых. 4) Если для какой-то вершины такой грани нет, попробуйте иначе выбрать внешний треугольник или порядок добавления вершин. При 21 ребре каждый шаг должен разбивать грань-треугольник на три треугольника, поэтому вершину степени 3 всегда добавляют последней.
Полезная проверка готового рисунка — формула Эйлера: \( B - P + \Gamma = 9 - 21 + \Gamma = 2 \), то есть граней должно получиться \( \Gamma = 14 \).
Задали работу по этой теме?
Реферат, доклад или проект по параграфу: план, текст, таблицы и оформление по требованиям.
ВНИМАНИЕ: Представленные фрагменты из учебных материалов используются исключительно в научно-образовательных целях в объеме, оправданном поставленной целью.
Данное использование осуществляется в рамках, установленных законодательством об авторском праве (в частности, нормами о свободном использовании произведения для образовательных целей).
В соответствии с законодательством, автор и источник заимствования указаны для каждого используемого фрагмента.
