ওরিয়েন্টেড গ্রাফ। একটি নির্দেশিত গ্রাফ সংযোজন ম্যাট্রিক্স উদাহরণের সংজ্ঞা

একটি প্রান্ত হল শীর্ষবিন্দুগুলির একটি আদেশযুক্ত জোড়া৷ একটি গ্রাফ যার জন্য এর প্রতিটি প্রান্তের দিক নির্দেশিত হয় তাকে বলা হয় ভিত্তিক.

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

নির্দেশিত গ্রাফ দ্বারা একটি ক্রম বা পছন্দ সম্পর্ক সংজ্ঞায়িত করাও সম্ভব।

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

উদাহরণস্বরূপ, জটিল নমুনা মূল্যায়নে (উদাহরণস্বরূপ, ভূতত্ত্বে), প্রান্তের দিকটি পছন্দ নির্দেশ করে। একটি স্বাভাবিক পছন্দ সিস্টেমে চক্র থাকা উচিত নয়।

তানিয়া নাতাশা

যাতে আপনি সর্বদা একটি পছন্দ করতে পারেন, অন্যথায় আপনাকে পছন্দগুলির সিস্টেমটি পুনর্বিবেচনা করতে হবে।

একমুখী.

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

প্রশ্ন হল, শহরের রাস্তাগুলিকে কোন অবস্থায় এমনভাবে সাজানো যেতে পারে যে কোনও জায়গা থেকে আপনি নিয়ম লঙ্ঘন না করে অন্য যে কোনও জায়গায় যেতে পারেন? ট্রাফিকরাস্তার মাধ্যমে

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

এটা স্পষ্ট যে এই ধরনের প্রতিটি গ্রাফ সংযুক্ত করা আবশ্যক, কিন্তু এটি যথেষ্ট নয়।

প্রান্ত E = (A, B) বলা হবে সংযোগ প্রান্ত, বা ইসথমাসযদি এটি A থেকে B পর্যন্ত একমাত্র পথ হয় (বা এর বিপরীত)।

সংযোগকারী প্রান্তটি গ্রাফের সমস্ত শীর্ষকে দুটি সেটে বিভক্ত করে: যেগুলি প্রান্ত E বরাবর না গিয়ে A থেকে পৌঁছানো যায় এবং যেগুলি E বরাবর না গিয়ে B থেকে পৌঁছানো যায়৷ এই ক্ষেত্রে গ্রাফটি দুটি অংশ নিয়ে গঠিত G 1 এবং G 2 শুধুমাত্র E প্রান্ত দ্বারা সংযুক্ত (চিত্র a এবং a+1)।

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

যদি প্রান্ত E i = (A i , B i) সংযোগ না করে, তাহলে আরেকটি পথ আছে যা A i এবং B i কে সংযুক্ত করে এবং E i এর মধ্য দিয়ে যায় না। অতএব, এই ধরনের একটি প্রান্তকে একটি চক্রীয় প্রান্ত বলা হবে।

fig.2 সংযুক্ত ডুমুর. 2+1 চূড়ান্ত (সংযোগ) চিত্র 2+2 চক্রীয়

পাঁজর পাঁজর

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

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

আমরা গ্রাফটিকে সঠিকভাবে ওরিয়েন্ট করার উপায় দেখিয়ে এই উপপাদ্যটি প্রমাণ করতে পারি। এর মধ্যে নির্বাচন করা যাক জি নির্বিচারে প্রান্ত E \u003d (A, B) . যদি একটি ই - সংযোগকারী প্রান্ত, এটি দ্বি-পার্শ্বযুক্ত থাকবে এবং তারপরে সেখান থেকে যাওয়া সম্ভব হবে কিন্তু প্রতি AT এবং পিছনে (চিত্র 2+3)।

fig.2+3 ডুমুর। 2+4

যদি একটি ই একটি চক্রীয় প্রান্ত, তারপর এটি কিছু চক্রের মধ্যে অন্তর্ভুক্ত করা হয় থেকে, যার উপর আপনি চক্রীয় অভিযোজন সেট করতে পারেন (fig.2+4)।

ধরুন আমরা ইতিমধ্যে কিছু অংশ ওরিয়েন্টেড করেছি এইচ গণনা জি, যাতে গ্রাফের যেকোনো শীর্ষ থেকে এইচ আপনি একমুখী ট্র্যাফিকের নিয়ম মেনে এর অন্য যেকোনো শীর্ষে যেতে পারেন। গ্রাফ থেকে জি সংযুক্ত, তারপর হয় এইচ পুরো গ্রাফের সাথে মিলে যায় ছ, অথবা একটি প্রান্ত আছে E \u003d (A, B), যা অন্তর্গত নয় এইচ , কিন্তু তার শীর্ষবিন্দু এক, বলুন কিন্তু , অন্তর্গত এইচ .

যদি একটি ই - সংযোগকারী পাঁজর এবি , তাহলে এটি দ্বিমুখী থাকবে। তারপর কোন শীর্ষবিন্দু জন্য এক্স গণনা এইচ কেউ একটি ওরিয়েন্টেড চেইন খুঁজে পেতে পারেন আর সংযোগ A এর সাথে X , যার অর্থ (প্রান্তের মাধ্যমে ই ) , এবং সাথে AT . উপর থেকে ফিরে AT শেষ প্রান্তে ই আপনি যেতে পারেন কিন্তু , এবং তারপর - ওরিয়েন্টিং চেইন বরাবর জেড - থেকে কিন্তু প্রতি এক্স (চিত্র a+5)। সংযুক্ত করা হচ্ছে ই প্রতি এইচ , আমরা ইতিমধ্যে পেতে সর্বাধিকগণনা জি প্রয়োজনীয় বৈশিষ্ট্য সহ। যদি প্রান্ত E \u003d (A, B) চক্রাকার, এটি কিছু চক্রের অন্তর্গত থেকে . আমরা জন্য দিক নির্ধারণ থেকে থেকে কিন্তু আগে AT এবং আরও বরাবর থেকে প্রথম শিখরে ডি থেকে থেকে মালিক এইচ (চিত্র a+6)।

চাল a+5 ডুমুর। a+6

এর এই সব প্রান্ত যোগ করা যাক এইচ . দিন এক্স - থেকে নির্বিচারে শীর্ষবিন্দু এইচ , ক এ - যেকোনো শীর্ষবিন্দু থেকে ; কেউ একটি ওরিয়েন্টেড চেইন খুঁজে পেতে পারেন আর , মালিকানাধীন এইচ এবং সংযোগ এক্স সঙ্গে কিন্তু এবং তারপর বরাবর থেকে উপরে যান এ থেকে থেকে . ফিরে এস এ আপনি পাশাপাশি হাঁটতে পারেন থেকে শীর্ষে ডি , এবং এটি থেকে - অন্তর্গত এইচ ওরিয়েন্টেড চেইন জেড - থেকে ডি প্রতি এক্স . অতএব, নির্দেশিত গ্রাফ যোগ করে প্রাপ্ত এইচ নির্দিষ্ট চক্র প্রান্ত থেকে , প্রয়োজনীয় শর্তগুলিও সন্তুষ্ট করে। এই প্রক্রিয়াটি অব্যাহত রেখে, আমরা শেষ পর্যন্ত মূল গ্রাফটিকে প্রয়োজনীয় উপায়ে অভিমুখী করি জি .

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

