গ্রাফ থিওরি শব্দকোষ

উইকিপিডিয়া, মুক্ত বিশ্বকোষ থেকে
Jump to navigation Jump to search

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

যে কোন শীর্ষবিন্দু কে সাধারণত একটি node বা বিন্দুর মাধ্যমে এঁকে প্রকাশ করা হয়। G গ্রাফের সব শীর্ষবিন্দুর সংগ্রহ তথা শীর্ষবিন্দু সেট কে সাধারণত V(G) বা V দ্বারা প্রকাশ করা হয়। কোন গ্রাফের মাত্রা বা order বলতে , সে গ্রাফের সর্বমোট শীর্ষবিন্দু সংখ্যাকে বোঝানো হয়, যা প্রকাশ করা হয়। V(G)| এর মাধ্যমে।

দু'টি শীর্ষবিন্দুকে রেখা দ্বারা সংযুক্ত করে এজ আঁকা হয়। কোন এজ এর দু;টি প্রান্তবিন্দুতে শীর্ষবিন্দু দু'টো যদি হয় যথাক্রমে x এবং y সেক্ষেত্রে xy সেই এজ টিকে বোঝায়। G গ্রাফের সব এজ এর সংগ্রহ তথা এজ সেট' কে সাধারণত E(G), অথবা শুধু E দ্বারা প্রকাশ করা হয়। কোন গ্রাফে সর্বমোট এজ সংখ্যা গ্রাফটির আকার তথা size প্রকাশ করে , যাকে| E(G)| হিসেবে লেখা হয়।[১]

লুপ কোন এজ এর দু'টি প্রান্তবিন্দুই একই শীর্ষবিন্দু হলে তাকে লুপ বলে। অপরদিকে এজ এর দু'প্রান্তের শীর্ষবিন্দু দু'টি ভিন্ন হলে তাকে বলা হয় লিংক

দু'টি নির্দিষ্ট শীর্ষবিন্দুর মাঝে একাধিক এজ থাকলে তাকে বলা হয় মাল্টিপল এজ। অপরদিকে শীর্ষবিন্দু দু'টির মাঝে কেবল মাত্র একটি এজ থাকলে তাকে বলা হয় সহজ এজ

তথ্যসূত্র[সম্পাদনা]

  1. Harris, John M. (২০০০)। Combinatorics and Graph Theory। New York: Springer-Verlag। পৃষ্ঠা 5। আইএসবিএন 0-387-98736-3