گراف خط

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

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

گراف حاصل را با $L(G)$

نشان داده و آن را گراف خط می‌نامیم.

geraph-khat

geraoh-khat1

قضیه: اگر G و $-r$

منتظم باشد و دارای n راس، آنگاه L(G) نیز منتظم و از درجه

2(r-1)

می‌باشد.

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

یال دیگر وارد می‌شوند.

یال مذکور تنها با این $Z(r-1)$

یال رأس مشترک دارد و در این یال رأس گراف

L(g)

است که به

Z(r-1)

رأس دیگر متصل است.

پس $L(G)$

یک گراف

Zr-Z

منتظم است.

نگارخانه

منابع

Kenneth H, Rosen (1998). "graphs". Discrete Mathematics and its Applications. SIGS Reference Library (به انگلیسی). William C Brown Pub; 4th edition. Retrieved 2007.

[daneshnameh.roshd.ir daneshnameh.roshd.ir].