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

5 بائٹ کا اضافہ ،  3 سال پہلے
م
درستی
م (درستی)
[[فائل:6n-graf.svg|تصغیر|250px|بائیں|تصویر 1: ملصق گراف کی نقاشی جس میں 6 راس اور 7 کنارے ہیں۔]]
<!--{{اصطلاح برابر|}} placed after the intro, for better mobile view -->
ریاضی میں '''گراف''' نقاط اور لکیروں پر مشتمل ہوتا ہے، ایسا کہ ہر لکیر صرف دو نقاط کو جوڑتی ہے۔ کوئی بھی نقاط کا جوڑا لکیر کے ذریعہ جوڑا جا سکتا ہے۔ ایک نقطہ اپنے آپ سے بھی لکیر کے ذریعہ جوڑا جا سکتا ہے (اسے مدور کہتے ہیں)۔
نقاط کو [[راس (نظریہ گراف)|راس]] کہتے ہیں اور جوڑنے والی لکیر کو کنارہ۔ ایک کنارہ صرف دو راس کو آپس میں جوڑتا ہے۔
 
[[فائل:house_layout_plan_and_its_graph.svg|وسط|تصغیر|400px|تصویر 2:گھر کا نقشہ اور گراف]]
 
[[فائل:Multigraph.svg|تصغیر|125px|بائیں|تصویر 3: مخططگراف کی جامع مثال۔ تین اقمات اور چھ کنارے۔]]
[[فائل:Isomorphic_and_equal_labeled_graphs.svg|دائیں|تصغیر|250px|دکھائے گئے دونوں مخططگراف دراصل ایک ہی ملصق گراف کی نقاشی ہے (دونوں گراف برابر ہیں، یعنی دو انداز سے ایک ہی گراف دکھایا گیا ہے)۔]]
 
{{اصطلاح برابر|
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">
</div>
تعریف: اگر دو راس کو ایک سے زیادہ کنارے جوڑتے ہوں، تو انھیں متعدد کنارے کہا جاتا ہے۔ اگر کنارہ راس کو اپنے آپ سے جوڑے تو اسے مدور کہا جاتا ہے۔ تصویر 3 میں سرخ رنگ میں تین "متعددکنارے" دکھائے گئے ہیں۔ نیلے رنگ میں "مدور" ہے۔
[[فائل:Undirected.svg|تصغیر|125px|سادہ‌مخطط،سادہ‌گراف، تین راس اور تین کنارے۔ چونکہ ہر قمہ کا درجہ دو ہے، اسلئے یہ باقاعدہ‌گراف بھی ہے۔]]
 
=== سادہ گراف ===
<tr>
<td>[[فائل:disconnected_simple_graph.svg|تصغیر|250px|نامتصل گراف]]
<td>[[فائل:subgraph_and_graph.svg|بائیں|تصغیر|250px|مخططگراف کا ذیلی‌گراف گہرے رنگ میں دکھایا گیا ہے۔]]
</tr>
</table>
 
=== عدیمہ گراف ===
جس گراف میں کوئی کنارے نہ ہوں کو عدیمہ گراف کہتے ہیں۔ عدیمہ‌گراف جس کی راس کی تعداد ''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'' کے کسی قمہ سے جوڑتا ہو۔ تصویر میں اقمات کے ذیلی مجموعات کو "نیلے" اور "سرخ" رنگ میں دکھایا گیا ہے۔
[[فائل:Isomorphic_unlabeled_graphs.svg|بائیں|تصغیر|250px|دونوں ناملصق گراف متشاکل ہیں]]
 
== متشاکل مخططگراف ==
دو گراف ''G'' اور ''F'' کو متشاکل کہا جائے گا اگر ''G'' کو ''F'' میں تبدیل کیا جا سکے اس کے ملصق کی جگہ تبدیل کر کے۔ دوسرے الفاظ میں اگر ''G'' اور ''F'' کی راس میں ایسا ارتباط واحد الواحد ہو، کہ ''G'' میں کسی بھی "راس جوڑے" کو جوڑنے والے کنارے کی تعداد برابر ہو ''F'' میں ارتباطی "راس جوڑے" کو جوڑنے والے کناروں کی تعداد کے ۔
 
 
{{ریاضی مدد}}
 
 
[[زمرہ:نظریہ گراف]]
43,445

ترامیم