"گراف (ریاضی)" کے نسخوں کے درمیان فرق
م درستی |
م درستی |
||
سطر 4: | سطر 4: | ||
نقاط کو [[راس (نظریہ گراف)|راس]] کہتے ہیں اور جوڑنے والی لکیر کو کنارہ۔ ایک کنارہ صرف دو راس کو آپس میں جوڑتا ہے۔ |
نقاط کو [[راس (نظریہ گراف)|راس]] کہتے ہیں اور جوڑنے والی لکیر کو کنارہ۔ ایک کنارہ صرف دو راس کو آپس میں جوڑتا ہے۔ |
||
مثال کے طور پر تصویر 2 میں گھر کا نقشہ دیا ہے۔ اس نقشہ کا گراف بنانے کے لیے ہر کمرے کو راس (دائرہ) سے دکھایا گیا ہے۔ جن دو کمروں کے درمیان دروازہ ہے، گراف میں وہ کنارہ سے جڑے دکھائے گئے ہیں۔ |
مثال کے طور پر تصویر 2 میں گھر کا نقشہ دیا ہے۔ اس نقشہ کا گراف بنانے کے لیے ہر کمرے کو راس (دائرہ) سے دکھایا گیا ہے۔ جن دو کمروں کے درمیان دروازہ ہے، گراف میں وہ کنارہ سے جڑے دکھائے گئے ہیں۔ راس پر کمرے کا عدد لکھا گیا ہے۔ اس طرح یہ کمروں کے اتصال کا گراف ہے۔ |
||
[[فائل:house_layout_plan_and_its_graph.svg|وسط|تصغیر|400px|تصویر 2:گھر کا نقشہ اور گراف]] |
[[فائل:house_layout_plan_and_its_graph.svg|وسط|تصغیر|400px|تصویر 2:گھر کا نقشہ اور گراف]] |
||
[[فائل:Multigraph.svg|تصغیر|125px|بائیں|تصویر 3: گراف کی جامع مثال۔ تین |
[[فائل:Multigraph.svg|تصغیر|125px|بائیں|تصویر 3: گراف کی جامع مثال۔ تین راس اور چھ کنارے۔]] |
||
[[فائل:Isomorphic_and_equal_labeled_graphs.svg|دائیں|تصغیر|250px|دکھائے گئے دونوں گراف دراصل ایک ہی ملصق گراف کی نقاشی ہے (دونوں گراف برابر ہیں، یعنی دو انداز سے ایک ہی گراف دکھایا گیا ہے)۔]] |
[[فائل:Isomorphic_and_equal_labeled_graphs.svg|دائیں|تصغیر|250px|دکھائے گئے دونوں گراف دراصل ایک ہی ملصق گراف کی نقاشی ہے (دونوں گراف برابر ہیں، یعنی دو انداز سے ایک ہی گراف دکھایا گیا ہے)۔]] |
||
سطر 15: | سطر 15: | ||
== گراف اور اس کی اقسام == |
== گراف اور اس کی اقسام == |
||
تعریف: ''گراف'' ''G'' مشتمل ہوتا ہے غیر خالی مجموعہ پر جس کے ارکان راس ہوتے ہیں اور ان ارکان کے جوڑوں کی نامرتب فہرست پر، جنہیں کنارے کہا جاتا ہے۔ راس کے مجموعہ کو گراف کا "راس مجموعہ" کہتے ہیں اور <code dir="ltr">''V(G)''</code> لکھتے ہیں۔ کناروں کی فہرست کو "کنارہ فہرست" کہتے ہیں اور <code dir="ltr">''E(G)''</code> لکھتے ہیں۔ اگر ''u'' اور ''v'' |
تعریف: ''گراف'' ''G'' مشتمل ہوتا ہے غیر خالی مجموعہ پر جس کے ارکان راس ہوتے ہیں اور ان ارکان کے جوڑوں کی نامرتب فہرست پر، جنہیں کنارے کہا جاتا ہے۔ راس کے مجموعہ کو گراف کا "راس مجموعہ" کہتے ہیں اور <code dir="ltr">''V(G)''</code> لکھتے ہیں۔ کناروں کی فہرست کو "کنارہ فہرست" کہتے ہیں اور <code dir="ltr">''E(G)''</code> لکھتے ہیں۔ اگر ''u'' اور ''v'' راس ہوں، تو کنارہ ''uv'' یا ''vw''، راس ''u'' اور ''v'' کو آپس میں "مِلاتا" ہے۔ |
||
تصویر 1 میں |
تصویر 1 میں |
||
<div dir="ltr"> |
<div dir="ltr"> |
||
سطر 46: | سطر 46: | ||
گراف مٰیں تمام راس کے درجات کی حاصل جمع دوگنی ہوتی ہے کناروں کی تعداد کے ۔ |
گراف مٰیں تمام راس کے درجات کی حاصل جمع دوگنی ہوتی ہے کناروں کی تعداد کے ۔ |
||
* راس کے درجات کا حاصلجمع [[جفت عدد]] ہوتا ہے۔ |
* راس کے درجات کا حاصلجمع [[جفت عدد]] ہوتا ہے۔ |
||
* ایسی |
* ایسی راس جن کا درجہ [[طاق عدد]] ہو، کی تعداد جفت عدد ہوتی ہے۔ |
||
* باقاعدہگراف درجہ ''r'' کے ساتھ، کی |
* باقاعدہگراف درجہ ''r'' کے ساتھ، کی راس کی تعداد ''n'' ہو، تو کناروں کی تعداد <math>\frac{nr}{2}</math> ہو گی۔ |
||
{{اصطلاح برابر| |
{{اصطلاح برابر| |
||
سطر 67: | سطر 67: | ||
=== دورہ گراف === |
=== دورہ گراف === |
||
گراف جس میں صرف ایک [[چال (نظریہ گراف)|دورہ]] ہو کو دورہ گراف کہتے ہیں۔ دورہگراف جس کی |
گراف جس میں صرف ایک [[چال (نظریہ گراف)|دورہ]] ہو کو دورہ گراف کہتے ہیں۔ دورہگراف جس کی راس کی تعداد ''n'' ہو کو <math>C_n</math> لکھتے ہیں۔ |
||
[[فائل:Path-graph.svg|150px|تصغیر|رستہ گراف <math>P_6</math>]] |
[[فائل:Path-graph.svg|150px|تصغیر|رستہ گراف <math>P_6</math>]] |
||
=== راستہ گراف === |
=== راستہ گراف === |
||
گراف جس میں صرف ایک [[رستہ (نظریہ گراف)|رستہ]] ہو کو راستہگراف کہتے ہیں۔ رستہ گراف جس کی |
گراف جس میں صرف ایک [[رستہ (نظریہ گراف)|رستہ]] ہو کو راستہگراف کہتے ہیں۔ رستہ گراف جس کی راس کی تعداد ''n'' ہو کو <math>P_n</math> لکھتے ہیں۔ |
||
[[فائل:bipartite_graph.svg|تصغیر|دائیں|دوحصائی گراف]] |
[[فائل:bipartite_graph.svg|تصغیر|دائیں|دوحصائی گراف]] |
||
=== دوحصائی گراف === |
=== دوحصائی گراف === |
||
ایسا گراف جس کے راس مجموعہ کو دو ذیلی مجموعات ''A'' اور ''B'' میں بانٹا جا سکے اس طرح کہ ہر کنارہ مجموعہ ''A'' کے کسی قمہ کو مجموعہ ''B'' کے کسی قمہ سے جوڑتا ہو۔ تصویر میں |
ایسا گراف جس کے راس مجموعہ کو دو ذیلی مجموعات ''A'' اور ''B'' میں بانٹا جا سکے اس طرح کہ ہر کنارہ مجموعہ ''A'' کے کسی قمہ کو مجموعہ ''B'' کے کسی قمہ سے جوڑتا ہو۔ تصویر میں راس کے ذیلی مجموعات کو "نیلے" اور "سرخ" رنگ میں دکھایا گیا ہے۔ |
||
{{اصطلاح برابر| |
{{اصطلاح برابر| |
||
سمتی گراف <br/> موزون گراف| |
سمتی گراف <br/> موزون گراف| |
||
سطر 88: | سطر 88: | ||
=== موزون گراف === |
=== موزون گراف === |
||
موزون گراف، ایسا گراف جس میں ہر کنارے کے ساتھ ایک مثبت عدد نتھی کر دیا جائے جو اس کا وزن کہلائے۔ مثلاً اگر |
موزون گراف، ایسا گراف جس میں ہر کنارے کے ساتھ ایک مثبت عدد نتھی کر دیا جائے جو اس کا وزن کہلائے۔ مثلاً اگر راس شہر ہوں تو وزن دو شہروں کے درمیان فاصلہ۔ |
||
{{اصطلاح برابر| |
{{اصطلاح برابر| |
نسخہ بمطابق 05:56، 31 مارچ 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 پڑھیٔے ریاضی علامات