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