ডিগ্রাফ উদাহরণ। নির্দেশিত গ্রাফের সংজ্ঞা

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

নির্দেশিত এবং অনির্দেশিত গ্রাফ

লিঙ্ক(গ্রাফের একটি প্রান্তের দুই প্রান্তের ক্রম গুরুত্বপূর্ণ নয়) বলা হয় অনির্দেশিত .

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

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

লুপ করা গ্রাফ, মিশ্র গ্রাফ, খালি গ্রাফ, মাল্টিগ্রাফ, সাধারণ গ্রাফ, সম্পূর্ণ গ্রাফ

যদি গ্রাফ ধারণ করে loops, তারপর এই পরিস্থিতিটি বিশেষভাবে গ্রাফের প্রধান বৈশিষ্ট্যের সাথে "লুপ সহ" শব্দগুলি যোগ করে নির্দিষ্ট করা হয়েছে, উদাহরণস্বরূপ, "লুপ সহ ডাইগ্রাফ"। যদি গ্রাফে লুপ না থাকে, তাহলে "লুপ ছাড়া" শব্দ যোগ করা হয়।

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

শুধুমাত্র নিয়ে গঠিত গ্রাফ খালি চূড়া, বলা হয় খালি .

মাল্টিগ্রাফ এমন একটি গ্রাফ বলা হয় যেখানে জোড়া শীর্ষবিন্দু একাধিক প্রান্ত দ্বারা সংযুক্ত হতে পারে, অর্থাৎ একাধিক প্রান্ত, কিন্তু loops ছাড়া.

আর্কস (অর্থাৎ অনির্দেশিত), লুপ এবং একাধিক প্রান্ত ছাড়া একটি গ্রাফকে বলা হয় সাধারণ . নীচের চিত্রে একটি সাধারণ গ্রাফ দেখানো হয়েছে।

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

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

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

উদাহরণ 1নির্মাণ করুন সম্পূর্ণদ্বিপক্ষীয় গ্রাফ।

একটি সম্পূর্ণ দ্বিপক্ষীয় গ্রাফে দুটি সেটের শীর্ষবিন্দু এবং একটি সেটের শীর্ষবিন্দুকে অন্য সেটের শীর্ষবিন্দুর সাথে সংযোগকারী সমস্ত সম্ভাব্য লিঙ্ক থাকে (নীচের চিত্র)।

ইউলার গ্রাফ

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

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

উদাহরণ 2একই সংখ্যা সহ সম্পূর্ণ গ্রাফ nযে প্রান্তের প্রতিটি শীর্ষবিন্দু ঘটনা, একটি অয়লার গ্রাফ? উত্তরটি ব্যাখ্যা কর। উদাহরণ দাও.

উত্তর. যদি nএকটি বিজোড় সংখ্যা, তারপর প্রতিটি শীর্ষবিন্দু ঘটনা n-1 পাঁজর। এই ক্ষেত্রে, প্রদত্ত গ্রাফটি একটি অয়লার গ্রাফ। এই ধরনের গ্রাফের উদাহরণ নীচে দেখানো হয়েছে।

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

নিয়মিত গ্রাফ একটি সংযুক্ত গ্রাফ যার সমস্ত শীর্ষবিন্দু একই ডিগ্রি k. সুতরাং, উদাহরণ 2-এর জন্য চিত্রটি নিয়মিত গ্রাফের উদাহরণ দেখায়, যাকে এর শীর্ষবিন্দু 4-নিয়মিত এবং 2-নিয়মিত গ্রাফ বা 4র্থ ডিগ্রি এবং 2য় ডিগ্রির নিয়মিত গ্রাফের ডিগ্রি দ্বারা বলা হয়।

একটি নিয়মিত গ্রাফে শীর্ষবিন্দুর সংখ্যা k-ম ডিগ্রি কম হতে পারে না k+1 বিজোড় ডিগ্রির একটি নিয়মিত গ্রাফে কেবলমাত্র জোড় সংখ্যক শীর্ষবিন্দু থাকতে পারে।

