Earl (mathematics)

Undirected graph with six vertices and seven edges

A graph is the main object of study of mathematical graph theory, a collection of a nonempty set of vertices and sets of pairs of vertices (connections between vertices).

Objects are represented as vertices or nodes of a graph, and links as arcs, or edges ^[1] . For different applications, types of graphs can vary in direction, restrictions on the number of links, and additional data on vertices or edges.

Many structures of practical interest in mathematics and computer science can be represented by graphs. For example, the structure of Wikipedia can be modeled using a directed graph (digraph), in which vertices are articles, and arcs (oriented edges) are hyperlinks (thematic map).

Definitions [edit]

Graph theory does not have established terminology. In different articles, the same terms mean different things. Below are the most common definitions.

Count [edit]

Graph or undirected graph - this is an ordered pair. where Is a non-empty set of vertices or nodes , and - the set of pairs (in the case of an undirected graph - unordered) vertices, called edges .

(and therefore, otherwise it would be a multiset) are usually considered finite sets. Many results obtained for finite graphs are incorrect (or differ in some way) for infinite graphs , since not all the assertions that hold for finite sets are fulfilled in the case of infinite sets.

The vertices and edges of the graph are also called the elements of the graph, the number of vertices in the graph - order , the number of edges - the size of the graph.

Vertices and are called end vertices (or just ends ) edges . The edge, in turn, connects these vertices. Two end vertices of the same edge are called adjacent .

Two edges are called adjacent if they have a common terminal vertex.

Two edges are called multiple if the sets of their terminal vertices coincide.

An edge is called a loop if its ends coincide, that is, .

Degree tops call the number of edges incident to it (with the loop counting twice).

A vertex is called isolated if it is not an end for any edge; hanging (or sheet ), if it is the end of exactly one edge.

Oriented graph [edit]

Oriented graph (abbreviated digraph ) - this is an ordered pair. where - a non-empty set of vertices or nodes , and - A set of (ordered) pairs of different edges, called arcs or oriented edges .

An arc is an ordered pair of vertices. where is the top called the beginning as well - the end of the arc. We can say that the arc leads from the top to the top .

Mixed Count [edit]

Mixed graph - is a graph in which some edges may be oriented, and some - non-oriented. It is recorded in an orderly three. where , and defined as above.

Oriented and undirected graphs are special cases of mixed.

Isomorphic graphs [edit]

Graph called isomorphic to a graph if there is a bijection from the set of vertices of the graph in many vertices of the graph with the following property: if in the column there is an edge from the top to the top then in the graph there must be an edge from the top to the top and vice versa - if in the graph there is an edge from the top to the top then in the graph there must be an edge from the top to the top . In the case of a directed graph, this bijection must also preserve the orientation of the edge. In the case of a weighted graph, the bijection must also preserve the weight of the edge.

Other related definitions [edit]

A route in a graph is a finite sequence of vertices in which each vertex (except the last) is connected to the next edge in the sequence. A chain is a route without repeated edges. A simple chain is a route without repeating vertices (whence it follows that there are no repeating edges in a simple chain).

Oriented route (or path ) in a digraph is a finite sequence of vertices and arcs in which each element is incident to the previous and next.

A cycle is a chain in which the first and last vertices coincide. The length of the path (or cycle) is called the number of its edges . Note that if the vertices and are the ends of some edge, then according to this definition, the sequence is a cycle. To avoid such “degenerate” cases, the following concepts are introduced.

The path (or cycle) is called simple if the edges in it do not repeat; elementary if it is simple and the vertices are not repeated in it. It is not difficult to see that:

• Every path connecting two vertices contains an elementary path connecting the same two vertices.
• Every simple non-elementary path contains an elementary loop .
• Every simple cycle passing through a certain vertex (or edge) contains an elementary (sub-) cycle passing through the same vertex (or edge).
• The loop is an elementary loop.

A binary relation on the set of vertices of the graph, given as "there is a path from at , Is an equivalence relation and, therefore, splits this set into equivalence classes, called the connected components of the graph. If the graph has exactly one connected component, then the graph is connected. On the connected component, one can introduce the concept of the distance between vertices as the minimum length of the path connecting these vertices.

Every maximal connected subgraph of a graph G is called a connected component (or simply a component) of a graph . The word "maximum" means maximum relative to inclusion, that is, not contained in a connected subgraph with a large number of elements.

An edge of a graph is called a bridge if its removal increases the number of components.

Additional characteristics of the graphs [edit]

Count is called:

