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

از ویکیپدیا، دانشنامه آزاد

گراف پالی از سفارش 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 هر زمان μ غیر صفر باشد. این است گراف به صورت محلی خطی هر زمان که λ است.

فهرست

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

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

چهار پارامتر در یک 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 ، رابطه به شرح زیر است.

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

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

$AJ = JA = kJ ،$

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

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

که بیانگر یک نظم قوی است. IJ عنصر توریم از سمت چپ می دهد تعدادی از مسیرهای دو مرحله ای از من به 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) یک نمودار کاملاً منظم از این طریق می دهد: برای wit ، یک srg ((s + 1) (st + 1) ، s (t + 1) ، s-1 ، 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

+ نوشته شده در جمعه بیست و چهارم بهمن ۱۳۹۹ ساعت 9:9 توسط علی رضا نقش نیلچی |

ریاضیات

آموزش ریاضی