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

Earl (mathematics)

Lecture



  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).

Content

  • 1 Definitions
    • 1.1 Count
    • 1.2 Oriented graph
    • 1.3 Mixed Count
    • 1.4 Isomorphic graphs
    • 1.5 Other related definitions
    • 1.6 Additional characteristics of the graphs
  • 2 Generalization of the concept of a graph
  • 3 Ways to represent the graph in computer science
    • 3.1 Adjacency Matrix
    • 3.2 Incidence Matrix
    • 3.3 List of ribs
    • 3.4 Description Languages ​​and Graph Building Programs
      • 3.4.1 Description Languages
      • 3.4.2 Programs for building
      • 3.4.3 Visualization software
  • 4 See also
  • 5 Notes
  • 6 Literature

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]

  Earl (mathematics)

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

  Earl (mathematics) (and therefore,   Earl (mathematics) 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   Earl (mathematics) - order , the number of edges   Earl (mathematics) - the size of the graph.

Vertices   Earl (mathematics) and   Earl (mathematics) are called end vertices (or just ends ) edges   Earl (mathematics) . 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,   Earl (mathematics) .

Degree   Earl (mathematics) tops   Earl (mathematics) 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]

  Earl (mathematics)

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

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

Mixed Count [edit]

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

Oriented and undirected graphs are special cases of mixed.

Isomorphic graphs [edit]

Graph   Earl (mathematics) called isomorphic to a graph   Earl (mathematics) if there is a bijection   Earl (mathematics) from the set of vertices of the graph   Earl (mathematics) in many vertices of the graph   Earl (mathematics) with the following property: if in the column   Earl (mathematics) there is an edge from the top   Earl (mathematics) to the top   Earl (mathematics) then in the graph   Earl (mathematics) there must be an edge from the top   Earl (mathematics) to the top   Earl (mathematics) and vice versa - if in the graph   Earl (mathematics) there is an edge from the top   Earl (mathematics) to the top   Earl (mathematics) then in the graph   Earl (mathematics) there must be an edge from the top   Earl (mathematics) to the top   Earl (mathematics) . 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   Earl (mathematics) and   Earl (mathematics) are the ends of some edge, then according to this definition, the sequence   Earl (mathematics) 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   Earl (mathematics) at   Earl (mathematics) , 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   Earl (mathematics) . 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   Earl (mathematics) ,   Earl (mathematics) there is a way out   Earl (mathematics) at   Earl (mathematics) .
  • 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   Earl (mathematics) and   Earl (mathematics) so that every edge connects a vertex from   Earl (mathematics) with top of   Earl (mathematics) .
  • k-longitudinal if its vertices can be split into   Earl (mathematics) disjoint subsets   Earl (mathematics) ,   Earl (mathematics) , ...,   Earl (mathematics) 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   Earl (mathematics) where   Earl (mathematics) and   Earl (mathematics) - some sets ( vertices and edges , respectively), and   Earl (mathematics) - the incidence function (or incidentor ) associating each edge   Earl (mathematics) (ordered or unordered) a pair of vertices   Earl (mathematics) and   Earl (mathematics) of   Earl (mathematics) (his ends ). Special cases of this concept are:

  • directed graphs (digraphs) - when   Earl (mathematics) always an ordered pair of vertices;
  • undirected graphs - when   Earl (mathematics) 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   Earl (mathematics) and   Earl (mathematics) 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   Earl (mathematics) -th line with   Earl (mathematics) -m column of the matrix is ​​written:

one
in case the connection   Earl (mathematics) "Coming out" from the top   Earl (mathematics) ,
−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   Earl (mathematics) ) 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]

  1. De Trudeau Richard J. Introduction to Graph Theory. - Corrected, enlarged republication .. - New York: Dover Pub., 1993. - P. 19. - ISBN 978-0-486-67870-2.

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.

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.