Я рассматриваю ориентированный граф. Мне нужно показать, что если такой граф имеет гамильтонов цикл, то мы можем записать его матрицу смежности A как A = P + C, где P - матрица перестановок, а C - неотрицательный.
Я рассуждал так: если A имеет гамильтонов цикл, то это должно означать, что каждая строка и столбец матрицы смежности для A будет содержать ровно одну запись в «1» и все остальные нули. Это также определение матрицы перестановок. Поэтому, если я напишу A - P = C и скажу, что A = P, то получу матрицу C со всеми нулевыми записями (таким образом, соблюдая неотрицательное условие)
Полагаю, это правильно, но кажется, чтослишком легко, так может кто-нибудь сказать мне, если есть какой-то другой, более сложный способ ответить на этот вопрос?