ریاضیات

در ریاضیات ، دو -گراف مجموعه ای از سه گانه (غیر مرتب) است که از یک راس محدود X انتخاب می شود ، به این ترتیب که هر چهار چهارگانه (غیر مرتب) از X شامل تعداد زوج سه گانه دو نمودار است. یک دو نمودار منظم این خاصیت را دارد که هر جفت رئوس در همان تعداد سه برابر دو نمودار قرار دارد. دو نمودار به دلیل ارتباط آنها با خطوط مثلثی و برای دو نمودار منظم ، نمودارهای کاملاً منظم و همچنین گروه های محدود مورد مطالعه قرار گرفته اند زیرا بسیاری از نمودارهای منظم دارای دو گروه جالب شکل سازی هستند .

دو نمودار یک نمودار نیست و نباید با اشیا called دیگر به نام 2 نمودار در تئوری نمودار مانند نمودارهای 2 منظم اشتباه گرفته شود .

فهرست

• 1مثال ها
• 2تعویض و نمودارها
• 3ماتریس همجواری
• 4خطوط مثلثی
• 5نمودارهای کاملاً منظم
• 6یادداشت
• 7منابع

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

در مجموعه رئوس {1 ، ... ، 6} مجموعه زیر از سه گانه های نامرتب دو نمودار است:

123 124 135 146 156 236 245 256 345 346

این دو نمودار یک نمودار دو منظم است زیرا هر جفت رئوس مجزا دقیقاً در دو سه گانه با هم ظاهر می شوند.

با توجه به یک نمودار ساده G = ( V ، E ) ، مجموعه سه گانه مجموعه راس V که زیرگراف القایی آن دارای تعداد عجیب و غریب لبه ها است ، یک نمودار دو مجموعه ای روی مجموعه V تشکیل می دهد . هر دو نمودار را می توان به این روش نشان داد. [1] از این مثال به عنوان ساختار استاندارد دو نمودار از یک نمودار ساده یاد می شود.

به عنوان یک مثال پیچیده تر ، بگذارید T یک درخت با مجموعه لبه E باشد. مجموعه تمام سه گانه های E که در مسیری از T وجود ندارند ، یک دو نمودار روی مجموعه E تشکیل می دهند . [2]

تعویض و نمودارها [ ویرایش ]

تغییر {X ، Y} در یک نمودار

یک دو نمودار معادل یک کلاس تعویض نمودار و همچنین یک کلاس تعویض (امضا شده) نمودار کامل امضا شده است .

تغییر یک مجموعه رئوس در یک نمودار (ساده) به معنی معکوس کردن مجاورت های هر جفت رئوس است ، یکی در مجموعه و دیگری در مجموعه نیست: بنابراین مجموعه لبه تغییر می کند به طوری که یک جفت مجاور غیر همسایه و یک جفت غیر مجاور می شود مجاور می شود. لبه هایی که نقاط انتهایی آنها هر دو در مجموعه هستند ، یا هر دو در مجموعه نیستند ، تغییر نمی کنند. نمودارها در صورتی معادل سوئیچینگ هستند که بتوان یکی را با تعویض از دیگری به دست آورد. یک کلاس معادل سازی نمودارهای تحت سوئیچینگ ، کلاس تعویض نامیده می شود . سوئیچینگ توسط van Lint & Seidel (1966) معرفی شد و توسط Seidel توسعه یافت. تا حدودی برای تمایز آن از سوئیچینگ ، تغییر نمودار یا Seidel Switching نامیده شده استنمودار امضا .

در ساخت استاندارد یک دو نمودار از یک نمودار ساده که در بالا آورده شده است ، دو نمودار همان دو نمودار را ارائه می دهند اگر و فقط اگر در تعویض برابر باشند ، یعنی در یک کلاس تعویض باشند.

بگذارید Γ یک دو نمودار روی مجموعه X باشد. برای هر عنصر x از X ، یک نمودار با مجموعه راس X با رئوس y و z مجاور تعریف کنید ، اگر و فقط اگر { x ، y ، z } در Γ باشد. در این نمودار ، x یک راس جداگانه خواهد بود. این ساخت و ساز قابل برگشت است. با یک نمودار ساده G ، یک عنصر جدید x را به مجموعه رئوس G اضافه کنید و دو نمودار را تعریف کنید که سه برابر آن { x ، y ، z } باشد ، جایی که y و zرئوس مجاور در G هستند . این دو نمودار است به نام پسوند از G توسط X در طراحی زبان نظری . [3] در یک کلاس تغییر داده شده از نمودارهای یک نمودار دو عادی ، بگذارید Γ x یک نمودار منحصر به فرد باشد که دارای x به عنوان یک راس جدا شده است (این همیشه وجود دارد ، فقط هر نمودار در کلاس را بگیرید و محله باز x را تغییر دهید ) بدون راس x . این است که، دو نمودار است گسترش Γ ایکس توسط X . در اولین مثال بالا از دو نمودار منظم ، Γ x برای هر انتخاب x یک چرخه 5 است. [4]

