قطر گراف برابر است با شعاع گراف

[Goharshady]

یک سوال نسبتا سخت:
همه گرافهایی را بیابید که قطر و شعاع آنها برابر باشد.
البته امیدوارم معنی قطر و شعاع گراف را بدانیددر غیر این صورت به این لینک مراجعه کنید:
http://en.wikipedia.org/wiki/Graph_theory
اگر نمی توانید این مسئله را حل کنید به این یکی فکر کنید:
همه گرافهایی را بیابیدکه قطر آنها دو برابر شعاعشان باشد
-----
ممنون می شم اگه نظرتون راجع به نحوه حل رو هم بنویسین چون همین کمک بزرگیه
جالبه که تو ویکی پدیا ، یه نفر این گرافها رو به اسم من ثبت کرده:
http://fa.wikipedia.org/wiki/فاصله_در_گراف

 

[bihamta]

امیر جان اینجا در مورد شعاع و قطر چیزی نگفته.
منظورت چیه؟

 

[Goharshady]

اگه External links اونو باز می کردی حتما پیداش می کردی ولی اینم از تعریف قطر و شعاع که کار آسانی هم نیست:
به این شکل دقت کنید:

مطمئنا معنی راس و یال گراف را می دانید
فاصله دو راس : کمینه تعداد یالهایی که باید طی شود تا از راس i به راس j برویم را فاصله i و j گویند و با D(i,j)
نشان می دهند

برای مثال فاصله i و j در گراف فوق 2 است.
خروج از مرکز راس i : به فاصله i از دورترین راس نسبت به i خروج از مرکز i گویند
برای مثال خروج از مرکز i در این گراف برابر 2 است. خروج از مرکز i را با ecc(i) نمایش می دهند
قطر گراف : به بزرگترین خروج از مرکز راس های گراف قطر گراف گویند برای مثال قطر این گراف 2 است
شعاع گراف : به کوچکترین خروج از مرکز رئوس گراف شعاع گراف گویند شعاع این گراف 2 است
پس قطر و شعاع این گراف با هم برابرند
و این یکی از همان گرافهایی است که من به دنبالش بودم

 

[Goharshady]

مسئله ساده تر برای شروع

قبل از حل این مسئله می توانید روی مسئله ساده تری فکر کنید که لینکش را می گذارم:
رابطه بین قطر و شعاع گراف