Thrackle
একটি থ্র্যাকল হল সমতলে একটি গ্রাফের এম্বেডিং যেখানে প্রতিটি প্রান্ত একটি জর্ডান চাপ এবং প্রতিটি জোড়া প্রান্ত ঠিক একবার মিলিত হয়। প্রান্তগুলি হয় একটি সাধারণ শেষ বিন্দুতে মিলিত হতে পারে, অথবা, যদি তাদের কোনও সাধারণ শেষ বিন্দু না থাকে, তবে তাদের অভ্যন্তরের একটি বিন্দুতে। পরের ক্ষেত্রে, তাদের অবশ্যই তাদের ছেদ বিন্দুতে অতিক্রম করতে হবেঃ ছেদটি অবশ্যই আড়াআড়ি হতে হবে। রৈখিক থ্র্যাকল হল এমন একটি থ্র্যাকল যা এমনভাবে আঁকা হয় যে এর প্রান্তগুলি সরলরেখার অংশ হয়। পল এরদোস যেমন পর্যবেক্ষণ করেছেন, প্রতিটি রৈখিক থ্রেকলের শীর্ষের মতো সর্বাধিক প্রান্ত থাকে। যদি একটি শীর্ষ v তিন বা ততোধিক প্রান্ত vw, vx এবং vy এর সাথে সংযুক্ত থাকে, তবে সেই প্রান্তগুলির মধ্যে কমপক্ষে একটি (যেমন vw) এমন একটি লাইনে অবস্থিত যা অন্য দুটি প্রান্তকে পৃথক করে। তারপর, ডাব্লু-এর অবশ্যই এক ডিগ্রি থাকতে হবে, কারণ ডাব্লু-তে শেষ হওয়া কোনও লাইন সেগমেন্ট, ভিডব্লিউ ছাড়া, ভিএক্স এবং ভিওয়াই উভয়কেই স্পর্শ করতে পারে না। ডাব্লু এবং ভিডব্লিউ অপসারণ একটি ছোট থ্র্যাকল তৈরি করে, প্রান্ত এবং শীর্ষের সংখ্যার মধ্যে পার্থক্য পরিবর্তন না করে। এই ধরনের অপসারণের পরে একটি থ্র্যাকলের দিকে নিয়ে যায় যেখানে প্রতিটি শীর্ষে সর্বাধিক দুটি প্রতিবেশী থাকে, হ্যান্ডশেকিং লেম্মা দ্বারা প্রান্তের সংখ্যা সর্বাধিক শীর্ষের সংখ্যা। এরদোসের প্রমাণের উপর ভিত্তি করে, কেউ অনুমান করতে পারে যে প্রতিটি রৈখিক থ্রেকল একটি ছদ্মবন। বিজোড় দৈর্ঘ্যের প্রতিটি চক্রকে একটি রৈখিক থ্র্যাকল গঠনের জন্য সাজানো যেতে পারে, তবে জোড় দৈর্ঘ্যের চক্রের জন্য এটি সম্ভব নয়, কারণ যদি চক্রের একটি প্রান্ত নির্বিচারে বেছে নেওয়া হয় তবে অন্য চক্রের শীর্ষগুলি অবশ্যই এই প্রান্তের মধ্য দিয়ে রেখার বিপরীত দিকে পর্যায়ক্রমে থাকতে হবে। মিশা পার্লস আরেকটি সহজ প্রমাণ দিয়েছিলেন যে রৈখিক থ্রেকলগুলির সর্বাধিক n প্রান্ত থাকে, এই সত্যের উপর ভিত্তি করে যে একটি রৈখিক থ্রেকলে প্রতিটি প্রান্তের একটি শেষ বিন্দু থাকে যেখানে প্রান্তগুলি সর্বাধিক 180° কোণে প্রসারিত হয় এবং যার জন্য এটি এই সময়ের মধ্যে সবচেয়ে ঘড়ির কাঁটার দিকে প্রান্ত। কারণ, যদি না হয়, তবে দুটি প্রান্ত থাকবে, প্রান্তের বিপরীত প্রান্তবিন্দুতে এবং প্রান্তের মধ্য দিয়ে রেখার বিপরীত দিকে অবস্থিত, যা একে অপরকে অতিক্রম করতে পারে না। কিন্তু প্রতিটি শীর্ষে শুধুমাত্র একটি প্রান্তের সাপেক্ষে এই বৈশিষ্ট্য থাকতে পারে, তাই প্রান্তের সংখ্যা শীর্ষের সংখ্যার সর্বাধিক সমান। যেমন এরদোস আরও পর্যবেক্ষণ করেছেন, একটি বিন্দু সেটের ব্যাস অনুধাবনকারী জোড়া বিন্দুর সেটকে অবশ্যই একটি রৈখিক থ্রেকল গঠন করতে হবেঃ কোনও দুটি ব্যাস একে অপরের থেকে বিচ্ছিন্ন হতে পারে না, কারণ যদি তারা হয় তবে তাদের চারটি প্রান্তবিন্দুতে দুটি বিচ্ছিন্ন প্রান্তের চেয়ে দূরে দূরত্বে একটি জোড়া থাকবে। এই কারণে, সমতলে n বিন্দুর প্রতিটি সেটে সর্বাধিক n ব্যাস জোড়া থাকতে পারে, যা 1934 সালে হেইঞ্জ হপফ এবং এরিকা প্যানউইটস দ্বারা উত্থাপিত একটি প্রশ্নের উত্তর দেয়। অ্যান্ড্রু ভাজসোনি উচ্চ মাত্রায় ব্যাসের জোড়ার সংখ্যার উপর সীমানা অনুমান করেছেন, এই সমস্যাটিকে সাধারণীকরণ করেছেন। গণনামূলক জ্যামিতিতে, ঘূর্ণায়মান ক্যালিপারের পদ্ধতিটি উত্তল অবস্থানে যে কোনও বিন্দুর সেট থেকে একটি রৈখিক থ্র্যাকল তৈরি করতে ব্যবহার করা যেতে পারে, যা বিন্দুর উত্তল কাঠামোর সমান্তরাল রেখাগুলিকে সমর্থন করে এমন জোড়াগুলিকে সংযুক্ত করে। এই গ্রাফে একটি সাবগ্রাফ হিসাবে ব্যাসের জোড়ার থ্র্যাকল রয়েছে। রেইনহার্ড্ট বহুভুজগুলির ব্যাস রৈখিক থ্র্যাকল গঠন করে। রৈখিক থ্র্যাকলগুলির একটি গণনা সবচেয়ে বড় ছোট বহুভুজ সমস্যা সমাধানের জন্য ব্যবহার করা যেতে পারে, যার ব্যাসের তুলনায় সর্বাধিক ক্ষেত্রফল সহ একটি এন-গন খুঁজে বের করার জন্য। থ্র্যাকল অনুমান জন এইচ কনওয়ে অনুমান করেছিলেন যে, যে কোনও থ্র্যাকলে, প্রান্তের সংখ্যা শীর্ষের সংখ্যার সর্বাধিক সমান। কনওয়ে নিজেই পরিভাষা পথ এবং দাগগুলি (যথাক্রমে প্রান্ত এবং শীর্ষগুলির জন্য) ব্যবহার করেছিলেন, তাই কনওয়ের থ্র্যাকল অনুমানটি মূলত এই আকারে বলা হয়েছিল যে প্রতিটি থ্র্যাকলের পথের মতো কমপক্ষে অনেকগুলি দাগ রয়েছে। কনওয়ের 99-গ্রাফ সমস্যা, ড্যানজার সেটের ন্যূনতম ব্যবধান এবং 16 নম্বর পদক্ষেপের পরে সিলভার মুদ্রার বিজয়ী সহ পুরস্কার সমস্যার একটি অংশ হিসাবে কনওয়ে এই অনুমানটি প্রমাণ বা অস্বীকার করার জন্য $1000 পুরস্কারের প্রস্তাব দিয়েছিলেন। সমতুল্যভাবে, থ্র্যাকল অনুমানটি বলা যেতে পারে কারণ প্রতিটি থ্র্যাকল একটি ছদ্মবন। আরও সুনির্দিষ্টভাবে, যদি থ্র্যাকল অনুমানটি সত্য হয়, তবে থ্র্যাকলগুলি উডলের ফলাফল দ্বারা ঠিক চিহ্নিত করা যেতে পারেঃ এগুলি ছদ্মবন যেখানে দৈর্ঘ্য চার এবং সর্বাধিক একটি বিজোড় চক্রের কোনও চক্র নেই। এটি প্রমাণিত হয়েছে যে সি4 ব্যতীত প্রতিটি চক্র গ্রাফের একটি থ্র্যাকল এম্বেডিং রয়েছে, যা দেখায় যে অনুমানটি তীক্ষ্ণ। অর্থাৎ, পথের মতো একই সংখ্যক দাগযুক্ত থ্র্যাকল রয়েছে। অপর প্রান্তে, সবচেয়ে খারাপ পরিস্থিতি হল যে স্থানের সংখ্যা পথের সংখ্যার দ্বিগুণ; এটিও অর্জনযোগ্য। থ্র্যাকল অনুমানটি এমনভাবে টানা থ্র্যাকলগুলির জন্য সত্য বলে জানা যায় যে প্রতিটি প্রান্ত একটি এক্স-মনোটোন বক্ররেখা, প্রতিটি উল্লম্ব রেখা দ্বারা সর্বাধিক একবার অতিক্রম করা হয়। পরিচিত সীমানা প্রমাণ করে যে প্রতিটি দ্বিদলীয় থ্র্যাকল একটি প্ল্যানার গ্রাফ, যদিও প্ল্যানার উপায়ে আঁকা হয় না। ফলস্বরূপ, তারা দেখায় যে n শীর্ষ সহ প্রতিটি থ্র্যাকলেবল গ্রাফের সর্বাধিক 2n−3 প্রান্ত থাকে। তারপর থেকে এই সীমাটি বেশ কয়েকবার উন্নত করা হয়েছে। প্রথমত, এটি 3 (এন-1)/2-এ উন্নীত করা হয়েছিল এবং অন্য একটি উন্নতির ফলে মোটামুটিভাবে 1.428n-এর একটি সীমা তৈরি হয়েছিল। উপরন্তু, পরবর্তী ফলাফল প্রমাণ করার জন্য ব্যবহৃত পদ্ধতিটি যে কোনও ε> 0-এর জন্য একটি সসীম অ্যালগরিদম প্রদান করে যা হয় (1 + ε) n-এর সীমানাকে উন্নত করে বা অনুমানকে অস্বীকার করে। বর্তমান রেকর্ডটি যার কারণে, যিনি 1.3984n-এর সীমাবদ্ধতা প্রমাণ করেছেন। যদি অনুমানটি মিথ্যা হয়, তবে একটি ন্যূনতম পাল্টা উদাহরণে একটি শীর্ষ ভাগ করে নেওয়ার দুটি জোড় চক্রের রূপ থাকবে। অতএব, অনুমানটি প্রমাণ করার জন্য, এটি প্রমাণ করা যথেষ্ট যে এই ধরনের গ্রাফগুলি থ্র্যাকল হিসাবে আঁকা যায় না। তথ্যসূত্র বাহ্যিক লিঙ্ক thrackle.org-সমস্যা সম্পর্কে ওয়েবসাইট অনুমান টপোলজিকাল গ্রাফ তত্ত্ব জ্যামিতিক ছেদ