شنبه ۲۵ خرداد ۱۳۹۲ | 15:31 | آرش عبدی -
یک درخت از شرایط زیر پیروی می کند.
اگر یک جنگل با n راس باشد آن گاه از شرایط زیر پیروی می کند:
در شکل درختی با 6 راس و 5 یال وجود دارد مقدار یالها برابر 5 = 1- 6 است. و بین دو راس 2 و 6 دقیقاً یک مسیر وجود دارد که عبارت است از 6-5-4-2
درخت مولد گراف مانند G بزرگترین گراف درختی مانند T در G است که با افزودن یک یال از درخت بودن خارج می شود و واضح
- در آن هیچ مدار یا حلقه ای موجود نیست.
- درخت یک گراف همبند است.
- با حذف یک یال از درخت، دیگر آن گراف یک درخت نخواهد بود.
- هر دو راس در یک درحت بوسیله مسیر منحصر به فرد به هم متصل می شوند.
اگر یک جنگل با 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 راس با درجات 
می توان ساخت برابر مقدار زیر است:
می توان ساخت برابر مقدار زیر است: در نظریه گراف، گراف شاه(King's Graph) گرافی است که همه حرکات مجاز مهره شاه را در یک صفحه شطرنجنشان می
دهد که در آن هر راس یک خانه از صفحه شطرنج را نشان میدهد و هر راس نشان دهنده یک حرکت مجاز به خانه دیگر است.
به صورت کلی تر و دقیق تر یک گراف شاه m×n یک گراف با mn راس(از مرتبه mn) است که در آن هر راس نمایانگر یک خانه از
یک صفحه شطرنج m×n است و هر یال عبارت است از حرکت مجازه که شاه می تواند از آن راس(که در اینجا یک خانه شطرنج
است) به راس دیگر انجام دهد. تعداد یالها در یک گراف شاه n×n عبارت است از (2n(2n+1، بنابراین برای ...,n=1,2,3 مقاریر
اولیه عبارتند از: 6و20و42و72و110و...
آرش عبدی
هدف من از ایجاد این وبلاگ ارائه مطالب و نکته های درسی مهم و قرار دادن کتابها و جزوات دانشگاهیه