You get a bonus - 1 coin for daily activity. Now you have 1 coin

Bichrophic Earl (Bigraph)

Lecture



Content

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

Bichrophic Earl (Bigraph)

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

Bichrophic Earl (Bigraph)

Full bipartite graph Bichrophic Earl (Bigraph)

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

  • no vertex in Bichrophic Earl (Bigraph) not connected to vertices in Bichrophic Earl (Bigraph) and
  • no vertex in Bichrophic Earl (Bigraph) not connected to vertices in Bichrophic Earl (Bigraph)

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 Bichrophic Earl (Bigraph) there is an edge Bichrophic Earl (Bigraph) . For

Bichrophic Earl (Bigraph)

such a graph is denoted by the symbol Bichrophic Earl (Bigraph) .

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 Bichrophic Earl (Bigraph) elements of one of the shares are associated with at least Bichrophic Earl (Bigraph) elements of another (Hall theorem).
  • A complete bichromatic graph with more than 2 vertices in each part is non-planar.

Checking the dichotomy

Bichrophic Earl (Bigraph)

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 Bichrophic Earl (Bigraph) , and all odd - Bichrophic Earl (Bigraph) .

Applications

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

See also

  • Glossary of graph theory
  • Bijection

Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Discrete Math. Set theory. Graph theory. Combinatorics.

Terms: Discrete Math. Set theory. Graph theory. Combinatorics.