گراف جهت دار با مجموعه گره های [tex]V={a,b,c,d,e}[/tex]
و مجموعه یال های [tex]E={(a,c),(a,e),(c,d),(d,e),(e,b),(e,c)}[/tex]
را در نظر بگیرید . اگر این گراف با روش پیمایش عمق اول، پیمایش شود به ترتیب از چپ به راست، تعداد کمان های درخت، کمان های برگشتی، کمان های ضربدری و کمان های جلورو برابر کدام است؟
پاسخ: گزینه ۴
۱) (۴,۰,۱,۱)
۲) (۴,۱,۱,۰)
۳) (۳,۲,۱,۰)
۴) (۴,۱,۰,۱)
(19 بهمن 1390 11:06 ب.ظ)zeinab نوشته شده توسط: [ -> ]گراف جهت دار با مجموعه گره های [tex]V={a,b,c,d,e}[/tex]
و مجموعه یال های [tex]E={(a,c),(a,e),(c,d),(d,e),(e,b),(e,c)}[/tex]
را در نظر بگیرید . اگر این گراف با روش پیمایش عمق اول، پیمایش شود به ترتیب از چپ به راست، تعداد کمان های درخت، کمان های برگشتی، کمان های ضربدری و کمان های جلورو برابر کدام است؟
پاسخ: گزینه ۴
۱) (۴,۰,۱,۱)
۲) (۴,۱,۱,۰)
۳) (۳,۲,۱,۰)
۴) (۴,۱,۰,۱)
وقتی با پیمایش عمق اول یا همون DFS کار میکنیم برای هر گره دو مقدار ذخیره میشه یکی مربوط زمان ملاقات گره و دیگری هم مربوط به زمان به پایان هست.
با توجه به این دو زمان میشه مشخص کرد که هر یال بین گره‌ها از چه نوعی هستن:
در هنگام پیمایش گراف فرض کن دو گره AوB رو داریم که از A به سمت B یال وجود داره A--->B
اگه مقدار زمان ملا قات گره Bاز گره A بیشتر باشه و زمان پایان هنوز ثبت نشده ---->یال درختی
مقدار زمان ملا قات گره B از A کمتره ولی برای B هنوز زمان پایان ثبت نشده اما A به پایان رسیده ---->یال برگشتی
مقدار زمان ملاقات گره B از A کمتر اما زمان پایان از A بیشتر ----->یال جلورو
مقدار هم زمان ملاقات و هم زمان پایان گره B از A کمتره------->یال ضربدری
اگه گراف این سوال رو بکشی و این چیزایی که بالا گفتم رو مشخص کنی و بررسی کنی همون گزینه‌ی ۴ جواب میشه
(19 بهمن 1390 11:06 ب.ظ)zeinab نوشته شده توسط: [ -> ]گراف جهت دار با مجموعه گره های [tex]V={a,b,c,d,e}[/tex]
و مجموعه یال های [tex]E={(a,c),(a,e),(c,d),(d,e),(e,b),(e,c)}[/tex]
را در نظر بگیرید . اگر این گراف با روش پیمایش عمق اول، پیمایش شود به ترتیب از چپ به راست، تعداد کمان های درخت، کمان های برگشتی، کمان های ضربدری و کمان های جلورو برابر کدام است؟
پاسخ: گزینه ۴
۱) (۴,۰,۱,۱)
۲) (۴,۱,۱,۰)
۳) (۳,۲,۱,۰)
۴) (۴,۱,۰,۱)
راه حل ساده‌تر اینه که گراف رو رسم کنید و پیمایش DFS رو روش انجام بدید.
هر یالی که در گراف حاصل از DFS موند می شه درختی
هر یالی که یک فرزند رو به باباش متصل کرد می شه برگشتی
هر یالی که باباش رو به فرزند متصل کرد می شه جلو رو
بقیه چرت و پرت‌ها می شه ضربدری
راه حل ساده‌تر اینه که گراف رو رسم کنید و پیمایش DFS رو روش انجام بدید.
هر یالی که در گراف حاصل از DFS موند می شه درختی
هر یالی که یک فرزند رو به باباش متصل کرد می شه برگشتی
هر یالی که باباش رو به فرزند متصل کرد می شه جلو رو
بقیه چرت و پرت‌ها می شه ضربدری
[/quote]
مرسی اما درست متوجه نشدم !!
اگر هر یالی که باباش رو به فرزند متصل کرد می شه جلو رو " پس ۵ تا یال میشه جلورو!!!
میشه اسم یال‌ها رو برام بنویسین در مورد هرکدوم.
وقتی با پیمایش عمق اول یا همون DFS کار میکنیم برای هر گره دو مقدار ذخیره میشه یکی مربوط زمان ملاقات گره و دیگری هم مربوط به زمان به پایان هست.
با توجه به این دو زمان میشه مشخص کرد که هر یال بین گره‌ها از چه نوعی هستن:
در هنگام پیمایش گراف فرض کن دو گره AوB رو داریم که از A به سمت B یال وجود داره A--->B
اگه مقدار زمان ملا قات گره Bاز گره A بیشتر باشه و زمان پایان هنوز ثبت نشده ---->یال درختی
مقدار زمان ملا قات گره B از A کمتره ولی برای B هنوز زمان پایان ثبت نشده اما A به پایان رسیده ---->یال برگشتی
مقدار زمان ملاقات گره B از A کمتر اما زمان پایان از A بیشتر ----->یال جلورو
مقدار هم زمان ملاقات و هم زمان پایان گره B از A کمتره------->یال ضربدری
اگه گراف این سوال رو بکشی و این چیزایی که بالا گفتم رو مشخص کنی و بررسی کنی همون گزینه‌ی ۴ جواب میشه
[/quote]
کی مقدار زمان ملاقات یک گره بیشتره؟!!!
از ریشه شروع میکنیم زمان ملاقات ریشه =۱ هست بعد فرزند با شماره کوچکتر رو ملاقات میکنیم زمان ملاقات=۲ حالا به همین ترتیب میریم پایین و فرزندان هر گره رو ملاقات میکنیم و وقتی دیگه نود فرزندی نداشت گره های هم سطحش رو ملاقات میکنیم و ....
وقتی برای یک گره همه فرزندانش رو ملاقات کردیم برمیگردیم و اون گره رو ترک میکنیم که زمان ترک میشه زمان ترک آخرین فرزند+۱ .
زمان ملاقات پایین ترین و راست ترین گره از همه بیشتره. (وقتی گره های یک سطح از چپ به راست شماره گذاری شده باشند )
زمان ملاقات ریشه =۱
زمان ترک ریشه هم از همه بیشتره.
(20 بهمن 1390 06:27 ب.ظ)zeinab نوشته شده توسط: [ -> ]کی مقدار زمان ملاقات یک گره بیشتره؟!!!
زمان ملاقات یعنی اینکه اولین باری که گره رو میبینیم پس اگه تو یک گره رو زودتر از گره دیگه ایی ببینی زمان ملا قات گره بعدی بیشتر از گره قبلی میشه
به عنوان مثال یک شکل رو پیوست کردم که شماره های کوچکتر (در صورت کسر)نشون دهنده‌ی اینه که گره زودتر ملا قات شده و یا اینکه (در مخرج کسر)زودتر بازدید از گره وفرزندانش به پایان رسیده