নির্দেশিত গ্রাফের জন্য, আমাদের প্রতিটি শীর্ষবিন্দুতে বহির্গামীর সংখ্যা p(A) এবং আগত প্রান্তগুলির p*(A) সংখ্যা রয়েছে। মোট সংখ্যাপাঁজর সমান:

N \u003d p (A 1) + p (A 2) + ... + p (A n) \u003d p * (A 1) + p * (A 2) + ... + p * (A n)

পাওয়া যায় বিভিন্ন ধরনেরগ্রাফ যার জন্য শীর্ষবিন্দুর কিছু বিশেষ বৈশিষ্ট্য রয়েছে। গণনা বলা হয় সমজাতীয়, যদি এর সমস্ত শীর্ষবিন্দুর ডিগ্রী একই সংখ্যার সমান হয় r: প্রতিটি শীর্ষবিন্দু A এর জন্য:

p(A) = p * (A) = r

অনুশীলন

n = 2,6,7,8 শীর্ষবিন্দু সহ r = 2 ডিগ্রির সমজাতীয় নির্দেশিত গ্রাফ তৈরি করুন।

সম্পর্ক

সম্পর্ক এবং গ্রাফ।

যে কোনো গাণিতিক ব্যবস্থা কিছু বস্তু বা উপাদানের একটি সেট নিয়ে কাজ করে। (লক্ষণ: বীজগণিত, জ্যামিতি)

নির্মাণের জন্য গাণিতিক তত্ত্ব, আমরা এই উপাদান নিজেদের না শুধুমাত্র প্রয়োজন, কিন্তু সম্পর্কতাদের মধ্যে. (উদাহরণ: সংখ্যা a > b; জ্যামিতিতে - ত্রিভুজের সমতা, // লাইন; সেট তত্ত্বে - সেটের সমতা এবং অন্তর্ভুক্তি।)

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

আসুন বাইনারি সম্পর্কের R-এর একটি সাধারণ সংজ্ঞা প্রবর্তন করি: аRв - в হল R-এর সাথে a সম্পর্কিত।

উদাহরণ স্বরূপ, a > b সম্পর্কের অর্থ হল b হল a এর চেয়ে কম সকল সংখ্যার সেটের অন্তর্গত

প্রকৃতপক্ষে, প্রতিটি নির্দেশিত গ্রাফ G তার শীর্ষবিন্দুগুলির সেটে কিছু সম্পর্ককে সংজ্ঞায়িত করে। এই অনুপাতটি এভাবে লেখা যেতে পারে: аGв. এর মানে হল যে গ্রাফটির একটি নির্দেশিত প্রান্ত আছে a থেকে b পর্যন্ত।

বিশেষ শর্ত.

কিছু সম্পর্ক R দেওয়া যাক। যদি একটি উপাদান a নিজের সাথে R সম্পর্কে থাকে তবে এটি গ্রাফের একটি লুপের সাথে মিলে যায়

সম্পর্ক R যার জন্য শর্ত аRв সন্তুষ্ট যে কোন একটি জন্য, বলা হয় প্রতিফলিত.

যদি aRv শর্তটি কোনো উপাদানের জন্য সন্তুষ্ট না হয়, তাহলে R বলা হয় বিরোধী প্রতিবিম্বিত মনোভাব.এই ক্ষেত্রে, গ্রাফের শীর্ষবিন্দুগুলির কোনোটিতেই লুপ নেই।

প্রতিটি সম্পর্কের জন্য R, একজন সংজ্ঞায়িত করতে পারেন বিপরীত অনুপাত R*, ধরে নিচ্ছি যে аR * в যদি এবং শুধুমাত্র যদি ARв।

এটি বিপরীত সম্পর্কের সংজ্ঞা থেকে দেখা যায় যে R এর সাথে সম্পর্কিত গ্রাফ G এর একটি প্রান্ত (a, b), তাহলে গ্রাফ G * R * এর সাথে একটি প্রান্ত (c, a) থাকতে হবে। অন্য কথায়, গ্রাফ G * হল G এর বিপরীত, অর্থাৎ G এর মতো একই প্রান্ত সহ একটি গ্রাফ, কিন্তু বিপরীতমুখী।

সম্পর্ক বলা হয় প্রতিসম, যদি аRв থেকে вра অনুসরণ করে।

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

সম্পর্ক বলা হয় প্রতিসম, যদি এটি ARв থেকে অনুসরণ করে যে এটি অবশ্যই Rа তে ধরে না। অ্যান্টিসিমেট্রিক রিলেশন গ্রাফে একই জোড়া শিরোনামের সংযোগকারী অনির্দেশিত বা বিপরীতমুখী প্রান্ত থাকে না; অধিকন্তু, তাদের উপর কোন লুপ নেই, যেমন এই সম্পর্ক বিরোধী প্রতিফলিত হয়.

অনুপাত পরিবর্তনশীলভাবে, যদি এটি aRb এবং bRc দুটি শর্ত থেকে অনুসরণ করে যে aRc।

একটি ট্রানজিটিভ সম্পর্কের গ্রাফে নিম্নলিখিত বৈশিষ্ট্যযুক্ত বৈশিষ্ট্য রয়েছে: প্রতিটি জোড়া প্রান্তের জন্য (a, b), (b, c) আছে বন্ধপ্রান্ত এই বৈশিষ্ট্যটি বারবার প্রয়োগ করে, আমরা উপসংহারে পৌঁছেছি যে যদি এই গ্রাফটিতে শীর্ষবিন্দু X থেকে শীর্ষ Y পর্যন্ত একটি নির্দেশিত পথ থাকে, তবে একটি নির্দেশিত প্রান্তও রয়েছে (x, y)।

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

সমতা সম্পর্ক।

একটি সমতুল্য সম্পর্ক, সাধারণত ~ দ্বারা চিহ্নিত করা হয়, এর নিম্নলিখিত তিনটি বৈশিষ্ট্য রয়েছে:

এক). রিফ্লেক্সিভিটি: a ~ a;

2)। প্রতিসাম্য: a ~ থেকে z থেকে ~ a;

3)। ট্রানজিটিভিটি: a ~ থেকে এবং ~ c Þ a ~ c থেকে।

প্রকৃতপক্ষে, সমতা সম্পর্ক হল সমতার সম্পত্তির একটি সাধারণীকরণ।

সমতুল্য সম্পর্ক শীর্ষবিন্দুর সেটে একটি পার্টিশন প্রবর্তন করে বিচ্ছিন্ন সমতুল্য ক্লাস.

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

আংশিক আদেশ।

মনোভাব আংশিক আদেশহল (সেটের উদাহরণে):

এক). রিফ্লেক্সিভিটি: A Ê A

