قطر گراف برابر با حداکثر فاصله بین رئوس در گراف است.در گرافهای همبند از مرتبه ۱۰۰ و اندازه ۱۰۰ ،اختلاف کمترین و بیشترین مقدار ممکن برای قطر گراف ،با کدام گزینه برابر است؟
۱)۴۸
۲)۹۵
۳)۴۹
۴)۹۶
جواب:گزینه ۴
سلام
برای داشتن قطری با طول کمتر کافیه تا جایی که میتوانیم رئوس را به هم نزدیکتر کنیم مثلا یک راس مرکزی فرض کنیم و ۹۹ راس دیگر را دور ان قرار دهیم که هر کدام با یک یال به راس مرکزی وصل می شوندکه ۹۹ تا یال نیاز است و باید یک یال دیگر هم اضافه کنیم که اگر گراف را طبق معمول ساده فرض کنیم مجبوریم دو راس از ۹۹ راس اطراف راس مرکزی را انتخاب کنیم مثلا دو راس به نام های aو b در این حالت قطر گراف ۳ خواهد بود چرا که دو حالت داریم یا از یال ۱۰۰ یعنی (a,b ) استفاده نکنیم که طولانی ترین مسیر های مابه طول ۲ می شوند و اگر استفاده کنیم ۳ می شوند مثلا فاصله از a به یکی از راس های بجز b می شود ۳ مثلا مسیر ازa بهb و از b به مرکز و از مرکز به راس دیگر.
برای داشتن قطر حداکثر یک مسیر ساده با ۱۰۰ راس و ۹۹ تا یال را در نظر بگیرید که فاصله راس اول از اخر ۹۹ میشه یال ۱۰۰ هم می توانیم به دلخواه بین دوراس قرار دهیم که تاثیر ندارد چرا که باز دو حالت دارد یا انتخاب نمی شود یا می شود در حالت انتخاب نشدن طول طولانی ترین مسیر ها۹۹ می شود و در حالت انتخاب شدن اگر دو راس مجاور را به هم وصل کرده باشد که تاثیری ندارد و طول همچنان ۹۹ است و اگر دو راس غیر مجاور را وصل کند و استفاده هم بشه که طول مسیر را کم می کند پس:
[tex]99-3=96[/tex]
گزینه ی ۴
سلام.خیلی ممنون.
ببخشید من اینو متوجه نمیشم.منظور از قطر اینه که از بین همه کوتاه ترین مسیر ها بین هر ۲ راس دلخواه , بزرگ ترین را پیدا کنیم.در این صورت در این شکل قطر گراف میشه ۲.اگه از a به b بریم و از b به مرکز و سپس به c دیگه کوتاهترین مسیر از a به c نیست.
[attachment=22373]
(۲۶ بهمن ۱۳۹۶ ۰۵:۲۷ ب.ظ)ss311 نوشته شده توسط: سلام.خیلی ممنون.دوست گرامی شما قطر را درست تعریف می کنید این تعریف در کتاب کورمن برای قطر درخت بود ولی ایا این تنها تعریف قطر است ؟یا تعریف قطر گراف با قطر درخت یکی است؟ مثل تعریف سطح یا ارتفاع که در مراجع مختلف با هم اختلاف دارند (بیشتر مراجع قبل با فعلی)پس بهتره از تعریفی که در خوده سوال امده استفاده کنیم.در خود سوال قطر را برای ما تعریف کرده و براساس همین تعریف از ما جواب می خواهد اگه توجه کنیم قطر را حداکثر فاصله ی بین رئوس تعریف کرده نه حداکثر کوتاه ترین فاصله ی بین رئوس.
ببخشید من اینو متوجه نمیشم.منظور از قطر اینه که از بین همه کوتاه ترین مسیر ها بین هر ۲ راس دلخواه , بزرگ ترین را پیدا کنیم.در این صورت در این شکل قطر گراف میشه ۲.اگه از a به b بریم و از b به مرکز و سپس به c دیگه کوتاهترین مسیر از a به c نیست.
طبق تعریف خود سوال حداکثر فاصله یعنی حداکثر کوتاهترین مسیر.من فاصله بین دو راس رو کوتاهترین مسیر بین دو راس در نظر میگیرم.
(۲۶ بهمن ۱۳۹۶ ۰۸:۲۸ ب.ظ)ss311 نوشته شده توسط: طبق تعریف خود سوال حداکثر فاصله یعنی حداکثر کوتاهترین مسیر.من فاصله بین دو راس رو کوتاهترین مسیر بین دو راس در نظر میگیرم.
دوست گرامی به نظرم بین حداکثر فاصله و حداکثر کوتاه ترین مسیر اختلاف وجود دارد.به نظر شما کاملا احترام می گذارم و اصراری بر درستی جوابی که دادم ندارم و اصولا انچه به ذهنم می رسد را بیان می کنم تا کمکی هر چند ناچیز کرده باشم.موفق باشید
واقعا ممنون به خاطر پاسخ ها و وقتی که میگذارید.
سلام.عنوان سوال من این مواردی که شما نوشتید نیست.عنوان " سوال ۱۳ دکتری علوم کامپیوتر ۹۶ " چه ایرادی داره؟
(۰۶ اسفند ۱۳۹۶ ۰۶:۳۲ ب.ظ)ss311 نوشته شده توسط: سلام.عنوان سوال من این مواردی که شما نوشتید نیست.عنوان " سوال ۱۳ دکتری علوم کامپیوتر ۹۶ " چه ایرادی داره؟اون موارد صرفا مثال بود. مهم این هست که "عنوان سوال باید گویای مبحث سوال باشد". سوال ۱۳ دکتری علوم کامپیوتر، صرفا نشون میده این سوال در کنکور دکترای علوم کامپیوتر اومده، نه بیشتر.
عنوانی مثل "کمترین و بیشترین مقدار قطر گراف" مشخص و قابل قبول است.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۰۸ اسفند ۱۳۹۶ ۰۷:۴۸ ق.ظ)Behnam نوشته شده توسط:این جوری سرچ راحتتره.مثلا وقتی سوالات سال ۹۶ رو میخونیم با یه سرچ هر سوالی برای این سال هست میاد و نیازی نیست که دوباره سرچ کنیم.(06 اسفند ۱۳۹۶ ۰۶:۳۲ ب.ظ)ss311 نوشته شده توسط: سلام.عنوان سوال من این مواردی که شما نوشتید نیست.عنوان " سوال ۱۳ دکتری علوم کامپیوتر ۹۶ " چه ایرادی داره؟اون موارد صرفا مثال بود. مهم این هست که "عنوان سوال باید گویای مبحث سوال باشد". سوال ۱۳ دکتری علوم کامپیوتر، صرفا نشون میده این سوال در کنکور دکترای علوم کامپیوتر اومده، نه بیشتر.
عنوانی مثل "کمترین و بیشترین مقدار قطر گراف" مشخص و قابل قبول است.