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

Question

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

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

Answer 1

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

قضیه: اگر گراف $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$ را مطالعه نمایید که زیر بخشی هم با عنوان شرایط ضروری برای گرافهای همیلتونی دارد.