উদাহরণ 3একটি নিয়মিত গ্রাফ তৈরি করুন যাতে ক্ষুদ্রতম চক্রের দৈর্ঘ্য 4 থাকে।

সমাধান। আমরা নিম্নোক্তভাবে তর্ক করি: প্রদত্ত শর্ত পূরণ করার জন্য চক্রের দৈর্ঘ্যের জন্য, গ্রাফের শীর্ষবিন্দুর সংখ্যা চারটির একাধিক হওয়া প্রয়োজন। শীর্ষবিন্দুর সংখ্যা চার হলে নিচের চিত্রে দেখানো গ্রাফটি পাওয়া যাবে। এটি নিয়মিত, তবে এর ক্ষুদ্রতম চক্রের দৈর্ঘ্য 3।

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

হ্যামিলটোনিয়ান গ্রাফ

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

উদাহরণ 4একটি দ্বিপক্ষীয় গ্রাফ দেওয়া হয়েছে যার মধ্যে n- সেট থেকে শীর্ষবিন্দুর সংখ্যা ক, ক মি- সেট থেকে শীর্ষবিন্দুর সংখ্যা খ. কোন ক্ষেত্রে গ্রাফটি একটি ইউলেরিয়ান গ্রাফ, এবং কোন ক্ষেত্রে এটি একটি হ্যামিলটোনিয়ান গ্রাফ?

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

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

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

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

এটি মূলত একটি গ্রাফ। পাঁচটি কম্পিউটার হল শীর্ষবিন্দু, এবং তাদের মধ্যে সংযোগ (সংকেত পথ) হল প্রান্ত। কম্পিউটারগুলিকে শীর্ষবিন্দু দিয়ে প্রতিস্থাপন করে, আমরা একটি গাণিতিক বস্তু পাই - একটি গ্রাফ যার 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 এর অন্তর্গত।

প্রথম পাঠে, একটি গ্রাফের ধারণাটি প্রবর্তন করে, আমরা ক্রীড়া দলের প্রতিযোগিতাকে একটি উদাহরণ হিসাবে বিবেচনা করেছি। আমরা। দুটি দলকে সংযুক্ত করেছে, A এবং C বলে, এজ এসি দিয়ে যখন এই দলগুলি ইতিমধ্যে একে অপরের সাথে খেলছিল। যাইহোক, এই ধরনের একটি গ্রাফ একটি খুব গুরুত্বপূর্ণ প্রশ্নের উত্তর দেয় না: কে ঠিক গেমটি জিতেছে?
এই ঘাটতি সহজেই দূর করা যায়। যদি A দল C এর বিরুদ্ধে জয়ী হয়, আমরা A থেকে C পর্যন্ত নির্দেশিত প্রান্ত AC-তে একটি তীর রাখতে রাজি হব। ধরুন আমরা ইতিমধ্যেই খেলা সমস্ত গেমের ফলাফল জানি এবং গ্রাফ চিত্রে যোগ করি। 1 সংশ্লিষ্ট তীর; চিত্রে দেখানো গ্রাফে এই ফলাফলটি দেখা যাক। 58.

চিত্র 58।

এই গ্রাফটি দেখায় যে টিম A C কে পরাজিত করেছে, টিম F A এর কাছে হেরেছে এবং B টিম C, E, F ইত্যাদির বিরুদ্ধে সমস্ত গেম জিতেছে।

