سلام
اجزائ دو همبند گزاف روبه رو چند تا است ؟
سوالم اینه که ایا یال های شماره ۸-۹ و ۸-۱۰ و ۶-۵ رو درست به عنوان اجزائ دو همبند گرفته ؟
(۰۶ بهمن ۱۳۹۱ ۰۲:۰۴ ق.ظ)ana_12345 نوشته شده توسط: سلام
اجزائ دو همبند گزاف روبه رو چند تا است ؟
سوالم اینه که ایا یال های شماره ۸-۹ و ۸-۱۰ و ۶-۵ رو درست به عنوان اجزائ دو همبند گرفته ؟
ببخشید شماره یالها توی این یکی پیوست هست که جوابش .
میشه تعریف جزئ دو همبند رو بگید ؟ و اینکه چه جوری تشخیصش بدیم ؟
یک گراف K-همبند (به انگلیسی: K-connected Graph)است اگر و تنها اگر برای ناهمبند کردن آن لازم باشد حداقل K راس از رئوس آن را حذف کنیم.
مطلبی که به طور مستقیم از قضیه بالا به دست می‌آید این است که یک گراف دوهمبند نیست اگر و تنها اگر یک راس در آن یافت شود که حذف آن موجب ناهمبند شدن گراف شود.چنین راسی را راس برشی می‌نامند.
حال با توجه به رئوس برشی سعی می‌کنیم تعریفی از مولفه‌های دوهمبند گراف ارائه دهیم.
مولفه دو همبند یک گراف یک مجموعه ماکسیمال از یالهای گراف است که زیر گراف تولید شده توسط آنها دوهمبند باشد.
همان طور که از تعریف بالا بر می‌آید مولفه‌های دوهمبند به صورت مجموعه‌ای از یالها تعریف می‌شود و در نتیجه یک رأس می‌تواند در بیش از یک مولفه دو همبند قرار داشته باشد. پس ما به دنبال یک افراز از یالها هستیم. برای این کار از دو لم زیر کمک می‌گیریم:
لم ۱
یالهای e و f به یک مولفهٔ دو همبند تعلق دارند اگر و تنها اگر یک دور وجود داشته باشد که شامل هر دوی آنها باشد.
البته یک مولفه دو همبند می‌تواند شامل فقط یک یال باشد و لم بالا فقط مولفه‌های با بیش از یک یال را مد نظر دارد.
لم ۲
هر یال فقط در یک مولفه دوهمبند قرار دارد.
تو clrs هم فکر کنم هست خودم ندارم براتون چک کنم شرمنده!
منبع:ویکی پدیا
خیلی خیلی ممنونم از پاسخ فوق العادتون . ممنون خیلی گیج شده بودم الان یه دسته بندی تو مغزم درست شد .
ایشالا رتبه زیر ۱۰ شین .
با ارزوی موفقیت .
(۰۶ بهمن ۱۳۹۱ ۰۵:۳۵ ب.ظ)ana_12345 نوشته شده توسط: یک گراف K-همبند (به انگلیسی: K-connected Graph)است اگر و تنها اگر برای ناهمبند کردن آن لازم باشد حداقل K راس از رئوس آن را حذف کنیم.مرسی دوست عزیز حالا با این توجه تعریف رسمی و استاندار کدومه اولی یا دومی؟!
مطلبی که به طور مستقیم از قضیه بالا به دست می‌آید این است که یک گراف دوهمبند نیست اگر و تنها اگر یک راس در آن یافت شود که حذف آن موجب ناهمبند شدن گراف شود.چنین راسی را راس برشی می‌نامند.
حال با توجه به رئوس برشی سعی می‌کنیم تعریفی از مولفه‌های دوهمبند گراف ارائه دهیم.
مولفه دو همبند یک گراف یک مجموعه ماکسیمال از یالهای گراف است که زیر گراف تولید شده توسط آنها دوهمبند باشد.
همان طور که از تعریف بالا بر می‌آید مولفه‌های دوهمبند به صورت مجموعه‌ای از یالها تعریف می‌شود و در نتیجه یک رأس می‌تواند در بیش از یک مولفه دو همبند قرار داشته باشد.
تعریف اولی رو من در کتب کنکوری ندیدم!جایی رسما عنوان شده؟!
اما تعریف دوم در کتاب ساختمان یوسفی با عنوان مولفه های دوطرف همبند(Biconnected) بیان شده.
سوالتونو نفهمیدم ؟
(۰۷ بهمن ۱۳۹۱ ۰۱:۱۹ ق.ظ)ana_12345 نوشته شده توسط: ک گراف K-همبند (به انگلیسی: K-connected Graph)است اگر و تنها اگر برای ناهمبند کردن آن لازم باشد حداقل K راس از رئوس آن را حذف کنیم.منظورم این بود که تعریف اول رو کتب کنکوری گفتن؟
مطلبی که به طور مستقیم از قضیه بالا به دست می‌آید این است که یک گراف دوهمبند نیست اگر و تنها اگر یک راس در آن یافت شود که حذف آن موجب ناهمبند شدن گراف شود.چنین راسی را راس برشی می‌نامند.
سلام
توی سوال من تو پست اول ، خواسته که مولفه های دوهمبندی رو تشخیص بدیم و من با توجه به این توضیح فهمیدم ۲ مجموعه مشخص شده تو شکل به این دلیل
مولفه دو همبند یک گراف یک مجموعه ماکسیمال از یالهای گراف است که زیر گراف تولید شده توسط آنها دوهمبند باشد.
همان طور که از تعریف بالا بر می‌آید مولفه‌های دوهمبند به صورت مجموعه‌ای از یالها تعریف می‌شود و در نتیجه یک رأس می‌تواند در بیش از یک مولفه دو همبند قرار داشته باشد. پس ما به دنبال یک افراز از یالها هستیم. برای این کار از دو لم زیر کمک می‌گیریم:
لم ۱
یالهای e و f به یک مولفهٔ دو همبند تعلق دارند اگر و تنها اگر یک دور وجود داشته باشد که شامل هر دوی آنها باشد.
و یالهایی که شماره هاش رو گفتم به این دلیل
البته یک مولفه دو همبند می‌تواند شامل فقط یک یال باشد و لم بالا فقط مولفه‌های با بیش از یک یال را مد نظر دارد.
لم ۲
هر یال فقط در یک مولفه دوهمبند قرار دارد.
در سوال به عنوان مولفه دو همبندی گرفته شده
اما سوالی که اقای mehdi و operation داشتن روی این موضوع هست
دوستان من پاسخ کامل نزدم .
اما برای من چون جوابم داده شد تشکر کردم .
(۰۶ بهمن ۱۳۹۱ ۰۳:۵۷ ب.ظ)teacherpc نوشته شده توسط: یک گراف K-همبند (به انگلیسی: K-connected Graph)است اگر و تنها اگر برای ناهمبند کردن آن لازم باشد حداقل K راس از رئوس آن را حذف کنیم.
مطلبی که به طور مستقیم از قضیه بالا به دست می‌آید این است که یک گراف دوهمبند نیست اگر و تنها اگر یک راس در آن یافت شود که حذف آن موجب ناهمبند شدن گراف شود.چنین راسی را راس برشی می‌نامند.
و اینکه پس تو گراف شکل بالا ما راس برشی داریم در کل به این گراف، گراف دو همبند پس نباید بگیم ؟ درست ؟
یعنی گراف ۲ همبند نیست اما مولفه دو همبندی دارد .
طبق همین توضیحاتteacherpc لطف کرده و گذاشت آره درسته. قبلا اینو تو ویکی خوندم ولی درست نفهمیدم الان که یکی دو بار خوندم فهمیدمش
طبق تعریف اگر در یکی از مولفه ها یک راس رو حذف کنیم و گراف ناهمبند نشه اون مولفه مولفه ی دو همبند حساب می شه
حالا اگر در ۸ - ۹ راس ۸ رو حذف کنیم تک راس ۹ باقی می مونه و تک راس هم هم بنده به همین ترتیب برای ۱۰-۸ و ۵-۶ می شه اثبات کرد.
درست شد؟
وقت نشد تاپیکتون رو کامل بخونم ولی فرصتم نمیشه دوباره چک کنم شرمنده این جمع بندی اخر من نمیزاره زیاد تو تاپیکها شرکت کنم یا اگه اشتباهی بوده یانه سهوی عفو کنید
بابا دمتون گرم
من که در حد سوالم فیض بردم و مشکلم حل شد .
شما و operation سوال داشتین حالا operation هم میاد می گه منم می دونستم
باشه ما خوشحالیم سوال دوستان رفع شد
پس تاپیک : پاسخ کامل
همه موفق باشین