Yurii Nosov » Публикация
Поделиться публикацией:
Опубликовано
2015-09-15
Опубликовано на SciPeople2020-05-03 19:51:59
ЖурналПрикладная дискретная математика
О максимальных внешнеплоских графах с двумя симплициальными вершинами
ПДМ,2015,3(29),С.95–109.
УДК 519.17; DOI:10.17223/20710410/29/8
Аннотация
Рассматриваются максимальные внешнеплоские графы (МВП-графы) с двумя
симплициальными вершинами. Для графов этого класса получены: рекурсивная
характеризация, формула для расчёта количества непомеченных графов и полный
инвариант, отличающийся от известного полного инварианта произвольных МВПграфов. Описан полиномиальный алгоритм вычисления полного инварианта.