در کتاب مقسمی نوشته قطر گراف ماکزیمم یال موجو در گراف هست و طبق شکل موجود در پیوست
اینها رو بدست اورده و گفته قطر گراف ۴ هست.
[tex]e(v1)=4 , e(v2)=3 , e(v3)=2 , e(v4)=3 , e(v5)=3 , e(v6)=4 , e(v7)=4[/tex]
اما به نظر من اگر از راس ۱ به خواهیم به ۷ برسیم میتونیم اول به ۲ بعد ۳ بعد ۴ بعد ۶ بعد ۵ بعد ۷رفت که میشه ۶ یال عبوری!!
قطر گراف برابر حداکثر تعداد یالهای از یک گره به گره دیگر است ، پس حرف شما درسته ، برای رفتن از v1 به v7 باید از ۶ تا یال عبور کرد، برای رفتن از v1 به v5 هم باید از ۵ تا یال عبور کرد. پس اگر طبق تعریف جواب مقسمی غلطه.
اما اگه قطر رو اینطوری معرفی کنیم : "کوتاه ترین مسیر ساده (بدون سیکل مسلما) از هر گره به گره دیگر رو حساب کن ، سپس از این مجموعه ماکزیمم بگیر ،اگه اینکارو انجام بدی جواب مقسمی درست خواهد بود، مثلا مقسمی گفته برای v3 برابره ۲ هست، طبق تعریف اولیه جواب ۳ میشه چون مسیر ۳ یالی وجود دارد که مربوط به فاصله V7 تا V1 میشه، اما طبق تعریف که ما الان ما درستش کردیم (بزن به نام بنده !!) درست درمیاد، پس از مینیمم مسیرها ماکزیمم بگیر.
به نظر میاد همین تعریف ما درسته چون هدف از الگوریتم های متععد پیدا کردن مینیمم یال هست و اگه بخواهیم حداکثز زمان اجرا رو تو بدترین حالت حساب کنیم باید از مینیمم ها ماکزیمم بگیریم. حتما یه نیگاه به کتاب clrs بنداز ببین آقان کورمن و دوستان چی گفتن و اونا با ما موافققن یا با مقسمی !!
در کتاب مقسمی دقیقا به این صورت نوشته!
[tex]max(e(v))[/tex]
حالا پی دی اف CLRS نگاهی بندازم ببینم چی گفته در موردش
(۲۷ مهر ۱۳۹۱ ۰۵:۰۵ ب.ظ)esi نوشته شده توسط: قطر گراف برابر حداکثر تعداد یالهای از یک گره به گره دیگر است
فکر کنم همین مد نظر باشه... این قطر گراف در الگوریتم Depth Limited Search هوش مصنوعی هم به همین شکل کاربرد داره.