Bipartite Graph
দ্বিপক্ষীয় গ্রাফ
Vertex-দের দুই দলে ভাগ করা যায় যেন প্রতিটা edge এক দল থেকে অন্য দলে যায়। সমতুল্যভাবে: কোনো বিজোড় দৈর্ঘ্যের cycle নেই।
also: bipartite
Theorem: graph bipartite ⟺ কোনো বিজোড় cycle নেই।
BFS দিয়ে O(V+E)-তে যাচাই করা যায় — ২ রঙে রাঙান, conflict
পেলে বিজোড় cycle আছে:
color[v] = 1 - color[u]
if color[v] == color[u]: return Falseঅর্থাৎ bipartite মানে ঠিক χ(G) ≤ 2 — [[graph-coloring]]-এর
সবচেয়ে সহজ ক্ষেত্র, আর NP-complete নয়।
যেখানে দেখা যায়:
| প্রয়োগ | দুইটা দল |
|---|---|
| Matching | worker ↔ job |
| Scheduling | task ↔ time slot |
| Recommendation | user ↔ item |
| Ad serving | ad ↔ slot |
| Compiler | variable ↔ register (কখনো) |
Bipartite matching-এর efficient algorithm আছে (Hopcroft–Karp,
O(E√V)) — যেখানে সাধারণ graph-এ matching অনেক কঠিন। এটাই
কাঠামো চিনে ফেলার মূল্য: সমস্যাটা bipartite কি না জানা থাকলে
অনেক দ্রুত algorithm ব্যবহার করা যায়।
প্রতিটা [[tree]] bipartite (cycle-ই নেই, তাই বিজোড় cycle-ও নেই)।