به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+1 امتیاز
256 بازدید
در دانشگاه توسط OXIDE
ویرایش شده توسط erfanm

ثابت کنید در یک گراف ساده ، اگر با حذف $k$ راس ، گراف به $k+1$ قسمت یا بیشتر تفکیک شود، گراف همیلتنی نیست.

اگر روش های دیگه ای هم دارید بگید.

1 پاسخ

+1 امتیاز
توسط erfanm
ویرایش شده توسط erfanm

با استفاده از قضیه زیر این حکم نتیجه شده است.

قضیه: اگر گراف $ G $ همیلتونی باشد آنگاه به ازای هر زیر مجموعه سره $S \subseteq V(G) $ داریم: $ \kappa (G -S) \leq \mid S \mid $ که در ان $ \kappa (G -S) $ تعداد مولفه های همبندی گراف حاصل از حذف رئوس مجموعه $S $ است.

اثبات: فرض کنید که $ \kappa (G -S)=k$ لذا فرض کنید که $k $ مولفه ی همبندی $ G_{1} , G_{2} ,... ,G_{k} $ را داریم. فرض کنید $C=( v_{1} ,v_{2} ,..., v_{n}, v_{1} ) $ دور همیلتونی گراف $ G$ باشد بدون کاستن از کلیت می توان فرض کرد که $v_{1} \in G_{1} $ و همچنین به ازای هر $1 \leq j \leq k $ راس $v_{{i} _{j} } $ آخرین راس از $ C $ باشد که در $G_{j} $ قرار دارد چون $ G_{j} $ و $G_{j+1} $ متصل نیستند لذا باید $ v_{{i} _{j} +1} \in S $ باشد (به ازای هر $1 \leq j \leq k $) یعنی $\kappa (G -S)=k \leq \mid S \mid $

برای اطلاعات بیشتر در زمینه گراف های همیلتنونی میتوانید کتاب $Graphs \ \& \ Digraphs$

$By \ \ Gary \ \ Chartrand, Linda \ \ Lesniak,\ \ Ping \ \ Zhang$ را مطالعه نمایید که زیر بخشی هم با عنوان شرایط ضروری برای گرافهای همیلتونی دارد.

حمایت مالی


کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...