بخشی از مقاله
دراین مقاله ابتدا نشان می دهیم که ماتریس مجاورت گراف کامل به ازای ١ k تصادفی دوگانه متقارن -kتعمیم یافته می باشد وسپس نشان می دهیم ماتریس مجاورت گراف-1منتظم تصادفی دوگانه متقارن است وسپس با مشخص کردن همه ماتریس های تصادفی دوگانه متقارن که توسط طیف شان در ∆snمشخص می شوند، ماتریس مجاورت گراف های منتظم را به دست می آور یم و در انتها نتایج به دست آمده را بیان می کنیم.
واژه های کلیدی: مساله مقدار ویژه معکوس،ماتریس تصادفی دوگانه، گراف کامل، گراف -k منتظم، ماتریس مجاورت
١مقدمه
ماتریس مجاورت گراف ساده G را با A - G - نمایش می دهیم که ماتریس - - 0,1 - متقارن نامنفی است و مقادیر ویژه :::; n ;١ که طیف G می باشد را - G - می نامیم و :::; ng ; ١ - G - = f گراف G صحیح نامیده می شود ا گرتمام مقادیر ویژه آن اعدادصحیح باشند و ا گر A - G - دوری باشد آنگاه دوری نامیده می شود. درمجموع گراف G ، -k منتظم نامیده می شود ا گر درجه هرراس آن k باشد. گراف ا کیدا منتظم G با پارامتر های - ; ; ; - ، -kمنتظم است که کامل نمی باشد و در دوشرط زیرصدق می کنند:.١برای هر زوج ازرئوس مجاور، رئوس مجاور در هر دو وجود داشته باشد.برای هر زوج از رئوس غیرمجاور،رئوس مجاور درهردو وجود داشته باشند.
گراف کامل روی n راس که هرراس به رئوس دیگرمتصل است را با kn نشان می دهیم. علاوه بر این در گراف کامل دو قسمتی ٢;n١kn ، رئوس به دو زیر مجموعه ١v و ٢v از هریک از عناصر ١n و ٢n تقسیم می شود ودو راس مجاور هستندا گر و تنها ا گریکی در ١v باشد و دیگری در ٢v باشد. دوگراف ایزومرفیک گفته می شود ا گر و تنها ا گرماتریس مجاورت آنها به طورجایگشتی متشابه باشد.دوگراف هم طیف گفته می شود ا گر طیف مشابه داشته باشند وگراف G ، DS گفته می شود ا گر هر گراف H که هم طیف G است ایزومرفیک G باشد. در کل مساله مشخص کردن این که آیا گراف G ، DS هست یا نه، هنوز بازاست. در این مقاله به بحث در باره اینکه گراف منتظم DS است یا نه ،باتوجه به رابطه آن با مسئله مشخص کردن همه ماتریس های تصادفی دوگانه متقارن که DS در ∆sn است، می پردازیم. اما ابتدا یادآوری می کنیم که ا گر G گراف -k منتظم روی n راس باشد آنگاه شعاع طیفی A - G - مساوی K ومقدار ویژه G مربوط به بردار ویژه واحد - en - برابر k است.
٢ رابطه بین ماتریس مجاورت گراف و ماتریس تصادفی دوگانه
تعریف ٢. ١. فرض کنید Ωsn - k - مجموعه همه ماتریس های متقارن نامنفی از مرتبه n n باشد که مجموع هرسطر و ستون آن مساوی k باشد و _n - k - نمایش زیر مجموعه Ωsn - k - متشکل از همه ماتریس های - - 0.1 - که k ، ١ در هر سطر و ستون دارد و n - k - ٠_ مجموعه عناصر _n - k - می باشد که اثر صفر دارد.
قضیه ٢ . ٢. هرماتریس مجاورت گراف کامل kn ، - ٢ - n تصادفی دوگانه -n تعمیم یافته می باشد.
قضیه ٢ . ٣. هر ماتریس مجاورت گراف -1 منتظم تصادفی دو گانه است.
قضیه ٢ . ۴. n - k - ٠A 2 ا گرو تنها ا گر A ماتریس مجاورت گراف های -k منتظم که n راس و k یال دارد، می باشد.
اثبات. ابتدا فرض کنید A ماتریس مجاورت گراف منتظم که n راس و k یال دارد، باشد.آنگاه واضح است که A ماتریس متقارن نامنفی از مرتبه n n می باشد.ا گرمجموع هر سطر و ستون ان مساوی k است و دارای اثر صفر می باشد پس n - k - ٠. A 2 برعکس فرض کنید n - k - ٠A 2 آنگاه A ماتریس مجاورت گراف منتظم که n راس و n یال دارد ،می باشد.
قضیه ٢ . ۵. A 2 sn - k - ا گرو تنها ا گر k A١ عنصر ∆sn باشد.
نتیجه ٢ . ۶. A 2 n - k - ،DS در Ωsn - k - است ا گر و تنها ا گر k A١ ، DS در ∆sn است.
٣ حل مساله مقدار ویژه معکوس ماتریس مجاورت با استفاده از ماتریس تصادفی دوگانه
قضیه ٣ . ١. گراف های -1منتظم DSهستند.
اثبات. فرض کنید A ماتریس مجاورت گراف -1 منتظم باشدآنگاه چون A ماتریس جایگشتی تحویل ناپذیر است، به ازای ماتریس معکوس پذیر Xداریم AX = B١X و B تصادفی دوگانه است و همچنین B تحویل ناپذیر می باشد و همه مقادیر ویژه آن قدرمطلق ١ دارند بنابراین A و B هم طیف می باشند و همچنین به طور جایگشتی متشابه هستند و لذا A و B ایزومرفیک بوده و بنابراین A ، DC می باشد.
مثال ٣. ٢. طیف g١ ;١f گراف -1منتظم مرتبه ٢ را مشخص می کند و همچنین g١ ;١ ;١ ;١f گراف -1 منتظم مرتبه ۴ را مشخص می کند .
قضیه ٣ . ٣. هرگراف کامل kn ، DS است.اثبات. داریم k A - kn - = cn١ آنگاه چون و برای هر ماتریس وارون پذیر X به طوری که CnX١X تصادفی دوگانه متقان باشد، ما به دست می آور یمکه سمت چپ ماتریس نامنفی است که مجموع سطر و ستون مساوی ١ +١ می باشد بنابراین تصادفی دوگانه متقارن است و چون JnX = Jn١X لذا A - kn - ، DS است.
مثال ٣ . ۴. طیف g١:::; ;١ ; - ١ f - n گراف کامل Kn را مشخص می کند.
قضیه ٣ . ۵. ناحیه غیرمشترک گرافهای کامل DS است.اثبات. داریم k A - kn - = cn١ به استقرا اثبات می کنیم ابتدا نشان می دهیم cn cn ، DSدر n٢∆ است. ا گر n٢z 2 ∆متشابه cn cn باشد آن گاه به وضوح طیف z برابر - ١١:::; n ;١١n ;١ ;١ - می باشدچون z تحویل ناپذیر است و مقدار ویژه ١ دوبار تکرار می شود آن گاه z به طور جایگشتی متشابه مجموع مستقیم دو ماتریس تصادفی دوگانه B و C است امااثرهای وصفر هستند به طوری که در صورت لزوم طیف و مشابه و مساوی ١n ١n١می باشد باتوجه به این که ا گر JnX١B = X تصادفی دوگانه باشدآنگاه وجود دارد Y 2 ∆n به طوری که JnY١B = Y و از اینروB = C = Cn و بنابراین این براساس استقرا روی n برای هر عدد صحیح مثبت :::; nk ;١n ماتریس ::: cnk ١cn در +:::+nk١∆n ، DS است.
۴ نتایج اصلی
١kn;n . ، DS هست.اثبات. نتیجه قضیه - ٢ . ٢ - ، - ٣ . ١ - :
ابتدا ثابت می کنیم که I و J در n٢∆ ، DSهستند اگر وجود داشته باشد n٢Z 2 ∆ که متشابه J هست ، آنگاه بوضوح طیف Z برابر n٢R - آنگاه Z بطور جایگشتی متشابه ماتریس به شکل ] D ٠که D 2 ∆n می باشد به طوری که DDT 2 ∆sn و مقادیر ویژه آن - ٠ ;::: ;٠ ;١ - وبنابراین DDT متشابه Jn است آنگاه، DDT = Jn و چونآنگاه D = Jn و بنابراین Z = J حالا فرض می کنیم که n٢S 2 ∆ متشابه I است آنگاه S طیف - ١:::; ;١ ;١ ;::: ;١ - را دارد و بنابراین S بطور جایگشتی متشابه ٢ ::: c ٢n - c مرتبه - می باشد ولذا Iو S بطور جایگشتی متشابه هستند چون I١ ١ J n ١C = nn آنگاه C در n٢∆ ، DS می باشدبا استفاده از گراف های منظم هم طیف ه ایزومرفیک نیستند می توان ماتریس تصادفی دو گانه که در ∆sn، DS نیستند را به دست آورد.
٣. اگر G گراف -k منظم باشد که DS می باشد آنگاه k A - G - ١ ، DS می باشد.
