ہملٹونین گراف

سانچہ:اصطلاح برابر ریاضی کی شاخ "نظریہ گراف" میں متصل گراف کو ہملٹونین گراف کہا جاتا ہے اگر ایسا "دورہ" ممکن ہو جس میں گراف کے تمام راس شامل ہوں۔ اور ایسے دورہ کو ہملٹونین دورہ کہا جائے گا۔

مثال کے طور پر شطرنج کے $n\times n$ تختہ پر کیا یہ ممکن ہے کہ گھوڑا اپنی چال چلتا ہوا تمام خانوں کا دورہ کرے اور اسی خانے پر واپس پہنچے جہاں سے چلا تھا؟ اس میں ہر خانے کو قمہ سمجھتے ہوئے گراف بنایا جا سکتا ہے اور جن دو راس کے درمیان گھوڑے کی چال ممکن ہو وہاں کنارہ۔ یہ ثابت کیا جا سکتا ہے کہ $8\times 8$ تختہ پر ایسا دورہ (ہملٹونین دورہ) ممکن ہے۔

ڈائرک مسلئہ اثباتی

سادہ گراف ہو جس کی راس n ہوں اور $n\ge 3$ ہو۔ اگر قمہ کا درجہ

$deg(v)\ge \frac{n}{2}$

ہر قمہ v کے لیے، تو یہ گراف ہملٹونین ہو گا۔

عور مسلئہ اثباتی

سادہ گراف ہو جس کی راس n ہوں اور $n\ge 3$ ہو۔ اگر راس کا درجہ

$deg(v)+deg(w)\ge n$

ہر دو ناملمس راس v اور w کے جوڑے کے لیے، تو یہ گراف ہملٹونین ہو گا۔

مزید دیکھیے

==بیرونی روابط ==* سانچہ:ریاضی مدد