تو کنکور کارشناسی ارشد آی تی سال ۸۴ تستی اومده که پرسیده:
یک گراف جهتدار را در نظر بگیرید فرض کنید این گراف را، با ماتریس هم جوار نشان می دهیم. کدام یک از گزاره های ذیل درست است؟
۱) شرط کافی برای آنکه این ماتریس از نوع بالا مثلثی باشد، آن است که Acyclicنباشد
۲)شرط لازم برای آنکه این ماتریس از نوع پایین مثلثی باشد، آن است که دو نقطه‌ی انفصالی داشته باشد.
۳) شرط لازم و کافی برای آنکه این ماتریس از نوع پایین مثلثی باشد، آن است که گراف فوق از نوع Acyclic باشد.
۴) شرط لازم برای آنکه این ماتریس از نوع بالا مثلثی باشد، آن است که گراف فوق از نوع Acyclic باشد.
کتاب پارسه میگه که گزینه‌ی ۴ درسته اما در کنکور گزینه‌ی ۳ درست اعلام شده.
یعنی کتاب پارسه میگه شرط کافی نیست این موضوع و صرفا لازمه
اما سوال من کلا اینه گراف Acyclic به چه گرافی گفته میشه؟؟
گرافی Acyclic، گرافی است است که دارای دور نیست.
خوب گرافی که دور نداره میشه درخت اما ماتریس مجاورت یه درخت بالا یا پایین مثلثی نمیشه؟؟
یعنی منظور گراف جهت داره؟ که دور هم نداره؟؟
بازم از راهنماییتون بی نهایت ممنونم
(۱۵ تیر ۱۳۹۰ ۱۱:۴۷ ب.ظ)shadi نوشته شده توسط: خوب گرافی که دور نداره میشه درخت اما ماتریس مجاورت یه درخت بالا یا پایین مثلثی نمیشه؟؟تعریف درخت:
یعنی منظور گراف جهت داره؟ که دور هم نداره؟؟
بازم از راهنماییتون بی نهایت ممنونم
a tree is an undirected graph in which any two vertices are connected by exactly one simple path
درخت جهت دار:
A directed tree is a directed graph which would be a tree if the directions on the edges were ignored. Some authors restrict the phrase to the case where the edges are all directed towards a particular vertex, or all directed away from a particular vertex (see arborescence).
گراف acyclic
a directed acyclic graph (DAG, i /ˈdæɡ/), is a directed graph with no directed cycles
منظور از درخت تو متن‌ها معمولا همون بدون جهتشه (اما بعضی جا‌ها هم منظور از درخت همون درخت جهت داره )
درخت همبنده اما گراف acyclic لزوما همبند نیست .
جواب سنجش درسته
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
با توجه با این , گراف جهت دار بدون دور شرط کافی برای پایین مثلثی بودنه .
بی نهایت از جواب کاملتون و وقتی که برای جواب دادن به سوالم گذاشتید ممنونم دوستان.