Trémaux tree
গ্রাফ তত্ত্বে, একটি অনির্দিষ্ট গ্রাফের ট্রেমাক্স গাছ হল এক ধরনের বিস্তৃত গাছ, যা গভীরতা-প্রথম অনুসন্ধান গাছগুলিকে সাধারণীকরণ করে। এগুলি সেই বৈশিষ্ট্য দ্বারা সংজ্ঞায়িত করা হয় যা গাছের প্রতিটি প্রান্ত একটি পূর্বপুরুষ-বংশোদ্ভূত জুটিকে সংযুক্ত করে। ট্রেমাক্স গাছগুলির নামকরণ করা হয়েছে 19 শতকের ফরাসি লেখক চার্লস পিয়ের ট্রেমাক্সের নামে, যিনি ম্যাজ সমাধানের কৌশল হিসাবে গভীর-প্রথম অনুসন্ধানের একটি রূপ ব্যবহার করেছিলেন। বিশেষত অসীম গ্রাফের প্রেক্ষাপটে এগুলিকে সাধারণ বিস্তৃত গাছও বলা হয়। সমস্ত গভীর-প্রথম অনুসন্ধান গাছ এবং সমস্ত হ্যামিল্টনিয়ান পথ হল ট্রেমাক্স গাছ। সীমাবদ্ধ গ্রাফগুলিতে, প্রতিটি ট্রেমাক্স গাছ একটি গভীরতা-প্রথম অনুসন্ধান গাছ, তবে যদিও গভীরতা-প্রথম অনুসন্ধান নিজেই সহজাতভাবে ক্রমিক, ট্রেমাক্স গাছগুলি জটিলতা শ্রেণীর আরএনসি-তে একটি এলোমেলো সমান্তরাল অ্যালগরিদম দ্বারা তৈরি করা যেতে পারে। এগুলি একটি গ্রাফের বৃক্ষ-গভীরতা সংজ্ঞায়িত করতে এবং একটি গ্রাফ একটি সমতলীয় গ্রাফ কিনা তা পরীক্ষার জন্য বাম-ডান সমতলীয় পরীক্ষার অংশ হিসাবে ব্যবহার করা যেতে পারে। গ্রাফের মনাডিক দ্বিতীয়-ক্রম যুক্তিতে ট্রেমাক্স গাছের একটি বৈশিষ্ট্যায়ন করসেলের উপপাদ্য ব্যবহার করে সীমাবদ্ধ ত্রি-প্রস্থের গ্রাফের জন্য অভিযোজন জড়িত গ্রাফ বৈশিষ্ট্যগুলিকে দক্ষতার সাথে সনাক্ত করার অনুমতি দেয়। প্রতিটি অসীম সংযুক্ত গ্রাফের একটি ট্রামাক্স গাছ থাকে না, এবং প্রতিটি অসীম ট্রামাক্স গাছ একটি গভীরতা-প্রথম অনুসন্ধান গাছ নয়। যে গ্রাফগুলিতে ট্রেমাক্স গাছ রয়েছে সেগুলি নিষিদ্ধ অপ্রাপ্তবয়স্কদের দ্বারা চিহ্নিত করা যেতে পারে। একটি অসীম ট্রেমাক্স গাছের অবশ্যই গ্রাফের প্রতিটি প্রান্তের জন্য ঠিক একটি অসীম পথ থাকতে হবে এবং একটি ট্রেমাক্স গাছের অস্তিত্ব সেই গ্রাফগুলিকে চিহ্নিত করে যার প্রতিটি প্রান্তের জন্য অনন্ততায় একটি বিন্দু যোগ করে গঠিত টপোলজিকাল সম্পূর্ণতা মেট্রিক স্পেস। সংজ্ঞা এবং উদাহরণ একটি ট্রেমাক্স গাছ, একটি গ্রাফের জন্য, একটি বিস্তৃত গাছ যার বৈশিষ্ট্য হল, প্রতিটি প্রান্তের জন্য, দুটি শেষ বিন্দুর মধ্যে একটি এবং অন্যটির পূর্বপুরুষ। একটি বিস্তৃত গাছ হওয়ার জন্য, এটি শুধুমাত্র এর প্রান্ত ব্যবহার করতে হবে, এবং প্রতিটি শীর্ষকে অন্তর্ভুক্ত করতে হবে, প্রতিটি জোড়া শীর্ষের মধ্যে একটি অনন্য সীমাবদ্ধ পথ সহ। উপরন্তু, এই গাছের পূর্বপুরুষ-বংশোদ্ভূত সম্পর্ককে সংজ্ঞায়িত করতে, এর একটি শীর্ষকে অবশ্যই এর মূল হিসাবে চিহ্নিত করতে হবে। যদি একটি সীমাবদ্ধ গ্রাফের একটি হ্যামিল্টনিয়ান পথ থাকে, তবে তার দুটি শেষ বিন্দুর একটিতে সেই পথটি শিকড় দিয়ে একটি ট্রেমাক্স গাছ তৈরি করে। এই ধরনের পথের জন্য, প্রতিটি জোড়া শীর্ষ একটি পূর্বপুরুষ-বংশোদ্ভূত জোড়া। নীচের গ্রাফটিতে দেখানো হয়েছে, 1-3,2-3 এবং 3-4 প্রান্তযুক্ত গাছটি একটি ট্রেমাক্স গাছ যখন এটি শীর্ষ 1 বা শীর্ষ 2-এ শিকড়যুক্ত থাকেঃ গ্রাফের প্রতিটি প্রান্ত 1-2 প্রান্ত ব্যতীত গাছের অন্তর্গত, যা (মূলের এই পছন্দগুলির জন্য) একটি পূর্বপুরুষ-বংশোদ্ভূত জুটিকে সংযুক্ত করে। যাইহোক, শীর্ষ 3 বা শীর্ষ 4-এ একই গাছের শিকড় একটি শিকড়যুক্ত গাছ তৈরি করে যা ট্রেমাক্স গাছ নয়, কারণ এই মূল 1 এবং 2 আর একে অপরের পূর্বপুরুষ এবং বংশধর নয়। সসীম আলেখ্যে অস্তিত্ব প্রতিটি সসীম সংযুক্ত অনির্দিষ্ট আলেখ্যে কমপক্ষে একটি ট্রেমাক্স গাছ থাকে। গভীর-প্রথম অনুসন্ধান করে এবং প্রতিটি শীর্ষকে (অনুসন্ধানের প্রারম্ভিক শীর্ষ ব্যতীত) যে পূর্ববর্তী শীর্ষ থেকে এটি আবিষ্কৃত হয়েছিল তার সাথে সংযুক্ত করে এই জাতীয় গাছ তৈরি করা যেতে পারে। এইভাবে নির্মিত গাছটি ডেপথ-ফার্স্ট সার্চ ট্রি নামে পরিচিত। যদি গ্রাফের একটি স্বেচ্ছাচারী প্রান্ত হয়, এবং অনুসন্ধানের মাধ্যমে পৌঁছানো দুটি শীর্ষের মধ্যে পূর্ববর্তী হয়, তবে অবশ্যই গভীরতা-প্রথম অনুসন্ধান গাছ থেকে অবতরণকারী উপ-গাছের অন্তর্গত হতে হবে, কারণ অনুসন্ধানটি অবশ্যই এই উপ-গাছটি অন্বেষণ করার সময় আবিষ্কার করবে, হয় উপ-গাছের অন্য একটি শীর্ষ থেকে বা তা ব্যর্থ হলে সরাসরি থেকে। প্রতিটি সসীম ট্রেমাক্স গাছ একটি গভীরতা-প্রথম অনুসন্ধান গাছ হিসাবে তৈরি করা যেতে পারেঃ যদি একটি সসীম গ্রাফের একটি ট্রেমাক্স গাছ হয়, এবং একটি গভীরতা-প্রথম অনুসন্ধান অন্য কোনও শীর্ষগুলি অন্বেষণ করার আগে প্রতিটি শীর্ষের শিশুদের অন্বেষণ করে, তবে এটি অবশ্যই তার গভীরতা-প্রথম অনুসন্ধান গাছ হিসাবে তৈরি করবে। সমান্তরাল নির্মাণ ট্রামাক্স গাছটি খুঁজে বের করা পি-সম্পূর্ণ যা একটি ক্রমিক গভীরতা-প্রথম অনুসন্ধান অ্যালগরিদম দ্বারা পাওয়া যাবে, যেখানে প্রতিটি শীর্ষের প্রতিবেশীদের তাদের পরিচয় অনুসারে অনুসন্ধান করা হয়। তবুও, একটি এলোমেলো সমান্তরাল অ্যালগরিদম দ্বারা একটি ভিন্ন ট্রেমাক্স গাছ খুঁজে পাওয়া সম্ভব, যা দেখায় যে ট্রেমাক্স গাছের নির্মাণ জটিলতা শ্রেণীর আরএনসি-র অন্তর্গত। 0-1 ওজনের গ্রাফে ন্যূনতম ওজনের নিখুঁত মিল খুঁজে বের করার জন্য অ্যালগরিদমটি আরেকটি এলোমেলো সমান্তরাল অ্যালগরিদমের উপর ভিত্তি করে তৈরি। 1997 সাল পর্যন্ত, জটিলতা শ্রেণী এন. সি-তে একটি নির্ধারক সমান্তরাল অ্যালগরিদম দ্বারা ট্রেমাক্স গাছ নির্মাণ করা যেতে পারে কিনা তা অজানা ছিল। যদি এন. সি-তে মিল পাওয়া যায়, তাহলে ট্রেমাক্স গাছও পাওয়া যেতে পারে। যৌক্তিক অভিব্যক্তি এই বৈশিষ্ট্যটি প্রকাশ করা সম্ভব যে মূল শীর্ষের পছন্দের সাথে প্রান্তের একটি সেট একটি ট্রেমাক্স ট্রি গঠন করে, গ্রাফের মনাডিক দ্বিতীয়-ক্রম যুক্তিতে এবং আরও নির্দিষ্টভাবে এমএসও 2 নামক এই যুক্তির আকারে, যা শীর্ষ এবং প্রান্ত সেট উভয়ের উপর পরিমাণ নির্ধারণের অনুমতি দেয়। এই বৈশিষ্ট্যটি নিম্নলিখিত বৈশিষ্ট্যগুলির সংমিশ্রণ হিসাবে প্রকাশ করা যেতে পারেঃ গ্রাফটি প্রান্ত দ্বারা সংযুক্ত। এটিকে যৌক্তিকভাবে এই বিবৃতি হিসাবে প্রকাশ করা যেতে পারে যে, গ্রাফের শীর্ষগুলির প্রতিটি অ-খালি সঠিক উপসেটের জন্য, প্রদত্ত উপসেটে ঠিক একটি শেষ বিন্দু সহ একটি প্রান্ত বিদ্যমান। এটি অ্যাসাইক্লিক। এটিকে যৌক্তিকভাবে এই বিবৃতি হিসাবে প্রকাশ করা যেতে পারে যে এমন কোনও খালি উপসেট নেই যার জন্য প্রতিটি শীর্ষ শূন্য বা দুটি প্রান্তে আপতিত হয়। প্রতিটি প্রান্ত যা পূর্বপুরুষ-বংশোদ্ভূত জোড়াকে সংযুক্ত করে না। এটি সত্য যখন উভয় শেষ বিন্দু একটি পথের অন্তর্গত। এটি যুক্তিসঙ্গতভাবে এই বিবৃতি হিসাবে প্রকাশ করা যেতে পারে যে, সমস্ত প্রান্তের জন্য, এমন একটি উপসেট বিদ্যমান যে ঠিক দুটি শীর্ষ, তাদের মধ্যে একটি, এর একক প্রান্তে আপতিত হয় এবং এর উভয় প্রান্তবিন্দু কমপক্ষে এক প্রান্তে আপতিত হয়। একবার একটি ট্রেমাক্স গাছকে এইভাবে চিহ্নিত করা হলে, পূর্বপুরুষের শেষ বিন্দু থেকে বংশধরের শেষ বিন্দু পর্যন্ত যে প্রান্তের অভিযোজন হয় তার সেট নির্দিষ্ট করে প্রদত্ত গ্রাফের একটি অভিযোজন বর্ণনা করা যেতে পারে। এই সেটের বাইরের অবশিষ্ট প্রান্তগুলি অবশ্যই অন্য দিকে অভিমুখী হতে হবে। এই কৌশলটি মনোডিক দ্বিতীয় ক্রম যুক্তিতে অভিমুখের সাথে জড়িত গ্রাফ বৈশিষ্ট্যগুলিকে নির্দিষ্ট করার অনুমতি দেয়, যার ফলে এই বৈশিষ্ট্যগুলি করসেলের উপপাদ্য ব্যবহার করে আবদ্ধ ত্রি-প্রস্থের গ্রাফগুলিতে দক্ষতার সাথে পরীক্ষা করা যায়। সম্পর্কিত বৈশিষ্ট্যগুলি যদি একটি গ্রাফের একটি হ্যামিল্টনিয়ান পথ থাকে, তবে সেই পথটিও (তার শেষ বিন্দুগুলির একটিতে শিকড়যুক্ত) একটি ট্রেমাক্স গাছ। প্রতিটি ট্রেমাক্স গাছের যে অনির্দিষ্ট গ্রাফগুলির জন্য এই রূপটি রয়েছে সেগুলি হল চক্র গ্রাফ, সম্পূর্ণ গ্রাফ এবং ভারসাম্যপূর্ণ সম্পূর্ণ দ্বিদলীয় গ্রাফ। ট্রেমাক্স গাছগুলি গাছের গভীরতার ধারণার সাথে ঘনিষ্ঠভাবে সম্পর্কিত। একটি গ্রাফের বৃক্ষ-গভীরতাকে ক্ষুদ্রতম সংখ্যা হিসাবে সংজ্ঞায়িত করা যেতে পারে যার জন্য একটি গ্রাফ রয়েছে, যার গভীরতার একটি ট্রেমাক্স গাছ রয়েছে, যেমন একটি উপগ্রাফ। গ্রাফের একটি পরিবারে বাউন্ডেড ট্রি-ডেপথ এমন একটি পথের অস্তিত্বের সমতুল্য যা পরিবারের গ্রাফের একটি ছোট গ্রাফ হিসাবে ঘটতে পারে না। গ্রাফের অনেক কঠিন গণনামূলক সমস্যার অ্যালগরিদম রয়েছে যা স্থির-পরামিতি ট্র্যাক্টেবল যখন তাদের ইনপুটগুলির ট্রি-গভীরতা দ্বারা প্যারামিটারাইজ করা হয়। প্রদত্ত গ্রাফটি সমতলীয় কিনা তা পরীক্ষা করার জন্য ফ্রেইসিক্স-রোজেনস্টিল প্ল্যানারিটি মানদণ্ডে ট্রেমাক্স গাছগুলিও মূল ভূমিকা পালন করে। এই মানদণ্ড অনুসারে, একটি গ্রাফ সমতলীয় হয় যদি, একটি প্রদত্ত ট্রেমাক্স গাছের জন্য, অবশিষ্ট প্রান্তগুলি গাছের বাম বা ডানদিকে সামঞ্জস্যপূর্ণ উপায়ে স্থাপন করা যেতে পারে, এমন সীমাবদ্ধতার সাপেক্ষে যা একই স্থানের প্রান্তগুলিকে একে অপরকে অতিক্রম করতে বাধা দেয়। অসীম গ্রাফের অস্তিত্ব প্রতিটি অসীম গ্রাফের একটি স্বাভাবিক বিস্তৃত গাছ থাকে না। উদাহরণস্বরূপ, একটি অগণিত শীর্ষগুলির সেটের একটি সম্পূর্ণ গ্রাফের একটি নেইঃ একটি সম্পূর্ণ গ্রাফে একটি স্বাভাবিক বিস্তৃত গাছ কেবল একটি পথ হতে পারে, তবে একটি পথে কেবল গণনাযোগ্য সংখ্যক শীর্ষ থাকে। যাইহোক, গণনাযোগ্য শীর্ষগুলির সেটের প্রতিটি গ্রাফের একটি স্বাভাবিক স্প্যানিং ট্রি থাকে। এমনকি গণনাযোগ্য গ্রাফগুলিতেও, একটি গভীরতা-প্রথম অনুসন্ধান শেষ পর্যন্ত পুরো গ্রাফটি অন্বেষণে সফল নাও হতে পারে, এবং প্রতিটি স্বাভাবিক বিস্তৃত গাছ একটি গভীরতা-প্রথম অনুসন্ধান দ্বারা তৈরি করা যায় নাঃ একটি গভীরতা-প্রথম অনুসন্ধান গাছ হতে, একটি গণনাযোগ্য স্বাভাবিক বিস্তৃত গাছের অবশ্যই একটি অসীম পথ বা অসীম সংখ্যক শিশু সহ একটি নোড থাকতে হবে (এবং উভয়ই নয়)। অপ্রাপ্তবয়স্করা যদি একটি অসীম গ্রাফের একটি স্বাভাবিক স্প্যানিং ট্রি থাকে, তবে প্রতিটি সংযুক্ত গ্রাফের ক্ষেত্রেও এটি ছোট হয়। এর থেকে বোঝা যায় যে, যে গ্রাফগুলিতে স্বাভাবিকভাবে বিস্তৃত গাছ রয়েছে সেগুলিতে নিষিদ্ধ অপ্রাপ্তবয়স্কদের দ্বারা একটি বৈশিষ্ট্য রয়েছে। নিষিদ্ধ অপ্রাপ্তবয়স্কদের দুটি শ্রেণীর মধ্যে একটি দ্বিদলীয় গ্রাফ নিয়ে গঠিত যেখানে দ্বিদলীয় বিভাজনের একটি দিক গণনাযোগ্য, অন্য দিকটি অগণিত এবং প্রতিটি শীর্ষে অসীম মাত্রা রয়েছে। নিষিদ্ধ অপ্রাপ্তবয়স্কদের অন্য শ্রেণীটি অ্যারোনসজান গাছ থেকে প্রাপ্ত নির্দিষ্ট গ্রাফ নিয়ে গঠিত। এই বৈশিষ্ট্যের বিশদ বিবরণ গণিতকে আনুষ্ঠানিক করতে ব্যবহৃত সেট-তাত্ত্বিক স্বতঃসিদ্ধকরণের পছন্দের উপর নির্ভর করে। বিশেষত, সেট তত্ত্বের মডেলগুলিতে যার জন্য মার্টিনের স্বতঃসিদ্ধ সত্য এবং কন্টিনিউয়াম হাইপোথিসিস মিথ্যা, এই বৈশিষ্ট্যের দ্বিদলীয় গ্রাফের শ্রেণিকে একক নিষিদ্ধ মাইনর দ্বারা প্রতিস্থাপিত করা যেতে পারে। যাইহোক, যে মডেলগুলিতে কন্টিনিউয়াম হাইপোথিসিস সত্য, এই শ্রেণীতে এমন গ্রাফ রয়েছে যা ছোটখাটো ক্রমে একে অপরের সাথে অতুলনীয়। শেষ এবং পরিমাপযোগ্যতা সাধারণ বিস্তৃত গাছগুলি একটি অসীম গ্রাফের প্রান্তের সাথেও ঘনিষ্ঠভাবে সম্পর্কিত, অসীম পথের সমতুল্য শ্রেণী যা স্বজ্ঞাতভাবে একই দিকে অনন্তের দিকে যায়। যদি একটি গ্রাফের একটি স্বাভাবিক বিস্তৃত গাছ থাকে, তবে এই গাছের প্রতিটি গ্রাফের প্রান্তের জন্য অবশ্যই একটি করে অসীম পথ থাকতে হবে। একটি অসীম গ্রাফকে একটি টপোলজিকাল স্পেস তৈরি করতে ব্যবহার করা যেতে পারে গ্রাফটিকে একটি সরল জটিল হিসাবে দেখে এবং গ্রাফের প্রতিটি প্রান্তের জন্য অনন্ততায় একটি বিন্দু যোগ করে। এই টপোলজির সাথে, একটি গ্রাফের একটি স্বাভাবিক বিস্তৃত গাছ থাকে যদি এবং কেবল তখনই যদি এর শীর্ষগুলির সেটটি বন্ধ সেটগুলির গণনাযোগ্য ইউনিয়নে বিভক্ত করা যায়। উপরন্তু, এই টপোলজিকাল স্থানটি একটি মেট্রিক স্থান দ্বারা প্রতিনিধিত্ব করা যেতে পারে যদি এবং শুধুমাত্র যদি গ্রাফটিতে একটি স্বাভাবিক বিস্তৃত গাছ থাকে। রেফারেন্স গ্রাফ তত্ত্বের বস্তু বিস্তৃত বৃক্ষ গ্রাফ গৌণ তত্ত্ব অসীম গ্রাফ