গ্রাফ রঞ্জন
যত কম সম্ভব রং দিয়ে একটি গ্রাফ রাঙান
এই ক্যালকুলেটর সম্পর্কে
গ্রাফ রঞ্জন ক্যালকুলেটর বর্ণ সংখ্যা χ(G) বের করে — অর্থাৎ একটি গ্রাফের শীর্ষবিন্দুগুলো এমনভাবে রং করতে ন্যূনতম কতগুলো রং লাগে যাতে কোনো ধার একই রঙের দুটি শীর্ষবিন্দুকে যুক্ত না করে — এবং একটি সর্বোত্তম রঞ্জন দেখায়। শীর্ষবিন্দুর সংখ্যা ও ধারের তালিকা লিখুন; এটি ব্রাঞ্চ-অ্যান্ড-বাউন্ড অনুসন্ধানে χ নির্ভুলভাবে হিসাব করে, সর্বোচ্চ মাত্রা Δ ও বৃহত্তম ক্লিক ω (χ-এর একটি নিম্নসীমা) দেখায়, দ্বিবিভাজিত ও পূর্ণ গ্রাফ চিহ্নিত করে এবং রঞ্জিত গ্রাফটি আঁকে। সময়সূচি তৈরি, রেজিস্টার বরাদ্দ, মানচিত্র রঞ্জন এবং বর্ণ সংখ্যা অধ্যয়নে কাজে লাগে।
একটি গ্রাফ কীভাবে রঞ্জন করবেন
- শীর্ষবিন্দুর সংখ্যা লিখুন; সেগুলো 1 থেকে n পর্যন্ত নম্বরযুক্ত।
- ধারগুলো 1-2, 2-3-এর মতো জোড়া হিসেবে লিখুন — প্রতিটি সংযোগে একটি জোড়া।
- বর্ণ সংখ্যা χ(G) এবং প্রতিটি শীর্ষবিন্দুতে নির্ধারিত রং দেখে নিন।
- কেন ততগুলো রং লাগে তা বুঝতে χ-কে বৃহত্তম ক্লিক ω-এর সঙ্গে তুলনা করুন, অথবা অন্বেষণের জন্য একটি প্রিসেট লোড করুন।
সাধারণ উদাহরণ
- একটি ত্রিভুজের (K₃) 3টি রং লাগে — এর প্রতিটি শীর্ষবিন্দু-জোড়া সংলগ্ন।
- জোড় চক্র দ্বিবিভাজিত এবং মাত্র 2টি রং লাগে; C₅-এর মতো বিজোড় চক্রে 3টি লাগে।
- পূর্ণ গ্রাফ Kₙ-এর ঠিক n-টি রং লাগে।
- ω আকারের একটি বৃহত্তম ক্লিক কমপক্ষে ω-টি রং বাধ্যতামূলক করে, তাই χ(G) ≥ ω।
- গ্রোয়ৎশ গ্রাফে কোনো ত্রিভুজ না থাকলেও 4টি রং লাগে, তাই χ ক্লিক সংখ্যাকে ছাড়িয়ে যেতে পারে।
প্রায়শই জিজ্ঞাসিত প্রশ্ন
বর্ণ সংখ্যা কী?
বর্ণ সংখ্যা χ(G) হলো একটি গ্রাফের শীর্ষবিন্দুগুলো এমনভাবে রং করতে প্রয়োজনীয় ন্যূনতম রঙের সংখ্যা, যাতে কোনো ধার একই রঙের দুটি শীর্ষবিন্দুকে যুক্ত না করে।
ন্যূনতম রঙের সংখ্যা কীভাবে বের করা হয়?
গ্রাফটি ছোট বলে ক্যালকুলেটর নির্ভুলভাবে অনুসন্ধান করে: প্রথমে 1টি রং, তারপর 2টি, এভাবে চেষ্টা করে এবং প্রথম যে সংখ্যায় একটি যথাযথ রঞ্জন সম্ভব সেটি ফেরত দেয়। সেই সংখ্যাটি নিশ্চিতভাবে প্রকৃত ন্যূনতম।
সর্বোচ্চ মাত্রা ও বৃহত্তম ক্লিক কী?
সর্বোচ্চ মাত্রা Δ হলো যেকোনো একটি শীর্ষবিন্দুতে মিলিত সর্বাধিক ধারের সংখ্যা। বৃহত্তম ক্লিক ω হলো শীর্ষবিন্দুর সবচেয়ে বড় সেট যার সবগুলো পরস্পর সংলগ্ন; যেহেতু এদের সবার রং আলাদা হতে হবে, χ(G) কমপক্ষে ω।
ত্রিভুজহীন গ্রাফেও কেন অনেক রং লাগতে পারে?
একটি বড় ক্লিক অনেক রং বাধ্যতামূলক করে, কিন্তু এটিই একমাত্র কারণ নয়। বিজোড় চক্র এবং গ্রোয়ৎশ গ্রাফের মতো গ্রাফে কোনো ত্রিভুজ না থাকলেও অতিরিক্ত রং লাগে, তাই χ(G) ক্লিক সংখ্যার চেয়ে বড় হতে পারে।
গ্রাফের আকারের কি কোনো সীমা আছে?
হ্যাঁ। নির্ভুল গ্রাফ রঞ্জন গণনাগতভাবে কঠিন, তাই ফলাফল তাৎক্ষণিক ও নিখুঁত রাখতে ক্যালকুলেটর গ্রাফকে সর্বোচ্চ 12টি শীর্ষবিন্দুতে সীমিত রাখে।