В.И. Петрунин, В.П. Полесский

2-связный 2-лесистый граф с заданным числом вершин и ребер с минимальным числом остовов

Под редкой топологией сети передачи информации понимают 2-связный граф и граф с небольшим (относительно заданного числа вершин) числом ребер, соответственно. Простейшими и реальными примерами редких топологий служат 2-связные 2-лесистые графы. Дополнительной мерой качества в 2-связной топологии может служить количество остовов. В классе 2-связных 2-лесистых графов с заданным числом вершин и ребер найден подкласс, имеющий наименьшее число остовов - наихудшая (по чиcлу оставов) 2-лесистая топология.