Bichrophic Earl (Bigraph)

Content

• 1 Definition
• 2 Examples
• 3 Properties
• 4 Checking the dichotomy
• 5 Applications
• 6 See also

Bigraf

A double graph or bigo- graph is a mathematical term for graph theory, denoting a graph whose set of vertices can be divided into two parts in such a way that each edge of the graph connects one vertex from one part to some vertex of another part, that is, there is no edge connecting two vertices from the same part.

Definition

Full bipartite graph

Undirected graph is called bichromatic if the set of its vertices can be divided into two parts , , , so that

• no vertex in not connected to vertices in and
• no vertex in not connected to vertices in

A bipartite graph is called a complete bipartite graph (this concept is different from a complete graph, that is, one in which each pair of vertices is connected by an edge) if for each pair of vertices there is an edge . For

such a graph is denoted by the symbol .

Examples

Bichrophic graphs naturally occur when modeling the relationship between two different classes of objects. For example, the count of football players and clubs, the edge connects the corresponding player and the club, if the player played in this club. More abstract examples of bipartite graphs:

• A cycle consisting of an even number of vertices.
• Any planar graph for which every face is bounded by an even number of edges.

Properties

• A graph is bipartite if and only if it does not contain a cycle of odd length. Therefore, a bichromatic graph can not contain a click larger than 2.
• A graph is bipartite if and only if it is 2-coloring (that is, its chromatic number is two)
• A graph is divided into pairs of colored vertices if and only if any elements of one of the shares are associated with at least elements of another (Hall theorem).
• A complete bichromatic graph with more than 2 vertices in each part is non-planar.

Checking the dichotomy

Check of dichotomy with parity of distances

In order to check the graph for bipartite, it suffices to select any vertex in each connected component and mark the remaining vertices during the traversal of the graph (for example, search wide) alternately as even and odd (see illustration). If there is no conflict, all even vertices form a set , and all odd - .

Applications

• Petri nets
• Count Levy
• Coding Theory
  • Factor graph
  • Tanner graph

See also

• Glossary of graph theory
• Bijection