نمودار کاملاً منظم

توسط علی رضا نقش نیلچی | سه شنبه هجدهم خرداد ۱۴۰۰ | 6:29

نمودار پالی از سفارش 13، یک گراف به شدت به طور منظم با پارامترهای SRG (13،6،2،3).

خانواده های نمودار توسط اتومورفیسم آنها تعریف شده است
فاصله گذرا	→	فاصله منظم	←	به شدت منظم
↓
متقارن (قوس-انتقالی)	←	t -transitive ، t ≥ 2		کج-متقارن
↓
(در صورت اتصال) راس و لبه انتقالی	→	لبه انتقالی و منظم	→	لبه دار
↓		↓		↓
راس-انتقالی	→	منظم	→	(اگر دو بخشی باشد ) بی قاعده است
↑
نمودار کیلی	←	متقارن صفر		نامتقارن

در تئوری گراف ، یک گراف کاملاً منظم به شرح زیر تعریف شده است. بگذارید G = ( V ، E ) یک نمودار منظم با V رئوس و درجه k باشد . G گفته می شود که اگر عدد صحیح λ و μ نیز وجود داشته باشد ، به شدت منظم است که:

هر دو راس مجاور λ همسایه مشترک دارند.
هر دو راس غیر مجاور μ همسایه مشترک دارند.

گرافی از این نوع گاهی اوقات گفته می شود srg ( v ، k ، λ ، μ). نمودارهای کاملاً منظمی توسط راج چاندرا بوز در سال 1963 معرفی شد . [1]

برخی از نویسندگان ، نمودارهایی را که تعریف را به صورت پیش پا افتاده مطابقت می دهند ، شامل آن دسته از نمودارهایی که اتحاد جداگانه یک یا چند نمودار کامل با اندازه مساوی هستند ، [2] [3] و مکمل آنها ، نمودارهای کامل چند بخشی با مجموعه های مستقل با اندازه یکسان را حذف می کنند.

مکمل از SRG ( V ، K ، λ، μ) است نیز به شدت به طور منظم. این یک srg است ( v ، v − k −1 ، v −2−2 k + μ ، v −2 k + λ).

یک نمودار کاملاً منظم ، یک نمودار منظم با فاصله است که قطر 2 هر زمان μ غیر صفر باشد. هر زمان λ = 1 یک نمودار محلی خطی است .

فهرست

خصوصیات [ ویرایش ]

رابطه بین پارامترها [ ویرایش ]

چهار پارامتر در یک srg ( v ، k ، λ ، μ) مستقل نیستند و باید از رابطه زیر پیروی کنند:

$(vk-1) \ mu = k (k- \ lambda -1)$

رابطه فوق را می توان به راحتی از طریق یک استدلال شمارش به شرح زیر بدست آورد:

راسهای گراف را تصور کنید که در سه سطح قرار دارند. هر راس را به عنوان ریشه در سطح 0 انتخاب کنید. سپس k همسایه آن در سطح 1 قرار می گیرند و سایر رئوس در سطح 2 قرار دارند.
رئوس سطح 1 مستقیماً به ریشه متصل هستند ، از این رو باید λ دیگر همسایه مشترک با ریشه داشته باشند ، و این همسایه مشترک نیز باید در سطح 1 باشند. از آنجا که هر راس دارای درجه k است ، $k- \ لامبدا -1$ لبه های باقی مانده برای هر گره سطح 1 برای اتصال به گره های سطح 2 وجود دارد. بنابراین ، وجود دارد $k \ بار (k- \ lambda -1)$ لبه های بین سطح 1 و سطح 2.
رئوس سطح 2 مستقیماً به ریشه متصل نیستند ، از این رو باید همسایه μ مشترک با ریشه داشته باشند ، و این همسایگان مشترک باید همه در سطح 1 باشند. $(vk-1)$ رئوس در سطح 2 ، و هر یک به گره های μ در سطح 1 متصل می شوند ، بنابراین تعداد لبه ها بین سطح 1 و سطح 2 برابر است $(vk-1) \ بار \ mu$ .
با برابر کردن دو عبارت برای لبه ها بین سطح 1 و سطح 2 ، رابطه به شرح زیر است.

ماتریس همسایگی [ ویرایش ]

اجازه دهید I ماتریس هویت را نشان دهد و اجازه دهید J ماتریس همه یک نشان دهد ، هر دو ماتریس ترتیب v . ماتریس مجاورت از ارضا نمودار به شدت منظم دو معادله. اولین:

$AJ = JA = kJ ،$

که یک بیان مجدد پیش پاافتاده از الزام نظم است. این نشان می دهد که k یک مقدار ویژه از ماتریس مجاورت با بردار ویژه همه یک است. دوم یک معادله درجه دوم است ،

