The characteristic polynomial of adjacency matrix is used to study:
A
chromatic number directly
B
Graph spectra
C
connectivity only
D
planarity
উত্তরের বিবরণ
Adjacency matrix-এর characteristic polynomial ব্যবহার করা হয় Graph spectra অধ্যয়নের জন্য। এটি গ্রাফ তত্ত্বে একটি গুরুত্বপূর্ণ ধারণা, যা গ্রাফের গাণিতিক বৈশিষ্ট্য নির্ণয়ে সহায়তা করে।
বিস্তারিতভাবে—
-
Characteristic Polynomial: এটি adjacency matrix (A)-এর জন্য সংজ্ঞায়িত হয় (|A - \lambda I| = 0) আকারে, যেখানে (\lambda) হলো eigenvalue।
-
Graph Spectra: কোনো গ্রাফের spectrum হলো তার adjacency matrix-এর eigenvalues-এর সমষ্টি। এগুলো গ্রাফের গঠন, সংযোগ, ও সমমিতি (symmetry) সম্পর্কিত তথ্য প্রদান করে।
-
ব্যবহার: Graph spectra বিশ্লেষণ করে গ্রাফের বৈশিষ্ট্য যেমন regularity, connectivity, isomorphism, এবং random walk behavior বোঝা যায়।
অতএব, adjacency matrix-এর characteristic polynomial ব্যবহার করা হয় Graph spectra অধ্যয়নের জন্য।
0
Updated: 14 hours ago
A tree with K leaves has at least___________ vertices.
Created: 14 hours ago
A
K
B
K-1
C
K+1
D
2K
যদি কোনো tree-তে Kটি leaf থাকে, তবে সেটিতে অন্তত K + 1টি vertex থাকবে। তাই সঠিক উত্তর হলো গ) K + 1।
বিস্তারিতভাবে:
-
একটি path graph (সোজা রেখার মতো গঠন) হলো সর্বনিম্ন কাঠামোর tree, যেখানে দুই প্রান্তের দুটি vertex হলো leaves, আর মাঝেরগুলো non-leaf।
-
যদি একটি path graph-এ Vটি vertex থাকে, তবে এর leaf সংখ্যা 2 (যদি V > 1 হয়)।
-
একটি star graph (Sₖ) বিবেচনা করা যাক—
-
এর কেন্দ্রীয় একটি vertex সব leaf vertex-এর সঙ্গে সংযুক্ত থাকে।
-
Leaves = K (বাহিরের vertex গুলো)।
-
Non-leaf = 1 (কেন্দ্রীয় vertex)।
-
Total vertices = K + 1।
-
অতএব, যেকোনো tree-এর জন্য এই সম্পর্ক প্রযোজ্য—
[V ≥ L + 1]
যেখানে,
-
V = vertex সংখ্যা,
-
L = leaf সংখ্যা।
সুতরাং, একটি tree-তে Kটি leaf থাকলে অন্তত K + 1টি vertex থাকা আবশ্যক।
0
Updated: 14 hours ago
প্রোগ্রামিং ধারণার জনক হিসেবে কাকে স্বীকৃতি দেওয়া হয়?
Created: 3 weeks ago
A
Ada Lovelace
B
John von Neumann
C
Alan Turing
D
Charles Babbage
প্রোগ্রামিং ধারণার প্রবর্তক হিসেবে সাধারণভাবে অ্যাডা লাভলেস (Ada Lovelace)-কে স্বীকৃতি দেওয়া হয়। ১৯শ শতকের মাঝামাঝি সময়ে তিনি চার্লস ব্যাবেজের “অ্যানালিটিকাল ইঞ্জিন” এর উপর কাজ করেন এবং প্রথমেই বোঝেন যে এই যন্ত্র কেবল সংখ্যা গণনার জন্য নয়, বরং সঙ্গীত, অক্ষর বা অন্যান্য তথ্য প্রক্রিয়াকরণেও ব্যবহার করা যেতে পারে। তিনি এমন একটি “প্রোগ্রাম” তৈরি করেন যা মেশিনকে নির্দিষ্ট ক্রমে কাজ করতে শেখায়। এই দৃষ্টিভঙ্গি আধুনিক প্রোগ্রামিং ধারণার ভিত্তি স্থাপন করে।
-
উত্তর: ক) Ada Lovelace
-
অ্যাডা লাভলেস (Ada Lovelace):
-
গণনার কাজ আরও কার্যকর করার বিষয় নিয়ে চিন্তাভাবনা করেছিলেন লর্ড বায়রনের কন্যা অ্যাডা লাভলেস (১৮১৫-১৮৫২)।
-
মায়ের কারণে ছোটোবেলা থেকেই বিজ্ঞান ও গণিতের প্রতি আগ্রহী হন।
-
১৮৩৩ সালে চার্লস ব্যাবেজের সঙ্গে পরিচয় হয় এবং তিনি চার্লস ব্যাবেজের অ্যানালিটিক্যাল ইঞ্জিনকে কাজে লাগানোর জন্য প্রোগ্রামিং ধারণা প্রবর্তন করেন।
-
১৮৪০ সালে চার্লস ব্যাবেজ তুরিন বিশ্ববিদ্যালয়ে ইঞ্জিন সম্পর্কে বক্তৃতা দেন, তখন অ্যাডা লাভলেস তাঁর সহায়তায় ইঞ্জিনের কাজ ধাপে ধাপে ক্রমাঙ্কিত করেন।
-
মৃত্যুর ১০০ বছর পর, ১৯৫৩ সালে সেই নোট পুনঃপ্রকাশিত হলে বিজ্ঞানীরা বুঝতে পারেন, অ্যাডা লাভলেস অ্যালগরিদম প্রোগ্রামিং-এর ধারণাই প্রথম প্রকাশ করেছিলেন।
-
0
Updated: 3 weeks ago
Which case a suffix tree is useful for?
Created: 14 hours ago
A
Fast string search
B
Minimum cut
C
Sorting numbers
D
Graph coloring
Suffix tree সবচেয়ে বেশি ব্যবহৃত হয় দ্রুত string search বা pattern matching-এর ক্ষেত্রে। তাই সঠিক উত্তর হলো ক) Fast string search।
Suffix Tree ব্যাখ্যা:
-
এটি একটি বিশেষ ডেটা স্ট্রাকচার যা কোনো স্ট্রিংয়ের সব suffix সংরক্ষণ ও সূচিবদ্ধ (indexed) করে।
-
এর প্রধান সুবিধা হলো বড় টেক্সটে দ্রুত সাবস্ট্রিং অনুসন্ধান করা যায়, কারণ সার্চের সময় জটিলতা কেবল pattern-এর দৈর্ঘ্যের ওপর নির্ভরশীল (O(|P|)), টেক্সটের দৈর্ঘ্যের ওপর নয়।
মূল ব্যবহার ক্ষেত্র:
-
Substring Search: কোনো নির্দিষ্ট প্যাটার্ন (P) টেক্সট (T)-এর মধ্যে কতবার ও কোথায় আছে তা দ্রুত খুঁজে বের করা।
-
Longest Repeated Substring: স্ট্রিংয়ে সবচেয়ে বড় পুনরাবৃত্ত সাবস্ট্রিং শনাক্ত করা।
-
Longest Common Substring: দুই বা ততোধিক স্ট্রিংয়ের মধ্যে সাধারণ সবচেয়ে বড় সাবস্ট্রিং খুঁজে বের করা।
-
Shortest Unique Substring: এমন সবচেয়ে ছোট সাবস্ট্রিং নির্ধারণ করা যা পুরো স্ট্রিংয়ে মাত্র একবার পাওয়া যায়।
ভুল বিকল্পগুলো:
-
(খ) Minimum cut: এটি গ্রাফ থিওরির সমস্যা, যার সমাধানে Max-Flow Min-Cut theorem বা Edmonds-Karp, Dinic’s algorithm ব্যবহৃত হয়।
-
(গ) Sorting numbers: এটি Merge Sort, Quick Sort, বা Radix Sort দিয়ে সম্পন্ন হয়, suffix tree দিয়ে নয়।
-
(ঘ) Graph coloring: এটি একটি combinatorial optimization সমস্যা, যা সাধারণত backtracking বা heuristic algorithm দিয়ে সমাধান করা হয়।
অতএব, suffix tree সবচেয়ে উপযোগী দ্রুত string search ও pattern matching-এর জন্য।
0
Updated: 14 hours ago
