ہملٹونین مخطط

آزاد دائرۃ المعارف، ویکیپیڈیا سے
:چھلانگ بطرف رہنمائی، تلاش
اصطلاح term

مُخطط
دورہ
ہملٹونین
ناملمس

graph
cycle
Hamiltonian
non-adjacent

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

مثال کے طور پر شطرنج کے 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 کے جوڑے کے لیے، تو یہ مخطط ہملٹونین ہو گا۔


اور دیکھو[ترمیم]

بیرونی روابط[ترمیم]

E=mc2     اردو ویکیپیڈیا پر ریاضی مساوات کو بائیں سے دائیں LTR پڑھیٔے     ریاضی علامات