Heawood graph
গ্রাফ তত্ত্বের গাণিতিক ক্ষেত্রে, হেউড গ্রাফ হল 14টি শীর্ষ এবং 21টি প্রান্ত সহ একটি অনির্দিষ্ট গ্রাফ, যার নামকরণ পার্সি জন হেউডের নামে করা হয়েছে। সমন্বিত বৈশিষ্ট্য গ্রাফটি ঘন, এবং গ্রাফের সমস্ত চক্রের ছয় বা ততোধিক প্রান্ত থাকে। প্রতিটি ছোট কিউবিক গ্রাফের ছোট চক্র থাকে, তাই এই গ্রাফটি 6-কেজের, যা ঘের 6-এর সবচেয়ে ছোট কিউবিক গ্রাফ। এটি একটি দূরত্ব-ক্ষণস্থায়ী গ্রাফ (ফস্টার আদমশুমারি দেখুন) এবং তাই দূরত্ব নিয়মিত। হিউড গ্রাফে 24টি নিখুঁত মিল রয়েছে; প্রতিটি মিলনের জন্য, মিলনের মধ্যে না থাকা প্রান্তগুলির সেট একটি হ্যামিল্টনিয়ান চক্র গঠন করে। উদাহরণস্বরূপ, চিত্রটি একটি চক্রের উপর স্থাপন করা গ্রাফের শীর্ষগুলি দেখায়, যার সাথে চক্রের অভ্যন্তরীণ তির্যকগুলি মিলে যায়। চক্রের প্রান্তগুলিকে দুটি ম্যাচে বিভক্ত করে, আমরা আটটি ভিন্ন উপায়ে হিউড গ্রাফকে তিনটি নিখুঁত ম্যাচে (অর্থাৎ, এর প্রান্তগুলিকে 3-রঙে) ভাগ করতে পারি। প্রতি দুটি নিখুঁত মিল এবং প্রতি দুটি হ্যামিল্টনিয়ান চক্র গ্রাফের প্রতিসাম্য দ্বারা একে অপরের মধ্যে রূপান্তরিত হতে পারে। হিউড গ্রাফে 28টি ছয়-ভার্টেক্স চক্র রয়েছে। প্রতিটি 6-চক্র ঠিক তিনটি অন্য 6-চক্র থেকে বিচ্ছিন্ন; এই তিনটি 6-চক্রের মধ্যে, প্রতিটি হল অন্য দুটির প্রতিসম পার্থক্য। প্রতি 6-চক্রে একটি নোড এবং 6-চক্রের প্রতিটি বিচ্ছিন্ন জুটির জন্য একটি প্রান্ত সহ গ্রাফটি হল কক্সেটার গ্রাফ। জ্যামিতিক এবং ভূতাত্ত্বিক বৈশিষ্ট্য হেউড গ্রাফ একটি টরয়েডাল গ্রাফ; অর্থাৎ, এটি একটি টরাসের উপর ক্রস না করেই এম্বেড করা যেতে পারে। এই ধরনের একটি এম্বেডিং তার শীর্ষ এবং প্রান্তগুলিকে ত্রিমাত্রিক ইউক্লিডীয় স্থানে একটি নন-কনভেক্স পলিহেড্রনের শীর্ষ এবং প্রান্তের সেট হিসাবে একটি টরাস, সিলাসি পলিহেড্রনের টপোলজি সহ স্থাপন করে। আরেকটি এম্বেডিং নিম্নরূপঃ নিয়মিত ষড়ভুজ ব্যবহার করে সমতল টাইল করুন এবং পর্যায়ক্রমে 7টি রঙ দিয়ে রঙ করুন। যে কোনও রঙের জন্য, এই রঙের ষড়ভুজগুলি একটি ত্রিভুজাকার গ্রিড গঠন করে। এই গ্রিডে, নির্বাচিত রঙের ষড়ভুজগুলির মাঝখানে কেন্দ্রগুলির সাথে একটি সমান্তরাল চতুর্ভুজ নেওয়া যেতে পারে। এই সমান্তরাল চতুর্ভুজটি ভাঁজ করলে হিউড গ্রাফ ব্যবহার করে 7টি ষড়ভুজ দিয়ে টাইল করা একটি টরাস পাওয়া যাবে (নীচের গ্যালারিতে যেমন চিত্রিত হয়েছে, তবে একটি বর্গক্ষেত্র সহ) গ্রাফটির নামকরণ পার্সি জন হিউডের নামে করা হয়েছে, যিনি 1890 সালে প্রমাণ করেছিলেন যে টরাসের প্রতিটি মহকুমায় বহুভুজগুলিতে, বহুভুজ অঞ্চলগুলি সর্বাধিক সাতটি রঙ দ্বারা রঙ করা যেতে পারে। হেউড গ্রাফ সাতটি পারস্পরিক সংলগ্ন অঞ্চল সহ টরাসের একটি উপবিভাগ গঠন করে, যা দেখায় যে এই সীমানাটি শক্ত। হেউড গ্রাফ হল ফানো সমতলের লেভি গ্রাফ, যে গ্রাফটি সেই জ্যামিতিতে বিন্দু এবং রেখার মধ্যে ঘটনার প্রতিনিধিত্ব করে। এই ব্যাখ্যার সাথে, হিউড গ্রাফের 6-চক্রগুলি ফানো সমতলে ত্রিভুজের সাথে মিলে যায়। এছাড়াও, হেউড গ্রাফ হল এসএল3 (এফ2) গ্রুপের টিটস বিল্ডিং। হিউড গ্রাফের ক্রসিং নম্বর 3 রয়েছে এবং এটি সেই ক্রসিং নম্বর সহ সবচেয়ে ছোট ঘন গ্রাফ। হিউড গ্রাফ সহ, ক্রসিং নম্বর 3 সহ 14 ক্রমের 8 টি স্বতন্ত্র গ্রাফ রয়েছে। কলিন ডি ভার্ডিয়ের গ্রাফ অপরিবর্তনীয় μ = 6 সহ হিউড গ্রাফ হল সবচেয়ে ছোট ঘন গ্রাফ। হিউড গ্রাফ একটি একক দূরত্বের গ্রাফঃ এটি সমতলে এমনভাবে এম্বেড করা যেতে পারে যাতে সংলগ্ন শীর্ষগুলি ঠিক এক দূরে থাকে, একই বিন্দুতে কোনও দুটি শীর্ষ সংযুক্ত থাকে না এবং কোনও প্রান্তের মধ্যে কোনও বিন্দুতে কোনও শীর্ষ সংযুক্ত থাকে না। বীজগাণিতিক বৈশিষ্ট্য হিউড গ্রাফের অটোমরফিজম গ্রুপটি প্রজেক্টিভ লিনিয়ার গ্রুপ পি. জি. এল2 (7)-এর সমরূপ, যা 336 ক্রমাঙ্কের একটি গ্রুপ। এটি শীর্ষে, প্রান্তে এবং গ্রাফের খিলানগুলিতে ক্ষণস্থায়ীভাবে কাজ করে। অতএব, হিউড গ্রাফ একটি প্রতিসম গ্রাফ। এর অটোমরফিজম রয়েছে যা যে কোনও শীর্ষকে অন্য যে কোনও শীর্ষে এবং যে কোনও প্রান্তকে অন্য কোনও প্রান্তে নিয়ে যায়। আরও দৃঢ়ভাবে, হিউড গ্রাফটি 4-আর্ক-ট্রানজিটিভ। ফস্টার আদমশুমারি অনুসারে, হেউড গ্রাফ, যা F014A হিসাবে উল্লেখ করা হয়েছে, 14টি শীর্ষে একমাত্র ঘন প্রতিসম গ্রাফ। এর বইয়ের পুরুত্ব 3 এবং সারি নম্বর 2। হেউড গ্রাফের চরিত্রগত বহুপদী হল। এটি এই বৈশিষ্ট্যযুক্ত বহুপদী সহ একমাত্র গ্রাফ, যা এটিকে তার বর্ণালী দ্বারা নির্ধারিত একটি গ্রাফ করে তোলে। গ্যালারি তথ্যসূত্র স্বতন্ত্র গ্রাফ নিয়মিত গ্রাফ