2)। ট্রানজিটিভিটি: যদি A Ê B এবং B Ê C Þ A Ê C

3)। পরিচয়: যদি A Ê B এবং B Ê Az A = B

কঠোর অন্তর্ভুক্তি সম্পর্ক -

এক). অ্যান্টি-রিফ্লেক্সিভিটি: A ÉA কখনই ঘটে না;

2)। ট্রানজিটিভিটি: A É B এবং B É C হলে A É C

আদেশ সম্পর্ক(কঠোর অর্থে) একটি কঠোর আদেশ বলা হয়, a > b, যার জন্য, পূর্ববর্তী শর্তগুলি ছাড়াও, নিম্নলিখিতগুলিও ধারণ করে:

সম্পূর্ণতা শর্ত।যে কোন দুটি অ-কাকতালীয় উপাদানের জন্য এবং a, দুটি সম্পর্কের একটি a>b বা b>a সর্বদা সন্তুষ্ট।

সাধারণত, একটি আংশিক আদেশকৃত গ্রাফ একটি আদেশকৃত আকারে চিত্রিত হয়। যেহেতু যেকোনো প্রান্ত (a, b) এবং (b, c) এর জন্য একটি ক্লোজিং এজ (a, c) আছে, তাই এটি বাদ দেওয়া যেতে পারে।

ফ্ল্যাট গ্রাফ।

প্ল্যানার গ্রাফের জন্য শর্ত।

কাউন্ট কুরাতোভস্কি কে 3.3

তিনটি ঘর এবং তিনটি কূপ সম্পর্কে গ্রাফ সমস্যা

কাউন্ট কুরাতোভস্কি কে 5

এই দুটি গ্রাফ ফ্ল্যাট নয়!

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

কয়েকটি প্রান্ত নিয়ে গঠিত প্রাথমিক চেইন হয়ে ওঠে।

বিপরীত অপারেশন, যেখানে প্রাথমিক চেইন থেকে বিচ্ছিন্ন শীর্ষবিন্দুগুলি সরানো হয়, তাকে বলা হয় সঙ্কোচনচিত্রলেখ.

কুরাতোভস্কির উপপাদ্য

একটি গ্রাফ সমতল হওয়ার জন্য, এটি প্রয়োজনীয় এবং যথেষ্ট যে এটির মধ্যে এমন কোনও গ্রাফ নেই যা একটি K 3.3 গ্রাফ বা K 5 গ্রাফে সংকুচিত হতে পারে।

অয়লারের সূত্র

আমরা সমতলে তৈরি প্ল্যানার গ্রাফগুলি বিবেচনা করব বহুভুজ নেটওয়ার্ক. এর মানে হল সমতল গ্রাফ G এর প্রান্তগুলি একে অপরের সংলগ্ন বহুভুজের একটি সেট তৈরি করে, সমতলটিকে বহুভুজ অঞ্চলে বিভক্ত করে।

এটি বহুভুজ গ্রাফের সংজ্ঞা থেকে অনুসরণ করে যে তারা সংযুক্ত। আমরা এটাও চাই যে কোন বহুভুজ অন্যের ভিতরে থাকে না। এই ধরনের প্রতিটি বহুভুজের সীমানা প্রান্তগুলি একটি চক্র গঠন করে, কখনও কখনও বলা হয় ন্যূনতম চক্র. সমতলের যে অংশটি বহুভুজের মধ্যে আবদ্ধ থাকে তাকে বলা হয় গ্রাফ মুখ. গ্রাফও আছে সর্বোচ্চ চক্র C 1, পুরোটা ঘিরেএর সমস্ত মুখ সহ গ্রাফ। আমরা C 1 এর বাইরে থাকা প্লেনের অংশটিকে C 1 সীমানা সহ একটি গ্রাফের মুখ হিসাবে বিবেচনা করব - অন্তহীনমুখ F ¥

দ্বারা নির্দেশ করুন

শীর্ষবিন্দু, প্রান্ত এবং মুখের সংখ্যা স্থান বহুভুজ।.

অয়লারের উপপাদ্য

c - p + r = 2

প্রমাণ: n প্রান্ত বিশিষ্ট বহুভুজের জন্য সূত্রটি স্পষ্ট। প্রকৃতপক্ষে, n শীর্ষবিন্দু এবং n প্রান্ত, পাশাপাশি দুটি মুখ F 1 F ¥

আমরা মুখ বরাবর অঙ্কন করে r মুখ সহ একটি গ্রাফে একটি নতুন মুখ যুক্ত করি F ¥ কিছু প্রাথমিক শৃঙ্খল যা সর্বাধিক গ্রাফের দুটি শীর্ষবিন্দুকে সংযুক্ত করে। যদি এই চাপটির r প্রান্ত থাকে, তবে আমাদের r - 1টি নতুন শীর্ষবিন্দু এবং একটি নতুন যুক্ত করতে হবে। মুখ কিন্তু তারপর

c' - p' + r' = (c + r - 1) - (p + r) + (r + 1) = c - p + r (= 2!)

আবেশন অনুমান দ্বারা.

ম্যাট্রিক্স উপস্থাপনা।

1. ঘটনা ম্যাট্রিক্স A.

ক)। একটি অনির্দেশিত গ্রাফের জন্য ইনসিডেন্স ম্যাট্রিক্সএকটি ম্যাট্রিক্স যার সারিগুলি শীর্ষবিন্দুর সাথে মিলে যায় এবং যার কলামগুলি প্রান্তের সাথে মিলে যায়৷ ম্যাট্রিক্স উপাদানটি 1 এর সমান হয় যদি শীর্ষবিন্দুটি একটি প্রান্তের সাথে ঘটে থাকে। অন্যথায়, ম্যাট্রিক্স উপাদানটি মান 0 নেয়।

খ)। একটি নির্দেশিত গ্রাফের জন্য, আপতন ম্যাট্রিক্সের উপাদানটি +1 হয় যখন চাপের শীর্ষবিন্দু ঘটনাটি চাপের প্রাথমিক শীর্ষবিন্দু হয় (অর্থাৎ, এই শীর্ষবিন্দু থেকে বৃত্তের উৎপত্তি হয়)। যখন চাপ একটি শীর্ষবিন্দুতে প্রবেশ করে তখন উপাদানটি -1 হয়। যদি শীর্ষবিন্দুটি চাপের সাথে সংঘটিত না হয়, তাহলে ম্যাট্রিক্স উপাদানটি 0 হয়।

2. চক্রের ম্যাট্রিক্স সি.

ক)। একটি অনির্দেশিত গ্রাফের জন্য, সাইকেল ম্যাট্রিক্সের সারিগুলি গ্রাফের সরল চক্রের সাথে মিলে যায় এবং কলামগুলি এর প্রান্তগুলির সাথে মিলে যায়৷ ম্যাট্রিক্স উপাদান a ij =1 যদি চক্র С i এ প্রান্ত e j থাকে। অন্যথায় একটি ij = 0।

