گراف $Q_k$ دارای $2^k$ راس است که هر کدام یک دنباله‌ی $k$ تایی منحصر به فرد از ۱ و ۰ دارند. و دو راس که دنباله‌های آن‌ها دقیقا در یک مولفه با هم تفاوت دراند، به هم یال دارند.

فرض کنید هر راس $x$ یک بسته‌ی پستی دارد و می‌خواهد آن را به راس $P(x)$ برساند که $P$ یک جایگشت روی رئوس $Q_k$ می‌باشد. مسیری که هر بسته روی یال‌ها طی می‌کند تا به مقصد برسد این طور به‌دست می‌آید:

اگر بسته‌ای در حال حاضر در راس $a=(a_1,...,a_k)$ باشد و هدف آن راس $b=(b_1,...,b_k)$ باشد، ( و $a<>b$ ) کوچک‌ترین $i$ را پیدا می‌کند که $a_i<>b_i$ و طی حرکت بعدی، به راس همسایه‌ی $a$ یعنی $(a_1,...,a_{i-1},b_i,a_{i+1},...,a_k)$ می‌رود. پس هر بسته با این الگوریتم راه خود را تا مقصد پیدا می‌کند.

حرکت بسته‌ها روی یال‌ها دارای پالس زمانی هماهنگ کننده می‌باشد. در هر پالس بعضی بسته‌ها روی بعضی یال‌ها حرکت می‌کنند. در ضمن هر یال در هر واحد زمانی فقط می‌تواند راه عبور یک بسته را فراهم کند اما در یک لحظه، چند بسته می‌توانند در یک راس باشند. بنابراین احتمالا، بعضی از بسته‌ها مجبورند چند پالس زمانی در یک راس منتظر بمانند و بعد به حرکت خود ادامه دهند. نشان دهید جایگشت $P$ وجود دارد که به ازای آن هر طور بسته‌ها با رعایت شروط گفته شده حرکت کنند، حداقل $\Omega (\frac{2^{\frac{k}{2}}}{k})$ واحد زمانی طول می‌کشد تا همه‌ی بسته‌ها به مقصد برسند.

• سوال بعد
• سوال قبل