PDA

توجه ! این یک نسخه آرشیو شده میباشد و در این حالت شما عکسی را مشاهده نمیکنید برای مشاهده کامل متن و عکسها بر روی لینک مقابل کلیک کنید : گراف شاه



shirin71
08-04-2011, 10:55 PM
گراف شاه


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




http://minag.persiangig.com/image/KingsGraph_1000.gif

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