گراف جانسون

[*Ghazale*]

گراف جانسون

گراف جانسون یک نوع خاص از گراف بدون جهت تعریف شده از نظام مجموعه‌ها است. رئوس گراف جانسون هستند؛ زیرمجموعه از یک مجموعه با ; دو راسی مجاور هستند که تقاطع دو راس (زیر مجموعه) شامل . هر دوی گراف جانسون و جانسون طرح به نام سلمر مارتین جانسون نام گذاری شده‌است.

موارد خاص

گراف کامل Kn است.
گراف هشت وجهی است.
گراف مکمل برای گراف پترسن است، بنابراین گراف خط K5 است. به‌طور کلی، به ازای هر n، گراف جانسون مکمل گراف نسر

گروه خودسازی

یک زیر گروه فاصله-متعدی از هم ریخت به . در واقع ≅ مگر اینکه ; در غیر این صورت ≅

آرایه تقاطع

به عنوان یک نتیجه از در فاصله-متعدی بودن، همچنین با فاصله منظم بودن . به صورت نمایش داده می‌شود که در آن:

برای همه .
برای همه .
مگر آنکه ; آرایه تقاطع با سه گراف دیگر با فاصله منظمی که گراف جانسون نباشند به اشتراک گذاشته می‌شود

مقادیر ویژه و بردارهای ویژه

مشخصه چند جمله ای به روش زیر به دست می‌آید: .
این بردارهای ویژه از توصیف صریحی دارند.

رابـ*ـطه با طرح جانسون

گراف جانسون رابـ*ـطه نزدیکی با طرح جانسون دارد، یک طرح انجمنی که در آن هر جفت از k عضو مجموعه در ارتباط با عددی است که نصف اندازه تفاضل متقارن این دو مجموعه است.گراف جانسون برای هر جفت از مجموعه‌ها که فاصله آن‌ها در طرح انجمنی یکی است، یک یال دارد، و فواصل در طرح انجمنی دقیقاً کوتاهترین مسیر در گراف جانسون است.

طرح جانسون همچنین با دیگر خانواده‌ها از مسیر-متعدی، گراف‌های فرد که رئوس آن‌ها دارای زیر مجموعه‌هایی با از مجموعه ای شامل .

مشکلات حل نشده

ویژگی‌های گسترش راس از گراف جانسون به خوبی ساختار متناظر مجموعه‌های رئوس از اندازه داده شده، به‌طور کامل قابل فهم نیست. اگرچه، به‌طور متناوب محدوده کوچک‌تر در گسترش مجموعه‌های بزرگ از رئوس، به تازگی به دست آمده‌است.

به‌طور کلی، در تعیین تعداد رنگ‌ها برای گراف جانسون یک مشکل حل نشده‌است.

گراف جانسون

رمان ۹۸ | بهترین انجمن رمان نویسی

بهترین انجمن رمان نویسی ایران | رمان ۹۸

forum.roman98.com

رمان ۹۸ | دانلود رمان

نودهشتیا,بزرگترین مرجع تایپ رمان, دانلود رمان جدید,دانلود رمان عاشقانه, رمان خارجی, رمان ایرانی, دانلود رمان بدون سانسور,دانلود رمان اربابی,

roman98.com