سلام دوستان
من میخوام بدونم که مولفه های همبندی یا مولفه های همبندی گراف قویا همبند رو چیجوری میشه بدست اورد؟؟ اگه کسی می تونه با یه مثال توضیح بده ممنون میشم
(۰۳ بهمن ۱۳۹۲ ۱۱:۳۷ ب.ظ)Mindhunter نوشته شده توسط: سلام دوستان
من میخوام بدونم که مولفه های همبندی یا مولفه های همبندی گراف قویا همبند رو چیجوری میشه بدست اورد؟؟ اگه کسی می تونه با یه مثال توضیح بده ممنون میشم
راس هایی مثل x,y که هم از x به y و هم از y به x قابل دستیابی هست تو یه مجموعه قرار میگیرند
(۰۳ بهمن ۱۳۹۲ ۱۱:۵۲ ب.ظ)bermoda14 نوشته شده توسط:جناب با یک شکل توضیح بدین ممنون میشم(03 بهمن ۱۳۹۲ ۱۱:۳۷ ب.ظ)Mindhunter نوشته شده توسط: سلام دوستان
من میخوام بدونم که مولفه های همبندی یا مولفه های همبندی گراف قویا همبند رو چیجوری میشه بدست اورد؟؟ اگه کسی می تونه با یه مثال توضیح بده ممنون میشم
راس هایی مثل x,y که هم از x به y و هم از y به x قابل دستیابی هست تو یه مجموعه قرار میگیرند
منظورتون با الگوریتمه؟ یا همینجوری روی گراف میخواید بدونید؟
(۰۴ بهمن ۱۳۹۲ ۱۲:۱۷ ق.ظ)El@he نوشته شده توسط: منظورتون با الگوریتمه؟ یا همینجوری روی گراف میخواید بدونید؟
نه همینجوری با شکل روی گراف
(۰۴ بهمن ۱۳۹۲ ۱۲:۲۸ ق.ظ)Mindhunter نوشته شده توسط:(04 بهمن ۱۳۹۲ ۱۲:۱۷ ق.ظ)El@he نوشته شده توسط: منظورتون با الگوریتمه؟ یا همینجوری روی گراف میخواید بدونید؟
نه همینجوری با شکل روی گراف
خب مثلا اینجا از ۱ به ۲ میشه رفت، از ۲ هم به ۱ میشه رفت. پس {۱و۲}
از ۲ به ۳ میشه رفت، ولی از ۳ به ۲ نمیشه! پس دیگه ۳ تو مجموعه ی بالا قرار نمیگیره.
پس درواقع گره هایی توی یه مجموعه ی قویا همبند قرار میگیرن که از هر کدوم راهی به بقیه باشه.
اگه ۳ توی مجموعه ی بالا قرار بگیره راهی به ۱ یا ۲ نداره.
یه جورایی مولفه های قویا همبند توی گراف های جهت دار، معادلن با مولفه های همبند توی گراف بدون جهت!
حالا سوالتون نمیدونم دقیقا چیه :ی میخواید یه کم بیشتر توضیح بدید.
عکس خیلی حرفه ای شد ببخشید :ی
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
(۰۴ بهمن ۱۳۹۲ ۱۲:۴۹ ق.ظ)El@he نوشته شده توسط:(04 بهمن ۱۳۹۲ ۱۲:۲۸ ق.ظ)Mindhunter نوشته شده توسط:(04 بهمن ۱۳۹۲ ۱۲:۱۷ ق.ظ)El@he نوشته شده توسط: منظورتون با الگوریتمه؟ یا همینجوری روی گراف میخواید بدونید؟
نه همینجوری با شکل روی گراف
خب مثلا اینجا از ۱ به ۲ میشه رفت، از ۲ هم به ۱ میشه رفت. پس {۱و۲}
از ۲ به ۳ میشه رفت، ولی از ۳ به ۲ نمیشه! پس دیگه ۳ تو مجموعه ی بالا قرار نمیگیره.
پس درواقع گره هایی توی یه مجموعه ی قویا همبند قرار میگیرن که از هر کدوم راهی به بقیه باشه.
اگه ۳ توی مجموعه ی بالا قرار بگیره راهی به ۱ یا ۲ نداره.
یه جورایی مولفه های قویا همبند توی گراف های جهت دار، معادلن با مولفه های همبند توی گراف بدون جهت!
حالا سوالتون نمیدونم دقیقا چیه :ی میخواید یه کم بیشتر توضیح بدید.
عکس خیلی حرفه ای شد ببخشید :ی
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
الان مجموعه مولفه های همبند قوی این گراف رو چیجوری بدست میاریم؟؟؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
ببخشید اگه بد شد
(۰۴ بهمن ۱۳۹۲ ۰۱:۲۴ ق.ظ)Mindhunter نوشته شده توسط:(04 بهمن ۱۳۹۲ ۱۲:۴۹ ق.ظ)El@he نوشته شده توسط:(04 بهمن ۱۳۹۲ ۱۲:۲۸ ق.ظ)Mindhunter نوشته شده توسط:(04 بهمن ۱۳۹۲ ۱۲:۱۷ ق.ظ)El@he نوشته شده توسط: منظورتون با الگوریتمه؟ یا همینجوری روی گراف میخواید بدونید؟
نه همینجوری با شکل روی گراف
خب مثلا اینجا از ۱ به ۲ میشه رفت، از ۲ هم به ۱ میشه رفت. پس {۱و۲}
از ۲ به ۳ میشه رفت، ولی از ۳ به ۲ نمیشه! پس دیگه ۳ تو مجموعه ی بالا قرار نمیگیره.
پس درواقع گره هایی توی یه مجموعه ی قویا همبند قرار میگیرن که از هر کدوم راهی به بقیه باشه.
اگه ۳ توی مجموعه ی بالا قرار بگیره راهی به ۱ یا ۲ نداره.
یه جورایی مولفه های قویا همبند توی گراف های جهت دار، معادلن با مولفه های همبند توی گراف بدون جهت!
حالا سوالتون نمیدونم دقیقا چیه :ی میخواید یه کم بیشتر توضیح بدید.
عکس خیلی حرفه ای شد ببخشید :ی
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
الان مجموعه مولفه های همبند قوی این گراف رو چیجوری بدست میاریم؟؟؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
ببخشید اگه بد شد
شما اول یه dfs روی گراف میزنی و زمان های f رو بدست میاری، بعدش یال ها رو برعکس میکنی و توی گراف جدیدت از راسی که بیشترین f رو داره دوباره dfs میزنی و تا اونجایی که میشه راس ملاقات میکنی و این میشه یه SCC حالا به همین ترتیب واسه سایر راس های دیده نشده عمل میکنیم. البته دقیقش یادم نیست
(۰۴ بهمن ۱۳۹۲ ۰۱:۲۷ ب.ظ)Riemann نوشته شده توسط:(04 بهمن ۱۳۹۲ ۰۱:۲۴ ق.ظ)Mindhunter نوشته شده توسط:(04 بهمن ۱۳۹۲ ۱۲:۴۹ ق.ظ)El@he نوشته شده توسط:(04 بهمن ۱۳۹۲ ۱۲:۲۸ ق.ظ)Mindhunter نوشته شده توسط:(04 بهمن ۱۳۹۲ ۱۲:۱۷ ق.ظ)El@he نوشته شده توسط: منظورتون با الگوریتمه؟ یا همینجوری روی گراف میخواید بدونید؟
نه همینجوری با شکل روی گراف
خب مثلا اینجا از ۱ به ۲ میشه رفت، از ۲ هم به ۱ میشه رفت. پس {۱و۲}
از ۲ به ۳ میشه رفت، ولی از ۳ به ۲ نمیشه! پس دیگه ۳ تو مجموعه ی بالا قرار نمیگیره.
پس درواقع گره هایی توی یه مجموعه ی قویا همبند قرار میگیرن که از هر کدوم راهی به بقیه باشه.
اگه ۳ توی مجموعه ی بالا قرار بگیره راهی به ۱ یا ۲ نداره.
یه جورایی مولفه های قویا همبند توی گراف های جهت دار، معادلن با مولفه های همبند توی گراف بدون جهت!
حالا سوالتون نمیدونم دقیقا چیه :ی میخواید یه کم بیشتر توضیح بدید.
عکس خیلی حرفه ای شد ببخشید :ی
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
الان مجموعه مولفه های همبند قوی این گراف رو چیجوری بدست میاریم؟؟؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
ببخشید اگه بد شد
شما اول یه dfs روی گراف میزنی و زمان های f رو بدست میاری، بعدش یال ها رو برعکس میکنی و توی گراف جدیدت از راسی که بیشترین f رو داره دوباره dfs میزنی و تا اونجایی که میشه راس ملاقات میکنی و این میشه یه SCC حالا به همین ترتیب واسه سایر راس های دیده نشده عمل میکنیم. البته دقیقش یادم نیست
داداشی اصلا نفهمیدم
(۰۴ بهمن ۱۳۹۲ ۰۱:۳۶ ب.ظ)Mindhunter نوشته شده توسط:(04 بهمن ۱۳۹۲ ۰۱:۲۷ ب.ظ)Riemann نوشته شده توسط:(04 بهمن ۱۳۹۲ ۰۱:۲۴ ق.ظ)Mindhunter نوشته شده توسط:(04 بهمن ۱۳۹۲ ۱۲:۴۹ ق.ظ)El@he نوشته شده توسط:(04 بهمن ۱۳۹۲ ۱۲:۲۸ ق.ظ)Mindhunter نوشته شده توسط: نه همینجوری با شکل روی گراف
خب مثلا اینجا از ۱ به ۲ میشه رفت، از ۲ هم به ۱ میشه رفت. پس {۱و۲}
از ۲ به ۳ میشه رفت، ولی از ۳ به ۲ نمیشه! پس دیگه ۳ تو مجموعه ی بالا قرار نمیگیره.
پس درواقع گره هایی توی یه مجموعه ی قویا همبند قرار میگیرن که از هر کدوم راهی به بقیه باشه.
اگه ۳ توی مجموعه ی بالا قرار بگیره راهی به ۱ یا ۲ نداره.
یه جورایی مولفه های قویا همبند توی گراف های جهت دار، معادلن با مولفه های همبند توی گراف بدون جهت!
حالا سوالتون نمیدونم دقیقا چیه :ی میخواید یه کم بیشتر توضیح بدید.
عکس خیلی حرفه ای شد ببخشید :ی
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
الان مجموعه مولفه های همبند قوی این گراف رو چیجوری بدست میاریم؟؟؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
ببخشید اگه بد شد
شما اول یه dfs روی گراف میزنی و زمان های f رو بدست میاری، بعدش یال ها رو برعکس میکنی و توی گراف جدیدت از راسی که بیشترین f رو داره دوباره dfs میزنی و تا اونجایی که میشه راس ملاقات میکنی و این میشه یه SCC حالا به همین ترتیب واسه سایر راس های دیده نشده عمل میکنیم. البته دقیقش یادم نیست
داداشی اصلا نفهمیدم
منظوره دوستمون اینه که هر فراخونی تابع دوم یه مولفه همبنده
(۰۴ بهمن ۱۳۹۲ ۰۲:۰۳ ب.ظ)mohammad.ardeshiri نوشته شده توسط:بازم نفهمیدم(04 بهمن ۱۳۹۲ ۰۱:۳۶ ب.ظ)Mindhunter نوشته شده توسط:(04 بهمن ۱۳۹۲ ۰۱:۲۷ ب.ظ)Riemann نوشته شده توسط:(04 بهمن ۱۳۹۲ ۰۱:۲۴ ق.ظ)Mindhunter نوشته شده توسط:(04 بهمن ۱۳۹۲ ۱۲:۴۹ ق.ظ)El@he نوشته شده توسط: خب مثلا اینجا از ۱ به ۲ میشه رفت، از ۲ هم به ۱ میشه رفت. پس {۱و۲}
از ۲ به ۳ میشه رفت، ولی از ۳ به ۲ نمیشه! پس دیگه ۳ تو مجموعه ی بالا قرار نمیگیره.
پس درواقع گره هایی توی یه مجموعه ی قویا همبند قرار میگیرن که از هر کدوم راهی به بقیه باشه.
اگه ۳ توی مجموعه ی بالا قرار بگیره راهی به ۱ یا ۲ نداره.
یه جورایی مولفه های قویا همبند توی گراف های جهت دار، معادلن با مولفه های همبند توی گراف بدون جهت!
حالا سوالتون نمیدونم دقیقا چیه :ی میخواید یه کم بیشتر توضیح بدید.
عکس خیلی حرفه ای شد ببخشید :ی
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
الان مجموعه مولفه های همبند قوی این گراف رو چیجوری بدست میاریم؟؟؟
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
ببخشید اگه بد شد
شما اول یه dfs روی گراف میزنی و زمان های f رو بدست میاری، بعدش یال ها رو برعکس میکنی و توی گراف جدیدت از راسی که بیشترین f رو داره دوباره dfs میزنی و تا اونجایی که میشه راس ملاقات میکنی و این میشه یه SCC حالا به همین ترتیب واسه سایر راس های دیده نشده عمل میکنیم. البته دقیقش یادم نیست
داداشی اصلا نفهمیدم
منظوره دوستمون اینه که هر فراخونی تابع دوم یه مولفه همبنده
یک سرچ بزن در مورد الگوریتم کازوراژو Kosaraju
(۰۶ بهمن ۱۳۹۲ ۱۱:۱۳ ب.ظ)Riemann نوشته شده توسط: یک سرچ بزن در مورد الگوریتم کازوراژو Kosaraju
داداشی گلم حل شد ممنون از همه
