|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Перечисление всех остовных деревьев с точностью до изоморфизма для некоторых классов графовкурсовая работа (Бакалавр)
- Научный руководитель: Половников В.С.
- Автор: Измайлова А.А.
- Тип: Бакалавр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Кафедра: Филиал МГУ в г. Ташкент
- Год защиты: 2017
- Курс: 3
- Аннотация: Александра обобщила алгоритм проверки корневых деревьев на изоморфизм до произвольных деревьев и доказала его линейность. Следовательно, для любых классов графов, где количество занумерованных деревьев зависит от числа вершин полиномиально, существует эффективный алгоритм перечисления неизоморфных остовных деревьев. Это и было продемонстрировано в курсовой работе Измайловой. В качестве исследуемого класса были выбраны графы с фиксированным цикломатическим числом γ. Для них существует не более n^γ занумерованных остовных деревьев. Измайлова А.А. показала, что алгоритм перечисления неизоморфных остовных деревьев имеет сложность O(n^(2γ+1)).
- Добавил в систему: Половников Владимир Сергеевич