گره های گراف های جهت دار زیر را طوری شماره گذاری کنید که برای هر یالِ $(x,y)$ داشته باشیم $5x+y$ ضریبی از ۷ است. برای چند شکل این کار ممکن است؟

Question

می‌خواهيم برای اشکالی مانند شکل زير، روی هريک از رئوس شکل، اعدادی بين $1,2,...,6$ بنويسيم طوریکه برای هر پيکان که از رأس با عدد $x$ خارج و به رأس با عدد $y$ وارد شده باشد، $5x+y$ مضرب ۷ باشد. در چند شکل از اشکال زیر می‌توان این کار را انجام داد؟

Answer 1

به نام خدا.

توجه کنید که شماره گذاری رأس ها به یکی از دو حالت زیر است:

$1 \rightarrow 2 \rightarrow 4 \rightarrow 1$

$3 \rightarrow 6 \rightarrow 5 \rightarrow 3$

پس به جای این حالات، حالت زیر را در نظر می گیریم:

$a \rightarrow b \rightarrow c \rightarrow a$

شکل اول را بررسی می کنیم.

این حالت نامطلوب است. زیرا دو رأس با شماره یکسان به هم وصل شده اند.

شکل دوم‌:

این حالت مطلوب است. مثلاً به جای a عدد یک را بگذارید.

شکل سوم:

توجه کنید چون به رأس b دو یال وارد شده است، باید آن دو رأس با شماره یکسان باشند. پس این حالت نامطلوب است.

شکل چهارم:

این حالت هم نامطلوب است. زیرا از b به a یال وجود دارد.

شکل پنجم:

این شکل مطلوب است.

پس در کل دو شکل مطلوب است.