پرش به محتوا

گراف خط

از ویکی‌پدیا، دانشنامهٔ آزاد

گراف خط

[ویرایش]

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

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

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

geraph-khat
geraoh-khat1

قضیه: اگر 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. {{cite book}}: Check date values in: |بازبینی= (help)

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