End (graph theory)
অসীম গ্রাফের গণিতে, একটি গ্রাফের শেষ স্বজ্ঞাতভাবে এমন একটি দিককে উপস্থাপন করে যেখানে গ্রাফটি অনন্ত পর্যন্ত প্রসারিত হয়। শেষগুলি গাণিতিকভাবে অসীম পথের সমতুল্য শ্রেণী হিসাবে আনুষ্ঠানিক করা যেতে পারে, গ্রাফের অনুসরণ-ফাঁকি খেলার কৌশলগুলি বর্ণনা করার আশ্রয়স্থল হিসাবে, বা (স্থানীয়ভাবে সীমাবদ্ধ গ্রাফের ক্ষেত্রে) গ্রাফের সাথে যুক্ত টপোলজিকাল স্পেসের টপোলজিকাল প্রান্ত হিসাবে। গ্রাফের প্রান্তগুলি ব্যবহার করা যেতে পারে (কেলি গ্রাফের মাধ্যমে) সীমাবদ্ধভাবে উত্পন্ন গোষ্ঠীর প্রান্তগুলি সংজ্ঞায়িত করতে। সীমাবদ্ধভাবে উৎপন্ন অসীম গোষ্ঠীগুলির এক, দুই বা অসীম সংখ্যক প্রান্ত থাকে এবং গোষ্ঠীর প্রান্ত সম্পর্কে স্ট্যালিংস উপপাদ্য একাধিক প্রান্তের গোষ্ঠীর জন্য একটি পচন প্রদান করে। সংজ্ঞা এবং চরিত্রায়ন গ্রাফের শেষগুলি অসীম পথের সমতুল্য শ্রেণীর পরিপ্রেক্ষিতে সংজ্ঞায়িত করা হয়েছিল। একটি অসীম আলেখ্যে 'এ' হল একটি আধা-অসীম সহজ পথ; অর্থাৎ, এটি শীর্ষগুলির একটি অসীম ক্রম যেখানে প্রতিটি শীর্ষক্রম ক্রমানুসারে সর্বাধিক একবার প্রদর্শিত হয় এবং ক্রমানুসারে প্রতিটি দুটি ধারাবাহিক শীর্ষবিন্দু গ্রাফের একটি প্রান্তের দুটি শেষ বিন্দু। হ্যালিনের সংজ্ঞা অনুসারে, দুটি রশ্মি এবং সমতুল্য যদি একটি রশ্মি থাকে (যা প্রদত্ত দুটি রশ্মির মধ্যে একটির সমান হতে পারে) যার প্রতিটি এবং এর মধ্যে অসীম সংখ্যক শীর্ষ থাকে। এটি একটি সমতুল্য সম্পর্কঃ প্রতিটি রশ্মি নিজের সমতুল্য, সংজ্ঞাটি দুটি রশ্মির ক্রমের ক্ষেত্রে প্রতিসম, এবং এটি ক্ষণস্থায়ী হিসাবে দেখানো যেতে পারে। অতএব, এটি সমস্ত রশ্মির সেটকে সমতুল্য শ্রেণীতে বিভক্ত করে এবং হ্যালিন একটি প্রান্তকে এই সমতুল্য শ্রেণীগুলির মধ্যে একটি হিসাবে সংজ্ঞায়িত করেন। একই সমতুল্য সম্পর্কের একটি বিকল্প সংজ্ঞাও ব্যবহার করা হয়েছেঃ দুটি রশ্মি এবং সমতুল্য যদি শীর্ষগুলির কোনও সীমাবদ্ধ সেট না থাকে যা এর অসীম সংখ্যক শীর্ষ থেকে অসীম সংখ্যক শীর্ষকে পৃথক করে। এটি হ্যালিনের সংজ্ঞার সমতুল্যঃ যদি হ্যালিনের সংজ্ঞা থেকে রশ্মি বিদ্যমান থাকে, তবে যে কোনও বিভাজকে অবশ্যই অসীম সংখ্যক বিন্দু থাকতে হবে এবং তাই সসীম হতে পারে না, এবং বিপরীতভাবে যদি বিদ্যমান না থাকে তবে এমন একটি পথ যা যতবার সম্ভব পরিবর্তিত হয় এবং অবশ্যই পছন্দসই সসীম বিভাজক গঠন করতে হবে। হ্যাভেন, ফাংশন যা একটি গ্রাফে সাধনা-ফাঁকি খেলার জন্য ফাঁকি কৌশল বর্ণনা করে, তার পরিপ্রেক্ষিতে এন্ডসের আরও সুনির্দিষ্ট বৈশিষ্ট্য রয়েছে। প্রশ্নবিদ্ধ খেলায়, একজন ডাকাত প্রান্ত বরাবর শীর্ষ থেকে শীর্ষে সরে গিয়ে একদল পুলিশকে এড়িয়ে যাওয়ার চেষ্টা করছে। পুলিশের কাছে হেলিকপ্টার রয়েছে এবং তাই প্রান্তগুলি অনুসরণ করার দরকার নেই; তবে ডাকাত পুলিশকে আসতে দেখতে পারে এবং হেলিকপ্টারগুলি অবতরণের আগে পরবর্তী কোথায় যেতে হবে তা বেছে নিতে পারে। একটি হ্যাভেন এমন একটি ফাংশন যা মুছে ফেলার মাধ্যমে গঠিত সাবগ্রাফের সংযুক্ত উপাদানগুলির মধ্যে একটিতে পুলিশের অবস্থানগুলির প্রতিটি সেটকে ম্যাপ করে; একজন ডাকাত খেলার প্রতিটি রাউন্ডে এই উপাদানটির মধ্যে একটি শীর্ষে চলে গিয়ে পুলিশকে এড়াতে পারে। হ্যাভেনদের অবশ্যই একটি সামঞ্জস্যপূর্ণ সম্পত্তি পূরণ করতে হবে (এই প্রয়োজনীয়তার সাথে সামঞ্জস্যপূর্ণ যে ডাকাতটি যে শীর্ষে পুলিশ ইতিমধ্যে অবতরণ করেছে তার মধ্য দিয়ে যেতে পারে না): যদি এটি একটি উপসেট হয়, এবং উভয়ই এবং প্রদত্ত পুলিশের সেটের জন্য বৈধ অবস্থানের সেট হয়, তবে অবশ্যই একটি সুপারসেট হতে হবে। একটি হ্যাভেনের অর্ডার থাকে যদি পুলিশ অবস্থানগুলির সংগ্রহ যার জন্য এটি একটি পালানোর কৌশল সরবরাহ করে তাতে গ্রাফের শীর্ষগুলির চেয়ে কম সমস্ত উপসেট অন্তর্ভুক্ত থাকে; বিশেষত, এটির অর্ডার (ক্ষুদ্রতম আলেফ নম্বর) থাকে যদি এটি শীর্ষগুলির প্রতিটি সীমাবদ্ধ উপসেটকে এর একটি উপাদানের সাথে ম্যাপ করে। প্রতিটি রশ্মি ক্রমের একটি স্বর্গের সাথে মিলে যায়, যথা, ফাংশন; যা প্রতিটি সসীম সেটকে তার অনন্য উপাদানের সাথে ম্যাপ করে যার মধ্যে রশ্মির অসীম সংখ্যক শীর্ষ রয়েছে। বিপরীতভাবে, ক্রমের প্রতিটি আশ্রয়কে একটি রশ্মি দ্বারা এইভাবে সংজ্ঞায়িত করা যেতে পারে। দুটি রশ্মি সমতুল্য হয় যদি এবং শুধুমাত্র যদি তারা একই স্বর্গকে সংজ্ঞায়িত করে, তাই একটি গ্রাফের প্রান্তগুলি তার ক্রমের স্বর্গগুলির সাথে এক-থেকে-এক অনুপাতে থাকে। উদাহরণস্বরূপ, অসীম গ্রাফটি যদি নিজেই একটি রশ্মি হয়, তবে এর অসীম সংখ্যক রশ্মি উপ-গ্রাফ রয়েছে, যা এর প্রতিটি শীর্ষ থেকে শুরু হয়। তবে, এই সমস্ত রশ্মি একে অপরের সমতুল্য, তাই এর একটি মাত্র প্রান্ত রয়েছে। যদি একটি বন হয় (অর্থাৎ, একটি গ্রাফ যার কোনও সীমাবদ্ধ চক্র নেই), তবে যে কোনও দুটি রশ্মির ছেদ হয় একটি পথ বা একটি রশ্মি; দুটি রশ্মি সমতুল্য যদি তাদের ছেদ একটি রশ্মি হয়। যদি প্রতিটি সংযুক্ত অংশে একটি বেস ভার্টেক্স বেছে নেওয়া হয়, তবে এর প্রতিটি প্রান্তে বেস ভার্টিসের একটি থেকে শুরু করে একটি অনন্য রশ্মি থাকে, তাই প্রান্তগুলি এই ক্যানোনিকাল রশ্মির সাথে এক-থেকে-এক সংযোগে স্থাপন করা যেতে পারে। প্রতিটি গণনাযোগ্য গ্রাফের একটি বিস্তৃত বন রয়েছে যার একই প্রান্ত রয়েছে। যাইহোক, শুধুমাত্র একটি প্রান্ত সহ অগণিত অসীম গ্রাফ রয়েছে যেখানে প্রতিটি বিস্তৃত গাছের অসীম সংখ্যক প্রান্ত রয়েছে। যদি একটি অসীম গ্রিড গ্রাফ হয়, তবে এতে অনেক রশ্মি রয়েছে এবং নির্বিচারে শীর্ষ-বিচ্ছিন্ন রশ্মির বড় সেট রয়েছে। তবে এর একটি মাত্র শেষ রয়েছে। স্বর্গের পরিপ্রেক্ষিতে প্রান্তগুলির বৈশিষ্ট্য ব্যবহার করে এটি সবচেয়ে সহজেই দেখা যেতে পারেঃ শীর্ষগুলির যে কোনও সীমাবদ্ধ সেট অপসারণ ঠিক একটি অসীম সংযুক্ত উপাদান ছেড়ে যায়, তাই কেবল একটি স্বর্গ রয়েছে (যা প্রতিটি সীমাবদ্ধ সেটকে অনন্য অসীম সংযুক্ত উপাদানের সাথে ম্যাপ করে)। টপোলজিক্যাল প্রান্তের সাথে সম্পর্ক বিন্দু-সেট টপোলজিতে, একটি প্রান্তের ধারণা রয়েছে যা গ্রাফ তত্ত্বের একটি প্রান্তের ধারণার অনুরূপ, তবে একেবারে একই নয়, যা অনেক আগে থেকে রয়েছে। যদি একটি টপোলজিকাল স্থান কম্প্যাক্ট সেটগুলির একটি নেস্টেড ক্রম দ্বারা আচ্ছাদিত করা যায়, তবে স্থানটির একটি প্রান্ত হল কম্প্যাক্ট সেটগুলির পরিপূরকের উপাদানগুলির একটি ক্রম। এই সংজ্ঞাটি কম্প্যাক্ট সেটগুলির পছন্দের উপর নির্ভর করে নাঃ এই ধরনের একটি পছন্দ দ্বারা সংজ্ঞায়িত প্রান্তগুলি অন্য কোনও পছন্দ দ্বারা সংজ্ঞায়িত প্রান্তগুলির সাথে এক-থেকে-এক চিঠিতে স্থাপন করা যেতে পারে। একটি অসীম গ্রাফকে দুটি ভিন্ন কিন্তু সম্পর্কিত উপায়ে একটি টপোলজিকাল স্পেসে তৈরি করা যেতে পারেঃ গ্রাফের প্রতিটি শীর্ষকে একটি বিন্দু দ্বারা প্রতিস্থাপন করা এবং গ্রাফের প্রতিটি প্রান্তকে একটি উন্মুক্ত একক ব্যবধান দ্বারা প্রতিস্থাপন করা গ্রাফ থেকে একটি হাউসডর্ফ স্থান তৈরি করে যেখানে একটি সেটকে সংজ্ঞায়িত করা হয় যখনই গ্রাফের প্রান্তের সাথে প্রতিটি ছেদ একক ব্যবধানের একটি উন্মুক্ত উপসেট হয়। গ্রাফের প্রতিটি শীর্ষকে একটি বিন্দু দ্বারা এবং গ্রাফের প্রতিটি প্রান্তকে একটি বিন্দু দ্বারা প্রতিস্থাপিত করলে একটি অ-হাউজডর্ফ স্থান তৈরি হয় যেখানে খোলা সেটগুলি সেই বৈশিষ্ট্যযুক্ত সেট হয় যে, যদি এর একটি শীর্ষ থাকে, তবে প্রতিটি প্রান্ত তার শেষ বিন্দুগুলির মধ্যে একটি হিসাবে থাকে। উভয় ক্ষেত্রেই, প্রতিটি সসীম সাবগ্রাফ টপোলজিকাল স্পেসের একটি কম্প্যাক্ট সাবস্পেসের সাথে মিলে যায় এবং প্রতিটি কম্প্যাক্ট সাবস্পেস একত্রে একটি সসীম সাবগ্রাফের সাথে মিলে যায়, হাউসডর্ফের ক্ষেত্রে, প্রান্তের সীমাবদ্ধভাবে অনেকগুলি কম্প্যাক্ট যথাযথ সাবসেট। সুতরাং, একটি গ্রাফ কম্প্যাক্ট সেটগুলির একটি নেস্টেড ক্রম দ্বারা আচ্ছাদিত হতে পারে যদি এবং শুধুমাত্র যদি এটি স্থানীয়ভাবে সীমাবদ্ধ হয়, প্রতিটি শীর্ষে প্রান্তের একটি সীমাবদ্ধ সংখ্যা থাকে। যদি একটি গ্রাফ সংযুক্ত থাকে এবং স্থানীয়ভাবে সীমাবদ্ধ থাকে, তবে এর একটি সংক্ষিপ্ত আবরণ থাকে যেখানে সেটটি কিছু নির্বিচারে নির্বাচিত প্রারম্ভিক শীর্ষ থেকে সর্বাধিক দূরত্বে শীর্ষগুলির সেট। এই ক্ষেত্রে যে কোনও আশ্রয়স্থল টপোলজিকাল স্থানের একটি শেষকে সংজ্ঞায়িত করে। এবং বিপরীতভাবে, যদি থেকে সংজ্ঞায়িত টপোলজিকাল স্থানের একটি শেষ হয়, তবে এটি একটি আশ্রয়স্থলকে সংজ্ঞায়িত করে যেখানে উপাদানটি রয়েছে, যেখানে যে কোনও সংখ্যা যথেষ্ট বড় যা ধারণ করে। সুতরাং, সংযুক্ত এবং স্থানীয়ভাবে সীমাবদ্ধ গ্রাফগুলির জন্য, টপোলজিকাল প্রান্তগুলি গ্রাফ-তাত্ত্বিক প্রান্তগুলির সাথে এক-থেকে-এক মিল রয়েছে। যে গ্রাফগুলি স্থানীয়ভাবে সীমাবদ্ধ নাও হতে পারে, সেগুলির জন্য গ্রাফ এবং তার প্রান্তগুলি থেকে একটি টপোলজিকাল স্থান সংজ্ঞায়িত করা এখনও সম্ভব। এই স্থানটিকে মেট্রিক স্থান হিসাবে উপস্থাপন করা যেতে পারে যদি এবং শুধুমাত্র গ্রাফটিতে একটি স্বাভাবিক বিস্তৃত গাছ থাকে, একটি শিকড়যুক্ত বিস্তৃত গাছ যাতে প্রতিটি গ্রাফের প্রান্ত একটি পূর্বপুরুষ-বংশোদ্ভূত জুটিকে সংযুক্ত করে। যদি একটি স্বাভাবিক স্প্যানিং ট্রি বিদ্যমান থাকে, তবে প্রদত্ত গ্রাফের মতো এটির প্রান্তগুলির একই সেট রয়েছেঃ গ্রাফের প্রতিটি প্রান্তে অবশ্যই গাছের মধ্যে ঠিক একটি অসীম পথ থাকতে হবে। বিশেষ ধরনের প্রান্ত মুক্ত প্রান্ত একটি গ্রাফের প্রান্তকে একটি মুক্ত প্রান্ত হিসাবে সংজ্ঞায়িত করা হয় যদি গ্রাফের অন্যান্য সমস্ত প্রান্ত থেকে পৃথক বৈশিষ্ট্যযুক্ত শীর্ষগুলির একটি সীমাবদ্ধ সেট থাকে। (অর্থাৎ, স্বর্গের দিক থেকে, অন্য প্রতিটি প্রান্ত থেকে বিচ্ছিন্ন।) সীমাবদ্ধভাবে অনেক প্রান্ত সহ একটি গ্রাফে, প্রতিটি প্রান্ত অবশ্যই মুক্ত হতে হবে। এটি প্রমাণ করে যে, যদি অসীম সংখ্যক প্রান্ত থাকে, তবে হয় এমন একটি প্রান্ত থাকে যা মুক্ত নয়, অথবা এমন একটি অসীম রশ্মি পরিবার রয়েছে যা একটি সাধারণ প্রারম্ভিক শীর্ষ ভাগ করে এবং অন্যথায় একে অপরের থেকে বিচ্ছিন্ন। একটি গ্রাফের একটি পুরু প্রান্ত হল এমন একটি প্রান্ত যেখানে অসীম সংখ্যক জোড়া-বিচ্ছিন্ন রশ্মি থাকে। হ্যালিনের গ্রিড উপপাদ্যটি এমন গ্রাফগুলিকে চিহ্নিত করে যা পুরু প্রান্ত ধারণ করেঃ এগুলি ঠিক সেই গ্রাফ যা একটি উপগ্রাফ হিসাবে ষড়ভুজাকার টাইলিংয়ের একটি উপবিভাগ রয়েছে। বিশেষ ধরনের গ্রাফ প্রতিসম এবং প্রায়-প্রতিসম গ্রাফগুলি একটি সংযুক্ত স্থানীয়ভাবে সীমাবদ্ধ গ্রাফকে "প্রায় প্রতিসম" হিসাবে সংজ্ঞায়িত করে যদি একটি শীর্ষ এবং এমন একটি সংখ্যা বিদ্যমান থাকে যে, অন্য প্রতিটি শীর্ষের জন্য, গ্রাফের একটি স্বয়ংক্রিয়তা থাকে যার জন্য চিত্রটি দূরত্বের মধ্যে থাকে; সমতুল্যভাবে, একটি সংযুক্ত স্থানীয়ভাবে সীমাবদ্ধ গ্রাফ প্রায় প্রতিসম হয় যদি তার স্বয়ংক্রিয়তা গোষ্ঠীর সীমাবদ্ধভাবে অনেক কক্ষপথ থাকে। তিনি যেমন দেখিয়েছেন, প্রতিটি সংযুক্ত স্থানীয়ভাবে সীমাবদ্ধ প্রায়-প্রতিসম গ্রাফের জন্য, প্রান্তের সংখ্যা হয় সর্বাধিক দুই বা অগণিত; যদি এটি অগণিত হয়, তবে প্রান্তগুলিতে ক্যান্টর সেটের টপোলজি থাকে। উপরন্তু, মোহর দেখায় যে প্রান্তের সংখ্যা চিগার ধ্রুবককে নিয়ন্ত্রণ করে যেখানে গ্রাফের শীর্ষগুলির সমস্ত সীমাবদ্ধ অ-খালি সেটের মধ্যে থাকে এবং যেখানে একটি শেষ বিন্দু সহ প্রান্তের সেটকে বোঝায়। অগণিত অনেক প্রান্ত সহ প্রায়-প্রতিসম গ্রাফের জন্য, তবে, মাত্র দুটি প্রান্ত সহ প্রায়-প্রতিসম গ্রাফের জন্য,। কাইলি গ্রাফ প্রতিটি গ্রুপ এবং গ্রুপের জন্য জেনারেটরের একটি সেট একটি কাইলি গ্রাফ নির্ধারণ করে, একটি গ্রাফ যার শীর্ষগুলি গ্রুপ উপাদান এবং প্রান্তগুলি উপাদানগুলির জোড়া যেখানে জেনারেটরগুলির মধ্যে একটি। একটি সীমাবদ্ধভাবে উৎপন্ন গোষ্ঠীর ক্ষেত্রে, গোষ্ঠীর প্রান্তগুলি জেনারেটরের সীমাবদ্ধ সেটের জন্য কাইলি গ্রাফের প্রান্ত হিসাবে সংজ্ঞায়িত করা হয়; এই সংজ্ঞাটি জেনারেটরের পছন্দের অধীনে অপরিবর্তনীয়, এই অর্থে যে যদি দুটি ভিন্ন সীমাবদ্ধ সেট জেনারেটর বেছে নেওয়া হয়, তবে দুটি কাইলি গ্রাফের প্রান্তগুলি একে অপরের সাথে এক-থেকে-এক চিঠিতে থাকে। উদাহরণস্বরূপ, প্রতিটি মুক্ত গোষ্ঠীর একটি কেলি গ্রাফ (তার মুক্ত জেনারেটরের জন্য) রয়েছে যা একটি গাছ। একটি জেনারেটরের মুক্ত গোষ্ঠীর কাইলি গ্রাফের মতো দ্বিগুণ অসীম পথ রয়েছে, যার দুটি প্রান্ত রয়েছে। প্রতিটি মুক্ত গোষ্ঠীর অসীম সংখ্যক শেষ রয়েছে। প্রতিটি পরিমিতভাবে উৎপন্ন অসীম গোষ্ঠীর হয় 1,2 বা অসীম সংখ্যক প্রান্ত থাকে এবং গোষ্ঠীর প্রান্ত সম্পর্কে স্ট্যালিংস উপপাদ্য একাধিক প্রান্ত সহ গোষ্ঠীগুলির একটি পচন প্রদান করে। বিশেষতঃ একটি পরিমিতভাবে উৎপন্ন অসীম গোষ্ঠীর 2টি প্রান্ত থাকে যদি এবং শুধুমাত্র যদি এটির সসীম সূচকের একটি চক্রাকার উপগোষ্ঠী থাকে। একটি পরিমিতভাবে উৎপন্ন অসীম গোষ্ঠীর অসীম সংখ্যক প্রান্ত থাকে যদি এবং শুধুমাত্র যদি এটি সংমিশ্রণ সহ একটি অ-তুচ্ছ মুক্ত পণ্য হয় বা সীমাবদ্ধ সংমিশ্রণ সহ এইচ. এন. এন-সম্প্রসারণ হয়। সীমাবদ্ধভাবে উৎপন্ন অন্যান্য সমস্ত অসীম গোষ্ঠীর ঠিক একটি প্রান্ত রয়েছে। নোটস রেফারেন্স গ্রাফ তত্ত্ব অসীম গ্রাফকে লক্ষ্য করে।