صفحه‌ها: ۱ ۲
لبه متقاطع منظورش چی ؟
گزینه درست رو ۴ گفته . چرا ؟
خودم عکسی که گذاشته بودم رو نشد باز کنم نمی دو نم چرا .... سوال رو نوشتم .
سوال : G یک گراف متصل و T یکی از درختان پوشای عمقی برای آن است انگاه
۱- G حداقل یک لبه متقاطع با Tدارد .
۲-G حداکثر یک لبه متقاطع با T دارد .
۳-G دقیقا یک لبه متقاطع با T دارد
۴-G هیچ لبه متقاطع با T ندارد
منظور از لبه یا Edge همون یال هست.متقاطع هم یعنی برخورد و قطع که معلومه
می دونم این رو اما این یعنی چی:
G" هیچ لبه متقاطع با T ندارد "
می شه یکم بیشتر توضیح بدین .
(۲۵ آذر ۱۳۹۱ ۰۱:۱۱ ق.ظ)ana_12345 نوشته شده توسط: لبه متقاطع منظورش چی ؟منظور از لبه ، همان یال است و منظور از لبه متقاطع یال cross هست.
یعنی وقتی داریم گراف رو پیمایش میکنیم ، درحالی که همه گرهها پیمایش نشده اند ، به بن بست میرسیم و دیگر نمی توانیم ادامه دهیم و برای دیدن و بسط گره بعدی مجبوریم به عقب برگردیم تا جایی که اولین گره پیمایش نشده را ببینیم ، در این شورت یالی که بین این دو گره ایجاد می شود را یال cross یا متقاطع میگویند(چون دو بخش مجزا از درخت را به هم وصل میکند ، درضمن این دو بخش هیچ ارتباط والد و فرزندی بینشان نیست).
مرسی از توضیحتون اما منم تعریف یال cross رو می دونم اما چرا گفته گزینه ۴ درست. مفهوم G" هیچ لبه متقاطع با T ندارد " یعنی چی ؟؟؟؟ من فکر کردم منظوزش اینه که cross داره یا نه که در اینصورت میشه گزینه ۱/
مطمئن نیستم ولی شاید منظرش اینه که چون t شامل همه رئوس کمینه میشه طبیعتا همه یالها رو پوشش داده ونیازی نیست که به گره دیگه ای از g وصل بشه (چون دروااقع یال کراس یعنی راهمون بسته شده و مجبوریم بازگشت داشته باشیم به گره بسط نیافته ، ولی در اینجا که کل گراف با جستجوی عمقی پوشش داده شده نیازی به بازگشت نیست)
گراف متصل هم گرافی هست که حداقل C(n-1,2)+1 یال داشته باشه.تا اینجا بلد بودم.کاش می گفتی سوالو از کجا آوردی
سوال گنگه. ولی تحلیل من اینه:
بخاطر اینکه پیمایش عمقی از پشته استفاده می کنه نیاز به بازگشت به شکلی که از یال های قبلی عبور کنه نداره.
مثلا R ریشه هست و A وB دو فرزند اولش و داریم تو مسیر A و فرزنداش پیمایش عمقی انجام میدیم.
اول S خونده می شه و B و بعد A در پشته قرار داده می شه.
حالا در مسیر فرزندان A به پیمایش ادامه می دیم و هی پشته اضافه و کم میشه و مثلا می رسیم به جایی که دیگه نمیشه پیمایش ادامه پیدا کنه ولی هنوز پیمایش پوشا نشده. در گراف مجبور می شه cross ایجاد کنه ولی تو پیمایش عمقی چون از پشته بهره می بره الان B در ابتدای پشته هست و به راحتی و بدون ایجاد cross فرزنداشو بسط می ده و به پیمایشش ادامه می ده و زمانی پشته خالی می شه که درخت پوشایی ایجاد شده باشه.
حالا سوالی که ایجاد می شه اینه که اگه با پیمایش سطحی که از صف استفاده می کنه انجام بدیم موقع شبیه سازیش روی گراف cross ایجاد می شه؟ یا بهتر بگم تو کدوم نوع از پیمایشها وقتی رو گراف شبیه سازی می شه cross ایجاد می شه. تا بتونیم با عمقی مقایسش کنیم؟
چه ربطی داشت ؟
معمولا الگوریتمی که از پشته استفاده کنه میشه بازگشتی
(۲۷ آذر ۱۳۹۱ ۰۳:۰۷ ب.ظ)csharpisatechnology نوشته شده توسط: چه ربطی داشت ؟مگه تعریف گراف متصل شما به قضیه ربطی داشت
معمولا الگوریتمی که از پشته استفاده کنه میشه بازگشتی
.من نگفتم جواب کامل هست چون اصلا سوال گنگه معلوم نیست چی می خواد!
صورت سوال گفته با پیمایش عمقی درخت پوشا ساخته شده.
باید دید خواص پیمایش عمقی چی هست که باعث تفاوت با بقیه پیمایشها می شه. مهمترین خصیصه اش اینه که با پشته پیاده سازی می شه.
(۲۶ آذر ۱۳۹۱ ۱۱:۵۴ ب.ظ)fatima1537 نوشته شده توسط: (چون دروااقع یال کراس یعنی راهمون بسته شده و مجبوریم بازگشت داشته باشیم به گره بسط نیافته ، ولی در اینجا که کل گراف با جستجوی عمقی پوشش داده شده نیازی به بازگشت نیست)وقتی DFS استفاده می کنیم هم کل گراف رو پوشش می دیم و در نهایت درخت بدست امده پوشا هستش اصلا هدفمون از پیمایش همین " که کل نود ها رو بازدید کنیم " و حالا بسته به نوع گراف میشه بازگشت داشته باشیم و یال کراس ایجاد بشه .
(۲۷ آذر ۱۳۹۱ ۰۹:۱۷ ق.ظ)farhadk نوشته شده توسط: یا بهتر بگم تو کدوم نوع از پیمایشها وقتی رو گراف شبیه سازی می شه cross ایجاد می شه. تا بتونیم با عمقی مقایسش کنیم؟
DFS در گراف جهت دار کراس داره .
DFS در گراف بدون جهت کراس نداره .
BFS کراس نداره و فقط عقب گرد و درختی داره .
(۲۷ آذر ۱۳۹۱ ۰۵:۳۱ ق.ظ)csharpisatechnology نوشته شده توسط: .کاش می گفتی سوالو از کجا آوردی
سوال ازمون سنجش تسلط هستش.
فک کنم همون یال منظورشه
حرفا تون باعث شد یه نتیجه برسم :
سوال گفته G یک گراف متصل و T یکی از درختان پوشای عمقی برای آن است.
جواب :
-G هیچ لبه متقاطع با T ندارد
اگر جواب معنیش این باشه که گراف یال متقاطع نداره به نظر من با صورت سوال داده شده فقط نمیتونیم به این نتیجه برسیم .چون تعریف درخت پوشای عمقی که فقط درختی نیست که الزاما یال کراس نداشته باشیم یا به عبارت دیگه به هیچ نود بسط داده شده ای ارجاع نکنیم منظورم اینه که هر پیمایش عمقی درخت پوشا عمقی می ده مگه نه ؟ حالا چه کراس داشته باشن چه نداشته باشن .
(۲۷ آذر ۱۳۹۱ ۰۴:۴۷ ب.ظ)ana_12345 نوشته شده توسط: DFS در گراف جهت دار کراس داره .منم بخاطر همین سوال کردم چون دیدم تو BFS هم cross ایجاد نمی شه.
DFS در گراف بدون جهت کراس نداره .
BFS کراس نداره و فقط عقب گرد و درختی داره .
در گراف جهت دار به این خاطر cross ایجاد می شه که مثلا فرض کنین از S شروع می کنیم دو گره بهش وصل هستن یکی A و دیگری B جهت از S به Aهست و فرض کنین جهت از B به سمت S.
حالا S گره B رو نمی خونه و در پشته قرار نمیده چون به B دسترسی نداره بلکه B بهش دسترسی داره.
A رو میخونه و فرزندانش هم همینطور. فرض می کنیم دیگه نمی تونه ادامه بده ولی الان تو پشته B نیست و مجبور می شه cross بوجود بیاره و B رو تو پشته قرار بده.
من جواب پاسخنامه رو هم می زارم .که دقیقا پیدا فقط گراف رو بدون جهت در نظر میگیره .
شایدم درست خوب تعریف گراف در اصل بدون جهت بودن .
DFS در گراف بدون جهت فقط یال عقب گرد و درختی داره .و کراس نداره .