ریاضیات

از ویکیپدیا، دانشنامه آزاد

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

با گراف مسیر اشتباه گرفته نشود .

در رشته ریاضی نظریه گراف ، گراف خط یک گراف G غیر جهت دار گراف دیگری L ( G ) است که مجاورت های بین لبه های G را نشان می دهد . L ( G ) به روش زیر ساخته شده است: برای هر لبه (یال)در G ، یک راس در L ( G ) ایجاد کنید. از هر دو لبه (یال)G که یک راس مشترک دارند ، بین رئوس مربوطه در L ( G ) یک لبه (یال)ایجاد کنید .

نام گراف خط از مقاله ای توسط هاری و نورمن (1960) گرفته شده است ، هر چند ویتنی (1932) و کراوس (1943) از ساخت و ساز قبل از این استفاده کرده اند. [1] سایر عبارات مورد استفاده برای گراف خط شامل گراف پوششی ، مشتق ، دوتایی لبه (یال)به راس ، مزدوج ، گراف نماینده و ϑ-obrazom ، [1] و همچنین گراف لبه (یال)، گراف گراف مبادله ، گراف الحاقی و گراف مشتق شده . [2]

Hassler ویتنی  ( 1932 ) ثابت کرد که با یک مورد استثنایی ساختار یک گراف همبند G می توان به طور کامل از گراف خط خود را بازیافت. [3] بسیاری از خصوصیات دیگر گرافهای خطی با ترجمه خصوصیات گراف زمینه ای از رأس به لبه (یال)ها دنبال می شوند و توسط قضیه ویتنی ، ترجمه مشابه را می توان در جهت دیگر نیز انجام داد. گرافهای خط بدون پنجه هستند و گرافهای گرافهای دو بخشی عالی هستند . گرافهای خطی با نه زیرنویس ممنوع مشخص می شوند و می توانند در زمان خطی تشخیص داده شوند .

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

فهرست

• 1تعریف رسمی
• 2مثال
• 3خواص
  • 3.1خصوصیات ترجمه شده گراف زیر
  • 3.2قضیه ایزومورفیسم ویتنی
  • 3.3گرافهای خطی کاملاً منظم و کامل
  • 3.4سایر خانواده های گراف مربوط
• 4شخصیت پردازی و تشخیص
  • 4.1پارتیشن کلیک
  • 4.2زیرنویس های ممنوع
  • 4.3الگوریتم ها
• 5تکرار عملگر گراف خط
• 6تعمیم ها
  • 6.1گرافهای داخلی و چند وجهی محدب
  • 6.2کل گرافها
  • 6.3چند نگاره
  • 6.4گرافهای خطی
  • 6.5گرافهای خط وزنی
  • 6.6گرافهای خط هایپراگراف
  • 6.7گراف عدم انسجام
• 7یادداشت
• 8منابع
• 9لینک های خارجی

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

با توجه به یک گراف G ، گراف خطی آن L ( G ) یک گراف است به طوری که

• هر راس از L ( G ) نشان دهنده یک لبه (یال)G ؛ و
• دو راس از L ( G ) هستند مجاور اگر و تنها اگر لبه (یال)های مربوط به خود را به اشتراک گذاشتن یک نقطه پایانی مشترک ( "هستند حادثه") در G .

یعنی گراف تقاطع لبه (یال)های G است که نمایانگر هر لبه (یال)با مجموعه دو نقطه انتهایی آن است. [2]

منبع

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