گراف کاملاً منظم

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

نمودار پالی از سفارش 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) به این ترتیب یک نمودار کاملاً منظم می دهد: 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]

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

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

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

ریاضیات

آموزش ریاضی

گراف کاملاً منظم

پیوندهای روزانه

نوشته‌های پیشین

آرشیو موضوعی

پیوندها

آمارگیر وبلاگ

کد پربازدیدترین