Flag algebra
ফ্ল্যাগ অ্যালজেব্রা গ্রাফ তত্ত্বের ক্ষেত্রে একটি গুরুত্বপূর্ণ গণনামূলক সরঞ্জাম যার সমরূপতা ঘনত্ব এবং সম্পর্কিত বিষয়গুলিতে বিস্তৃত প্রয়োগ রয়েছে। মোটামুটিভাবে, তারা সমরূপতার ঘনত্ব যোগ এবং গুণ করার ধারণাকে আনুষ্ঠানিক করে তোলে এবং কম্পিউটারের সাথে গ্রাফ সমরূপতার বৈষম্যগুলি অর্ধ-সীমাবদ্ধ প্রোগ্রামিং সমস্যায় হ্রাস করে সমাধান করার জন্য একটি কাঠামো স্থাপন করে। মূলত 2007 সালের একটি গবেষণাপত্রে আলেকজান্ডার রাজবোরভ দ্বারা প্রবর্তিত, পদ্ধতিটি তখন থেকে অসংখ্য কঠিন, পূর্বে অমীমাংসিত গ্রাফ তাত্ত্বিক প্রশ্নের সমাধান করতে এসেছে। এর মধ্যে রয়েছে সম্ভাব্য প্রান্ত ঘনত্বের অঞ্চল, ত্রিভুজ ঘনত্ব জোড়া এবং ত্রিভুজ মুক্ত আলেখ্যে সর্বাধিক সংখ্যক পেন্টাগন সম্পর্কিত প্রশ্ন। অনুপ্রেরণা ফ্ল্যাগ অ্যালজেব্রা তত্ত্বের অনুপ্রেরণার কৃতিত্ব জন অ্যাড্রিয়ান বন্ডী এবং ক্যাকেটা-হ্যাগকভিস্ট অনুমানের উপর তাঁর কাজকে দেওয়া হয়, যেখানে তিনি মান্টেলের উপপাদ্যের স্বাদযুক্ত প্রমাণের গ্রাফ সমরূপতার মাধ্যমে তাঁর প্রধান ধারণাগুলি চিত্রিত করেছিলেন। এই প্রমাণটি দ্বৈত গণনার মাধ্যমে ম্যান্টেলের ঐতিহ্যবাহী প্রমাণের একটি অভিযোজন, গ্রাফ সমরূপতার ঘনত্বের পরিপ্রেক্ষিতে বাক্যাংশ ব্যতীত এবং দেখায় যে কেবল ঘনত্বের সম্পর্কের সাথে কতটা তথ্য এনকোড করা যেতে পারে। উপপাদ্য (ম্যান্টেল): একটি ত্রিভুজ-মুক্ত গ্রাফের প্রান্তের ঘনত্ব সর্বাধিক। অন্য কথায়, যেহেতু গ্রাফটি ত্রিভুজ-মুক্ত, 3টি শীর্ষের মধ্যে, তারা হয় একটি স্বাধীন সেট, একটি একক প্ররোচিত প্রান্ত বা দৈর্ঘ্য 2-এর পথ তৈরি করতে পারে। একটি সাবগ্রাফের প্ররোচিত ঘনত্ব হিসাবে চিহ্নিত করে, ডাবল কাউন্টিং দেয়ঃ স্বজ্ঞাতভাবে, যেহেতু a শুধু দুটি s একসাথে সংযুক্ত থাকে, এবং 3 টি পয়েন্টের সেটের মধ্যে সাধারণ শীর্ষকে লেবেল করার 3 টি উপায় রয়েছে। প্রকৃতপক্ষে, প্ররোচিত s-এর সংখ্যা দ্বিগুণ গণনা করে এটি কঠোরভাবে প্রমাণ করা যেতে পারে। এর শীর্ষগুলির সংখ্যা নির্দেশ করে, আমাদের আছেঃ দৈর্ঘ্য 2-এর পথটি কোথায় তার মধ্য শীর্ষটি লেবেলযুক্ত, এবং লেবেলযুক্ত শীর্ষটি যে সীমাবদ্ধতার সাপেক্ষে s-এর ঘনত্বকে উপস্থাপন করে, এবং এটি একটি যথাযথ প্ররোচিত উপগ্রাফ হিসাবে গণনা করা হয় যখন এর লেবেলযুক্ত শীর্ষটি এর সাথে মিলে যায়। এখন, লক্ষ্য করুন যে যেহেতু দুটি এস বেছে নেওয়ার সম্ভাবনা যেখানে লেবেলবিহীন শীর্ষগুলি মিলে যায় তা ছোট (কঠোর হতে, একটি সীমা হিসাবে নেওয়া উচিত, তাই বড় এবং বড় গ্রাফের ক্রমের উপর একটি সীমা ফাংশন হিসাবে কাজ করে। এই ধারণাটি ফ্ল্যাগ অ্যালজেব্রার প্রকৃত সংজ্ঞার জন্য গুরুত্বপূর্ণ হবে।) শেষ করার জন্য, কচি-শোয়ার্জ বৈষম্য প্রয়োগ করে এটিকে আমাদের মূল সম্পর্কের মধ্যে ফিরিয়ে আনার জন্য যা অনুমান করা হয়েছিল তা স্বজ্ঞাতভাবে প্রমাণ করে। পরিশেষে, লক্ষ্য করুন যে এই প্রমাণ থেকে যে গুরুত্বপূর্ণ ধারণাগুলি ফ্ল্যাগ অ্যালজেব্রা তত্ত্বের ক্ষেত্রে সাধারণীকরণ করা হবে সেগুলি হল প্রতিস্থাপন, যেমন লেবেলযুক্ত গ্রাফ ঘনত্বের ব্যবহার, ঘনত্বের শুধুমাত্র "সীমা কেস" বিবেচনা করা এবং অর্থপূর্ণ ফলাফল পাওয়ার জন্য শেষে কাউচি প্রয়োগ করা। সংজ্ঞা নিষিদ্ধ উপ-গ্রাফের একটি সংগ্রহ ঠিক করুন এবং-মুক্ত গ্রাফের গ্রাফের সেট বিবেচনা করুন। এখন, একটি ধরনের আকারকে লেবেলযুক্ত শীর্ষ সহ একটি গ্রাফ হিসাবে সংজ্ঞায়িত করুন। আকারের ধরন 0 সাধারণত হিসাবে চিহ্নিত করা হয়। প্রথমত, আমরা একটি-পতাকা সংজ্ঞায়িত করি, একটি আংশিক লেবেলযুক্ত গ্রাফ যা ফ্ল্যাগ অ্যালজেব্রা তত্ত্বের জন্য গুরুত্বপূর্ণ হবেঃ সংজ্ঞাঃ একটি-পতাকা এমন একটি জোড়া যেখানে একটি অন্তর্নিহিত, লেবেলবিহীন,-মুক্ত গ্রাফ, যখন শীর্ষে এম্বেড করা একটি লেবেলযুক্ত গ্রাফকে সংজ্ঞায়িত করে। - পতাকার সেটটি এবং-পতাকার আকারের সেটটি নির্দেশ করুন। উদাহরণস্বরূপ, উপরের ম্যান্টেলের উপপাদ্যের প্রমাণ থেকে একটি-পতাকা রয়েছে যেখানে একটি একক শীর্ষের সাথে সম্পর্কিত 1 আকারের একটি প্রকার রয়েছে। - পতাকা সন্তোষজনক হওয়ার জন্য, আমরা অন্তর্নিহিত গ্রাফের উপর-পতাকার ঘনত্বকে নিম্নলিখিত উপায়ে সংজ্ঞায়িত করতে পারিঃ সংজ্ঞাঃ-পতাকার ঘনত্বকে এমনভাবে সংজ্ঞায়িত করা হয় যাতে তারা এলোমেলোভাবে সফলভাবে এম্বেড করা যায় যাতে তারা ছেদ না করে এবং সবগুলিই ঠিক একইভাবে লেবেলযুক্ত থাকে। আরও সুনির্দিষ্টভাবে বলতে গেলে, এলোমেলোভাবে পেয়ারওয়াইজ ডিজজয়েন্ট বেছে নিন এবং-ফ্ল্যাগটি সকলের জন্য আইসোমরফিক হওয়ার সম্ভাবনা হিসাবে সংজ্ঞায়িত করুন। মনে রাখবেন যে,-পতাকা কোথায় রয়েছে তাতে এম্বেড করার সময়, এটি প্রথমে আকারের একটি-পতাকায় এম্বেড করে এবং তারপরে এম্বেড করে করা যেতে পারে, যা সূত্রটি দেয়ঃ এটিকে-পতাকার সেটগুলিতে প্রসারিত করলে শৃঙ্খল নিয়মটি পাওয়া যায়ঃ উপপাদ্য (শৃঙ্খল নিয়ম): যদি-পতাকা হয়, তবে তা এমন প্রাকৃতিক যা মাপের পতাকার সঙ্গে মানানসই, এবং মাপের একটি পতাকার সঙ্গে মানানসই। মনে রাখবেন যে ম্যান্টেলের পূর্ববর্তী প্রমাণটিতে ফর্মের পদগুলির রৈখিক সংমিশ্রণ জড়িত ছিল। প্রাসঙ্গিক ধারণাগুলি অনন্তের দিকে ঝোঁক দেওয়ার ক্ষেত্রে কিছুটা অস্পষ্ট ছিল, তবে স্পষ্টতই এমন একটি ক্রম রয়েছে যা সকলের জন্য কিছুতে একত্রিত হয়, যেখানে একটি সীমা কার্যকরী বলা হয়। সুতরাং, সমস্ত রেফারেন্স প্রকৃতপক্ষে কার্যকরী সীমা বোঝায়। এখন, গ্রাফ সমরূপতা অসমতা বিভিন্ন s-এর সাথে রৈখিক সংমিশ্রণ হিসাবে লেখা যেতে পারে, তবে এগুলিকে একক শব্দ হিসাবে প্রকাশ করা সুবিধাজনক হবে। এটি-পতাকার আনুষ্ঠানিক রৈখিক সংমিশ্রণের সেটকে সংজ্ঞায়িত করতে অনুপ্রাণিত করে এবং এখন এটিকে একটি রৈখিক ফাংশনে প্রসারিত করা যেতে পারে। যাইহোক, শুধুমাত্র সীমিত কার্যকারিতা অনুসন্ধান করার সময় সম্পূর্ণ স্থান ব্যবহার করা অপচয়, কারণ নির্দিষ্ট পতাকার ঘনত্বের মধ্যে অ-তুচ্ছ সম্পর্ক রয়েছে। বিশেষত, চেইন রুল দেখায় যে এটি সর্বদা সত্য। কার্নেলের এই সমস্ত উপাদান নিয়ে কাজ করার পরিবর্তে, উপরের ফর্মের অভিব্যক্তিগুলির সেট (অর্থাৎ। যেগুলি চেইন রুল থেকে একটি একক পতাকা সহ প্রাপ্ত হয়েছে) এবং আমাদের চূড়ান্ত বিশ্লেষণে সেগুলি উদ্ধৃত করে। এই ধারণাগুলি একত্রিত হয়ে একটি ফ্ল্যাগ বীজগণিতের সংজ্ঞা গঠন করেঃ সংজ্ঞা (ফ্ল্যাগ অ্যালজেব্রা): একটি ফ্ল্যাগ বীজগণিত দ্বি-রৈখিক অপারেটর এবং যে কোনও প্রাকৃতিক দ্বারা সজ্জিত-ফ্ল্যাগগুলির রৈখিক সংমিশ্রণের স্থানের উপর সংজ্ঞায়িত করা হয় যা আকারের-ফ্ল্যাগটিতে ফিট করে, অপারেটরকে রৈখিকভাবে প্রসারিত করে। এটি পরীক্ষা করা বাকি থাকে যে একটি জুটির জন্য পছন্দটি গুরুত্বপূর্ণ নয় যদি এটি যথেষ্ট বড় হয় (এটি চেইন রুল দিয়ে প্রমাণিত হতে পারে) পাশাপাশি যদি তা হয়, যার অর্থ অপারেটর ভাগফলকে সম্মান করে এবং এইভাবে পছন্দসই স্থানে একটি সু-সংজ্ঞায়িত বীজগণিত গঠন করে। অপারেটরের জন্য এই সংজ্ঞার একটি গুরুত্বপূর্ণ ফলাফল হল যে সীমা কার্যকারিতার উপর গুণকে সম্মান করা হয়। বিশেষত, কার্যকরী একটি সীমার জন্য, পরিচয়টি সত্য। উদাহরণস্বরূপ, এটি দেখানো হয়েছিল যে ম্যান্টেলের জন্য আমাদের প্রমাণ এবং এই ফলাফলটি এই বিবৃতির একটি উপসংহার মাত্র। আরও সাধারণভাবে, গুণিতক মানে হল যে সমস্ত সীমা কার্যকারিতা এবং এর মধ্যে বীজগণিত সমরূপতা। নিম্নমুখী অপারেটর উপরের সংজ্ঞাটি-পতাকা নিয়ে কাজ করার জন্য একটি কাঠামো প্রদান করে, যা আংশিকভাবে লেবেলযুক্ত গ্রাফ। যাইহোক, বেশিরভাগ সময়, লেবেলবিহীন গ্রাফ বা-পতাকা সবচেয়ে বেশি আগ্রহের বিষয়। প্রথম থেকে পরেরটিতে যেতে, নিম্নমুখী অপারেটরকে সংজ্ঞায়িত করুন। নিম্নমুখী অপারেটরকে সবচেয়ে স্বাভাবিক উপায়ে সংজ্ঞায়িত করা হয়ঃ একটি-পতাকা দেওয়া হলে, নির্ধারিত লেবেলগুলি ভুলে যাওয়ার ফলে-পতাকা হতে দিন। এখন,-পতাকা এবং লেবেলবিহীন গ্রাফের মধ্যে একটি প্রাকৃতিক ম্যাপিং সংজ্ঞায়িত করার জন্য, র্যান্ডম-এ নেওয়া একটি ইনজেক্টিভ মানচিত্রে চিত্রের সমরূপতা এবং সংজ্ঞায়িত হওয়ার সম্ভাবনাটি ধরা যাক। রৈখিকভাবে প্রসারিত করলে একটি বৈধ রৈখিক মানচিত্র পাওয়া যায় যা লেবেলবিহীন পতাকার সংমিশ্রণে-পতাকার সংমিশ্রণ পাঠায়। সবচেয়ে গুরুত্বপূর্ণ ফলাফল হল এর গড় বৈশিষ্ট্য। বিশেষত, একটি-ফ্ল্যাগ এবং লেবেলবিহীন গ্রাফ ঠিক করুন, তারপরে এলোমেলোভাবে একটি এম্বেডিং বেছে নেওয়া এলোমেলো পরিবর্তনশীলকে সংজ্ঞায়িত করে। এটি দেখানো যেতে পারে যে ফ্ল্যাগ অ্যালজেব্রা সহ অপ্টিমাইজেশন সমস্ত রৈখিক কার্যকারিতা, বীজগণিত সমরূপতা। উপরন্তু, সংজ্ঞা অনুসারে, যে কোনও-পতাকার জন্য যেহেতু একটি ঘনত্ব সীমা প্রতিনিধিত্ব করে। সুতরাং, বলুন যে একটি সমরূপতা ধনাত্মক হয় যদি এবং শুধুমাত্র যদি, এবং ধনাত্মক সমরূপতার সেট হতে দিন। কেউ দেখাতে পারে যে সীমা কার্যকারিতার সেটটি ঠিক ইতিবাচক সমরূপতার সেট, তাই সেটটির পরবর্তী সংজ্ঞাটি বোঝার জন্য এটি যথেষ্ট। একটি রৈখিক সংমিশ্রণের জন্য একটি বৈধ গ্রাফ সমরূপতা বৈষম্য অর্জনের জন্য, এটি সমস্ত সম্ভাব্য রৈখিক কার্যকারিতার উপর অ-নেতিবাচক হতে হবে, যা তখন বোঝাবে যে এটি সমস্ত গ্রাফের জন্য সত্য। এই বিষয়টি মাথায় রেখে, শব্দার্থিক শঙ্কু প্রকারটি সংজ্ঞায়িত করুন, এমন একটি সেট যা আবারও সর্বাধিক আগ্রহের বিষয়, যা লেবেলবিহীন গ্রাফের ক্ষেত্রে মিলে যায়। যাইহোক, নিম্নমুখী অপারেটরের ম্যাপিংয়ের বৈশিষ্ট্য রয়েছে এবং এটি দেখানো যেতে পারে যে নিচের চিত্রটি এর একটি উপসেট, যার অর্থ শব্দার্থিক শঙ্কু প্রকারের যে কোনও ফলাফল সহজেই লেবেলবিহীন গ্রাফগুলিতেও সাধারণীকরণ করে। কেবল সরলভাবে উপাদানগুলিকে পরিচালনা করে, শব্দার্থিক শঙ্কুটির অসংখ্য উপাদান তৈরি করা যেতে পারে। উদাহরণস্বরূপ, যেহেতু এর উপাদানগুলি-পতাকার জন্য অ-ঋণাত্মক, তাই এর উপাদানগুলির যে কোনও শঙ্কু সংমিশ্রণ এর একটি উপাদান প্রদান করবে। সম্ভবত আরও অ-তুচ্ছভাবে, এর উপাদানগুলির বর্গগুলির যে কোনও শঙ্কু সংমিশ্রণও শব্দার্থিক শঙ্কু একটি উপাদান উৎপন্ন করবে। যদিও কেউ পতাকার বর্গ খুঁজে পেতে পারে যা ম্যানুয়ালি অ-তুচ্ছ ফলাফলের সমষ্টি, প্রক্রিয়াটি স্বয়ংক্রিয় করা প্রায়শই সহজ। বিশেষত, বহুপদগুলির জন্য ফ্ল্যাগ অ্যালজেব্রাগুলির জন্য সমষ্টি-বর্গ অপ্টিমাইজেশনে ধারণাগুলি মানিয়ে নেওয়া সম্ভব। একটি ভেক্টরের ডিগ্রীকে বৃহত্তম ফ্ল্যাগ হিসাবে সংজ্ঞায়িত করুন যার সম্প্রসারণে অ-শূন্য সহগ রয়েছে এবং সমস্ত পছন্দের উপর একটি ভেক্টরের ন্যূনতম ডিগ্রি হতে দিন। এছাড়াও, সকলের জন্য নিজের কাছে পাঠানোর ক্যানোনিকাল এম্বেডিং হিসাবে সংজ্ঞায়িত করুন। এই সংজ্ঞাগুলি নিম্নলিখিত ফ্ল্যাগ-অ্যালজেব্রা অ্যানালগের জন্ম দেয়ঃ উপপাদ্যঃ প্রদত্ত, তবে কিছু ক্ষেত্রে বিদ্যমান থাকে যদি এবং শুধুমাত্র যদি এমন একটি ধনাত্মক সেমিডিফাইনাইট ম্যাট্রিক্স থাকে। এই উপপাদ্যের সাহায্যে, গ্রাফ সমরূপতা সমস্যাগুলিকে এখন সেমিডিফাইনাইট প্রোগ্রামিং-এ শিথিল করা যেতে পারে যা কম্পিউটারের মাধ্যমে সমাধান করা যেতে পারে। উদাহরণস্বরূপ, ম্যান্টেলের উপপাদ্যকে সবচেয়ে ছোট উপপাদ্য খুঁজে বের করা হিসাবে পুনর্ব্যবহার করা যেতে পারে। যেমনটি খুব কমই বোঝা যায়, এই আকারে প্রশ্নের অগ্রগতি করা কঠিন, তবে মনে রাখবেন যে-পতাকা এবং ভেক্টরের বর্গগুলির শঙ্কু সংমিশ্রণ রয়েছে, তাই পরিবর্তে একটি আধা-সীমাবদ্ধ শিথিলতা গ্রহণ করুন। বিশেষত, সীমাবদ্ধতার অধীনে হ্রাস করুন যে-পতাকার একটি শঙ্কু সংমিশ্রণ কোথায় এবং ধনাত্মক আধা-নির্দিষ্ট। এই নতুন অপ্টিমাইজেশান সমস্যাটিকে একটি সেমিডিফাইনাইট-প্রোগ্রামিং সমস্যায় রূপান্তরিত করা যেতে পারে যা তারপর স্ট্যান্ডার্ড অ্যালগরিদমের সাহায্যে সমাধানযোগ্য। সাধারণীকরণ ফ্ল্যাগ অ্যালজেব্রার পদ্ধতি সহজেই অসংখ্য গ্রাফের মতো গঠনে সাধারণীকরণ করে। যেমনটি রাজবোরভ তাঁর মূল গবেষণাপত্রে লিখেছেন, পতাকার পরিবর্তে সীমাবদ্ধ মডেল তত্ত্ব দিয়ে বর্ণনা করা যেতে পারে। গ্রাফের পরিবর্তে, শুধুমাত্র প্রেডিকেট চিহ্ন সহ একটি সীমাবদ্ধ সম্পর্কিত স্বাক্ষরের সমতা সহ কিছু ননডিজেনারেট ইউনিভার্সাল ফার্স্ট-অর্ডার তত্ত্বের মডেল ব্যবহার করা যেতে পারে। একটি মডেল, যা একটি গ্রাফ সম্পর্কে আমাদের আগের ধারণাকে প্রতিস্থাপন করে, তার স্থল সেট থাকে, যার উপাদানগুলিকে শীর্ষ বলা হয়। এখন, সাব-মডেল এবং মডেল এম্বেডিংকে সাবগ্রাফ এবং গ্রাফ এম্বেডিংয়ের অনুরূপভাবে সংজ্ঞায়িত করা, উপরের সমস্ত সংজ্ঞা এবং উপপাদ্য প্রায় সরাসরি মডেল তত্ত্বের ভাষায় অনুবাদ করা যেতে পারে। ফ্ল্যাগ অ্যালজেব্রার তত্ত্বটি ভালভাবে সাধারণীকরণের অর্থ হল যে এটি কেবল সহজ গ্রাফের সমস্যা সমাধানের জন্যই ব্যবহার করা যায় না, তবে নির্দেশিত গ্রাফ এবং হাইপারগ্রাফগুলির মধ্যে সীমাবদ্ধ নয় এমন অনুরূপ গঠনও ব্যবহার করা যেতে পারে। তথ্যসূত্র গ্রাফ তত্ত্ব