Movatterモバイル変換

[0]ホーム

Jump to content

Bipartite graph

Edit links

From Wikipedia, the free encyclopedia

Graph divided into two independent sets

Example of a bipartite graph without cycles

Acomplete bipartite graph withm = 5 andn = 3

In themathematical field ofgraph theory, abipartite graph (orbigraph) is agraph whosevertices can be divided into twodisjoint andindependent sets $U {\displaystyle U}$ and $V {\displaystyle V}$ , that is, everyedge connects avertex in $U {\displaystyle U}$ to one in $V {\displaystyle V}$ . Vertex sets $U {\displaystyle U}$ and $V {\displaystyle V}$ are usually called theparts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-lengthcycles.^[1]^[2]

The two sets $U {\displaystyle U}$ and $V {\displaystyle V}$ may be thought of as acoloring of the graph with two colors: if one colors all nodes in $U {\displaystyle U}$ blue, and all nodes in $V {\displaystyle V}$ red, each edge has endpoints of differing colors, as is required in the graph coloring problem.^[3]^[4] In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as atriangle: after one node is colored blue and another red, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color.

One often writes $G=(U,V,E)$ to denote a bipartite graph whose partition has the parts $U {\displaystyle U}$ and $V {\displaystyle V}$ , with $E {\displaystyle E}$ denoting the edges of the graph. If a bipartite graph is notconnected, it may have more than one bipartition;^[5] in this case, the $(U,V,E)$ notation is helpful in specifying one particular bipartition that may be of importance in an application. If $|U|=|V|$ , that is, if the two subsets have equalcardinality, then $G {\displaystyle G}$ is called abalanced bipartite graph.^[3] If all vertices on the same side of the bipartition have the samedegree, then $G {\displaystyle G}$ is calledbiregular.

Examples

[edit]

When modellingrelations between two different classes of objects, bipartite graphs very often arise naturally. For instance, a graph of football players and clubs, with an edge between a player and a club if the player has played for that club, is a natural example of anaffiliation network, a type of bipartite graph used insocial network analysis.^[6]

Another example where bipartite graphs appear naturally is in the (NP-complete) railway optimization problem, in which the input is a schedule of trains and their stops, and the goal is to find a set of train stations as small as possible such that every train visits at least one of the chosen stations. This problem can be modeled as adominating set problem in a bipartite graph that has a vertex for each train and each station and an edge for each pair of a station and a train that stops at that station.^[7]

More abstract examples include the following:

Everytree is bipartite.^[4]
Cycle graphs with an even number of vertices are bipartite.^[4]
Everyplanar graph whosefaces all have even length is bipartite.^[8] Special cases of this aregrid graphs andsquaregraphs, in which every inner face consists of 4 edges and every inner vertex has four or more neighbors.^[9]
Thecomplete bipartite graph onm andn vertices, denoted byK_n,m is the bipartite graph $G=(U,V,E)$ , whereU andV are disjoint sets of sizem andn, respectively, andE connects every vertex inU with all vertices inV. It follows thatK_m,n hasmn edges.^[10] Closely related to the complete bipartite graphs are thecrown graphs, formed from complete bipartite graphs by removing the edges of aperfect matching.^[11]
Hypercube graphs,partial cubes, andmedian graphs are bipartite. In these graphs, the vertices may be labeled bybitvectors, in such a way that two vertices are adjacent if and only if the corresponding bitvectors differ in a single position. A bipartition may be formed by separating the vertices whose bitvectors have an even number of ones from the vertices with an odd number of ones. Trees and squaregraphs form examples of median graphs, and every median graph is a partial cube.^[12]

Properties

[edit]

Characterization

[edit]

Bipartite graphs may be characterized in several different ways:

An undirected graph is bipartiteif and only if it does not contain an oddcycle.^[13]^[14]
A graph is bipartite if and only if it is 2-colorable, (i.e. itschromatic number is less than or equal to 2).^[3]
A graph is bipartite if and only if every edge belongs to an odd number ofbonds, minimal subsets of edges whose removal increases the number of components of the graph.^[15]
A graph is bipartite if and only if thespectrum of the graph is symmetric.^[16]

Kőnig's theorem and perfect graphs

[edit]

