۳۴- گزینه ۱ درست است.
با استفاده از مثال نقض زیر می توان نشان داد که هیچ یک از گزاره های ۱ و ۲ صحیح نیستند. گراف زیر را در نظر بگیرد. در این گراف کوتاهترین مسیر از گره ۱ به گره ۳ از گره ۲ رد می شود و طول آن برابر ۳- است.
با اجرای الگوریتم WEIGHTS گراف در دو مرحله به صورت زیر تبدیل می شود در این گراف طول کوتاهترین مسیر از گره ۱ به گره ۳ برابر صفر است و این مسیر از هیچ گره میانی ای رد نمی شود.
*******************************************************************************************************
۳۵-گزینهی ۱ صحیح میباشد.
این مسئله را همانند مسئلهی طولانیترین زیردنبالهی مشترک میتوان توسط برنامهنویسی پویا و در زمان [tex]O(nm)[/tex]
محاسبه نمود.
قدم اول: بازای هر [tex]0\leq i \leq n[/tex] و [tex]0\leq j \leq m[/tex] ، فرض کنیم که [tex]X_{i}[/tex] بیانگر دنبالهی [tex]x_{1}... x_{i}[/tex] و [tex]Y_{j}[/tex] بیانگر دنبالهی [tex]y_{1}... y_{j}[/tex] باشد. لذا [tex]Y_{m}=Y , X_{n}=X[/tex] میباشد. عنصر [tex](0\leq i\leq n , 0\leq j\leq m) S[i,j][/tex] از ماتریس S را به عنوان طول کوتاهترین ابردنبالهی، دنبالهی [tex]X_{i}[/tex] و [tex]Y_{j}[/tex] در نظر میگیریم. در نهایت پس از اتمام الگوریتم [tex]S[n,m][/tex] بیانگر طول کوتاهترین ابردنبالهی دنبالههای X و Y خواهد بود.
قدم دوم: بطور واضح کوتاهترین ابردنبالهی مشترک یک دنبالهی s با هر دنبالهی خالی خود دنبالهی s خواهد بود. بنابراین بازای تمام مقادیر [tex]0\leq i \leq n[/tex] و [tex]0\leq j \leq m[/tex] خواهیم داشت: [tex]S[i,0]=i[/tex] و [tex]S[0,j]=j[/tex] .
حال برای هر مرحله از برنامهنویسی پویا داریم:
۱- اگر [tex]x_{i}=y_{j}[/tex] باشد، آنگاه میتوان آنها را با یک عنصر یکسان مشترک جایگزین نمود. به عبارتی افزودن [tex]x_{i}[/tex] به SCS دنبالههای [tex]X_{i-1}[/tex] و [tex]Y_{j-1}[/tex] ، کوتاهترین ابردنبالهی مشترک [tex]X_{i}[/tex] و [tex]Y_{j}[/tex] را میسازد که دارای طول [tex]S[i-1,j-1] 1[/tex] میباشد.
۲- اگر [tex]x_{i}\neq y_{j}[/tex] باشد، آنگاه یا باید [tex]x_{i}[/tex]را به SCS دنبالهی [tex]X_{i-1}[/tex] و [tex]Y_{j}[/tex] بیافزاییم و یا باید [tex]y_{j}[/tex] را به SCS دنبالههای [tex]X_{i}[/tex] و [tex]Y_{j-1}[/tex] بیافزاییم. کمینهی این دو حالت جواب مسئله میباشد
لذا رابطهی بازگشتی به صورت زیر میباشد:
[tex]S[i,j]=min\left\{\begin{matrix} S[i-1,j] 1 & \\ S[i,j-1] 1 & \\ S[i-1,j-1] 1 & x_{i}=y_{j} \end{matrix}\right.[/tex]
*******************************************************************************************************
۳۶- گزینه ۱ صحیح است.
مسئله اول به مسئله خوشه (Clique) معروف بوده و جز مسائل ان پی است که بهترین الگوریتم موجود برای حل آن از مرتبه [tex]n^{o(n)}[/tex] است.
مسئله دوم در واقع مسئله کوله پشتی صفر و یک است. این مسئله ان پی تمام است و بهترین الگوریتمی که تا به حال پیدا شده و آن را حل می کند نمایی است.
مسئله سوم را نمی توان در زمان چندجمله ای حل کرد زیرا گرافهایی وجود دارند که تعداد دورهای آن ها از مرتبه نمایی بوده و مشخص است که هیچ الگوریتم کلی ای نمی تواند همه دورهای این گونه گراف ها را در زمان چندجمله ای تشخیص دهد. به عنوان مثال گراف های کامل از این گونه گراف ها هستند که تعداد دورهای آن از مرتبه نمایی است.
مسئله چهارم نیز در واقع مسئله تصمیم هامیلوتی بودن یگ گراف است که این مسئله نیز یک مسئله ان پی بوده و بهترین الگوریتم موجود برای حل آن از مرتبه [tex]O(n2^{n})[/tex] است.
*******************************************************************************************************
۳۷-گزینه ۲ صحیح است.
این مسئله با استفاده از روش برنامه نویسی پویا برای ضرب زنجیری ماتریس ها قابل حل است اما از آنجا که این راه حل طولانی است بهتر است از نکته زیر برای حل این گونه سئوالات استفاده شود.
نکته: سعی کنید ابتدا [tex]A_{i}\times A_{i 1}[/tex] هایی را انجام دهید که [tex]d_{i 1}[/tex] (بعد دوم ماتریس اول) بزرگتر،و [tex]d_{i}[/tex] و [tex]d_{i 1}[/tex] کوچکتر باشند.
در این مسئله ابتدا [tex]A_{2}\times A_{3}[/tex] انجام می شود و ماتریس X با ابعاد [tex]40 \times 5[/tex] حاصل می شود. تعداد ضرب ها در این مرحله برابر [tex]40 \times 20 \times 5 =4000[/tex] است. بعد از این مرحله مسئله تبدیل می شود به محاسبه کمینه حاصلضربهای [tex]A_{1} \times X \times A_{4} \times A_{5}[/tex] .
در گام ۲، [tex]A_{1} \times X[/tex] را انجام می دهیم که ماتریس Y با ابعاد [tex]30 \times 5[/tex] حاصل می شود. تعداد ضرب ها در این مرحله برابر [tex]30 \times 40 \times 5=6000[/tex] است. بعد از این مرحله مسئله تبدیل می شود به محاسبه کمینه حاصلضربهای [tex]Y \times A_{4} \times A_{5}[/tex] .
در گام ۳، [tex]A_{4} \times A_{5}[/tex] را انجام می دهیم که ماتریس Z با ابعاد [tex]5 \times 20[/tex] حاصل می شود. تعداد ضرب ها در این مرحله برابر [tex]5 \times 10\times 20=1000[/tex] است. بعد از این مرحله مسئله تبدیل می شود به محاسبه کمینه حاصلضربهای [tex]Y \times Z[/tex] .
در گام ۴، [tex]Y \times Z[/tex] انجام می شود که تعداد اعمال ضرب برای محاسبه آن برابر است با [tex]30 \times 5\times 20=3000[/tex] .
بنابراین تعداد کل ضرب های لازم برابر است با: ۱۴۰۰۰
*******************************************************************************************************
۳۸- گزینه ۴ صحیح است.
برای تشخیص اویلری بودن یک گراف می توان از قضیه زیر استفاده کرد:
قضیه: یک گراف اویلری است اگر و تنها اگر همبند بوده و درجه تمامی رئوس آن زوج باشد.
از آنجا که تشخیص همبند بودن یک گراف، و همچنین تشخیص اینکه درجه تمامی رئوس زوج است یا خیر هر دو در زمان چندجمله ای قابل انجام هستند بنابراین تشخیص اویلری بودن یک گراف جز مسائل پی (P) بوده و چون هر مسئله P در NP نیز هست، پس یک مسئله NP میباشد. با توجه به این مطلب بدیهی است که تشخیص اویلری نبودن یک گراف نیز در زمان چندجلمه ای قابل تشخیص بوده و این مسئله نیز جز مسائل P و در نتیجه NP است.
تشخیص همیلتنی بودن یک گراف جز مسائل ان پی کامل(NP-C) است زیرا می توان آن را در زمان چندجمله ای به مسئله فروشنده دوره گرد (TSP) کاهش داد و مسئله TSP نیز NP-C است. تشخیص همیلتونی نبودن یک گراف نیز جز مسائل ان پی است.