نمایش مبدأ برای گراف خط

== گراف خط ==
[[گراف]] غیر تهی G را در نظر بگیرید. اگر به جای هر [[یال]] G راأسی در نظر بگیریم و دو [[رأس]] را به هم متصل می‌کنیم.

در صورتی که یال‌های متناظر آن دو رأس در G در یک رأس از G با هم مشترک باشند.

گراف حاصل را با <math>L(G)</math> نشان داده و آن را گراف خط می‌نامیم.

[[پرونده:Geraph-khat.jpg|بندانگشتی|geraph-khat]]

[[پرونده:Geraoh-khat1.jpg|بندانگشتی|geraoh-khat1]]

قضیه: اگر G و <math>-r</math> منتظم باشد و دارای n راس، آنگاه L(G) نیز منتظم و از درجه <math>2(r-1)</math> می‌باشد.

اثبات: هر یال گراف G به دو رأس ختم می‌شود که به هر یک از این رأس‌ها به جز یال مذکور ، <math>r-1</math> یال دیگر وارد می‌شوند.

یال مذکور تنها با این <math>Z(r - 1)</math> یال رأس مشترک دارد و در این یال رأس گراف <math>L(g)</math> است که به <math>Z(r - 1)</math> رأس دیگر متصل است.

پس <math>L(G)</math> یک گراف <math>Zr - Z</math> منتظم است.

== نگارخانه ==
<gallery>
File:Line graph construction 1.svg|<!--Graph G-->
File:Line graph construction 2.svg|<!--Vertices in L(G) constructed from edges in G-->
File:Line graph construction 3.svg|<!--Added edges in L(G)-->
File:Line graph construction 4.svg|<!--The line graph L(G)-->
</gallery>

== منابع ==
{{پانویس}}
{{یادکرد کتاب | نام خانوادگی۱ = Kenneth H| نام۱ = Rosen | فصل = graphs| عنوان = Discrete Mathematics and its Applications| سری = SIGS Reference Library | سال = 1998| ناشر = William C Brown Pub; 4th edition | شابک = 0072899050| نشانی = https://www.amazon.com/Discrete-Mathematics-Applications-Kenneth-Rosen/dp/0072899050| بازبینی = 2007| زبان = en}}
* {{یادکرد وب|نویسنده = |نشانی = daneshnameh.roshd.ir|عنوان = | ناشر = |تاریخ = |تاریخ بازدید =}}

[[رده:خانواده‌های گراف]]
[[رده:رده‌های تقاطعی گراف‌ها]]
[[رده:عملیات گراف]]