۰
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