Вопрос:

120 На рисунке 21 изображён граф. С помощью Движения вершин изобразите этот граф так, чтобы рёбра не пересекались во внутренних точках (получатся два одинаковых графа). Рисунок 21

Смотреть решения всех заданий с листа

Ответ:

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

  1. Переместите одну из верхних вершин графа вниз, чтобы она оказалась ниже нижней линии вершин.
  2. Переместите остальные верхние вершины таким образом, чтобы ни одно из рёбер не пересекалось.

В результате получится два одинаковых графа, в которых рёбра не пересекаются во внутренних точках.

Пример изображения графа до и после преобразования (схематично, псевдографикой):

До преобразования:

    o---o---o
   /|\ /|\ /|\
  / | \/ | \/ | \
 o--o--o--o--o--o

После преобразования:

      o---o---o
     /   /   /  
    /   /   /   
   /   /   /    
  o--o--o--o--o--o
   \   \   \    
    \   \   \   
     \   \   \  
      o---o---o

В данном примере верхние вершины были перемещены вниз, чтобы избежать пересечения рёбер.

Ответ: Граф изображён без пересечения рёбер во внутренних точках.

ГДЗ по фото 📸
Подать жалобу Правообладателю