Bipartite graph
Bipartite graph
A bipartite graph is a special type of 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 in the graph connects a vertex in the first set to a vertex in the second set.
Definition[edit | edit source]
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 \) connects a vertex in \( U \) to a vertex in \( W \). This can be written as: \[ U \cup W = V \] \[ U \cap W = \emptyset \] \[ \forall (u, v) \in E, u \in U \text{ and } v \in W \]
Properties[edit | edit source]
- A graph is bipartite if and only if it does not contain any odd cycles.
- The chromatic number of a bipartite graph is 2, meaning it can be colored using two colors such that no two adjacent vertices share the same color.
- Bipartite graphs are also known as 2-colorable graphs.
Examples[edit | edit source]
- The simplest example of a bipartite graph is the complete bipartite graph \( K_{m,n} \), where every vertex in set \( U \) is connected to every vertex in set \( W \).
- Trees are bipartite graphs because they do not contain any cycles, let alone odd cycles.
Applications[edit | edit source]
Bipartite graphs have numerous applications in various fields:
- In computer science, they are used in matching problems and network flow algorithms.
- In sociology, bipartite graphs can model relationships between two different classes of objects, such as people and the clubs they belong to.
- In biology, they can represent interactions between two different species, such as plants and their pollinators.
Related Concepts[edit | edit source]
- Matching (graph theory)
- Network flow
- Graph coloring
- Complete bipartite graph
- Tree (graph theory)
- Cycle (graph theory)
See Also[edit | edit source]
References[edit | edit source]
External Links[edit | edit source]
 | This mathematics-related article is a stub. You can help WikiMD by expanding it. |
Search WikiMD
Ad.Tired of being Overweight? Try W8MD's physician weight loss program.
Semaglutide (Ozempic / Wegovy and Tirzepatide (Mounjaro / Zepbound) available.
Advertise on WikiMD
|
WikiMD's Wellness Encyclopedia |
| Let Food Be Thy Medicine Medicine Thy Food - Hippocrates |
Translate this page: - East Asian
中文,
日本,
한국어,
South Asian
हिन्दी,
தமிழ்,
తెలుగు,
Urdu,
ಕನ್ನಡ,
Southeast Asian
Indonesian,
Vietnamese,
Thai,
မြန်မာဘာသာ,
বাংলা
European
español,
Deutsch,
français,
Greek,
português do Brasil,
polski,
română,
русский,
Nederlands,
norsk,
svenska,
suomi,
Italian
Middle Eastern & African
عربى,
Turkish,
Persian,
Hebrew,
Afrikaans,
isiZulu,
Kiswahili,
Other
Bulgarian,
Hungarian,
Czech,
Swedish,
മലയാളം,
मराठी,
ਪੰਜਾਬੀ,
ગુજરાતી,
Portuguese,
Ukrainian
Medical Disclaimer: WikiMD is not a substitute for professional medical advice. The information on WikiMD is provided as an information resource only, may be incorrect, outdated or misleading, and is not to be used or relied on for any diagnostic or treatment purposes. Please consult your health care provider before making any healthcare decisions or for guidance about a specific medical condition. WikiMD expressly disclaims responsibility, and shall have no liability, for any damages, loss, injury, or liability whatsoever suffered as a result of your reliance on the information contained in this site. By visiting this site you agree to the foregoing terms and conditions, which may from time to time be changed or supplemented by WikiMD. If you do not agree to the foregoing terms and conditions, you should not enter or use this site. See full disclaimer.
Credits:Most images are courtesy of Wikimedia commons, and templates Wikipedia, licensed under CC BY SA or similar.
Contributors: Prab R. Tumpati, MD