${\ displaystyle {A} ^ {2} = k {I} + \ lambda {A} + \ mu ({JIA})}$

که بیانگر یک نظم قوی است. عنصر IJ توریم از سمت چپ می دهد تعدادی از مسیرهای دو مرحله ای از I به J . اصطلاح اول RHS تعداد مسیرهای خود از i به i را می دهد ، یعنی k لبه های خارج و برگشت. اصطلاح دوم تعداد مسیرهای دو مرحله ای را هنگامی که i و j مستقیماً به هم متصل می شوند ، می دهد. اصطلاح سوم هنگامی که i و j به هم متصل نیستند مقدار مربوطه را می دهد . از آنجا که این سه مورد متقابلاً منحصر به فرد و در مجموع جامع و کامل هستند ، برابری افزایشی ساده به دنبال دارد.

برعکس ، گرافی که ماتریس مجاورت آن هر دو شرایط فوق را برآورده می کند و یک نمودار کامل یا صفر نیست ، یک نمودار کاملاً منظم است. [4]

مقادیر ویژه [ ویرایش ]

ماتریس مجاورت نمودار دقیقاً دارای سه مقدار ویژه است :

k ، که تعدد آن 1 است (همانطور که در بالا مشاهده می شود)
${\ displaystyle {\ frac {1} {2}} \ left [(\ lambda - \ mu) + {\ sqrt {(\ lambda - \ mu) ^ {2} +4 (k- \ mu)}} \ درست]،}$ که تعدد آن است ${\ frac {1} {2}} \ left [(v-1) - {\ frac {2k + (v-1) (\ lambda - \ mu)} {{\ sqrt {(\ lambda - \ mu) ^ {2} +4 (k- \ mu)}}}} \ راست]$
${\ displaystyle {\ frac {1} {2}} \ left [(\ lambda - \ mu) - {\ sqrt {(\ lambda - \ mu) ^ {2} +4 (k- \ mu)}} \ درست]،}$ که تعدد آن است ${\ frac {1} {2}} \ left [(v-1) + {\ frac {2k + (v-1) (\ lambda - \ mu)} {{\ sqrt {(\ lambda - \ mu) ^ {2} +4 (k- \ mu)}}}} \ راست]$

از آنجا که ضرب ها باید عدد صحیح باشند ، عبارات آنها محدودیت های بیشتری را در مقادیر v ، k ، μ و λ ایجاد می کنند ، مربوط به شرایط به اصطلاح کرین .

نمودارهای کاملاً منظمی که $2k + (v-1) (\ lambda - \ mu) = 0$ به دلیل ارتباط با ماتریس کنفرانس متقارن ، نمودار کنفرانس نامیده می شوند . پارامترهای آنها به کاهش می یابد

${\ text {srg}} \ چپ (v ، {\ tfrac {1} {2}} (v-1) ، {\ tfrac {1} {4}} (v-5) ، {\ tfrac {1} {4}} (v-1) \ راست).$

نمودارهای کاملاً منظمی که $2k + (v-1) (\ lambda - \ mu) \ neq 0$ دارای مقادیر ویژه عدد صحیح با چند برابر نابرابر هستند.

برعکس ، یک نمودار منظم متصل فقط با سه مقدار ویژه کاملاً منظم است. [5]

مثالها [ ویرایش ]

چرخه طول 5 SRG (5، 2، 0، 1) است.
گراف پترسن SRG (10، 3، 0، 1) است.
نمودار Clebsch به SRG (16، 5، 0، 2) است.
نمودار Shrikhande SRG (16، 6، 2، 2) است که نمی باشد نمودار فاصله-متعدی .
N × N مربع نمودار رخ ، به عنوان مثال، نمودار خط از گراف دوبخشی کامل و متعادل کننده K ، N، N ، یک SRG است ( N 2 ، 2 نفر - 2، N - 2، 2). پارامترهای n = 4 با پارامترهای نمودار Shrikhande همزمان هستند ، اما این دو نمودار غیر شکل نیستند.
نمودار خط از یک گراف کامل K N SRG (است ${\ displaystyle {\ binom {n} {2}} ، 2 (n-2) ، n-2،4}$ )
نمودار چانگ می SRG (28، 12، 6، 4)، همان نمودار خط K 8 ، اما این چهار نمودار، می ریخت است.
نمودار خط از یک چهارگوش تعمیم GQ (2، 4) SRG (27، 10، 1، 5) است. در واقع هر چهار ضلعی مرتب شده (s ، t) از این طریق یک نمودار کاملاً منظم می دهد: 1+)
نمودار Schläfli SRG (27، 16، 10، 8) است. [6]
نمودار هافمن – سینگلتون یک srg است (50 ، 7 ، 0 ، 1).
نمودار Sims-Gewirtz یک نمودار (56 ، 10 ، 0 ، 2) است.
نمودار M22 با نام مستعار نمودار Mesner SRG (77، 16، 0، 4) است.
نمودار Brouwer – Haemers یک srg است (81 ، 20 ، 1 ، 6).
نمودار Higman – Sims یک srg است (100 ، 22 ، 0 ، 6).
نمودار مک لافلین محلی SRG (162، 56، 10، 24).
نمودار کامرون SRG (231، 30، 9، 3) است.
نمودار Berlekamp – van Lint – Seidel یک srg است (243 ، 22 ، 1 ، 2).
نمودار مک لافلین SRG (275، 112، 30، 56) است.
نمودار پالی از سفارش Q SRG (است س ، ( Q - 1) / 2، ( Q - 5) / 4، ( Q - 1) / 4). کوچکترین نمودار Paley ، با q = 5 ، 5 دور است (در بالا).
نمودارهای خود-مکمل قوسی-انتقالی کاملا منظم هستند.

