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