با سلام.
دوستان ابهامی درباره‌ی گراف‌های همیلتونی هست... طبق ۲ قضیه‌ی گریمالدی داریم:
دو رأس x و y غیر مجاور باشند و:
[tex]|V|=n\geq 3, \ \ deg(x) deg(y)\geq n[/tex]
آنگاه دور همیلتونی دارد
و
برای رأس در گراف
[tex]|V|=n\geq 3, \ \ deg(v)\geq \frac{n}{2}[/tex]
آنگاه دور همیلتونی دارد..
تا اینجا مشکلی نیست٬ در یکی از کتاب‌ها اما این دو قضیه را غلط فرض کرده و استدلالش هم سیکل [tex]C_{6}[/tex] بوده... به نظر شما اشکال این موضوع کجاست؟
یعنی این دو قضیه٬ کمک برای تشخیص گراف‌های همیلتونی هستند و جامعیت ندارند؟
سلام. این شرط ها شرط کافی هستن. اگه گراف این شرط رو داشته باشه حتماً همیلتونیه. ولی گراف همیلتونی ازوماً این شرطو نداره. گرافی رو درنظر بگیرید که از ۱۰ تا راس درجه دو تشکیل شده باشه و فقط یک دور داشته باشه (یک دور به طول ۱۰). این گراف همیلتونیه.