In bipartite graphs, the size ofminimum vertex cover is equal to the size of themaximum matching; this isKőnig's theorem.^[17]^[18] An alternative and equivalent form of this theorem is that the size of themaximum independent set plus the size of the maximum matching is equal to the number of vertices. In any graph withoutisolated vertices the size of theminimum edge cover plus the size of a maximum matching equals the number of vertices.^[19] Combining this equality with Kőnig's theorem leads to the facts that, in bipartite graphs, the size of the minimum edge cover is equal to the size of the maximum independent set, and the size of the minimum edge cover plus the size of the minimum vertex cover is equal to the number of vertices.

Another class of related results concernsperfect graphs: every bipartite graph, thecomplement of every bipartite graph, theline graph of every bipartite graph, and the complement of the line graph of every bipartite graph, are all perfect. Perfection of bipartite graphs is easy to see (theirchromatic number is two and theirmaximum clique size is also two) but perfection of thecomplements of bipartite graphs is less trivial, and is another restatement of Kőnig's theorem. This was one of the results that motivated the initial definition of perfect graphs.^[20] Perfection of the complements of line graphs of perfect graphs is yet another restatement of Kőnig's theorem, and perfection of the line graphs themselves is a restatement of an earlier theorem of Kőnig, that every bipartite graph has anedge coloring using a number of colors equal to its maximum degree.

According to thestrong perfect graph theorem, the perfect graphs have aforbidden graph characterization resembling that of bipartite graphs: a graph is bipartite if and only if it has no odd cycle as a subgraph, and a graph is perfect if and only if it has no odd cycle or itscomplement as aninduced subgraph. The bipartite graphs, line graphs of bipartite graphs, and their complements form four out of the five basic classes of perfect graphs used in the proof of the strong perfect graph theorem.^[21] It follows that any subgraph of a bipartite graph is also bipartite because it cannot gain an odd cycle.^[22]

Degree

[edit]

For a vertex, the number of adjacent vertices is called thedegree of the vertex and is denoted $\deg v$ . Thedegree sum formula for a bipartite graph states that^[23]

\sum _{v\in V}\deg v=\sum _{u\in U}\deg u=|E|\,.

The degree sequence of a bipartite graph is the pair of lists each containing the degrees of the two parts $U {\displaystyle U}$ and $V {\displaystyle V}$ . For example, the complete bipartite graphK_3,5 has degree sequence $(5,5,5),(3,3,3,3,3)$ .Isomorphic bipartite graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a bipartite graph; in some cases, non-isomorphic bipartite graphs may have the same degree sequence.

Thebipartite realization problem is the problem of finding a simple bipartite graph with the degree sequence being two given lists of natural numbers. (Trailing zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the digraph.)

Relation to hypergraphs and directed graphs

[edit]

Thebiadjacency matrix of a bipartite graph $(U,V,E)$ is a(0,1) matrix of size $|U|\times |V|$ that has a one for each pair of adjacent vertices and a zero for nonadjacent vertices.^[24] Biadjacency matrices may be used to describe equivalences between bipartite graphs, hypergraphs, and directed graphs.

Ahypergraph is a combinatorial structure that, like an undirected graph, has vertices and edges, but in which the edges may be arbitrary sets of vertices rather than having to have exactly two endpoints. A bipartite graph $(U,V,E)$ may be used to model a hypergraph in whichU is the set of vertices of the hypergraph,V is the set of hyperedges, andE contains an edge from a hypergraph vertexv to a hypergraph edgee exactly whenv is one of the endpoints ofe. Under this correspondence, the biadjacency matrices of bipartite graphs are exactly theincidence matrices of the corresponding hypergraphs. As a special case of this correspondence between bipartite graphs and hypergraphs, anymultigraph (a graph in which there may be two or more edges between the same two vertices) may be interpreted as a hypergraph in which some hyperedges have equal sets of endpoints, and represented by a bipartite graph that does not have multiple adjacencies and in which the vertices on one side of the bipartition all havedegree two.^[25]

A similar reinterpretation of adjacency matrices may be used to show a one-to-one correspondence betweendirected graphs (on a given number of labeled vertices, allowing self-loops) and balanced bipartite graphs, with the same number of vertices on both sides of the bipartition. For, the adjacency matrix of a directed graph withn vertices can be any(0,1) matrix of size $n\times n$ , which can then be reinterpreted as the adjacency matrix of a bipartite graph withn vertices on each side of its bipartition.^[26] In this construction, the bipartite graph is thebipartite double cover of the directed graph.

Algorithms

[edit]

Testing bipartiteness

[edit]