খ)। একটি নির্দেশিত গ্রাফের জন্য একটি ij =1, -1 বা 0, C i এবং চাপ e j চক্রের স্থিতিবিন্যাস একই বা বিপরীত, বা এই চক্রটিতে চাপ e j আদৌ নেই তার উপর নির্ভর করে।

3. শীর্ষবিন্দু সংলগ্ন ম্যাট্রিক্স (বা সহজভাবে সংলগ্ন ম্যাট্রিক্স) V হল একটি ম্যাট্রিক্স যার সারি এবং কলামগুলি শীর্ষবিন্দুগুলির সাথে মিলে যায়, এবং একটি অনির্দেশিত গ্রাফের ক্ষেত্রে ম্যাট্রিক্স উপাদান a ij হল শীর্ষবিন্দু i এবং j সংযোগকারী প্রান্তের সংখ্যার সমান . একটি নির্দেশিত গ্রাফের জন্য, a ij উপাদানটি শীর্ষ i থেকে শীর্ষ j পর্যন্ত নির্দেশিত প্রান্তের সংখ্যার সমান।

এর সাথে সম্পর্কিত মৌলিক উপপাদ্য ম্যাট্রিক্স উপস্থাপনাগ্রাফ

1) n শীর্ষবিন্দু সহ একটি সংযুক্ত গ্রাফের (নির্দেশিত এবং অনির্দেশিত) ইনসিডেন্স ম্যাট্রিক্স A-এর র্যাঙ্ক (রৈখিকভাবে স্বাধীন কলামের সর্বাধিক সংখ্যা) সমান (n-1)।

2)। m প্রান্ত এবং n শীর্ষবিন্দু সহ একটি সংযুক্ত গ্রাফের চক্র ম্যাট্রিক্স C এর র্যাঙ্ক হল (m-n+1)।

একটি সংলগ্ন ম্যাট্রিক্স ব্যবহার করার একটি উদাহরণ।

নিম্নলিখিত ম্যাপিং দেখায় যে G 1 এবং G 2 গ্রাফগুলি আইসোমরফিক

সংলগ্ন ম্যাট্রিক্সে, সারি এবং কলামগুলি একই সাথে পারমিউট করা হয়, যা একটি সাদৃশ্য রূপান্তর এবং একটি পারমুটেশন ম্যাট্রিক্স ব্যবহার করে সঞ্চালিত হতে পারে।

A 2 \u003d PA 1 P", যেখানে

পি = , বা p ij = d p(i), j (ক্রোনেকার প্রতীক)

এবং R" হল ট্রান্সপোজড ম্যাট্রিক্স।

P ম্যাট্রিক্স খোঁজা কঠিন হতে পারে।

জি 1 এবং জি 2 এর আইসোমরফিজমের অর্থ হল A 1 এবং A 2 এর ইজেন ভ্যালু একই। যাইহোক, এই শর্তটি যথেষ্ট নয় (নীচের উদাহরণ)।

দিন ভি, ডিনির্বিচারে সেট, এবং ভি??।দ্বারা নির্দেশ করুন V 2কার্টেসিয়ান বর্গাকার সেট ভি.

নির্দেশিত গ্রাফ বা, সংক্ষেপে, ডিগ্রাফ জিএকটি ট্রিপল বলা হয় ভি, ডি, গ) : কোথায় গ- সেটে D সেটের কিছু ম্যাপিং V 2. উপাদান সেট করুন ভিএবং ডিবলা হয়, যথাক্রমে, ডাইগ্রাফের শীর্ষবিন্দু এবং চাপ জি. একটি ডাইগ্রাফের শীর্ষবিন্দু এবং আর্কসের সেট জিদ্বারা সুবিধাজনকভাবে চিহ্নিত করা হয়েছে ভিজিএবং ডিজিযথাক্রমে যদি একটি চ- অর্ক, তাহলে গ(চ) একটি আদেশযুক্ত জোড়া ( এবং, v), কোথায় এবং : v জে ভি. অর্ক চশীর্ষ থেকে বেরিয়ে আসছে এবংএবং শীর্ষে যায় v; তার পালা এবংএবং vচাপের শেষ শীর্ষবিন্দু বলা হয় চ; ভবিষ্যতে আমরা লিখব চ= (এবং কখনও কখনও এমনকি - চ = UVযদি বিভ্রান্তির কোন আশঙ্কা না থাকে)।

একটি নির্বিচারে ডিগ্রাফ লেখার সময়, এটি সাধারণত হিসাবে উপস্থাপন করা হবে জি = (ভি, ডি).

ডাইগ্রাফগুলি সাধারণত গ্রাফের জন্য চিত্রের মতো ডায়াগ্রাম ব্যবহার করে চিত্রিত করা হয়। একমাত্র পার্থক্য হল আর্ককে চিত্রিত করা রেখাটির একটি দিক রয়েছে।

প্রতিটি ডিগ্রাফের সাথে জি = (ভি, ডি) স্বাভাবিকভাবে গ্রাফ সংযোগ জি o = (ভি, ই), প্রদত্ত ডিগ্রাফের ভিত্তি বলা হয়। ভিত্তি প্রাপ্ত করার জন্য, এটি ডিগ্রাফে প্রয়োজনীয় জিপ্রতিটি চাপ প্রতিস্থাপন করুন চ= প্রান্ত e = uv

ডুমুর উপর. 8 ডিগ্রাফ এবং এর ভিত্তি দেখায়

চিত্র 8

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

যার মধ্যে

এই রুট বলা হয় (v সম্পর্কিত , v t) - আদর্শ রুট; চূড়া v oএবং v tবলা হয়, যথাক্রমে, এই ধরনের একটি রুটের প্রাথমিক এবং চূড়ান্ত শীর্ষবিন্দু। যদি একটি v o = v t, তারপর বা-রুটটিকে বন্ধ বলা হয়। প্যাটার্নটি তৈরি করে এমন আর্কের সংখ্যা হল প্যাটার্নের দৈর্ঘ্য।

আর্কসের পুনরাবৃত্তি ছাড়া একটি পথকে অরচেইন বলা হয়। একটি সাধারণ অরচেন হল এমন একটি অরচেন যার পুনরাবৃত্তির শীর্ষবিন্দু নেই (সম্ভবত একই শুরু এবং শেষ শীর্ষবিন্দুগুলি ছাড়া)। একটি বন্ধ সরল অরচেনকে বলা হয় অরসাইকেল বা কনট্যুর।

এর অস্তিত্ব যাচাই করা সহজ (এবং, v;) - orroute একটি সাধারণ ( এবং, v) - orcepi.

তারা বলে যে শীর্ষ vউপরে থেকে পৌঁছানো যায় এবং, যদি বিদ্যমান থাকে ( এবং, v)রুট ডাইগ্রাফ জিদৃঢ়ভাবে সংযুক্ত বা অপ-সংযুক্ত যদি এর কোনো শীর্ষবিন্দু অন্য কোনো শীর্ষবিন্দু থেকে পৌঁছানো যায়। স্পষ্টতই, একটি দৃঢ়ভাবে সংযুক্ত ডিগ্রাফ সংযুক্ত করা হয়; কথোপকথন, অবশ্যই, সত্য নয়.

