گراف خط
گراف خط
گراف غیر تهی G را در نظر بگیرید. اگر به جای هر یال G راأسی در نظر بگیریم و دو رأس را به هم متصل میکنیم.
در صورتی که یالهای متناظر آن دو رأس در G در یک رأس از G با هم مشترک باشند.
گراف حاصل را با نشان داده و آن را گراف خط مینامیم.
قضیه: اگر G و منتظم باشد و دارای n راس، آنگاه L(G) نیز منتظم و از درجه میباشد.
اثبات: هر یال گراف G به دو رأس ختم میشود که به هر یک از این رأسها به جز یال مذکور ، یال دیگر وارد میشوند.
یال مذکور تنها با این یال رأس مشترک دارد و در این یال رأس گراف است که به رأس دیگر متصل است.
پس یک گراف منتظم است.
نگارخانه
منابع
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].