Bipartíció

Bipartíció is a term used in graph theory to describe a specific property of graphs. A graph is considered bipartite if its vertices can be divided into two disjoint and independent sets, U and V, such that every edge connects a vertex in U to one in V. In simpler terms, there are no edges connecting two vertices within the same set. This means that if you pick any vertex, all of its neighbors must belong to the other set.

One of the key characteristics of bipartite graphs is that they do not contain any odd-length cycles. A cycle is a path that starts and ends at the same vertex. If a graph contains a cycle of length 3, 5, 7, or any other odd number, it cannot be bipartite. Conversely, if a graph contains no odd-length cycles, it is guaranteed to be bipartite. This property makes bipartite graphs a useful tool for solving certain types of problems.

There are efficient algorithms to determine if a graph is bipartite, often involving a breadth-first search (BFS) or depth-first search (DFS) traversal. During the traversal, vertices are colored with two alternating colors. If at any point an edge connects two vertices of the same color, the graph is not bipartite. Bipartite graphs have numerous applications in areas such as matching problems (e.g., assigning tasks to workers), network flow, and scheduling.