گراف (ریاضی)

ریاضی میں گراف نقاط اور لکیروں پر مشتمل ہوتا ہے، ایسا کہ ہر لکیر صرف دو نقاط کو جوڑتی ہے۔ کوئی بھی نقاط کا جوڑا لکیر کے ذریعہ جوڑا جا سکتا ہے۔ ایک نقطہ اپنے آپ سے بھی لکیر کے ذریعہ جوڑا جا سکتا ہے (اسے مدور کہتے ہیں)۔ نقاط کو راس کہتے ہیں اور جوڑنے والی لکیر کو کنارہ۔ ایک کنارہ صرف دو راس کو آپس میں جوڑتا ہے۔

تصویر 1: ملصق گراف کی نقاشی جس میں 6 راس اور 7 کنارے ہیں۔

مثال کے طور پر تصویر 2 میں گھر کا نقشہ دیا ہے۔ اس نقشہ کا گراف بنانے کے لیے ہر کمرے کو راس (دائرہ) سے دکھایا گیا ہے۔ جن دو کمروں کے درمیان دروازہ ہے، گراف میں وہ کنارہ سے جڑے دکھائے گئے ہیں۔ راس پر کمرے کا عدد لکھا گیا ہے۔ اس طرح یہ کمروں کے اتصال کا گراف ہے۔

فائل:House layout plan and its graph.svg

تصویر 2:گھر کا نقشہ اور گراف

تصویر 3: گراف کی جامع مثال۔ تین راس اور چھ کنارے۔

فائل:Isomorphic and equal labeled graphs.svg

دکھائے گئے دونوں گراف دراصل ایک ہی ملصق گراف کی نقاشی ہے (دونوں گراف برابر ہیں، یعنی دو انداز سے ایک ہی گراف دکھایا گیا ہے)۔

اصطلاح	term
گراف ذیلی گراف راس کنارہ مدور لصق ملصق ناملصق مرتب درجہ باقاعدہ متصل نامتصل	graph subgraph vertex, vertices edge loop label labeled unlabeled ordered degree regular connected disconnected

گراف اور اس کی اقسام

تعریف: گراف G مشتمل ہوتا ہے غیر خالی مجموعہ پر جس کے ارکان راس ہوتے ہیں اور ان ارکان کے جوڑوں کی نامرتب فہرست پر، جنہیں کنارے کہا جاتا ہے۔ راس کے مجموعہ کو گراف کا "راس مجموعہ" کہتے ہیں اور V(G) لکھتے ہیں۔ کناروں کی فہرست کو "کنارہ فہرست" کہتے ہیں اور E(G) لکھتے ہیں۔ اگر u اور v راس ہوں، تو کنارہ uv یا vw، راس u اور v کو آپس میں "مِلاتا" ہے۔ تصویر 1 میں

$V(G):=\{1,2,3,4,5,6\}$

$E(G):=\{\{1,2\},\{1,5\},\{2,3\},\{2,5\},\{3,4\},\{4,5\},\{4,6\}\}$

تعریف: اگر دو راس کو ایک سے زیادہ کنارے جوڑتے ہوں، تو انھیں متعدد کنارے کہا جاتا ہے۔ اگر کنارہ راس کو اپنے آپ سے جوڑے تو اسے مدور کہا جاتا ہے۔ تصویر 3 میں سرخ رنگ میں تین "متعددکنارے" دکھائے گئے ہیں۔ نیلے رنگ میں "مدور" ہے۔

سادہ‌گراف، تین راس اور تین کنارے۔ چونکہ ہر قمہ کا درجہ دو ہے، اس لیے یہ باقاعدہ‌گراف بھی ہے۔

سادہ گراف

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

متصل گراف

گراف جو صرف ایک ٹکرے میں ہو کو متصل گراف کہتے ہیں ورنہ نامتصل گراف۔

فائل:Disconnected simple graph.svg نامتصل گراف

فائل:Subgraph and graph.svg گراف کا ذیلی‌گراف گہرے رنگ میں دکھایا گیا ہے۔

ذیلی گراف

تعریف: گراف G کا راس مجموعہ V(G) اور کنارہ‌فہرست E(G)ہو۔ گراف کا ذیلی‌گراف ایسا گراف ہے جس کی تمام راس V(G) میں ہوں اور تمام کنارے E(G) میں ہوں۔