চিত্রলেখ জিএটিকে প্রাচ্যযোগ্য বলা হয় যদি এটি কিছু দৃঢ়ভাবে সংযুক্ত ডিগ্রাফের ভিত্তি হয়।

উপপাদ্য 1.3. সংযুক্ত গ্রাফ জিপ্রাচ্যযোগ্য যদি এবং শুধুমাত্র যদি এর প্রতিটি প্রান্ত একটি সেতু না হয়।

প্রমাণ. গণনা যাক জিডাইগ্রাফের ভিত্তি এইচএবং জিএকটি সেতু রয়েছে e. তারপর ইন এইচএকটি চাপ আছে চ=, কোথায় এবং, v- পাঁজর শেষ e. স্পষ্টতই মধ্যে এইচনা ( u, v) - রুট। অতএব, গ্রাফ জিঅভিমুখী নয়।

ফিরে, গণনা যাক জিকোন সেতু নেই, যেমন গ্রাফের প্রতিটি প্রান্ত জিএকটি চক্রের মধ্যে রয়েছে। যেহেতু যেকোন চক্র একটি প্রাচ্যযোগ্য গ্রাফ, গ্রাফে জিএকটি সর্বাধিক ওরিয়েন্টেবল সাবগ্রাফ আছে এইচ. এর নিশ্চিত করা যাক এইচ = জি. ধরে নিন যে এই সমতা সন্তুষ্ট নয়। গ্রাফের সংযোগের কারণে জিশীর্ষবিন্দুতে একটি প্রান্ত ই ঘটনা আছে vথেকে এইচএবং শুয়ে নেই এইচ. অনুমান দ্বারা, প্রান্তটি কিছু চক্রের মধ্যে থাকে থেকে. দ্বারা নির্দেশ করুন প্রচক্র প্রান্তের সেট যা সাবগ্রাফের অন্তর্গত নয় এইচ. এটা দেখতে সহজ যে, যোগ এইচসেট থেকে সব প্রান্ত প্র, আমরা আবার একটি প্রাচ্যযোগ্য সাবগ্রাফ পাই, পছন্দের বিপরীতে এইচ.

দিন জিএকটি নির্বিচারে ডিগ্রাফ। ফলাফলের ডিগ্রি degvচূড়া vসমস্ত চাপের সংখ্যা vএকটি শুরু হিসাবে একইভাবে, প্রবেশের ডিগ্রি degvসমস্ত চাপের সংখ্যা যার জন্য শীর্ষবিন্দু vশেষ হয়. ডিগ্রাফ ধারণকারী পৃশিখর এবং tআর্কস বলা হবে ( n, t) একটি ডিগ্রাফ।

আউট-ডিগ্রী এবং ইন-ডিগ্রী নিম্নলিখিত সুস্পষ্ট উপায়ে সম্পর্কিত।

লেম্মা ঘ. দিন জি- ইচ্ছামত ( n, t) একটি ডিগ্রাফ। তারপর

এই দাবিটি সেকেন্ডের লেমা 1 এর মতো। 1.1; এটা প্রায়ই হ্যান্ডশেক orlemma হিসাবে উল্লেখ করা হয়.

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

মৌলিক ধারণা

আনুষ্ঠানিকভাবে, ডিগ্রাফ D = (V , E) (\displaystyle D=(V,E))অনেকগুলি নিয়ে গঠিত V (\ ডিসপ্লেস্টাইল V), যার উপাদান বলা হয় চূড়া, এবং সেট ই (\ ডিসপ্লেস্টাইল ই)শিরোনাম জোড়া আদেশ u , v ∈ V (\displaystyle u,v\in V).

অর্ক (u, v) (\displaystyle (u,v)) ঘটনাগতচূড়া u (\ প্রদর্শনশৈলী u)এবং v (\ প্রদর্শনশৈলী v). একই সঙ্গে তারা বলেন, ড u (\ প্রদর্শনশৈলী u) - প্রাথমিক শিখর arcs, এবং v (\ প্রদর্শনশৈলী v) - টার্মিনাল শিখর.

সংযোগ

রুটএকটি ডাইগ্রাফে শীর্ষবিন্দুগুলির একটি বিকল্প ক্রম বলা হয় এবং আর্কস, ধরনের v 0 ( v 0 , v 1 ) v 1 ( v 1 , v 2 ) v 2 । . . v n (\displaystyle v_(0)\(v_(0),v_(1)\)v_(1)\(v_(1),v_(2)\)v_(2)...v_(n))(শীর্ষগুলি পুনরাবৃত্তি করা যেতে পারে)। রুট দৈর্ঘ্য- এতে আর্কের সংখ্যা।

পথএখানে রুটআর্কসের পুনরাবৃত্তি না করে একটি ডিগ্রাফে, সহজ পথ- কোন পুনরাবৃত্ত শীর্ষবিন্দু. যদি একটি শীর্ষবিন্দু থেকে অন্য শীর্ষে যাওয়ার পথ থাকে তবে দ্বিতীয় শীর্ষে অর্জনযোগ্যপ্রথম থেকে.

সার্কিটএকটি বন্ধ আছে পথ.

জন্য অর্ধেক পথআর্কসের দিকের সীমাবদ্ধতা সরানো হয়, অর্ধেক পথএবং সেমি কনট্যুর.

ডাইগ্রাফ দৃঢ়ভাবে সংযুক্ত, বা সহজভাবে শক্তিশালী, যদি এর সমস্ত শীর্ষবিন্দু পারস্পরিক হয় অর্জনযোগ্য; একমুখী সংযুক্ত, বা সহজভাবে একতরফাযদি কোন দুটি শীর্ষবিন্দুর জন্য কমপক্ষে একটি অন্যটি থেকে পৌঁছানো যায়; শিথিলভাবে সংযুক্ত, বা সহজভাবে দুর্বল, যদি আর্কসের দিক উপেক্ষা করে, একটি সংযুক্ত (মাল্টি) গ্রাফ প্রাপ্ত হয়;

সর্বোচ্চ শক্তিশালীসাবগ্রাফ বলা হয় শক্তিশালী উপাদান; একতরফা উপাদানএবং দুর্বল উপাদানএকই ভাবে সংজ্ঞায়িত করা হয়।

ঘনীভবনডাইগ্রাফ ডি (\ ডিসপ্লেস্টাইল ডি)একটি ডিগ্রাফ বলা হয় যার শীর্ষবিন্দু শক্তিশালী উপাদান ডি (\ ডিসপ্লেস্টাইল ডি), এবং আর্ক ইন D ⋆ (\displaystyle D^(\star))সংশ্লিষ্ট উপাদানগুলির মধ্যে অন্তর্ভুক্ত শীর্ষবিন্দুগুলির মধ্যে অন্তত একটি চাপের উপস্থিতি নির্দেশ করে৷

অতিরিক্ত সংজ্ঞা

