منو
 کاربر Online
850 کاربر online
تاریخچه ی: گرافهای یکریخت

در حال مقایسه نگارشها

نگارش واقعی نگارش:2


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


گراف های یکریخت

هرگراف به طور یکتا با آن مشخص می شود یعنی اگر دو گراف مجموعه رئوس و یالهای یکسانی داشته باشند،‌نمودار یکسان نیز خواهند داشت و اساساً خواهد بود.
اما فراتر از این، گراف هایی هستند که همانند نیستند ولیکن نمودارهای یکسان دارند مانند:
img/daneshnameh_up/8/8e/mco0049a.jpg

چنین گراف هایی را یکریخت می نامیم.
از آنجا که در مقدمه شهود این مفهوم داده شده است مستقیماً به سراغ تعریف و کاربرد می رویم:
دو گراف و را یکریخت گوییم اگر توابع دو طرفه


موجود باشند به طوری که در ، به متصل باشد اگر و تنها اگر تحت تبدیل بالا به متصل باشد.
به عبارت دیگر تبدیلی دو طرفه برای رئوسو یالهای متناظر آنها موجود باشد که را به تبدیل کند که در مثال قبل تبدیل زیر را به تبدیل می کند:


توصیه می گردد حتماً شهود یکریختی را که در " مقدمه " بحث شده بود را مطالعه کرده باشید.
بدین ترتیب مجموعه کل گراف های موجود در دنیا! به دسته های یکریختی افراز می گردد یعنی برای هر گراف دلخواه دسته هم ارزی ای وجود دارد که تمام گراف های آن با گراف دلخواه هم ارزند!
از این به بعد ما غالباً یکریختی را به مفهوم برابری و یکسانی می گیریم زیرا دو گراف یکریخت تنها در نام و نحوه رسم متفاوت می باشند و خصوصیات یکسان خواهند داشت.

تمرین

آیا ممکن است متعلق به یک دسته یک ریختی باشند ولی دنباله درجه های آنها متفاوت باشد؟
جواب
به وضوح خیر. زیرا در این صورت هیچ تبدیلی نمی تواند آنها را به هم تبدیل کند.

نتیجه

پس اولین شرط لازم و نه کافی برای یکریخت بودن، داشتن درجه های رئوس یکسان می باشد.

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

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

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





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


گراف های یکریخت

هرگراف به طور یکتا با آن مشخص می شود یعنی اگر دو گراف مجموعه رئوس و یالهای یکسانی داشته باشند،‌نمودار یکسان نیز خواهند داشت و اساساً خواهد بود.
اما فراتر از این، گراف هایی هستند که همانند نیستند ولیکن نمودارهای یکسان دارند مانند:
img/daneshnameh_up/8/8e/mco0049a.jpg

چنین گراف هایی را یکریخت می نامیم.
از آنجا که در مقدمه شهود این مفهوم داده شده است مستقیماً به سراغ تعریف و کاربرد می رویم:
دو گراف و را یکریخت گوییم اگر توابع دو طرفه


موجود باشند به طوری که در ، به متصل باشد اگر و تنها اگر تحت تبدیل بالا به متصل باشد.
به عبارت دیگر تبدیلی دو طرفه برای رئوسو یالهای متناظر آنها موجود باشد که را به تبدیل کند که در مثال قبل تبدیل زیر را به تبدیل می کند:


توصیه می گردد حتماً شهود یکریختی را که در " مقدمه " بحث شده بود را مطالعه کرده باشید.
بدین ترتیب مجموعه کل گراف های موجود در دنیا! به دسته های یکریختی افراز می گردد یعنی برای هر گراف دلخواه دسته هم ارزی ای وجود دارد که تمام گراف های آن با گراف دلخواه هم ارزند!
از این به بعد ما غالباً یکریختی را به مفهوم برابری و یکسانی می گیریم زیرا دو گراف یکریخت تنها در نام و نحوه رسم متفاوت می باشند و خصوصیات یکسان خواهند داشت.

تمرین

آیا ممکن است متعلق به یک دسته یک ریختی باشند ولی دنباله درجه های آنها متفاوت باشد؟
جواب
به وضوح خیر. زیرا در این صورت هیچ تبدیلی نمی تواند آنها را به هم تبدیل کند.

نتیجه

پس اولین شرط لازم و نه کافی برای یکریخت بودن، داشتن درجه های رئوس یکسان می باشد.

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

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

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




تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 14 آبان 1385 [11:22 ]   3   زینب معزی      جاری 
 یکشنبه 19 شهریور 1385 [10:02 ]   2   زینب معزی      v  c  d  s 
 یکشنبه 19 شهریور 1385 [06:00 ]   1   زینب معزی      v  c  d  s 


ارسال توضیح جدید
الزامی
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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..