# 二分图

（重定向自二分圖

## 特性

### 等價條件

• 一個圖是二分圖若且唯若它不包含奇作為子圖[13]
• 一個圖是二分圖若且唯若它的著色數是 2[3]
• 一個圖是二分圖若且唯若它的频谱是正負對稱的[14]

### 度數

${\displaystyle \sum _{v\in V}\deg(v)=\sum _{u\in U}\deg(u)=|E|}$

## 参考资料

1. ^ Diestel, Reinard. Graph Theory, Grad. Texts in Math. Springer. 2005. ISBN 978-3-642-14278-9.
2. ^ Asratian, Armen S.; Denley, Tristan M. J.; Häggkvist, Roland, Bipartite Graphs and their Applications, Cambridge Tracts in Mathematics 131, Cambridge University Press, 1998, ISBN 9780521593458.
3. Scheinerman, Edward R., Mathematics: A Discrete Introduction 3rd, Cengage Learning: 363, 2012, ISBN 9780840049421.
4. ^ Chartrand, Gary; Zhang, Ping, Chromatic Graph Theory, Discrete Mathematics And Its Applications 53, CRC Press: 223, 2008, ISBN 9781584888000.
5. ^ Wasserman, Stanley; Faust, Katherine, Social Network Analysis: Methods and Applications, Structural Analysis in the Social Sciences 8, Cambridge University Press: 299–302, 1994, ISBN 9780521387071.
6. ^ Bracey, Robert. On the Graphical Interpreation of Herod's Coinage in Judaea and Rome in Coins. 2012: 65–84.
7. ^ Soifer, Alexander, The Mathematical Coloring Book, Springer-Verlag: 136–137, 2008, ISBN 978-0-387-74640-1. This result has sometimes been called the "two color theorem"; Soifer credits it to a famous 1879 paper of Alfred Kempe containing a false proof of the four color theorem.
8. ^ Bandelt, H.-J.; Chepoi, V.; Eppstein, D., Combinatorics and geometry of finite and infinite squaregraphs, SIAM Journal on Discrete Mathematics, 2010, 24 (4): 1399–1440, arXiv:0905.4537, doi:10.1137/090760301.
9. ^ Asratian，Denley & Häggkvist (1998), p. 11.
10. ^ Archdeacon, D.; Debowsky, M.; Dinitz, J.; Gavlas, H., Cycle systems in the complete bipartite graph minus a one-factor, Discrete Mathematics, 2004, 284 (1–3): 37–43, doi:10.1016/j.disc.2003.11.021.
11. ^ Ovchinnikov, Sergei, Graphs and Cubes, Universitext, Springer, 2011. See especially Chapter 5, "Partial Cubes", pp. 127–181.
12. ^ Asratian，Denley & Häggkvist (1998), Theorem 2.1.3, p. 8. Asratian et al. attribute this characterization to a 1916 paper by Dénes Kőnig. For infinite graphs, this result requires the axiom of choice.
13. ^ Biggs, Norman, Algebraic Graph Theory, Cambridge Mathematical Library 2nd, Cambridge University Press: 53, 1994, ISBN 9780521458979.
14. ^ Kőnig, Dénes. Gráfok és mátrixok. Matematikai és Fizikai Lapok. 1931, 38: 116–119..
15. ^ Gross, Jonathan L.; Yellen, Jay, Graph Theory and Its Applications, Discrete Mathematics And Its Applications 2nd, CRC Press: 568, 2005, ISBN 9781584885054.
16. ^ Chartrand, Gary; Zhang, Ping, A First Course in Graph Theory, Courier Dover Publications: 189–190, 2012, ISBN 9780486483689.
17. ^ Béla Bollobás, Modern Graph Theory, Graduate Texts in Mathematics 184, Springer: 165, 1998, ISBN 9780387984889.
18. ^ Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin, The strong perfect graph theorem, Annals of Mathematics, 2006, 164 (1): 51–229, arXiv:math/0212070, doi:10.4007/annals.2006.164.51 已忽略未知参数|citeseerx= (帮助).
19. ^ Asratian，Denley & Häggkvist (1998), p. 17.
20. ^ A. A. Sapozhenko, Hypergraph, (编) Hazewinkel, Michiel, 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4
21. ^ Brualdi, Richard A.; Harary, Frank; Miller, Zevi, Bigraphs versus digraphs via matrices, Journal of Graph Theory, 1980, 4 (1): 51–73, MR 558453, doi:10.1002/jgt.3190040107. Brualdi et al. credit the idea for this equivalence to Dulmage, A. L.; Mendelsohn, N. S., Coverings of bipartite graphs, Canadian Journal of Mathematics, 1958, 10: 517–534, MR 0097069, doi:10.4153/CJM-1958-052-0.
22. ^ Sedgewick, Robert, Algorithms in Java, Part 5: Graph Algorithms 3rd, Addison Wesley: 109–111, 2004.
23. ^ Kleinberg, Jon; Tardos, Éva, Algorithm Design, Addison Wesley: 94–97, 2006.
24. ^ Eppstein, David, Testing bipartiteness of geometric intersection graphs, ACM Transactions on Algorithms, 2009, 5 (2): Art. 15, MR 2561751, arXiv:cs.CG/0307023, doi:10.1145/1497290.1497291.
25. ^ Yannakakis, Mihalis, Node-and edge-deletion NP-complete problems, Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78): 253–264, 1978, doi:10.1145/800133.804355
26. ^ Reed, Bruce; Smith, Kaleigh; Vetta, Adrian, Finding odd cycle transversals, Operations Research Letters, 2004, 32 (4): 299–301, MR 2057781, doi:10.1016/j.orl.2003.10.009 已忽略未知参数|citeseerx= (帮助).
27. ^ Guo, Jiong; Gramm, Jens; Hüffner, Falk; Niedermeier, Rolf; Wernicke, Sebastian, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Journal of Computer and System Sciences, 2006, 72 (8): 1386–1396, doi:10.1016/j.jcss.2006.02.001
28. ^ Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B., 12. Assignments and Matchings, Network Flows: Theory, Algorithms, and Applications, Prentice Hall: 461–509, 1993.
29. ^ Ahuja，Magnanti & Orlin (1993), p. 463: "Nonbipartite matching problems are more difficult to solve because they do not reduce to standard network flow problems."
30. ^ Hopcroft, John E.; Karp, Richard M., An n5/2 algorithm for maximum matchings in bipartite graphs, SIAM Journal on Computing, 1973, 2 (4): 225–231, doi:10.1137/0202019.
31. ^ Ahuja，Magnanti & Orlin (1993), Application 12.1 Bipartite Personnel Assignment, pp. 463–464.
32. ^
33. ^ Moon, Todd K., Error Correction Coding: Mathematical Methods and Algorithms, John Wiley & Sons: 638, 2005, ISBN 9780471648000.
34. ^ Moon (2005), p. 686.
35. ^ Cassandras, Christos G.; Lafortune, Stephane, Introduction to Discrete Event Systems 2nd, Springer: 224, 2007, ISBN 9780387333328.
36. ^