নির্দেশিত অ্যাসাইক্লিক গ্রাফবা হ্যামকএকটি কনট্যুরলেস ডিগ্রাফ।

প্রান্তের দিক বিপরীত করে প্রদত্ত একটি থেকে প্রাপ্ত নির্দেশিত গ্রাফ বলা হয় বিপরীত.

তিনটি নোড সহ সমস্ত ডিগ্রাফের চিত্র এবং বৈশিষ্ট্য

কিংবদন্তি: থেকে- দুর্বল, ওএস- একতরফা, এসএস- শক্তিশালী, এইচ- একটি নির্দেশিত গ্রাফ, জি- একটি হ্যামক (অ্যাসাইক্লিক), টি- একটি টুর্নামেন্ট

0 আর্কস	1 চাপ	2 আর্কস	3 আর্কস	4 আর্কস	5 আর্কস	6 আর্কস
খালি, এন, জি	এন, জি		ওএস	সিসি	সিসি	পূর্ণ, CC
		ওএস, এন, জি	সিসি, এন, টি	সিসি
		সি, এন, জি	ওএস, এন, জি, টি	ওএস
		সি, এন, জি	ওএস

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

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

গণিত জিনিসের বিষয়বস্তুর সাথে কাজ করে না, তবে তাদের গঠনের সাথে, এটিকে সামগ্রিকভাবে দেওয়া সমস্ত কিছু থেকে বিমূর্ত করে। শুধু এই কৌশলটি ব্যবহার করে, আমরা গ্রাফ সম্পর্কে কিছু বস্তু সম্পর্কে উপসংহার করতে পারি। এবং যেহেতু গ্রাফ তত্ত্বটি গণিতের একটি অংশ, তাই এটি কোন বিষয় নয়, নীতিগতভাবে, একটি বস্তু কি; একমাত্র গুরুত্বপূর্ণ বিষয় হল এটি একটি গ্রাফ কিনা, অর্থাৎ, এতে গ্রাফের জন্য প্রয়োজনীয় বৈশিষ্ট্য রয়েছে কিনা। অতএব, উদাহরণ দেওয়ার আগে, আমরা বিবেচনাধীন বস্তুর মধ্যে কেবলমাত্র কী, আমাদের মতে, আমাদেরকে একটি সাদৃশ্য দেখানোর অনুমতি দেবে, আমরা সাধারণ কিছু খুঁজি।

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

এটি মূলত একটি গ্রাফ। পাঁচটি কম্পিউটার হল শীর্ষবিন্দু, এবং তাদের মধ্যে সংযোগ (সংকেত পথ) হল প্রান্ত। কম্পিউটারগুলিকে শীর্ষবিন্দু দিয়ে প্রতিস্থাপন করে, আমরা একটি গাণিতিক বস্তু পাই - একটি গ্রাফ যার 10টি প্রান্ত এবং 5টি শীর্ষবিন্দু রয়েছে। আপনি নির্বিচারে শীর্ষবিন্দুগুলি সংখ্যা করতে পারেন, এবং অগত্যা যেভাবে এটি চিত্রে করা হয়েছে তা নয়। এটি লক্ষণীয় যে এই উদাহরণে কোনও লুপ ব্যবহার করা হয় না, অর্থাৎ, এমন একটি প্রান্ত যা শীর্ষবিন্দুটি ছেড়ে যায় এবং অবিলম্বে এটিতে প্রবেশ করে, তবে লুপগুলি সমস্যায় ঘটতে পারে।

এখানে গ্রাফ তত্ত্বে ব্যবহৃত কিছু গুরুত্বপূর্ণ নোটেশন রয়েছে:

• G=(V, E), এখানে G হল একটি গ্রাফ, V হল এর শীর্ষবিন্দু এবং E হল প্রান্ত;
• |ভি| - অর্ডার (শীর্ষের সংখ্যা);
• |ই| - গ্রাফ আকার (প্রান্তের সংখ্যা)।

আমাদের ক্ষেত্রে (চিত্র 1) |V|=5, |E|=10;

যখন কোন শীর্ষবিন্দু থেকে অন্য কোন শীর্ষে প্রবেশ করা যায়, তখন এই ধরনের গ্রাফ বলা হয় অনির্দেশিতসংযুক্ত গ্রাফ (চিত্র 1)। যদি গ্রাফ সংযুক্ত থাকে, কিন্তু এই শর্তটি সন্তুষ্ট না হয়, তাহলে এই ধরনের গ্রাফ বলা হয় ভিত্তিকঅথবা একটি ডিগ্রাফ (চিত্র 2)।

নির্দেশিত এবং অনির্দেশিত গ্রাফগুলিতে একটি শীর্ষবিন্দুর ডিগ্রির ধারণা রয়েছে। ভার্টেক্স ডিগ্রিএটি অন্যান্য শীর্ষবিন্দুর সাথে সংযোগকারী প্রান্তের সংখ্যা। একটি গ্রাফের সমস্ত ডিগ্রির যোগফল এর সমস্ত প্রান্তের দ্বিগুণ সংখ্যার সমান। চিত্র 2-এর জন্য, সমস্ত শক্তির যোগফল 20।

একটি ডাইগ্রাফে, একটি অনির্দেশিত গ্রাফের বিপরীতে, মধ্যবর্তী শীর্ষবিন্দু ছাড়াই শীর্ষবিন্দু h থেকে শীর্ষবিন্দুতে যাওয়া সম্ভব, শুধুমাত্র তখনই যখন একটি প্রান্ত h ছেড়ে s এ প্রবেশ করে, কিন্তু উল্টো নয়।

নির্দেশিত গ্রাফগুলির নিম্নলিখিত স্বরলিপি রয়েছে:

G=(V, A), যেখানে V হল শীর্ষবিন্দু, A হল নির্দেশিত প্রান্ত।

তৃতীয় ধরনের গ্রাফ- মিশ্রিতগ্রাফ (চিত্র 3)। তাদের নির্দেশিত প্রান্ত এবং অ-দিকনির্দেশক উভয়ই রয়েছে। আনুষ্ঠানিকভাবে, একটি মিশ্র গ্রাফ নিম্নরূপ লেখা হয়: G=(V, E, A), যেখানে বন্ধনীতে থাকা প্রতিটি অক্ষরও পূর্বে যাকে দায়ী করা হয়েছিল তা বোঝায়।

চিত্র 3-এর গ্রাফে, কিছু আর্ক নির্দেশিত [(e, a), (e, c), (a, b), (c, a), (d, b)], অন্যগুলি অ-নির্দেশিত [( e, d), (e, b), (d, c)…]।

প্রথম নজরে দুই বা ততোধিক গ্রাফ তাদের গঠনে ভিন্ন মনে হতে পারে, যা তাদের ভিন্ন উপস্থাপনার কারণে উদ্ভূত হয়। কিন্তু সব সময় তা হয় না। দুটি গ্রাফ নেওয়া যাক (চিত্র 4)।

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

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

