زمان کنونی: ۰۹ فروردین ۱۴۰۳, ۰۸:۴۳ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

عدد همبندی،مولفه k همبند.

ارسال:
  

mehdi.nine پرسیده:

عدد همبندی،مولفه k همبند.

سلام.
دوستان کسی می تونه یه تعریف ساده از عدد همبندی و مولفه k همبند ترجیحا با مثال بگه؟
مرسی.

۰
ارسال:
  

tayebe68 پاسخ داده:

عدد همبندی،مولفه k همبند.

(۰۶ بهمن ۱۳۹۱ ۰۳:۵۷ ب.ظ)teacherpc نوشته شده توسط:  یک گراف K-همبند (به انگلیسی: K-connected Graph)‏است اگر و تنها اگر برای ناهمبند کردن آن لازم باشد حداقل K راس از رئوس آن را حذف کنیم.
مطلبی که به طور مستقیم از قضیه بالا به دست می‌آید این است که یک گراف دوهمبند نیست اگر و تنها اگر یک راس در آن یافت شود که حذف آن موجب ناهمبند شدن گراف شود.چنین راسی را راس برشی می‌نامند.
حال با توجه به رئوس برشی سعی می‌کنیم تعریفی از مولفه‌های دوهمبند گراف ارائه دهیم.
مولفه دو همبند یک گراف یک مجموعه ماکسیمال از یالهای گراف است که زیر گراف تولید شده توسط آنها دوهمبند باشد.
همان طور که از تعریف بالا بر می‌آید مولفه‌های دوهمبند به صورت مجموعه‌ای از یال‌ها تعریف می‌شود و در نتیجه یک رأس می‌تواند در بیش از یک مولفه دو همبند قرار داشته باشد. پس ما به دنبال یک افراز از یال‌ها هستیم. برای این کار از دو لم زیر کمک می‌گیریم:
لم ۱
یال‌های e و f به یک مولفهٔ دو همبند تعلق دارند اگر و تنها اگر یک دور وجود داشته باشد که شامل هر دوی آن‌ها باشد.
البته یک مولفه دو همبند می‌تواند شامل فقط یک یال باشد و لم بالا فقط مولفه‌های با بیش از یک یال را مد نظر دارد.

لم ۲
هر یال فقط در یک مولفه دوهمبند قرار دارد.
تو clrs هم فکر کنم هست خودم ندارم براتون چک کنم شرمنده!
منبع:ویکی پدیا

۰
ارسال:
  

mehdi.nine پاسخ داده:

عدد همبندی،مولفه k همبند.

ممنون.
آره خودم اینو تو ویکی پدیا خونده بودم ولی درست واسم جا نیفتاد :-(

۰
ارسال:
  

mehdi.nine پاسخ داده:

عدد همبندی،مولفه k همبند.

عدد هم بندی رو فمیدم:
می شه تعداد مولفه های همبند یک گراف.
مثلا فک کنید یه گراف داریم که شامل دوتا مکعبه با ۵ یال
چون دوتا مکعب هر کدوم جداگانه هم بندن عدد همبندی می شه ۲ Big Grin



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد روش های نوشتن عدد n ss311 ۲ ۲,۹۵۳ ۱۳ بهمن ۱۳۹۸ ۰۵:۲۷ ب.ظ
آخرین ارسال: ss311
Question یافتن دو عدد پیچیدگی زمانی O(n) porseshgar ۲ ۳,۵۰۵ ۱۵ بهمن ۱۳۹۷ ۱۲:۱۶ ب.ظ
آخرین ارسال: porseshgar
Sad پیدا کردن xای که حاصل جمع دو عدد Sanazzz ۳ ۳,۱۴۶ ۰۹ بهمن ۱۳۹۷ ۰۳:۰۴ ق.ظ
آخرین ارسال: Sanazzz
  مولفه DC کمک کنین خواهشا Sanazzz ۴ ۳,۵۹۷ ۱۳ آذر ۱۳۹۷ ۰۱:۱۱ ب.ظ
آخرین ارسال: Sanazzz
  سوال طراحی الگوریتم آی تی ۹۲(عدد گلوگاه) tarane1992 ۱۸ ۱۵,۴۰۰ ۲۲ فروردین ۱۳۹۶ ۰۹:۳۲ ق.ظ
آخرین ارسال: *ahoo
  عدد nام کاتالان ali.majed.ha ۲ ۱,۵۱۴ ۱۹ اسفند ۱۳۹۵ ۰۵:۲۸ ب.ظ
آخرین ارسال: ali.majed.ha
  بزرگترین مقدار عدد ثابت K ss311 ۲ ۱,۸۶۴ ۱۵ اسفند ۱۳۹۵ ۰۱:۴۴ ب.ظ
آخرین ارسال: ss311
  بدست اوردن ریشه nم یک عدد مختلط H-Arshad ۱ ۱۷,۰۳۳ ۱۳ آذر ۱۳۹۵ ۰۶:۰۷ ق.ظ
آخرین ارسال: Iranian Wizard
  تبدیل عدد به حرف parizadgh ۱ ۲,۰۶۰ ۰۹ آذر ۱۳۹۵ ۰۸:۵۹ ق.ظ
آخرین ارسال: mostafaheydar1370
  مرتبه زمانی عدد نپر به توان رادیکال n در مقایسه با همین تابع به همراه یک ضریب در توان sMohammad ۱ ۲,۲۷۶ ۲۴ آبان ۱۳۹۵ ۰۲:۰۱ ق.ظ
آخرین ارسال: Saman

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close