Moser spindle
গ্রাফ তত্ত্বে, গণিতের একটি শাখা, মোজার স্পিন্ডল (মোজার্স স্পিন্ডল বা মোজার গ্রাফ নামেও পরিচিত) হল একটি অনির্দিষ্ট গ্রাফ, যা গণিতবিদ লিও মোজার এবং তাঁর ভাই উইলিয়ামের নামে নামকরণ করা হয়েছে, যার সাতটি শীর্ষ এবং এগারোটি প্রান্ত রয়েছে। এটি একটি একক দূরত্বের গ্রাফ যার জন্য যে কোনও গ্রাফের রঙে চারটি রঙের প্রয়োজন হয় এবং এর অস্তিত্ব প্রমাণ করতে ব্যবহার করা যেতে পারে যে সমতলের ক্রোমাটিক সংখ্যা কমপক্ষে চারটি। মোজার স্পিন্ডলকে গিওর্গি হাজোসের পরে হাজোস গ্রাফও বলা হয়েছে, কারণ এটি হাজোস নির্মাণের একটি উদাহরণ হিসাবে দেখা যেতে পারে। যাইহোক, "হাজোস গ্রাফ" নামটি একটি ভিন্ন গ্রাফের ক্ষেত্রেও প্রয়োগ করা হয়েছে, একটি ষড়ভুজের মধ্যে খোদাই করা ত্রিভুজ আকারে। একক দূরত্বের গ্রাফ হিসাবে, মোজার স্পিন্ডলটি 60 এবং 120 ডিগ্রি কোণ সহ দুটি রম্বির দ্বারা গঠিত হয়, যাতে রম্বির পার্শ্ব এবং ছোট তির্যকগুলি সমবাহু ত্রিভুজ গঠন করে। দুটি রম্বিকে সমতলে স্থাপন করা হয়, তাদের একটি তীব্র-কোণযুক্ত শীর্ষকে এমনভাবে ভাগ করে নেওয়া হয় যে বাকি দুটি তীব্র-কোণযুক্ত শীর্ষগুলি একে অপরের থেকে একক দূরত্বের মধ্যে থাকে। গ্রাফের এগারোটি প্রান্ত হল আটটি রম্বাস দিক, রম্বির দুটি ছোট তির্যক এবং তীব্র-কোণযুক্ত শীর্ষগুলির একক-দূরত্ব জুটির মধ্যে প্রান্ত। মোজার স্পিন্ডলটি গ্রাফ-তাত্ত্বিকভাবেও তৈরি করা যেতে পারে, জ্যামিতিক এম্বেডিংয়ের উল্লেখ ছাড়াই, চারটি শীর্ষে দুটি সম্পূর্ণ গ্রাফ দিয়ে শুরু হওয়া হাজোস নির্মাণ ব্যবহার করে। এই নির্মাণ প্রতিটি সম্পূর্ণ গ্রাফ থেকে একটি প্রান্ত সরিয়ে দেয়, সরানো প্রান্তের দুটি শেষ বিন্দুকে উভয় চক্রের দ্বারা ভাগ করা একটি একক শীর্ষে একত্রিত করে এবং সরানো প্রান্তের বাকি দুটি শেষ বিন্দুকে সংযুক্ত করে একটি নতুন প্রান্ত যোগ করে। মোজার স্পিন্ডল নির্মাণের আরেকটি উপায় হল ইউটিলিটি গ্রাফ K3,3 থেকে তৈরি গ্রাফের পরিপূরক গ্রাফ হিসাবে এর একটি প্রান্তকে উপবিভাগ করে। হ্যাডউইগার-নেলসন সমস্যার প্রয়োগ হ্যাডউইগার-নেলসন সমস্যা জিজ্ঞাসা করে যে ইউক্লিডীয় সমতলের বিন্দুগুলিকে এমনভাবে রঙ করার জন্য কতগুলি রঙের প্রয়োজন যাতে একে অপরের থেকে একক দূরত্বে প্রতিটি জোড়া বিন্দুকে বিভিন্ন রঙ দেওয়া হয়। অর্থাৎ, এটি অসীম গ্রাফের ক্রোমাটিক সংখ্যা জিজ্ঞাসা করে যার শীর্ষগুলি সমতলের সমস্ত বিন্দু এবং যার প্রান্তগুলি একক দূরত্বে সমস্ত জোড়া বিন্দু। মোজার স্পিন্ডলের যে কোনও গ্রাফ রঙে চারটি রঙের প্রয়োজন হয়ঃ যে দুটি রম্বির মধ্যে যেটি থেকে এটি গঠিত হয় তার যে কোনও তিন রঙে, রম্বির দুটি তীব্র-কোণযুক্ত শীর্ষে অবশ্যই একে অপরের মতো একই রঙ থাকবে। কিন্তু যদি দুটি রম্বির ভাগ করা শীর্ষের দুটি বিপরীত তীব্র-কোণযুক্ত শীর্ষের মতো একই রঙ থাকে, তবে এই দুটি শীর্ষের একে অপরের মতো একই রঙ থাকে, যা তাদের সংযুক্ত প্রান্তের ভিন্ন রঙের প্রান্তবিন্দু থাকার প্রয়োজনীয়তা লঙ্ঘন করে। এই দ্বন্দ্ব দেখায় যে তিনটি রঙ অসম্ভব, তাই কমপক্ষে চারটি রঙের প্রয়োজন। মোজার স্পিন্ডলকে রঙ দেওয়ার জন্য চারটি রঙই যথেষ্ট, উদাহরণস্বরূপ, এর অবক্ষয় তিনটি। মোজার স্পিন্ডলের জন্য চারটি রঙের প্রয়োজন তার একটি বিকল্প প্রমাণ হাজোস নির্মাণ থেকে পাওয়া যায়। যে দুটি সম্পূর্ণ গ্রাফ থেকে মোজার স্পিন্ডল গঠিত হয় তার জন্য চারটি রঙের প্রয়োজন হয় এবং হাজোস নির্মাণ এই বৈশিষ্ট্যটি সংরক্ষণ করে। আরও সরাসরি, মোজার স্পিন্ডলের প্রতিটি স্বাধীন সেটের সর্বাধিক দুটি শীর্ষ থাকে, তাই সাতটি শীর্ষকে আচ্ছাদন করতে কমপক্ষে চারটি স্বাধীন সেট লাগে। যেহেতু মোজার স্পিন্ডল সমতলের অসীম একক দূরত্বের গ্রাফের একটি উপগ্রাফ, তাই সমতলের গ্রাফের জন্য যে কোনও রঙে কমপক্ষে চারটি রঙের প্রয়োজন হয়। ডি ব্রুইন-এর্ডোস উপপাদ্য অনুসারে (পছন্দের স্বতঃসিদ্ধ সত্য বলে অনুমান সহ), সমতলের ক্রোমাটিক সংখ্যা তার যে কোনও সীমাবদ্ধ উপ-গ্রাফের বৃহত্তম ক্রোমাটিক সংখ্যার সমান; 2018 সালে 5-ক্রোমাটিক একক দূরত্ব গ্রাফের একটি পরিবার আবিষ্কার না হওয়া পর্যন্ত, অসীম একক দূরত্ব গ্রাফের কোনও উপ-গ্রাফ পাওয়া যায়নি যার জন্য মোজার স্পিন্ডলের চেয়ে বেশি সংখ্যক রঙের প্রয়োজন হয়। যাইহোক, সমতলের ক্রোমাটিক সংখ্যার জন্য সর্বোত্তম উপরের সীমা হল সাত, যা মোজার স্পিন্ডলের জন্য প্রয়োজনীয় রঙের সংখ্যার তুলনায় উল্লেখযোগ্যভাবে বেশি। অন্যান্য বৈশিষ্ট্য এবং প্রয়োগ মোজার স্পিন্ডল একটি সমতলীয় গ্রাফ, যার অর্থ এটি সমতলে ক্রসিং ছাড়াই আঁকা যেতে পারে। যাইহোক, সরলরেখার প্রান্ত সহ এমন একটি অঙ্কন তৈরি করা সম্ভব নয় যা একটি একক দূরত্ব অঙ্কন; অর্থাৎ, এটি একটি ম্যাচস্টিক গ্রাফ নয়। মোজার স্পিন্ডলটিও একটি ল্যামন গ্রাফ, যার অর্থ এটি সমতলে এম্বেড করার সময় একটি ন্যূনতম অনমনীয় সিস্টেম গঠন করে। প্ল্যানার ল্যামান গ্রাফ হিসাবে, এটি একটি তীক্ষ্ণ সিউডোট্রিয়াঙ্গুলেশনের গ্রাফ, যার অর্থ এটি সমতলে এমনভাবে এম্বেড করা যেতে পারে যে সীমাহীন মুখটি এম্বেডিংয়ের উত্তল হুল এবং প্রতিটি আবদ্ধ মুখ একটি সিউডোট্রিয়াঙ্গেল মাত্র তিনটি উত্তল শীর্ষ সহ। মোজার গ্রাফের পরিপূরক গ্রাফটি একটি ত্রিভুজ-মুক্ত গ্রাফ। সুতরাং, মোজার গ্রাফের একক দূরত্ব এম্বেডিংটি সমতলে সাতটি পয়েন্ট রাখার সমস্যাটি এমনভাবে সমাধান করতে ব্যবহার করা যেতে পারে যাতে প্রতিটি তিনগুণ পয়েন্টে একে অপরের থেকে একক দূরত্বে কমপক্ষে একটি জোড়া থাকে। মোজার স্পিন্ডলে কোনও প্রান্ত যুক্ত করার ফলে এমন একটি গ্রাফ তৈরি হয় যা সমতলে একক দূরত্বের গ্রাফ হিসাবে এম্বেড করা যায় না এবং মোজার স্পিন্ডল থেকে কোনও ছোট একক দূরত্বের গ্রাফের সমরূপতা বিদ্যমান নেই। মোজার স্পিন্ডলের এই দুটি বৈশিষ্ট্য একটি প্রদত্ত গ্রাফের দ্বি-মাত্রিক একক দূরত্বের উপস্থাপনা রয়েছে কিনা তা পরীক্ষার এনপি-কঠোরতা দেখানোর জন্য ব্যবহার করা হয়েছিল; প্রমাণটি 3এসএটি থেকে হ্রাস ব্যবহার করে যেখানে মোজার স্পিন্ডলকে হ্রাসের কেন্দ্রীয় সত্য-সেটিং গ্যাজেট হিসাবে ব্যবহার করা হয়। মোজার স্পিন্ডল ইউক্লিডীয় রামসে তত্ত্বের একটি ফলাফল প্রমাণ করতেও ব্যবহার করা যেতে পারেঃ যদি টি সমতলে কোনও ত্রিভুজ হয় এবং সমতলের বিন্দুগুলি দুই রঙের কালো এবং সাদা হয়, তবে হয় টি-এর একটি কালো অনুবাদ বা একে অপরের থেকে একক দূরত্বে এক জোড়া সাদা বিন্দু থাকে। যদি এম + টি-র কোনও সাদা একক-দূরত্ব জোড়া না থাকে, তবে এম + টি-তে মোজার স্পিন্ডলের তিনটি অনুলিপির প্রত্যেকটিতে সর্বাধিক দুটি করে সাদা বিন্দু থাকতে হবে, কারণ প্রতিটি অনুলিপির সাদা বিন্দুগুলিকে অবশ্যই একটি স্বাধীন সেট গঠন করতে হবে এবং মোজার স্পিন্ডলের বৃহত্তম স্বাধীন সেটটির আকার দুই হতে হবে। অতএব, মোজার স্পিন্ডলের সাতটি শীর্ষের মধ্যে সর্বাধিক ছয়টি রয়েছে যার এম + টি-তে একটি সাদা অনুলিপি রয়েছে, তাই সাতটি শীর্ষের মধ্যে একটি অবশ্যই থাকতে হবে যার সমস্ত অনুলিপি কালো। কিন্তু তারপর এই শীর্ষের তিনটি অনুলিপি টি-এর অনুবাদ গঠন করে। আরও দেখুন গোলম্ব গ্রাফ রেফারেন্স বাহ্যিক লিঙ্ক স্বতন্ত্র গ্রাফ প্ল্যানার গ্রাফ