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

آزاد دائرۃ المعارف، ویکیپیڈیا سے
(ہملٹونین مخطط سے رجوع مکرر)
یہاں جائیں: رہنمائی، تلاش کریں
اصطلاح term

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

graph
cycle
Hamiltonian
non-adjacent

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

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

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

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

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

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

سادہ گراف ہو جس کی راس n ہوں اور ہو۔ اگر راس کا درجہ

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

مزید دیکھیے[ترمیم]

==بیرونی روابط ==*

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