بخشی از مقاله
چکیده
چند جمله ای هوسیای گراف G، - H - G:l مجموع روی l به توان d - u; v - فاصله دو راس به ازای تمام رئوس در گراف م باشد. در این مقاله این چند جمله ای برای گراف هانوی با ۴ میله، گراف هانوی با ی قرص ،k میله وبرخ دی ر از شاخص های توپولوژی گراف Hnk محاسبه شده است.
واژه های کلیدی: گراف هانوی، چند جمله ای هوسیا، شاخص های توپولوژی .
١مقدمه
فرض کنید G ی گراف همبند و V - G - مجموعه رئوس آن باشد. فاصله هر دو رأس را باd - vi; v j - ، درجه هر رأس را با deg - vi - و چند جمله ای هاسویا با - H - G; l، شاخص وینر با W - G - ، شاخص خروج از مرکز با x c - G - ، چند جمله ای خروج از مرکز با ECP - G - ،شاخص شولتز با S - G - و شاخص شولتز تعمیم یافته با S_ - G - نمایش داده م شود. در]٢[ نحوه محاسبه چند جمله ای هاسویای گراف هانوی با ۳ میله آمده است. در این مقاله چند جمله ای هوسیا برای گراف هانوی با k میله و ی دیس ، چند جمله ای هوسیا برای١٧٢گراف هانوی با ۴ میله و n دیس ، شاخص شولتز و شاخص شولتز تعمیم یافته برای گراف هانوی با k میله و n دیس آورده شده است.
٢گراف هانوی
معمای برج هانوی در سال ١٨٨٣ توسط ریاضیدان فرانسوی ادوارد لوکاس طرح شد و بعد از آن بعنوان ی مثال و مسئله مهم در ریاضیات گسسته مورد استفاده قرار گرفت. ]٢[ این مسأله شامل n صفحه ی سان با شعاع های متمایز است که روی ی میله به ترتیب شعاع روی هم قرار گرفته اند. اگر شعاع بزرگترین صفحه ۱d باشد آنگاه > ___ ۲> d ۱d بنابراین در پایین ترین قسمت میله صفحه با شعاع ۱d بعد صفجه با شعاع ۲d و ___ قرار گرفته اند.مسأله به این صورت است که باید صفحه ها از این میله به میله دی ر منتقل شود به طوری که روی میله دوم باز هم بر اساس ترتیب شعاع ها قرار گیرند و برای این امر از میله سوم استفاده میشود.
اگر میله ها را به عنوان رأس وn حرکت صفحه ها را یال در نظر ب یریم،گراف هانوی حاصل م شود کهn۳ رأس و - ۱ ۳ - ۳ یال دارد. این مسأله را میتوان با ۴ میله طرح کرد که در این حالت گراف هانوی دارایn ۴ رأس و - ۱ ۱ n۴_۳ - ۴ یال میباشد.همچنین در حالت کل گراف هانوی با n دیس و k میله دارای kn راس و - ۱ ۱ kn۳ - ۲k یال میباشد. برای هر عدد صحیح n گراف هانوی یگراف همیلتون می باشد که دارای قطر - ۱ n۲ - - ۳ میله - ، - ۱ ۱n۲_۳ - - ۴ میله - و به طور کل۱ ۱ n۲ - ۲k - - k + میله - است و دقیقاً ۳ ، ۴ و k رأس از درجه ۲، - ۳n۳ - ، - ۴n۴ - و k - - kn رأس از درجه ۳ است.
٣ نتایج اصل
برای محاسبه چند جمله ای هوسیای گراف ۴Hn ابتدا مجموعه های زیر را تعریف م کنیم: