গ্রাফ তত্ত্ব - নতুনদের জন্য দ্রুত গাইড

30 অক্টোবর, 2021

গ্রাফ তত্ত্ব এই সবগুলির মধ্যে অ্যাপ্লিকেশন রয়েছে এবং এইভাবে বেশ জনপ্রিয়, তা গণিত, কম্পিউটার বিজ্ঞান, জীববিজ্ঞান, তথ্য প্রযুক্তি বা ভাষাবিজ্ঞান হোক।

সুতরাং, এটা স্বাভাবিক যে আপনি গ্রাফ তত্ত্ব সম্পর্কে আরও অধ্যয়ন করতে আগ্রহী।

এই নিবন্ধটি আপনাকে গ্রাফ তত্ত্বের একটি নির্দেশিকা এনেছে যা আপনাকে এর ধারণাগুলি বুঝতে সাহায্য করবে।

গ্রাফ তত্ত্ব বস্তুর মধ্যে সম্পর্ক মডেল করতে ব্যবহৃত গ্রাফ বা গাণিতিক কাঠামোর অধ্যয়ন হিসাবে সংজ্ঞায়িত করা হয়।

এই গাণিতিক মডেলগুলি বেশিরভাগই প্রান্ত এবং শীর্ষবিন্দু এবং একে অপরের সাথে তাদের সম্পর্ক নিয়ে কাজ করে।

সুচিপত্র

ডেটা স্ট্রাকচার: গাছ এবং গ্রাফ
গ্রাফ তত্ত্বের প্রয়োগ
আসুন বেসিক সম্পর্কে কথা বলি
একটি গ্রাফ কি?
গ্রাফের ধরন
গাছ এবং বন
ভার্টেক্স ডিগ্রী
রং করা
সংযোগ
স্বাধীন সেট
আবরণ
মৌলিক বৈশিষ্ট্য
ভ্রমণযোগ্যতা
মিল
আইসোমরফিজম
হোমোমরফিজম
- হোমোমরফিজম এবং আইসোমরফিজম
- পলিহেড্রাল গ্রাফ
সচরাচর জিজ্ঞাস্য
প্রস্তাবিত প্রবন্ধ

ডেটা স্ট্রাকচার: গাছ এবং গ্রাফ

গাছ এবং গ্রাফ একই বা ভিন্ন ডেটা স্ট্রাকচার হলে আমরা সবসময় বিভ্রান্ত হয়েছি।

হ্যাঁ ঠিক. তারা প্রায় একই।

বৃক্ষ হল নেটওয়ার্ক বা গ্রাফের রুট নোড যা অন্যান্য চাইল্ড এবং লিফ নোডের সাথে সংযোগ করে এবং সবসময় নিয়মের একটি সেট দ্বারা সংজ্ঞায়িত করা হয়। গ্রাফগুলির কোনও সীমাবদ্ধতা নেই এবং কোনও রুট নোড নেই।

গ্রাফগুলিতে, নোডগুলিকে যে কোনও উপায়ে সংযুক্ত করা যেতে পারে এবং গাছের বিপরীতে, গ্রাফগুলিকে এক-দিকনির্দেশিক হতে হবে না।

একটি গাছ সবসময় একটি গ্রাফ বা একটি নেটওয়ার্ক, কিন্তু একটি গ্রাফ বা একটি নেটওয়ার্ক সবসময় একটি গাছ হবে না।

গ্রাফ তত্ত্বের প্রয়োগ

সামাজিক, শারীরিক, তথ্য, এবং জৈবিক সিস্টেমগুলি তাদের মধ্যেকার সম্পর্ক এবং প্রক্রিয়াগুলি গ্রাফ ব্যবহার করে মডেল করা যেতে পারে।

উদাহরণস্বরূপ, বেশিরভাগ কম্পিউটার বিজ্ঞানের ছাত্রদের অবশ্যই নেটওয়ার্ক এবং নেটওয়ার্কিং এর শর্তাবলী সম্পর্কে সচেতন হতে হবে। নেটওয়ার্কগুলি হল এক ধরণের গ্রাফ যার সাথে শীর্ষবিন্দু এবং প্রান্তগুলির সাথে যুক্ত বৈশিষ্ট্যগুলি (যেমন রাউটার, কম্পিউটার সিস্টেম ইত্যাদি)।

এখন যেহেতু আপনি গ্রাফ সম্পর্কে জানেন আসুন আমরা আপনাকে কয়েকটি অ্যাপ্লিকেশন বলি যা আপনার কৌতূহল বাড়াতে এবং গ্রাফ তত্ত্বকে আরও ভালভাবে বুঝতে সাহায্য করবে।

1. কম্পিউটার সায়েন্স

গ্রাফগুলি কমিউনিকেশন নেটওয়ার্ক, কম্পিউটেশনাল ডিভাইস, ডাটা অর্গানাইজেশন, কম্পিউটেশন প্রবাহ ইত্যাদির প্রতিনিধিত্ব করতে পারে।

এর সমস্যাগুলি সামাজিক মাধ্যম , জীববিদ্যা, নিউরোডিজেনারেটিভ রোগের ম্যাপিং, ভ্রমণ, কম্পিউটার চিপ ডিজাইন এবং অন্যান্য অনেক ক্ষেত্রে গ্রাফের প্রান্ত এবং নোড ধারণা ব্যবহার করে।

কম্পিউটার বিজ্ঞানীরা গ্রাফ ডাটাবেস তৈরি করতে গ্রাফ বা নেটওয়ার্ক ট্রান্সফরমেশন সিস্টেম ব্যবহার করতে পারেন যা নিরাপদ লেনদেন, নেটওয়ার্ক-গঠিত ডেটা অনুসন্ধান এবং অবিরাম স্টোরেজের অনুমতি দেয়।

2. গণিত

জ্যামিতি, গণিতের একটি ধারণা, গ্রাফের সর্বাধিক ব্যবহার করে। নট তত্ত্ব, যা টপোলজির একটি অংশ, এছাড়াও গ্রাফ ব্যবহার করে।

বীজগণিত গ্রাফ তত্ত্ব জটিলতা এবং গতিশীল সিস্টেম সহ অনেক ক্ষেত্রে প্রয়োগ করা হয় এবং গ্রুপ তত্ত্বের সাথে ঘনিষ্ঠ সম্পর্ক রয়েছে।

3. ভাষাবিজ্ঞান

প্রাকৃতিক ভাষা এবং বিচ্ছিন্ন কাঠামোর মধ্যে ভাল সামঞ্জস্যের কারণে, ভাষাবিজ্ঞান গ্রাফ তত্ত্ব পদ্ধতির বিভিন্ন ব্যবহার খুঁজে পেয়েছে।

উদাহরণস্বরূপ, সিনট্যাক্স এবং কম্পোজিশনাল শব্দার্থবিদ্যা, যা ঐতিহ্যগত পন্থা, গাছ-ভিত্তিক বা শ্রেণিবদ্ধ নেটওয়ার্ক বা গ্রাফ মডেলগুলি অনুসরণ করে।

মাথা চালিত শব্দগুচ্ছ গঠন ব্যাকরণ, প্রাকৃতিক ভাষায় একটি সমসাময়িক পদ্ধতি, টাইপ করা বৈশিষ্ট্য কাঠামো বা নির্দেশিত অ্যাসাইক্লিক গ্রাফ ব্যবহার করে মডেল করা হয়।

অনেক প্রতিষ্ঠান, যেমন TextGraphs, WordNet, VerbNet ইত্যাদি, ভাষাবিজ্ঞানে গ্রাফের অনেক ব্যবহারের কারণে কার্যকরী হয়েছে।

4. সামাজিক বিজ্ঞান

সমাজবিজ্ঞান গ্রাফ তত্ত্ব ব্যবহার করে সামাজিক নেটওয়ার্ক বিশ্লেষণ করতে গুজব ছড়ানোর অন্বেষণ করতে বা এই নেটওয়ার্কগুলিতে অভিনেতাদের প্রতিপত্তি পরিমাপ করে।

অন্যান্য গ্রাফের মধ্যে রয়েছে পরিচিতি গ্রাফ, বন্ধুত্বের গ্রাফ, প্রভাব গ্রাফ, সহযোগিতার গ্রাফ ইত্যাদি, যার সবকটিই মানুষের আচরণ অধ্যয়ন করে।

5. পদার্থবিদ্যা এবং রসায়ন

আপনি জেনে আশ্চর্য হবেন, কিন্তু গ্রাফ তত্ত্ব আণবিক নেটওয়ার্কের অধ্যয়নে এটি ব্যবহার করে পদার্থবিদ্যা এবং রসায়নে তার পথ খুঁজে পেয়েছে।

এটি পদার্থবিদ্যায় ঘনীভূত পদার্থের পদার্থবিদ্যা এবং ত্রিমাত্রিক পারমাণবিক কাঠামো এবং নেটওয়ার্কগুলি অধ্যয়ন করতে ব্যবহৃত হয় যা পরমাণু টপোলজি সম্পর্কিত গ্রাফ-তত্ত্ব পরিসংখ্যান ব্যবহার করে।

পদার্থবিজ্ঞানের কোয়ান্টাম ক্ষেত্র তত্ত্বটি ফাইনম্যান গ্রাফ এবং গণনার নিয়ম ব্যবহার করে সংক্ষিপ্ত করা যেতে পারে।

গ্রাফ তত্ত্ব গণনামূলক নিউরোসায়েন্সেও এর ব্যবহারযোগ্যতা খুঁজে পেয়েছে, যা বিভিন্ন জ্ঞানীয় প্রক্রিয়ার সাথে সম্পর্কিত মস্তিষ্কের অঞ্চলগুলির মধ্যে কার্যকরী সংযোগের প্রতিনিধিত্ব করে।

6. জীববিদ্যা

গ্রাফ তত্ত্ব জীববিজ্ঞানের বিভিন্ন প্রজাতির কথোপকথনের প্রচেষ্টায় সহায়ক ভূমিকা পালন করে যেখানে নির্দিষ্ট প্রজাতির আবাসস্থলগুলিকে নোড হিসাবে এবং তাদের স্থানান্তরের পথগুলি প্রান্ত হিসাবে উপস্থাপন করা হয়।

এটি একক-কোষ ট্রান্সক্রিপ্টোম বিশ্লেষণে কোষ-প্রকারে কোষের ক্লাস্টারিংয়ের মতো জটিল সম্পর্কের সাথে ডেটাসেটগুলির মডেলিং এবং বিশ্লেষণের ক্ষেত্রেও কার্যকর।

গ্রাফগুলি জিন বা প্রোটিনকে মডেল করতে এবং তাদের সম্পর্ক অধ্যয়ন করতেও ব্যবহৃত হয়, যেমন জিন নিয়ন্ত্রক নেটওয়ার্ক এবং বিপাকীয় পথ।

স্নায়ুতন্ত্র হল একটি নেটওয়ার্ক বা গ্রাফ যেখানে নিউরনগুলি শীর্ষবিন্দু হিসাবে এবং তাদের মধ্যে সংযোগগুলি প্রান্ত হিসাবে।

7. সামগ্রিকভাবে

আপনার কখনও কখনও শহরের রুট বা নেটওয়ার্কগুলি পর্যবেক্ষণ করা উচিত ছিল। গ্রাফগুলি সহজেই তাদের প্রতিনিধিত্ব করতে পারে।

আপনার পারিবারিক গাছ থেকে অনুক্রমিক তথ্যগুলি একটি গাছের ডেটা কাঠামো, একটি নির্দিষ্ট গাণিতিক মডেল টাইপ দ্বারাও চিত্রিত করা যেতে পারে।

আসুন বেসিক সম্পর্কে কথা বলি

গ্রাফ তত্ত্বটি গ্রাফ বা নেটওয়ার্ক ধারণার একটি অংশ যা কম্পিউটার বিজ্ঞান ধার করেছে কারণ এতে কোডিং অ্যাপ্লিকেশন রয়েছে।

আমরা গ্রাফ তত্ত্ব নিয়ে এগিয়ে যাওয়ার আগে, আসুন কিছু মৌলিক ধারণা বা মৌলিক বিষয়গুলি বুঝতে পারি।

1. পয়েন্ট

একটি বিন্দু, একটি বিন্দু দ্বারা প্রতিনিধিত্ব করা হয়, একটি অবস্থান যা একটি এক-, দুই-, ত্রিমাত্রিক স্থানে সংজ্ঞায়িত করা হয় এবং একটি বর্ণমালা দ্বারা চিহ্নিত করা হয়।

উদাহরণ স্বরূপ,

এখানে, 'x' হল বিন্দু।

2. ভার্টেক্স

এটি একাধিক লাইনের একটি মিটিং পয়েন্ট এবং এটি একটি নোড হিসাবেও পরিচিত। একটি বর্ণমালা এটিকে বোঝায়।

উদাহরণ স্বরূপ,

এখানে, 'x' হল শীর্ষবিন্দু।

3. লাইন

দুটি বিন্দুর মধ্যে সংযোগকে লাইন বলে।

উদাহরণ স্বরূপ,

এখানে ‘x’ এবং ‘y’ বিন্দু দুটির মধ্যে সংযোগকে লাইন বলে।

4. প্রান্ত

একটি প্রান্ত হল একটি পথ বা একটি লাইন যা দুটি শীর্ষবিন্দুকে সংযুক্ত করে, যথা- প্রারম্ভিক শীর্ষ এবং শেষ শীর্ষবিন্দু।

অনেক প্রান্ত গঠিত হতে পারে; এইভাবে, অন্তত একটি শীর্ষবিন্দু একটি প্রান্ত গঠন করা আবশ্যক.

উদাহরণ স্বরূপ,

এখানে, শীর্ষবিন্দু 'x' এবং 'y'-এর মধ্যে সংযোগটিকে একটি প্রান্ত বলা হয়।

5. সমান্তরাল প্রান্ত

দুটি শীর্ষবিন্দুর মধ্যে একাধিক প্রান্ত থাকলে, প্রান্তগুলি সমান্তরাল হয়।

উদাহরণ স্বরূপ,

উপরের গ্রাফে, দুটি শীর্ষবিন্দুর মধ্যে 'q' এবং 'w', দুটি প্রান্ত রয়েছে এবং এইভাবে এই প্রান্তগুলিকে সমান্তরাল প্রান্ত বলা হয়।

6. গ্রাফ

একটি গ্রাফ 'g' হল একটি নেটওয়ার্ক, বা প্রান্ত এবং নোড ব্যবহার করে গঠিত একটি গাণিতিক মডেল।

এটিকে 'G' দ্বারা চিহ্নিত করা হয়, যাকে G = (V, E) হিসাবে সংজ্ঞায়িত করা হয় যেখানে 'V' হল শীর্ষবিন্দুর সেট এবং 'E' হল প্রান্তের সেট।

উদাহরণ স্বরূপ,

উপরের নেটওয়ার্ক বা গ্রাফটিকে এর শীর্ষবিন্দু এবং প্রান্তগুলি ব্যবহার করে সংজ্ঞায়িত করা যেতে পারে, যা হল:

V= {a, b, c, d}

E = {ab, bc, cd}

7. মাল্টিগ্রাফ

একটি গ্রাফ বা নেটওয়ার্ক যাতে সমান্তরাল প্রান্ত থাকে তাকে মাল্টিগ্রাফ বলে।

উদাহরণ স্বরূপ,

উপরের নেটওয়ার্কটি একটি মাল্টিগ্রাফ কারণ এর শীর্ষবিন্দু 'b' এবং 'c' এর মধ্যে দুটি প্রান্ত রয়েছে।

8. লুপ

একটি প্রান্তের একই প্রারম্ভিক এবং শেষ শীর্ষবিন্দু থাকলে আপনি যে কাঠামোটি পান তাকে লুপ বলা হয়, অর্থাত্ এটি শীর্ষবিন্দু থেকে নিজের দিকে আঁকা একটি প্রান্ত সহ একটি গ্রাফ।

উদাহরণ স্বরূপ,

উপরের গ্রাফটিকে এর শীর্ষবিন্দু এবং প্রান্তগুলি ব্যবহার করে সংজ্ঞায়িত করা যেতে পারে, যা হল:

V= {a, b, c, d}

E= {aa, ab, bb, bc, cd, da}

লুপগুলি a এবং b শীর্ষবিন্দুতে রয়েছে।

9. সংলগ্নতা

একটি গ্রাফ বা নেটওয়ার্কের প্রান্ত এবং নোডগুলির জন্য সংলগ্নতার নিয়মগুলি আলাদা। তারা হল:

(i) যদি দুটি শীর্ষবিন্দুর মধ্যে একটি প্রান্ত উপস্থিত থাকে, তবে সেগুলি একে অপরের সংলগ্ন বা সংলগ্ন বলে বলা হয় এবং এই সংলগ্নতাটি দুটি শীর্ষবিন্দুকে সংযোগকারী একক প্রান্ত দ্বারা বজায় রাখা হয়।

(ii) যদি একটি সাধারণ শীর্ষবিন্দু দুটি প্রান্তের মধ্যে উপস্থিত থাকে, তবে প্রান্তগুলিকে সংলগ্ন বা সংলগ্ন বলা হয় এবং সেই একক শীর্ষবিন্দুটি দুটি প্রান্তের মধ্যে সংলগ্নতা বজায় রাখে।

উদাহরণ স্বরূপ,

উপরের গ্রাফে, প্রান্ত এবং শীর্ষবিন্দুগুলির সংলগ্নতাকে সংজ্ঞায়িত করা যেতে পারে:

শীর্ষবিন্দু a এবং b সংলগ্ন কারণ তারা একটি সাধারণ প্রান্ত ab দ্বারা সংযুক্ত।
শীর্ষবিন্দু c এবং d সংলগ্ন কারণ তারা একটি সাধারণ প্রান্ত cd দ্বারা সংযুক্ত।
প্রান্তগুলি ab, ac এবং ad সংলগ্ন কারণ তারা একটি সাধারণ শীর্ষবিন্দু a দ্বারা সংযুক্ত।
প্রান্তগুলি bc এবং cd সংলগ্ন কারণ তারা একটি সাধারণ শীর্ষবিন্দু c দ্বারা সংযুক্ত।

একটি গ্রাফ কি?

গ্রাফ হল ডেটা স্ট্রাকচার বা নেটওয়ার্ক যার দুটি প্রধান উপাদান রয়েছে: একটি নোড এবং একটি প্রান্ত।

নোড: একটি গ্রাফ বা নেটওয়ার্কের শীর্ষবিন্দু একটি নোড N বা শীর্ষবিন্দু V হিসাবে পরিচিত।

প্রান্ত: দুটি নোডের মধ্যে সংযোগ, বলুন u, v, একটি অনন্য জোড়া হিসাবে চিহ্নিত (u, v) একটি প্রান্ত E বা একটি আদেশযুক্ত জোড়া হিসাবে পরিচিত। কখনও কখনও গ্রাফের প্রান্তগুলি তাদের সাথে কিছু যুক্ত থাকতে পারে। বিঃদ্রঃ- সর্বদা মনে রাখবেন যে (u, v) এবং (v, u) একই নয় এবং তাই অর্ডারযুক্ত জোড়া হিসাবে পরিচিত এবং অনন্য।

একটি গ্রাফ g একটি নেটওয়ার্ক বা (V, E) সেটের একটি সচিত্র উপস্থাপনা হিসাবে বোঝা যেতে পারে, যেখানে একটি শীর্ষবিন্দু V এবং প্রান্ত Eগুলির একটি সেট রয়েছে।

উদাহরণ স্বরূপ:

এই নেটওয়ার্কে,

V বা N = {a, b, c, d, e, f}

