1. Главная
  2. Библиотека
  3. Другое
  4. В каких семействах графов реализуется степенная последо...
Разбор задачи

В каких семействах графов реализуется степенная последовательность: а) ; ) ) ; ) ;

  • Предмет: Другое
  • Автор: Кэмп
В каких семействах графов реализуется степенная последовательность: а) ; ) ) ; ) ;

Условие:

В каких семействах графов реализуется степенная последовательность: а) 2,2,1,1,1,12,2,1,1,1,1;\nb) 4,4,2,2,1,1;4,4,2,2,1,1 ;\nc) 11,3,2,2,1,111,3,2,2,1,1;\nd) 3,2,2,2,1,13,2,2,2,1,1;

Решение:

Найдем, для какой из данных последовательностей существует граф, а если нет – то для какого семейства (простых графов, мультиграфов, деревьев, лесов) она реализуется.

Задача состоит из четырех пунктов. Рассмотрим каждый по шагам.

––––––
Пункт а) 2, 2, 1, 1, 1, 1

  1. Вычислим сумму степеней:
      2 + 2 + 1 + 1 + 1 + 1 =
    8.
      Сумма чётная – необходимое условие.
  2. Применим процедуру (например, алгоритм Хавела–Хакими) – легко проверить, что последовательность графическая.
  3. Если рассматривать граф на 6 вершинах, то дерево...

Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит

Попробуй решить по шагам

Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение

Какое из следующих утверждений о степенных последовательностях графов является верным?

Что нужно знать по теме:

Что нужно знать по теме

Алгоритм решения

Топ 3 ошибок

Что спросит препод

Похожие задачи

Похожие задачи

Не нашел нужную задачу?Воспользуйся поиском

AI помощники

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

E
S
А
Б
В
Г
Д
Е
Ж
З
И
К
Л
М
Н
О
П
Р
С
Т
У
Ф
Х
Ц
Ч
Э
Я