প্রান্তগ্রাফ বলা হয় ভিত্তিক, যদি একটি শীর্ষবিন্দু বিবেচনা করা হয় পাঁজরের শুরু, এবং অন্যান্য - শেষ.
যে গ্রাফের সমস্ত প্রান্ত ভিত্তিক তাকে বলা হয় অভিযোজনগণনা.
নির্দেশিত গ্রাফের একই শীর্ষবিন্দু কিছু প্রান্তের জন্য শুরু এবং অন্যগুলির জন্য শেষ হিসাবে কাজ করতে পারে। তদনুসারে, শীর্ষের দুটি ডিগ্রি আলাদা করা হয়: প্রস্থান ডিগ্রী এবং এন্ট্রি ডিগ্রী।
প্রস্থান ডিগ্রীএকটি নির্দেশিত গ্রাফের শীর্ষবিন্দু হল A (স্বরলিপি: d+(A)) ছেড়ে থাকা প্রান্তের সংখ্যা।
একটি নির্দেশিত গ্রাফের একটি শীর্ষবিন্দু A এর প্রবেশের ডিগ্রি হল এন্ট্রির সংখ্যা কপ্রান্ত (প্রতীক: d-(A))।
যদি একটি খেলা ড্র শেষ হয়? আমরা সংশ্লিষ্ট প্রান্তগুলিকে অনির্দেশিত রেখে গ্রাফে টাই ফলাফলগুলি প্রতিফলিত করতে পারি। এটা করতে গিয়ে আমরা তথাকথিত পাই smশ্যানি গণনা, যার নির্দেশিত এবং অনির্দেশিত উভয় প্রান্ত রয়েছে।
নির্দেশিত গ্রাফে একটি পথ A1 থেকে An পর্যন্ত G হল ওরিয়েন্টেড প্রান্তগুলির একটি ক্রম<А1; А2>, <А2; А3>, ..., <Аn-1; Аn>, যেমন প্রতিটি পূর্ববর্তী প্রান্তের শেষ পরেরটির শুরুর সাথে মিলে যায় এবং কোন প্রান্ত একবারের বেশি ঘটে না।

