سوال مورد نظر پیوست شده است
جوابش رو گزینه ۳ زده و گفته که مورد ب درست نیست.
ممنون از دوستان
سلام
ابتدا دنباله درجات را به صورت زوج مرتب در میاورم که مولفه ی اول درجه ی ورودی و مولفه ی دوم درجه ی خروجی مثلا برای الف داریم[tex](0,2)(1,2)(2,1)(3,1)[/tex]
هربار یک راس دلخواه انتخاب میکنیم به شرطی که در جه ی خروجی ان صفر نباشدمثلا [tex](1,2)[/tex] این راس و کنار میگذاریم و در باقی مانده ی روئوس از ۲(درجه ی خروجی راس انتخاب شده) راس ابتدایی برحسب تریبب قاموسی غیر افزایشی ([tex]a_i\: >a_{i+1}\: or\: a_i=a_{i+1}\: and\: b_i\ge b_{i+1}[/tex])از درجه ی ورودی شان هر کدام یک واحد کم میکنیم مثلا اینجااولین راس [tex](3,1)[/tex] و دومین راس [tex](2,1)[/tex] در تریب قاموسی بین سه راس باقی مانده است حال از درجه ی ورودی هرکدام یک واحد کم میکنیم و همینطور درجه ی خروجی راس انتخاب شده را صفر میکنیم یعنی داریم[tex](0,2)(1,0)(1,1)(2,1)[/tex] در واقع ما یک راس انتخاب کردیم و از ان به دو راس دیگر یال رسم کردیم پس تا اینجا درجه ی خروجی راس انتخابی صفر شد و از درجه ی ورودی دوراس دیگر که یال به انها وارد شد یک واحد کم شد.دوباره یک راس دلخواه انتخاب میکنیم مثلا[tex](2,1)[/tex] چون درجه ی خروجی ان ۱ است پس اولین راس در ترتیب قاموسی سه راس باقی مانده را انتخاب میکنیم یعنی [tex](1,1)[/tex] و از درجه ی ورودی ان یک واحد کم میکنیم ودرجه ی خروجی راس انتخابی را هم ۰ میکنیم پس داریم [tex](0,2)(1,0)(0,1)(2,0)[/tex] راس دلخواه دیگر [tex](0,2)[/tex] واز دوراس ابتدایی ترتیب قاموسی سه راس دیگر هر کدام از ورودیشان یک واحد کم میکنیم و خروجی خود راس انتخابی را هم ۰ میکنیم یعنی داریم[tex](0,0)(0,0)(0,1)(1,0)[/tex] در این نقطه فقط راس [tex](0,1)[/tex] را میتواینم انتخاب کنیم چون فقط راس خروجی ان غیر صفر است(شرط اولیه ما) که باعث میشود ازورودی اولین راس در ترتیب قاموسی یک واحد کم و خروجی خودش هم. ۰ می شود پس داریم.[tex](0,0)(0,0)(0,0)(0,0)[/tex] زمانی که به این نقطه رسیدم یعنی این دنباله درجات, دنباله درجات یک گراف جهت دار است اگر منفی ایجاد بشه یاترتیب تکراری داشته باشیم می توان گفت که دنباله درجات یک گراف جهت دار نیست در کل اگر N راس داشته باشیم الگوریتم باید در n گام پایان بیابد ورگرنه ترتیب های تکراری تولید می شود. اسم این الگوریتمی که بررسی کردیم الگوریتم کلیتمن وانگ است.
برای حال ب داریم [tex](2,2)(2,2)(1,1)[/tex] راس [tex](2,2)[/tex] اول را انتخاب میکنیم پس داریم [tex](2,0)(1,2)(0,1)[/tex] اینبار راس[tex](1,2)[/tex] را نتخاب میکنیم حاصل [tex](1,0)(1,0)(-1,1)[/tex] چون منفی شد پس این دنباله, دنباله درجات یک گراف جهت دار نیست
برای حالت ج داریم [tex](1,2)(1,2)(2,3)(3,1)(3,2)[/tex]
با انتخاب [tex](2,3)[/tex] داریم [tex](1,2)(0,2)(2,0)(2,1)(2,2)[/tex]
با انتخاب[tex](2,2)[/tex] داریم [tex](1,2)(0,2)(1,0)(1,1)(2,0)[/tex]
با انتخاب [tex](1,2)[/tex] داریم [tex](1,0)(0,2)(1,0)(0,1)(1,0)[/tex]
با انتخاب [tex](0,2)[/tex] داریم [tex](0,0)(0,0)(0,0)(0,1)(1,0)[/tex]
با انتخاب [tex](0,1)[/tex] داریم [tex](0,0)(0,0)(0,0)(0,0)(0,0)[/tex]
پس ج هم دنباله در جات یک گراف جهت داراست پس جواب تست گزینه ۳ یعنی دو دنباله درجه ی گراف جهت دار داریم الف و ج
(۰۷ آذر ۱۳۹۶ ۰۳:۴۶ ب.ظ)msour44 نوشته شده توسط: سلام
ابتدا دنباله درجات را به صورت زوج مرتب در میاورم که مولفه ی اول درجه ی ورودی و مولفه ی دوم درجه ی خروجی مثلا برای الف داریم[tex](0,2)(1,2)(2,1)(3,1)[/tex]
هربار یک راس دلخواه انتخاب میکنیم به شرطی که در جه ی خروجی ان صفر نباشدمثلا [tex](1,2)[/tex] این راس و کنار میگذاریم و در باقی مانده ی روئوس از ۲(درجه ی خروجی راس انتخاب شده) راس ابتدایی برحسب تریبب قاموسی غیر افزایشی ([tex]a_i\: >a_{i+1}\: or\: a_i=a_{i+1}\: and\: b_i\ge b_{i+1}[/tex])از درجه ی ورودی شان هر کدام یک واحد کم میکنیم مثلا اینجااولین راس [tex](3,1)[/tex] و دومین راس [tex](2,1)[/tex] در تریب قاموسی بین سه راس باقی مانده است حال از درجه ی ورودی هرکدام یک واحد کم میکنیم و همینطور درجه ی خروجی راس انتخاب شده را صفر میکنیم یعنی داریم[tex](0,2)(1,0)(1,1)(2,1)[/tex] در واقع ما یک راس انتخاب کردیم و از ان به دو راس دیگر یال رسم کردیم پس تا اینجا درجه ی خروجی راس انتخابی صفر شد و از درجه ی ورودی دوراس دیگر که یال به انها وارد شد یک واحد کم شد.دوباره یک راس دلخواه انتخاب میکنیم مثلا[tex](2,1)[/tex] چون درجه ی خروجی ان ۱ است پس اولین راس در ترتیب قاموسی سه راس باقی مانده را انتخاب میکنیم یعنی [tex](1,1)[/tex] و از درجه ی ورودی ان یک واحد کم میکنیم ودرجه ی خروجی راس انتخابی را هم ۰ میکنیم پس داریم [tex](0,2)(1,0)(0,1)(2,0)[/tex] راس دلخواه دیگر [tex](0,2)[/tex] واز دوراس ابتدایی ترتیب قاموسی سه راس دیگر هر کدام از ورودیشان یک واحد کم میکنیم و خروجی خود راس انتخابی را هم ۰ میکنیم یعنی داریم[tex](0,0)(0,0)(0,1)(1,0)[/tex] در این نقطه فقط راس [tex](0,1)[/tex] را میتواینم انتخاب کنیم چون فقط راس خروجی ان غیر صفر است(شرط اولیه ما) که باعث میشود ازورودی اولین راس در ترتیب قاموسی یک واحد کم و خروجی خودش هم. ۰ می شود پس داریم.[tex](0,0)(0,0)(0,0)(0,0)[/tex] زمانی که به این نقطه رسیدم یعنی این دنباله درجات, دنباله درجات یک گراف جهت دار است اگر منفی ایجاد بشه یاترتیب تکراری داشته باشیم می توان گفت که دنباله درجات یک گراف جهت دار نیست در کل اگر N راس داشته باشیم الگوریتم باید در n گام پایان بیابد ورگرنه ترتیب های تکراری تولید می شود. اسم این الگوریتمی که بررسی کردیم الگوریتم کلیتمن وانگ است.
برای حال ب داریم [tex](2,2)(2,2)(1,1)[/tex] راس [tex](2,2)[/tex] اول را انتخاب میکنیم پس داریم [tex](2,0)(1,2)(0,1)[/tex] اینبار راس[tex](1,2)[/tex] را نتخاب میکنیم حاصل [tex](1,0)(1,0)(-1,1)[/tex] چون منفی شد پس این دنباله, دنباله درجات یک گراف جهت دار نیست
برای حالت ج داریم [tex](1,2)(1,2)(2,3)(3,1)(3,2)[/tex]
با انتخاب [tex](2,3)[/tex] داریم [tex](1,2)(0,2)(2,0)(2,1)(2,2)[/tex]
با انتخاب[tex](2,2)[/tex] داریم [tex](1,2)(0,2)(1,0)(1,1)(2,0)[/tex]
با انتخاب [tex](1,2)[/tex] داریم [tex](1,0)(0,2)(1,0)(0,1)(1,0)[/tex]
با انتخاب [tex](0,2)[/tex] داریم [tex](0,0)(0,0)(0,0)(0,1)(1,0)[/tex]
با انتخاب [tex](0,1)[/tex] داریم [tex](0,0)(0,0)(0,0)(0,0)(0,0)[/tex]
پس ج هم دنباله در جات یک گراف جهت داراست پس جواب تست گزینه ۳ یعنی دو دنباله درجه ی گراف جهت دار داریم الف و ج
ممنونم از وقتی که گذاشتید. رویه کار درسته ولی توی صورت سوال گفته که نباید یال چندگانه داشته باشیم، با این حل در گزینه ۱ بین رئوس c و d یال چندگانه ایجاد میشه. در کل برای گزینه یک هرمدل دیگه هم رئوس رو شروع کنیم بهرحال بین راس d با یک راس دیگر یال چندگانه ایجاد خواهد شد
(۱۳ آذر ۱۳۹۶ ۱۰:۱۱ ب.ظ)Sepideh96 نوشته شده توسط:دوست گرامی به نظر یال چند گانه ایجاد نمیشه باز بهتر بود منظورتونو از c و d مشخص میکردید که کدام راس ها هستش اگر را س های (۱و۲ ) و (۳,۱) باشه باز یال چند گانه ایجاد نمیشه.بله یک یال چهت دار از (۱و۲) به (۱و۳) و برعکس ایجاد میشه ولی توجه کنید این یال چندگانه نیست گراف ما گرافی چهت دار است و بین این دوراس دو یال در جهت های متفاوت ایجاد میشه و این صورت سوال را نقض نمیکند.در سوال گفته از یک راس به راس دیگر حداکثر یک یال جهت دار وجود دارد در اینجا هم از c به d یک یال جهت دار و از d به c هم یک یال جهت دار وجود دارد.(07 آذر ۱۳۹۶ ۰۳:۴۶ ب.ظ)msour44 نوشته شده توسط:
ممنونم از وقتی که گذاشتید. رویه کار درسته ولی توی صورت سوال گفته که نباید یال چندگانه داشته باشیم، با این حل در گزینه ۱ بین رئوس c و d یال چندگانه ایجاد میشه. در کل برای گزینه یک هرمدل دیگه هم رئوس رو شروع کنیم بهرحال بین راس d با یک راس دیگر یال چندگانه ایجاد خواهد شد
(۱۴ آذر ۱۳۹۶ ۰۲:۰۴ ق.ظ)msour44 نوشته شده توسط:(13 آذر ۱۳۹۶ ۱۰:۱۱ ب.ظ)Sepideh96 نوشته شده توسط:دوست گرامی به نظر یال چند گانه ایجاد نمیشه باز بهتر بود منظورتونو از c و d مشخص میکردید که کدام راس ها هستش اگر را س های (۱و۲ ) و (۳,۱) باشه باز یال چند گانه ایجاد نمیشه.بله یک یال چهت دار از (۱و۲) به (۱و۳) و برعکس ایجاد میشه ولی توجه کنید این یال چندگانه نیست گراف ما گرافی چهت دار است و بین این دوراس دو یال در جهت های متفاوت ایجاد میشه و این صورت سوال را نقض نمیکند.در سوال گفته از یک راس به راس دیگر حداکثر یک یال جهت دار وجود دارد در اینجا هم از c به d یک یال جهت دار و از d به c هم یک یال جهت دار وجود دارد.(07 آذر ۱۳۹۶ ۰۳:۴۶ ب.ظ)msour44 نوشته شده توسط:
ممنونم از وقتی که گذاشتید. رویه کار درسته ولی توی صورت سوال گفته که نباید یال چندگانه داشته باشیم، با این حل در گزینه ۱ بین رئوس c و d یال چندگانه ایجاد میشه. در کل برای گزینه یک هرمدل دیگه هم رئوس رو شروع کنیم بهرحال بین راس d با یک راس دیگر یال چندگانه ایجاد خواهد شد
بله درسته. خیلی ممنون.
من تصورم این بود که اگر بین دو راس دو یال جهت دار (مخالف) باشه یال چندگانه ایجاد میشه