"گراف (ریاضی)" کے نسخوں کے درمیان فرق

م
clean up, replaced: ← (16) using AWB
(<!--{{اصطلاح برابر|}} placed after the intro, for better mobile view -->)
م (clean up, replaced: ← (16) using AWB)
[[Image:6n-graf.svg|thumb|250px|left|تصویر 1: ملصق مخطط کی نقاشی جس میں 6 اقمات اور 7 کنارے ہیں۔]]
<!--{{اصطلاح برابر|}} placed after the intro, for better mobile view -->
ریاضی میں مُخطط نقاط اور لکیروں پر مشتمل ہوتا ہے، ایسا کہ ہر لکیر صرف دو نقاط کو جوڑتی ہے۔ کوئی بھی نقاط کا جوڑا لکیر کے ذریعہ جوڑا جا سکتا ہے۔ ایک نقطہ اپنے آپ سے بھی لکیر کے ذریعہ جوڑا جا سکتا ہے (اسے مدور کہتے ہیں)۔
نقاط کو اقمات کہتے ہیں، اور جوڑنے والی لکیر کو کنارہ۔ ایک کنارہ صرف دو اقمات کو آپس میں جوڑتا ہے۔
 
 
 
مثال کے طور پر تصویر 2 میں گھر کا نقشہ دیا ہے۔ اس نقشہ کا مخطط بنانے کے لیے ہر کمرے کو قمہ (دائرہ) سے دکھایا گیا ہے۔ جن دو کمروں کے درمیان دروازہ ہے، مخطط میں وہ کنارہ سے جڑے دکھائے گئے ہیں۔ اقمات پر کمرے کا عدد لکھا گیا ہے۔ اس طرح یہ کمروں کے اتصال کا مخطط ہے۔
{{اصطلاح برابر|
مُخطط <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}}
 
==مخطط اور اس کی اقسام==
<math>E(G) := \{\{1, 2\}, \{1, 5\}, \{2, 3\}, \{2, 5\}, \{3, 4\}, \{4, 5\}, \{4, 6\}\}</math>
</div>
تعریف: اگر دو اقمات کو ایک سے زیادہ کنارے جوڑتے ہوں، تو انھیں متعدد کنارے کہا جاتا ہے۔ اگر کنارہ قمہ کو اپنے آپ سے جوڑے تو اسے مدور کہا جاتا ہے۔ تصویر 3 میں سرخ رنگ میں تین "متعدد‌کنارے" دکھائے گئے ہیں۔ نیلے رنگ میں "مدور" ہے۔
[[Image:Undirected.svg|thumb|125px|سادہ‌مخطط، تین اقمات اور تین کنارے۔ چونکہ ہر قمہ کا درجہ دو ہے، اسلئے یہ باقاعدہ‌مخطط بھی ہے۔]]
 
</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 ہے۔
=== مکمل مُخطط===
: تفصیلی مضمون [[مکمل مخطط]]
ایسا مخطط جس کے کوئی بھی دو واضح اقمات صرف اور صرف ایک کنارے سے جڑی ہوں، کو مکمل مخطط کہا جاتا ہے۔ مکمل‌مخطط جس کی اقمات کی تعداد ''n'' ہو کو <math>K_n</math> لکھتے ہیں۔
 
===عدیمہ مخطط ===
جس مخطط میں کوئی کنارے نہ ہوں کو عدیمہ مخطط کہتے ہیں۔ عدیمہ‌مخطط جس کی اقمات کی تعداد ''n'' ہو کو <math>N_n</math> لکھتے ہیں۔ یہ مخطط باقاعدہ ہو گا درجہ 0 کے ساتھ۔
 
<table align="left">
 
===دورہ مخطط ===
مخطط جس میں صرف ایک [[چال (نظریہ مخطط)|دورہ]] ہو کو دورہ مخطط کہتے ہیں۔ دورہ‌مخطط جس کی اقمات کی تعداد ''n'' ہو کو <math>C_n</math> لکھتے ہیں۔
 
[[Image:Path-graph.svg|150px|thumb|رستہ مخطط <math>P_6</math>]]
===راستہ مخطط ===
مخطط جس میں صرف ایک [[رستہ (نظریہ مخطط)|رستہ]] ہو کو راستہ‌مخطط کہتے ہیں۔ رستہ مخطط جس کی اقمات کی تعداد ''n'' ہو کو <math>P_n</math> لکھتے ہیں۔
 
[[Image:bipartite_graph.svg|thumb|right|دوحصائی مخطط]]
=== سمتی مخطط===
:تفصیلی مضمون [[سمتی مخطط]]
ایسا مخطط جس میں کناروں کی سمت مقرر ہو جو تیر کے نشان سے دکھائی جاتی ہے۔ اسے یوں سمجھا جا سکتا ہے جیسے مقام ''ا'' اور ''ب'' کے درمیان ریل‌گاڑی مقام ''ا'' سے ''ب'' کی طرف چلتی ہو مگر دوسری جانب نہیں۔
:تعریف: سمتی مخطط ''D'' مشتمل ہوتا ہے ایک مجموعہ جسے ''اقمات'' کہتے ہیں، اور اقمات کے جوڑوں کی مرتب فہرست جنہیں ''تیر'' کہتے ہیں۔ اقمات کو "اقمات مجموعہ" <code dir="ltr">V(D)</code> لکھتے ہیں، اور تیروں کو "تیر فہرست" <code dir="ltr">A(D)</code> لکھتے ہیں۔ اگر ''a'' اور ''b'' اقمات ہیں تو تیر ''ab'' کی سمت ''a'' سے ''b'' ہوتی ہے، یا ''a'' کو ''b'' سے جوڑتا ہے (مگر ''b'' کو ''a'' سے نہیں جوڑتا)۔
 
[[Image:a_weighted_graph_example.svg|left|thumb|وزن شدہ مخطط]]
isomorphic <br> one to one correspondence <br> corresponding <br> pair }}
[[Image:Isomorphic_notequal_labeled_graphs.svg|right|thumb|250px|دونوں ملصق مخطط برابر نہیں، مگر متشاکل ہیں]]
[[Image:Isomorphic_unlabeled_graphs.svg|left|thumb|250px|دونوں ناملصق مخطط متشاکل ہیں]]
 
==متشاکل مخطط ==
دو مخطط ''G'' اور ''F'' کو متشاکل کہا جائے گا اگر ''G'' کو ''F'' میں تبدیل کیا جا سکے اس کے ملصق کی جگہ تبدیل کر کے۔ دوسرے الفاظ میں اگر ''G'' اور ''F'' کی اقمات میں ایسا ارتباط واحد الواحد ہو، کہ ''G'' میں کسی بھی "اقمات جوڑے" کو جوڑنے والے کنارے کی تعداد برابر ہو ''F'' میں ارتباطی "اقمات جوڑے" کو جوڑنے والے کناروں کی تعداد کے۔
 
==اور دیکھو ==
 
==بیرونی روابط ==
* [http://commons.wikimedia.org/wiki/Graph_theory commons]
 
{{ریاضی مدد}}
 
[[زمرہ:نگاری نظریہ]]
[[زمرہ:نظریہ مخطط]]
21,671

ترامیم