ভাত। 59
যদি নির্দেশিত গ্রাফে G থেকে একটি পথ থাকে ক B থেকে, তারপর থেকে ফিরে ভিতরেপ্রতি কনাও হতে পারে (চিত্র 59)।
যদি A থেকে B পর্যন্ত একটি নির্দেশিত পথ থাকে তবে B বলা হয় পৌঁছানোমাএ থেকে
চিত্র 38 বি-তে জি কলামে অর্জনযোগ্য
A থেকে A, B থেকে A পৌঁছানো যায় না।
সহজ উপায়একটি নির্দেশিত গ্রাফ হল এমন একটি পথ যেখানে কোনো শীর্ষবিন্দু একাধিকবার থাকে না। বন্ধ পথনির্দেশিত গ্রাফে একটি নির্দেশিত চক্র বলা হয়।
দীর্ঘ পথএই পথের প্রান্তের সংখ্যা।
দূরত্বনির্দেশিত গ্রাফে A থেকে B হল A থেকে B পর্যন্ত সবচেয়ে ছোট পথের দৈর্ঘ্য। A থেকে B পর্যন্ত কোনো পথ না থাকলে A থেকে B পর্যন্ত দূরত্বকে অসীম বলা হয় এবং চিহ্নিত করা হয়? A থেকে B পর্যন্ত দূরত্ব S (AB) দ্বারা চিহ্নিত করা হবে। চিত্র 38-এর গ্রাফের জন্য
S (AB) \u003d 1, S (CB) - 2, S (BC) \u003d?।
সমস্যা 9.1.
সমুদ্র উপকূলের একটি রিসর্ট শহরে, একমুখী ট্র্যাফিক স্থাপনের পরে, দেখা গেল যে রাস্তার সংখ্যা আপনি প্রতিটি চৌরাস্তায় প্রবেশ করতে পারেন এমন রাস্তার সংখ্যার সমান যেগুলি দিয়ে আপনি এটি ছেড়ে যেতে পারেন। প্রমাণ করুন যে একটি টহল পথ প্রস্তাব করা সম্ভব যেটি একই জায়গায় শুরু এবং শেষ হয় এবং প্রতিটি রাস্তার অংশের মধ্য দিয়ে ঠিক একবার চলে যায়।
সমাধান।
আসুন আমরা একটি ডিগ্রাফ জি তৈরি করি যা শহরের আন্দোলনকে সংজ্ঞায়িত করে।
ডাইগ্রাফ বলা হয় সংযুক্ত,যদি তাদের অভিযোজন বিবেচনা না করে এর যেকোনো শীর্ষবিন্দু থেকে আর্ক বরাবর অন্য কোনো স্থানে যাওয়া সম্ভব হয়। সংযুক্ত ডাইগ্রাফ বলা হয় অয়লার,যদি এটির একটি অয়লার চক্র থাকে।
উপপাদ্য 12. একটি সংযুক্ত ডিগ্রাফ হল অয়লার যদি এবং শুধুমাত্র যদি এর প্রতিটি শীর্ষের জন্যvসমতাd- (v) = d+ (v) .
উপপাদ্যটি ঠিক একইভাবে প্রমাণিত হয়েছে যেমন সমস্যা 4.2-এর উপপাদ্য।
এটি সমস্যার শর্তগুলি থেকে অনুসরণ করে যে নির্মিত গ্রাফ G-এর শীর্ষবিন্দুগুলির জন্য, সমতা d-(v) = d+(v) সন্তুষ্ট। অতএব, অয়লার গ্রাফ G, এবং অয়লার চক্র পছন্দসই টহল পথ নির্ধারণ করবে।
সমস্যা 9.2।
সমতলে সীমিত সংখ্যক বিন্দু চিহ্নিত করা হয়েছে। কিছু জোড়া বিন্দু হল ভেক্টরের শুরু এবং শেষ এবং যেকোনো বিন্দুতে প্রবেশকারী ভেক্টরের সংখ্যা এটি ছেড়ে যাওয়া ভেক্টরের সংখ্যার সমান। ভেক্টরের যোগফল নির্ণয় কর।
সমাধান।
সমতলের বিন্দুগুলি ভেক্টরের সাথে মিলিত হয়ে একটি ডিগ্রাফ G গঠন করে। একটি ডিগ্রাফের চক্র, যার সমস্ত শীর্ষবিন্দু আলাদা, তাকে বলা হয় কনট্যুর
উপপাদ্য 13. সংযুক্ত ডিগ্রাফজিঅয়লার যদি এবং শুধুমাত্র যদিজিকনট্যুরগুলির মিলন যা জোড়ায়িকভাবে সাধারণ প্রান্ত থাকে না।
প্রমাণ। প্রয়োজন। জি একটি অয়লার ডিগ্রাফ হতে দিন। এটির যেকোনো শীর্ষ u1 বিবেচনা করুন। আসুন কিছু চাপ (u1, u2) বরাবর শীর্ষবিন্দু u1 ছেড়ে দিই। এটি করা যেতে পারে, যেহেতু ডিগ্রাফ G সংযুক্ত। যেহেতু d-(u2) = d+(u2), তাই চাপ (u2, u3) বরাবর শীর্ষবিন্দু u2 ছেড়ে যাওয়া সম্ভব। . ডাইগ্রাফ G-এর একটি সীমিত সংখ্যক শীর্ষবিন্দু রয়েছে, তাই আমরা কিছু শীর্ষবিন্দুতে শেষ করি যেখানে আমরা আগে ছিলাম। চেইনের যে অংশটি শুরু হয় এবং w এ শেষ হয় সেটি হল পাথ C1। ডিগ্রাফ G থেকে কনট্যুর C1 এর আর্কগুলি সরান . ফলস্বরূপ ডিগ্রাফ G1-এ (সম্ভবত সংযোগ বিচ্ছিন্ন), C এর অন্তর্গত শীর্ষবিন্দুগুলির প্রবেশ এবং প্রস্থান ডিগ্রী এক দ্বারা হ্রাস পেয়েছে, অবশিষ্ট শীর্ষবিন্দুগুলির প্রবেশ এবং প্রস্থান ডিগ্রী পরিবর্তিত হয়নি। তাই, ডিগ্রাফ C1-এর যেকোনো শীর্ষ v এর জন্য, সমতা d-(v) = d+(v) ধরে থাকবে। অতএব, ডিগ্রাফ জি 1-এ, আমরা কনট্যুর সিকে একক আউট করতে পারি 2 ইত্যাদি
একটি অয়লার চক্রে কনট্যুরগুলিকে একত্রিত করে পর্যাপ্ততা প্রমাণিত হয় (সমস্যা 4.2-এ উপপাদ্যটির প্রমাণ দেখুন)।
উপপাদ্য প্রমাণিত হয়েছে। সম্ভবত আমাদের সমস্যার ভেক্টর সংজ্ঞায়িত ডিগ্রাফ G সংযুক্ত নয়। ডিগ্রাফের প্রতিটি সংযুক্ত অংশে প্রমাণিত উপপাদ্য প্রয়োগ করে, আমরা ভেক্টরগুলির একটি বিভাজন কনট্যুরগুলিতে পাই। একটি কনট্যুরের অন্তর্গত ভেক্টরের যোগফল শূন্যের সমান। অতএব, সমস্ত ভেক্টরের যোগফল শূন্যের সমান।

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

