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

آزاد دائرۃ المعارف، ویکیپیڈیا سے
:چھلانگ بطرف رہنمائی، تلاش
اصطلاح term

لونی
ملصق
مشارک
قِمّہ، اقمات
کنار

Chromatic
labeled
associate
vertex, vertices
edge

تصویر 1: M4 نقشہ

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

\ 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

ہیں۔

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

  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
تصویر 2: M4 کا مخطط

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

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

تصویر 3۔ خالی مخطط
تصویر 4۔ مکمل مخطط

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

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

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

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

ہے۔

تصویر 5۔ مخطط G کے جزو

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

مخطط کا جزو ایسا ذیلی مخطط ہوتا ہے جو اعظم التصال ہو، یعنی یہ ذیلی مخطط کسی دوسرے متصل ذیلی مخطط کے اندر نہ سماء سکے۔ تصویر 5 میں مخطط G کے دو جزو G1 اور G2 ہیں۔ مخطط G کا لونی کثیر رقمی ان دو جزو مخطط کے لونی کثیر رقمی جانتے ہوئے یوں لکھا جاوے ہے:

\ P(G,\lambda) = P(G_1,\lambda) P(G_2,\lambda)

ہے۔ تصویر 5 میں اقمات a اور b اور انھیں جوڑنے والے کنارے پر مشتمل ذیلی مخطط جزو نہیں، کیونکہ یہ بڑے متصل ذیلی مخطط G1 میں سما جاتا ہے۔

اصطلاح 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) \le \lambda (\lambda-1)^{n-1} کسی بھی مثبت \lambda کے لیے۔

بیرونی روابط[ترمیم]

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

Chromatic polynomial