سمتی گراف

آزاد دائرۃ المعارف، ویکیپیڈیا سے
Jump to navigation Jump to search
Directed.svg
اصطلاح 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 کو ورد ہے۔ Vertex adjacency arc graph.png

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

مصافحہ مبعث[ترمیم]

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

اصطلاح term

قابلِ سمت بندی
پُل

orientable
bridge

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

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

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

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

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

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

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