۰
subtitle
ارسال: #۱
  
مولفه های همبند گراف
سلام
مولفه های همبند گراف رو چجوری میشه پیدا کرد؟؟...مثلا هر راس به تنهایی می تونه ی مولفه باشه؟؟تعریفی ک دیدم این بود ک هر زیر گراف از گراف اصلی ک همبند باشه رو میگن مولفه همبند؟؟
بعد هم با پیمایش dfs و هم BFS میشه تعدادشونو پیدا کرد؟؟..کسی میتونه رو این گراف برا من مولفه های همبندو بگه؟؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
مولفه های همبند گراف رو چجوری میشه پیدا کرد؟؟...مثلا هر راس به تنهایی می تونه ی مولفه باشه؟؟تعریفی ک دیدم این بود ک هر زیر گراف از گراف اصلی ک همبند باشه رو میگن مولفه همبند؟؟
بعد هم با پیمایش dfs و هم BFS میشه تعدادشونو پیدا کرد؟؟..کسی میتونه رو این گراف برا من مولفه های همبندو بگه؟؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
۲
ارسال: #۲
  
RE: مولفه های همبند گراف
دوست عزیز این که یک گراف بدون جهت و در گراف بدون جهت وقتی با پیمایش از هر راس دلخواه بتوان به تمام رئوس دسترسی داشته باشیم میشه همبند و این گراف چون بدون جهت است مولفه های همبندی میشه تمام رئوس چون از هر راس شروع کنید به تمام رئوس میرسید
در گراف جهت دار مولفه های همبندی این طوری که مثلا بین دو راس ۱ و ۲
اگر از ۱ به ۲ مسیری باشه و از ۲ به ۱ هم مسیری باشه این دو راس مولفه همبند قوی هستن و در یک مجموعه قرار میگیرن حالا از راس ۲ به راس ۳ مسیر هست ولی از ۳ به ۲ خیر پس این توی مجموعه قرار نمیگیره و جدا هست
{۱,۲} , {۳}
میشه مولفه های همبند قوی این گراف
در گراف جهت دار مولفه های همبندی این طوری که مثلا بین دو راس ۱ و ۲
اگر از ۱ به ۲ مسیری باشه و از ۲ به ۱ هم مسیری باشه این دو راس مولفه همبند قوی هستن و در یک مجموعه قرار میگیرن حالا از راس ۲ به راس ۳ مسیر هست ولی از ۳ به ۲ خیر پس این توی مجموعه قرار نمیگیره و جدا هست
{۱,۲} , {۳}
میشه مولفه های همبند قوی این گراف
۱
ارسال: #۳
  
RE: مولفه های همبند گراف
دوست عزیز ببیند هدف پیدا کردن بزرگترین ها هست یعنی هر مجموعه بزرگترین باشه و تعداد مجموعه ها کمتر باشه
روش کتابیش بخواهیم بگیم واسه گراف های پیچیده
اول برای هر راس d و f به دست میاریم
d راس u زمانی است که در پیمایش عمقی راس u برای اولین بار ملاقات شده است
f راس u زمانی است که در پیمایش عمقی از راس u به هیچ راس دیگری نشه بریم و در واقعا همه ی همسایه هاش ملاقات شده باشن و برمیگردیم به راس قبلیش
بعد از به دست اوردن این ها حالا درخت جهت یالهاشو برعکس می کنیم تمامشو و حالا درختی که از معکوس شدن یال ها به دست اومده را به ترتیب نزولی f ها پیمایش عمقی کنیم (یعنی اولویت با اونیه که f کمتری داره نه دیگه برحسب شماره راس یا ترتیب حروف الفبا) مولفه های همبندی به دست میاد و مثلا میشه چندتا مجموعه که همه ی این مجموعه ها اجتماعشون میشه کل راس های گراف
دقت کنید اول باید خوب مفهوم مولفه های همبندی متوجه شید یعنی چند تا راس وقتی توی یک مجموعه همبندی هستن که از هر راس به راس های دیگه مسیر باشه یعنی اگر مجموعه همبندی ۳ تا راس داره به اسم های ۱ و ۲و ۳ باید از ۱ به ۲ مسیر باشه و از ۲ به ۱ هم مسیر باشه از ۱ به ۳ مسیر باشه از ۳ به ۱ هم مسیر باشه از ۲به ۳ مسیر باشه و از ۳ به ۲ هم مسیر باشه دقت کنید مسیر
ولی اگر مفهموم مولفه همبندی متوجه شید می تونید اگر گراف ساده باشه بدون این الگوریتم خودتون مولفه ها را به دست بیارید یا با رد گزینه بهش برسید
اگر خوب متوجه نمیشید فکر کنم کتاب طراحی الگوریتم پوران تو فصل گراف ها را بخونید متوجه شید موفق باشید.
روش کتابیش بخواهیم بگیم واسه گراف های پیچیده
اول برای هر راس d و f به دست میاریم
d راس u زمانی است که در پیمایش عمقی راس u برای اولین بار ملاقات شده است
f راس u زمانی است که در پیمایش عمقی از راس u به هیچ راس دیگری نشه بریم و در واقعا همه ی همسایه هاش ملاقات شده باشن و برمیگردیم به راس قبلیش
بعد از به دست اوردن این ها حالا درخت جهت یالهاشو برعکس می کنیم تمامشو و حالا درختی که از معکوس شدن یال ها به دست اومده را به ترتیب نزولی f ها پیمایش عمقی کنیم (یعنی اولویت با اونیه که f کمتری داره نه دیگه برحسب شماره راس یا ترتیب حروف الفبا) مولفه های همبندی به دست میاد و مثلا میشه چندتا مجموعه که همه ی این مجموعه ها اجتماعشون میشه کل راس های گراف
دقت کنید اول باید خوب مفهوم مولفه های همبندی متوجه شید یعنی چند تا راس وقتی توی یک مجموعه همبندی هستن که از هر راس به راس های دیگه مسیر باشه یعنی اگر مجموعه همبندی ۳ تا راس داره به اسم های ۱ و ۲و ۳ باید از ۱ به ۲ مسیر باشه و از ۲ به ۱ هم مسیر باشه از ۱ به ۳ مسیر باشه از ۳ به ۱ هم مسیر باشه از ۲به ۳ مسیر باشه و از ۳ به ۲ هم مسیر باشه دقت کنید مسیر
ولی اگر مفهموم مولفه همبندی متوجه شید می تونید اگر گراف ساده باشه بدون این الگوریتم خودتون مولفه ها را به دست بیارید یا با رد گزینه بهش برسید
اگر خوب متوجه نمیشید فکر کنم کتاب طراحی الگوریتم پوران تو فصل گراف ها را بخونید متوجه شید موفق باشید.
۰
ارسال: #۴
  
