О ВЕРХНЕЙ ОЦЕНКЕ КОЛИЧЕСТВА ДОПОЛНИТЕЛЬНЫХ РЕБЕР ДЛЯ МИНИМАЛЬНЫХ РЕБЕРНЫХ 1-РАСШИРЕНИЙ СВЕРХСТРОЙНЫХ ДЕРЕВЬЕВ СПЕЦИАЛЬНОГО ВИДА | Компьютерные науки и информационные технологии

Сообщение об ошибке

Warning: fopen(http://www.sgu.ru/exchange/index.php?stat1=1): failed to open stream: HTTP request failed! HTTP/1.1 404 Not Found в функции eval() (строка 2 в файле /www/knit2012/modules/php/php.module(80) : eval()'d code).

Warning: fread() expects parameter 1 to be resource, boolean given в функции eval() (строка 3 в файле /www/knit2012/modules/php/php.module(80) : eval()'d code).

Warning: fclose() expects parameter 1 to be resource, boolean given в функции eval() (строка 4 в файле /www/knit2012/modules/php/php.module(80) : eval()'d code).

Задача нахождения минимального реберного расширения произвольного графа является NP-полной , поэтому представляет интерес нахождение классов графов, для которых возможно построить минимальное реберное расширение аналитически или найти «хорошую» верхнюю (нижнюю) оценку количества дополнительных ребер минимального расширения. В данной работе рассматривается верхняя оценка количества дополнительных ребер 1-расширений сверхстройных деревьев специального вида.

Материалы конференции: