. . .
: کارشناسی مرکز آزمون و سنجش حضرت علی(ع): ارزش هر کسی به میزان دانایی و تخصصی اوست تعداد سوالات : تستی : ۳۰ تشریحی : ۰ زمان آزمون (دقیقه) : تستی : ۸۰ تشریحی : ۰ سری سوال : یک ۱
عنوان درس : نظریه گراف و کاربردهای آن رشته تحصیلی /کد درس : مهندسی فناوری اطلاعات، مهندسی فناوری اطلاعات (چند بخشی )، مهندسی کامپیوتر-نرم افزار(چند بخشی )، علوم کامپیوتر(چند بخشی )، مهندسی کامپیوتر (سخت افزار) چند بخشی ۱۱۱۱۰۸۱ -، مهندسی کامپیوتر(نرم افزار) ۱۱۱۱۰۹۸
۱- کدام جفت گراف های زیر یکریخت نیستند؟
※ ত্ৰি । :
۲- فرض کنید G یک گراف ساده با Il راسی باشد. اگر G دارای ۵۶ یال و "G دارای ۸۰ یال باشد، Il چند است؟
\ १ . ि \ N . Yo \r Y \ Y . )
۳- گراف همبند و ساده G دارای ۳۰ یالی است. بیشترین مقداری که Il می تواند داشته باشد چقدر است؟
* y . * ו. ץץ" ༈ ད . ད་ 所人.1
۴- کدام یک از گراف های زیر، گراف پترسن نیست؟ Ço 。ャ ... ) . Y. o . Y.
い・い・ハ・Y・)%めY
نیمسال دوم ۹۱-۱۳۹۰ صفحه ۱ از ۸
***
. . .
: کارشناسی --- - - - டிய கள்: مرکز آزمون و سنجش حضرت علی(ع): ارزش هر کسی به میزان دانایی و تخصصی اوست تعداد سوالات : تستی : ۳۰ تشریحی : ۰ زمان آزمون (دقیقه) : تستی : ۸۰ تشریحی : ۰ سری سوال : ۱ یک
عنوان درس : نظریه گراف و کاربردهای آن رشته تحصیلی /کد درس : مهندسی فناوری اطلاعات، مهندسی فناوری اطلاعات (چند بخشی )، مهندسی کامپیوتر-نرم افزار(چند بخشی )، علوم کامپیوتر(چند بخشی )، مهندسی کامپیوتر (سخت افزار) چند بخشی ۱۱۱۱۰۸۱ -، مهندسی کامپیوتر(نرم افزار) ۱۱۱۱۰۹۸
۵- کمر گراف دو K چند است؟
* : * z . Y 人.Y ャ.い
۶- گراف K n دارای ۱۶ یال است و n کm، اعداد IT1 و Il به ترتیب (از چپ به راست) چند باشند تا این گراف اویلری
باشد ولی همیلتونی نباشد؟ 人3人 Y 人乡Y·W t v , * ۴. چنین اعدادی وجود ندارند.
۷- به یال های گراف G اعداد ۱+ و ۱- را نسبت داده ایم، مجموع اعداد یال های واقع بر هر راسی برابر ۱+ می شود. گراف G کدام یک از گراف های زیر می تواند باشد؟
to : « 。ャ ... ) K2.98 Kaogo Ко, Коо
—A )°E (G برابر خواهد بود
2 اکر G یک گراف ساده باشد و V (G) = n و * = (P(G باشد. آنه
با:
. Y. . Y. 。ャ ... )
n° 4 4 4 4
۹- کدام یک از دنباله های زیر گرافیکی است؟
(2,2,2,1,1) . * (7,5,4,3,2,1,1,1) . " (7,6,5,4,3,3,2) Y (6,6,5,4,3,3,1) .) ۱۰ - چند مسیر به طول ۴ در گراف , K وجود دارد؟
4! . . 71 . x. Y%・.Y Y NY . . \ ۱۱- حداقل تعداد رأس های غیر برشی در یک گراف همبند با حداقل دو رأس برابر است با:
* : * * . w ャ.Y \ . )
صفحه ۲ از ۸
ᏉᎵᎸ•-ᎸᏉ نیمسال دوم い・い・ハ・Y・)%めY
***
. . .
= دانشگاه پیام نور کارشناسی مرکز آزمون و سنجش
حضرت علی(ع): ارزش هر کسی به میزان دانایی و تخصصی اوست
تعداد سوالات : تستی : ۳۰ تشریحی : ۰ زمان آزمون (دقیقه) : تستی : ۸۰ تشریحی : ۰ سری سوال : ۱ یک عنوان درس : نظریه گراف و کاربردهای آن
رشته تحصیلی /کد درس : مهندسی فناوری اطلاعات، مهندسی فناوری اطلاعات (چند بخشی )، مهندسی کامپیوتر-نرم افزار(چند بخشی )، علوم کامپیوتر(چند بخشی )، مهندسی کامپیوتر (سخت افزار) چند بخشی ۱۱۱۱۰۸۱ -، مهندسی کامپیوتر(نرم افزار) ۱۱۱۱۰۹۸
۱۲- کدام یک از موارد زیر، صحیح است؟ مورد اول: یک گراف با حداقل سه رآس ۲- همبند است اگر و تنها اگر هر دو رآس از آن گراف در یک دور مشترک قرار داشته باشند.
مورد دوم: یک گراف با حداقل سه رأس ۲- همبند است اگر و تنها اگر هر دو یال از آن گراف در یک دور مشترک قرار داشته باشند.
مورد سوم: یک گراف با حداقل سه رأس ۲- همبند است اگر و تنها اگر هر رأس و هر یال از آن گراف در یک دور مشترک قرار داشته باشند.
۱. تنها موارد اول و دوم ۲. تنها موارد دوم و سوم ۳. تنها موارد اول و سوم ۴. موارد اول و دوم و سوم ----- یک درخت باشد، آنگاه T ۱۳- اگر ۱. حداکثر دو راس آویخته دارد. ۲. حداکثر یک جورسازی کامل دارد.
۳. منتظم نیست. f حتماً راسی با درجه زوج دارد.
۱۴- تعداد درخت های فراگیر گراف مقابل چند است؟ (گراف را برچسب دار فرض نمایید.)
\ Y t \ . . Y. A Y 人.1
۱۵- در بین همه گراف های ساده (غیر یکریخت) ۴ راسی، چند تا همبند هستند؟
人.* A . Y. 2 . Y * . ) ۱۶- کدام یک از موارد زیر، همواره صحیح است؟
مورد اول: مکمل هر درخت، همواره یک درخت است.
مورد دوم: مکمل هر درخت، همواره همبند است. مورد سوم: درخت های خود مکمل با هر تعداد رأس وجود دارند.
۱. تنها موارد اول و دوم ۲. موارد اول و دوم و سوم ۳. تنها مورد سوم ۴. هیچکدام از موارد
い・い・ハ・Y・)%めY
نیمسال دوم ۹۱-۱۳۹۰ صفحه ۳ از ۸

