14 شهریور 1391, 12:00 ب.ظ
با سلام.
دوستان ابهامی دربارهی گرافهای همیلتونی هست... طبق ۲ قضیهی گریمالدی داریم:
دو رأس 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] بوده... به نظر شما اشکال این موضوع کجاست؟
یعنی این دو قضیه٬ کمک برای تشخیص گرافهای همیلتونی هستند و جامعیت ندارند؟
دوستان ابهامی دربارهی گرافهای همیلتونی هست... طبق ۲ قضیهی گریمالدی داریم:
دو رأس 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] بوده... به نظر شما اشکال این موضوع کجاست؟
یعنی این دو قضیه٬ کمک برای تشخیص گرافهای همیلتونی هستند و جامعیت ندارند؟