لونی کثیر رقمی

اصطلاح	term
لونی ملصق مشارک راس کنار	Chromatic labeled associate vertex, vertices edge

نقشہ (ممالک کے ) میں رنگ بھرتے ہوئے دو ہمسایہ اضلاع جن کی سرحد بے اصل نہ ہو (یعنی نقطہ سے زیادہ ہو) پر مختلف رنگ چننے ہوتے ہیں۔ اگر نقشہ M میں بھرنے کے لیے آپ کے پاس $\lambda$ رنگ ہوں، تو رنگ بھرنے کی راہوں کی تعداد ایک کثیر رقمی $\ P(M,\lambda )$ سے دی جا سکتی ہے،

فائل:Chromatic polynomial m4 example.svg

تصویر 1: M₄ نقشہ

$\ P(M,\lambda )=c_{0}+c_{1}\lambda +c_{2}\lambda ^{2}+\cdots +c_{k}\lambda ^{k}$

جہاں $c_{0},c_{1},\cdots ,c_{k}$ صحیح اعداد ہیں اور نقشہ میں اضلاع کی تعداد k ہے۔ (یہاں ہم یہ سمجھتے ہیں کہ کوئی ملک دو بچھڑے ہوئے اضلاع پر مشتمل نہیں ہے۔) اس کثیر رقمی کو 'لونی کثیر رقمی کہا جاتا ہے۔

مثلاً دو اضلاع کے نقشہ $M_{1}$ میں پہلے ضلع کے لیے رنگ چننے کی راہیں $\lambda$ ہیں اور دوسرے ضلع کے لیے $\lambda -1$، اس لیے نقشہ میں رنگ بھرنے کی راہیں

$\ P(\lambda ,M_{1})=\lambda (\lambda -1)=\lambda ^{2}-1$

ہیں۔

تصویر میں نقشہ M₄ زیادہ پچیدہ ہے۔ ضلع د اور ب کے رنگ مختلف ہوں گے، مگر ضلع د اور ج کا رنگ ایک ہی ہو سکتا ہے۔ اس طرح دو صورتیں ہیں:

1. ضلع "ب" اور "ک" کا رنگ ایک ہے: ضلع "د" کے $\lambda$ رنگ ممکن ہیں اور "ب" اور "ک" کے مشترکہ رنگ کے $\lambda -1$ ممکن اور "ج" کے $\lambda -1$ ممکن (کیونکہ اس کا رنگ وہی جو "د" کا ہے ہو سکتا ہے)۔
2. ضلع "ب" اور "ک" کے رنگ مختلف ہیں: ضلع "د" کے $\lambda$ رنگ ممکن ہیں، "ب" کے $\lambda -1$، "ک" کے $\lambda -2$ اور "ج" کے $\lambda -2$ ("ج" کا رنگ "ب" اور "ک" جیسا نہیں ہو سکتا)۔

ان دونوں صورتوں کی راہوں کو جمع کر کے لونی کثیر رقمی بنتا ہے:

$\ P(M_{4},\lambda )=\lambda (\lambda -1)^{2}+\lambda (\lambda -1)(\lambda -2)^{2}=\lambda ^{4}-4\lambda ^{3}+6\lambda ^{2}-3\lambda$

فائل:Graph m4 example.svg

تصویر 2: M₄ کا گراف

ملصق نقشہ کے ساتھ ہم ملصق گراف مشارک کر سکتے ہیں، اس طرح کہ نقشہ کے ضلع سے گراف کے قمہ کو مشارک کر دیا جائے اور اگر دو اضلاع میں مشترکہ سرحد ہو تو مشارکہ راس کو کنار (لکیر) کے ساتھ جوڑ دیا جائے۔ تصویر 2 میں تصویر 1 کے نقشہ سے مشارک گراف دکھایا گیا ہے۔ نقشہ میں یوں رنگ بھرنے کہ مشترکہ سرحد والے اضلاع مختلف رنگی ہوں کے حوالے سے ضروری ہے کہ گراف کی راس کو یوں رنگا جائے کہ جو دو راس کنار سے جڑی ہوں وہ مختلف رنگ میں ہوں۔ تصویر 2 میں "ب" اور "ک" راس چونکہ آپس میں کنار سے جڑی نہیں ہوئی، اس لیے یہ ایک ہی رنگ کی جا سکتی ہیں۔ جس طرح نقشہ کے لیے لونی کثیر رقمی تعریف کیا گیا ہے، اسی طرح گراف کے لیے بھی کیا جا سکتا ہے: گراف کا لونی کثیر رقمی گراف کے راس کو رنگ کرنے کی راہیں بتاتا ہے، اس طرح کہ وہ راس جو کنار کے ذریعہ ملی ہوں مختلف رنگ میں ہوں۔