***
. . .
: کارشناسی --- - - - டிய கள்: مرکز آزمون و سنجش حضرت علی(ع): ارزش هر کسی به میزان دانایی و تخصصی اوست تعداد سوالات : تستی : ۳۰ تشریحی : ۰ زمان آزمون (دقیقه) : تستی : ۸۰ تشریحی : ۰ سری سوال : ۱ یک
عنوان درس : نظریه گراف و کاربردهای آن رشته تحصیلی /کد درس : مهندسی فناوری اطلاعات، مهندسی فناوری اطلاعات (چند بخشی )، مهندسی کامپیوتر-نرم افزار(چند بخشی )، علوم کامپیوتر(چند بخشی )، مهندسی کامپیوتر (سخت افزار) چند بخشی ۱۱۱۱۰۸۱ -، مهندسی کامپیوتر(نرم افزار) ۱۱۱۱۰۹۸
۱۷- با توجه به درخت رو به رو وزن راس (۱ کدام است؟
V2 v4 V5 - V1 I W3
A t \ Y . Y. \ . . Y \ \ . )
۱۸- حداکثر تعداد یال های یک گراف ساده با P مؤلفه برابر است با:
(n+p)(n–p-1) t (n+p)(n+p-1) Y (n-p)(n–p +1) Y (n-p)(n–p-1) . ) 2 2 2 2
۱۹- کدام گزینه درباره گراف مقابل صحیح است؟
۱. اویلری است. ۲. همیلتونی است. ۳. نامسطح است. ۴. دوبخشی است.
い・い・ハ・Y・)%めY
نیمسال دوم ۹۱-۱۳۹۰ صفحه ۴ از ۸

***