গ্রাফ তত্ত্বের প্রয়োগসমূহ
প্ল্যানার গ্রাফ
একটি গ্রাফ জি প্ল্যানার হিসাবে বলা হয় যদি এটি এমন একটি ফ্যাশনে কোনও সমতলে প্রতিনিধিত্ব করা যায় যে অনুভূমিকাগুলি সমস্ত স্বতন্ত্র বিন্দু, প্রান্তগুলি সহজ বক্ররেখা এবং কোনও দুটি প্রান্ত তাদের টার্মিনাল ব্যতীত একে অপরের সাথে মিলিত হয় না। উদাহরণস্বরূপ, চিত্র 4 এ হিসাবে দেখানো হয়েছে, কে 4, চারটি শীর্ষে সম্পূর্ণ গ্রাফটি প্ল্যানার।
দুটি গ্রাফকে হোমোমোরফিক বলা হয় যদি উভয়ই একই গ্রাফ থেকে প্রান্তের উপ-বিভাগ দ্বারা প্রাপ্ত করা যায়। উদাহরণস্বরূপ, চিত্র 4 এ এবং চিত্র 4 বি এর গ্রাফগুলি হোমিওমোরফিক।
কে এম, এন গ্রাফ এমন একটি গ্রাফ যার জন্য ভার্টেক্স সেটটি দুটি উপসংশে বিভক্ত করা যেতে পারে, একটি মিউটারিক্টস এবং একটি অপরটি এন উল্লম্ব সহ। একই উপসেটের যে কোনও দুটি উল্লম্ব হ'ল অনাডজ্যাসেন্ট, অন্যদিকে বিভিন্ন উপসর্গের যে কোনও দুটি উল্লম্ব সংলগ্ন। 1930 সালে পোলিশ গণিতবিদ কাজিমিয়েরেজ কুরাতোভস্কি নিম্নলিখিত বিখ্যাত উপপাদ্যটি প্রমাণ করেছিলেন:
গ্রাফ জি প্ল্যানার হওয়ার জন্য একটি প্রয়োজনীয় এবং পর্যাপ্ত শর্ত হ'ল এটিতে চিত্র 5 এ দেখানো কে 5 বা কে 3,3 এর কোনও সাবগ্রাফিক হোমোমর্ফিক নেই ।
গ্রাফ জি একটি প্রাথমিক সংকোচন একটি নতুন গ্রাফ জি জি এর একটি রূপান্তর হয় 1, এই ধরনের দুই সংলগ্ন ছেদচিহ্ন তোমার দর্শন লগ করা এবং জি এর υ জি W একটি নতুন প্রান্তবিন্দু দ্বারা প্রতিস্থাপিত হয় 1 এবং W জি সংলগ্ন 1 সব ছেদচিহ্ন করতে যা হয় আপনি বা G জি সংলগ্ন। একটি গ্রাফ জি * কে জি এর সংকোচনের কথা বলা হয় যদি জি * থেকে প্রাথমিক সংকোচনের অনুক্রমের সাহায্যে পাওয়া যায়। নীচেরটি ১৯৩37 সালে জার্মান গণিতবিদ কে। ওয়াগনারের কারণে প্ল্যানার গ্রাফের আরও একটি বৈশিষ্ট্য রয়েছে।
একটি গ্রাফ প্ল্যানার হয় যদি এবং কেবলমাত্র এটি কে 5 বা কে 3,3 এর সাথে সংকোচনযোগ্য নয় ।
চার রঙের মানচিত্রের সমস্যা
এক শতাব্দীরও বেশি সময় ধরে চার-বর্ণের মানচিত্র সমস্যার সমাধান প্রতিটি বিশ্লেষক যিনি এটি চেষ্টা করেছিলেন তা বন্ধ করে দিয়েছে। এই সমস্যাটি হয়তো মবিয়াসের দৃষ্টি আকর্ষণ করেছে, তবে এটির প্রথম লিখিত উল্লেখটি ফ্রান্সিস গুথ্রি থেকে তাঁর ভাই, আগস্টাস ডি মরগানের শিক্ষার্থী, ১৮৫২ সালে একটি চিঠি বলে মনে হয়েছে।
সমস্যাটি পরিকল্পনাকারী মানচিত্রগুলি নিয়ে উদ্বেগ প্রকাশ করে - এটি হ'ল বিমানের সাব-ডিভিশনগুলিকে সরল বদ্ধ বাঁক দ্বারা আবদ্ধ ননওভারল্যাপিং অঞ্চলগুলিতে। ভৌগলিক মানচিত্রগুলিতে এটি যথাযথভাবে পর্যবেক্ষণ করা হয়েছে, যতগুলি বিশেষ ক্ষেত্রে চেষ্টা করা হয়েছে, বেশিরভাগ ক্ষেত্রে, অঞ্চলগুলিকে রঙ করার জন্য সর্বাধিক চারটি রঙের প্রয়োজন হয় যাতে দুটি সীমা যা একটি সাধারণ সীমানা ভাগ করে সেখানে সবসময় আলাদা আলাদা হয় এবং কমপক্ষে চারটি রঙের প্রয়োজনীয় কিছু ক্ষেত্রে। (যে অঞ্চলগুলি কেবলমাত্র এক পর্যায়ে মিলিত হয়, যেমন আমেরিকার কলোরাডো এবং অ্যারিজোনা রাজ্যগুলির একটি সাধারণ সীমানা রয়েছে বলে মনে করা হয় না)। এই অভিজ্ঞতামূলক পর্যবেক্ষণের একটি আনুষ্ঠানিককরণ যা "চার বর্ণের উপপাদ্য" নামে পরিচিত তাকে গঠন করে। সমস্যাটি হ'ল প্রতিটি পরিকল্পনাকারী মানচিত্রের ক্ষেত্রে এটি হ'ল দৃ.়তা প্রমাণ বা অস্বীকার করা। এই তিনটি রঙই যথেষ্ট হবে না তা সহজেই প্রদর্শিত হয়, যেখানে পাঁচটি রঙের পর্যাপ্ততা 1890 সালে ব্রিটিশ গণিতবিদ পি জে হিউড প্রমাণ করেছিলেন।
1879 সালে এ বি কেম্পে নামে একজন ইংরেজ চার বর্ণের সমস্যার সমাধানের প্রস্তাব দেয়। যদিও হিউউড দেখিয়েছেন কেম্পের যুক্তি ত্রুটিযুক্ত ছিল, তবুও তদন্তে এর দুটি ধারণাগুলি ফলপ্রসূ প্রমাণিত হয়েছিল। এর মধ্যে একটি, যা অপ্রয়োজনীয়তা বলা হয়, সঠিকভাবে একটি মানচিত্র তৈরির অসম্ভবতাকে জানায় যেখানে চারটি কনফিগারেশনের প্রত্যেকটিই অনুপস্থিত (এই কনফিগারেশনে দুটি প্রতিবেশী একটি অঞ্চল নিয়ে গঠিত, একটি তিনজনের সাথে একটি, চারজনের সাথে একটি এবং পাঁচটির সাথে একটি)। দ্বিতীয় ধারণাটি, হ্রাসযোগ্যতা, কেম্পের বৈধ প্রমাণ থেকে এর নামটি নিয়েছে যে যদি সেখানে কোনও মানচিত্র থাকে যাতে কমপক্ষে পাঁচটি বর্ণের প্রয়োজন হয় এবং এতে চারটি (বা তিন বা দুই) প্রতিবেশী অঞ্চল রয়েছে তবে অবশ্যই পাঁচটি প্রয়োজন এমন একটি মানচিত্র থাকতে হবে সংখ্যক অঞ্চলের জন্য রঙ। পাঁচটি প্রতিবেশী অঞ্চল নিয়ে একটি অঞ্চলের মানচিত্রের হ্রাসযোগ্যতা প্রমাণের জন্য কেম্পের প্রয়াস ভুল ছিল, তবে ১৯ 1976 সালে কেনেথ আপেল এবং মার্কিন যুক্তরাষ্ট্রের ওল্ফগ্যাং হেকেন প্রকাশিত একটি প্রমাণে এটি সংশোধন করেছিল। তাদের প্রমাণটি কিছু সমালোচনা আকর্ষণ করেছিল কারণ এটি 1,936 স্বতন্ত্র মামলার মূল্যায়ন প্রয়োজন, যার মধ্যে প্রতিটি 500,000 হিসাবে লজিক্যাল অপারেশন জড়িত। অ্যাপেল, হ্যাকেন এবং তাদের সহযোগীরা এমন প্রোগ্রাম তৈরি করেছিলেন যা একটি বড় ডিজিটাল কম্পিউটারের পক্ষে এই বিবরণগুলি পরিচালনা করতে সক্ষম করে। কম্পিউটারটি কাজটি সম্পাদন করতে এক হাজার ঘন্টারও বেশি সময় প্রয়োজন এবং ফলস্বরূপ আনুষ্ঠানিক প্রমাণটি কয়েকশ পৃষ্ঠার দীর্ঘ।
ইউলেরিয়ান চক্র এবং কনিগসবার্গ ব্রিজ সমস্যা
একটি মাল্টিগ্রাফ জিতে প্রতিটি জোড়ের সাথে একটি ফ্রিকোয়েন্সি এফ ≥ 1 সংযুক্ত করে ভি (জি) এর স্বতন্ত্র উপাদানগুলির আনর্ডারড জোড়গুলির সেটের একটি খালি খালি সেট ভি (জি) এবং একটি উপসেট ই (জি) থাকে। যদি ফ্রিকোয়েন্সি এফের সাথে জুটি (x 1, x 2) ই (জি) এর হয়, তবে এক্স 1 এবং x 2 টি শীর্ষ প্রান্তের সাথে শীর্ষে যোগ করা হবে।
একটি মাল্টিগ্রাফ জি-এর একটি ইউলরিয়ান চক্র একটি বদ্ধ চেইন যা প্রতিটি প্রান্তটি একবারে একবারে উপস্থিত হয়। অয়লার দেখিয়েছেন যে একটি মাল্টিগ্রাফের মধ্যে একটি ইউলরিয়ান চক্র রয়েছে এবং কেবল যদি এটি সংযুক্ত থাকে (বিচ্ছিন্ন বিন্দুগুলি বাদে) এবং বিজোড় ডিগ্রির শীর্ষাংশের সংখ্যা হয় শূন্য বা দুটি হয়।
এই সমস্যাটি প্রথমে নিম্নলিখিত পদ্ধতিতে উত্থিত হয়েছিল। প্রেগেল নদী, এর দুটি শাখার সংমিশ্রণে গঠিত, কনিগসবার্গ শহর দিয়ে প্রবাহিত হয়েছিল এবং কনিফফ দ্বীপের দুপাশে প্রবাহিত হয়েছে। চিত্র 7 এ হিসাবে দেখানো হয়েছে সেখানে সাতটি সেতু ছিল। নগরবাসী অবাক হয়েছিলেন যে একবার এবং একবারে একবারে প্রতিটি সেতুটি হাঁটার পক্ষে এবং পার হওয়া সম্ভব ছিল কিনা? এটি চিত্র 6 বিতে মাল্টিগ্রাফের জন্য একটি ইউুলেরিয়ান চক্র সন্ধানের সমতুল্য। ইউলার এটিকে অসম্ভব বলে দেখিয়েছিলেন কারণ বিজোড় ক্রমের চারটি শীর্ষকোষ রয়েছে।
