گراف خط

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

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

گراف حاصل را با ${\displaystyle L(G)}$ نشان داده و آن را گراف خط می‌نامیم.

geraph-khat

geraoh-khat1

قضیه: اگر G و ${\displaystyle -r}$ منتظم باشد و دارای n راس، آنگاه L(G) نیز منتظم و از درجه ${\displaystyle 2(r-1)}$ می‌باشد.

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

یال مذکور تنها با این ${\displaystyle Z(r-1)}$ یال رأس مشترک دارد و در این یال رأس گراف ${\displaystyle L(g)}$ است که به ${\displaystyle Z(r-1)}$ رأس دیگر متصل است.

پس ${\displaystyle L(G)}$ یک گراف ${\displaystyle Zr-Z}$ منتظم است.

Kenneth H, Rosen (1998). "graphs". Discrete Mathematics and its Applications. SIGS Reference Library. William C Brown Pub; 4th edition. ISBN 0072899050. Retrieved 2007. Check date values in: |بازبینی= (help)

• [daneshnameh.roshd.ir daneshnameh.roshd.ir] مقدار |نشانی= را بررسی کنید (کمک). پارامتر |عنوان= یا |title= ناموجود یا خالی (کمک)