ریاضیات

سایر خانواده های گراف مربوط [ ویرایش ]

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

گرافهای خط درختان دقیقاً گرافهای بلوکی بدون پنجه هستند . [22] این گرافها برای حل مسئله ای در تئوری گراف افراطی ، ساخت گرافی با تعداد مشخصی از لبه (یال)ها و رئوس که بزرگترین درخت القا شده به عنوان زیرگراف تا حد ممکن کوچک است ، استفاده شده است. [23]

همه مقادیر ویژه از ماتریس مجاورت  از یک گراف خط حداقل −2 است. دلیل این امر این است که  می تواند به صورت  ، جایی که   ماتریس وقوع بدون علامت گراف پیش خط است و هویت است به خصوص، است ماتریس Gramian تمام گراف ها با این ویژگی شده اند به نام گراف خط تعمیم: یک سیستم از بردار. [24]

شخصیت پردازی و تشخیص [ ویرایش ]

پارتیشن کلیک [ ویرایش ]

تقسیم گراف خطی به صورت کلیکی

برای یک گراف دلخواه G ، و یک راس دلخواه v در G ، مجموعه لبه (یال)های رخ داده با v مربوط به یک دسته در گراف خط L ( G ) است. تکه های تشکیل شده به این ترتیب لبه (یال)های L ( G ) را تقسیم می کنند. هر راس L ( G ) دقیقاً به دو مورد از آنها تعلق دارد (دو کلیک مربوط به دو نقطه انتهایی لبه (یال)مربوطه در G ).

از وجود چنین پارتیشنی به صورت کلیکی می توان برای مشخص کردن گرافهای خط استفاده کرد: یک گراف L گراف خطی گراف یا چند گراف دیگری است اگر و فقط در صورت امکان یافتن مجموعه ای از کلیک ها در L (اجازه برخی از موارد کلیک ها به صورت یک راس واحد هستند) که لبه (یال)های L را تقسیم می کنند ، به طوری که هر راس L دقیقاً به دو دسته مربوط می شود. [20] این گراف خطی یک گراف است (به جای چند گراف) اگر این مجموعه کلیها شرایط دیگری را تأمین کند که هیچ دو راس L هر دو در همان دو کلیک نیست. با توجه به چنین خانواده ای از کلیک ها ، گراف زیر G برای آن Lگراف خطی است که می توان با ساختن یک راس در G برای هر دسته ، و یک لبه (یال)در G برای هر راس در L با نقاط انتهایی آن ، دو کلیک حاوی راس در L است . با توجه به نسخه قوی قضیه ایزومورفیسم ویتنی ، اگر گراف زیر G بیش از چهار رئوس داشته باشد ، فقط یک پارتیشن از این نوع وجود دارد.

به عنوان مثال ، از این خصوصیات می توان برای نشان دادن اینکه گراف زیر گراف خطی نیست استفاده کرد:

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