It is possible to test whether a graph is bipartite, and to return either a two-coloring (if it is bipartite) or an odd cycle (if it is not) inlinear time, usingdepth-first search (DFS). The main idea is to assign to each vertex the color that differs from the color of its parent in the DFS forest, assigning colors in apreorder traversal of the depth-first-search forest. This will necessarily provide a two-coloring of thespanning forest consisting of the edges connecting vertices to their parents, but it may not properly color some of the non-forest edges. In a DFS forest, one of the two endpoints of every non-forest edge is an ancestor of the other endpoint, and when the depth first search discovers an edge of this type it should check that these two vertices have different colors. If they do not, then the path in the forest from ancestor to descendant, together with the miscolored edge, form an odd cycle, which is returned from the algorithm together with the result that the graph is not bipartite. However, if the algorithm terminates without detecting an odd cycle of this type, then every edge must be properly colored, and the algorithm returns the coloring together with the result that the graph is bipartite.^[27]

Alternatively, a similar procedure may be used withbreadth-first search in place of DFS. Again, each node is given the opposite color to its parent in the search forest, in breadth-first order. If, when a vertex is colored, there exists an edge connecting it to a previously-colored vertex with the same color, then this edge together with the paths in the breadth-first search forest connecting its two endpoints to theirlowest common ancestor forms an odd cycle. If the algorithm terminates without finding an odd cycle in this way, then it must have found a proper coloring, and can safely conclude that the graph is bipartite.^[28]

For theintersection graphs of $n {\displaystyle n}$ line segments or other simple shapes in theEuclidean plane, it is possible to test whether the graph is bipartite and return either a two-coloring or an odd cycle in time $O(n\log n)$ , even though the graph itself may have up to $O(n^{2})$ edges.^[29]

Odd cycle transversal

[edit]

Main article:Odd cycle transversal

A graph with an odd cycle transversal of size 2: removing the two blue bottom vertices leaves a bipartite graph.

Odd cycle transversal is anNP-complete algorithmic problem that asks, given a graphG = (V,E) and a numberk, whether there exists a set of k vertices whose removal fromG would cause the resulting graph to be bipartite.^[30] The problem isfixed-parameter tractable, meaning that there is an algorithm whose running time can be bounded by a polynomial function of the size of the graph multiplied by a larger function ofk.^[31] The nameodd cycle transversal comes from the fact that a graph is bipartite if and only if it has no oddcycles. Hence, to delete vertices from a graph in order to obtain a bipartite graph, one needs to "hit all odd cycle", or find a so-called odd cycletransversal set. In the illustration, every odd cycle in the graph contains the blue (the bottommost) vertices, so removing those vertices kills all odd cycles and leaves a bipartite graph.

Theedge bipartization problem is the algorithmic problem of deleting as few edges as possible to make a graph bipartite and is also an important problem in graph modification algorithmics. This problem is alsofixed-parameter tractable, and can be solved in time ${\textstyle O\left(2^{k}m^{2}\right)}$ ,^[32] wherek is the number of edges to delete andm is the number of edges in the input graph.

Matching

[edit]

Main article:Matching (graph theory)

Amatching in a graph is a subset of its edges, no two of which share an endpoint.Polynomial time algorithms are known for many algorithmic problems on matchings, includingmaximum matching (finding a matching that uses as many edges as possible),maximum weight matching, andstable marriage.^[33] In many cases, matching problems are simpler to solve on bipartite graphs than on non-bipartite graphs,^[34] and many matching algorithms such as theHopcroft–Karp algorithm for maximum cardinality matching^[35] work correctly only on bipartite inputs.

As a simple example, suppose that a set $P {\displaystyle P}$ of people are all seeking jobs from among a set $J {\displaystyle J}$ of jobs, with not all people suitable for all jobs. This situation can be modeled as a bipartite graph $(P,J,E)$ where an edge connects each job-seeker with each suitable job.^[36] Aperfect matching describes a way of simultaneously satisfying all job-seekers and filling all jobs;Hall's marriage theorem provides a characterization of the bipartite graphs which allow perfect matchings. TheNational Resident Matching Program applies graph matching methods to solve this problem forU.S. medical student job-seekers andhospital residency jobs.^[37]

TheDulmage–Mendelsohn decomposition is a structural decomposition of bipartite graphs that is useful in finding maximum matchings.^[38]

Additional applications

[edit]

Bipartite graphs are extensively used in moderncoding theory, especially to decodecodewords received from the channel.Factor graphs andTanner graphs are examples of this. A Tanner graph is a bipartite graph in which the vertices on one side of the bipartition represent digits of a codeword, and the vertices on the other side represent combinations of digits that are expected to sum to zero in a codeword without errors.^[39] A factor graph is a closely relatedbelief network used for probabilistic decoding ofLDPC andturbo codes.^[40]

