1. Главная
  2. Библиотека
  3. Высшая математика
  4. Какие из утверждений верные? (1) Если из полного графа...
Решение задачи на тему

Какие из утверждений верные? (1) Если из полного графа с семью вершинами удалить один цикл длины 3, то получится планарный граф. (2) Обыкновенный граф с пятью вершинами и девятью ребрами - планарный граф (3) Если из полного графа с шестью вершинами

  • Высшая математика
  • #Дискретная математика
  • #Теория графов
Какие из утверждений верные?
(1) Если из полного графа с семью вершинами удалить один цикл длины 3, то получится планарный граф.
(2) Обыкновенный граф с пятью вершинами и девятью ребрами - планарный граф
(3) Если из полного графа с шестью вершинами

Условие:

Какие из утверждений верные?
(1) Если из полного графа с семью вершинами удалить один цикл длины 3, то получится планарный граф.
(2) Обыкновенный граф с пятью вершинами и девятью ребрами - планарный граф
(3) Если из полного графа с шестью вершинами удалить одну из вершин, то получится планарный граф.
(4) Остов полного графа с семью вершинами - планарный граф.

Ответ запишите в формате последовательности из 0 и 1 без пробелов, скобок и запятых (например, 0101): на первом месте запишите 1, если утверждение (1) верное, в противном случае запишите 0; на втором месте запишите 1, если утверждение (2) верное, в противном случае запишите 0; и т.д.

Решение:

Рассмотрим последовательно каждое утверждение.


Утверждение (1): Если из полного графа с семью вершинами удалить один цикл длины 3, то получится планарный граф.

  1. Полный граф с 7 вершинами (K7) имеет 21 ребро.
  2. Удалив цикл длины 3 (то есть 3 ребра, образующие треугольник), остаётся 21 – 3 = 18 ребер.
  3. Для планарного графа с n ≥ 3 вершинами должно выполняться неравенство: E ≤ 3n – 6. Для n = 7 получаем: 3·7 – 6 = 15.
  4. Так как 18 15, полученный граф не может быть планарным.

Вывод: утверждение (1) неверно → 0.

-------------------------...

Выбери предмет