منو
 کاربر Online
1123 کاربر online

گراف خط یک گراف

تازه کردن چاپ
علوم ریاضی > علو م رایانه
(cached)



این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


گراف خط

گراف غیر تهی را در نظر بگیرید. اگر به جای هر یال،‌ راسی در نظر بگیریم و دو راس را به هم متصل کنیم در صورتی که یالهای متناظر با آن دو راس در ،‌ در یک راس از با هم مشترک باشند. گراف حاصل را با نشان داده و آن را گراف خط می نامیم.

مثال

img/daneshnameh_up/d/d0/mco0076a.jpg

همچنین در گراف غیر یک ریخت ممکن است گراف خطهای یک ریخت داشته باشند:
img/daneshnameh_up/6/68/mco0076b.jpg


قضیه

اگر ، منتظم باشد و دارای راس،‌ آنگاه نیز منتظم و از درجه می باشد.
اثبات
هر یال گراف به دو راس ختم می شود که به هر یک از این راس ها به جز یال مذکور، یال دیگر وارد می شوند. یال مذکور تنها با این یال راس مشترک دارد و در این یال راس گراف است که به راس دیگر متصل است. پس یک گراف منتظم است.

پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0082.pdf

همچنین ببینید




تعداد بازدید ها: 11295


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..