ریاضی کی شاخ نظریہ گراف میں ایسا گراف جس میں کناروں کی سمت مقرر ہو جو تیر کے نشان سے دکھائی جاتی ہے۔ اسے یوں سمجھا جا سکتا ہے جیسے مقام ا اور ب کے درمیان ریلگاڑی مقام ا سے ب کی طرف چلتی ہو مگر دوسری جانب نہیں۔
اصطلاح | term |
---|---|
سمتی گراف | directed graph (digraph) |
تعریف: سمتی گراف 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 |
تعریف: گراف G کو "قابلِ سمت بندی" کہا جائے گا اگر یہ کسی قوی متصل سمتیگراف کا زیریں گراف ہو۔ یعنی G کے ہر کنارے کو اس طرح سے سمت دی جا سکے کہ حاصل ہونے والا سمتیگراف قوی متصل ہو۔
تعریف: متصل گراف کے ایسے کنارے کو "پُل" کہیں گے اگر اس کو ہٹانے سے گراف نامتصل ہو جائے۔
متصل گراف قابل سمت بندی ہو گا اگر بشرط اگر اس میں کوئی پُل نہ ہوں۔
==بیرونی روابط ==*
E=mc2
اردو ویکیپیڈیا پر ریاضی مساوات کو بائیں سے دائیں LTR پڑھیٔے ریاضی علامات
This article uses material from the Wikipedia اردو article سمتی گراف, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). تمام مواد CC BY-SA 4.0 کے تحت میسر ہے، جب تک اس کی مخالفت مذکور نہ ہو۔ Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki اردو (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.