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

36 بائٹ کا ازالہ ،  4 سال پہلے
م
درستی
م (درستی)
م (درستی)
نقاط کو [[راس (نظریہ گراف)|راس]] کہتے ہیں اور جوڑنے والی لکیر کو کنارہ۔ ایک کنارہ صرف دو راس کو آپس میں جوڑتا ہے۔
 
مثال کے طور پر تصویر 2 میں گھر کا نقشہ دیا ہے۔ اس نقشہ کا گراف بنانے کے لیے ہر کمرے کو راس (دائرہ) سے دکھایا گیا ہے۔ جن دو کمروں کے درمیان دروازہ ہے، گراف میں وہ کنارہ سے جڑے دکھائے گئے ہیں۔ اقماتراس پر کمرے کا عدد لکھا گیا ہے۔ اس طرح یہ کمروں کے اتصال کا گراف ہے۔
[[فائل:house_layout_plan_and_its_graph.svg|وسط|تصغیر|400px|تصویر 2:گھر کا نقشہ اور گراف]]
 
[[فائل:Multigraph.svg|تصغیر|125px|بائیں|تصویر 3: گراف کی جامع مثال۔ تین اقماتراس اور چھ کنارے۔]]
[[فائل:Isomorphic_and_equal_labeled_graphs.svg|دائیں|تصغیر|250px|دکھائے گئے دونوں گراف دراصل ایک ہی ملصق گراف کی نقاشی ہے (دونوں گراف برابر ہیں، یعنی دو انداز سے ایک ہی گراف دکھایا گیا ہے)۔]]
 
 
== گراف اور اس کی اقسام ==
تعریف: ''گراف'' ''G'' مشتمل ہوتا ہے غیر خالی مجموعہ پر جس کے ارکان راس ہوتے ہیں اور ان ارکان کے جوڑوں کی نامرتب فہرست پر، جنہیں کنارے کہا جاتا ہے۔ راس کے مجموعہ کو گراف کا "راس مجموعہ" کہتے ہیں اور <code dir="ltr">''V(G)''</code> لکھتے ہیں۔ کناروں کی فہرست کو "کنارہ فہرست" کہتے ہیں اور <code dir="ltr">''E(G)''</code> لکھتے ہیں۔ اگر ''u'' اور ''v'' اقماتراس ہوں، تو کنارہ ''uv'' یا ''vw''، راس ''u'' اور ''v'' کو آپس میں "مِلاتا" ہے۔
تصویر 1 میں
<div dir="ltr">
گراف مٰیں تمام راس کے درجات کی حاصل جمع دوگنی ہوتی ہے کناروں کی تعداد کے ۔
* راس کے درجات کا حاصل‌جمع [[جفت عدد]] ہوتا ہے۔
* ایسی اقماتراس جن کا درجہ [[طاق عدد]] ہو، کی تعداد جفت عدد ہوتی ہے۔
* باقاعدہ‌گراف درجہ ''r'' کے ساتھ، کی اقماتراس کی تعداد ''n'' ہو، تو کناروں کی تعداد <math>\frac{nr}{2}</math> ہو گی۔
 
{{اصطلاح برابر|
 
=== دورہ گراف ===
گراف جس میں صرف ایک [[چال (نظریہ گراف)|دورہ]] ہو کو دورہ گراف کہتے ہیں۔ دورہ‌گراف جس کی اقماتراس کی تعداد ''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/> موزون گراف|
 
=== موزون گراف ===
موزون گراف، ایسا گراف جس میں ہر کنارے کے ساتھ ایک مثبت عدد نتھی کر دیا جائے جو اس کا وزن کہلائے۔ مثلاً اگر اقماتراس شہر ہوں تو وزن دو شہروں کے درمیان فاصلہ۔
 
{{اصطلاح برابر|
43,445

ترامیم