اگر نمودار و مکمل آن به هم همبند شوند ، یک نمودار کاملاً منظم ابتدایی نامیده می شود . تمام نمودارهای فوق ابتدایی هستند ، در غیر این صورت μ = 0 یا λ = k.

مشکل 99 نمودار Conway خواستار ساخت srg است (99 ، 14 ، 1 ، 2). مشخص نیست که گرافی با این پارامترها وجود دارد یا خیر و جان هورتون کانوی جایزه ای 1000 دلاری برای حل این مسئله پیشنهاد داده است. [7]

نمودارهای بدون مثلث ، نمودارهای مور و نمودارهای ژئودزیکی [ ویرایش ]

نمودارهای کاملاً منظم با λ = 0 مثلث آزاد هستند . جدا از نمودارهای کامل در کمتر از 3 رئوس و همه نمودارهای کامل و کامل ، هفت نمودار ذکر شده در بالا (پنج ضلعی ، پیترسن ، کلبش ، هافمن-سینگلتون ، گویرتز ، مسنر-M22 و هیگمن-سیمز) تنها موارد شناخته شده هستند. نمودارهای کاملاً منظم با λ = 0 و μ = 1 نمودارهای مور با اندازه 5 هستند. باز هم سه نمودار فوق (پنج ضلعی ، پیترسن و هافمن-سینگلتون) ، با پارامترهای (5 ، 2 ، 0 ، 1) ، (10 ، 3 ، 0 ، 1) و (50 ، 7 ، 0 ، 1) ، تنها موارد شناخته شده هستند. تنها مجموعه پارامترهای ممکن دیگر که دارای نمودار مور هستند (3250 ، 57 ، 0 ، 1) است. اگر چنین گرافی وجود داشته باشد ، مشخص نیست و اگر چنین است ، منحصر به فرد است یا نه. [8]

به طور کلی ، هر نمودار کاملاً منظمی با $\ mu = 1$ یک نمودار ژئودتیک است ، گرافی که در آن هر دو رئوس کوتاهترین مسیر بدون وزنه را دارد . [9] تنها نمودارهای کاملاً منظم شناخته شده با $\ mu = 1$ نمودارهای مور هستند. وجود چنین گرافی امکان پذیر نیست $\ lambda = 1$ ، اما سایر ترکیبات پارامترها مانند (400 ، 21 ، 2 ، 1) هنوز منتفی نیستند. با وجود تحقیقات مداوم در مورد خواصی که یک نمودار کاملاً منظم با آنها دارد $\ mu = 1$ باید، [10] [11] از آن است که آیا هر موجود و یا حتی اینکه آیا تعداد آنها محدود است شناخته شده نیست. [9]

همچنین به [ ویرایش ] مراجعه کنید

یادداشت ها

https://en.wikipedia.org/wiki/Strongly_regular_graph

مشخصات وب

در این وبلاگ به ریاضیات و کاربردهای آن و تحقیقات در آنها پرداخته می شود. مطالب در این وبلاگ ترجمه سطحی و اولیه است و کامل نیست.در صورتی سوال یا نظری در زمینه ریاضیات دارید مطرح نمایید .در صورت امکان به آن می پردازم. من دوست دارم برای یافتن پاسخ به سوالات و حل پروژه های علمی با دیگران همکاری نمایم.در صورتی که شما هم بامن هم عقیده هستید با من تماس بگیرید.
09132003030

ریاضیات

آموزش ریاضی