Euler Characteristics of a Planar Graph

প্রথমেই জানা দরকার  Planar Graph কী?
Planar Graph হচ্ছে, দ্বিমাত্রিক তলে আঁকা এমন একটা গ্রাফ যেখানে একটা এজ কখনোই অন্য একটা এজকে ছেদ করবে না।

একটি গ্রাফের Euler Characteristics বা Euler Number = Vertices - Edges + Faces

এখানে, Faces = গ্রাফটির মোট সাইকেল + ১ 

এখানে, একটা সাইকেল কে তখনই হিসেবে আনবো যখন তার ভিতর অন্য কোন সাইকেল থাকবে না।

মজার ব্যাপার হচ্ছে, Planar Graph এর জন্য সবসময় ই Euler Number = 2


ছবিতে, ১ম গ্রাফটি Planar Graph নয়! কারণ, একটা এজ অন্য এজ কে ছেদ করেছে।

২য় গ্রাফের জন্য, Euler Number = 4 - 6 + 4 = 2

৩য় গ্রাফের জন্য, Euler Number = 4 - 6 +4 = 2

এভাবে, সকল Planar Graph এর জন্যই Euler Number = 2 যা অনেক থিওরিতে এপ্লাই করা লাগে। আশা করি, পরবর্তীতে কোন থিওরি তে এপ্লাই করে দেখাবো Planar Graph এর এই প্রোপার্টি।

Happy Coding -_-

Comments

Trending Post

At Coder Educational DP-A | DP Series(Episode-1)

Magic In Grid

At Coder Educational DP-B | DP Series(Episode-2)