মৌলিক ধারণা

আনুষ্ঠানিকভাবে, ডিগ্রাফ 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
		ওএস, এন, জি	সিসি, এন, টি	সিসি
		সি, এন, জি	ওএস, এন, জি, টি	ওএস
		সি, এন, জি	ওএস

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

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

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

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

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

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

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

একমুখী.

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

প্রশ্ন হল, শহরের রাস্তাগুলিকে এমনভাবে কোন্‌ অবস্থায় রাখা যায় যে রাস্তায় রাস্তার নিয়ম লঙ্ঘন না করে যে কোনও পয়েন্ট থেকে অন্য যে কোনও জায়গায় গাড়ি চালানো যায়।

গ্রাফ তত্ত্বের ভাষায়, এটি নিম্নরূপ প্রণয়ন করা হয়েছে: কোন অবস্থায় গ্রাফ 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) . যদি ই - সংযোগকারী প্রান্ত, এটি দ্বি-পার্শ্বযুক্ত থাকবে এবং তারপরে সেখান থেকে যাওয়া সম্ভব হবে ক প্রতি ভিতরে এবং পিছনে (চিত্র 2+3)।

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

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

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

যদি ই - সংযোগকারী পাঁজর এবি , তাহলে এটি দ্বিমুখী থাকবে। তারপর কোন শীর্ষবিন্দু জন্য এক্স গণনা এইচ কেউ একটি ওরিয়েন্টেড চেইন খুঁজে পেতে পারেন আর সংযোগ A এর সাথে X , যার অর্থ (প্রান্তের মাধ্যমে ই ) , এবং সাথে ভিতরে . উপর থেকে ফিরে ভিতরে শেষ প্রান্তে ই আপনি যেতে পারেন ক , এবং তারপর - ওরিয়েন্টিং চেইন বরাবর জেড - থেকে ক প্রতি এক্স (চিত্র a+5)। সংযুক্ত করা হচ্ছে ই প্রতি এইচ , আমরা গ্রাফের বেশিরভাগই পাব জি প্রয়োজনীয় বৈশিষ্ট্য সহ। যদি প্রান্ত E \u003d (A, B) চক্রাকার, এটি কিছু চক্রের অন্তর্গত সঙ্গে . আমরা জন্য দিক নির্ধারণ সঙ্গে থেকে ক আগে ভিতরে এবং আরও বরাবর সঙ্গে প্রথম শিখরে ডি থেকে সঙ্গে মালিক এইচ (চিত্র 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) থাকে তবে R * এর সাথে সম্পর্কিত গ্রাফ G * এর একটি প্রান্ত (c, a) থাকতে হবে। অন্য কথায়, গ্রাফ G * হল G এর বিপরীত, অর্থাৎ G এর মতো একই প্রান্ত সহ একটি গ্রাফ, কিন্তু বিপরীতমুখী।

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

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

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

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

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

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

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

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

1)। রিফ্লেক্সিভিটি: a ~ a;

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

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

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

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

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

আংশিক আদেশ।

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

1)। রিফ্লেক্সিভিটি: A Ê A

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

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

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

1)। অ্যান্টি-রিফ্লেক্সিভিটি: 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 পর্যন্ত নির্দেশিত প্রান্তের সংখ্যার সমান।

গ্রাফের ম্যাট্রিক্স উপস্থাপনা সম্পর্কিত Onovye উপপাদ্য।

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 এর ইজেন ভ্যালু একই। যাইহোক, এই শর্তটি যথেষ্ট নয় (নীচের উদাহরণ)।