سمتی مخطط

اصطلاح	term
سمتی مُخطط ذیلی مخطط قِمّہ، اقمات کنارہ تیر مدور لصق ملصق ناملصق مرتب درجہ باقاعدہ زیریں متعدد ورد ورود قوی	directed graph (digraph) subgraph vertices edge arc loop label labeled unlabeled ordered degree regular underlying multiple incident incidence strong

ریاضی کی شاخ نظریہ مخطط میں ایسا مخطط جس میں کناروں کی سمت مقرر ہو جو تیر کے نشان سے دکھائی جاتی ہے۔ اسے یوں سمجھا جا سکتا ہے جیسے مقام ا اور ب کے درمیان ریل‌گاڑی مقام ا سے ب کی طرف چلتی ہو مگر دوسری جانب نہیں۔

تعریف: سمتی مخطط D مشتمل ہوتا ہے ایک مجموعہ جسے اقمات کہتے ہیں، اور اقمات کے جوڑوں کی مرتب فہرست جنہیں تیر کہتے ہیں۔ اقمات کو "اقمات مجموعہ" V(D) لکھتے ہیں، اور تیروں کو "تیر فہرست" A(D) لکھتے ہیں۔ اگر a اور b اقمات ہیں تو تیر ab کی سمت a سے b ہوتی ہے، یا a کو b سے جوڑتا ہے (مگر b کو a سے نہیں جوڑتا)۔

تعریف: سمتی مخطط D کے ہر تیر کو اس کے ارتباطی کنارے سے بدل دینے سے جو مخطط حاصل ہوتا ہے اسے D کا "زیریں مخطط" کہا جاتا ہے۔

تعریف: اگر دو اقمات کو ایک سے زیادہ تیر ایک ہی سمت میں جوڑتے ہوں، تو انھیں متعدد تیر کہا جاتا ہے۔ اگر تیر قمہ کو اپنے آپ سے جوڑے تو اسے مدور کہا جاتا ہے۔

سادہ سمتی مخطط

سمتی مخطط جس میں متعددتیر اور مدور نہ ہوں کو سادہ سمتی‌مخطط کہا جائے گا۔

متصل سمتی مخطط

سمتی مخطط کا زیریں مخطط اگر متصل ہو تو سمتی مخطط کو متصل کہیں گے ورنہ نامتصل۔ سمتی مخطط کو "قوی متصل" کہیں گے اگر کسی بھی قمہ سے کسی بھی قمہ تک رستہ ہو۔

ذیلی سمتی مخطط

تعریف: سمتی مخطط D کا اقمات‌مجموعہ V(D) اور تیر‌فہرست A(D)ہو۔ سمتی مخطط کا ذیلی‌سمتی‌مخطط ایسا سمتی‌مخطط ہے جس کی تمام اقمات V(D) میں ہوں اور تمام تیر A(D) میں ہوں۔

تیر e قمہ a سے ورد ہے، اور تیر e قمہ b کو ورد ہے۔

تعریف: اگر D سمتی‌مخطط ہے بغیر مدور کے، اور v اس کا ایک قمہ ہے۔ قمہ v کا اخراج درجہ اس سے ورد ہونے والے تیروں کی تعداد ہے، اور اسے outdeg(v) لکھتے ہیں۔ قمہ v کا ادخال درجہ اس کو ورد ہونے والے تیروں کی تعداد ہے، اور اسے indeg(v) لکھتے ہیں۔

مصافحہ مبعث

سمتی‌مخطط مٰیں تمام اقمات کے اخراج درجات کی حاصل جمع برابر ہوتی ہے تیروں کی تعداد کے۔ اور تمام اقمات کے ادخال درجات کی حاصل جمع بھی برابر ہوتی ہے تیروں کی تعداد کے۔

اصطلاح	term
قابلِ سمت بندی پُل	orientable bridge

تعریف: مخطط G کو "قابلِ سمت بندی" کہا جائے گا اگر یہ کسی قوی متصل سمتی‌مخطط کا زیریں‌مخطط ہو۔ یعنی G کے ہر کنارے کو اس طرح سے سمت دی جا سکے کہ حاصل ہونے والا سمتی‌مخطط قوی متصل ہو۔

تعریف: متصل مخطط کے ایسے کنارے کو "پُل" کہیں گے اگر اس کو ہٹانے سے مخطط نامتصل ہو جائے۔

مسلئہ اثباتی

متصل مخطط قابل سمت بندی ہو گا اگر بشرط اگر اس میں کوئ پُل نہ ہوں۔

اور دیکھو

• ملمس مصفوفہ
• ورود مصفوفہ

بیرونی روابط

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