Well-covered graph
গ্রাফ তত্ত্বে, একটি সু-আচ্ছাদিত গ্রাফ হল একটি অনির্দিষ্ট গ্রাফ যেখানে প্রতিটি ন্যূনতম শীর্ষ আবরণের আকার প্রতিটি অন্যান্য ন্যূনতম শীর্ষ আবরণের সমান হয়। সমতুল্যভাবে, এগুলি এমন গ্রাফ যেখানে সমস্ত সর্বাধিক স্বাধীন সেটের সমান আকার থাকে। সু-আচ্ছাদিত গ্রাফগুলি 1970 সালে মাইকেল ডি প্লামার দ্বারা সংজ্ঞায়িত এবং প্রথম অধ্যয়ন করা হয়েছিল। ভালভাবে আচ্ছাদিত গ্রাফগুলিতে সমস্ত সম্পূর্ণ গ্রাফ, ভারসাম্যপূর্ণ সম্পূর্ণ দ্বিদলীয় গ্রাফ এবং রুকের গ্রাফ অন্তর্ভুক্ত থাকে যার শীর্ষগুলি একটি দাবা বোর্ডের বর্গক্ষেত্রের প্রতিনিধিত্ব করে এবং প্রান্তগুলি একটি দাবা রুকের পদক্ষেপের প্রতিনিধিত্ব করে। সু-আচ্ছাদিত ঘন গ্রাফগুলির পরিচিত বৈশিষ্ট্যায়ন, সু-আচ্ছাদিত নখ-মুক্ত গ্রাফ এবং উচ্চ ঘেরের সু-আচ্ছাদিত গ্রাফগুলি এই গ্রাফগুলিকে বহুপদী সময়ে সনাক্ত করার অনুমতি দেয়, তবে অন্যান্য ধরণের গ্রাফ ভালভাবে আচ্ছাদিত কিনা তা পরীক্ষা করা একটি সিওএনপি-সম্পূর্ণ সমস্যা। সংজ্ঞাগুলি গ্রাফের একটি শীর্ষ আবরণ হল শীর্ষগুলির একটি সেট যা গ্রাফের প্রতিটি প্রান্তকে স্পর্শ করে। একটি শীর্ষ আবরণ ন্যূনতম, বা অপরিবর্তনীয়, যদি এটি থেকে কোনও শীর্ষ অপসারণ আচ্ছাদন সম্পত্তি ধ্বংস করে দেয়। যদি কম শীর্ষ সহ অন্য কোনও শীর্ষ আবরণ না থাকে তবে এটি সর্বনিম্ন। একটি ভালভাবে আচ্ছাদিত গ্রাফ হল এমন একটি যেখানে প্রতিটি ন্যূনতম আবরণও ন্যূনতম হয়। ভালভাবে আচ্ছাদিত গ্রাফগুলি সংজ্ঞায়িত করা মূল গবেষণাপত্রে, প্লামার লিখেছেন যে এটি "স্পষ্টতই সমতুল্য" যে প্রতিটি দুটি ন্যূনতম কভারের একে অপরের মতো একই সংখ্যক শীর্ষ থাকে। একটি গ্রাফে একটি স্বাধীন সেট হল শীর্ষগুলির একটি সেট যার মধ্যে দুটি একে অপরের সংলগ্ন নয়। যদি একটি গ্রাফের একটি শীর্ষ আবরণ হয়, তবে এর পরিপূরক অবশ্যই একটি স্বাধীন সেট হতে হবে, এবং তদ্বিপরীত। একটি ন্যূনতম শীর্ষ আবরণ যদি এবং শুধুমাত্র যদি এর পরিপূরক একটি সর্বাধিক স্বাধীন সেট হয়, এবং একটি ন্যূনতম শীর্ষ আবরণ হয় যদি এবং শুধুমাত্র যদি এর পরিপূরক একটি সর্বাধিক স্বাধীন সেট হয়। অতএব, একটি সু-আচ্ছাদিত গ্রাফ হল, সমতুল্যভাবে, এমন একটি গ্রাফ যেখানে প্রতিটি সর্বাধিক স্বাধীন সেটের একই আকার থাকে, বা এমন একটি গ্রাফ যেখানে প্রতিটি সর্বাধিক স্বাধীন সেট সর্বাধিক হয়। ভালভাবে আচ্ছাদিত গ্রাফগুলি সংজ্ঞায়িত করার মূল গবেষণাপত্রে, এই সংজ্ঞাগুলি সংযুক্ত গ্রাফগুলিতে সীমাবদ্ধ ছিল, যদিও এগুলি বিচ্ছিন্ন গ্রাফগুলির জন্যও অর্থবহ। কিছু পরবর্তী লেখক সংযোগের প্রয়োজনীয়তাকে দুর্বল প্রয়োজনীয়তার সাথে প্রতিস্থাপন করেছেন যে একটি ভালভাবে আচ্ছাদিত গ্রাফের কোনও বিচ্ছিন্ন শীর্ষ থাকতে হবে না। সংযুক্ত ভালভাবে আচ্ছাদিত গ্রাফ এবং বিচ্ছিন্ন শীর্ষগুলি ছাড়া ভালভাবে আচ্ছাদিত গ্রাফ উভয়ের জন্যই, কোনও প্রয়োজনীয় শীর্ষ থাকতে পারে না, শীর্ষগুলি যা প্রতিটি ন্যূনতম শীর্ষের আবরণের অন্তর্গত। উপরন্তু, প্রতিটি ভালভাবে আচ্ছাদিত গ্রাফ শীর্ষস্থানের জন্য একটি গুরুত্বপূর্ণ গ্রাফ এই অর্থে যে, প্রতিটি শীর্ষস্থানের জন্য, গ্রাফ থেকে মুছে ফেললে একটি ছোট ন্যূনতম শীর্ষস্থানের আচ্ছাদন সহ একটি গ্রাফ তৈরি হয়। একটি গ্রাফের ইন্ডিপেন্ডেন্স কমপ্লেক্স হল সরল জটিল যার প্রতিটি স্বাধীন সেটের জন্য একটি সিম্প্লেক্স থাকে। একটি সরল জটিলকে বিশুদ্ধ বলা হয় যদি এর সমস্ত সর্বাধিক সরলতার একই প্রধানতা থাকে, তাই একটি ভালভাবে আচ্ছাদিত গ্রাফ সমতুল্যভাবে একটি বিশুদ্ধ স্বাধীনতা জটিল সহ একটি গ্রাফ হয়। উদাহরণস্বরূপ, চার বা পাঁচ দৈর্ঘ্যের একটি চক্র গ্রাফ ভালভাবে আচ্ছাদিত থাকেঃ প্রতিটি ক্ষেত্রে, প্রতিটি সর্বাধিক স্বাধীন সেটের আকার দুই থাকে। সাত দৈর্ঘ্যের একটি চক্র এবং তিন দৈর্ঘ্যের একটি পথও ভালভাবে আচ্ছাদিত। প্রতিটি সম্পূর্ণ গ্রাফ ভালভাবে আচ্ছাদিত থাকেঃ প্রতিটি সর্বাধিক স্বাধীন সেট একটি একক শীর্ষ নিয়ে গঠিত। একইভাবে, প্রতিটি ক্লাস্টার গ্রাফ (সম্পূর্ণ গ্রাফের একটি বিচ্ছিন্ন মিলন) ভালভাবে আচ্ছাদিত। একটি সম্পূর্ণ দ্বিদলীয় গ্রাফ ভালভাবে আচ্ছাদিত করা হয় যদি এর দ্বিদলীয় বিভাজনের উভয় পক্ষের সমান সংখ্যক শীর্ষ থাকে, কারণ এগুলি কেবল তার সর্বোচ্চ দুটি স্বাধীন সেট। কোনও বিচ্ছিন্ন শীর্ষ ছাড়াই ত্রিভুজ-মুক্ত গ্রাফের পরিপূরক গ্রাফটি ভালভাবে আচ্ছাদিত থাকেঃ এটির দুটির চেয়ে বড় কোনও স্বাধীন সেট নেই এবং প্রতিটি একক শীর্ষকে দ্বি-ভার্টেক্স স্বাধীন সেটে প্রসারিত করা যেতে পারে। একটি রুকের গ্রাফ ভালভাবে আচ্ছাদিত থাকেঃ যদি কেউ দাবা বোর্ডে কোনও রুকের সেট রাখে যাতে কোনও দুটি রুক একে অপরকে আক্রমণ না করে, তবে দাবা বোর্ডের প্রতিটি সারি এবং কলামে একটি না হওয়া পর্যন্ত আরও বেশি আক্রমণ না করা রুক স্থাপন করা সর্বদা সম্ভব। যে গ্রাফের শীর্ষগুলি একটি সাধারণ বহুভুজের তির্যক এবং যার প্রান্তগুলি একে অপরকে অতিক্রম করে এমন তির্যক জোড়া সংযুক্ত করে তা ভালভাবে আচ্ছাদিত, কারণ এর সর্বাধিক স্বাধীন সেটগুলি বহুভুজের ত্রিভুজ এবং সমস্ত ত্রিভুজগুলির একই সংখ্যক প্রান্ত থাকে। যদি কোনও-ভার্টেক্স গ্রাফ হয়, তবে এক-প্রান্তের গ্রাফের মূল গুণফল (অর্থাৎ, নতুন শীর্ষগুলি যোগ করে গঠিত গ্রাফ, প্রতিটি ডিগ্রি এক এবং প্রতিটি একটি স্বতন্ত্র শীর্ষের সংলগ্ন) ভালভাবে আচ্ছাদিত। কারণ, একটি সর্বাধিক স্বাধীন সেট অবশ্যই পরিপূরক সেটের ডিগ্রি-ওয়ান প্রতিবেশীদের সাথে একত্রে একটি নির্বিচারে স্বাধীন সেট নিয়ে গঠিত হতে হবে এবং তাই অবশ্যই আকার থাকতে হবে। আরও সাধারণভাবে, একটি চক্রের আচ্ছাদন (চক্রের শীর্ষগুলির একটি বিভাজন) সহ যে কোনও গ্রাফ দেওয়া হলে, প্রতিটি গোষ্ঠীতে আরেকটি শীর্ষ যোগ করে গঠিত গ্রাফটি ভালভাবে আবৃত থাকে; মূলযুক্ত পণ্যটি এই নির্মাণের বিশেষ ক্ষেত্রে যখন এক-ভার্টেক্স চক্র নিয়ে গঠিত হয়। সুতরাং, প্রতিটি গ্রাফ একটি ভালভাবে আচ্ছাদিত গ্রাফের একটি প্ররোচিত উপগ্রাফ। দ্বিপক্ষীয়তা, খুব ভালভাবে আচ্ছাদিত গ্রাফ এবং ঘের একটি খুব ভালভাবে আচ্ছাদিত গ্রাফকে একটি ভালভাবে আচ্ছাদিত গ্রাফ (সম্ভবত সংযোগ বিচ্ছিন্ন, তবে কোনও বিচ্ছিন্ন শীর্ষ ছাড়াই) হিসাবে সংজ্ঞায়িত করে যেখানে প্রতিটি সর্বাধিক স্বাধীন সেট (এবং তাই প্রতিটি ন্যূনতম শীর্ষ আবরণও) ঠিক অর্ধেক শীর্ষ থাকে। এই সংজ্ঞাটিতে একটি গ্রাফের মূল পণ্য এবং একটি এক-প্রান্তের গ্রাফ অন্তর্ভুক্ত রয়েছে। উদাহরণস্বরূপ, এটি এবং দ্বারা অধ্যয়ন করা দ্বিদলীয় ভাল-আচ্ছাদিত গ্রাফগুলিও অন্তর্ভুক্ত করেঃ বিচ্ছিন্ন শীর্ষ ছাড়াই দ্বিদলীয় গ্রাফে, যে কোনও দ্বিদলীয় বিভাজনের উভয় দিক সর্বাধিক স্বাধীন সেট (এবং ন্যূনতম শীর্ষ আবরণ) গঠন করে, তাই যদি গ্রাফটি ভালভাবে আবৃত থাকে তবে উভয় পক্ষের সমানভাবে অনেকগুলি শীর্ষ থাকতে হবে। একটি সু-আচ্ছাদিত আলেখ্যে, বিচ্ছিন্ন শীর্ষ ছাড়াই, সর্বাধিক স্বাধীন সেটের আকার সর্বাধিক হয়, তাই খুব ভালভাবে আচ্ছাদিত গ্রাফগুলি ভালভাবে আচ্ছাদিত গ্রাফ যেখানে সর্বাধিক স্বাধীন সেটের আকার যতটা সম্ভব বড় হয়। একটি দ্বিদলীয় গ্রাফ ভালভাবে আচ্ছাদিত হয় যদি এবং শুধুমাত্র যদি এটির বৈশিষ্ট্যের সাথে একটি নিখুঁত মিল থাকে যা প্রতিটি প্রান্তের জন্য, প্রতিবেশীদের প্ররোচিত উপগ্রাফ এবং একটি সম্পূর্ণ দ্বিদলীয় গ্রাফ গঠন করে। মিলনের পরিপ্রেক্ষিতে বৈশিষ্ট্যায়ন দ্বিদলীয় গ্রাফ থেকে খুব ভালভাবে আচ্ছাদিত গ্রাফ পর্যন্ত প্রসারিত করা যেতে পারেঃ একটি গ্রাফ খুব ভালভাবে আচ্ছাদিত করা হয় যদি এবং শুধুমাত্র যদি এর নিম্নলিখিত দুটি বৈশিষ্ট্যের সাথে নিখুঁত মিল থাকেঃ কোনও প্রান্ত ত্রিভুজের অন্তর্গত না হয়, এবং যদি একটি প্রান্ত ত্রি-প্রান্ত পথের কেন্দ্রীয় প্রান্ত হয়, তবে পথের দুটি শেষ বিন্দু অবশ্যই সংলগ্ন হতে হবে। উপরন্তু, যদি খুব ভালভাবে আচ্ছাদিত করা হয়, তবে প্রতিটি নিখুঁত মিল এই বৈশিষ্ট্যগুলিকে সন্তুষ্ট করে। গাছগুলি দ্বিদলীয় গ্রাফের একটি বিশেষ ক্ষেত্রে, এবং একটি গাছ ভালভাবে আচ্ছাদিত কিনা তা পরীক্ষা করা ভালভাবে আচ্ছাদিত দ্বিদলীয় গ্রাফের বৈশিষ্ট্যের একটি সহজ বিশেষ ক্ষেত্রে পরিচালনা করা যেতে পারেঃ যদি দুটি শীর্ষযুক্ত একটি গাছ হয়, তবে এটি ভালভাবে আচ্ছাদিত হয় যদি এবং শুধুমাত্র যদি গাছের প্রতিটি অ-পাতার নোড ঠিক একটি পাতার সংলগ্ন থাকে। একই বৈশিষ্ট্য স্থানীয়ভাবে গাছের মতো গ্রাফের ক্ষেত্রে প্রযোজ্য, এই অর্থে যে প্রতিটি শীর্ষের নিম্ন-ব্যাসের আশেপাশের অঞ্চলগুলি অ্যাসাইক্লিকঃ যদি একটি গ্রাফের ঘের আট বা তার বেশি হয় (যাতে, প্রতিটি শীর্ষের জন্য, তিনটির দূরত্বের মধ্যে শীর্ষগুলির সাবগ্রাফ অ্যাসাইক্লিক হয়) তবে এটি ভালভাবে আচ্ছাদিত হয় যদি এবং কেবলমাত্র যদি একের চেয়ে বড় ডিগ্রির প্রতিটি শীর্ষে ঠিক এক ডিগ্রি প্রতিবেশী থাকে। একটি ঘনিষ্ঠভাবে সম্পর্কিত কিন্তু আরও জটিল বৈশিষ্ট্য পাঁচ বা তার বেশি ঘেরের ভালভাবে আচ্ছাদিত গ্রাফের ক্ষেত্রে প্রযোজ্য। নিয়মিততা এবং সমতলীয়তা ঘন (3-নিয়মিত) সু-আচ্ছাদিত গ্রাফগুলিকে শ্রেণীবদ্ধ করা হয়েছেঃ এগুলি সাতটি 3-সংযুক্ত উদাহরণ নিয়ে গঠিত, কম সংযোগ সহ ঘন গ্রাফের তিনটি অসীম পরিবার সহ। সাতটি 3-সংযুক্ত কিউবিক সু-আচ্ছাদিত গ্রাফ হল সম্পূর্ণ গ্রাফ, ত্রিভুজাকার প্রিজম এবং পঞ্চভুজাকার প্রিজমের গ্রাফ, ড্যুরার গ্রাফ, ইউটিলিটি গ্রাফ, ওয়াই-ডি রূপান্তর দ্বারা ইউটিলিটি গ্রাফ থেকে প্রাপ্ত আট-ভার্টেক্স গ্রাফ এবং 14-ভার্টেক্স সাধারণীকৃত পিটারসেন গ্রাফ। এই গ্রাফগুলির মধ্যে প্রথম চারটি হল সমতলীয় গ্রাফ। এগুলি কেবলমাত্র চারটি ঘন পলিহেড্রাল গ্রাফ (সাধারণ উত্তল পলিহেড্রার গ্রাফ) যা ভালভাবে আচ্ছাদিত। চারটি গ্রাফ (দুটি প্রিজম, ড্যুরার গ্রাফ এবং) হল পিটারসেন গ্রাফের সাধারণীকরণ। 1-এবং 2-সংযুক্ত ঘন ভাল-আচ্ছাদিত গ্রাফগুলি সমস্ত একটি পথ বা চক্রের নোডগুলিকে গ্রাফের তিনটি টুকরো দ্বারা প্রতিস্থাপিত করে গঠিত হয় যা লেবেল করে, এবং। একটি চক্রের নোড বা কোনও পথের অভ্যন্তরীণ নোড প্রতিস্থাপনের জন্য ফ্র্যাগমেন্ট বা ব্যবহার করা যেতে পারে, অন্যদিকে একটি পথের দুটি প্রান্ত নোড প্রতিস্থাপনের জন্য ফ্র্যাগমেন্ট ব্যবহার করা হয়। খণ্ডে একটি সেতু থাকে, তাই একটি পথে এই প্রতিস্থাপন প্রক্রিয়াটি সম্পাদন করার এবং কিছু পথ নোড (এবং অবশিষ্ট নোডের জন্য অন্যান্য দুটি টুকরো) প্রতিস্থাপনের জন্য খণ্ড ব্যবহার করার ফলাফল হল একটি 1-ভার্টেক্স-সংযুক্ত ঘন ভাল-আচ্ছাদিত গ্রাফ। সমস্ত 1-ভার্টেক্স-সংযুক্ত কিউবিক সু-আচ্ছাদিত গ্রাফের এই রূপ রয়েছে এবং এই ধরনের সমস্ত গ্রাফ সমতল। দুই ধরনের 2-ভার্টেক্স-সংযুক্ত কিউবিক ভাল-আচ্ছাদিত গ্রাফ রয়েছে। এই দুটি পরিবারের মধ্যে একটি চক্রের নোডগুলিকে টুকরো দ্বারা প্রতিস্থাপন করে গঠিত হয় এবং কমপক্ষে দুটি টুকরো টাইপের হয়; এই ধরনের একটি গ্রাফ সমতল হয় যদি এবং শুধুমাত্র যদি এতে কোনও ধরণের টুকরো না থাকে। অন্য পরিবারটি একটি পথের নোডগুলিকে টুকরো টুকরো দ্বারা প্রতিস্থাপিত করে গঠিত হয় এবং এই ধরনের সমস্ত গ্রাফ সমতলীয়। তিনটি মাত্রায় সু-আচ্ছাদিত সাধারণ পলিহেড্রার বৈশিষ্ট্যের পরিপূরক হিসাবে, গবেষকরা সু-আচ্ছাদিত সরল পলিহেড্রাকে বা সমতুল্যভাবে সু-আচ্ছাদিত সর্বাধিক সমতলীয় গ্রাফগুলিও বিবেচনা করেছেন। পাঁচ বা ততোধিক শীর্ষযুক্ত প্রতিটি সর্বাধিক সমতলীয় গ্রাফের শীর্ষ সংযোগ 3,4 বা 5 রয়েছে। কোনও ভালভাবে আচ্ছাদিত 5-সংযুক্ত সর্বাধিক সমতলীয় গ্রাফ নেই, এবং শুধুমাত্র চারটি 4-সংযুক্ত ভালভাবে আচ্ছাদিত সর্বাধিক সমতলীয় গ্রাফ রয়েছেঃ নিয়মিত অষ্টতলকের গ্রাফ, পঞ্চভুজাকার দ্বিমেরু, স্নব ডিসফেনয়েড, এবং 12টি শীর্ষ, 30টি প্রান্ত এবং 20টি ত্রিভুজাকার মুখ সহ একটি অনিয়মিত পলিহেড্রন (একটি নন-কনভেক্স ডেল্টাহেড্রন)। যাইহোক, অসীমভাবে অনেকগুলি 3-সংযুক্ত সু-আচ্ছাদিত সর্বাধিক সমতলীয় গ্রাফ রয়েছে। উদাহরণস্বরূপ, যদি একটি-ভার্টেক্স ম্যাক্সিমাল প্ল্যানার গ্রাফের ত্রিভুজ মুখগুলি বিচ্ছিন্ন থাকে, তবে এই মুখগুলি একটি চক্র আবরণ গঠন করবে। অতএব, চক্রের আবরণ গঠন, যা এই গ্রাফগুলির জন্য একটি কেন্দ্রীয় শীর্ষে মিলিত এই ত্রিভুজগুলির প্রত্যেকটিকে তিনটি নতুন ত্রিভুজে বিভক্ত করে, একটি ভালভাবে আচ্ছাদিত সর্বাধিক সমতলীয় গ্রাফ তৈরি করে। একটি গ্রাফে বিভিন্ন আকারের দুটি সর্বাধিক স্বাধীন সেট রয়েছে কিনা তা পরীক্ষা করা এন. পি-সম্পূর্ণ; অর্থাৎ, পরিপূরকভাবে, একটি গ্রাফ ভালভাবে আচ্ছাদিত কিনা তা পরীক্ষা করা সি. ও. এন. পি-সম্পূর্ণ। যদিও গ্রাফগুলিতে সর্বাধিক স্বাধীন সেটগুলি খুঁজে পাওয়া সহজ যা ভালভাবে আচ্ছাদিত হিসাবে পরিচিত, তবে কোনও অ্যালগরিদমের পক্ষে আউটপুট হিসাবে উত্পাদন করা এনপি-হার্ড, সমস্ত গ্রাফগুলিতে, হয় সর্বাধিক স্বাধীন সেট বা গ্যারান্টি যে ইনপুটটি ভালভাবে আচ্ছাদিত নয়। এর বিপরীতে, একটি প্রদত্ত গ্রাফ বহুপদী সময়ে খুব ভালভাবে আচ্ছাদিত কিনা তা পরীক্ষা করা সম্ভব। এটি করার জন্য, একটি খুব ভালভাবে আচ্ছাদিত গ্রাফে একটি মিলে যাওয়া প্রান্তের দুটি বৈশিষ্ট্যকে সন্তুষ্ট করে এমন প্রান্তগুলির সমন্বিত উপগ্রাফটি খুঁজে বের করুন এবং তারপরে একটি নিখুঁত মিল রয়েছে কিনা তা পরীক্ষা করার জন্য একটি মিলে যাওয়া অ্যালগরিদম ব্যবহার করুন। কিছু সমস্যা যা নির্বিচারে গ্রাফের জন্য এনপি-সম্পূর্ণ, যেমন হ্যামিল্টনিয়ান চক্র খুঁজে পাওয়ার সমস্যা, খুব ভালভাবে আচ্ছাদিত গ্রাফের জন্য বহুপদী সময়েও সমাধান করা যেতে পারে। একটি গ্রাফকে সমতুল্য বলা হয় যদি প্রতিটি সর্বোচ্চ মিল সর্বাধিক হয়; অর্থাৎ, যদি এর রেখাচিত্রটি ভালভাবে আবৃত থাকে তবে এটি সমতুল্য। আরও দৃঢ়ভাবে এটিকে এলোমেলোভাবে মিলনীয় বলা হয় যদি প্রতিটি সর্বাধিক মিল একটি নিখুঁত মিল হয়। একমাত্র সংযুক্ত এলোমেলোভাবে মেলানো গ্রাফগুলি হল সম্পূর্ণ গ্রাফ এবং ভারসাম্যপূর্ণ সম্পূর্ণ দ্বিদলীয় গ্রাফ। একটি লাইন গ্রাফ, বা আরও সাধারণভাবে একটি নখ-মুক্ত গ্রাফ, বহুপদী সময়ে ভালভাবে আচ্ছাদিত কিনা তা পরীক্ষা করা সম্ভব। পাঁচ বা ততোধিক ঘের সহ সু-আচ্ছাদিত গ্রাফগুলির বৈশিষ্ট্যায়ন এবং 3-নিয়মিত সু-আচ্ছাদিত গ্রাফগুলির বৈশিষ্ট্যও এই গ্রাফগুলিকে সনাক্ত করার জন্য দক্ষ বহুপদী সময় অ্যালগরিদমের দিকে পরিচালিত করে। উল্লেখগুলি উল্লেখ করুন। । যেমনটি উল্লেখ করা হয়েছে। । । । । । । । । । । । । । । । । । । । । । । । । যেমনটি উল্লেখ করা হয়েছে। । । । গ্রাফ পরিবার