منو
 صفحه های تصادفی
سن نسبی
بیماریهای لثه
مثلث «صورت فلکی»
فرمولهای مولد عددهای اول
گرافهای بازه ای
اوگستن کوشی
شبدر قرمز «داروئی»
Calcium oxide
رشته صنایع چوب شاخه فنی و حرفه ای
اعجاز در هماهنگی قرآن
 کاربر Online
789 کاربر online
تاریخچه ی: گراف بازه‌ای

تفاوت با نگارش: 1

Lines: 1-47Lines: 1-64
 __~~brown:@#18:گراف بازه ها:#@~~__ __~~brown:@#18:گراف بازه ها:#@~~__
 ^@#12:فرض می کنیم مجموعه ای از بازه های باز داریم. اگر این بازه ها را به عنوان رئوس و اتصال دو راس را، به شرط ناتهی بودن اشتراک بازه های متناظر، یال ها در نظر بگیریم، گرافی می توان رسم کرد که به آن گراف بازی ها میگوییم. به عبارت دریگر گراف بازه ای متناظر با بازی های باز {TEX()} {I_1,I_2,...,I_n} {TEX} گرافی است که رئوس آن بازه های باز {TEX()} {I_1,I_2,...,I_n} {TEX} بوده و در صورتی دو راس مجاورند(میانشان یال وجود دارد) که بازه های متناظر آن دو راس اشتراک ناتهی داشته باشند.#@^ ^@#12:فرض می کنیم مجموعه ای از بازه های باز داریم. اگر این بازه ها را به عنوان رئوس و اتصال دو راس را، به شرط ناتهی بودن اشتراک بازه های متناظر، یال ها در نظر بگیریم، گرافی می توان رسم کرد که به آن گراف بازی ها میگوییم. به عبارت دریگر گراف بازه ای متناظر با بازی های باز {TEX()} {I_1,I_2,...,I_n} {TEX} گرافی است که رئوس آن بازه های باز {TEX()} {I_1,I_2,...,I_n} {TEX} بوده و در صورتی دو راس مجاورند(میانشان یال وجود دارد) که بازه های متناظر آن دو راس اشتراک ناتهی داشته باشند.#@^
 *~~purple:تذکر: از حساب دیفرانسیل و انتگرال به یاد داریم که بازه ی باز {TEX()} {(a,b)} {TEX} مجموعه همه اعداد حقیقی بین دو عدد a و b(که شامل خود a و b ===نمی شود===) است.~~ *~~purple:تذکر: از حساب دیفرانسیل و انتگرال به یاد داریم که بازه ی باز {TEX()} {(a,b)} {TEX} مجموعه همه اعداد حقیقی بین دو عدد a و b(که شامل خود a و b ===نمی شود===) است.~~
 __~~red:مـثال:~~__ به عنوان مثال می خواهیم گراف بازه ای متناظر با بازه های زیر را رسـم کنیم: __~~red:مـثال:~~__ به عنوان مثال می خواهیم گراف بازه ای متناظر با بازه های زیر را رسـم کنیم:
  {TEX()} {(6,9),(3,8),(3,4),(2,5),(1,4),(0,2)} {TEX}  {TEX()} {(6,9),(3,8),(3,4),(2,5),(1,4),(0,2)} {TEX}
 ~~green:پاسخ:~~ دو بازه {TEX()} {(1,4),(0,2)} {TEX} اشتراک ناتهی دارند، لذا راس های متناظر این دو بازه را با یک یال به هم وصل می کنیم. ولی دو بازه {TEX()} {(2,5),(0,2)} {TEX} اشتراکشان تهی است، پس راس هایی متناظر این دو بازه به هم وصل نمی شوند. به این ترتیب به همین استدلال نمودار گراف بازه ای شش بازه فوق به صورت زیر در می آید:  ~~green:پاسخ:~~ دو بازه {TEX()} {(1,4),(0,2)} {TEX} اشتراک ناتهی دارند، لذا راس های متناظر این دو بازه را با یک یال به هم وصل می کنیم. ولی دو بازه {TEX()} {(2,5),(0,2)} {TEX} اشتراکشان تهی است، پس راس هایی متناظر این دو بازه به هم وصل نمی شوند. به این ترتیب به همین استدلال نمودار گراف بازه ای شش بازه فوق به صورت زیر در می آید:
 ::{img src=img/daneshnameh_up/5/51/baze-Graph.JPG}:: ::{img src=img/daneshnameh_up/5/51/baze-Graph.JPG}::
 --- ---
 ~~purple:@#15:__نحوه تشخیص گراف بازه ای:__#@~~  ~~purple:@#15:__نحوه تشخیص گراف بازه ای:__#@~~
 سوالی که پیش می آید این است که چگونه می توان تشخیص داد که یک گراف بازه ای است یا نه؟ سوالی که پیش می آید این است که چگونه می توان تشخیص داد که یک گراف بازه ای است یا نه؟
 به عنوان مثال می خواهیم تحقیق کنیم که آیا این گراف بازه ای است یا نه:  به عنوان مثال می خواهیم تحقیق کنیم که آیا این گراف بازه ای است یا نه:
 ::{img src=img/daneshnameh_up/a/a3/example1.jpg}:: ::{img src=img/daneshnameh_up/a/a3/example1.jpg}::
 سعی می کنیم بازه هایی را بیابیم که گراف متناظر آنها (گراف بازه ای آنها) به این صورت باشد. سعی می کنیم بازه هایی را بیابیم که گراف متناظر آنها (گراف بازه ای آنها) به این صورت باشد.
 5 بازه زیر را در نظر می گیریم:  5 بازه زیر را در نظر می گیریم:
 {TEX()} {a=(1,4),b=(5,8),c=(4,6),d=(3,4),e=(7,9)} {TEX} {TEX()} {a=(1,4),b=(5,8),c=(4,6),d=(3,4),e=(7,9)} {TEX}
 (دقت شود که دو بازه a و b نباید اشتراک داشته باشند) (دقت شود که دو بازه a و b نباید اشتراک داشته باشند)
 مشاهده می شود گراف متناظر با این بازه ها به صورت گراف داده شده است پس این گراف بازه ای است. مشاهده می شود گراف متناظر با این بازه ها به صورت گراف داده شده است پس این گراف بازه ای است.
 حال به این نمونه توجه کنید. می خواهیم بازه ای بودن این گراف را بررسی کنیم:  حال به این نمونه توجه کنید. می خواهیم بازه ای بودن این گراف را بررسی کنیم:
 ::{img src=img/daneshnameh_up/5/56/example2.jpg}:: ::{img src=img/daneshnameh_up/5/56/example2.jpg}::
 قبل از بررسی کردن به توضیحات زیر توجه کنید: قبل از بررسی کردن به توضیحات زیر توجه کنید:
 *__در حالت کلی می توان گفت هر گراف دلخواه دارای یک دور از مرتبه 4 گراف بازه ای نمی باشد.__ *__در حالت کلی می توان گفت هر گراف دلخواه دارای یک دور از مرتبه 4 گراف بازه ای نمی باشد.__
 ^@#12:__~~green:برهان~~__ ^@#12:__~~green:برهان~~__
  فرض می کنیم دور مرتبه 4 مقابل خود یک گراف یا قسمتی از یک گراف باشد:  فرض می کنیم دور مرتبه 4 مقابل خود یک گراف یا قسمتی از یک گراف باشد:
 ::{img src=img/daneshnameh_up/4/44/4-cric.jpg}:: ::{img src=img/daneshnameh_up/4/44/4-cric.jpg}::
 نشان می دهیم این گراف و یا گرافی شامل این دور بازه ای نمی باشد. به برهان خلف اگر این گراف یا گراف شامل ایت دور بازه ای باشد: نشان می دهیم این گراف و یا گرافی شامل این دور بازه ای نمی باشد. به برهان خلف اگر این گراف یا گراف شامل ایت دور بازه ای باشد:
 روی محور اعداد حقیقی برای هر یک از راس ها بازه ای به صورت زیر در نظر می گیریم: روی محور اعداد حقیقی برای هر یک از راس ها بازه ای به صورت زیر در نظر می گیریم:
 چون a با b مجاور است باید روی محور اعداد بازه های متناظر با این دو راس دارای اشتراک باشند مطابق شکل: چون a با b مجاور است باید روی محور اعداد بازه های متناظر با این دو راس دارای اشتراک باشند مطابق شکل:
 ::{img src=img/daneshnameh_up/f/f7/example3.jpg}:: ::{img src=img/daneshnameh_up/f/f7/example3.jpg}::
 از طرفی c نیز با b مجاور است و با a مجاور نمی باشد پس بازه متناظر با c با بازه b اشتراک دارد ولی با بازه متناظر a اشتراک ندارد. مطابق شکل: از طرفی c نیز با b مجاور است و با a مجاور نمی باشد پس بازه متناظر با c با بازه b اشتراک دارد ولی با بازه متناظر a اشتراک ندارد. مطابق شکل:
 ::{img src=img/daneshnameh_up/d/d9/example4.jpg}:: ::{img src=img/daneshnameh_up/d/d9/example4.jpg}::
 حال چون d هم با a و هم با c مجاور است پس بازه متناظر با راس d باید به گونه ای اشد که هم به a و هم به c اشتراک داشته باشد و این تناقض است چرا که در این صورت d با b هم اشتراک پیدا می کند در حالی که از b به d یالی رسم نشده است. حال چون d هم با a و هم با c مجاور است پس بازه متناظر با راس d باید به گونه ای اشد که هم به a و هم به c اشتراک داشته باشد و این تناقض است چرا که در این صورت d با b هم اشتراک پیدا می کند در حالی که از b به d یالی رسم نشده است.
 ::{img src=img/daneshnameh_up/0/0a/example5.jpg}:: ::{img src=img/daneshnameh_up/0/0a/example5.jpg}::
  پس فرض خلف باطل و حکم برقرار است.  پس فرض خلف باطل و حکم برقرار است.
 #@^ #@^
 پس در این گراف چون abcd یک دور با طول 4 است بنابر دلایل ذکر شده بازه ای نمی باشد. پس در این گراف چون abcd یک دور با طول 4 است بنابر دلایل ذکر شده بازه ای نمی باشد.
 ::{img src=img/daneshnameh_up/5/56/example2.jpg}:: ::{img src=img/daneshnameh_up/5/56/example2.jpg}::
 --- ---
 ^@#12:روش دیگری که می توان بوسیله آن تعیین نمود که گراف بازه ای نمی باشد این است که اگر در گرافی حفره وجود داشت آن گراف بازه ای نمی باشد. مشاهده می شود این روش تعمیمی بر روش استدلال گفته شده در بالا است. ^@#12:روش دیگری که می توان بوسیله آن تعیین نمود که گراف بازه ای نمی باشد این است که اگر در گرافی حفره وجود داشت آن گراف بازه ای نمی باشد. مشاهده می شود این روش تعمیمی بر روش استدلال گفته شده در بالا است.
  __البته این شرط، یک شرط کافی برای غیر بازه ای بودن گراف است و اگر در گرافی حفره مشاهده نشد نمی توان نتیجه گرفت لزوما گراف بازه ای است.__#@^  __البته این شرط، یک شرط کافی برای غیر بازه ای بودن گراف است و اگر در گرافی حفره مشاهده نشد نمی توان نتیجه گرفت لزوما گراف بازه ای است.__#@^
 به عنوان مثال گراف زیر دارای حفره نمی باشد ولی در عین حال بازه ای نیز نمی باشد: به عنوان مثال گراف زیر دارای حفره نمی باشد ولی در عین حال بازه ای نیز نمی باشد:
 ::{img src=img/daneshnameh_up/e/e4/example6.jpg}:: ::{img src=img/daneshnameh_up/e/e4/example6.jpg}::
 *~~green:یادآوری(تعریف حفره): در گراف ها هر چهار ضلعی یا n ضلعی (n>3) که بدون قطر باشد را یک حفره می گوییم.~~ *~~green:یادآوری(تعریف حفره): در گراف ها هر چهار ضلعی یا n ضلعی (n>3) که بدون قطر باشد را یک حفره می گوییم.~~
 به عنوان مثال در گراف قبلی به صورت: به عنوان مثال در گراف قبلی به صورت:
 ::{img src=img/daneshnameh_up/5/56/example2.jpg}:: ::{img src=img/daneshnameh_up/5/56/example2.jpg}::
 abcd یک حفره محسوب می شود و لذا گراف همان طور که گفته شد بازه ای نمی باشد. abcd یک حفره محسوب می شود و لذا گراف همان طور که گفته شد بازه ای نمی باشد.
 --- ---
 +__~~green:@#15:همچنین ببینید:#@~~__
 +*((نظریه گراف))
 +*((گراف همبند))
 +*((گراف ناهمبند))
 +*((گراف کامل))
 +*((گراف اویلری))
 +*((گراف همیلتونی))
 +*((گراف درختی))
 +*((گراف مسطح))
 +*((گراف چندبخشی))
 +*((گراف k-مکعب))
 +*((گراف چرخ))
 +*((گراف ستاره‌ای))
 +*((گراف اشتراکی))
 +*((گراف منظم))
 +*((گراف جهت‌دار))

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