https://wikimd.org/index.php?action=history&feed=atom&title=BipartiteBipartite - Revision history2026-04-26T05:01:06ZRevision history for this page on the wikiMediaWiki 1.44.2https://wikimd.org/index.php?title=Bipartite&diff=5880361&oldid=prevPrab: CSV import2024-06-01T22:38:13Z<p>CSV import</p>
<p><b>New page</b></p><div>{{Short description|Mathematical concept in graph theory}}<br />
{{About|the mathematical concept|other uses|Bipartite (disambiguation)}}<br />
<br />
A '''bipartite graph''', also known as a '''bigraph''', is a special kind of [[graph (discrete mathematics)|graph]] in the field of [[graph theory]]. A graph is bipartite if its set of [[vertices]] can be divided into two disjoint sets such that no two graph vertices within the same set are adjacent. In other words, every edge connects a vertex in one set to a vertex in the other set.<br />
<br />
== Definition ==<br />
Formally, a graph \( G = (V, E) \) is bipartite if the vertex set \( V \) can be partitioned into two disjoint sets \( U \) and \( W \) such that every edge in \( E \) has one endpoint in \( U \) and the other endpoint in \( W \). This can be written as:<br />
\[ U \cup W = V \]<br />
\[ U \cap W = \emptyset \]<br />
\[ \forall (u, v) \in E, u \in U \text{ and } v \in W \]<br />
<br />
== Properties ==<br />
* **Two-colorable**: A bipartite graph is two-colorable, meaning its vertices can be colored using two colors such that no two adjacent vertices share the same color.<br />
* **No odd-length cycles**: A graph is bipartite if and only if it contains no odd-length cycles. This is a direct consequence of the two-colorability property.<br />
* **Complete bipartite graph**: A complete bipartite graph, denoted as \( K_{m,n} \), is a bipartite graph where every vertex in set \( U \) is connected to every vertex in set \( W \).<br />
<br />
== Applications ==<br />
Bipartite graphs have numerous applications in various fields:<br />
* **Matching problems**: In [[combinatorial optimization]], bipartite graphs are used to model matching problems, such as the [[assignment problem]] and the [[maximum bipartite matching]] problem.<br />
* **Network flow**: Bipartite graphs are used in network flow problems, particularly in the [[Ford-Fulkerson algorithm]] for computing the maximum flow in a flow network.<br />
* **Social networks**: In [[social network analysis]], bipartite graphs can represent relationships between two different classes of entities, such as people and the events they attend.<br />
<br />
== Examples ==<br />
* **Bipartite graph in biology**: In [[ecology]], bipartite graphs can represent interactions between two different types of species, such as plants and their pollinators.<br />
* **Bipartite graph in computer science**: In [[computer science]], bipartite graphs are used in [[database]] systems to model relationships between different types of entities, such as customers and products.<br />
<br />
== Related Concepts ==<br />
* [[Graph theory]]<br />
* [[Matching (graph theory)]]<br />
* [[Network flow]]<br />
* [[Two-colorable graph]]<br />
* [[Complete bipartite graph]]<br />
<br />
== See also ==<br />
* [[Graph (discrete mathematics)]]<br />
* [[Cycle (graph theory)]]<br />
* [[Ford-Fulkerson algorithm]]<br />
* [[Social network analysis]]<br />
<br />
== References ==<br />
{{Reflist}}<br />
<br />
[[Category:Graph theory]]<br />
[[Category:Discrete mathematics]]<br />
[[Category:Combinatorial optimization]]<br />
[[Category:Network flow]]<br />
<br />
{{Graph theory}}<br />
{{math-stub}}</div>Prab