گراف خط

گراف خط

گراف غیر تهی 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$ منتظم است.

نگارخانه

• 
• 
• 
• 

منابع

• الگو:یادکرد وب