۰
subtitle
ارسال: #۱
  
قطر گراف
در کتاب مقسمی نوشته قطر گراف ماکزیمم یال موجو در گراف هست و طبق شکل موجود در پیوست
اینها رو بدست اورده و گفته قطر گراف ۴ هست.
[tex]e(v1)=4 , e(v2)=3 , e(v3)=2 , e(v4)=3 , e(v5)=3 , e(v6)=4 , e(v7)=4[/tex]
اما به نظر من اگر از راس ۱ به خواهیم به ۷ برسیم میتونیم اول به ۲ بعد ۳ بعد ۴ بعد ۶ بعد ۵ بعد ۷رفت که میشه ۶ یال عبوری!!
اینها رو بدست اورده و گفته قطر گراف ۴ هست.
[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 بنداز ببین آقان کورمن و دوستان چی گفتن و اونا با ما موافققن یا با مقسمی !!
اما اگه قطر رو اینطوری معرفی کنیم : "کوتاه ترین مسیر ساده (بدون سیکل مسلما) از هر گره به گره دیگر رو حساب کن ، سپس از این مجموعه ماکزیمم بگیر ،اگه اینکارو انجام بدی جواب مقسمی درست خواهد بود، مثلا مقسمی گفته برای v3 برابره ۲ هست، طبق تعریف اولیه جواب ۳ میشه چون مسیر ۳ یالی وجود دارد که مربوط به فاصله V7 تا V1 میشه، اما طبق تعریف که ما الان ما درستش کردیم (بزن به نام بنده !!) درست درمیاد، پس از مینیمم مسیرها ماکزیمم بگیر.
به نظر میاد همین تعریف ما درسته چون هدف از الگوریتم های متععد پیدا کردن مینیمم یال هست و اگه بخواهیم حداکثز زمان اجرا رو تو بدترین حالت حساب کنیم باید از مینیمم ها ماکزیمم بگیریم. حتما یه نیگاه به کتاب clrs بنداز ببین آقان کورمن و دوستان چی گفتن و اونا با ما موافققن یا با مقسمی !!
۰
ارسال: #۳
  
RE: قطر گراف
در کتاب مقسمی دقیقا به این صورت نوشته!
[tex]max(e(v))[/tex]
حالا پی دی اف CLRS نگاهی بندازم ببینم چی گفته در موردش
[tex]max(e(v))[/tex]
حالا پی دی اف CLRS نگاهی بندازم ببینم چی گفته در موردش
۰
ارسال: #۴
  
قطر گراف
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
رنگ کردن رئوس گراف( ارشد علوم کامپیوتر ۹۸ ) | ss311 | ۰ | ۱,۹۴۰ |
۰۳ اسفند ۱۳۹۸ ۱۲:۴۳ ب.ظ آخرین ارسال: ss311 |
|
تعداد مسیرها در گراف | ss311 | ۰ | ۱,۸۴۸ |
۰۸ بهمن ۱۳۹۸ ۱۲:۴۷ ب.ظ آخرین ارسال: ss311 |
|
مرتبه زمانی یافتن قطر | Sepideh96 | ۲ | ۳,۵۱۳ |
۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ آخرین ارسال: erfan30 |
|
طراحی گرافیکی | simaakbari | ۰ | ۲,۳۰۱ |
۱۶ خرداد ۱۳۹۸ ۰۴:۵۴ ب.ظ آخرین ارسال: simaakbari |
|
کوتاه ترین مسیر در گراف | Sanazzz | ۳ | ۳,۷۴۵ |
۰۷ فروردین ۱۳۹۸ ۰۲:۵۷ ق.ظ آخرین ارسال: Sanazzz |
|
کتاب خوب در باره نظریه گراف | ماهی ۲۵۸ | ۰ | ۱,۸۱۲ |
۲۸ شهریور ۱۳۹۷ ۱۲:۲۸ ب.ظ آخرین ارسال: ماهی ۲۵۸ |
|
یافتن مسیر در گراف کامل دو بخشی | Sepideh96 | ۳ | ۳,۷۷۳ |
۲۶ بهمن ۱۳۹۶ ۱۲:۴۲ ب.ظ آخرین ارسال: αɾια |
|
رنگ آمیزی راسهای گراف | ss311 | ۲ | ۲,۱۳۶ |
۰۳ بهمن ۱۳۹۶ ۰۱:۲۳ ق.ظ آخرین ارسال: ss311 |
|
سوال در مورد ساختن یک گراف دانش محدود | zahra89 | ۰ | ۱,۵۷۵ |
۰۲ بهمن ۱۳۹۶ ۰۳:۴۱ ب.ظ آخرین ارسال: zahra89 |
|
درخواست حل سوال گراف از مهندسی کامپیوتر ۹۳ | Sepideh96 | ۴ | ۲,۸۲۶ |
۱۴ آذر ۱۳۹۶ ۰۲:۲۹ ق.ظ آخرین ارسال: Sepideh96 |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close