مقاله خواص متریک مکعب های فیبوناتچی و لوکاس

بخشی از مقاله

چکیده

یک مکعب فیبوناتچی -nبعدی گرافی است که رئوس آن رشته^های دودویی به طول n هستند بهKطوری_که در آن_ها هیچ دو ١ متوالی وجود ندارند. همچنین، رئوس مکعب لوکاس -nبعدی رشته^های دودویی هستند که علاوه بر این خاصیت، در مکان^های ابتدایی و انتهایی خود بهÁطور همزمان ١ ندارند. قاعده مجاورت بین رئوس این دو نوع مکعب همانند ابرمکعب_ها است. بنابراین، دو راس با هم مجاورند، اگروتنهااگر فاصله همینگ آن_ها ١ باشد. کاربرد بسیار زیاد و مهم این مکعب_ها در علوم مختلف، به_خصوص در علم کامپیوتر، ما را بر آن داشت که خواص و ویژگی^های این مکعب_ها را مورد بررسی قرار دهیم.  به دلیل گستردگی مطالب، ویژگی^های جبری و نیز ویژگی^های ترکیبیاتی آن_ها را در مقاله^های قبلی مطرح کردیم و در این_جا تنها به بررسی ویژگی^های متریک این مکعب_ها میyپردازیم.

واژه های کلیدی: ابرمکعب، مکعب فیبوناتچی، مکعب لوکاس

١    مقدمه

در این مقاله، پس از ارائه تعریف دقیق از مکعب^های فیبوناتچی و لوکاس و همچنین بیان مختصری از کاربردها و اهمیت آن^ها، مفاهیم و قضایای مورد نیاز را مطرح کرده و سپس خواص و ویژگی^های متریک آن_ها را بیان میNکنیم. لازم به ذکر است که برخی از خصوصیات مکعب^های فیبوناتچی در ]۵١[ جمع_آوری شده_اند. ما در این_جا علاوه بر طرح خصوصیات بیشتری از مکعب^های فیبوناتچی، ویژگی^های مکعب^های لوکاس را نیز بررسی کرده_ایم. در سراسر این مقاله، منظور از گراف، گراف ساده - بدون طوقه و یال چندگانه - ، همبند و غیرجهت]دار است. فاصله بین دو راس u و v در گراف G، طول کوتاه_ترین مسیری است که این دو راس را به یکدیگر متصل می_کند. با در نظر گرفتن هر دو راس دل_خواه از گراف G، بزرگ_ترین فاصله موجود را قطر گراف می_گوییم. منظور از خروج از مرکز راس v از گراف G، طول بیشترین فاصله بین v و هر راس دیگر ازگراف است.

شعاع گراف G که با rad - G - نمایش داده می_شود، کوچک_ترین خروج از مرکز بین رئوس گراف است. مجموعه تمام رئوس گراف Gبا کوچک_ترین خروج از مرکز را مرکز گراف نامیده و با Z - G - نمایش میNدهیم. دنباله_ای از حروف و اعداد به شکل ___xn ٢x١x را یک رشته به طول می_nنامیم. درصورتی_که هر یک از _ i _ n - ١xi - ها، ٠ و یا ١باشند، آن^گاه این رشته را یک رشته دودوییمی_گوییم. فاصله همینگ بین دو رشته، تعداد مکان_هایی است که آن_ها با هم در اختلاف هستند. منظور از یک ابرمکعب -nبعدی گرافی است که رئوس آن رشته^های دودویی به طول n هستند و در آن دو راس با هم مجاورند، هرگاه فاصله همینگ آن_ها برابر با ١ باشد. ابرمکعب -nبعدی را با Qnنمایش میNدهیم. اگر هر سه راس دل_خواه u، v و w از گراف G دارای راس میانی - راسی مانند qکه به کوتاه_ترین مسیر بین هر دو راس از u، v و wتعلق دارد - باشند، آن^گاه G را یک گراف میانیمی_نامیم. ثابت میÁشود که