اگرچہ مستوی میں کسی بھی نقشہ کا گراف بنایا جا سکتا ہے، مگر ہر گراف کا مستوی میں نقشہ ہونا ممکن نہیں ہوتا۔

فائل:Empty graph.svg تصویر 3۔ خالی گراف

فائل:Complete graph.svg تصویر 4۔ مکمل گراف

لونی کثیر رقمی نکالنے کے طریقہ میں تولیفات کی تعداد بہت زیادہ ہو جاتی ہے۔ نیچے ہم کچھ نتائج بیان کرتے ہیں جن کی مدد سے تکراری طریقہ سے یہ کثیر رقمی معلوم کیے جا سکتے ہیں۔

خالی گراف ایسے گراف کو کہا جاتا ہے جس میں صرف n راس ہو اور کوئی کنار نہ ہو (تصویر 3)۔ اس گراف کا لونی کثیر رقمی $\lambda ^{n}$ ہے۔

مکمل گراف ایسے گراف کو کہا جاتا ہے جس میں n راس ہو اور ان میں سے ہر دو کنار سے جڑی ہوں (تصویر 4)۔ اس گراف کا لونی کثیر رقمی

$\ P(G,\lambda )=\lambda (\lambda -1)\cdots (\lambda -(n-1))$

ہے۔

فائل:Maximally connected subgraphs.svg

تصویر 5۔ گراف G کے جزو

گراف کو متصل کہتے ہیں اگر کسی بھی قمہ سے کسی بھی دوسرے قمہ تک جانے کا راستہ (کناروں سے ہوتے ہوئے) موجود ہو۔

گراف کا جزو ایسا ذیلی گراف ہوتا ہے جو اعظم التصال ہو، یعنی یہ ذیلی گراف کسی دوسرے متصل ذیلی گراف کے اندر نہ سماء سکے۔ تصویر 5 میں گراف G کے دو جزو G₁ اور G₂ ہیں۔ گراف G کا لونی کثیر رقمی ان دو جزو گراف کے لونی کثیر رقمی جانتے ہوئے یوں لکھا جاوے ہے:

$\ P(G,\lambda )=P(G_{1},\lambda )P(G_{2},\lambda )$

ہے۔ تصویر 5 میں راس a اور b اور انھیں جوڑنے والے کنارے پر مشتمل ذیلی گراف جزو نہیں، کیونکہ یہ بڑے متصل ذیلی گراف G₁ میں سما جاتا ہے۔

اصطلاح	term
خالی گراف مکمل گراف اعظم التصال متصل	empty graph complete graph maximally connected connected

تصویر 6۔

تصویر 6

تصویر 6 میں گراف G کے کنار E کے حوالے سے دو گراف تعریف کرتے ہیں۔ کنار E کو مٹا دینے سے گراف G_E_1 حاصل ہوتا ہے۔ اب G_E_1 میں ان دو راس (a اور b جو کنار E سے جڑے تھے) کو ایک تصور کرتے ہوئے گراف G_E_2 حاصل ہوتا ہے۔ اصل گراف کے لونی کثیر رقمی ان دو گراف کے لونی کثیر رقمی کی مدد سے یوں لکھا جا سکتا ہے:

$\ P(G,\lambda )=P(G_{E1},\lambda )-P(G_{E2},\lambda )$

خصوصیاتِ لونی کثیررقمی

گراف G جس کی راس کی تعداد n ہو کا لونی کثیر رقمی $\ P(G,\lambda )$

• $\ P(G,\lambda )$ کا درجہ n ہے۔
• $\ P(G,\lambda )$ میں $\lambda ^{n}$ کا عددی سر 1 ہے۔
• $\ P(G,\lambda )$ میں دائم رقم نہیں ہوتی۔
• $\ P(G,\lambda )$ کی رقوم کے اشارات اُلٹتے رہتے ہیں، یعنی (مثبت، منفی، مثبت، منفی، ...)
• $\ P(G,\lambda )$ کے دوسرے عددی سر کی مطلق قدر گراف میں کناروں کی تعداد کے برابر ہوتی ہے۔
• اگر G متصل گراف ہو، تو $\ P(G,\lambda )\leq \lambda (\lambda -1)^{n-1}$ کسی بھی مثبت $\lambda$ کے لیے۔

==بیرونی روابط ==*

E=mc2     اردو ویکیپیڈیا پر ریاضی مساوات کو بائیں سے دائیں LTR پڑھیٔے     ریاضی علامات

Chromatic polynomial