تعریف: اگر G گراف ہے بغیر مدور کے اور v اس کا ایک قمہ ہے۔ قمہ v کا درجہ اس میں ملنے والے کناروں کی تعداد ہے اور اسے deg(v) لکھتے ہیں۔ تصویر 1 میں قمہ 5 کا درجہ 3 ہے۔

باقاعدہ گراف

اگر گراف کی تمام راس کے درجات برابر ہوں، تو گراف کو باقاعدہ گراف کہیں گے۔ اگر درجہ r ہو تو گراف کو باقاعدہ‌گراف درجہ r کے ساتھ کہیں گے۔

مصافحہ مبعث

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

• راس کے درجات کا حاصل‌جمع جفت عدد ہوتا ہے۔
• ایسی راس جن کا درجہ طاق عدد ہو، کی تعداد جفت عدد ہوتی ہے۔
• باقاعدہ‌گراف درجہ r کے ساتھ، کی راس کی تعداد n ہو، تو کناروں کی تعداد ${\frac {nr}{2}}$ ہو گی۔

اصطلاح	term
مکمل عدیمہ دورہ راستہ دوحصائی	complete null cycle path bipartite

مکمل گراف

تفصیلی مضمون مکمل گراف

ایسا گراف جس کے کوئی بھی دو واضح راس صرف اور صرف ایک کنارے سے جڑی ہوں، کو مکمل گراف کہا جاتا ہے۔ مکمل‌گراف جس کی راس کی تعداد n ہو کو $K_{n}$ لکھتے ہیں۔

عدیمہ گراف

جس گراف میں کوئی کنارے نہ ہوں کو عدیمہ گراف کہتے ہیں۔ عدیمہ‌گراف جس کی راس کی تعداد n ہو کو $N_{n}$ لکھتے ہیں۔ یہ گراف باقاعدہ ہو گا درجہ 0 کے ساتھ۔

فائل:Empty graph.svg عدیمہ گراف، $N_{4}$

دورہ گراف $C_{6}$

دورہ گراف

گراف جس میں صرف ایک دورہ ہو کو دورہ گراف کہتے ہیں۔ دورہ‌گراف جس کی راس کی تعداد n ہو کو $C_{n}$ لکھتے ہیں۔

رستہ گراف $P_{6}$

راستہ گراف

گراف جس میں صرف ایک رستہ ہو کو راستہ‌گراف کہتے ہیں۔ رستہ گراف جس کی راس کی تعداد n ہو کو $P_{n}$ لکھتے ہیں۔

فائل:Bipartite graph.svg

دوحصائی گراف

دوحصائی گراف

ایسا گراف جس کے راس مجموعہ کو دو ذیلی مجموعات A اور B میں بانٹا جا سکے اس طرح کہ ہر کنارہ مجموعہ A کے کسی قمہ کو مجموعہ B کے کسی قمہ سے جوڑتا ہو۔ تصویر میں راس کے ذیلی مجموعات کو "نیلے" اور "سرخ" رنگ میں دکھایا گیا ہے۔

اصطلاح	term
سمتی گراف موزون گراف	directed graph (digraph) weighted graph

سمتی گراف

تفصیلی مضمون سمتی گراف

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

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

فائل:A weighted graph example.svg

وزن شدہ گراف

موزون گراف

موزون گراف، ایسا گراف جس میں ہر کنارے کے ساتھ ایک مثبت عدد نتھی کر دیا جائے جو اس کا وزن کہلائے۔ مثلاً اگر راس شہر ہوں تو وزن دو شہروں کے درمیان فاصلہ۔

اصطلاح	term
متشاکل ارتباط واحد الواحد ارتباطی جوڑے	isomorphic one to one correspondence corresponding pair

فائل:Isomorphic notequal labeled graphs.svg

دونوں ملصق گراف برابر نہیں، مگر متشاکل ہیں

فائل:Isomorphic unlabeled graphs.svg

دونوں ناملصق گراف متشاکل ہیں

متشاکل گراف

دو گراف G اور F کو متشاکل کہا جائے گا اگر G کو F میں تبدیل کیا جا سکے اس کے ملصق کی جگہ تبدیل کر کے۔ دوسرے الفاظ میں اگر G اور F کی راس میں ایسا ارتباط واحد الواحد ہو کہ G میں کسی بھی "راس جوڑے" کو جوڑنے والے کنارے کی تعداد برابر ہو F میں ارتباطی "راس جوڑے" کو جوڑنے والے کناروں کی تعداد کے ۔

مزید دیکھیے

• لونی کثیر رقمی
• ملمس مصفوفہ
• ورود مصفوفہ

بیرونی روابط

• commons

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