Тесты СинергияАртём Хелп
Артём Help онлайнПолучить расчёт
Бесплатно оценим сроки и стоимостьОтправить задание в Telegram
Теория графов.dor_БАК_25-122-Б

Теория графов.dor_БАК_25-122-Б — вариант 5

Просмотрите все вопросы и варианты бесплатно. Правильные ответы скрыты и открываются только после получения доступа.

11 вопросов Вариант 5 Доступ 7 дней
Содержание теста

Вопросы и варианты

Без отметок и подсказок к правильным ответам

Вопрос 1

Соотнесите понятия из теории графов с их определениями:

  1. Планарные графы
  2. Грань
  3. Триангуляция
  4. Гомеоморфные графы
  5. графы, допускающие укладку без пересечений ребер
  6. область плоскости, ограниченная ребрами
  7. плоский граф, где каждая грань является треугольником
  8. графы, получаемые друг из друга операциями подразделения ребер
Вопрос 2

Упорядочьте шаги построения плоского вложения графа:

  1. определить количество ребер и вершин
  2. проверить планарность графа
  3. нарисовать вершины
  4. расставить ребра без пересечений
  5. определить грани вложения
Вопрос 3

Для связного планарного графа с 8 вершинами максимальное количество ребер – …

  1. 12
  2. 16
  3. 18
  4. 24
Вопрос 4

Согласно теореме Понтрягина–Куратовского, минимальным непланарным является граф …

  1. K4
  2. K3,2
  3. K3,3
  4. «дерево»
Вопрос 5

Неверно, что планарный граф …

  1. характеризуется тем, что для него выполняется формула Эйлера
  2. не содержит подграфов, гомеоморфных K5
  3. характеризуется тем, что все его вершины имеют степень ≤ 5
  4. может быть изображен на сфере
Вопрос 6

Говоря о деревьях, можно утверждать, что эти графы …

  1. всегда имеют несколько граней
  2. могут быть непланарными
  3. имеют ровно одну грань при плоской укладке
  4. не подчиняются формуле Эйлера
Вопрос 7

Грань в планарном графе – это …

  1. множество вершин
  2. область плоскости, ограниченная ребрами
  3. подграф без циклов
  4. максимальное независимое множество
Вопрос 8

Количество граней, которое имеет дерево с 10 вершинами при плоской укладке, – …

  1. один
  2. 1
  3. 1 грань
  4. одна
  5. одна грань
Вопрос 9

… граф – это граф, который можно изобразить на плоскости без пересечений ребер

  1. Планарный
Вопрос 10

Количество граней, которое имеет полный граф K₄ при планарной укладке, – …

  1. 4
  2. четыре
  3. 4 грани
  4. четыре грани
Вопрос 11

Имеется связный граф с 12 вершинами и 20 ребрами. Какое максимальное количество граней может иметь плоское вложение этого графа?

  1. 9
  2. 10
  3. 11