RE: مولفه های همبند گراف
هرکدام ازاین راسها به تنهایی میتونن مولفه همبند باشن؟
این شکل شما یعنی دو مولفه هم بند داره درسته؟؟؟بعد چجوری با dfs میتونیم لهش برسیم؟
این شکل شما یعنی دو مولفه هم بند داره درسته؟؟؟بعد چجوری با dfs میتونیم لهش برسیم؟
ارسال: #۵
  
RE: مولفه های همبند گراف
(۲۲ آذر ۱۳۹۳ ۰۸:۳۷ ب.ظ)shamim_70 نوشته شده توسط: هرکدام ازاین راسها به تنهایی میتونن مولفه همبند باشن؟
این شکل شما یعنی دو مولفه هم بند داره درسته؟؟؟بعد چجوری با dfs میتونیم لهش برسیم؟
برای پیمایش گراف بدون جهت فرق نمیکنه از کجا شروع کنی ،اگر از هر جایی شروع کردی همه گره هارو بهت میده(در صورت همبندی)
در گراف جهت دارد هم اگه همبند قوی باشه همینشرایطه،ولی درغیر اینصورت ممکنه چندتا گره پیمایش نشن!
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
رنگ کردن رئوس گراف( ارشد علوم کامپیوتر ۹۸ ) | ss311 | ۰ | ۲,۱۰۶ |
۰۳ اسفند ۱۳۹۸ ۱۲:۴۳ ب.ظ آخرین ارسال: ss311 |
|
تعداد مسیرها در گراف | ss311 | ۰ | ۲,۰۱۵ |
۰۸ بهمن ۱۳۹۸ ۱۲:۴۷ ب.ظ آخرین ارسال: ss311 |
|
طراحی گرافیکی | simaakbari | ۰ | ۲,۴۵۳ |
۱۶ خرداد ۱۳۹۸ ۰۴:۵۴ ب.ظ آخرین ارسال: simaakbari |
|
کوتاه ترین مسیر در گراف | Sanazzz | ۳ | ۴,۱۱۸ |
۰۷ فروردین ۱۳۹۸ ۰۲:۵۷ ق.ظ آخرین ارسال: Sanazzz |
|
مولفه DC کمک کنین خواهشا | Sanazzz | ۴ | ۴,۰۷۸ |
۱۳ آذر ۱۳۹۷ ۰۱:۱۱ ب.ظ آخرین ارسال: Sanazzz |
|
کتاب خوب در باره نظریه گراف | ماهی ۲۵۸ | ۰ | ۱,۹۶۶ |
۲۸ شهریور ۱۳۹۷ ۱۲:۲۸ ب.ظ آخرین ارسال: ماهی ۲۵۸ |
|
یافتن مسیر در گراف کامل دو بخشی | Sepideh96 | ۳ | ۴,۱۲۲ |
۲۶ بهمن ۱۳۹۶ ۱۲:۴۲ ب.ظ آخرین ارسال: αɾια |
|
رنگ آمیزی راسهای گراف | ss311 | ۲ | ۲,۳۷۳ |
۰۳ بهمن ۱۳۹۶ ۰۱:۲۳ ق.ظ آخرین ارسال: ss311 |
|
سوال در مورد ساختن یک گراف دانش محدود | zahra89 | ۰ | ۱,۶۹۳ |
۰۲ بهمن ۱۳۹۶ ۰۳:۴۱ ب.ظ آخرین ارسال: zahra89 |
|
درخواست حل سوال گراف از مهندسی کامپیوتر ۹۳ | Sepideh96 | ۴ | ۳,۱۸۷ |
۱۴ آذر ۱۳۹۶ ۰۲:۲۹ ق.ظ آخرین ارسال: Sepideh96 |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close