আমরা বিবেচনা করেছি যে কোনও গ্রাফে, একটি পথ নির্বাচন করা সম্ভব এবং তদ্ব্যতীত, একাধিক। পথশীর্ষবিন্দুগুলির একটি ক্রম, যার প্রতিটি একটি প্রান্তের মাধ্যমে পরেরটির সাথে সংযুক্ত। যদি প্রথম এবং শেষ শীর্ষবিন্দু মিলে যায়, তাহলে এই ধরনের পথকে একটি চক্র বলা হয়। একটি পথের দৈর্ঘ্য এটি তৈরি করা প্রান্তের সংখ্যা দ্বারা নির্ধারিত হয়। উদাহরণস্বরূপ, চিত্র 4.a-এ, পথটি ক্রম [(e), (a), (b), (c)]। এই পথটি একটি সাবগ্রাফ, যেহেতু পরেরটির সংজ্ঞা এটিতে প্রযোজ্য, যথা: গ্রাফ G'=(V', E') গ্রাফ G=(V, E) এর একটি সাবগ্রাফ শুধুমাত্র V' এবং E' হলে V, E এর অন্তর্গত।

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

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

5.1। মৌলিক সংজ্ঞা এবং ধারণা

চলুন নির্দেশিত গ্রাফ সম্পর্কিত কিছু মৌলিক সংজ্ঞা এবং ধারণার পরিচয় দিয়ে শুরু করা যাক।

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

চিহ্নগুলি শীর্ষবিন্দুকে মনোনীত করতে ব্যবহৃত হয়, এবং চিহ্নগুলি আর্কগুলি মনোনীত করতে ব্যবহৃত হয়। যদি , তাহলে শেষ শীর্ষবিন্দু বলা হয়, এবং - প্রাথমিক শীর্ষবিন্দু, - শেষ শীর্ষবিন্দু। যে সমস্ত আর্কগুলির একই জোড়া শুরু এবং শেষ শীর্ষবিন্দু রয়েছে তাকে সমান্তরাল বলা হয়। একটি চাপকে একটি লুপ বলা হয় যদি ঘটনা শীর্ষবিন্দুটি এর শুরু এবং শেষ শীর্ষ উভয়ই হয়।

একটি নির্দেশিত গ্রাফের গ্রাফিকাল উপস্থাপনায়, শীর্ষবিন্দুগুলিকে বিন্দু বা বৃত্ত দ্বারা এবং প্রান্তগুলি (আর্কস) অংশগুলি দ্বারা উপস্থাপিত হয়।

বিন্দু বা বৃত্তের সাথে সংযোগকারী লাইনগুলি তাদের শেষবিন্দুকে প্রতিনিধিত্ব করে। উপরন্তু, arcs একটি স্থিতিবিন্যাস বরাদ্দ করা হয়, শুরু শীর্ষবিন্দু থেকে শেষ শীর্ষবিন্দুতে নির্দেশ করা একটি তীর দ্বারা নির্দেশিত।

উদাহরণস্বরূপ, যদি তাদের হয়), একটি নির্দেশিত গ্রাফ ডুমুর দ্বারা প্রতিনিধিত্ব করা যেতে পারে। 5.1। এই গ্রাফে - সমান্তরাল আর্কস, এবং - লুপ।

ভাত। 5.1। ওরিয়েন্টেড গ্রাফ।

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

একটি চাপকে তার প্রারম্ভিক শীর্ষবিন্দু থেকে বহির্গামী এবং তার চূড়ান্ত শীর্ষে প্রবেশ করা বলে। একটি শীর্ষবিন্দুকে বিচ্ছিন্ন বলা হয় যদি এতে কোনো আপতিত চাপ না থাকে।

একটি শীর্ষবিন্দুর ডিগ্রী হল এটিতে সংঘটিত আর্কসের সংখ্যা। একটি শীর্ষবিন্দুর ইন-ডিগ্রী হল V তে প্রবেশ করা আর্কের সংখ্যা এবং আউট-ডিগ্রী হল বহির্গামী আর্কের সংখ্যা। চিহ্ন এবং b" নির্দেশিত গ্রাফের সর্বনিম্ন আউট-ডিগ্রী এবং ইন-ডিগ্রী নির্দেশ করে। একইভাবে, চিহ্নগুলি যথাক্রমে সর্বাধিক আউট-ডিগ্রী এবং ইন-ডিগ্রী নির্দেশ করে।

যেকোনো শীর্ষবিন্দুর সেটগুলিকে নিম্নরূপ সংজ্ঞায়িত করা হয়েছে: . উদাহরণস্বরূপ, চিত্রের গ্রাফে। 5.1।

লক্ষ্য করুন যে লুপটি এই শীর্ষবিন্দুর প্রবেশ এবং প্রস্থান উভয়ের অর্ধ-ডিগ্রী বৃদ্ধি করে। নিম্নলিখিত দাবিটি এই সত্যের একটি ফলাফল যে প্রতিটি চাপ একটি নির্দেশিত গ্রাফের ইনপুট এবং আউটপুট উভয়ের সেমিডিগ্রির যোগফলের 1 দ্বারা বৃদ্ধি পায়।

উপপাদ্য 5.1। আর্কস সহ একটি নির্দেশিত গ্রাফে

ইন-ডিগ্রির যোগফল = আউট-ডিগ্রির যোগফল = মি।

একটি নির্দেশিত গ্রাফের সাবগ্রাফ এবং জেনারেটেড সাবগ্রাফগুলি একইভাবে সংজ্ঞায়িত করা হয়েছে যেমন অনির্দেশিত গ্রাফের ক্ষেত্রে (সেক. 1.2)৷

একটি নির্দেশিত গ্রাফ G এর আর্কস থেকে অভিযোজন অপসারণের ফলে একটি অনির্দেশিত গ্রাফকে অন্তর্নিহিত অনির্দেশিত গ্রাফ G বলা হয় এবং এটি দ্বারা চিহ্নিত করা হয়।

নির্দেশিত গ্রাফের একটি নির্দেশিত পথ হল শীর্ষবিন্দুগুলির একটি সসীম ক্রম

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

একটি ওরিয়েন্টেড রুটকে খোলা বলা হয় যদি এর শেষ শীর্ষবিন্দু ভিন্ন হয়, অন্যথায় এটি বন্ধ বলা হয়।

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

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

একটি বন্ধ ওরিয়েন্টেড চেইনকে ওরিয়েন্টেড সাইকেল বা কনট্যুর বলা হয় যদি টার্মিনালগুলি বাদ দিয়ে এর শীর্ষবিন্দুগুলি ভিন্ন হয়।

একটি নির্দেশিত গ্রাফকে বলা হয় অ্যাসাইক্লিক বা কনট্যুরলেস যদি এর কোন কনট্যুর না থাকে। উদাহরণস্বরূপ, চিত্র 1-এ নির্দেশিত গ্রাফটি অ্যাসাইক্লিক। 5.2।

ভাত। 5.2। অ্যাসাইক্লিক নির্দেশিত গ্রাফ।

ভাত। 5.3। একটি দৃঢ়ভাবে সংযুক্ত নির্দেশিত গ্রাফ।

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

