تست های فصل اول گسسته ( گراف ) کنکور سراسری و آزاد

تست های

فصل اول گسسته ( گراف )

کنکور سراسری و آزاد  

ادامه نوشته

گراف

اصل درخت(گراف)

در نظریه گراف، یک درخت گرافی است که هر دو راس آن بوسیله دقیقاً یک یال به هم متصل شده اند، یک جنگل گرافی است که دو راس آن با بیشتر از یک راس به هم متصل اند. یک جنگل در واقع از اتصال، مجموعه ای از درخت ها به وجود می آید.

تعریف ها:

یک درخت از شرایط زیر پیروی می کند.

• در آن هیچ مدار یا حلقه ای موجود نیست.
• درخت یک گراف همبند است.
• با حذف یک یال از درخت، دیگر آن گراف یک درخت نخواهد بود.
• هر دو راس در یک درحت بوسیله مسیر منحصر به فرد به هم متصل می شوند.

اگر یک جنگل با n راس باشد آن گاه از شرایط زیر پیروی می کند:

• T یک درخت است.
• T مداری ندارد و n-1 یال دارد.
• T همبند است و n-1 یال دارد.
• هر دو راس T با مسیر منحصر به فرد به هم متصل می شوند.
• T مداری ندارد و با افزودن یگ یال جدید دقیقاً یک مدار بوجود می آید.

مثال:

در شکل درختی با 6 راس و 5 یال وجود دارد مقدار یالها برابر 5 = 1- 6 است. و بین دو راس 2 و 6 دقیقاً یک مسیر وجود دارد که عبارت است از 6-5-4-2

بیشتر بدانیم:

درخت مولد گراف مانند G بزرگترین گراف درختی مانند T در G است که با افزودن یک یال از درخت بودن خارج می شود و واضح است اگر یک گراف n راس و m یال داشته باشد آن گاه درخت مولد n-1 یال داشته و باید m >= n-1 باشد.
تعداد درخت های مولد متمایز برای گراف کامل با n راس برابر است. این قضیه به قضیه کایلی معروف است.
تعداد درخت هایی که با n راس با درجات می توان ساخت برابر مقدار زیر است:

گراف شاه

در نظریه گراف، گراف شاه(King's Graph) گرافی است که همه حرکات مجاز مهره شاه را در یک صفحه شطرنج نشان می دهد که در آن هر راس یک خانه از صفحه شطرنج را نشان میدهد و هر راس نشان دهنده یک حرکت مجاز به خانه دیگر است.

به صورت کلی تر و دقیق تر یک گراف شاه m×n یک گراف با mn راس(از مرتبه mn) است که در آن هر راس نمایانگر یک خانه از یک صفحه شطرنج m×n است و هر یال عبارت است از حرکت مجازه که شاه می تواند از آن راس(که در اینجا یک خانه شطرنج است) به راس دیگر انجام دهد. تعداد یالها در یک گراف شاه n×n عبارت است از (2n(2n+1، بنابراین برای ...,n=1,2,3 مقاریر اولیه عبارتند از: 6و20و42و72و110و...

نظریه گراف

نظریه گراف
نظریه گراف شاخه‌ای از ریاضیات است که دربارهٔ گراف ها بحث می‌کند. به صورت شهودی، گراف نموداری است، شامل تعدادی رأس، که با یال‌هایی‌ به هم وصل شده‌اند.

نمایش تصویری یک گراف

---

تعریف
تعریف دقیق‌تر گراف به این صورت است، که گراف مجموعه‌ای از رأس‌ها است، که توسط خانواده‌ای از زوج‌های مرتب که همان یال‌ها هستند به هم مربوط شده‌اند.

یال‌ها بر دو نوع ساده و جهت دار هستند، که هر کدام در جای خود کاربردهای بسیاری دارد. مثلاً اگر صرفاً اتصال دو نقطه -مانند اتصال تهران و زنجان با کمک آزادراه- مد نظر شما باشد، کافیست آن دو شهر را با دو نقطه نمایش داده، و اتوبان مزبور را با یالی ساده نمایش دهید. اما اگر بین دو شهر جاده‌ای یکطرفه وجود داشته باشد آنگاه لازمست تا شما با قرار دادن یالی جهت دار مسیر حرکت را در آن جاده مشخص کنید.

آغاز نظریهٔ گراف به سدهٔ هجدهم بر می‌گردد. اولر ریاضیدان بزرگ مفهوم گراف را برای حل مسئله پل‌های کونیگسبرگ ابداع کرد اما رشد و پویایی این نظریه عمدتاً مربوط به نیم سدهٔ اخیر و با رشد علم انفورماتیک بوده‌است.

مهم‌ترین کاربرد گراف، مدل‌سازی پدیده‌های گوناگون و بررسی بر روی آنهاست. با گراف می‌توان به راحتی یک نقشه بسیار بزرگ یا شبکه‌ای عظیم را در درون یک ماتریس به نام ماتریس وقوع گراف ذخیره کرد و یا الگوریتمهای‌ مناسب مانند الگوریتم دایسترا یا الگوریتم کروسکال و ... را بر روی آن اعمال نمود.

یکی از قسمت‌های پرکاربرد نظریهٔ گراف، گراف مسطح است که به بررسی گراف‌هایی می‌پردازد که می‌توان آن‌ها را به نحوی روی صفحه کشید که یال‌ها جز در محل راس‌ها یکدیگر را قطع نکنند. این نوع گراف در ساخت جاده‌ها و حل مساله کلاسیک و قدیمی سه خانه و سه چاه آب به کار می‌رود.

نظریه گراف یکی از پرکاربردترین نظریه‌ها در شاخه‌های مختلف علوم مهندسی (مانند عمران)، باستان‌شناسی (کشف محدوده یک تمدن) و ... است.

روابط میان راس های یک گراف را می‌توان با کمک ماتریس بیان کرد .


انواع گراف
گراف ساده: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از تمام زیرمجموعه‌های دو عضوی V می‌باشد. اعضای V را رأسهای G و اعضای E را یالهای G مینامیم. به بیان ساده تر بین دو رأس یک گراف ساده حداکثر یک یال وجود دارد.

گراف چندگانه: هرگاه بین دو رأس متمایز از یک گراف بیش از یک یال وجود داشته باشد، آن را یک گراف چند گانه می‌گوییم.

گراف جهت دار: هر گراف G زوج مرتبی مانند (V,E) است که در آن V مجموعه‌ای متناهی و ناتهی است و E زیرمجموعه‌ای از مجموعهٔ تمام زوج مرتب‌های متشکل از اعضای V است.

گراف مسطح: گراف مسطح گرافی است که می‌توان آن را در یک صفحه محاط کرد به گونه ای که یال هایش یکدیگر را تنها در راس ها قطع کنند.