فهرست مندرجات
سوالات ۱۶ تا ۱۸
گراف ساده‌ی $n$ رأسی $G$ با رئوس $1, 2, ..., n$ را در نظر بگیرید. ماتریس مسیریاب گراف، یک ماتریس $n \times n$ است که درایه‌ی سطر $i$ام و ستون $j$ام آن، تعداد مسیرهای بین رأس $i$ و رأس $j$ است (مسیر دنباله‌ای از رئوس است که بین هر دو رأس متوالی یک یال وجود دارد و هر رأس حداکثر یک بار آمده است).
در صورتی که $i = j$ باشد، مقدار $1$ را در ماتریس قرار می‌دهیم.
سوال ۱۶
کدام یک از ماتریس‌های زیر، می‌تواند یک ماتریس مسیریاب باشد؟
- ماتریس ۲
- ماتریس ۳
- ماتریس ۵
- ماتریس ۱
- ماتریس ۴
پاسخ
گزینه (۵) درست است.
ماتریس مسیریاب یک درخت، ماتریسی با درایه‌های 1 است. اضافه کردن یک یال باعث می‌شود دوری بوجود آید که حداقل شامل سه راس است و تعداد مسیرهای بین آنها 2 خواهد شد. در نتیجه ماتریس 1 نمی‌تواند ماتریس مسیریاب یک گراف باشد. به همین استدلال ماتریس 3 نیز باید یک دور سه تایی با یک راس متصل به آنها باشد که در این حالت هم ماتریس گراف برابر ماتریس 3 نمی‌شود.
در صورتی که در یک مولفه‌ی گراف دو دور داشته باشیم دو راس خواهیم داشت که تعداد مسیرهای بین آنها حداقل 4 تا باشد در نتیجه ماتریس 2 و 5 هم قابل دست‌یابی نیست. با بررسی گراف‌های چهار راسی می‌توان مثالی برای ماتریس 4 یافت (گرافی با 5 یال).
سوال ۱۷
می‌خواهیم با پرسیدن تعدادی از خانه‌های ماتریس مسیریاب یک گراف، تعداد مؤلفه‌های گراف را تشخیص دهیم. در هر گام می‌توان یکی از خانه‌های ماتریس را پرسید. در حداقل چند گام به طور تضمینی به هدف می‌رسیم؟
- $n$
- $\binom{n-1}{2}+1$
- $n-2$
- $\binom{n}{2}$
- $n-1$
پاسخ
گزینه (۴) درست است.
واضح است که با $\binom{n}{2}$ تعداد یال می‌توان به هدف رسید (هر دو راسی که در یک مولفه باشند درایه‌ی متناظر با آنها بزرگتر از صفر است). ادعا می‌کنیم با کمتر از این تعداد نمی‌توان به هدف رسید.
فرض کنید $\binom{n}{2} - 1$ پرسش انجام داده‌ایم و پاسخ تمام آنها صفر باشد. در این صورت گرافی داریم که هیچ یالی ندارد مگر اینکه بین دو راسی که سوال نپرسیده‌ایم یال باشد (که هنوز درباره‌ی آن اطلاعی نداریم). پس در این حالت خاص بدون پرسش آخر نمی‌توان تعداد مولفه‌ها را تشخیص داد.
سوال ۱۸
با استفاده از ماتریس مسیریاب یک گراف، پاسخ چند تا از موارد زیر را همواره می‌توان فهمید؟ (رأس برشی، رأسی است که پس از حذف آن تعداد مؤلفه‌های همبندی گراف افزایش یابد.)
- آیا گراف رأس برشی دارد؟
- آیا رأس $v$ برشی است؟
- بین دو رأس $v$ و $u$ یال وجود دارد یا نه؟
- آیا گراف حداقل ۲ (نه لزوما مجزا) دور دارد؟
- ۱
- ۴
- ۳
- ۲
- ۰
پاسخ
گزینه (۴) درست است.
سوال اول: می‌توان فهمید. اگر راس برشی در گرافی باشد، آن راس و همسایگانش تنها یک مسیر به یکدیگر دارند. پس در این حالت حداقل سه راس هستند که درایه‌ی متناظرشان 1 است. از طرفی اگر چنین سه راسی وجود داشته باشند بدین معنی است که یکی از آنها بین دو راس دیگر است (در غیر این صورت تعداد مسیرهای بین این دو راس حداقل 2 بود). حال پس از حذف راس میانی دو راس دیگر در دو مولفه جدا قرار می‌گیرند.
سوال دوم و سوم: نمی‌توان فهمید. یک درخت را در نظر بگیرید. در این حالت متریس مسیریاب آن تماما 1 است. در یک درخت برگ‌ها برشی نیستند ولی بقیه‌ی رئوس برشی هستند. از طرفی در این درخت نمی‌توان فهمید که بین دو راس مشخص یال هست یا نه.
سوال چهارم: می‌توان فهمید. ابتدا مولفه‌ها را از روی ماتریس می‌یابیم. حال اگر در یک ماتریس مسیریاب هر مولفه تنها 1 وجود داشت دور ندارد، اگر تنها شامل 1 و 2 بود یک دور وجود دارد ولی اگر شامل اعداد 3 یا بیشتر بود حداقل دو دور وجود دارد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
