Yurii Nosov » Публикация

Поделиться публикацией:

Опубликовано 2015-09-15 Опубликовано на SciPeople2020-05-03 19:51:59 ЖурналПрикладная дискретная математика

О максимальных внешнеплоских графах с двумя симплициальными вершинами

Носов Ю.Л. / Yurii Nosov

ПДМ,2015,3(29),С.95–109. УДК 519.17; DOI:10.17223/20710410/29/8

Аннотация Рассматриваются максимальные внешнеплоские графы (МВП-графы) с двумя симплициальными вершинами. Для графов этого класса получены: рекурсивная характеризация, формула для расчёта количества непомеченных графов и полный инвариант, отличающийся от известного полного инварианта произвольных МВПграфов. Описан полиномиальный алгоритм вычисления полного инварианта.