ریاضیات

تکرار عملگر گراف خط [ ویرایش ]

van Rooij & Wilf (1965) توالی گرافها را در نظر می گیرند

آنها نشان می دهند ، وقتی G یک گراف متصل محدود است ، فقط چهار رفتار برای این توالی امکان پذیر است:

• اگر G یک گراف سپس L ( G ) و هر گراف پس از آن در این رشته هستند ریخت به G است. این تنها گرافهای همبنداست که L ( G ) برای G یکسان نیست . [26]
• اگر G یک پنجه K 1،3 باشد ، L ( G ) و تمام گرافهای بعدی در توالی مثلث هستند.
• اگر G یک گراف مسیر باشد ، هر گراف بعدی در دنباله یک مسیر کوتاه تر است تا اینکه در نهایت توالی با یک گراف خالی خاتمه یابد .
• در تمام موارد باقیمانده ، اندازه گرافها در این توالی سرانجام بدون محدودیت افزایش می یابد.

اگر G همبندنباشد ، این طبقه بندی به طور جداگانه برای هر جز component G اعمال می شود .

برای گرافهای همبندکه مسیر نیستند ، تمام تکرارهای عمل گراف خطی به اندازه کافی زیاد ، گرافهایی تولید می کنند که همیلتونین هستند. [27]

تعمیم [ ویرایش ]

گرافهای داخلی و چند وجهی محدب [ ویرایش ]

مقاله اصلی: گراف داخلی

وقتی یک گراف مسطح G دارای حداکثر درجه راس سه باشد ، گراف خط آن مسطح است و هر تعبیه مسطح G می تواند به یک تعبیه شده از L ( G ) گسترش یابد. با این حال ، گرافهای مسطحی با درجه بالاتر وجود دارد که گرافهای خطی آنها غیرهمسطح هستند. این موارد شامل ، به عنوان مثال ، 5 ستاره K 1،5 ، گراف جواهرات تشکیل شده با اضافه کردن دو مورب غیر تلاقی در یک پنج ضلعی منظم ، و همه چند وجه های محدب با راس درجه چهار یا بیشتر. [28]

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

برای چند وجهی های معمولی یا چند وجهی های ساده ، می توان از طریق هندس به وسیله برش هر راس چند وجهی توسط یک صفحه از طریق نقاط میانی تمام لبه (یال)های برخوردش ، گراف گراف داخلی را نشان داد. [30] این عملیات به عنوان کوتاه سازی دوم ، [31] کوتاه شدن منحط ، [32] یا اصلاح شناخته می شود . [33]

گرافهای کل [ ویرایش ]

گراف کل T ( G ) یک گراف G دارای عناصر (رئوس یا لبه (یال)ها) G است و هر زمان که اتفاق افتاده یا مجاور باشد بین دو عنصر یک لبه (یال)دارد. گراف کل نیز ممکن است با تقسیم هر لبه (یال)G و سپس گرفتن مربع گراف تقسیم شده بدست آید. [34]

چند نگاره [ ویرایش ]

مفهوم گراف خط G به طور طبیعی ممکن است در موردی که G یک چند گراف است گسترش یابد . در این حالت ، خصوصیات این گرافها را می توان ساده کرد: شخصیت پردازی از نظر پارتیشن های کلیکی دیگر نیازی به جلوگیری از تعلق دو راس به همان دسته ها ندارد و شخصیت پردازی توسط گرافهای ممنوع به جای نه گراف ، هفت گراف ممنوع دارد. [35]

با این حال ، برای چند گرافها ، تعداد بیشتری جفت گراف غیر همسان وجود دارد که گرافهای خط یکسانی دارند. به عنوان مثال یک گراف دو بخشی کامل K 1 ، n دارای گراف خطی همان گراف دو قطبی و ضرب شانون با تعداد لبه (یال)های یکسان است. با این وجود هنوز هم می توان در این مورد از آنالوگ قضیه ایزومورفیسم ویتنی استفاده کرد. [12]

گرافهای خطی[ ویرایش ]

ساخت گرافهای دی بروین به عنوان گرافهای تکراری خط

همچنین می توان گرافهای خط را به گرافهای هدایت شده تعمیم داد. [36] اگر G یک گراف جهت است، آن گراف خط به کارگردانی و یا گراف خط یک راس برای هر لبه (یال)G . دو رئوس نمایانگر لبه (یال)های جهت دار از u به v و از w به x در G با یک لبه (یال)از uv به wx در گراف خطی همبندمی شوند که v = w . یعنی هر لبه (یال)در گراف خط G نشان دهنده یک مسیر دو جهته در G است . گرافهای د بروین ممکن است با تکرار این روند تشکیل گرافهای خط مستقیم ، از یک گراف کامل کارگردانی ، تشکیل شوند . [37]

گرافهای خط وزنی [ ویرایش ]

در گراف خط L ( G ) ، هر راس درجه k در گراف اصلی G باعث ایجاد k ( k - 1) / 2 لبه (یال)در گراف خط می شود. برای بسیاری از انواع تجزیه و تحلیل ، این بدان معنی است که گره های درجه بالا در G در گراف خط L ( G ) بیش از حد نشان داده شده اند . به عنوان مثال ، یک قدم زدن تصادفی بر روی رئوس گراف اصلی G را در نظر بگیرید. این در امتداد برخی از لبه (یال)های e با برخی از فرکانس f عبور می کند از طرف دیگر ، این لبه (یال)e به یک راس منحصر به فرد ، مثلاً v ، در گراف خط L ترسیم می شود( G ) اگر اکنون یک نوع پیاده روی تصادفی را بر روی رئوس گراف خط انجام دهیم ، فرکانس بازدید از v می تواند کاملا با f متفاوت باشد . اگر لبه (یال)e ما در G به گره های درجه O ( k ) همبندباشد ، در گراف خط L ( G ) بیشتر O ( k 2 ) عبور داده می شود . به عبارت دیگر، ویتنی تضمین قضیه یکریختی گراف که گراف خط تقریبا همیشه کد می توپولوژی از گراف اصلی Gصادقانه اما تضمین نمی کند که پویایی در این دو گراف یک رابطه ساده دارد. یک راه حل ساختن گراف خط وزنی است ، یعنی یک گراف خطی با لبه (یال)های وزن دار . چندین روش طبیعی برای انجام این کار وجود دارد. [38] به عنوان مثال اگر لبه (یال)های d و e در گراف G در یک راس v با درجه k قرار داشته باشند ، در گراف خط L ( G ) می توان به لبه (یال)اتصال دو راس d و e وزن 1 / ( k) داد - 1) به این ترتیب هر لبه (یال)در G(به شرطی که هیچ یک از انتها به راس درجه 1 همبندنباشد) دارای مقاومت 2 در گراف خط L ( G ) مربوط به دو انتهای لبه (یال)در G خواهد بود. ساده است که این تعریف از گراف خط وزنی را به مواردی که گراف اصلی G کارگردانی یا حتی وزنی شده است ، گسترش دهیم. [39] اصل در همه موارد این است که اطمینان حاصل شود گراف خط L ( G ) دینامیک و همچنین توپولوژی گراف اصلی G را منعکس می کند .

گرافهای خط هایپراگراف [ ویرایش ]

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

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

گراف عدم انسجام [ ویرایش ]

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

منبع

https://en.wikipedia.org/wiki/Line_graph