"گراف (ریاضی)" کے نسخوں کے درمیان فرق
م خودکار: خودکار درستی املا ← سے، سے، == مزید دیکھیے == |
م خودکار درستی+ربط+ترتیب+صفائی (9.7) |
||
سطر 1: | سطر 1: | ||
[[ |
[[فائل:6n-graf.svg|تصغیر|250px|بائیں|تصویر 1: ملصق مخطط کی نقاشی جس میں 6 اقمات اور 7 کنارے ہیں۔]] |
||
<!--{{اصطلاح برابر|}} placed after the intro, for better mobile view --> |
<!--{{اصطلاح برابر|}} placed after the intro, for better mobile view --> |
||
ریاضی میں مُخطط نقاط اور لکیروں پر مشتمل ہوتا ہے، ایسا کہ ہر لکیر صرف دو نقاط کو جوڑتی ہے۔ کوئی بھی نقاط کا جوڑا لکیر کے ذریعہ جوڑا جا سکتا ہے۔ ایک نقطہ اپنے آپ سے بھی لکیر کے ذریعہ جوڑا جا سکتا ہے (اسے مدور کہتے ہیں)۔ |
ریاضی میں مُخطط نقاط اور لکیروں پر مشتمل ہوتا ہے، ایسا کہ ہر لکیر صرف دو نقاط کو جوڑتی ہے۔ کوئی بھی نقاط کا جوڑا لکیر کے ذریعہ جوڑا جا سکتا ہے۔ ایک نقطہ اپنے آپ سے بھی لکیر کے ذریعہ جوڑا جا سکتا ہے (اسے مدور کہتے ہیں)۔ |
||
سطر 5: | سطر 5: | ||
مثال کے طور پر تصویر 2 میں گھر کا نقشہ دیا ہے۔ اس نقشہ کا مخطط بنانے کے لیے ہر کمرے کو قمہ (دائرہ) سے دکھایا گیا ہے۔ جن دو کمروں کے درمیان دروازہ ہے، مخطط میں وہ کنارہ سے جڑے دکھائے گئے ہیں۔ اقمات پر کمرے کا عدد لکھا گیا ہے۔ اس طرح یہ کمروں کے اتصال کا مخطط ہے۔ |
مثال کے طور پر تصویر 2 میں گھر کا نقشہ دیا ہے۔ اس نقشہ کا مخطط بنانے کے لیے ہر کمرے کو قمہ (دائرہ) سے دکھایا گیا ہے۔ جن دو کمروں کے درمیان دروازہ ہے، مخطط میں وہ کنارہ سے جڑے دکھائے گئے ہیں۔ اقمات پر کمرے کا عدد لکھا گیا ہے۔ اس طرح یہ کمروں کے اتصال کا مخطط ہے۔ |
||
[[ |
[[فائل:house_layout_plan_and_its_graph.svg|وسط|تصغیر|400px|تصویر 2:گھر کا نقشہ اور مخطط]] |
||
[[ |
[[فائل:Multigraph.svg|تصغیر|125px|بائیں|تصویر 3: مخطط کی جامع مثال۔ تین اقمات اور چھ کنارے۔]] |
||
[[ |
[[فائل:Isomorphic_and_equal_labeled_graphs.svg|دائیں|تصغیر|250px|دکھائے گئے دونوں مخطط دراصل ایک ہی ملصق مخطط کی نقاشی ہے (دونوں مُخطط برابر ہیں، یعنی دو انداز سے ایک ہی مخطط دکھایا گیا ہے)۔]] |
||
{{اصطلاح برابر| |
{{اصطلاح برابر| |
||
مُخطط <br>ذیلی مخطط<br> قِمّہ، اقمات <br>کنارہ<br> مدور <br> لصق<br> ملصق<br> ناملصق <br>مرتب <br>درجہ <br> باقاعدہ <br> متصل<br> نامتصل| |
مُخطط <br/>ذیلی مخطط<br/> قِمّہ، اقمات <br/>کنارہ<br/> مدور <br/> لصق<br/> ملصق<br/> ناملصق <br/>مرتب <br/>درجہ <br/> باقاعدہ <br/> متصل<br/> نامتصل| |
||
graph <br> subgraph<br> vertex, vertices <br> edge<br> loop <br> label <br> labeled <br>unlabeled<br> ordered <br>degree<br> regular <br> connected <br> disconnected}} |
graph <br/> subgraph<br/> vertex, vertices <br/> edge<br/> loop <br/> label <br/> labeled <br/>unlabeled<br/> ordered <br/>degree<br/> regular <br/> connected <br/> disconnected}} |
||
==مخطط اور اس کی اقسام== |
== مخطط اور اس کی اقسام == |
||
تعریف: ''مخطط'' ''G'' مشتمل ہوتا ہے غیر خالی مجموعہ پر جس کے ارکان اقمات ہوتے ہیں اور ان ارکان کے جوڑوں کی نامرتب فہرست پر، جنہیں کنارے کہا جاتا ہے۔ اقمات کے مجموعہ کو مخطط کا "اقمات مجموعہ" کہتے ہیں اور <code dir="ltr">''V(G)''</code> لکھتے ہیں۔ کناروں کی فہرست کو "کنارہ فہرست" کہتے ہیں اور <code dir="ltr">''E(G)''</code> لکھتے ہیں۔ اگر ''u'' اور ''v'' اقمات ہوں، تو کنارہ ''uv'' یا ''vw''، اقمات ''u'' اور ''v'' کو آپس میں "مِلاتا" ہے۔ |
تعریف: ''مخطط'' ''G'' مشتمل ہوتا ہے غیر خالی مجموعہ پر جس کے ارکان اقمات ہوتے ہیں اور ان ارکان کے جوڑوں کی نامرتب فہرست پر، جنہیں کنارے کہا جاتا ہے۔ اقمات کے مجموعہ کو مخطط کا "اقمات مجموعہ" کہتے ہیں اور <code dir="ltr">''V(G)''</code> لکھتے ہیں۔ کناروں کی فہرست کو "کنارہ فہرست" کہتے ہیں اور <code dir="ltr">''E(G)''</code> لکھتے ہیں۔ اگر ''u'' اور ''v'' اقمات ہوں، تو کنارہ ''uv'' یا ''vw''، اقمات ''u'' اور ''v'' کو آپس میں "مِلاتا" ہے۔ |
||
تصویر 1 میں |
تصویر 1 میں |
||
سطر 21: | سطر 21: | ||
<math>E(G) := \{\{1, 2\}, \{1, 5\}, \{2, 3\}, \{2, 5\}, \{3, 4\}, \{4, 5\}, \{4, 6\}\}</math> |
<math>E(G) := \{\{1, 2\}, \{1, 5\}, \{2, 3\}, \{2, 5\}, \{3, 4\}, \{4, 5\}, \{4, 6\}\}</math> |
||
</div> |
</div> |
||
تعریف: اگر دو اقمات کو ایک سے زیادہ کنارے جوڑتے ہوں، تو انھیں متعدد کنارے کہا جاتا ہے۔ اگر کنارہ قمہ کو اپنے آپ سے جوڑے تو اسے مدور کہا جاتا ہے۔ تصویر 3 میں سرخ رنگ میں تین " |
تعریف: اگر دو اقمات کو ایک سے زیادہ کنارے جوڑتے ہوں، تو انھیں متعدد کنارے کہا جاتا ہے۔ اگر کنارہ قمہ کو اپنے آپ سے جوڑے تو اسے مدور کہا جاتا ہے۔ تصویر 3 میں سرخ رنگ میں تین "متعددکنارے" دکھائے گئے ہیں۔ نیلے رنگ میں "مدور" ہے۔ |
||
[[ |
[[فائل:Undirected.svg|تصغیر|125px|سادہمخطط، تین اقمات اور تین کنارے۔ چونکہ ہر قمہ کا درجہ دو ہے، اسلئے یہ باقاعدہمخطط بھی ہے۔]] |
||
===سادہ مخطط === |
=== سادہ مخطط === |
||
ایک مخطط جس میں متعددکنارے اور مدور نہ ہوں کو ''سادہ مخطط'' کہا جائے گا۔ |
ایک مخطط جس میں متعددکنارے اور مدور نہ ہوں کو ''سادہ مخطط'' کہا جائے گا۔ |
||
===متصل مخطط=== |
=== متصل مخطط === |
||
مخطط جو صرف ایک ٹکرے میں ہو کو ''متصل مخطط'' کہتے ہیں ورنہ نامتصل مخطط۔ |
مخطط جو صرف ایک ٹکرے میں ہو کو ''متصل مخطط'' کہتے ہیں ورنہ نامتصل مخطط۔ |
||
<table align="center"> |
<table align="center"> |
||
<tr> |
<tr> |
||
<td>[[ |
<td>[[فائل:disconnected_simple_graph.svg|تصغیر|250px|نامتصل مخطط]] |
||
<td>[[ |
<td>[[فائل:subgraph_and_graph.svg|بائیں|تصغیر|250px|مخطط کا ذیلیمخطط گہرے رنگ میں دکھایا گیا ہے۔]] |
||
</tr> |
</tr> |
||
</table> |
</table> |
||
===ذیلی مخطط=== |
=== ذیلی مخطط === |
||
تعریف: ''مخطط'' ''G'' کا اقماتمجموعہ <code dir="ltr">''V(G)''</code> اور کنارہفہرست <code dir="ltr">''E(G)''</code>ہو۔ مخطط کا ''ذیلیمخطط'' ایسا مخطط ہے جس کی تمام اقمات <code dir="ltr">''V(G)''</code> میں ہوں اور تمام کنارے <code dir="ltr">''E(G)''</code> میں ہوں۔ |
تعریف: ''مخطط'' ''G'' کا اقماتمجموعہ <code dir="ltr">''V(G)''</code> اور کنارہفہرست <code dir="ltr">''E(G)''</code>ہو۔ مخطط کا ''ذیلیمخطط'' ایسا مخطط ہے جس کی تمام اقمات <code dir="ltr">''V(G)''</code> میں ہوں اور تمام کنارے <code dir="ltr">''E(G)''</code> میں ہوں۔ |
||
تعریف: اگر ''G'' مخطط ہے بغیر مدور کے اور ''v'' اس کا ایک قمہ ہے۔ قمہ ''v'' کا ''درجہ'' اس میں ملنے والے کناروں کی تعداد ہے اور اسے <code dir="ltr">''deg(v)''</code> لکھتے ہیں۔ تصویر 1 میں قمہ 5 کا درجہ 3 ہے۔ |
تعریف: اگر ''G'' مخطط ہے بغیر مدور کے اور ''v'' اس کا ایک قمہ ہے۔ قمہ ''v'' کا ''درجہ'' اس میں ملنے والے کناروں کی تعداد ہے اور اسے <code dir="ltr">''deg(v)''</code> لکھتے ہیں۔ تصویر 1 میں قمہ 5 کا درجہ 3 ہے۔ |
||
===باقاعدہ مخطط === |
=== باقاعدہ مخطط === |
||
اگر مخطط کی تمام اقمات کے درجات برابر ہوں، تو مخطط کو ''باقاعدہ'' مخطط کہیں گے۔ اگر درجہ ''r'' ہو تو مخطط کو باقاعدہمخطط درجہ ''r'' کے ساتھ کہیں گے۔ |
اگر مخطط کی تمام اقمات کے درجات برابر ہوں، تو مخطط کو ''باقاعدہ'' مخطط کہیں گے۔ اگر درجہ ''r'' ہو تو مخطط کو باقاعدہمخطط درجہ ''r'' کے ساتھ کہیں گے۔ |
||
=== مصافحہ مبعث=== |
=== مصافحہ مبعث === |
||
مخطط مٰیں تمام اقمات کے درجات کی حاصل جمع دوگنی ہوتی ہے کناروں کی تعداد کے ۔ |
مخطط مٰیں تمام اقمات کے درجات کی حاصل جمع دوگنی ہوتی ہے کناروں کی تعداد کے ۔ |
||
*اقمات کے درجات کا حاصلجمع [[جفت عدد]] ہوتا ہے۔ |
* اقمات کے درجات کا حاصلجمع [[جفت عدد]] ہوتا ہے۔ |
||
*ایسی اقمات جن کا درجہ [[طاق عدد]] ہو، کی تعداد جفت عدد ہوتی ہے۔ |
* ایسی اقمات جن کا درجہ [[طاق عدد]] ہو، کی تعداد جفت عدد ہوتی ہے۔ |
||
*باقاعدہمخطط درجہ ''r'' کے ساتھ، کی اقمات کی تعداد ''n'' ہو، تو کناروں کی تعداد <math>\frac{nr}{2}</math> ہو گی۔ |
* باقاعدہمخطط درجہ ''r'' کے ساتھ، کی اقمات کی تعداد ''n'' ہو، تو کناروں کی تعداد <math>\frac{nr}{2}</math> ہو گی۔ |
||
{{اصطلاح برابر| |
{{اصطلاح برابر| |
||
مکمل <br> عدیمہ<br> دورہ<br> راستہ<br> دوحصائی| |
مکمل <br/> عدیمہ<br/> دورہ<br/> راستہ<br/> دوحصائی| |
||
complete<br> null <br> cycle <br> path <br> bipartite}} |
complete<br/> null <br/> cycle <br/> path <br/> bipartite}} |
||
=== مکمل مُخطط=== |
=== مکمل مُخطط === |
||
: تفصیلی مضمون [[مکمل مخطط]] |
: تفصیلی مضمون [[مکمل مخطط]] |
||
ایسا مخطط جس کے کوئی بھی دو واضح اقمات صرف اور صرف ایک کنارے سے جڑی ہوں، کو مکمل مخطط کہا جاتا ہے۔ مکملمخطط جس کی اقمات کی تعداد ''n'' ہو کو <math>K_n</math> لکھتے ہیں۔ |
ایسا مخطط جس کے کوئی بھی دو واضح اقمات صرف اور صرف ایک کنارے سے جڑی ہوں، کو مکمل مخطط کہا جاتا ہے۔ مکملمخطط جس کی اقمات کی تعداد ''n'' ہو کو <math>K_n</math> لکھتے ہیں۔ |
||
===عدیمہ مخطط === |
=== عدیمہ مخطط === |
||
جس مخطط میں کوئی کنارے نہ ہوں کو عدیمہ مخطط کہتے ہیں۔ عدیمہمخطط جس کی اقمات کی تعداد ''n'' ہو کو <math>N_n</math> لکھتے ہیں۔ یہ مخطط باقاعدہ ہو گا درجہ 0 کے ساتھ۔ |
جس مخطط میں کوئی کنارے نہ ہوں کو عدیمہ مخطط کہتے ہیں۔ عدیمہمخطط جس کی اقمات کی تعداد ''n'' ہو کو <math>N_n</math> لکھتے ہیں۔ یہ مخطط باقاعدہ ہو گا درجہ 0 کے ساتھ۔ |
||
<table align="left"> |
<table align="left"> |
||
<tr> |
<tr> |
||
<td>[[ |
<td>[[فائل:Empty_graph.svg|100px|تصغیر|عدیمہ مخطط، <math>N_4</math>]] |
||
<td>[[ |
<td>[[فائل:Undirected 6 cycle.svg|100px|تصغیر|دورہ مُخطط <math>C_6</math>]] |
||
</table> |
</table> |
||
===دورہ مخطط === |
=== دورہ مخطط === |
||
مخطط جس میں صرف ایک [[چال (نظریہ مخطط)|دورہ]] ہو کو دورہ مخطط کہتے ہیں۔ دورہمخطط جس کی اقمات کی تعداد ''n'' ہو کو <math>C_n</math> لکھتے ہیں۔ |
مخطط جس میں صرف ایک [[چال (نظریہ مخطط)|دورہ]] ہو کو دورہ مخطط کہتے ہیں۔ دورہمخطط جس کی اقمات کی تعداد ''n'' ہو کو <math>C_n</math> لکھتے ہیں۔ |
||
[[ |
[[فائل:Path-graph.svg|150px|تصغیر|رستہ مخطط <math>P_6</math>]] |
||
===راستہ مخطط === |
=== راستہ مخطط === |
||
مخطط جس میں صرف ایک [[رستہ (نظریہ مخطط)|رستہ]] ہو کو راستہمخطط کہتے ہیں۔ رستہ مخطط جس کی اقمات کی تعداد ''n'' ہو کو <math>P_n</math> لکھتے ہیں۔ |
مخطط جس میں صرف ایک [[رستہ (نظریہ مخطط)|رستہ]] ہو کو راستہمخطط کہتے ہیں۔ رستہ مخطط جس کی اقمات کی تعداد ''n'' ہو کو <math>P_n</math> لکھتے ہیں۔ |
||
[[ |
[[فائل:bipartite_graph.svg|تصغیر|دائیں|دوحصائی مخطط]] |
||
===دوحصائی مخطط === |
=== دوحصائی مخطط === |
||
ایسا مخطط جس کے اقمات مجموعہ کو دو ذیلی مجموعات ''A'' اور ''B'' میں بانٹا جا سکے اس طرح کہ ہر کنارہ مجموعہ ''A'' کے کسی قمہ کو مجموعہ ''B'' کے کسی قمہ سے جوڑتا ہو۔ تصویر میں اقمات کے ذیلی مجموعات کو "نیلے" اور "سرخ" رنگ میں دکھایا گیا ہے۔ |
ایسا مخطط جس کے اقمات مجموعہ کو دو ذیلی مجموعات ''A'' اور ''B'' میں بانٹا جا سکے اس طرح کہ ہر کنارہ مجموعہ ''A'' کے کسی قمہ کو مجموعہ ''B'' کے کسی قمہ سے جوڑتا ہو۔ تصویر میں اقمات کے ذیلی مجموعات کو "نیلے" اور "سرخ" رنگ میں دکھایا گیا ہے۔ |
||
{{اصطلاح برابر| |
{{اصطلاح برابر| |
||
سمتی مخطط <br> موزون مخطط| |
سمتی مخطط <br/> موزون مخطط| |
||
directed graph (digraph) <br> weighted graph}} |
directed graph (digraph) <br/> weighted graph}} |
||
[[ |
[[فائل:Directed.svg|بائیں|تصغیر|150px]] |
||
=== سمتی مخطط=== |
=== سمتی مخطط === |
||
:تفصیلی مضمون [[سمتی مخطط]] |
:تفصیلی مضمون [[سمتی مخطط]] |
||
ایسا مخطط جس میں کناروں کی سمت مقرر ہو جو تیر کے نشان سے دکھائی جاتی ہے۔ اسے یوں سمجھا جا سکتا ہے جیسے مقام ''ا'' اور ''ب'' کے درمیان ریلگاڑی مقام ''ا'' سے ''ب'' کی طرف چلتی ہو مگر دوسری جانب نہیں۔ |
ایسا مخطط جس میں کناروں کی سمت مقرر ہو جو تیر کے نشان سے دکھائی جاتی ہے۔ اسے یوں سمجھا جا سکتا ہے جیسے مقام ''ا'' اور ''ب'' کے درمیان ریلگاڑی مقام ''ا'' سے ''ب'' کی طرف چلتی ہو مگر دوسری جانب نہیں۔ |
||
:تعریف: سمتی مخطط ''D'' مشتمل ہوتا ہے ایک مجموعہ جسے ''اقمات'' کہتے ہیں اور اقمات کے جوڑوں کی مرتب فہرست جنہیں ''تیر'' کہتے ہیں۔ اقمات کو "اقمات مجموعہ" <code dir="ltr">V(D)</code> لکھتے ہیں اور تیروں کو "تیر فہرست" <code dir="ltr">A(D)</code> لکھتے ہیں۔ اگر ''a'' اور ''b'' اقمات ہیں تو تیر ''ab'' کی سمت ''a'' سے ''b'' ہوتی ہے یا ''a'' کو ''b'' سے جوڑتا ہے (مگر ''b'' کو ''a'' سے نہیں جوڑتا)۔ |
:تعریف: سمتی مخطط ''D'' مشتمل ہوتا ہے ایک مجموعہ جسے ''اقمات'' کہتے ہیں اور اقمات کے جوڑوں کی مرتب فہرست جنہیں ''تیر'' کہتے ہیں۔ اقمات کو "اقمات مجموعہ" <code dir="ltr">V(D)</code> لکھتے ہیں اور تیروں کو "تیر فہرست" <code dir="ltr">A(D)</code> لکھتے ہیں۔ اگر ''a'' اور ''b'' اقمات ہیں تو تیر ''ab'' کی سمت ''a'' سے ''b'' ہوتی ہے یا ''a'' کو ''b'' سے جوڑتا ہے (مگر ''b'' کو ''a'' سے نہیں جوڑتا)۔ |
||
[[ |
[[فائل:a_weighted_graph_example.svg|بائیں|تصغیر|وزن شدہ مخطط]] |
||
===موزون مخطط === |
=== موزون مخطط === |
||
موزون مخطط، ایسا مخطط جس میں ہر کنارے کے ساتھ ایک مثبت عدد نتھی کر دیا جائے جو اس کا وزن کہلائے۔ مثلاً اگر اقمات شہر ہوں تو وزن دو شہروں کے درمیان فاصلہ۔ |
موزون مخطط، ایسا مخطط جس میں ہر کنارے کے ساتھ ایک مثبت عدد نتھی کر دیا جائے جو اس کا وزن کہلائے۔ مثلاً اگر اقمات شہر ہوں تو وزن دو شہروں کے درمیان فاصلہ۔ |
||
{{اصطلاح برابر| |
{{اصطلاح برابر| |
||
متشاکل<br> ارتباط واحد الواحد<br> ارتباطی <br> جوڑے| |
متشاکل<br/> ارتباط واحد الواحد<br/> ارتباطی <br/> جوڑے| |
||
isomorphic <br> one to one correspondence <br> corresponding <br> pair |
isomorphic <br/> one to one correspondence <br/> corresponding <br/> pair}} |
||
[[ |
[[فائل:Isomorphic_notequal_labeled_graphs.svg|دائیں|تصغیر|250px|دونوں ملصق مخطط برابر نہیں، مگر متشاکل ہیں]] |
||
[[ |
[[فائل:Isomorphic_unlabeled_graphs.svg|بائیں|تصغیر|250px|دونوں ناملصق مخطط متشاکل ہیں]] |
||
==متشاکل مخطط == |
== متشاکل مخطط == |
||
دو مخطط ''G'' اور ''F'' کو متشاکل کہا جائے گا اگر ''G'' کو ''F'' میں تبدیل کیا جا سکے اس کے ملصق کی جگہ تبدیل کر کے۔ دوسرے الفاظ میں اگر ''G'' اور ''F'' کی اقمات میں ایسا ارتباط واحد الواحد ہو، کہ ''G'' میں کسی بھی "اقمات جوڑے" کو جوڑنے والے کنارے کی تعداد برابر ہو ''F'' میں ارتباطی "اقمات جوڑے" کو جوڑنے والے کناروں کی تعداد کے ۔ |
دو مخطط ''G'' اور ''F'' کو متشاکل کہا جائے گا اگر ''G'' کو ''F'' میں تبدیل کیا جا سکے اس کے ملصق کی جگہ تبدیل کر کے۔ دوسرے الفاظ میں اگر ''G'' اور ''F'' کی اقمات میں ایسا ارتباط واحد الواحد ہو، کہ ''G'' میں کسی بھی "اقمات جوڑے" کو جوڑنے والے کنارے کی تعداد برابر ہو ''F'' میں ارتباطی "اقمات جوڑے" کو جوڑنے والے کناروں کی تعداد کے ۔ |
||
سطر 104: | سطر 104: | ||
* [[ورود مصفوفہ]] |
* [[ورود مصفوفہ]] |
||
==بیرونی روابط == |
== بیرونی روابط == |
||
* [ |
* [//commons.wikimedia.org/wiki/Graph_theory commons] |
||
{{ریاضی مدد}} |
{{ریاضی مدد}} |
||
⚫ | |||
[[زمرہ:نگاری نظریہ]] |
[[زمرہ:نگاری نظریہ]] |
||
[[زمرہ:نظریہ مخطط]] |
[[زمرہ:نظریہ مخطط]] |
||
⚫ |
نسخہ بمطابق 09:06، 23 مارچ 2018ء
ریاضی میں مُخطط نقاط اور لکیروں پر مشتمل ہوتا ہے، ایسا کہ ہر لکیر صرف دو نقاط کو جوڑتی ہے۔ کوئی بھی نقاط کا جوڑا لکیر کے ذریعہ جوڑا جا سکتا ہے۔ ایک نقطہ اپنے آپ سے بھی لکیر کے ذریعہ جوڑا جا سکتا ہے (اسے مدور کہتے ہیں)۔ نقاط کو اقمات کہتے ہیں اور جوڑنے والی لکیر کو کنارہ۔ ایک کنارہ صرف دو اقمات کو آپس میں جوڑتا ہے۔
مثال کے طور پر تصویر 2 میں گھر کا نقشہ دیا ہے۔ اس نقشہ کا مخطط بنانے کے لیے ہر کمرے کو قمہ (دائرہ) سے دکھایا گیا ہے۔ جن دو کمروں کے درمیان دروازہ ہے، مخطط میں وہ کنارہ سے جڑے دکھائے گئے ہیں۔ اقمات پر کمرے کا عدد لکھا گیا ہے۔ اس طرح یہ کمروں کے اتصال کا مخطط ہے۔
اصطلاح | term |
---|---|
مُخطط |
graph |
مخطط اور اس کی اقسام
تعریف: مخطط G مشتمل ہوتا ہے غیر خالی مجموعہ پر جس کے ارکان اقمات ہوتے ہیں اور ان ارکان کے جوڑوں کی نامرتب فہرست پر، جنہیں کنارے کہا جاتا ہے۔ اقمات کے مجموعہ کو مخطط کا "اقمات مجموعہ" کہتے ہیں اور V(G)
لکھتے ہیں۔ کناروں کی فہرست کو "کنارہ فہرست" کہتے ہیں اور E(G)
لکھتے ہیں۔ اگر u اور v اقمات ہوں، تو کنارہ uv یا vw، اقمات u اور v کو آپس میں "مِلاتا" ہے۔
تصویر 1 میں
تعریف: اگر دو اقمات کو ایک سے زیادہ کنارے جوڑتے ہوں، تو انھیں متعدد کنارے کہا جاتا ہے۔ اگر کنارہ قمہ کو اپنے آپ سے جوڑے تو اسے مدور کہا جاتا ہے۔ تصویر 3 میں سرخ رنگ میں تین "متعددکنارے" دکھائے گئے ہیں۔ نیلے رنگ میں "مدور" ہے۔
سادہ مخطط
ایک مخطط جس میں متعددکنارے اور مدور نہ ہوں کو سادہ مخطط کہا جائے گا۔
متصل مخطط
مخطط جو صرف ایک ٹکرے میں ہو کو متصل مخطط کہتے ہیں ورنہ نامتصل مخطط۔
ذیلی مخطط
تعریف: مخطط G کا اقماتمجموعہ V(G)
اور کنارہفہرست E(G)
ہو۔ مخطط کا ذیلیمخطط ایسا مخطط ہے جس کی تمام اقمات V(G)
میں ہوں اور تمام کنارے E(G)
میں ہوں۔
تعریف: اگر G مخطط ہے بغیر مدور کے اور v اس کا ایک قمہ ہے۔ قمہ v کا درجہ اس میں ملنے والے کناروں کی تعداد ہے اور اسے deg(v)
لکھتے ہیں۔ تصویر 1 میں قمہ 5 کا درجہ 3 ہے۔
باقاعدہ مخطط
اگر مخطط کی تمام اقمات کے درجات برابر ہوں، تو مخطط کو باقاعدہ مخطط کہیں گے۔ اگر درجہ r ہو تو مخطط کو باقاعدہمخطط درجہ r کے ساتھ کہیں گے۔
مصافحہ مبعث
مخطط مٰیں تمام اقمات کے درجات کی حاصل جمع دوگنی ہوتی ہے کناروں کی تعداد کے ۔
- اقمات کے درجات کا حاصلجمع جفت عدد ہوتا ہے۔
- ایسی اقمات جن کا درجہ طاق عدد ہو، کی تعداد جفت عدد ہوتی ہے۔
- باقاعدہمخطط درجہ r کے ساتھ، کی اقمات کی تعداد n ہو، تو کناروں کی تعداد ہو گی۔
اصطلاح | term |
---|---|
مکمل |
complete |
مکمل مُخطط
- تفصیلی مضمون مکمل مخطط
ایسا مخطط جس کے کوئی بھی دو واضح اقمات صرف اور صرف ایک کنارے سے جڑی ہوں، کو مکمل مخطط کہا جاتا ہے۔ مکملمخطط جس کی اقمات کی تعداد n ہو کو لکھتے ہیں۔
عدیمہ مخطط
جس مخطط میں کوئی کنارے نہ ہوں کو عدیمہ مخطط کہتے ہیں۔ عدیمہمخطط جس کی اقمات کی تعداد n ہو کو لکھتے ہیں۔ یہ مخطط باقاعدہ ہو گا درجہ 0 کے ساتھ۔
دورہ مخطط
مخطط جس میں صرف ایک دورہ ہو کو دورہ مخطط کہتے ہیں۔ دورہمخطط جس کی اقمات کی تعداد n ہو کو لکھتے ہیں۔
راستہ مخطط
مخطط جس میں صرف ایک رستہ ہو کو راستہمخطط کہتے ہیں۔ رستہ مخطط جس کی اقمات کی تعداد n ہو کو لکھتے ہیں۔
دوحصائی مخطط
ایسا مخطط جس کے اقمات مجموعہ کو دو ذیلی مجموعات A اور B میں بانٹا جا سکے اس طرح کہ ہر کنارہ مجموعہ A کے کسی قمہ کو مجموعہ B کے کسی قمہ سے جوڑتا ہو۔ تصویر میں اقمات کے ذیلی مجموعات کو "نیلے" اور "سرخ" رنگ میں دکھایا گیا ہے۔
اصطلاح | term |
---|---|
سمتی مخطط |
directed graph (digraph) |
سمتی مخطط
- تفصیلی مضمون سمتی مخطط
ایسا مخطط جس میں کناروں کی سمت مقرر ہو جو تیر کے نشان سے دکھائی جاتی ہے۔ اسے یوں سمجھا جا سکتا ہے جیسے مقام ا اور ب کے درمیان ریلگاڑی مقام ا سے ب کی طرف چلتی ہو مگر دوسری جانب نہیں۔
- تعریف: سمتی مخطط D مشتمل ہوتا ہے ایک مجموعہ جسے اقمات کہتے ہیں اور اقمات کے جوڑوں کی مرتب فہرست جنہیں تیر کہتے ہیں۔ اقمات کو "اقمات مجموعہ"
V(D)
لکھتے ہیں اور تیروں کو "تیر فہرست"A(D)
لکھتے ہیں۔ اگر a اور b اقمات ہیں تو تیر ab کی سمت a سے b ہوتی ہے یا a کو b سے جوڑتا ہے (مگر b کو a سے نہیں جوڑتا)۔
موزون مخطط
موزون مخطط، ایسا مخطط جس میں ہر کنارے کے ساتھ ایک مثبت عدد نتھی کر دیا جائے جو اس کا وزن کہلائے۔ مثلاً اگر اقمات شہر ہوں تو وزن دو شہروں کے درمیان فاصلہ۔
اصطلاح | term |
---|---|
متشاکل |
isomorphic |
متشاکل مخطط
دو مخطط G اور F کو متشاکل کہا جائے گا اگر G کو F میں تبدیل کیا جا سکے اس کے ملصق کی جگہ تبدیل کر کے۔ دوسرے الفاظ میں اگر G اور F کی اقمات میں ایسا ارتباط واحد الواحد ہو، کہ G میں کسی بھی "اقمات جوڑے" کو جوڑنے والے کنارے کی تعداد برابر ہو F میں ارتباطی "اقمات جوڑے" کو جوڑنے والے کناروں کی تعداد کے ۔
مزید دیکھیے
بیرونی روابط
E=mc2
اردو ویکیپیڈیا پر ریاضی مساوات کو بائیں سے دائیں LTR پڑھیٔے ریاضی علامات