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

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

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

  • تذکر: از حساب دیفرانسیل و انتگرال به یاد داریم که بازه ی باز مجموعه همه اعداد حقیقی بین دو عدد a و b(که شامل خود a و b نمی شود) است.
مـثال: به عنوان مثال می خواهیم گراف بازه ای متناظر با بازه های زیر را رسـم کنیم:

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


نحوه تشخیص گراف بازه ای:
سوالی که پیش می آید این است که چگونه می توان تشخیص داد که یک گراف بازه ای است یا نه؟
به عنوان مثال می خواهیم تحقیق کنیم که آیا این گراف بازه ای است یا نه:
تصویر

سعی می کنیم بازه هایی را بیابیم که گراف متناظر آنها (گراف بازه ای آنها) به این صورت باشد.
5 بازه زیر را در نظر می گیریم:

(دقت شود که دو بازه a و b نباید اشتراک داشته باشند)
مشاهده می شود گراف متناظر با این بازه ها به صورت گراف داده شده است پس این گراف بازه ای است.

حال به این نمونه توجه کنید. می خواهیم بازه ای بودن این گراف را بررسی کنیم:
تصویر

قبل از بررسی کردن به توضیحات زیر توجه کنید:
  • در حالت کلی می توان گفت هر گراف دلخواه دارای یک دور از مرتبه 4 گراف بازه ای نمی باشد.
برهان
فرض می کنیم دور مرتبه 4 مقابل خود یک گراف یا قسمتی از یک گراف باشد:
تصویر

نشان می دهیم این گراف و یا گرافی شامل این دور بازه ای نمی باشد. به برهان خلف اگر این گراف یا گراف شامل ایت دور بازه ای باشد:
روی محور اعداد حقیقی برای هر یک از راس ها بازه ای به صورت زیر در نظر می گیریم:
چون a با b مجاور است باید روی محور اعداد بازه های متناظر با این دو راس دارای اشتراک باشند مطابق شکل:
تصویر

از طرفی c نیز با b مجاور است و با a مجاور نمی باشد پس بازه متناظر با c با بازه b اشتراک دارد ولی با بازه متناظر a اشتراک ندارد. مطابق شکل:
تصویر

حال چون d هم با a و هم با c مجاور است پس بازه متناظر با راس d باید به گونه ای اشد که هم به a و هم به c اشتراک داشته باشد و این تناقض است چرا که در این صورت d با b هم اشتراک پیدا می کند در حالی که از b به d یالی رسم نشده است.
تصویر

پس فرض خلف باطل و حکم برقرار است.

پس در این گراف چون abcd یک دور با طول 4 است بنابر دلایل ذکر شده بازه ای نمی باشد.
تصویر


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

به عنوان مثال گراف زیر دارای حفره نمی باشد ولی در عین حال بازه ای نیز نمی باشد:
تصویر

  • یادآوری(تعریف حفره): در گراف ها هر چهار ضلعی یا n ضلعی (n>3) که بدون قطر باشد را یک حفره می گوییم.
به عنوان مثال در گراف قبلی به صورت:
تصویر

abcd یک حفره محسوب می شود و لذا گراف همان طور که گفته شد بازه ای نمی باشد.

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

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

  • تذکر: از حساب دیفرانسیل و انتگرال به یاد داریم که بازه ی باز مجموعه همه اعداد حقیقی بین دو عدد a و b(که شامل خود a و b نمی شود) است.
مـثال: به عنوان مثال می خواهیم گراف بازه ای متناظر با بازه های زیر را رسـم کنیم:

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


نحوه تشخیص گراف بازه ای:
سوالی که پیش می آید این است که چگونه می توان تشخیص داد که یک گراف بازه ای است یا نه؟
به عنوان مثال می خواهیم تحقیق کنیم که آیا این گراف بازه ای است یا نه:
تصویر

سعی می کنیم بازه هایی را بیابیم که گراف متناظر آنها (گراف بازه ای آنها) به این صورت باشد.
5 بازه زیر را در نظر می گیریم:

(دقت شود که دو بازه a و b نباید اشتراک داشته باشند)
مشاهده می شود گراف متناظر با این بازه ها به صورت گراف داده شده است پس این گراف بازه ای است.

حال به این نمونه توجه کنید. می خواهیم بازه ای بودن این گراف را بررسی کنیم:
تصویر

قبل از بررسی کردن به توضیحات زیر توجه کنید:
  • در حالت کلی می توان گفت هر گراف دلخواه دارای یک دور از مرتبه 4 گراف بازه ای نمی باشد.
برهان
فرض می کنیم دور مرتبه 4 مقابل خود یک گراف یا قسمتی از یک گراف باشد:
تصویر

نشان می دهیم این گراف و یا گرافی شامل این دور بازه ای نمی باشد. به برهان خلف اگر این گراف یا گراف شامل ایت دور بازه ای باشد:
روی محور اعداد حقیقی برای هر یک از راس ها بازه ای به صورت زیر در نظر می گیریم:
چون a با b مجاور است باید روی محور اعداد بازه های متناظر با این دو راس دارای اشتراک باشند مطابق شکل:
تصویر

از طرفی c نیز با b مجاور است و با a مجاور نمی باشد پس بازه متناظر با c با بازه b اشتراک دارد ولی با بازه متناظر a اشتراک ندارد. مطابق شکل:
تصویر

حال چون d هم با a و هم با c مجاور است پس بازه متناظر با راس d باید به گونه ای اشد که هم به a و هم به c اشتراک داشته باشد و این تناقض است چرا که در این صورت d با b هم اشتراک پیدا می کند در حالی که از b به d یالی رسم نشده است.
تصویر

پس فرض خلف باطل و حکم برقرار است.

پس در این گراف چون abcd یک دور با طول 4 است بنابر دلایل ذکر شده بازه ای نمی باشد.
تصویر


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

به عنوان مثال گراف زیر دارای حفره نمی باشد ولی در عین حال بازه ای نیز نمی باشد:
تصویر

  • یادآوری(تعریف حفره): در گراف ها هر چهار ضلعی یا n ضلعی (n>3) که بدون قطر باشد را یک حفره می گوییم.
به عنوان مثال در گراف قبلی به صورت:
تصویر

abcd یک حفره محسوب می شود و لذا گراف همان طور که گفته شد بازه ای نمی باشد.


تاریخ شماره نسخه کاربر توضیح اقدام
 یکشنبه 28 خرداد 1385 [09:59 ]   2   مرادی فر      جاری 
 سه شنبه 16 خرداد 1385 [17:21 ]   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 در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..