برای یک گراف G مربوط Σ گراف کامل امضا در مجموعه راس همان، که لبه ها منفی اگر در امضا وجود دارد G و اگر نه مثبت در G . برعکس ، G زیرنویس Σ است که از همه رئوس و تمام لبه های منفی تشکیل شده است. دو نمودار G همچنین می تواند مجموعه ای از سه راس رئوس باشد که از یک مثلث منفی پشتیبانی می کنند (یک مثلث با تعداد عجیب و غریب لبه های منفی) در Σ. دو نمودار کامل امضا شده ، دو نمودار یکسانی را ارائه می دهند در صورتی که فقط در صورت تعادل با سوئیچینگ برابر باشند.

سوئیچینگ G و S با هم مرتبط هستند: تغییر رئوس یکسان در هر دو یک نمودار H و نمودار کامل امضا شده مربوط به آن را به دست می دهد.

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

ماتریس مجاورت یک گراف دو است ماتریس مجاورت گراف کامل مربوطه را امضا کردند؛ بنابراین متقارن است ، روی مورب صفر است و ورودی های آن 1 off از مورب است. اگر G نمودار متناظر با نمودار کامل امضا شده Σ باشد ، به این ماتریس ماتریس اضافه شدن مجاورت (0 ، −1 ، 1) یا ماتریس مجاور Seidel از G می گویند . ماتریس Seidel دارای صفر ورودی در مورب اصلی ، -1 ورودی برای رئوس مجاور و 1+ ورودی برای رئوس غیر مجاور است.

اگر نمودار G و H در یک کلاس سوئیچینگ هستند، multisets مقادیر ویژه از دو ماتریس مجاورت سیدل از G و H همزمان، از ماتریس مشابه هستند. [5]

دو نمودار در یک مجموعه V منظم است اگر و فقط اگر ماتریس مجاور آن فقط دو مقدار ویژه متمایز داشته باشد ρ 1 > 0> ρ 2 بگویید ، جایی که ρ 1 ρ 2 = 1 - | V |. [6]

خطوط مثلثی [ ویرایش ]

مقاله اصلی: خطوط مثلثی

هر دو نمودار معادل مجموعه ای از خطوط در برخی فضای اقلیدسی بعدی است که هر جفت از آنها در یک زاویه قرار می گیرند. مجموعه خطوط ساخته شده از دو نمودار روی n رئوس به شرح زیر بدست می آید. اجازه دهید -ρ باشد کوچکترین مقادیر ویژه از ماتریس مجاورت سیدل ، ، از دو نمودار، و فرض کنید که آن را تا تعدد N - D . سپس ماتریس ρ I + A مثبت نیمه مشخص از درجه d است و بنابراین می تواند به عنوان ماتریس گرم محصولات داخلی n بردار در اقلیدسی d نشان داده شود-فضا. از آنجا که این بردارها همان هنجار را دارند (یعنی) و ضرب درونی متقابل ± 1 ، هر جفت از n خطی که توسط آنها پوشانده شده اند در همان زاویه φ قرار می گیرند که در آن cos φ = 1 / ρ. برعکس ، هر مجموعه ای از خطوط مثلثی غیر متعامد در یک فضای اقلیدسی می تواند منجر به ایجاد یک دو نمودار شود ( خطوط مثلثی شکل را ببینید ). [7]

با علامت گذاری شده در بالا ، حداکثر کاردینالیته n n ≤ d (ρ 2 - 1) / (ρ 2 - d ) را برآورده می کند و محدودیت در صورتی حاصل می شود که فقط در صورت منظم بودن دو نمودار باشد.

نمودارهای کاملاً منظم [ ویرایش ]

مقاله اصلی: نمودار کاملاً منظم

دو نمودار روی X متشکل از تمام سه گانه های احتمالی X و هیچ سه گانه X دو نمودار منظم نیستند و دو نمودار پیش پا افتاده محسوب می شوند .

برای دو نمودار غیر پیش پا افتاده در مجموعه X ، دو نمودار منظم است اگر و فقط اگر برای برخی از x در X نمودار Γ x یک نمودار کاملاً منظم با k = 2μ باشد (درجه هر راس دو برابر عدد است) از رئوس مجاور هر دو از هر جفت راس غیر مجاور). اگر این شرط برای یک x در X نگه داشته شود ، برای همه عناصر X صدق می کند . [8]

از این رو می توان گفت که دو نمودار منظم غیر پیش پا افتاده دارای تعداد زوج است.

اگر G یک نمودار منظم است که پسوند دو نمودار آن Γ دارای n نقطه است ، پس Γ یک نمودار دو منظم است اگر و فقط اگر G یک نمودار کاملاً منظم با مقادیر ویژه k ، r و s باشد که n = 2 را راضی کند ( k - r ) یا n = 2 ( k - s ). [9]