True2008,

T>направленный граф и ориентированный граф это одно и то же. ориентированный и неориентированный графы являются частными случаями смешанного. силлогизм: для смешанного графа — Chinese postman problem NP-hard, следовательно для ориентированного(направленного), частного случая смешанного, Chinese postman problem так же NP-hard.


Силлогизм конечно же не верен. Если задача NP-трудна, то это НЕ значит, что частный случай этой задачи NP-труден. Для примера можете взять задачу коммивояжёра с длинами дуг == 1, насколько трудно её решить? Во.