زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۰۲:۰۳ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

سوال ۹۷ مهندسی ۹۴

ارسال:
  

mzha پرسیده:

سوال ۹۷ مهندسی ۹۴

سلام
صورت سوال این هست چند مورد رو میتونیم توی v+e در گراف بدون جهت وبی وزن باdfsب دست بیاریم که مورد اول بررسی دو بخشی بودن هست وجواب گفته که میشه این مورد روبا dfsب دست اورد مگه دو بخشی روباbfsنمیگفتیم؟هر دومیشه؟یا شرایط خاص داره؟
ممنون[/size]
نقل قول این ارسال در یک پاسخ

۲
ارسال:
  

msour44 پاسخ داده:

RE: سوال ۹۷ مهندسی ۹۴

سلام
در تشخیص دو بخشی بودن از هر دوی bfs , dfs می توان استفاده کرد.
در دوبخشی می توان رئوس را به دوبخش تقسیم کردطوری که برای هر یال دو سر ان در دو بخش قرار می گیرد.در هر دو از این نکته که هر گرافی که عدد کروماتیک ان ۲ باشد دوبخشی است و برعکس استفاده می شود(در اصل برای اثبات نبود دور فرد استفاده می شود).یعنی در دوبخشی می توان رئوس را با دو رنگ رنگ امیزی کرد.
در bfs که به صورت سطح به سطح پیمایش می شود(استفاده از صف) از دو رنگ مثلا قرمز و ابی استفاده می کنیم ریشه را قرمز و فرزندان ان را ابی و بعد که فرزندان فرزندهای ریشه را پیمایش می کینم را دوباره ابی و ال اخر ...در dfs هم که در عمق حرکت می کنیم نودها را یک در میان قرمز و ابی می کنیم (البته توجه شود که هر نود یک بار رنگ می گیرد) بعد از اتمام پیمایش تمامی یال ها را بررسی می کنیم که دو راس هر یال دارای دو رنگ متفاوت باشند این الگورتیم در کل از مرتبه[tex]O(n+e)[/tex] البته با لیست و با مارتریس [tex]O(n^2)[/tex]
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Behnam‌ پاسخ داده:

RE: سوال ۹۷ مهندسی ۹۴

(۳۰ اسفند ۱۳۹۵ ۱۰:۱۸ ق.ظ)mzha نوشته شده توسط:  سلام
صورت سوال این هست چند مورد رو میتونیم توی v+e در گراف بدون جهت وبی وزن باdfsب دست بیاریم که مورد اول بررسی دو بخشی بودن هست وجواب گفته که میشه این مورد روبا dfsب دست اورد مگه دو بخشی روباbfsنمیگفتیم؟هر دومیشه؟یا شرایط خاص داره؟
ممنون[/size]

سلام
لطفاً صورت سؤال رو کامل بذارید. هر دو میشه:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

mzha پاسخ داده:

RE: سوال ۹۷ مهندسی ۹۴

ممنون از پاسختون
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  سوال مهندسی نرم افزار سال ۸۶(مهندسی نیازمندی ها) tarane1992 ۴ ۴,۸۲۵ ۲۲ بهمن ۱۳۹۷ ۰۲:۳۷ ق.ظ
آخرین ارسال: Bon_Nemesis
  فرق بین مهندسی کامپیوتر گرایش نرم افزار با مهندسی کامپیوتر نرم افزار Rafaat ۰ ۳,۷۸۷ ۲۵ اردیبهشت ۱۳۹۷ ۰۲:۴۵ ب.ظ
آخرین ارسال: Rafaat
  سوال ۱۱۵- مهندسی ۹۶- منطق مرتبه اول mzi ۰ ۱,۵۲۷ ۲۱ فروردین ۱۳۹۷ ۰۵:۰۵ ب.ظ
آخرین ارسال: mzi
  درخواست حل سوال گراف از مهندسی کامپیوتر ۹۳ Sepideh96 ۴ ۲,۷۷۱ ۱۴ آذر ۱۳۹۶ ۰۲:۲۹ ق.ظ
آخرین ارسال: Sepideh96
  سوال درباره علوم تصمیم و مهندسی دانش mohammad386 ۷ ۶,۲۴۷ ۱۶ خرداد ۱۳۹۶ ۰۹:۵۳ ب.ظ
آخرین ارسال: mehran_360
  سیستم عامل ۹۴و ۹۵ فناوری اطلاعات signal_micro ۲ ۲,۵۴۷ ۰۴ اردیبهشت ۱۳۹۶ ۰۱:۱۷ ب.ظ
آخرین ارسال: Rehe1994
  سوال ۱۲۰ مهندسی هوش ۹۲ MBe ۱ ۱,۵۹۵ ۰۴ اردیبهشت ۱۳۹۶ ۰۸:۲۳ ق.ظ
آخرین ارسال: آزادمنش
  سوال ۴۶ گسسته کنکور ارشد مهندسی کامپیوتر سال ۹۵ mhasa ۱۳ ۸,۵۴۷ ۱۲ فروردین ۱۳۹۶ ۰۱:۵۴ ب.ظ
آخرین ارسال: ali.majed.ha
  مهندسی کامپیوتر ۸۸-سوال ۷۵-چارت ASM MiladCr7 ۵ ۴,۸۹۴ ۱۰ اسفند ۱۳۹۵ ۰۸:۳۲ ق.ظ
آخرین ارسال: M a h d i
  سوال مهندسی کامپیوتر - آزاد ۸۵ ali.majed.ha ۴ ۲,۲۲۷ ۲۹ بهمن ۱۳۹۵ ۱۰:۱۳ ب.ظ
آخرین ارسال: ali.majed.ha

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close