مشتق گیری ضمنی

[فلفل نمك]

قضیه: اگر G یک گراف ساده و دو بخشی از مرتبه p و اندازه q باشد آنگاه

[فلفل نمك]

برهان:
چون گراف دو بخشی است مطابق قضیه قبل حداکثر یال آن برابر است با:
که m تعداد یال بخش X و n تعداد یال بخش Y است.(بیشترین تعداد یال مربوط به زمانی است که گراف، دو بخشی کامل باشد).

[فلفل نمك]

برهان:
چون گراف دو بخشی است مطابق قضیه قبل حداکثر یال آن برابر است با:
که m تعداد یال بخش X و n تعداد یال بخش Y است.(بیشترین تعداد یال مربوط به زمانی است که گراف، دو بخشی کامل باشد).
از طرفی می دانیم که: پس: , داریم:

چون u آهنگ تغییرات تعداد یال را نشان می دهد و پس از نتیجه می شود که:
ضمنا" می دانیم که:

پس بیشترین مقدار u در نقطه اتفاق می افتد، یعنی:

بنابراین تعداد کل یالها نمی تواند از بیشتر باش

[فلفل نمك]

گراف چرخ

هر گراف که دارای راس باشد که و یکی از رئوس از درجه ی و بقیه از درجه ی سه باشند، را یک گراف چرخ می نامیم- مانند مثال های زیر:

گراف چرخ راسی را با نمایش می دهیم.

[فلفل نمك]

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

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

[فلفل نمك]

مـثال: به عنوان مثال می خواهیم گراف بازه ای متناظر با بازه های زیر را رسـم کنیم:

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

[فلفل نمك]

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

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

[فلفل نمك]

بازه زیر را در نظر می گیریم:

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

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

[فلفل نمك]

• در حالت کلی می توان گفت هر گراف دلخواه دارای یک دور از مرتبه 4 گراف بازه ای نمی باشد.

برهان
فرض می کنیم دور مرتبه 4 مقابل خود یک گراف یا قسمتی از یک گراف باشد