کافیه یک گراف با ۶ راس، متناظر اعداد ۱ تا ۶ که روی هر نیمه هر دومینو ظاهر میشن، بسازین و به ازای هر دومینو یک یال بدون جهت بین راسهای متناظر دو نیمه اش بگذارید. مثلا اگر یک دومینو $(5,3)$ باشه یک یال بدون جهت بین راس ۵ و راس ۳ میگذاریم، و اگر $(5,5)$ باشه یک یال از راس ۵ به راس ۵ (یک حلقه). به این صورت گرافی به وجود میاد که بین بعضی زوج راسهاش، یا از راس به خودش، یک یا چند یال وجود داشته باشه.

حالا یک ترتیب درست چیدن دومینو ها متناظر با یک تور در این گراف هست، چرا که هر دومینو متناظر با یک یال هست، و در هر تور دو یال مجاور راس مشترکی دارند، که این راس مشترک متناظر عددی هست که در دو نیمه کنار هم قرار گرفته از دو دومینوی پشت سرهم تکرار شده. به همین ترتیب یک ترتیب درست از چیدن دومینو ها که شامل همه دومینوها بشه معادل یافتن یک تور در این گراف هست که همه یالها رو شامل بشه، یعنی یک تور اویلری!

پس میتونیم از همه الگوریتمهای مختلفی که برای پیدا کردن تور اویلری در گراف ارایه شدن استفاده کنیم که بر حسب تعداد راسها و یالها زمان اجراشون خطی هست، لذا حتی برای چند صد میلیون دومینو هم در کسری از ثانیه کار میکنند.

بیشتر بخوانیم

گرافی که به این ترتیب ساخته شد مشابه یک دسته از گرافها به نام «دو براین» De Bruijn است. میتونید در مورد این گرافها در کتابهای مقدماتی بر نظریه گراف، نوشته داگلاس وست، که توی ایران هم ترجمش منتشر شده، یا کتاب مشابهی نوشته باندی و مورتی بیشتر بخوانید، و یا این صفحه ویکی پدیا رو مطالعه کنید.