In computer science, aPetri net is a mathematical modeling tool used in analysis and simulations of concurrent systems. A system is modeled as a bipartite directed graph with two sets of nodes: A set of "place" nodes that contain resources, and a set of "event" nodes which generate and/or consume resources. There are additional constraints on the nodes and edges that constrain the behavior of the system. Petri nets utilize the properties of bipartite directed graphs and other properties to allow mathematical proofs of the behavior of systems while also allowing easy implementation of simulations of the system.^[41]

Inprojective geometry,Levi graphs are a form of bipartite graph used to model the incidences between points and lines in aconfiguration. Corresponding to the geometric property of points and lines that every two lines meet in at most one point and every two points be connected with a single line, Levi graphs necessarily do not contain any cycles of length four, so theirgirth must be six or more.^[42]

References

[edit]

^Diestel, Reinard (2005),Graph Theory,Graduate Texts in Mathematics, Springer,ISBN 978-3-642-14278-9,archived from the original on 2011-04-09, retrieved2012-02-27
^Asratian, Armen S.; Denley, Tristan M. J.; Häggkvist, Roland (1998),Bipartite Graphs and their Applications, Cambridge Tracts in Mathematics, vol. 131, Cambridge University Press,ISBN 9780521593458.
^^a ^b ^cAsratian, Denley & Häggkvist (1998), p. 7.
^^a ^b ^cScheinerman, Edward R. (2012),Mathematics: A Discrete Introduction (3rd ed.), Cengage Learning, p. 363,ISBN 9780840049421.
^Chartrand, Gary;Zhang, Ping (2008),Chromatic Graph Theory, Discrete Mathematics And Its Applications, vol. 53, CRC Press, p. 223,ISBN 9781584888000.
^Wasserman, Stanley; Faust, Katherine (1994),Social Network Analysis: Methods and Applications, Structural Analysis in the Social Sciences, vol. 8, Cambridge University Press, pp. 299–302,ISBN 9780521387071.
^Niedermeier, Rolf (2006),Invitation to Fixed Parameter Algorithms, Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press, pp. 20–21,ISBN 978-0-19-856607-6
^Soifer, Alexander (2008),The Mathematical Coloring Book, Springer-Verlag, pp. 136–137,ISBN 978-0-387-74640-1. This result has sometimes been called the "two color theorem"; Soifer credits it to a famous 1879 paper ofAlfred Kempe containing a false proof of thefour color theorem.
^Bandelt, H.-J.; Chepoi, V.;Eppstein, D. (2010), "Combinatorics and geometry of finite and infinite squaregraphs",SIAM Journal on Discrete Mathematics,24 (4):1399–1440,arXiv:0905.4537,doi:10.1137/090760301,S2CID 10788524.
^Asratian, Denley & Häggkvist (1998), p. 11.
^Archdeacon, D.; Debowsky, M.;Dinitz, J.; Gavlas, H. (2004), "Cycle systems in the complete bipartite graph minus a one-factor",Discrete Mathematics,284 (1–3):37–43,doi:10.1016/j.disc.2003.11.021.
^Ovchinnikov, Sergei (2011),Graphs and Cubes, Universitext, Springer. See especially Chapter 5, "Partial Cubes", pp. 127–181.
^Asratian, Denley & Häggkvist (1998), Theorem 2.1.3, p. 8. Asratian et al. attribute this characterization to a 1916 paper byDénes Kőnig. For infinite graphs, this result requires theaxiom of choice.
^Bang-Jensen, Jørgen; Gutin, Gregory (2001),Digraphs: Theory, Algorithms and Applications(PDF) (1st ed.), Springer, p. 25,ISBN 9781852332686,archived(PDF) from the original on 2023-01-02, retrieved2023-01-02
^Woodall, D. R. (1990), "A proof of McKee's Eulerian-bipartite characterization",Discrete Mathematics,84 (2):217–220,doi:10.1016/0012-365X(90)90380-Z,MR 1071664
^Biggs, Norman (1994),Algebraic Graph Theory, Cambridge Mathematical Library (2nd ed.), Cambridge University Press, p. 53,ISBN 9780521458979.
^Kőnig, Dénes (1931), "Gráfok és mátrixok",Matematikai és Fizikai Lapok,38:116–119.
^Gross, Jonathan L.; Yellen, Jay (2005),Graph Theory and Its Applications, Discrete Mathematics And Its Applications (2nd ed.), CRC Press, p. 568,ISBN 9781584885054.
^Chartrand, Gary;Zhang, Ping (2012),A First Course in Graph Theory, Courier Dover Publications, pp. 189–190,ISBN 9780486483689.
^Béla Bollobás (1998),Modern Graph Theory, Graduate Texts in Mathematics, vol. 184, Springer, p. 165,ISBN 9780387984889.
^Chudnovsky, Maria;Robertson, Neil;Seymour, Paul;Thomas, Robin (2006), "The strong perfect graph theorem",Annals of Mathematics,164 (1):51–229,arXiv:math/0212070,CiteSeerX 10.1.1.111.7265,doi:10.4007/annals.2006.164.51,S2CID 119151552.
^DeVos, Matt,"Matchings"(PDF),Lecture notes: Introduction to Graph Theory, Math 345, Simon Fraser University
^Lovász, László (2014),Combinatorial Problems and Exercises (2nd ed.), Elsevier, p. 281,ISBN 9780080933092
^Asratian, Denley & Häggkvist (1998), p. 17.
^A. A. Sapozhenko (2001) [1994],"Hypergraph",Encyclopedia of Mathematics,EMS Press
^Brualdi, Richard A.;Harary, Frank; Miller, Zevi (1980), "Bigraphs versus digraphs via matrices",Journal of Graph Theory,4 (1):51–73,doi:10.1002/jgt.3190040107,MR 0558453. Brualdi et al. credit the idea for this equivalence toDulmage, A. L.;Mendelsohn, N. S. (1958), "Coverings of bipartite graphs",Canadian Journal of Mathematics,10:517–534,doi:10.4153/CJM-1958-052-0,MR 0097069,S2CID 123363425.
^Sedgewick, Robert (2004),Algorithms in Java, Part 5: Graph Algorithms (3rd ed.), Addison Wesley, pp. 109–111.
^Kleinberg, Jon;Tardos, Éva (2006),Algorithm Design, Addison Wesley, pp. 94–97.
^Eppstein, David (2009), "Testing bipartiteness of geometric intersection graphs",ACM Transactions on Algorithms,5 (2): Art. 15,arXiv:cs.CG/0307023,doi:10.1145/1497290.1497291,MR 2561751,S2CID 60496.
^Yannakakis, Mihalis (1978), "Node-and edge-deletion NP-complete problems",Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78), pp. 253–264,doi:10.1145/800133.804355,S2CID 363248
^Reed, Bruce; Smith, Kaleigh; Vetta, Adrian (2004), "Finding odd cycle transversals",Operations Research Letters,32 (4):299–301,CiteSeerX 10.1.1.112.6357,doi:10.1016/j.orl.2003.10.009,MR 2057781.
^Guo, Jiong; Gramm, Jens; Hüffner, Falk; Niedermeier, Rolf; Wernicke, Sebastian (2006), "Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization",Journal of Computer and System Sciences,72 (8):1386–1396,doi:10.1016/j.jcss.2006.02.001
^Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), "12. Assignments and Matchings",Network Flows: Theory, Algorithms, and Applications, Prentice Hall, pp. 461–509.
^Ahuja, Magnanti & Orlin (1993), p. 463: "Nonbipartite matching problems are more difficult to solve because they do not reduce to standard network flow problems."
^Hopcroft, John E.;Karp, Richard M. (1973), "Ann^5/2 algorithm for maximum matchings in bipartite graphs",SIAM Journal on Computing,2 (4):225–231,doi:10.1137/0202019.
^Ahuja, Magnanti & Orlin (1993), Application 12.1 Bipartite Personnel Assignment, pp. 463–464.
^Robinson, Sara (April 2003),"Are Medical Students Meeting Their (Best Possible) Match?"(PDF),SIAM News (3): 36, archived fromthe original(PDF) on 2016-11-18, retrieved2012-08-27.
^Dulmage & Mendelsohn (1958).
^Moon, Todd K. (2005),Error Correction Coding: Mathematical Methods and Algorithms, John Wiley & Sons, p. 638,ISBN 9780471648000.
^Moon (2005), p. 686.
^Cassandras, Christos G.; Lafortune, Stephane (2007),Introduction to Discrete Event Systems (2nd ed.), Springer, p. 224,ISBN 9780387333328.
^Grünbaum, Branko (2009),Configurations of Points and Lines,Graduate Studies in Mathematics, vol. 103,American Mathematical Society, p. 28,ISBN 9780821843086.