• connected if for any vertices , there is a way out at .
• strongly connected or oriented connected if it is oriented, and from any vertex to any other there is an oriented path.
• tree if it is connected and does not contain non-trivial cycles.
• complete , if any of its two (different if loops are not allowed) vertices are connected by an edge.
• bipartite if its vertices can be divided into two disjoint subsets and so that every edge connects a vertex from with top of .
• k-longitudinal if its vertices can be split into disjoint subsets , , ..., so that there will be no edges connecting the vertices of the same subset.
• full bipartite if each vertex of one subset is connected by an edge with each vertex of another subset.
• planar if the graph can be represented as a diagram on a plane without intersections of edges.
• weighted , if each edge of the graph is assigned a certain number, called the weight of the edge.
• chordal if the graph does not contain induced cycles with a length of more than three.

It also happens:

• k-colored
• k-chromatic

Generalization of the concept of the graph [edit]

A simple graph is a one-dimensional simplicial complex.

More abstract, the graph can be set as a triple where and - some sets ( vertices and edges , respectively), and - the incidence function (or incidentor ) associating each edge (ordered or unordered) a pair of vertices and of (his ends ). Special cases of this concept are:

• directed graphs (digraphs) - when always an ordered pair of vertices;
• undirected graphs - when always an unordered pair of vertices;
• mixed graphs - in which there are both oriented and non-oriented edges and loops;
• Eulerian graphs - a graph in which there exists a cyclic Eulerian path (Eulerian cycle);
• multigraphs - graphs with multiple edges, having their ends the same pair of vertices;
• pseudographs are multigraphs that admit loops;
• simple graphs - not having loops and multiple edges.

Under this definition some other generalizations do not fit:

• hypergraph - if the edge can connect more than two vertices.
• ultragraph - if between elements and There are binary relations of incidence.

Ways to represent the graph in computer science [edit]

Adjacency matrix [edit]

A table where both columns and rows correspond to the vertices of the graph. In each cell of this matrix, a number is written that determines whether there is a connection from the vertex-row to the vertex-column (or vice versa).

The disadvantage is the memory requirements that are directly proportional to the square of the number of vertices.

• Two-dimensional array;
• Matrix with passes;
• Implicit task (using the function).

Incidence Matrix [edit]

Each row corresponds to a certain vertex of the graph, and the columns correspond to the connections of the graph. In the cell at the intersection -th line with -m column of the matrix is ​​written:

one

in case the connection "Coming out" from the top ,

−1,

if the connection "enters" at the top

0

in all other cases (that is, if the link is a loop or the link is not incident to the top)

This method is the most capacious (the size is proportional to ) for storage, but makes it easier to find cycles in the graph.

Rib List [edit]

The edge list is a type of graph representation, implying that each edge is represented by two numbers - the numbers of the vertices of this edge.

Description languages ​​and graph construction programs [edit]

Description Languages ​​[edit]

For the description of graphs for purposes suitable for machine processing and at the same time convenient for human perception, several standardized languages ​​are used, including:

• DOT (language)
• GraphML
• Trivial Graph Format
• GML
• Gxl
• Xgmml
• DGML

Build programs [edit]

A series of commercial programs for graph construction has been developed, for example, graph construction underlies the ILOG application software packages (owned by IBM since 2009), among others are GoView, Lassalle AddFlow, LEDA (there is a free edition).

There is also a free program for constructing graphs igraph and a free library Boost (free software).

Visualization software [edit]

To visualize graphs you can use:

• Graphviz (Eclipse Public License)
• LION Graph Visualizer.
• The graph analyzer is a Russian-language program with a simple user interface (GNU LGPL; only for Windows).
• Gephi is a graphical shell for representing and studying graphs (GNU GPL, CDDL).
• The GraphX ​​library, a free .NET library for calculating and drawing graphs, uses WPF 4.0.

See also [edit]

• Graph visualization
• Direct product of graphs
• Object graph

Notes [edit]

Literature [edit]

• Ore O. Graph theory. M .: Science, 1968. 336s.
• Wilson R. Introduction to graph theory. Per from English M .: Mir, 1977. 208с.
• Harari F. Graph Theory. M .: Mir, 1973.
• Kormen, TM, and others. Part VI. Algorithms for working with graphs // Algorithms: construction and analysis = Introduction to Algorithms. - 2nd ed. - M .: Williams, 2006. - p. 1296. - ISBN 0-07-013151-1.
• Saliy V.N., Bogomolov A.M. Algebraic Foundations of the Theory of Discrete Systems. - M .: Physics and mathematics literature, 1997. - ISBN 5-02-015033-9.
• Kasyanov V.N., Evstigneev V.A. Graphs in programming: processing, visualization and application. - SPb .: BHV-Petersburg, 2003. - p. 1104. - ISBN 5-94157-184-4.
• Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Lectures on graph theory. M .: Nauka, 1990. 384с. (Ed. 2, Rev. M .: URSS, 2009. 392 p.)
• Kirsanov MN Graphs in Maple. M .: Fizmatlit, 2007. - 168 c.