مخطط (ریاضی)

آزاد دائرۃ المعارف، ویکیپیڈیا سے
:چھلانگ بطرف رہنمائی، تلاش
تصویر 1: ملصق مخطط کی نقاشی جس میں 6 اقمات اور 7 کنارے ہیں۔

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


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

تصویر 2:گھر کا نقشہ اور مخطط
تصویر 3: مخطط کی جامع مثال۔ تین اقمات اور چھ کنارے۔
دکھائے گئے دونوں مخطط دراصل ایک ہی ملصق مخطط کی نقاشی ہے (دونوں مُخطط برابر ہیں، یعنی دو انداز سے ایک ہی مخطط دکھایا گیا ہے)۔
اصطلاح 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 میں سرخ رنگ میں تین "متعدد‌کنارے" دکھائے گئے ہیں۔ نیلے رنگ میں "مدور" ہے۔

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

سادہ مخطط[ترمیم]

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

متصل مخطط[ترمیم]

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

نامتصل مخطط
مخطط کا ذیلی‌مخطط گہرے رنگ میں دکھایا گیا ہے۔

ذیلی مخطط[ترمیم]

تعریف: مخطط 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 کے ساتھ۔

عدیمہ مخطط، N_4
دورہ مُخطط C_6

دورہ مخطط[ترمیم]

مخطط جس میں صرف ایک دورہ ہو کو دورہ مخطط کہتے ہیں۔ دورہ‌مخطط جس کی اقمات کی تعداد n ہو کو C_n لکھتے ہیں۔

رستہ مخطط P_6

راستہ مخطط[ترمیم]

مخطط جس میں صرف ایک رستہ ہو کو راستہ‌مخطط کہتے ہیں۔ رستہ مخطط جس کی اقمات کی تعداد n ہو کو P_n لکھتے ہیں۔

دوحصائی مخطط

دوحصائی مخطط[ترمیم]

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

اصطلاح term

سمتی مخطط
موزون مخطط

directed graph (digraph)
weighted graph

Directed.svg

سمتی مخطط[ترمیم]

تفصیلی مضمون سمتی مخطط

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

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

موزون مخطط[ترمیم]

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

اصطلاح term

متشاکل
ارتباط واحد الواحد
ارتباطی
جوڑے

isomorphic
one to one correspondence
corresponding
pair

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

متشاکل مخطط[ترمیم]

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

اور دیکھو[ترمیم]

بیرونی روابط[ترمیم]

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