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