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

بائیں|frame|تصویر 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 زیادہ پچیدہ ہے۔ ضلع د اور ب کے رنگ مختلف ہوں گے، مگر ضلع د اور ج کا رنگ ایک ہی ہو سکتا ہے۔ اس طرح دو صورتیں ہیں:
# ضلع "ب" اور "ک" کا رنگ ایک ہے: ضلع "د" کے \lambda رنگ ممکن ہیں اور "ب" اور "ک" کے مشترکہ رنگ کے \lambda-1 ممکن اور "ج" کے \lambda-1 ممکن (کیونکہ اس کا رنگ وہی جو "د" کا ہے ہو سکتا ہے)۔
# ضلع "ب" اور "ک" کے رنگ مختلف ہیں: ضلع "د" کے \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

بائیں|frame|تصویر 2: M4 کا گراف

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

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


frame|تصویر 3۔ خالی گراف
frame|تصویر 4۔ مکمل گراف


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

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

مکمل گراف ایسے گراف کو کہا جاتا ہے جس میں n راس ہو اور ان میں سے ہر دو کنار سے جڑی ہوں (تصویر 4)۔ اس گراف کا لونی کثیر رقمی
:\ P(G,\lambda) = \lambda (\lambda-1) \cdots (\lambda-(n-1))
ہے۔

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

گراف کا جزو ایسا ذیلی گراف ہوتا ہے جو اعظم التصال ہو، یعنی یہ ذیلی گراف کسی دوسرے متصل ذیلی گراف کے اندر نہ سماء سکے۔ تصویر 5 میں گراف G کے دو جزو G1 اور G2 ہیں۔ گراف G کا لونی کثیر رقمی ان دو جزو گراف کے لونی کثیر رقمی جانتے ہوئے یوں لکھا جاوے ہے:
:\ P(G,\lambda) = P(G_1,\lambda) P(G_2,\lambda)
ہے۔
تصویر 5 میں راس a اور b اور انھیں جوڑنے والے کنارے پر مشتمل ذیلی گراف جزو نہیں، کیونکہ یہ بڑے متصل ذیلی گراف G1 میں سما جاتا ہے۔


تصویر 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 کے لیے۔

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


زمرہ:تالیفیات
زمرہ:نظریہ گراف
زمرہ:نگاری نظریہ