ریاضیات

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

شکل های زیر یک گراف (سمت چپ ، با راس های آبی) و گراف خط آن (راست ، با راس های سبز) را نشان می دهد. هر راس گراف خط با برچسب جفت نقاط انتهایی لبه (یال)مربوطه در گراف اصلی نشان داده شده است. به عنوان مثال ، رأس سبز در سمت راست با برچسب 1،3 مربوط به لبه (یال)سمت چپ بین رأس های آبی 1 و 3 است. رأس سبز 1،3 در مجاورت سه رأس سبز دیگر است: 1،4 و 1،2 (مربوط به به لبه (یال)هایی که نقطه پایانی 1 را در گراف آبی به اشتراک می گذارند) و 4،3 (مربوط به یک لبه (یال)مشترک نقطه انتهایی 3 در گراف آبی).

گراف G

رئوس در L (G) از لبه (یال)های G ساخته شده است

لبه (یال)های اضافه شده در L (G)

گراف خط L (G)

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

خصوصیات ترجمه شده گراف اساسی [ ویرایش ]

خصوصیات یک گراف G که فقط به مجاورت بین لبه (یال)ها بستگی دارد ، می تواند در L ( G ) به خصوصیات معادل ترجمه شود که به مجاورت بین رئوس بستگی دارد. به عنوان مثال ، تطبیق در G مجموعه ای از لبه (یال)ها است که دو تا از آنها مجاور نیستند و مربوط به مجموعه ای از رئوس در L ( G ) است که هیچ دو مجاور نیستند ، یعنی یک مجموعه مستقل . [4]

بدین ترتیب،

• گراف خط یک گراف همبنداست. اگر G همبندباشد ، شامل مسیری است که هر دو لبه (یال)آن را بهم همبندمی کند ، که به یک مسیر در L ( G ) تبدیل می شود که شامل هر دو راس L ( G ) است. با این حال ، یک گراف G که دارای برخی از رئوس جدا شده است و بنابراین قطع شده است ، ممکن است دارای یک گراف خط همبندباشد. [5]
• یک گراف خط دارای نقطه بیان اگر و تنها اگر گراف زمینه دارای یک پل است که نه نقطه پایانی است یک درجه. [2]
• برای یک گراف G با n را راس و M لبه، تعداد رئوس گراف خط L ( G ) است M و تعداد لبه (یال)های L ( G ) نیمی از مجموع مربعات از است درجه رئوس در G ، منهای M . [6]
• یک مجموعه مستقل در L ( G ) مربوط به مطابقت در G است . به طور خاص ، یک مجموعه حداکثر مستقل در L ( G ) با حداکثر مطابقت در G مطابقت دارد . از آنجا که حداکثر تطابق ممکن است در زمان چند جمله ای پیدا شود ، بنابراین ممکن است حداکثر مجموعه های مستقل گرافهای خط ، با وجود سختی مشکل حداکثر مجموعه مستقل برای خانواده های کلی گرافها. [4] به طور مشابه ، مجموعه ای مستقل از رنگین کمان در L ( G ) مربوط به رنگین کمان است که در G مطابقت دارد .
• لبه (یال)عدد رنگی از یک گراف G به برابر است راس عدد رنگی گراف خط خود را L ( G ). [7]
• گراف خطی یک گراف لبه (یال)متعدی است راس-متعدی . از این ویژگی می توان برای ایجاد خانواده هایی از گراف استفاده کرد که (مانند گراف پیترسن ) راس-انتقالی هستند اما گرافهای Cayley نیستند : اگر G یک گراف حاشیه ای است که حداقل پنج راس دارد ، دو قسمت نیست و راس فرد دارد درجه ، سپس L ( G ) یک گراف غیر کایلی راس-انتقالی است. [8]
• اگر یک گراف G دارای یک دور اویلر ، این است که، اگر G همبنداست و حتی تعداد از لبه (یال)در هر راس، پس از آن گراف خط از G است هامیلتونی . با این حال ، همه دور های همیلتون در گرافهای خط از دور های اولر به این ترتیب حاصل نمی شوند. به عنوان مثال ، گراف خط یک گراف هامیلتونی G خود همیلتونی است ، صرف نظر از اینکه G نیز اولری باشد. [9]
• اگر دو گراف ساده یکدست نباشد ، گرافهای خطی آنها نیز نامتقارن است. ویتنی یکریختی گراف قضیه یک محاوره با این برای همه اما یک جفت از گراف فراهم می کند.
• در چارچوب نظریه پیچیده شبکه ، گراف خطی یک شبکه تصادفی بسیاری از خصوصیات شبکه مانند خاصیت جهان کوچک (وجود مسیرهای کوتاه بین همه جفت رأس ها) و شکل توزیع درجه آن را حفظ می کند . [10] Evans & Lambiotte (2009) مشاهده کردند که هر روشی برای یافتن خوشه های راس در یک شبکه پیچیده می تواند بر روی گراف خط اعمال شود و به جای آن برای خوشه بندی لبه (یال)های آن استفاده شود.

قضیه ایزومورفیسم ویتنی [ ویرایش ]

گراف الماس ، یک استثنا برای این قضیه قوی ویتنی

اگر گرافهای خطی دو گراف متصل به هم یکدست نباشند ، گرافهای زیرمجموعه هستند ، مگر در مورد گراف مثلث K 3 و پنجه K 1،3 ، که دارای گرافهای خط غیر همسان هستند اما خود منسجم نیستند. [3]

علاوه بر K 3 و K 1،3 ، گرافهای کوچک استثنایی دیگری نیز با این ویژگی وجود دارد که گراف خط آنها دارای درجه تقارن بالاتری از خود گراف است. به عنوان مثال ، گراف الماس K 1،1،2 (دو مثلث مشترک لبه) دارای چهار شکل گیری گراف است اما گراف خط آن K 1،2،2هشت تا دارد. در تصویر گراف الماس نشان داده شده ، چرخش 90 درجه گراف تقارن گراف نیست ، بلکه تقارن گراف خط آن است. با این حال ، همه این موارد استثنایی حداکثر چهار راس دارند. یک نسخه تقویت شده از قضیه ایزومورفیسم ویتنی بیان می کند که ، برای گرافهای همبندبا بیش از چهار راس ، بین یکسان سازی گرافها و ایزومورفیسم گرافهای خط آنها یک به یک مطابقت وجود دارد. [11]

آنالوگ از ریخت ویتنی قضیه برای گراف خط از ثابت شده است گرافهای چندگانه ، اما بیشتر در این مورد پیچیده است. [12]