Почему два пути не образуют один и тот же цикл в графе, несмотря на применение формулы сдвига CLRS? ⇐ Python

[Anonymous]

Ориентированный граф G = (V,E) на V = {1,2,3,4,5,6
Всем привет!
В настоящее время я работаю над книгой CLRS (Введение в алгоритмы), и у меня возникли проблемы с проверкой формулы, связанной с циклическими путями в графах. По книге два пути
⟨v0,v1​,v2​,…,v k-1​,v0​⟩ и ⟨v'0,v'1​,v' 2​,…,v'k-1​,v'0​⟩ образуют один и тот же цикл, если существует целое число j такое, что:
v'i​=v (i+j) mod k для i=0,1,…,k−1
b = [1, 2, 4, 1]
a = [4, 1, 2, 4]
k = len(a)

Перебрать возможные сдвиги (значения j)
for j in range(0, k):
match = True
print(f"Testing shift j = {j}:")
# Compare all elements after applying the shift
for i in range(0, k):
if b != a[(i + j) % k]:
print(f" Mismatch at index {i}: b[{i}] = {b} != a[{(i + j) % k}] = {a[(i + j) % k]}")
match = False
break # No need to check further if any mismatch occurs
else:
print(f" Match at index {i}: b[{i}] = {b} == a[{(i + j) % k}] = {a[(i + j) % k]}")
if match:
print(f"For j = {j}, the paths are the same.")
break # Exit after finding a valid j

if not match:
print("No valid shift found; the paths are different.")

Вывод:
Testing shift j = 0:
Mismatch at index 0: b[0] = 1 != a[0] = 4
Testing shift j = 1:
Match at index 0: b[0] = 1 == a[1] = 1
Match at index 1: b[1] = 2 == a[2] = 2
Match at index 2: b[2] = 4 == a[3] = 4
Mismatch at index 3: b[3] = 1 != a[0] = 4
Testing shift j = 2:
Mismatch at index 0: b[0] = 1 != a[2] = 2
Testing shift j = 3:
Mismatch at index 0: b[0] = 1 != a[3] = 4
No valid shift found; the paths are different.


Подробнее здесь: https://stackoverflow.com/questions/790 ... he-clrs-sh