একটি নির্দেশিত গ্রাফের চেইন, পথ এবং চক্র একইভাবে সংজ্ঞায়িত করা হয়।

একটি নির্দেশিত গ্রাফ সংযুক্ত বলা হয় যদি অন্তর্নিহিত অনির্দেশিত গ্রাফ সংযুক্ত থাকে।

নির্দেশিত গ্রাফ G এর একটি সাবগ্রাফকে গ্রাফ G এর একটি উপাদান বলা হয় যদি এটি গ্রাফের একটি উপাদান হয়

নির্দেশিত গ্রাফ G এর শীর্ষবিন্দুগুলিকে শক্তিশালীভাবে সংযুক্ত বলা হয় যদি G থেকে এবং পিছনের দিকে নির্দেশিত পথ থাকে। যদি দৃঢ়ভাবে সংযুক্ত হয় তাহলে, স্পষ্টতই, দৃঢ়ভাবে এর সাথে সংযুক্ত। প্রতিটি শীর্ষবিন্দু দৃঢ়ভাবে নিজের সাথে সংযুক্ত।

যদি একটি শীর্ষবিন্দু একটি শীর্ষবিন্দুর সাথে দৃঢ়ভাবে সংযুক্ত থাকে, তাহলে, যেমনটি দেখতে সহজ, শীর্ষবিন্দুটি শীর্ষবিন্দুর সাথে দৃঢ়ভাবে সংযুক্ত। তাই, এই ক্ষেত্রে, একজন সহজভাবে বলে যে শীর্ষবিন্দুগুলি দৃঢ়ভাবে সংযুক্ত।

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

একটি নির্দেশিত গ্রাফ G-এর সর্বাধিক দৃঢ়ভাবে সংযুক্ত সাবগ্রাফকে G-এর একটি দৃঢ়ভাবে সংযুক্ত উপাদান বলা হয়৷ যদি একটি নির্দেশিত গ্রাফ দৃঢ়ভাবে সংযুক্ত থাকে, তবে এটিতে একটি একক দৃঢ়ভাবে সংযুক্ত উপাদান থাকে, যথা নিজেই৷

একটি নির্দেশিত গ্রাফ বিবেচনা করুন। এটা সহজেই দেখা যায় যে এর প্রতিটি শীর্ষবিন্দু গ্রাফ G-এর ঠিক একটি দৃঢ়ভাবে সংযুক্ত উপাদানের অন্তর্গত। অতএব, দৃঢ়ভাবে সংযুক্ত উপাদানগুলির শীর্ষবিন্দুগুলির সেটগুলি গ্রাফের শীর্ষবিন্দু সেট Y-এর একটি বিভাজন তৈরি করে।

ভাত। 5.4। গ্রাফ এবং এর ঘনীভবন।

উদাহরণস্বরূপ, চিত্রে নির্দেশিত গ্রাফ। 5.4, ​​a তে শীর্ষবিন্দু সেটের সাথে তিনটি দৃঢ়ভাবে সংযুক্ত উপাদান রয়েছে এবং একটি নির্দেশিত গ্রাফের শীর্ষবিন্দু সেটের একটি পার্টিশন গঠন করে।

মজার বিষয় হল, একটি নির্দেশিত গ্রাফে আর্ক থাকতে পারে যা গ্রাফের কোনো দৃঢ়ভাবে সংযুক্ত উপাদানগুলিতে অন্তর্ভুক্ত নয়। উদাহরণস্বরূপ, কোন দৃঢ়ভাবে সংযুক্ত উপাদানগুলি চিত্রের গ্রাফে আর্কস অন্তর্ভুক্ত করে না। 5.4, ​​ক।

এইভাবে, যদিও "দৃঢ়ভাবে সংযুক্ত" বৈশিষ্ট্য গ্রাফের শীর্ষবিন্দুকে বিভক্ত করে, তবে এটি আর্কের সেটকে বিভক্ত নাও করতে পারে।

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

নির্দেশিত গ্রাফ G-এর দৃঢ়ভাবে সংযুক্ত উপাদানগুলির সমস্ত আর্কগুলির সংকোচনের ফলে গ্রাফটিকে G-এর ঘনীভূত গ্রাফ বলা হয়। চিত্রে দেখানো গ্রাফের ঘনীভবন। 5.4, ​​a, চিত্রে দেখানো হয়েছে। 5.4 খ.

গ্রাফের শীর্ষবিন্দুগুলি গ্রাফ G এর দৃঢ়ভাবে সংযুক্ত উপাদানগুলির সাথে মিলে যায় এবং উপাদানগুলির ঘনীভূত চিত্র বলা হয়।

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

আমরা এখন ন্যূনতমভাবে সংযুক্ত নির্দেশিত গ্রাফ সংজ্ঞায়িত করি এবং তাদের কিছু বৈশিষ্ট্য অধ্যয়ন করি।

একটি নির্দেশিত গ্রাফ G-কে ন্যূনতমভাবে সংযুক্ত বলা হয় যদি এটি দৃঢ়ভাবে সংযুক্ত থাকে, এবং কোনো চাপ অপসারণ করলে এটি তার দৃঢ়ভাবে সংযুক্ত সম্পত্তি থেকে বঞ্চিত হয়।

ভাত। 5.5। ন্যূনতম সংযুক্ত নির্দেশিত গ্রাফ।

ন্যূনতমভাবে সংযুক্ত, উদাহরণস্বরূপ, চিত্রে দেখানো গ্রাফটি। 5.5।

স্পষ্টতই, ন্যূনতমভাবে সংযুক্ত গ্রাফগুলিতে সমান্তরাল আর্ক এবং লুপ থাকতে পারে না।

আমরা জানি যে একটি অনির্দেশিত গ্রাফ ন্যূনতমভাবে সংযুক্ত থাকে যদি এবং শুধুমাত্র যদি এটি একটি গাছ হয় (উদাঃ 2.13)। উপপাদ্য 2.5 অনুসারে, একটি গাছের কমপক্ষে দুটি শীর্ষবিন্দু রয়েছে ডিগ্রী 1। তাই, ন্যূনতমভাবে সংযুক্ত অনির্দেশিত গ্রাফগুলিতে ডিগ্রী 1 এর কমপক্ষে দুটি শীর্ষবিন্দু রয়েছে।

নির্দেশিত গ্রাফের জন্য অনুরূপ ফলাফল স্থাপন করা যাক। একটি দৃঢ়ভাবে সংযুক্ত নির্দেশিত গ্রাফের যেকোনো শীর্ষবিন্দুর ডিগ্রী কমপক্ষে 2 হতে হবে, যেহেতু প্রতিটি শীর্ষে অবশ্যই বহির্গামী এবং আগত আর্ক থাকতে হবে। নিম্নলিখিত উপপাদ্যে, আমরা প্রমাণ করি যে একটি ন্যূনতম সংযুক্ত নির্দেশিত গ্রাফের কমপক্ষে দুটি শীর্ষবিন্দু ডিগ্রি 2 রয়েছে।