-
مدیر بازنشسته
قضیه: اگر G یک گراف ساده و دو بخشی از مرتبه p و اندازه q باشد آنگاه
-
-
مدیر بازنشسته
برهان:
چون گراف دو بخشی است مطابق قضیه قبل حداکثر یال آن برابر است با:
که m تعداد یال بخش X و n تعداد یال بخش Y است.(بیشترین تعداد یال مربوط به زمانی است که گراف، دو بخشی کامل باشد).
-
-
مدیر بازنشسته
-
-
مدیر بازنشسته
-
-
مدیر بازنشسته
-
-
مدیر بازنشسته
-
-
مدیر بازنشسته
نحوه تشخیص گراف بازه ای:
سوالی که پیش می آید این است که چگونه می توان تشخیص داد که یک گراف بازه ای است یا نه؟
به عنوان مثال می خواهیم تحقیق کنیم که آیا این گراف بازه ای است یا نه:
سعی می کنیم بازه هایی را بیابیم که گراف متناظر آنها (گراف بازه ای آنها) به این صورت باشد
-
-
مدیر بازنشسته
بازه زیر را در نظر می گیریم:
(دقت شود که دو بازه a و b نباید اشتراک داشته باشند)
مشاهده می شود گراف متناظر با این بازه ها به صورت گراف داده شده است پس این گراف بازه ای است.
حال به این نمونه توجه کنید. می خواهیم بازه ای بودن این گراف را بررسی کنی
-
-
مدیر بازنشسته
- در حالت کلی می توان گفت هر گراف دلخواه دارای یک دور از مرتبه 4 گراف بازه ای نمی باشد.
برهان
فرض می کنیم دور مرتبه 4 مقابل خود یک گراف یا قسمتی از یک گراف باشد
-
کلمات کلیدی این موضوع
مجوز های ارسال و ویرایش
- شما نمیتوانید موضوع جدیدی ارسال کنید
- شما امکان ارسال پاسخ را ندارید
- شما نمیتوانید فایل پیوست کنید.
- شما نمیتوانید پست های خود را ویرایش کنید
-
مشاهده قوانین
انجمن