ابرمکعب_ها گراف^های میانی هستند ]١٣، ٢٢.[ زیرگرافی از G که فاصله بین هر دو راس از آن با فاصله بین همان دو راس از گراف G برابر است، را زیرگراف طول-پایامی_گوییم. منظور از یک زیرگراف محدب از، Gزیرگرافی است که با در نظر گرفتن هر دو راس دل_خواه از آن، تمام کوتاه_gترین مسیرهای ممکن بین آن دو راس در G، در آن زیرگراف نیز باشند. یک زیرگراف طول-پایا از ابرمکعب را مکعب جزییم¶نامیم ]۶، ١٣.[ گراف^های میانی، مکعب^های جزیی هستند ]١٣.[ اگر G یک گراف باشد، زیرمجموعه D از مجموعه رئوس G را یک مجموعه غالبمی_نامیم، اگر هر راس در V - G - n D حداقل با یکی از رئوس D مجاور باشد.  عدد غالب که با g - G - نمایش داده می_شود، کوچک_ترین اندازه مجموعه غالب در Gاست. عدد ٢-بستهzبندی، متغیری از گراف، بسیار شبیه به عدد غالب است. مجموعه X _ V - G - را ٢-بسته_بندی می_نامیم، اگر برای هر دو راس متمایز u و v از X، ٢ .d - u; v - >عدد ٢-بسته_بندی - G - بزرگ_rترین اندازه ٢-بسته_بندی^های G است. ایمریچ١ و همکارانش در ]۴١[ ثابت کردهºاند که برای هر گراف G، .g - G - _ r - G - یک مجموعه راسی مستقل از گراف، Gزیرمجموعه_ای ار رئوس آن است بهKطوری_که هیچ دو عضو از آن یالی از Gنباشد. عدد استقلال راسی و یا بهÁطور خلاصه، عدد استقلال گراف Gاندازه بزرگ_ترین مجموعه راسی مستقل در آن است. این عدد را با a - G - نمایش میNدهیم. بهÁطور مشابه، یک مجموعه یالی مستقل در گراف، زیرمجموعه_Gای از یال^های آن است بهKطوری_که هیچ دو یال از آن راس مشترک نداشته باشند.

عدد استقلال یالی گراف G، اندازه بزرگ_ترین مجموعه یالی مستقل از آن است. این عدد را با b - G - نمایش میNدهیم. یک مسیر همیلتنی، مسیری است که از تمام رئوس گراف دقیقا یک بار می}گذرد. یک دور همیلتنی، مسیری همیلتنی است که دور باشد. گرافی که یک دور همیلتنی دارد را یک گراف همیلتنیمی_نامیم. توجه کنید که ابرمکعب_ها مسیر همیلتنی و نیز دور همیلتنی دارند. عدد رنگی گراف G که با G - نمایش - c داده می_شود، کوچک _ترین تعداد رنگ_هایی است که می_توان بهNوسیله آن رئوس G را چنان رنگ کرد که هیچ دو راس مجاور رنگ یکسان نداشته باشند. اندیس رنگی و یا همان عدد رنگی یالی، کمترین تعداد رنگ_ هایی است که بتوان بهNوسیله آن_ها یال^های گراف G را چنان رنگ کرد که هیچ دو یال مجاوری همºرنگ نباشند. این عدد با c′ - G - نمایش داده می_شود. رابطه دیوکویچ-وینکلر٢ که بانمایشQ داده می_شود، روی مجموعه یال^های گراف به_صورت زیر تعریف میÁشود ]۶، ٢٨:[

یال^های e = xy و f = uv از G در رابطه Qهستند و می_نویسیم eQ f، ا گر و تنها ا گر d - x; u - + d - y; v - ̸= d - x; v - + d - y; v - : Qانعکاسی و تقارنی است، اما لزوما متعدی نیست. بستارمتعدی این رابطه که به_صورت کوچک_ترین رابطه متعدی شامل Qتعریف می_شود، را با Q_نمایش میNدهیم. ا گر Gدوری با طول زوج باشد، آن^ گاه Qشامل تمام زوج یال^های مقابل هم می‡باشد. بنابراین، Q_ دارای nکلاس هم_ارزی است و در واقع در این حالت :Q = Q_ از طرف دیگر، هر یال از یک دور با طول فرد با دو یال مقابل آن در رابطه Q است. در این حالت Q_فقط یک کلاس هم_ارزی دارد. در ادامه به بیان برخی نتایج مهم از این رابطه میyپردازیم:

قضیه ١.١. - فصل ٢ از ]١٣ - [ فرض کنید Pیکی از کوتاه_ترین مسیرهای موجود در گراف G است. دراین}صورت، هیچ دو یال متمایز از P در رابطه Q نیستند. فرض کنید uv یالی از گراف G است. Wuv مجموعه تمام رئوسی از G است که به uنزدیک_ترند تا به .v به بیان ر یاضی، - ١.١ -     Wuv = fwjw 2 G; dG - w; u - < dG - w; v - g: در گراف^های دوبخشی، مجموعه^های Wuv و Wvu افرازی برای V - G - هستند. قضیه ١.٢. ] - ١٣ - [ فرض کنید e = uv یالی از گراف همبند و دوبخشی G است و دراین}صورت، GnFuv دقیقا دو مولفه همبند دارد که از مجموعه رئوس Wuv و Wvuالقا میºشوند.