E = {ab, bc,

গ্রাফের ধরন

1. নির্দেশিত গ্রাফ

গ্রাফ বা নেটওয়ার্ক যেগুলির প্রান্তগুলির অভিযোজন রয়েছে এবং একটি ক্রমযুক্ত জোড়া G = (V, E) হিসাবে সংজ্ঞায়িত করা হয়েছে যেখানে 'V' হল শীর্ষবিন্দুগুলির একটি সেট এবং 'E' হল প্রান্তের সেট যা শীর্ষবিন্দুগুলির ক্রমযুক্ত জোড়া নিয়ে গঠিত।

উদাহরণ স্বরূপ,

উপরের নির্দেশিত গ্রাফে, আমাদের একটি প্রান্ত (a, b) এবং শীর্ষবিন্দু a এবং b আছে। এই নোডগুলি শেষ বিন্দু হিসাবে পরিচিত যেখানে নোড 'a' হল লেজ এবং নোড 'b' হল প্রান্তের মাথা।

2. অনির্দেশিত গ্রাফ

একটি গ্রাফ বা একটি নেটওয়ার্ক যেখানে কোন সংজ্ঞায়িত দিক প্রান্ত নেই তাকে একটি অনির্দেশিত গ্রাফ বলা হয়।

অনির্দেশিত গ্রাফ G হল একটি ক্রমযুক্ত জোড়া G = (V, E), যেখানে E হল শীর্ষবিন্দুর অবিন্যস্ত জোড়ার সেট।

উদাহরণ স্বরূপ,

একটি প্রান্তে (a, b), শীর্ষবিন্দুর জোড়া a এবং b শেষবিন্দু হিসাবে পরিচিত, প্রান্তটি তাদের উপর দুটি শীর্ষবিন্দুর সাথে যুক্ত হওয়ার সাথে সাথে।

3. সাইকেল গ্রাফ

যদি 'n' শীর্ষবিন্দু সহ একটি সাধারণ গ্রাফ বা নেটওয়ার্কে 'n' দৈর্ঘ্যের 'n' প্রান্ত থাকে, তবে এই জাতীয় নেটওয়ার্ক একটি চক্র গ্রাফ হিসাবে পরিচিত।

শীর্ষবিন্দুর সংখ্যা 3 এর চেয়ে বেশি বা সমান হওয়া উচিত এবং শীর্ষবিন্দু দুটি হওয়া উচিত।

উদাহরণ স্বরূপ,

উপরের সাধারণ গ্রাফটি একটি চক্র গ্রাফ কারণ এটির 3টি প্রান্তের চেয়ে বেশি বা সমান এবং শীর্ষবিন্দুর ডিগ্রী = 2।

4. অ্যাসাইক্লিক গ্রাফ

কোন চক্র ছাড়া একটি নির্দেশিত গ্রাফ একটি নির্দেশিত অ্যাসাইক্লিক গ্রাফ বা DAG বলা হয়। একটি নেটওয়ার্ককে DAG বলা হবে যদি DAG-তে একটি শীর্ষবিন্দু ‘v’-এর কোনো নির্দেশিত প্রান্ত থাকে না হয় শুরু হয় বা শেষ হয় ‘v’-এ।

বিঃদ্রঃ: এটি নির্দেশিত এবং অনির্দেশিত উভয়ই হতে পারে।

উদাহরণ স্বরূপ,

উপরের চিত্রে, কোন চক্র নেই, তাই গ্রাফটি অ্যাসাইক্লিক বা অ-চক্রীয়।

5. চক্রীয় গ্রাফ

অ্যাসাইক্লিক গ্রাফের বিপরীতে, একটি অ্যাসাইক্লিক গ্রাফ হল এমন একটি নেটওয়ার্ক যার অন্তত একটি চক্র থাকে।

উদাহরণ স্বরূপ,

উপরের উভয় গ্রাফে, প্রান্তগুলি একটি চক্র গঠন করে, যার মানে হল নেটওয়ার্কটি চক্রাকারে।

6. সংযুক্ত গ্রাফ

যখন প্রতিটি জোড়া শিরোনামের মধ্যে একটি সংজ্ঞায়িত পথ থাকে এবং কোন নোডের কাছে পৌঁছানো যায় না, তখন গ্রাফ বা নেটওয়ার্কটিকে একটি সংযুক্ত গ্রাফ বলা হয়।

সংযুক্ত গ্রাফগুলিতে, নেটওয়ার্কের প্রতিটি দুটি শীর্ষবিন্দুর মধ্যে কমপক্ষে একটি প্রান্ত থাকা উচিত।

উদাহরণ স্বরূপ,

উপরের নেটওয়ার্কটি সংযুক্ত কারণ সমস্ত শীর্ষবিন্দু সংজ্ঞায়িত প্রান্তগুলির মাধ্যমে সংযুক্ত।

7. সংযোগ বিচ্ছিন্ন গ্রাফ

একটি সংযুক্ত গ্রাফের বিপরীতে, একটি সংযোগ বিচ্ছিন্ন নেটওয়ার্ক বা গ্রাফ তৈরি হয় যখন কমপক্ষে দুটি শীর্ষবিন্দু সংযুক্ত থাকে না।

উদাহরণ স্বরূপ,

উপরের নেটওয়ার্কটি একটি সংযোগ বিচ্ছিন্ন গ্রাফ কারণ দুটি শীর্ষবিন্দু সংযুক্ত নয়৷

8. সম্পূর্ণ গ্রাফ

একটি সম্পূর্ণ গ্রাফ ‘g’-এ, প্রতিটি নোড ‘x’ প্রতিটি নোড ‘y’-এর সংলগ্ন থাকে যাতে প্রতিটি জোড়া শীর্ষবিন্দুর মধ্যে একটি প্রান্ত থাকে।

সম্পূর্ণ গ্রাফটিতে 'n' পারস্পরিক শীর্ষবিন্দু থাকবে এবং 'Kn' দ্বারা চিহ্নিত করা হয়।

উদাহরণ স্বরূপ,

শীর্ষবিন্দু	প্রতি	খ	গ	d
প্রতি	সংযোগ বিচ্ছিন্ন	সংযুক্ত	সংযুক্ত	সংযুক্ত
খ	সংযুক্ত	সংযোগ বিচ্ছিন্ন	সংযুক্ত	সংযুক্ত
গ	সংযুক্ত	সংযুক্ত	সংযোগ বিচ্ছিন্ন	সংযুক্ত
d	সংযুক্ত	সংযুক্ত	সংযুক্ত	সংযোগ বিচ্ছিন্ন

উপরের চিত্রে গ্রাফটি সম্পূর্ণ কারণ এর সমস্ত শীর্ষবিন্দু অন্যান্য শীর্ষবিন্দুর সাথে সংযুক্ত।

9. দ্বিসংযুক্ত গ্রাফ

কোন উচ্চারণ বিন্দু ছাড়া একটি গ্রাফকে পরবর্তী অংশে বিভক্ত করা যাবে না যাকে দ্বিসংযুক্ত গ্রাফ বলা হয়।

এইভাবে, দ্বিসংযুক্ত গ্রাফগুলিকে সংযোগ বিচ্ছিন্ন করা যাবে না এমনকি যদি একটি শীর্ষবিন্দু সরানো হয়।

উদাহরণ স্বরূপ,

উপরের গ্রাফ G-এ, আমরা দেখতে পাচ্ছি যে উপরের গ্রাফ থেকে আমরা একটি শীর্ষবিন্দুকে সরিয়ে দিলেও এটি সংযুক্ত থাকবে।

10. নাল গ্রাফ

কোন প্রান্তবিহীন গ্রাফকে নাল গ্রাফ বলা হয়।

উদাহরণ স্বরূপ,

উপরের চিত্রে, চারটি শীর্ষবিন্দু আছে কিন্তু কোন প্রান্ত তাদের সংযুক্ত করছে না। সুতরাং, এটি একটি নাল গ্রাফ।

11. তুচ্ছ গ্রাফ

যে গ্রাফটি শুধুমাত্র একটি শীর্ষবিন্দু দিয়ে তৈরি এবং কোন প্রান্ত নেই তাকে তুচ্ছ গ্রাফ বলে। এটি একটি সমতলে একটি বিন্দু।

উদাহরণ স্বরূপ,

উপরের চিত্রে, শীর্ষবিন্দু 'q' একটি তুচ্ছ গ্রাফ নির্দেশ করে।

12. সরল গ্রাফ

যদি একটি গ্রাফের কোন লুপ না থাকে এবং কোন সমান্তরাল প্রান্ত না থাকে, তাহলে এই ধরনের গ্রাফ একটি সাধারণ গ্রাফ হিসাবে পরিচিত।

এই গ্রাফগুলির জন্য, যদি 'n' শীর্ষবিন্দু থাকে, তাহলে সর্বাধিক nC2 প্রান্ত থাকতে পারে এবং 2^(nC2) গ্রাফ সম্ভব, যেখানে nC2 = n(n-1)/2।

উদাহরণ স্বরূপ,

উপরের চিত্রটিতে চারটি শীর্ষবিন্দু এবং তিনটি প্রান্ত রয়েছে এবং কোন লুপ বা সমান্তরাল প্রান্ত নেই।

এখানে যদি আমরা দেখি,

তারপর n=4 সহ আমাদের nC2 এর সূত্র অনুসারে, আমরা দেখতে পাচ্ছি যে প্রান্তের সর্বাধিক সংখ্যা হল,

nC2 = n(n-1)/2

= 4(4-1)/2 = 6

এছাড়াও, 4টি শীর্ষবিন্দু সহ সর্বাধিক সংখ্যক গ্রাফ সম্ভব,

2^(nC2) = 2^4 = 16

কেন আপনি চেষ্টা করবেন না এবং সেই 16টি গ্রাফ তৈরি করুন এবং দেখুন সূত্রটি সঠিক কিনা?

এটা মজা হবে.

13. নিয়মিত গ্রাফ

যদি সমস্ত গ্রাফের শীর্ষবিন্দু একই ডিগ্রি থাকে, তবে এই ধরনের গ্রাফকে নিয়মিত গ্রাফ বলা হয়।

গ্রাফের ডিগ্রী তার নাম সংজ্ঞায়িত করে, যেমন, একটি 'k' শীর্ষবিন্দু গ্রাফ যাকে 'k-রেগুলার গ্রাফ' বলা হয়।

উদাহরণ স্বরূপ,

উপরের গ্রাফে, সমস্ত শীর্ষবিন্দুর একই ডিগ্রি = 2 এবং এইভাবে একটি নিয়মিত গ্রাফ।

14. হুইল গ্রাফ

যখন একটি নতুন শীর্ষবিন্দু, একটি হাব বলা হয়, একটি চক্র গ্রাফ Cn-1 এ যোগ করা হয়, তখন একটি চাকা গ্রাফ পাওয়া যায়, Wn দ্বারা চিহ্নিত করা হয়।

এই হাবটি Cn এর সমস্ত শীর্ষবিন্দুর সাথে সংযুক্ত।

একটি চাকা গ্রাফে প্রান্তের মোট সংখ্যা গণনা করতে আমাদের আছে,

প্রান্তের সংখ্যা = হাব থেকে অন্যান্য শীর্ষবিন্দুতে যাওয়া প্রান্তের সংখ্যা + হাব ছাড়া একটি চক্রে অন্যান্য সমস্ত নোড থেকে বেশ কয়েকটি প্রান্ত যাচ্ছে৷

=(n-1) + (n-1)

=2(n-1)

উদাহরণ স্বরূপ,

উপরের গ্রাফে, একটি কেন্দ্রীয় শীর্ষবিন্দু 'e' চক্র গ্রাফের অন্যান্য শীর্ষবিন্দুর সাথে সংযুক্ত। সুতরাং, এটি একটি চাকা গ্রাফ।

15. দ্বিপক্ষীয় গ্রাফ

যদি একটি গ্রাফে G = (V, E), সেট E-এর প্রতিটি প্রান্ত সেট V1-এর একটি শীর্ষবিন্দুর সাথে সেট V2-এর অন্য শীর্ষবিন্দুতে যোগ দেয়, তাহলে গ্রাফটিকে একটি দ্বিপক্ষীয় গ্রাফ শীর্ষবিন্দু বিভাজন V = (V1, V2) বলা হয়।

এইভাবে, আমরা বলতে পারি যে একটি দ্বিপাক্ষিক গ্রাফে, প্রতিটি প্রান্ত একটি ভিন্ন শীর্ষবিন্দু থেকে দুটি শীর্ষবিন্দুতে যোগ দেয়।

উদাহরণ স্বরূপ,

উপরের গ্রাফে, প্রান্তটি একটি ক্রসক্রসড পদ্ধতিতে দুটি শীর্ষবিন্দুর সাথে মিলিত হয়েছে।

16. সম্পূর্ণ দ্বিপক্ষীয় গ্রাফ

একটি সাধারণ দ্বিপক্ষীয় গ্রাফের বিপরীতে, V1 এবং V2 উভয় শীর্ষবিন্দু থেকে প্রতিটি শীর্ষবিন্দু একটি সম্পূর্ণ দ্বিপক্ষীয় গ্রাফে একটি প্রান্ত দ্বারা সংযুক্ত থাকে।

যাইহোক, মনে রাখবেন যে একটি সম্পূর্ণ দ্বিপক্ষীয় গ্রাফ একটি সম্পূর্ণ গ্রাফ নয় এবং বিভ্রান্ত হওয়া উচিত।

একটি সম্পূর্ণ দ্বিপক্ষীয় গ্রাফ কে (a, b) দ্বারা প্রতিনিধিত্ব করা হয়, যেখানে a হল V1 তে শীর্ষবিন্দুর সংখ্যা এবং b হল V2 তে শীর্ষবিন্দুর সংখ্যা।

এইভাবে, এটি উপসংহারে পৌঁছানো যেতে পারে যে গ্রাফ, K (a, b) এর মোট 'ab' প্রান্ত সংযুক্ত (a+b) শীর্ষবিন্দু রয়েছে, যা একটি নিয়মিত গ্রাফের মতো করা যেতে পারে যদি, a=b হয়।

উদাহরণ স্বরূপ,

প্রতিটি শীর্ষবিন্দুর মধ্যে একটি প্রান্ত রয়েছে যা দুটি শীর্ষবিন্দুকে একে অপরের সাথে সংযুক্ত করে।

17. তারকা গ্রাফ

K (1, n-1) দ্বারা চিহ্নিত স্টার গ্রাফ হল একটি দ্বিপক্ষীয় গ্রাফের একটি বিশেষ ক্ষেত্রে যেখানে V1 তে একটি শীর্ষবিন্দু এবং V2 তে (n-1) শীর্ষবিন্দু রয়েছে বা এর বিপরীতে।

অন্য কথায়, একটি সম্পূর্ণ দ্বিপক্ষীয় গ্রাফ যেখানে একটি সেট থেকে সমস্ত শীর্ষবিন্দু একটি একক শীর্ষবিন্দুর সাথে সংযুক্ত থাকে তাকে তারা গ্রাফ বলে।

উদাহরণ স্বরূপ,

উপরের চিত্রে, সমস্ত শীর্ষবিন্দু একই শীর্ষবিন্দুতে একত্রিত হয় বা মিলিত হয়। এটি একটি তারার গ্রাফ যেখানে শীর্ষবিন্দু V1 = {a} এবং V2 = {p, q, r, s}।

18. একটি গ্রাফের পরিপূরক

আমরা জানি যে একটি গ্রাফে প্রান্ত এবং শীর্ষবিন্দু (V, E) থাকে।

একটি গ্রাফের একটি পরিপূরক 'G-' হল একটি গ্রাফ যেখানে একটি গ্রাফ হিসাবে সমস্ত শীর্ষবিন্দু রয়েছে, কিন্তু প্রান্তগুলি শুধুমাত্র সেইগুলি হবে যারা গ্রাফে অনুপস্থিত।

এইভাবে, যদি দুটি গ্রাফে একটিতে উপস্থিত প্রান্তগুলি অন্যটির সাথে একই রকম না হয়, অর্থাৎ, উভয়ের একই সেট এবং শীর্ষবিন্দুর প্রান্তিককরণ থাকে, উভয় গ্রাফ একটি পরিপূরক হিসাবে পরিচিত।

দুটি সন্নিহিত গ্রাফ একত্রিত করে একটি সম্পূর্ণ গ্রাফ তৈরি করা যেতে পারে।

এইভাবে,

E (G1) + |E (G2) | = |ই (জি) |,

যেখানে G1 এবং G1 হল পরিপূরক গ্রাফ এবং G হল সম্পূর্ণ গ্রাফ।

উদাহরণ স্বরূপ,

উপরের গ্রাফগুলিতে, আমরা দেখতে পাচ্ছি যে গ্রাফ ‘I’ এবং গ্রাফ ‘II’ একে অপরের পরিপূরক কারণ তাদের একই প্রান্ত নেই কিন্তু একই শীর্ষবিন্দু রয়েছে। এছাড়াও, মার্জ করার সময়, আমরা একটি সম্পূর্ণ গ্রাফ পাই।

গাছ এবং বন

এখন যেহেতু আমরা গ্রাফ এবং তাদের প্রকারগুলি বুঝতে পেরেছি, আসুন দ্রুত গাছ এবং বন এবং কিভাবে তারা একটি গ্রাফ হয় তা দেখি।

প্রথমে আমরা গাছ সম্পর্কে দেখব।

গাছ

গাছ হল অ্যাসাইক্লিক এবং সীমাবদ্ধতা সহ সংযুক্ত গ্রাফ। সবচেয়ে গুরুত্বপূর্ণ সীমাবদ্ধতা হল একটি চাইল্ড নোডে শুধুমাত্র একটি প্যারেন্ট নোড থাকতে পারে।

আমরা আগে পড়েছি, একটি গাছ সবসময় একটি গ্রাফ হয়, কিন্তু একটি গ্রাফ একটি গাছ নাও হতে পারে।

বৃক্ষ হল বিশেষ নেটওয়ার্ক বা গ্রাফ যা একটি গাণিতিক মডেলে অনুক্রমিক কাঠামোর প্রতিনিধিত্ব করে এবং একটি সমৃদ্ধ কাঠামোর সাথে সহজতম গ্রাফ হিসাবে শ্রেণীবদ্ধ করা হয়।

এটি একটি কম্পিউটার বিজ্ঞান সমস্যার পারিবারিক গাছ হোক, গাছগুলি বেশ কার্যকর প্রমাণিত হয়েছে।

গাছ সম্পর্কিত কয়েকটি সংজ্ঞা রয়েছে:

1. রুট নোড: গাছের শীর্ষস্থানীয় নোড বা শীর্ষবিন্দুকে রুট নোড বলে। এই নোড থেকে গাছগুলি তাদের শ্রেণীবদ্ধ গঠন শুরু করে।

2. লিফ নোড: যে নোডগুলি বাচ্চা নেই এবং গাছের শেষ নোডগুলিকে লিফ নোড বলে।

3. চাইল্ড নোড: যে নোডগুলি রুট নোড বা লিফ নোড নয় তাদেরকে চাইল্ড নোড বলে। তারা আরও চাইল্ড নোড সহ রুট নোডের বংশধর।

4. শাখা: বিভিন্ন নোডের সাথে সংযোগকারী গাছের প্রান্তগুলিকে শাখা বলা হয়।

গাণিতিকভাবে, যদি একটি গাছের 'n' নোড থাকে, তবে এর 'n-1' প্রান্ত থাকে।

যদি প্রান্তগুলি 'n' হয়ে যায়, তবে এটিকে দুটি শীর্ষবিন্দুর সাথে যুক্ত করতে হবে, একটি চক্রীয় গ্রাফের জন্ম দেবে এবং গাছগুলি কখনই চক্রাকার হতে পারে না।

উদাহরণ স্বরূপ,

উপরের নেটওয়ার্কটি অ্যাসাইক্লিক প্রান্ত সহ একটি শ্রেণিবদ্ধ কাঠামো। এটি একটি গাছ।

রুট নোড: প্রতি

চাইল্ড নোড: খ, গ, ঘ

সীসা নোড: e, f, g, h

শাখা: ab, bc, bd, ce, cf, dg, dh

বিস্তৃত গাছ

যদি একটি সংযুক্ত গ্রাফের উপ-গ্রাফ একটি বৃক্ষ গঠন করে, তাকে একটি স্প্যানিং ট্রি বলে।

একটি সাব-গ্রাফ একটি বিস্তৃত গাছ হতে, দুটি শর্ত সন্তুষ্ট করা প্রয়োজন:

(i) এটি একটি গাছ হওয়া উচিত

(ii) গ্রাফের সমস্ত শীর্ষবিন্দু উপস্থিত থাকতে হবে।

উদাহরণ স্বরূপ,

উপরের গ্রাফগুলিতে X এবং Y, X হল একটি সংযুক্ত গ্রাফ, এবং Y হল X-এর একটি সাব-গ্রাফ, যেটি একটি গাছ কারণ এটির কোন চক্র নেই৷ এইভাবে, Y একটি বিস্তৃত গাছ।

সার্কিট র‍্যাঙ্ক

একটি স্প্যানিং ট্রি পেতে একটি সংযুক্ত গ্রাফ থেকে যে প্রান্তগুলি মুছে ফেলতে হবে তাকে সংযুক্ত গ্রাফের সার্কিট র‍্যাঙ্ক বলে।

ধরুন একটি সংযুক্ত গ্রাফ ‘G’-তে ‘v’ শীর্ষবিন্দু এবং ‘e’ প্রান্ত রয়েছে যেখান থেকে (v-1) প্রান্তের একটি বিস্তৃত গাছ তৈরি হয়েছে।

যেহেতু একটি বিস্তৃত গাছে 'v-1' প্রান্ত থাকে, তাই আমাদেরকে সেই অনেকগুলি প্রান্তকে 'e'-এর বাইরে রাখতে হবে যাতে কোনো চক্রবিহীন একটি প্রসারিত গাছ তৈরি হয়।

এইভাবে, সংযুক্ত গ্রাফের সার্কিট র‍্যাঙ্ক = e – (v-1)।

উদাহরণ স্বরূপ,

উপরের স্প্যানিং ট্রি উদাহরণে, সংযুক্ত গ্রাফ X, আছে

প্রান্তের সংখ্যা = 12টি

শীর্ষবিন্দুর সংখ্যা = 11টি

এইভাবে, সার্কিট র‌্যাঙ্ক = প্রান্তের সংখ্যা – (উল্লম্বের সংখ্যা – 1)

= 12 – (11 – 1)

= 2

অতএব, আমরা যে স্প্যানিং ট্রি পেয়েছি, অর্থাৎ গ্রাফ Y সঠিক।

কির্চফের উপপাদ্য

আপনি যদি একটি সংযুক্ত গ্রাফ থেকে গঠিত হতে পারে এমন বিস্তৃত গাছের সংখ্যা খুঁজে বের করতে চান, তাহলে কির্চফের উপপাদ্যটি ব্যবহার করা যেতে পারে।

উপপাদ্য, যা কেলির সূত্রের একটি সাধারণীকরণ, বলে যে একটি সংযুক্ত গ্রাফ থেকে স্প্যানিং-ট্রির সংখ্যা ল্যাপ্লাসিয়ান নির্ধারক ম্যাট্রিক্স ব্যবহার করে বহুপদী সময়ে গণনা করা যেতে পারে।

একটি গ্রাফের ল্যাপ্লাসিয়ান ম্যাট্রিক্স গ্রাফের ডিগ্রি ম্যাট্রিক্স এবং এর সংলগ্ন ম্যাট্রিক্সের মধ্যে পার্থক্যের সমান।

উদাহরণ স্বরূপ,

উপরের চিত্রটি বিবেচনা করুন।

এখানে ম্যাট্রিক্স এল ম্যাট্রিক্সে উপস্থিত বা অনুপস্থিত প্রান্তগুলি যথাক্রমে 1s এবং 0s ব্যবহার করে পূরণ করা যেতে পারে, অর্থাৎ, যদি একটি প্রান্ত উপস্থিত থাকে তবে 1 এবং অনুপস্থিত থাকলে 0।

0	প্রতি	খ	গ	d
প্রতি	0	এক	0	এক
খ	এক	0	এক	এক
গ	0	এক	0	এক
d	এক	এক	এক	0

সরলীকরণে আমরা পাই:

0	এক	0	এক
এক	0	এক	এক
0	এক	0	এক
এক	এক	এক	0

Kirchoff এর উপপাদ্য ব্যবহার করে, উপরের ম্যাট্রিক্সের প্রধান কর্ণটি শীর্ষবিন্দুর ডিগ্রি দ্বারা প্রতিস্থাপিত হবে, এবং বাকি পদগুলিকে -1 দ্বারা গুণ করা হবে।

দুই	-এক	0	-এক
-এক	3	-এক	-এক
0	-এক	দুই	-এক
-এক	-এক	-এক	3

সারি 1 এবং কলাম 1 অপসারণ করার সময়, আমরা পাই,

3	-এক	-এক
-এক	দুই	-এক
-এক	-এক	3

উপরের ম্যাট্রিক্সের নির্ধারক = 8।

এভাবে ৮টি স্প্যানিং গাছ সম্ভব হবে।

বন। জংগল

আমরা যদি বনের ইংরেজি অভিধানের সংজ্ঞায় যাই, তাহলে একে গাছের সংগ্রহ বলা যেতে পারে।

গ্রাফ তত্ত্বের ক্ষেত্রেও একই কথা সত্য।

একটি সংযোগ বিচ্ছিন্ন অ্যাসাইক্লিক গ্রাফ, বিভিন্ন গাছের একটি বিচ্ছিন্ন সংগ্রহ, একটি বন হিসাবে পরিচিত।

উদাহরণ স্বরূপ,

আমরা যদি উপরের দুটি গ্রাফের দিকে তাকাই, আমরা দেখতে পাব যে এগুলি একক সংযোগ বিচ্ছিন্ন বা বিচ্ছিন্ন গ্রাফ যার কোনো চক্র নেই। সুতরাং, এটি একটি বন।

ভার্টেক্স ডিগ্রী

একটি শীর্ষবিন্দু 'X'-এর সংলগ্ন শীর্ষবিন্দুর মোট সংখ্যাকে একটি শীর্ষবিন্দুর ডিগ্রি বলা হয় এবং deg(V) দ্বারা চিহ্নিত করা হয়,

আপনি (v)<= n-1 where, v belongs to G.

যেহেতু একটি শীর্ষবিন্দু নিজেই ব্যতীত একটি গ্রাফে অন্য সমস্ত শীর্ষবিন্দুর সাথে প্রান্ত তৈরি করতে পারে, তাই শীর্ষবিন্দুর ডিগ্রি সেই গ্রাফের মোট শীর্ষবিন্দুর সর্বোচ্চ - 1 হতে পারে।

শীর্ষবিন্দুর ডিগ্রির উপর নির্ভর করে, দুটি ধরণের শীর্ষবিন্দু রয়েছে:

(i) পেন্ডেন্ট শীর্ষবিন্দু

একটি শীর্ষবিন্দুর ডিগ্রী 1 হলে, তাকে পেন্ডেন্ট শীর্ষবিন্দু বলে। এই ধরনের শীর্ষবিন্দুর শুধুমাত্র একটি প্রান্ত থাকে যা তাদের একটি অন্য শীর্ষবিন্দুর সাথে সংযুক্ত করে।

উদাহরণ স্বরূপ,

উপরের চিত্রে শীর্ষবিন্দুটি একটি পেন্ডেন্ট শীর্ষবিন্দু কারণ এটির দিকে কেবল একটি প্রান্ত রয়েছে। সুতরাং, এটি একটি পেন্ডেন্ট শীর্ষবিন্দু।

(ii) বিচ্ছিন্ন ভার্টেক্স

একটি শীর্ষবিন্দুর ডিগ্রী 0 হলে, তাকে একটি বিচ্ছিন্ন শীর্ষবিন্দু বলে। এই ধরনের শীর্ষবিন্দুর কোন প্রান্ত নেই যা তাদের অন্য শীর্ষবিন্দুর সাথে সংযুক্ত করে।

উদাহরণ স্বরূপ,

উপরের চিত্রে, শীর্ষবিন্দুটি বিচ্ছিন্ন হয়েছে কারণ এটি থেকে কোন প্রান্ত যাচ্ছে না। সুতরাং, এটি একটি বিচ্ছিন্ন শীর্ষবিন্দু।

নীচের দুটি গ্রাফের উপর নির্ভর করে, শীর্ষবিন্দুর ডিগ্রী ভিন্ন হয়:

(i) নির্দেশিত গ্রাফ

(ii) অনির্দেশিত গ্রাফ

1. ভার্টেক্সের ডিগ্রী - অনির্দেশিত গ্রাফ

আসুন একটি উদাহরণ ব্যবহার করে এটি বুঝতে পারি:

নিচের গ্রাফটি বিবেচনা করুন,

এই গ্রাফে, 5টি শীর্ষবিন্দু রয়েছে। এখন, প্রতিটি শীর্ষবিন্দুর জন্য ডিগ্রী হবে:

deg (a) = 2

deg (b) = 3

deg (c) = 3

ডিগ্রী (d) = 2

ডিগ্রী (ই) = 3

2. শীর্ষবিন্দুর ডিগ্রী - নির্দেশিত গ্রাফ

নির্দেশিত প্রান্ত বিশিষ্ট একটি গ্রাফকে নির্দেশিত গ্রাফ বলা হয়। এই গ্রাফে, প্রতিটি শীর্ষে রয়েছে:

(i) অসম্পূর্ণ: এগুলি শীর্ষবিন্দু 'A' এর দিকে আসা প্রান্তের সংখ্যা এবং deg-(A) দ্বারা চিহ্নিত করা হয়।

(ii) আউটডিগ্রি: এগুলি শীর্ষবিন্দু 'A' থেকে যাওয়া প্রান্তের সংখ্যা এবং deg+(A) দ্বারা চিহ্নিত করা হয়।

উদাহরণ স্বরূপ,

নীচের নির্দেশিত গ্রাফ বিবেচনা করে,

শীর্ষবিন্দু, V = {a, b, c}

প্রান্ত, E = {ba, da, cb, cd, db}

আসুন এর প্রতিটি শীর্ষবিন্দুর জন্য indegree এবং outdegree গণনা করি:

অসম্পূর্ণ

(i) ডিগ্রি- (a) = 2

(ii) ডিগ্রি- (খ) = 2

(iii) ডিগ্রি- (গ) = 0

(iv) deg- (d) = 1

আউটডিগ্রি

(i) deg+(a) = 0

(ii) ডিগ্রি+(খ) = 1

(iii) deg+(c) = 2

(iv) deg+(d) = 2

একটি গ্রাফের ডিগ্রী ক্রম

যদি একটি গ্রাফের সমস্ত শীর্ষবিন্দুর ডিগ্রীর বিন্যাস হয় আরোহী বা অবতরণ হয়, তবে প্রাপ্ত ক্রম বা ক্রমকে সেই গ্রাফের ডিগ্রি ক্রম বলা হয়।

উদাহরণ স্বরূপ,

উপরের চিত্রে, দ

শীর্ষবিন্দু V = {a, b, c, d}

Edges E = {ab, bc, cd, de, ec, eb, ea}

প্রতিটি শীর্ষবিন্দুর ডিগ্রী হল:

deg (a) = 2

deg (b) = 3

deg (c) = 3

ডিগ্রী (d) = 2

ডিগ্রী (ই) = 4

এইভাবে, শীর্ষবিন্দু {a, d, b, c, e} ঊর্ধ্ব ক্রমে ডিগ্রী ক্রম হল: {2, 2, 3, 3, 4}

এবং শীর্ষবিন্দু {e, b, c, a, d} অবরোহ ক্রমে ডিগ্রী ক্রম হল: {4, 3, 3, 2, 2}

শীর্ষবিন্দু উপপাদ্যের ডিগ্রীর যোগফল

একটি অ-নির্দেশিত গ্রাফ = (V, E) শীর্ষবিন্দু সহ V = {V1, V2, ...., Vn}, শীর্ষবিন্দুগুলির ডিগ্রির সমষ্টি হবে

n Σ i = 1 ডিগ্রি (V_i) = 2 * | ই |

করলারি 1

একটি অ-নির্দেশিত গ্রাফে, এমনকি বেশ কয়েকটি শীর্ষবিন্দু রয়েছে যার একটি বিজোড় ডিগ্রি রয়েছে।

ফলাফল 2

n Σ i = 1 ডিগ্রি + (V_i) = | ই | = n Σ i = 1 ডিগ্রি- (V_i)

ফলাফল 3

একটি অ-নির্দেশিত গ্রাফে, যদি প্রতিটি শীর্ষবিন্দুর ডিগ্রী, deg(V)<= k then,

কে | ভি |<= 2|E|

ফলাফল 4

একটি অ-নির্দেশিত গ্রাফে, যদি প্রতিটি শীর্ষবিন্দুর ডিগ্রী, deg(V) = k তাহলে,

কে | ভি | = 2 | ই |

ফলাফল 5

একটি অ-নির্দেশিত গ্রাফে, যদি প্রতিটি শীর্ষবিন্দুর ডিগ্রী, deg(V) >= k তাহলে,

কে | ভি | > = 2 | ই |

রং করা

এক সময় বা অন্য সময়ে, আমরা সবাই সহজ রেফারেন্স এবং বোঝার জন্য আমাদের গুরুত্বপূর্ণ নোটগুলিকে লেবেল করতে রঙিন স্টিকি নোট ব্যবহার করেছি।

আমরা সবাই নিশ্চয়ই টিভি সিরিজে এবং বিভিন্ন রঙের মুভি ম্যাপিং নেটওয়ার্কে গোয়েন্দাদের দেখেছি।

একই গ্রাফ তত্ত্বের গ্রাফের রঙের জন্য যায়।

গ্রাফে রঙ করা বিভিন্ন গ্রাফিকাল উপাদান যেমন গ্রাফিকাল নেটওয়ার্কে প্রান্ত, সীমাবদ্ধ অঞ্চল এবং শীর্ষবিন্দু লেবেল করার একটি বাস্তবসম্মত উপায়।

একটি গ্রাফ রঙ করার জন্য, বিভিন্ন সীমাবদ্ধতা যেমন গ্রাফের রঙের সেট, রঙ নির্ধারণের পদ্ধতি এবং রঙের ক্রম ইত্যাদি মাথায় রাখতে হবে।

একই রঙের শীর্ষবিন্দুগুলি স্বাধীন সেটের অংশ।

একটি উপযুক্ত ক্রোম্যাটিক সংখ্যা সহ একটি রঙিন গ্রাফকে সঠিকভাবে রঙিন গ্রাফ বলা হয়।

রঙিন সংখ্যা: একটি নিয়ম হিসাবে, কোন দুটি সংলগ্ন শীর্ষবিন্দু, প্রান্ত বা অঞ্চলকে ন্যূনতম সংখ্যক রঙ দিয়ে রঙ করা যায় না যা ক্রোম্যাটিক সংখ্যা হিসাবে পরিচিত এবং C(G) দ্বারা চিহ্নিত করা হয়।

এটিকে গ্রাফ রঙ করার জন্য প্রয়োজনীয় ন্যূনতম সম্ভাব্য সংখ্যক রঙ হিসাবে সংজ্ঞায়িত করা যেতে পারে।

প্রান্তবিহীন একটি গ্রাফের জন্য, ক্রোম্যাটিক হবে 1, যেখানে অন্যদের জন্য, এটি 2-এর থেকে বড় বা সমান হবে৷

উদাহরণ স্বরূপ,

এখানে কোন সংলগ্ন শীর্ষবিন্দু একই রঙের নয়। এছাড়াও, যেহেতু গ্রাফটিতে 3টি রঙ ব্যবহার করা হয়েছে, তাই বর্ণের সংখ্যাটি হবে: 3

1. ভার্টেক্স রঙ

একটি গ্রাফের শীর্ষবিন্দুতে রঙের বরাদ্দ যাতে কোন সংলগ্ন শীর্ষবিন্দু নেই, অর্থাত্, একটি আদর্শ প্রান্তের শীর্ষবিন্দুতে একই রঙ থাকে সেটিকে ভার্টেক্স কালারিং বলা হয়।

2. অঞ্চল রঙ

একটি সমতলে বিভিন্ন অঞ্চলে বিভিন্ন রঙের বরাদ্দ যাতে কোনও দুটি সংলগ্ন অঞ্চল, অর্থাৎ, একই প্রান্তের অঞ্চলগুলিতে অঞ্চলের রঙের মতো একই রঙ থাকে না।

উদাহরণ স্বরূপ,

নীচের গ্রাফে, সবুজ এবং নীল অঞ্চলগুলিকে সংলগ্ন বলা হয়েছে কারণ তাদের মধ্যে একটি সাধারণ প্রান্ত 'ac' রয়েছে।

সুতরাং, গ্রাফটি নিম্নরূপ রঙিন করা যেতে পারে:

গ্রাফ রঙের অ্যাপ্লিকেশন

গ্রাফ তত্ত্বের অপরিহার্য অ্যাপ্লিকেশনগুলির মধ্যে একটি হওয়ায়, অনেক রিয়েল-টাইম অ্যাপ্লিকেশন এটি ব্যবহার করে।

এটি প্রাথমিকভাবে কম্পিউটার বিজ্ঞানে নিম্নরূপ ব্যবহৃত হয়:

চিত্র বিভাজন
প্রক্রিয়া নির্ধারণ
ক্লাস্টারিং
ছবি ক্যাপচারিং
সম্পদ বণ্টন
ডেটা মাইনিং
নেটওয়ার্কিং

সংযোগ

একটি গ্রাফকে এক শীর্ষ থেকে অন্য শীর্ষে যাওয়ার জন্য, গ্রাফটি অবশ্যই সংযুক্ত থাকতে হবে।

একটি গ্রাফ সংযুক্ত বা সংযোগ বিচ্ছিন্ন কিনা তা নির্ধারণ করতে, আমাদের এর সংযোগ পরীক্ষা করতে হবে, যা প্রান্ত এবং শীর্ষবিন্দুর জন্য আলাদা।

সংযুক্ত গ্রাফের সংজ্ঞা থেকে, আমরা জানি যে যদি একটি গ্রাফের প্রতিটি শীর্ষবিন্দুর মধ্যে একটি প্রান্ত থাকে তবে তাকে একটি সংযুক্ত গ্রাফ বলা হয়।

এইভাবে, যদি গ্রাফের প্রতিটি শীর্ষবিন্দু অতিক্রম করার জন্য একটি পথ বা লিঙ্ক থাকে তবে এটিকে গ্রাফের সংযোগ বলা হয়।

অন্যদিকে, গ্রাফে একাধিক সংযোগ বিচ্ছিন্ন প্রান্ত এবং শীর্ষবিন্দু থাকলে সংযোগ বিচ্ছিন্ন সহ একটি গ্রাফ।

উদাহরণ স্বরূপ,

উপরের গ্রাফে, সমস্ত শীর্ষবিন্দু একে অপরের সাথে সংযুক্ত কারণ প্রতিটি শীর্ষবিন্দুর মধ্যে একটি প্রান্ত রয়েছে।

শীর্ষবিন্দু কাটা

একটি সংযুক্ত গ্রাফে 'G', যদি কেউ 'G-V' মুছে দেয় বা কেটে দেয়, আমরা একটি সংযোগ বিচ্ছিন্ন গ্রাফ পাই, তাহলে G এর অন্তর্গত V শীর্ষবিন্দুটিকে কাটা শীর্ষ বলে।

একটি 'n' শীর্ষবিন্দু গ্রাফে সর্বাধিক (n-2) কাটা শীর্ষবিন্দু থাকতে পারে।

উদাহরণ স্বরূপ,

এই গ্রাফে, c এবং e শীর্ষবিন্দুগুলি কাটা শীর্ষবিন্দু।

ভার্টেক্স সংযোগ

ভার্টেক্স কানেক্টিভিটি সংজ্ঞায়িত করা হয় ন্যূনতম সংখ্যক শিরোনাম অপসারণ করার জন্য যাতে একটি সংযুক্ত গ্রাফ একটি সংযোগ বিচ্ছিন্ন গ্রাফে রূপান্তরিত হয়।

এটি K(G) দ্বারা চিহ্নিত করা হয় এবং যেকোনো সংযুক্ত গ্রাফ G-এর জন্য,

K (G) ≤ ƛ (G) ≤ δ (G) ………… (i)

কোথায়,

K(G) = ভার্টেক্স সংযোগ

ƛ(G) = প্রান্ত সংযোগ

δ(G) = G ডিগ্রীর ন্যূনতম সংখ্যা

উদাহরণ স্বরূপ,

উপরের গ্রাফ g এ, যদি আমরা শীর্ষবিন্দু d এবং c মুছে ফেলি, তাহলে একটি সংযোগ বিচ্ছিন্ন গ্রাফ তৈরি হবে।

এখানে,

δ (G) = 2

প্রান্ত 'ce' এবং 'ad' মুছে দিলে একটি সংযোগ বিচ্ছিন্ন গ্রাফ পাওয়া যায়, এইভাবে ƛ(G) = 2

সমীকরণ (i) এ δ(G) এবং ƛ(G) এর মান রাখলে আমরা পাই,

K(G) ≤ 2 ≤ 2

এইভাবে, K(G) = 2

কাটা প্রান্ত (সেতু)

একটি কাটা শীর্ষের মতো, যদি একটি সংযুক্ত গ্রাফ থেকে, একটি প্রান্ত এমনভাবে মুছে ফেলা হয় যে এটি একটি সংযোগ বিচ্ছিন্ন গ্রাফে পরিণত হয়, তাহলে এই ধরনের প্রান্তগুলিকে কাটা প্রান্ত বলা হয়।

একটি সংযুক্ত গ্রাফের জন্য 'G' যার 'v' শীর্ষবিন্দু রয়েছে,

প্রতিটি কাটা প্রান্তের জন্য কমপক্ষে একটি কাটা শীর্ষ রয়েছে; যাইহোক, এর বিপরীতটি বৈধ নয়।

প্রতিটি কাটা শীর্ষের জন্য, এটির সাথে একটি কাটা প্রান্ত যুক্ত হতে পারে বা নাও থাকতে পারে।

একটি প্রান্ত একটি কাটা প্রান্ত হতে পারে শুধুমাত্র যদি প্রান্ত কোন চক্রের একটি অংশ হয়।

সর্বাধিক 'v-1' কাটা প্রান্ত রয়েছে।

উদাহরণ স্বরূপ,

উপরের গ্রাফে, প্রান্তটি (c,e) কাটা প্রান্ত।

প্রান্ত সংযোগ

কাটা প্রান্তের ন্যূনতম সংখ্যা বা একটি গ্রাফের ক্ষুদ্রতম কাটা সেট যা একটি সংযুক্ত গ্রাফকে একটি সংযোগ বিচ্ছিন্ন গ্রাফে রূপান্তর করতে প্রয়োজন তাকে প্রান্ত সংযোগ বলে এবং ƛ(G) দ্বারা চিহ্নিত করা হয়।

উদাহরণ স্বরূপ,

এখানে, আমরা দেখতে পাচ্ছি যে আমরা গ্রাফ থেকে প্রান্তগুলি 'bc' এবং 'gf' সরিয়ে ফেললে গ্রাফটি সংযোগ বিচ্ছিন্ন হয়ে যায়। এইভাবে প্রান্ত সংযোগ হবে 2.

একটি গ্রাফের সেট কাটা

যদি একটি সংযুক্ত গ্রাফ থেকে প্রান্ত E’-এর একটি সেট মুছে ফেলার ফলে গ্রাফটি সংযোগ বিচ্ছিন্ন হয় এবং একটি সংযোগ বিচ্ছিন্ন গ্রাফ তৈরি করে, তাহলে সেট E প্রান্ত থেকে গঠিত উপসেট E'কে গ্রাফের কাটা সেট বলা হয়।

অন্য কথায়, মুছে ফেলা প্রান্তগুলির সেট যা একটি সংযুক্ত গ্রাফকে একটি সংযোগ বিচ্ছিন্ন গ্রাফে রূপান্তর করে তাকে গ্রাফের কাটা সেট বলে।

উদাহরণ স্বরূপ,

উপরের গ্রাফে, যদি আমরা 'bc' এবং 'gf' প্রান্তগুলি সরিয়ে ফেলি তবে আমরা একটি সংযোগ বিচ্ছিন্ন গ্রাফ পাই।

সুতরাং, কাটা সেট, E’ = {bc, gf}

স্বাধীন সেট

একটি সেট একটি স্বাধীন সেট হওয়ার জন্য,

(i), দুই প্রান্তের মধ্যে কোনো সন্নিহিত প্রান্ত এবং কোনো সাধারণ শীর্ষবিন্দু থাকা উচিত নয়।

(ii) দুটি শীর্ষবিন্দুর মধ্যে কোনো সন্নিহিত শীর্ষবিন্দু এবং কোনো সাধারণ প্রান্ত থাকা উচিত নয়।

1. স্বাধীন শীর্ষবিন্দু সেট

একটি গ্রাফ 'G' = (V, E) শীর্ষবিন্দুর 'V'-এর একটি উপসেট 'S' একটি স্বাধীন শীর্ষবিন্দু সেট বলে বলা হয় যদি 'S'-তে শীর্ষবিন্দুর কোনো সংলগ্ন সেট না থাকে।

উদাহরণ স্বরূপ,

উপরের গ্রাফে,

সম্ভাব্য উপসেটগুলি হল:

S1 = {b}

S2 = {b, e}

S3 = {c, f}

S4 = {a, e}

এখানে, উপসেটগুলি S2, S3, এবং S4 হল একটি স্বাধীন শীর্ষ কারণ তারা গ্রাফ থেকে কমপক্ষে দুটি শীর্ষবিন্দু ধারণ করে এবং শীর্ষবিন্দুগুলির একটিও সংলগ্ন নয়। উপসেট S1 একটি স্বাধীন শীর্ষবিন্দু সেট নয় কারণ এতে শুধুমাত্র একটি শীর্ষবিন্দু রয়েছে।

সর্বাধিক স্বাধীন শীর্ষবিন্দু সেট

যদি উপসেটে অন্য কোনো শীর্ষবিন্দু যোগ না করা হয় তাহলে একটি স্বাধীন শীর্ষবিন্দু সেট হল একটি গ্রাফ ‘G’-এর সর্বাধিক স্বাধীন শীর্ষবিন্দু সেট।

উদাহরণ স্বরূপ,

উপরের গ্রাফে, S2, S3, এবং S4 হল স্বাধীন শীর্ষবিন্দু সেট। যেহেতু এই উপসেটগুলির মধ্যে কোনটিতে আরও শীর্ষবিন্দু যোগ করা সম্ভব নয়, তাই এগুলি সর্বাধিক স্বাধীন শীর্ষবিন্দু সেট।

সর্বোচ্চ স্বাধীন শীর্ষবিন্দু সেট

একটি সর্বাধিক স্বাধীন শীর্ষবিন্দু সেটকে একটি সম্পূর্ণ স্বাধীন শীর্ষবিন্দু সেট বলা যেতে পারে যদি সর্বোচ্চ সেটে সর্বোচ্চ সংখ্যক শীর্ষবিন্দু থাকে।

উদাহরণ স্বরূপ,

উপরের গ্রাফে, S2, S3, এবং S4 হল সর্বাধিক স্বাধীন শীর্ষবিন্দু সেট এবং প্রতিটি উপসেটের সর্বোচ্চ সংখ্যক শীর্ষবিন্দু হল 2৷ এইভাবে, এই সমস্ত উপসেটগুলি হল সর্বাধিক স্বাধীন শীর্ষবিন্দু সেট৷

2. স্বাধীন লাইন সেট

একটি গ্রাফের একটি উপসেট L হল একটি স্বাধীন লাইনের উপসেট যদি L-এ কোন সন্নিহিত প্রান্ত না থাকে।

উদাহরণ স্বরূপ,

উপরের গ্রাফে,

সম্ভাব্য উপসেটগুলি হল:

L1 = {a, d} {e, f} {b, c}

L2 = {a, b} {c,e}

L3 = {a,c}

L4 = {e, f} {a, c}

এখানে, উপসেটগুলি L1, L2, এবং L4 স্বাধীন লাইন সেট কারণ গ্রাফ থেকে কমপক্ষে দুটি প্রান্ত রয়েছে এবং প্রান্তগুলির একটিও একে অপরের সংলগ্ন নয়। উপসেট L3 একটি স্বাধীন লাইন সেট নয় কারণ এটিতে শুধুমাত্র একটি প্রান্ত রয়েছে।

সর্বোচ্চ স্বাধীন লাইন সেট

একটি স্বাধীন লাইন সেট হল একটি গ্রাফ 'G'-এর সর্বাধিক স্বাধীন লাইন সেট যদি উপসেটে অন্য কোনো প্রান্ত যোগ করা না যায়।

উদাহরণ স্বরূপ,

উপরের গ্রাফে, উপসেট L2-এ আরও শীর্ষবিন্দু যোগ করা সম্ভব। এইভাবে, উপসেট L1 এবং L4 হল সর্বাধিক স্বাধীন লাইন সেট।

সর্বাধিক স্বাধীন লাইন সেট

একটি সর্বাধিক স্বাধীন লাইন সেটকে একটি সম্পূর্ণ স্বাধীন লাইন সেট বলা যেতে পারে যদি সর্বাধিক সেটটিতে সর্বাধিক সংখ্যক প্রান্ত থাকে।

উদাহরণ স্বরূপ,

উপরের গ্রাফে, উপসেটগুলি L1 এবং L4 হল সর্বাধিক স্বাধীন লাইনের উপসেট যার প্রান্তগুলির সর্বাধিক সংখ্যা L1 = 3 এবং L4 = 2-এ৷ এইভাবে, L1 হল সর্বাধিক স্বাধীন লাইন সেট৷

আবরণ

একটি সাবগ্রাফ যা একটি গ্রাফের সমস্ত শীর্ষ বা সমস্ত প্রান্তকে আচ্ছাদন করে তাকে কভারিং গ্রাফ বলে।

এটা দুই ধরনের হতে পারে:

(i) লাইন কভারিং - সমস্ত শীর্ষবিন্দু সম্বলিত একটি সাবগ্রাফকে লাইন কভারিং বা এজ কভারিং গ্রাফ বলা হয়।

(ii) ভার্টেক্স কভারিং - সমস্ত প্রান্ত সম্বলিত একটি সাবগ্রাফকে ভার্টেক্স কভারিং গ্রাফ বলা হয়।

1. লাইন আচ্ছাদন

একটি সাবগ্রাফ, C(E), একটি গ্রাফের G = (V, E) একটি লাইন কভারিং গ্রাফ বলা হয় যদি কমপক্ষে একটি প্রান্ত C থাকে যার উপর G এর প্রতিটি শীর্ষবিন্দু ঘটনা, অর্থাৎ, প্রতিটি শীর্ষবিন্দু অন্যটির সাথে সংযুক্ত হওয়া উচিত। একটি প্রান্ত দ্বারা শীর্ষবিন্দু.

এইভাবে,

Deg(V) >= একটি যেখানে প্রতিটি V G এর অন্তর্গত

বিঃদ্রঃ: বিচ্ছিন্ন শীর্ষবিন্দু সহ একটি গ্রাফে লাইন কভারিং থাকবে না। 'x' শীর্ষবিন্দু সহ একটি গ্রাফের রেখার আবরণে কমপক্ষে [1/2] প্রান্ত রয়েছে।

উদাহরণ স্বরূপ,

এই গ্রাফে, লাইন কভারিং সহ সাবগ্রাফগুলি হল:

C1 = {{a, d}, {d, b}, {b, c}}

C2 = {{a, b}, {a, c}, {b, d}}

C3 = {{c, d}, {a, d}, {b, c}}

C4 = {{a, d}, {b, c}}

C5 = {{a, c}, {b, d}}

ন্যূনতম লাইন আচ্ছাদন

একটি গ্রাফের একটি ন্যূনতম লাইন কভারিং হল একটি যেখানে C(E) থেকে আর কোন প্রান্ত মুছে ফেলা যাবে না।

উদাহরণ স্বরূপ,

উপরের গ্রাফে, লাইন কভারিং সাবগ্রাফগুলি হল:

C1 = {{a, d}, {d, b}, {b, c}}

C2 = {{a, b}, {a, c}, {b, d}}

C3 = {{c, d}, {a, d}, {b, c}}

C4 = {{a, d}, {b, c}}

C5 = {{a, c}, {b, d}}

যেহেতু প্রান্ত {d, b} C1 থেকে মুছে ফেলা যেতে পারে এবং প্রান্ত {c, d} C3 থেকে মুছে ফেলা যেতে পারে, এই উভয় সাবগ্রাফই ন্যূনতম লাইন কভারিং নয়। এইভাবে, C2, C4, এবং C5 হল ন্যূনতম লাইন কভারিং।

ন্যূনতম লাইন কভারিং

ক্ষুদ্রতম ন্যূনতম রেখার আচ্ছাদন, বা ন্যূনতম রেখার আবরণকে ক্ষুদ্রতম বা ন্যূনতম সংখ্যার প্রান্তগুলিকে ন্যূনতম লাইন আচ্ছাদন বলে।

'G' (α1) কে লাইন কভারিং নম্বর বলা হয়, যা ন্যূনতম লাইন কভারিং এর প্রান্তের সংখ্যা।

ন্যূনতম লাইন কভার করার জন্য মনে রাখার জন্য নির্দিষ্ট পয়েন্ট আছে:

প্রতিটি লাইন কভারিং ন্যূনতম লাইন কভারিং থাকতে পারে বা নাও থাকতে পারে।
যদি একটি লাইন কভারিং 3 এর সমান বা তার বেশি দৈর্ঘ্যের পাথ ধারণ না করে, তাহলে সেই লাইন কভারিংকে ন্যূনতম লাইন কভারিং বলে। এর কারণ হল সমস্ত লাইন কভারিং উপাদানগুলি তারকা গ্রাফ যা থেকে কোন প্রান্ত মুছে ফেলা যায় না।
প্রতিটি লাইন কভারিং ন্যূনতম লাইন আচ্ছাদন রয়েছে.
ন্যূনতম লাইন কভারে একটি চক্র সম্ভব নয়।

উদাহরণ স্বরূপ,

উপরের উদাহরণে,

উপরের গ্রাফে, লাইন কভারিং সাবগ্রাফগুলি হল:

C1 = {{a, d}, {d, b}, {b, c}}

C2 = {{a, b}, {a, c}, {b, d}}

C3 = {{c, d}, {a, d}, {b, c}}

C4 = {{a, d}, {b, c}}

C5 = {{a, c}, {b, d}}

আমরা আগে দেখেছি, C2, C4, এবং C5 হল ন্যূনতম লাইন কভারিং। এই C4 এবং C5 হল ন্যূনতম লাইন কভারিং কারণ তাদের প্রান্তের ন্যূনতম সংখ্যা রয়েছে।

2. ভার্টেক্স আচ্ছাদন

একটি শীর্ষবিন্দু কভারিং গ্রাফ হল গ্রাফ G = (V, E) এর একটি সাবগ্রাফ 'R' যেখানে গ্রাফের প্রতিটি প্রান্ত 'R'-এর একটি শীর্ষবিন্দুতে ঘটনা।

উদাহরণ স্বরূপ,

উপরের গ্রাফ G থেকে, নিম্নলিখিত সাবগ্রাফগুলি তৈরি করা যেতে পারে:

R1 = {a, c}

R2 = {b, d}

R3 = {a, d, b}

R4 = {a, b, c}

এর মধ্যে R1, R2, R3, এবং R4 হল শীর্ষবিন্দু কভারিং সাবগ্রাফ।

ন্যূনতম শীর্ষবিন্দু আচ্ছাদন

একটি গ্রাফ G-এর একটি ন্যূনতম শীর্ষবিন্দু হল একটি যেখানে C(E) থেকে অন্য কোনো শীর্ষবিন্দু মুছে ফেলা যায় না।

উদাহরণ স্বরূপ,

উপরের গ্রাফে, শীর্ষবিন্দু কভার সাবগ্রাফগুলি হল:

R1 = {a, c}

R2 = {b, d}

R3 = {a, d, b}

R4 = {a, b, c}

এতে, আমরা R4 থেকে শীর্ষবিন্দু 'b' মুছে ফেলতে পারি, এইভাবে R4 একটি ন্যূনতম শীর্ষবিন্দু নয়। R1, R2, এবং R3 হল ন্যূনতম শীর্ষবিন্দু কভারিং।

ন্যূনতম শীর্ষবিন্দু আচ্ছাদন

ক্ষুদ্রতম ন্যূনতম শীর্ষবিন্দুর আচ্ছাদন, বা সর্বনিম্ন শীর্ষবিন্দুর আচ্ছাদনকে সর্বনিম্ন বা সর্বনিম্ন সংখ্যক শীর্ষবিন্দুর আচ্ছাদন বলা হয়।

‘G’ (α2) কে লাইন কভারিং সংখ্যা বলা হয়, ন্যূনতম শীর্ষবিন্দুর আচ্ছাদনে শীর্ষবিন্দুর সংখ্যা।

উদাহরণ স্বরূপ,

উপরের উদাহরণে, লাইন কভারিং সাবগ্রাফগুলি হল:

R1 = {a, c}

R2 = {b, d}

R3 = {a, d, b}

R4 = {a, b, c}

এই চারটির মধ্যে, ন্যূনতম লাইন কভারিং সাবগ্রাফ হল R1, R2 এবং R3। যেহেতু, R1 এবং R2-এর ন্যূনতম সংখ্যক শীর্ষবিন্দু রয়েছে, তাই তারা ন্যূনতম শীর্ষবিন্দু কভারিং।

মৌলিক বৈশিষ্ট্য

গ্রাফ তত্ত্বের প্রতিটি গ্রাফের নির্দিষ্ট কিছু বৈশিষ্ট্য রয়েছে যা তাদের গঠনের উপর নির্ভর করে বৈশিষ্ট্যযুক্ত করার জন্য ব্যবহৃত হয়।

এই নির্দিষ্ট পদগুলি গ্রাফ তত্ত্বের ডোমেন সম্পর্কে এবং সমস্ত গ্রাফের জন্য সাধারণ।

দুটি শীর্ষবিন্দুর মধ্যে দূরত্ব

দুটি শীর্ষবিন্দুর মধ্যে বেশ কয়েকটি প্রান্ত থাকতে পারে এবং এইভাবে দুটির মধ্যে সবচেয়ে ছোট পথ বা দূরত্বকে d(U, V) দ্বারা চিহ্নিত দুটি শীর্ষবিন্দুর মধ্যবর্তী দূরত্ব বলা হয় যেখানে U এবং V শীর্ষবিন্দু যাদের মধ্যে দূরত্ব খুঁজে বের করতে হবে।

উদাহরণ স্বরূপ,

শীর্ষবিন্দু D থেকে শীর্ষবিন্দু A-তে পৌঁছানোর দুটি পথ রয়েছে, তবে তাদের মধ্যে সবচেয়ে ছোট পথটি হল ae -> ed। সুতরাং, এই পথটি এই দুটি শীর্ষের মধ্যে দূরত্ব হিসাবে বিবেচিত হবে।

একটি শীর্ষবিন্দুর বিকেন্দ্রতা

একটি শীর্ষবিন্দুর বিকেন্দ্রিকতা, e(v) দ্বারা চিহ্নিত, একটি শীর্ষবিন্দু থেকে অন্য সমস্ত শীর্ষবিন্দু পর্যন্ত গণনা করা দূরত্বের সর্বাধিক হিসাবে সংজ্ঞায়িত করা হয়।

উদাহরণ স্বরূপ,

উপরের গ্রাফে, 'b' এবং অন্যান্য সমস্ত শীর্ষবিন্দুর মধ্যে দূরত্ব হল:

'b' থেকে 'a' এর দূরত্ব: 1

'b' থেকে 'c' এর দূরত্ব: 1

'b' থেকে 'e' এর দূরত্ব: 2

'b' থেকে 'd' এর দূরত্ব: 3

'b' থেকে 'f' এর দূরত্ব: 3

সুতরাং, শীর্ষবিন্দু 'b', e(b) এর বিকেন্দ্রতা হল 3।

একইভাবে, অন্যান্য সমস্ত শীর্ষবিন্দুর জন্য বিকেন্দ্রতা হল:

এবং (a) = 3

এবং (c) = 2

এবং (d) = 3

e (e) = 2

e(f) = 3

একটি সংযুক্ত গ্রাফের ব্যাসার্ধ

একটি সংযুক্ত গ্রাফের ব্যাসার্ধ, যা r(G) দ্বারা চিহ্নিত করা হয়, তা হল সমস্ত উদ্বেগগুলির মধ্যে সর্বনিম্ন, বা অন্য সমস্ত শীর্ষবিন্দু থেকে একটি শীর্ষবিন্দুর সমস্ত সর্বোচ্চ দূরত্বের মধ্যে সর্বনিম্ন৷

আরও সরলীকরণের জন্য, আমরা বলতে পারি যে একটি গ্রাফ G-এর সমস্ত বিকেন্দ্রিকতার মধ্যে সর্বনিম্ন হল গ্রাফ G-এর ব্যাসার্ধ।

উদাহরণ স্বরূপ,

উপরের নেটওয়ার্ক বা গ্রাফে, শীর্ষবিন্দুগুলির উদ্বেগগুলি হল:

এবং (a) = 3

e(b) = 2

এবং (c) = 2

এবং (d) = 3

e (e) = 2

e(f) = 3

এইভাবে, গ্রাফের ব্যাসার্ধ, r(G) = 2 কারণ এটি সমস্ত বিকেন্দ্রিকতার মধ্যে সর্বনিম্ন।

একটি গ্রাফের ব্যাস

একটি সংযুক্ত গ্রাফের ব্যাসার্ধের বিপরীতে, একটি সংযুক্ত গ্রাফের ব্যাস হল অন্যান্য সমস্ত উদ্কেন্দ্রিকতার মধ্যে সর্বাধিক বিকেন্দ্রতা।

এইভাবে, যদি একটি শীর্ষবিন্দু এবং অন্যান্য সমস্ত শীর্ষবিন্দুর মধ্যে সমস্ত সর্বোচ্চ দূরত্বের মধ্যে সর্বাধিককে d(G) দ্বারা চিহ্নিত করা হয়।

উদাহরণ স্বরূপ,

উপরের নেটওয়ার্ক বা গ্রাফের উপর ভিত্তি করে, শীর্ষবিন্দুগুলির বিকেন্দ্রতাগুলি হল:

এবং (a) = 3

e(b) = 2

এবং (c) = 2

এবং (d) = 3

e (e) = 2

e(f) = 3

এইভাবে, গ্রাফের ব্যাস, d(G) = 3 কারণ এটি সমস্ত বিকেন্দ্রিকতার মধ্যে সর্বাধিক।

কেন্দ্রীয় পয়েন্ট

গ্রাফের কেন্দ্রীয় বিন্দুটি হল শীর্ষবিন্দু যার বিকেন্দ্রতা গ্রাফের ব্যাসার্ধের সমান।

সুতরাং, যদি e(V) = r(V),

তারপর শীর্ষবিন্দু V হল গ্রাফ G এর কেন্দ্র।

উদাহরণ স্বরূপ,

এবং (a) = 3

e(b) = 2

এবং (c) = 2

এবং (d) = 3

e (e) = 2

e(f) = 3

শীর্ষবিন্দুর 'b' এবং 'e' গ্রাফের ব্যাসার্ধের সমান, অর্থাৎ, r(G) = e(b) = e(e) = 2। এইভাবে, শীর্ষবিন্দু 'b' এবং 'e' হল গ্রাফের কেন্দ্রীয় পয়েন্ট।

কেন্দ্র

গ্রাফের কেন্দ্রকে গ্রাফ G এর কেন্দ্রীয় বিন্দুর সেট হিসাবে সংজ্ঞায়িত করা হয়।

উদাহরণ স্বরূপ,

উপরের গ্রাফের উপর ভিত্তি করে, গ্রাফের কেন্দ্র হল {b, e}।

পরিধি

গ্রাফ G-এর সর্বাধিক বর্ধিত চক্রের অংশের প্রান্তের সংখ্যাকে পরিধি বলা হয়।

উদাহরণ স্বরূপ,

উপরের গ্রাফের উপর ভিত্তি করে, দীর্ঘতম চক্র হল a-b-c-a বা d-e-f-d। এইভাবে গ্রাফের পরিধি 3।

ঘের

একটি গ্রাফের পরিধির বিপরীতে, গ্রাফ G-এর ক্ষুদ্রতম চক্রের প্রান্তের সংখ্যা হিসাবে ঘেরকে সংজ্ঞায়িত করা হয়।

এটি গ্রাফের উপর ভিত্তি করে পরিধির সমান হতে পারে বা নাও হতে পারে।

উদাহরণ স্বরূপ,

উপরের গ্রাফের উপর ভিত্তি করে, ক্ষুদ্রতম চক্রগুলি হল a-b-c-a বা d-e-f-d। এইভাবে গ্রাফের ঘের হল 3।

ভ্রমণযোগ্যতা

একই পথে ফিরে না গিয়ে শীর্ষবিন্দুগুলির মধ্যে একটি পথ অঙ্কন করে একটি গ্রাফ অতিক্রম করা হয়।

এই নিবন্ধে, আমরা গ্রাফ ট্রাভার্সিং এর দুটি প্রধান ধারণা বুঝতে পারব:

(i) অয়লারের পথ

(ii) হ্যামিলটোনিয়ান পথ

1. অয়লারের পথ

যদি সংযুক্ত বা নির্দেশিত গ্রাফ 'G'-এ একটি অয়লার পাথ উপস্থিত থাকে, তাহলে এই জাতীয় নেটওয়ার্ক অতিক্রমযোগ্য।

একটি অয়লার পাথে 'G'-এর ঠিক একটি প্রান্ত এবং 'G'-এর অন্তত একটি শীর্ষবিন্দু থাকা উচিত।

যদি একটি অয়লার পাথের প্রারম্ভ এবং শেষ শীর্ষবিন্দু একই হয়, তাহলে এই ধরনের পথকে অয়লার সার্কিট বলে।

উদাহরণ স্বরূপ,

উপরের গ্রাফে, অয়লার পাথ হল: d-a-b-d-c-b

অয়লার সার্কিট উপপাদ্য

অয়লারের সার্কিট উপপাদ্য অনুসারে, সংযুক্ত গ্রাফগুলি অতিক্রমযোগ্য হতে পারে, যদি (যদি এবং শুধুমাত্র যদি) জি-তে বিজোড় ডিগ্রি সহ ঠিক 2 বা 0 শীর্ষবিন্দু রয়েছে।

গ্রাফটিতে অয়লারের পথও থাকতে পারে এবং অয়লারের সার্কিট নয় যদি এটির বিজোড় ডিগ্রির সাথে শুধুমাত্র দুটি শীর্ষবিন্দু থাকে।

সুতরাং, একটি গ্রাফে অয়লারের সার্কিট থাকার জন্য এটিতে কোন বিজোড় ডিগ্রি শীর্ষবিন্দু থাকা উচিত নয়।

উপরের ক্ষেত্রে ব্যবহৃত গ্রাফ বা নেটওয়ার্ক বিবেচনা করে গ্রাফটিতে একটি অয়লারের পথ d-a-d-b-c-b রয়েছে। এই পথটি অয়লার সার্কিট নয় কারণ এখানে দুটি বিজোড় ডিগ্রি শীর্ষবিন্দু রয়েছে, যেমন, 'b' এবং 'd'।

2. হ্যামিলটোনিয়ান পথ

হ্যামিলটোনিয়ান পথ সম্পর্কে জানার আগে, আসুন হ্যামিলটোনিয়ান গ্রাফটি দেখে নেওয়া যাক।

হ্যামিলটোনিয়ান গ্রাফ হল একটি সংযুক্ত গ্রাফ G যেখানে গ্রাফ G এর সমস্ত শীর্ষবিন্দু সমন্বিত একটি চক্র বিদ্যমান।

একটি হ্যামিলটোনিয়ান গ্রাফে, G-এর প্রতিটি শীর্ষবিন্দু মাত্র একবারই বিদ্যমান থাকে এবং যে পথটি গঠিত হয় তাকে হ্যামিলটোনিয়ান পাথ বলা হয়।

হ্যামিলটোনিয়ান চক্র অয়লার চক্র থেকে ভিন্ন কারণ গ্রাফের প্রতিটি প্রান্ত অয়লার চক্রে একবারই বিদ্যমান। বিপরীতে, হ্যামিলটোনিয়ান চক্রে, গ্রাফের কিছু প্রান্ত এড়িয়ে যেতে পারে।

উদাহরণ স্বরূপ,

উপরের গ্রাফে আমরা বলতে পারি যে:

অয়লার পথ বিদ্যমান - সত্য

অয়লার সার্কিট বিদ্যমান - মিথ্যা

একটি হ্যামিলটোনিয়ান চক্র বিদ্যমান - সত্য

একটি হ্যামিলটোনিয়ান পথ বিদ্যমান - সত্য

মিল

যে সাবগ্রাফের কোন প্রান্ত সংলগ্নতা নেই বা কোন দুই প্রান্তের মধ্যে কোন সাধারণ শীর্ষবিন্দু নেই তাকে ম্যাচিং সাবগ্রাফ বলে।

গাণিতিকভাবে, একটি সাবগ্রাফকে একটি গ্রাফ G = (V, E) এর একটি মিলিত সাবগ্রাফ M(G) বলা যেতে পারে যদি G-এর প্রতিটি শীর্ষবিন্দু সাবগ্রাফ M-এর সর্বাধিক এক প্রান্তে ঘটে থাকে।

এইভাবে, G-এর অন্তর্গত সমস্ত V-এর জন্য deg(V) ≤ 1।

একটি মিলে যাওয়া সাবগ্রাফে, এটি মনে রাখা উচিত যে দুটি প্রান্ত সংলগ্ন হতে পারে না কারণ এই ধরনের ক্ষেত্রে, সন্নিহিত প্রান্তগুলির সাথে শীর্ষবিন্দুর ডিগ্রী দুটি ডিগ্রি থাকবে, যা মিলিত নিয়মের পরিপন্থী।

গ্রাফ মেলানোর সময়,

যদি deg(V) = 1 হয়, তাহলে শীর্ষবিন্দুটি মিলেছে বলা হয়।

যদি deg(V) = 0 হয়, তাহলে বলা হয় শীর্ষবিন্দুটি মিলছে না।

উদাহরণ স্বরূপ,

এই গ্রাফ G-এ, সংলগ্নতা ছাড়াই চারটি মিল অনুসরণ করে এবং সমস্ত নোডকে কভার করে c, f, e, d গঠিত হতে পারে:

উপরে দেওয়া গ্রাফ এবং উদাহরণ ব্যবহার করে, আপনি আরও নেটওয়ার্ক মিল তৈরি করার চেষ্টা করতে পারেন।

সর্বোচ্চ মিল

একটি মিলে যাওয়া সাবগ্রাফ M যাতে M-এর সাথে আর কোনো প্রান্ত যোগ করা যায় না তাকে সর্বাধিক মিলে যাওয়া সাবগ্রাফ বলে।

উদাহরণ স্বরূপ,

উপরের গ্রাফের উপর ভিত্তি করে, M1 এবং M3 হল সর্বাধিক মিলে যাওয়া সাবগ্রাফ।

সর্বোচ্চ মিল

সবচেয়ে বড় সর্বোচ্চ মিলে যাওয়া সাবগ্রাফ বা সর্বোচ্চ সংখ্যক প্রান্ত সহ সর্বাধিক সাবগ্রাফকে সর্বোচ্চ ম্যাচিং সাবগ্রাফ বলা হয়।

মিলে যাওয়া সংখ্যাটিকে সর্বাধিক মিলে যাওয়া সাবগ্রাফে প্রান্তের সংখ্যা হিসাবে সংজ্ঞায়িত করা হয়।

উদাহরণ স্বরূপ,

উপরের ক্ষেত্রে, আমাদের কাছে সর্বাধিক মিলে যাওয়া সাবগ্রাফ হিসাবে M1 এবং M3 রয়েছে যেগুলি সর্বাধিক মিলে যাওয়া সাবগ্রাফও কারণ তাদের উভয়েরই প্রান্তের সংখ্যা সমান।

নিখুঁত ম্যাচিং

যদি সাবগ্রাফের প্রতিটি শীর্ষবিন্দুর একটি ডিগ্রী থাকে, অর্থাৎ, গ্রাফ G থেকে প্রতিটি শীর্ষবিন্দু শুধুমাত্র একটি প্রান্তে ঘটনা হয়, তাহলে সাবগ্রাফটিকে একটি নিখুঁত ম্যাচিং সাবগ্রাফ হিসাবে পরিচিত করা হয়।

এইভাবে, আপনি (V) = 1 সমস্ত V এর জন্য।

বিঃদ্রঃ: যেহেতু একটি নিখুঁত ম্যাচিং সাবগ্রাফে কোনো প্রান্ত যোগ করা যায় না, তাই এটি একটি সর্বোচ্চ মিলে যাওয়া সাবগ্রাফও। কিন্তু এর বিপরীতটি বৈধ নয়।

শীর্ষবিন্দুর সংখ্যার উপর নির্ভর করে প্রতিটি সর্বোচ্চ মিলে যাওয়া সাবগ্রাফ হতে পারে বা নাও হতে পারে।

যদি শীর্ষবিন্দুর সংখ্যা জোড় হয়, তাহলে এটি একটি নিখুঁত মিলে যাওয়া সাবগ্রাফ।

যদি এটি বিজোড় হয়, তাহলে প্রতিটি শীর্ষবিন্দুর সাথে মিল করার পর, একটি একক শীর্ষবিন্দুকে শূন্য ডিগ্রি রেখে দেওয়া হবে, যা নিখুঁত মিলিত সাবগ্রাফের নীতির বিরুদ্ধে।

উদাহরণ স্বরূপ,

উপরের ক্ষেত্রে গঠিত গ্রাফগুলি ব্যবহার করে, আমরা বলতে পারি যে M1 এবং M3 নিখুঁত মিলে যাওয়া সাবগ্রাফ কারণ প্রতিটি নোডের ডিগ্রী 1 রয়েছে।

আইসোমরফিজম

একই সংখ্যক প্রান্ত, শীর্ষবিন্দু এবং প্রান্ত সংযোগ সহ একই গ্রাফের বিভিন্ন রূপকে আইসোমরফিজম বলা হয় এবং এই জাতীয় গ্রাফগুলি আইসোমরফিক গ্রাফ হিসাবে পরিচিত।

আইসোমরফিক গ্রাফ

যদি দুটি গ্রাফ G1 এবং G2, একই সংখ্যক উপাদান এবং একই প্রান্ত সংযোগ থাকে, তাহলে এই ধরনের গ্রাফগুলিকে আইসোমরফিক গ্রাফ বলা হয়।

যেহেতু G1 G2 এর মতো,

|V(G1) | = |V(G2) |

E (G1) = |E(G2) |

সুতরাং, এটা বলা যেতে পারে যে, আইসোমরফিক গ্রাফে,

যদি একটি গ্রাফের শীর্ষবিন্দুগুলি একটি চক্র গঠন করে, তবে অন্যটির শীর্ষবিন্দুগুলিও একটি চক্র গঠন করবে।

এছাড়াও, উভয় গ্রাফের ডিগ্রী ক্রম একই হবে।

উদাহরণ:

এই ক্ষেত্রে, উপরের প্রদত্ত অনির্দেশিত গ্রাফগুলি আইসোমেট্রিক কারণ I1 এবং I2 এর একই সংখ্যক উপাদান (নোড, প্রান্ত) এবং প্রান্ত সংযোগ রয়েছে।

প্ল্যানার গ্রাফ

একটি গ্রাফ যেখানে দুটি প্রান্ত পরস্পরকে অ-শীর্ষ বিন্দুতে অতিক্রম করে না একটি সমতলে বা একটি গোলক আঁকতে পারে যাকে প্ল্যানার গ্রাফ বলা হয়।

উদাহরণ স্বরূপ,

গ্রাফ 1:

গ্রাফ 2:

উপরের গ্রাফে, গ্রাফ 1 নন-প্ল্যানার এবং গ্রাফ 2 হল প্ল্যানার। এটির কারণ এটির কোন অ-শীর্ষ ছেদকারী প্রান্ত নেই।

অঞ্চলসমূহ

সমতল গ্রাফ দ্বারা গঠিত সংযুক্ত অঞ্চলগুলিকে অঞ্চল বলা হয়।

উদাহরণ স্বরূপ,

অঞ্চলের ডিগ্রী

একটি আবদ্ধ বা একটি সীমাহীন অঞ্চলের ডিগ্রী অঞ্চলটিকে ঘিরে থাকা প্রান্তের সংখ্যা দ্বারা নির্দিষ্ট করা হয়। এটি দ্বারা দেওয়া হয়,

r = deg(r) = r ঘেরা প্রান্তের সংখ্যা।

উদাহরণ স্বরূপ,

উপরের উদাহরণে, প্রতিটি অঞ্চলের ডিগ্রি হল:

ডিগ্রি (অঞ্চল 1) = 3

ডিগ্রী (অঞ্চল 2) = 7

ডিগ্রি (অঞ্চল 3) = 3

অঞ্চলের ডিগ্রির সমষ্টি

'n' শীর্ষবিন্দুগুলির একটি প্ল্যানার গ্রাফের জন্য, সমস্ত শীর্ষবিন্দুর ডিগ্রীর সমষ্টি দ্বারা দেওয়া হয়,

n Σ i = 1 deg (Vi) = 2 | E |

অঞ্চল উপপাদ্যের ডিগ্রীর যোগফল বলে যে 'n' অঞ্চল সম্বলিত একটি প্ল্যানার গ্রাফে অঞ্চলগুলির ডিগ্রীর সমষ্টি থাকবে যেমন,

n Σ i = 1 deg (Ri) = 2 | E |

সুতরাং, এটি উপসংহারে আসা যেতে পারে যে:

1. যদি D প্রতিটি অঞ্চলের ডিগ্রী হয়, তবে অঞ্চলগুলির ডিগ্রীর যোগফল হবে:

ডি|আর| = 2|ই|

2. যদি প্রতিটি অঞ্চলের ডিগ্রী 'r' কমপক্ষে D হয়, তবে অঞ্চলগুলির ডিগ্রির সমষ্টি হবে:

ডি|আর| ≤ 2|E|

3. যদি প্রতিটি অঞ্চলের ডিগ্রী 'r' সর্বাধিক D হয়, তবে অঞ্চলগুলির ডিগ্রির সমষ্টি হবে:

ডি|আর| ≥ 2|E|

এখন, ধরে নিচ্ছি যে সমস্ত অঞ্চলের ডিগ্রী একই এবং অয়লারের সূত্রগুলি প্লেনার গ্রাফে |V| শীর্ষবিন্দুর সংখ্যা, |R| অঞ্চলের সংখ্যা, এবং |E| আমাদের কাছে প্রান্তের সংখ্যা,

(i) |V| + |আর| = |ই| + 2 যদি গ্রাফ G প্ল্যানার সংযুক্ত থাকে।

(ii) |V| + |আর| = |ই| + (K+1) যদি এটি 'K' উপাদান সহ একটি প্ল্যানার গ্রাফ হয়।

হোমোমরফিজম

কিছু G-এর প্রান্তকে এক বা একাধিক শীর্ষবিন্দু দিয়ে ভাগ করার সময়, যদি আমরা G1 এবং G2 এর মতো আরও গ্রাফ পেতে পারি, এই ধরনের গ্রাফগুলিকে হোমোমরফিক গ্রাফ বলা হয়।

হোমোমরফিজম এবং আইসোমরফিজম

যদি একটি গ্রাফ G1 অন্য একটি গ্রাফ G2 থেকে আইসোমরফিক হয়, তাহলে বলা যেতে পারে যে গ্রাফ G2 মূল গ্রাফ G-এর সমকক্ষ। তবে, অন্যভাবে একই কথা বলা যাবে না।

পলিহেড্রাল গ্রাফ

যদি একটি সরল সংযুক্ত প্ল্যানার গ্রাফের প্রতিটি শীর্ষবিন্দু 3 এর থেকে বেশি বা সমান হয়, তবে এই ধরনের গ্রাফটিকে একটি পলিহেড্রাল গ্রাফ বলা হয়।

এইভাবে, G-এর অন্তর্গত সমস্ত V-এর জন্য deg(V) ≥ 3।

আমাদের চেক আউট হিউম্যান কম্পিউটার ইন্টারফেস গাইড যা নতুনদের জন্য ভালো হবে।

প্রোগ্রামিং