Условие:
Укажите графы, гомеоморфные дереву Т с кодом 2325:
(1) Полный граф с тремя вершинами.
(2) Простая цепь длины 4.
(3) Полный двудольный граф
Решение:
Обычно говорят, что два графа являются гомеоморфными, если один может быть получен из другого последовательными операциями вставки (или, обратно, удаления) вершин со степенью 2 – то есть, если их «сглаженные» (основные) структуры совпадают.
В данной задаче дерево T задано кодом 2325. Такой код можно интерпретировать как прюферовский код дерева. Напомним, что если у дерева на n вершинах прюферовский код имеет длину n–2, то имея код из 4 цифр, получаем n = 6. Тогда частоты появления цифр дают степени вершин по правилу: степень вершины = (число появлений в коде) +
1.
<...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Что нужно знать по теме:
Что нужно знать по теме
Алгоритм решения
Топ 3 ошибок
Что спросит препод
Похожие задачи