|
[[فائل:6n-graf.svg|تصغیر|250px|بائیں|تصویر 1: ملصق مخططگراف کی نقاشی جس میں 6 اقمات اور 7 کنارے ہیں۔]]
<!--{{اصطلاح برابر|}} placed after the intro, for better mobile view -->
ریاضی میں مُخططگراف نقاط اور لکیروں پر مشتمل ہوتا ہے، ایسا کہ ہر لکیر صرف دو نقاط کو جوڑتی ہے۔ کوئی بھی نقاط کا جوڑا لکیر کے ذریعہ جوڑا جا سکتا ہے۔ ایک نقطہ اپنے آپ سے بھی لکیر کے ذریعہ جوڑا جا سکتا ہے (اسے مدور کہتے ہیں)۔
نقاط کو اقمات[[راس (نظریہ گراف|راس]] کہتے ہیں اور جوڑنے والی لکیر کو کنارہ۔ ایک کنارہ صرف دو اقماتراس کو آپس میں جوڑتا ہے۔
مثال کے طور پر تصویر 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/> نامتصل|
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'' کو آپس میں "مِلاتا" ہے۔
تصویر 1 میں
<div dir="ltr">
<math>E(G) := \{\{1, 2\}, \{1, 5\}, \{2, 3\}, \{2, 5\}, \{3, 4\}, \{4, 5\}, \{4, 6\}\}</math>
</div>
تعریف: اگر دو اقماتراس کو ایک سے زیادہ کنارے جوڑتے ہوں، تو انھیں متعدد کنارے کہا جاتا ہے۔ اگر کنارہ قمہراس کو اپنے آپ سے جوڑے تو اسے مدور کہا جاتا ہے۔ تصویر 3 میں سرخ رنگ میں تین "متعددکنارے" دکھائے گئے ہیں۔ نیلے رنگ میں "مدور" ہے۔
[[فائل:Undirected.svg|تصغیر|125px|سادہمخطط، تین اقماتراس اور تین کنارے۔ چونکہ ہر قمہ کا درجہ دو ہے، اسلئے یہ باقاعدہمخططباقاعدہگراف بھی ہے۔]]
=== سادہ مخططگراف ===
ایک مخططگراف جس میں متعددکنارے اور مدور نہ ہوں کو ''سادہ مخططگراف'' کہا جائے گا۔
=== متصل مخططگراف ===
مخططگراف جو صرف ایک ٹکرے میں ہو کو ''متصل مخططگراف'' کہتے ہیں ورنہ نامتصل مخطط۔گراف۔
<table align="center">
<tr>
<td>[[فائل:disconnected_simple_graph.svg|تصغیر|250px|نامتصل مخططگراف]]
<td>[[فائل:subgraph_and_graph.svg|بائیں|تصغیر|250px|مخطط کا ذیلیمخططذیلیگراف گہرے رنگ میں دکھایا گیا ہے۔]]
</tr>
</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'' مخططگراف ہے بغیر مدور کے اور ''v'' اس کا ایک قمہ ہے۔ قمہ ''v'' کا ''درجہ'' اس میں ملنے والے کناروں کی تعداد ہے اور اسے <code dir="ltr">''deg(v)''</code> لکھتے ہیں۔ تصویر 1 میں قمہ 5 کا درجہ 3 ہے۔
=== باقاعدہ مخططگراف ===
اگر مخططگراف کی تمام اقماتراس کے درجات برابر ہوں، تو مخططگراف کو ''باقاعدہ'' مخططگراف کہیں گے۔ اگر درجہ ''r'' ہو تو مخططگراف کو باقاعدہمخططباقاعدہگراف درجہ ''r'' کے ساتھ کہیں گے۔
=== مصافحہ مبعث ===
مخططگراف مٰیں تمام اقماتراس کے درجات کی حاصل جمع دوگنی ہوتی ہے کناروں کی تعداد کے ۔
* اقماتراس کے درجات کا حاصلجمع [[جفت عدد]] ہوتا ہے۔
* ایسی اقمات جن کا درجہ [[طاق عدد]] ہو، کی تعداد جفت عدد ہوتی ہے۔
* باقاعدہمخططباقاعدہگراف درجہ ''r'' کے ساتھ، کی اقمات کی تعداد ''n'' ہو، تو کناروں کی تعداد <math>\frac{nr}{2}</math> ہو گی۔
{{اصطلاح برابر|
complete<br/> null <br/> cycle <br/> path <br/> bipartite}}
=== مکمل مُخططگراف ===
: تفصیلی مضمون [[مکمل مخططگراف]]
ایسا مخططگراف جس کے کوئی بھی دو واضح اقماتراس صرف اور صرف ایک کنارے سے جڑی ہوں، کو مکمل مخططگراف کہا جاتا ہے۔ مکملمخططمکملگراف جس کی اقماتراس کی تعداد ''n'' ہو کو <math>K_n</math> لکھتے ہیں۔
=== عدیمہ مخططگراف ===
جس مخططگراف میں کوئی کنارے نہ ہوں کو عدیمہ مخططگراف کہتے ہیں۔ عدیمہمخططعدیمہگراف جس کی اقماتراس کی تعداد ''n'' ہو کو <math>N_n</math> لکھتے ہیں۔ یہ مخطط باقاعدہ ہو گا درجہ 0 کے ساتھ۔
<table align="left">
<tr>
<td>[[فائل:Empty_graph.svg|100px|تصغیر|عدیمہ مخطط، <math>N_4</math>]]
<td>[[فائل:Undirected 6 cycle.svg|100px|تصغیر|دورہ مُخططگراف <math>C_6</math>]]
</table>
=== دورہ مخططگراف ===
مخططگراف جس میں صرف ایک [[چال (نظریہ مخططگراف)|دورہ]] ہو کو دورہ مخططگراف کہتے ہیں۔ دورہمخططدورہگراف جس کی اقمات کی تعداد ''n'' ہو کو <math>C_n</math> لکھتے ہیں۔
[[فائل:Path-graph.svg|150px|تصغیر|رستہ مخطط <math>P_6</math>]]
=== راستہ مخططگراف ===
مخططگراف جس میں صرف ایک [[رستہ (نظریہ مخططگراف)|رستہ]] ہو کو راستہمخططراستہگراف کہتے ہیں۔ رستہ مخططگراف جس کی اقمات کی تعداد ''n'' ہو کو <math>P_n</math> لکھتے ہیں۔
[[فائل:bipartite_graph.svg|تصغیر|دائیں|دوحصائی مخطط]]
=== دوحصائی مخططگراف ===
ایسا مخططگراف جس کے اقماتراس مجموعہ کو دو ذیلی مجموعات ''A'' اور ''B'' میں بانٹا جا سکے اس طرح کہ ہر کنارہ مجموعہ ''A'' کے کسی قمہ کو مجموعہ ''B'' کے کسی قمہ سے جوڑتا ہو۔ تصویر میں اقمات کے ذیلی مجموعات کو "نیلے" اور "سرخ" رنگ میں دکھایا گیا ہے۔
{{اصطلاح برابر|
سمتی مخططگراف <br/> موزون مخططگراف|
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'' سے نہیں جوڑتا)۔
[[فائل:a_weighted_graph_example.svg|بائیں|تصغیر|وزن شدہ مخططگراف]]
=== موزون مخططگراف ===
موزون مخطط،گراف، ایسا مخططگراف جس میں ہر کنارے کے ساتھ ایک مثبت عدد نتھی کر دیا جائے جو اس کا وزن کہلائے۔ مثلاً اگر اقمات شہر ہوں تو وزن دو شہروں کے درمیان فاصلہ۔
{{اصطلاح برابر|
متشاکل<br/> ارتباط واحد الواحد<br/> ارتباطی <br/> جوڑے|
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'' میں ارتباطی "اقماتراس جوڑے" کو جوڑنے والے کناروں کی تعداد کے ۔
== مزید دیکھیے ==
| 