Hajós construction
গণিতের একটি শাখা, গ্রাফ তত্ত্বে, হাজোস গঠন হল সেই নামে নামকরণ করা গ্রাফের উপর একটি অপারেশন যা যে কোনও সমালোচনামূলক গ্রাফ বা যে কোনও গ্রাফ তৈরি করতে ব্যবহার করা যেতে পারে যার ক্রোমাটিক সংখ্যা কমপক্ষে কিছু প্রদত্ত প্রান্তিক। নির্মাণ দুটি অনির্দিষ্ট গ্রাফ হতে দিন, এর একটি প্রান্ত হতে দিন এবং এর একটি প্রান্ত হতে দিন। তারপর হাজোস নির্মাণ একটি নতুন গ্রাফ গঠন করে যা দুটি গ্রাফকে একত্রিত করে শীর্ষগুলি সনাক্ত করে এবং একটি একক শীর্ষে, দুটি প্রান্ত সরিয়ে এবং একটি নতুন প্রান্ত যোগ করে। উদাহরণস্বরূপ, ধরা যাক এবং প্রতিটি চারটি শীর্ষে একটি সম্পূর্ণ গ্রাফ; এই গ্রাফগুলির প্রতিসাম্যের কারণে, তাদের প্রত্যেকটির মধ্যে থেকে কোন প্রান্তটি নির্বাচন করা হবে তা গুরুত্বপূর্ণ নয়। এই ক্ষেত্রে, হাজোস নির্মাণ প্রয়োগের ফলাফল হল মোজার স্পিন্ডল, একটি সাত-ভার্টেক্স একক দূরত্বের গ্রাফ যার জন্য চারটি রঙের প্রয়োজন। আরেকটি উদাহরণ হিসাবে, যদি এবং যথাক্রমে দৈর্ঘ্যের চক্র গ্রাফ হয়, তবে হাজোস নির্মাণের প্রয়োগের ফলাফল নিজেই দৈর্ঘ্যের একটি চক্র গ্রাফ। একটি গ্রাফকে-গঠনযোগ্য (বা হাজোস-গঠনযোগ্য) বলা হয় যখন এটি নিম্নলিখিত তিনটি উপায়ে গঠিত হয়ঃ সম্পূর্ণ গ্রাফটি-নির্মাণযোগ্য। যে কোনও দুটি-গঠনযোগ্য গ্রাফ হতে দিন। তারপর হাজোস গঠন প্রয়োগ করে তৈরি গ্রাফটি-গঠনযোগ্য। যে কোনও-গঠনযোগ্য গ্রাফ হতে দিন এবং যে কোনও দুটি অ-সংলগ্ন শীর্ষ হতে দিন। তারপর সংমিশ্রণে এবং একটি একক শীর্ষে গঠিত গ্রাফটিও-গঠনযোগ্য। সমতুল্যভাবে, এই গ্রাফটি গ্রাফের প্রান্ত যোগ করে এবং তারপর এটি সংকুচিত করে তৈরি করা যেতে পারে। রঙের সঙ্গে সংযোগ প্রতিটি-গঠনযোগ্য গ্রাফের যে কোনও সঠিক গ্রাফের রঙে কমপক্ষে রঙের প্রয়োজন হয় কিনা তা যাচাই করা সহজ। প্রকৃতপক্ষে, এটি সম্পূর্ণ গ্রাফের জন্য স্পষ্ট, এবং দুটি অ-সংলগ্ন শীর্ষ চিহ্নিত করার প্রভাব হল যে কোনও রঙে একে অপরের মতো একই রঙ রাখতে বাধ্য করা, এমন কিছু যা রঙের সংখ্যা হ্রাস করে না। হাজোস নির্মাণে, নতুন প্রান্তটি দুটি শীর্ষের মধ্যে কমপক্ষে একটিকে বাধ্য করে এবং এবং এর জন্য সম্মিলিত শীর্ষের চেয়ে আলাদা রঙ রাখে, তাই সম্মিলিত গ্রাফের যে কোনও সঠিক রঙ দুটি ছোট গ্রাফের মধ্যে একটির সঠিক রঙের দিকে পরিচালিত করে যা থেকে এটি গঠিত হয়েছিল, যার ফলে আবার এটির রঙের প্রয়োজন হয়। হাজোস আরও দৃঢ়ভাবে প্রমাণ করেছিলেন যে একটি গ্রাফের জন্য কমপক্ষে রঙের প্রয়োজন হয়, যে কোনও সঠিক রঙে, যদি এবং শুধুমাত্র যদি এতে একটি উপগ্রাফ হিসাবে একটি-গঠনযোগ্য গ্রাফ থাকে। সমতুল্যভাবে, প্রতিটি-সমালোচনামূলক গ্রাফ (এমন একটি গ্রাফ যার জন্য রঙের প্রয়োজন হয় কিন্তু যার জন্য প্রতিটি সঠিক উপ-গ্রাফের জন্য কম রঙের প্রয়োজন হয়)-গঠনযোগ্য। বিকল্পভাবে, রঙের প্রয়োজন এমন প্রতিটি গ্রাফ হাজোস নির্মাণের সংমিশ্রণ, যে কোনও দুটি অ-সংলগ্ন শীর্ষগুলি সনাক্ত করার ক্রিয়াকলাপ এবং সম্পূর্ণ গ্রাফ থেকে শুরু করে প্রদত্ত গ্রাফে একটি শীর্ষ বা প্রান্ত যুক্ত করার ক্রিয়াকলাপ দ্বারা গঠিত হতে পারে। রঙের পরিবর্তে তালিকা রঙ করার জন্য অনুরূপ নির্মাণ ব্যবহার করা যেতে পারে। সমালোচনামূলক গ্রাফের গঠনযোগ্যতা কারণ, প্রতিটি-সমালোচনামূলক গ্রাফ (অর্থাৎ, প্রতিটি বিজোড় চক্র) একটি-গঠনযোগ্য গ্রাফ হিসাবে তৈরি করা যেতে পারে যাতে এর নির্মাণে গঠিত সমস্ত গ্রাফও-সমালোচনামূলক হয়। কারণ, এটি সত্য নয়ঃ হাজোসের অনুমানের পাল্টা উদাহরণ হিসাবে পাওয়া একটি গ্রাফ যে-বর্ণগত গ্রাফগুলির একটি উপবিভাগ রয়েছে, এটি এই সমস্যার পাল্টা উদাহরণ হিসাবেও কাজ করে। পরবর্তীকালে, সকলের জন্য-সমালোচনামূলক কিন্তু গঠনমূলক নয়-শুধুমাত্র-সমালোচনামূলক গ্রাফের মাধ্যমে পাওয়া যায়। কারণ, এরকম একটি উদাহরণ হ 'ল ডোডেকাহেড্রন গ্রাফ থেকে প্রাপ্ত গ্রাফটি প্রতিটি জোড়া অ্যান্টিপোডাল শীর্ষগুলির মধ্যে একটি নতুন প্রান্ত যোগ করে হাজোস সংখ্যা কারণ দুটি অ-সংলগ্ন শীর্ষগুলির একত্রীকরণ ফলস্বরূপ গ্রাফের শীর্ষগুলির সংখ্যা হ্রাস করে, হাজোস দ্বারা সংজ্ঞায়িত ক্রিয়াকলাপগুলি ব্যবহার করে প্রদত্ত গ্রাফের প্রতিনিধিত্ব করার জন্য প্রয়োজনীয় ক্রিয়াকলাপের সংখ্যা শীর্ষগুলির সংখ্যা অতিক্রম করতে পারে। আরও সুনির্দিষ্টভাবে, একটি-বর্ণগত গ্রাফের হাজোস সংখ্যাকে নির্মাণের জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক ধাপ হিসাবে সংজ্ঞায়িত করুন, যেখানে প্রতিটি ধাপ পূর্বে গঠিত দুটি গ্রাফকে একত্রিত করে, পূর্বে গঠিত গ্রাফের দুটি অ-সংলগ্ন শীর্ষকে একত্রিত করে বা পূর্বে গঠিত গ্রাফের সাথে একটি শীর্ষ বা প্রান্ত যুক্ত করে একটি নতুন গ্রাফ তৈরি করে। তারা দেখিয়েছেন যে, প্রান্ত সহ একটি-ভার্টেক্স গ্রাফের জন্য,। যদি প্রতিটি গ্রাফের একটি বহুপদী হাজোস সংখ্যা থাকে, তবে এর অর্থ হবে যে অনির্ধারিত বহুপদী সময়ে অ-বর্ণযোগ্যতা প্রমাণ করা সম্ভব, এবং তাই বোঝায় যে এনপি = সহ-এনপি, জটিলতা তত্ত্ববিদদের দ্বারা অসম্ভব বলে বিবেচিত একটি উপসংহার। যাইহোক, এটি জানা যায় না যে কীভাবে কিছু জটিলতা-তাত্ত্বিক অনুমান না করে হাজোস সংখ্যার উপর অ-বহুপদী নিম্ন সীমা প্রমাণ করা যায় এবং যদি এই ধরনের সীমা প্রমাণ করা যায় তবে এটি গাণিতিক যুক্তিতে নির্দিষ্ট ধরনের ফ্রেজ সিস্টেমে অ-বহুপদী সীমার অস্তিত্বকেও বোঝায়। একটি প্রদত্ত গ্রাফের জন্য একটি হাজোস নির্মাণের বর্ণনাকারী একটি অভিব্যক্তি গাছের ন্যূনতম আকার হাজোস সংখ্যার তুলনায় উল্লেখযোগ্যভাবে বড় হতে পারে, কারণ একটি সংক্ষিপ্ততম অভিব্যক্তি একই গ্রাফ একাধিকবার পুনরায় ব্যবহার করতে পারে, একটি অভিব্যক্তি গাছে অনুমোদিত অর্থনীতি নয়। 3-বর্ণের গ্রাফ রয়েছে যার জন্য এই ধরনের ক্ষুদ্রতম অভিব্যক্তি গাছের সূচকীয় আকার রয়েছে। অন্যান্য প্রয়োগগুলি হাজোস নির্মাণকে 4-সমালোচনামূলক পলিহেড্রাল গ্রাফের একটি অসীম সেট তৈরি করতে ব্যবহার করেছিল, যার প্রত্যেকটির শীর্ষগুলির দ্বিগুণেরও বেশি প্রান্ত রয়েছে। একইভাবে, অনেক 4-সমালোচনামূলক ত্রিভুজ-মুক্ত গ্রাফ তৈরি করতে গ্রটজশ গ্রাফ থেকে শুরু করে নির্মাণটি ব্যবহার করা হয়েছিল, যা তারা ঐতিহ্যবাহী ব্যাকট্র্যাকিং অ্যালগরিদম ব্যবহার করে রঙ করা কঠিন বলে দেখিয়েছিল। পলিহেড্রাল কম্বিনেটরিক্সে, স্থিতিশীল সেট পলিটোপের দিকগুলি তৈরি করতে হাজোস নির্মাণ ব্যবহার করা হয়। উল্লেখগুলি উল্লেখ করুন। । । । । যেমনটি উল্লেখ করা হয়েছে। । । । । । । । । গ্রাফ অপারেশন গ্রাফ কালারিং