Graph theory and its application, Berge K. Graph theory: basic concepts and tasks
Informally, a graph can be thought of as a set of points and lines connecting these points, with or without arrows.
The first work of graph theory as a mathematical discipline is considered to be Euler's paper (1736), which considered the problem of the Köningsberg bridges. Euler showed that it is impossible to bypass the seven city bridges and return to the starting point by crossing each bridge exactly once. Graph theory received its next impetus almost 100 years later with the development of research on electrical networks, crystallography, organic chemistry and other sciences.
Without even noticing it, we encounter graphs all the time. For example, a graph is a diagram of subway lines. The dots on it represent stations, and the lines represent train routes. By researching our ancestry and tracing it back to a distant ancestor, we build a so-called family tree. And this tree is a graph.
Graphs serve as a convenient means of describing relationships between objects. We have previously used graphs as a way to visually represent finite binary relationships.
But the graph is used not only as an illustration. For example, considering a graph depicting a network of roads between settlements, you can determine the route from point A to point B. If there are several such routes, you would like to choose the optimal one in a certain sense, for example the shortest or the safest. To solve the selection problem, it is necessary to carry out certain calculations on graphs. When solving such problems, it is convenient to use algebraic techniques, and the very concept of a graph needs to be formalized.
Graph theory methods are widely used in discrete mathematics. It is impossible to do without them when analyzing and synthesizing various discrete converters: functional blocks of computers, software packages, etc.
Currently, graph theory covers a lot of material and is actively developing. When presenting it, we will limit ourselves to only part of the results and place the main emphasis on the description and justification of some widespread graph analysis algorithms that are used in the theory of formal languages.
Basic definitions
Graphs, as already noted in the examples, are a way of “visualizing” connections between certain objects. These connections can be “directed,” as, for example, in a family tree, or “undirected” (a network of two-way roads). In accordance with this, in graph theory there are two main types of graphs: directed (or directed) and undirected.
Presentation methods
So far, we have defined directed and undirected graphs, depicting them using drawings. You can define a graph as a pair of sets, following the definition, but this method is quite cumbersome and is rather of theoretical interest. The development of algorithmic approaches to analyzing the properties of graphs requires other ways of describing graphs that are more suitable for practical calculations, including using a computer. Let's look at the three most common ways to represent graphs.
Trees
Definition 5.5. An undirected tree is a connected and acyclic undirected graph. Definition 5.6. A directed tree is a non-contour directed graph in which the half-degree of any vertex is not greater than 1 and there is exactly one vertex, called the root of the directed tree, whose half-degree is 0.
Least weight spanning tree
The following problem is known in graph theory as the Steiner problem: n points are given on a plane; you need to connect them with straight segments in such a way that the total length of the segments is minimal.
Methods for systematically traversing graph vertices
Important problems in graph theory are the problems of global analysis of both undirected and directed graphs. These tasks include, for example, the task of finding cycles or contours, calculating the lengths of paths between pairs of vertices, listing paths with certain properties, etc. Global graph analysis should be distinguished from local analysis, an example of which is the problem of determining the sets of predecessors and successors of a fixed vertex of a directed graph.
Path problem in weighted directed graphs
Graph isomorphism
For a directed graph (V, E), the set E of arcs can be considered as a graph of a binary direct reachability relation defined on the set of vertices. In an undirected graph (V, E), the set E of edges is the set of unordered pairs. For each unordered pair (u, v) ∈ E we can assume that the vertices u and v are connected by a symmetric binary relation p, i.e. (u, v) ∈ р and (v, u) ∈ р.
Topological sorting
Definition 5.17. A directed network (or simply a network) is a contourless directed graph*. Since the network is a contourless graph, it can be shown that there are vertices (nodes) of the network with zero out-degree, as well as vertices (nodes) with zero in-degree. The former are called sinks or outputs of the network, and the latter are called sources or inputs of the network.
Elements of cyclomatics
When discussing the depth-first search algorithm in an undirected graph, the question of searching for the so-called fundamental cycles of the graph was considered. In this case, a fundamental cycle was understood as a cycle containing exactly one reverse edge, and a one-to-one correspondence was established between fundamental cycles and reverse edges; fundamental cycles arise whenever an arbitrary partition of all edges of an undirected graph into trees (forming some maximum edge forest of the original graph) and inverse, and in the general case this partition can be specified completely independently of the depth-first search algorithm. Depth-first search is just one way to implement such a partition.
The book by K. Berge is the first on graph theory in Russian. Meanwhile in recent years interest in the theory sharply increased both on the part of mathematicians and representatives of a wide variety of disciplines. This is explained by the fact that graph theory methods successfully solve numerous problems in the theory of electrical circuits, the theory of transport chains, information theory, cybernetics, etc.
In Berge's book, graph theory is presented sequentially, starting from the very basics. It is assumed that the reader has very modest mathematical knowledge, although he has some mathematical culture. The text includes numerous, often funny, examples. The book can be used for an initial study of graph theory. Professional mathematicians will also find a lot of interesting things in it.
An algorithm for directly identifying an Eulerian cycle.
[Fleury]. Let us consider a connected multigraph G, all of whose vertices have an even degree, and we will try to draw it with one stroke, without resorting to corrections in the already drawn part of the trajectory during the construction process. It is enough to adhere to the following rule:
1 We leave from an arbitrary vertex a; We cross out each passed edge.
2 We never go along such an edge and, which at the moment under consideration is an isthmus (i.e., when removed, the graph formed by uncrossed edges splits into two connected components having at least one edge each),
By following this rule, we will always be in a favorable position, because when we are at x = a, the graph (of uncrossed edges) has two vertices of odd degree: x and a; if isolated vertices are discarded, then a connected graph remains, which, by virtue of Theorem 1, has an Euler chain starting at x.
Content
Introduction
Chapter 1. Basic definitions
Sets and multivalued mappings
Graph. Paths and contours
Circuits and cycles
Chapter 2. Preliminary study of quasi-orderliness
Quasi-order defined by graph
Inductive graph and bases
Chapter 3. Ordinal function and function
Grundy for an infinite graph
General considerations regarding infinite graphs
Ordinal function
Grundy functions
Operations on graphs
Chapter 4. Basic numbers of graph theory
Cyclomatic number
Chromatic number
Internal stability number
External stability number
Chapter 5. Graph Kernels
Existence and uniqueness theorems
Application to Grundy functions
Chapter 6. Graph Games
Game Nim
General definition of the game (with full information)
Strategies
Chapter 7. Shortest Path Problem
Processes by stages Some generalizations
Chapter 8. Transport networks
Maximum Flow Problem Least Flow Problem
The Set-Value Compatible Flow Problem
Endless transport networks
Chapter 9. Theorem on half-powers
Semi degree of outgoing and entering
Chapter 10. Matching a simple graph
Maximum matching problem
Simple graph deficiency
Hungarian algorithm
Generalization to the infinite case
Application to matrix theory
Chapter 11. Factors
Hamiltonian paths and Hamiltonian contours
Finding a factor
Finding a partial graph with given half-degrees
Chapter 12. Graph Centers
Centers
Radius
Chapter 13. Diameter of a strongly connected graph
General properties of strongly connected graphs without loops
Diameter
Chapter 14. Graph Adjacency Matrix
Application of conventional matrix operations
Counting problems
Leader problem
Using Boolean Operations
Chapter 15. Incident matrices
Completely unimodular matrices
Completely unimodular systems
Cyclomatic matrices
Chapter 16. Trees and ancestral trees
Trees
Analytical research
Grandtrees
Chapter 17. Euler's problem
Euler cycles Euler contours
Chapter 18. Matching an arbitrary graph
Alternating Circuit Theory
Finding a partial graph with given vertex degrees
Perfect matching
Application to the internal stability number
Chapter 19. Factoroids
Hamiltonian cycles and factoroids
Necessary and sufficient condition for the existence of a factoroid
Chapter 20. Graph Connectivity
Articulation points
Graphs without articulations
h-connected graphs
Chapter 21. Planar graphs
Basic properties
Generalization
Additions
I. Off general theory, games
II. About transport tasks
III. On the use of potential concepts in transport networks
IV. Unsolved problems and unproven assumptions
V. On some basic principles of counting (J. Riguet)
VI. Additions to the Russian translation (A.A. Zykov and G.I. Kozhukhin)
Literature
Graph theory and the book of C. Berge (afterword to the Russian translation)
Character index
Name index
Subject index.
Download the e-book for free in a convenient format, watch and read:
Download the book Graph Theory and Its Applications, Berge K. - fileskachat.com, fast and free download.
Back Forward
Attention! Slide previews are for informational purposes only and may not represent all the features of the presentation. If you are interested this work, please download the full version.
Lesson objectives:
Equipment:
- computer class equipped with modern technology, video projector, screen;
- computers with Windows XP OS, Microsoft program Office 2003 PowerPoint;
- board equipment (lesson topic, new terms). Handout material.
Lesson plan.
II. Presentation of new material. (10 min.)
III. Fixing the material. Practical work. (15-20 min.)
IV. Summing up the lesson. (2 min)
V. Homework.
I. Organizational moment. Updating knowledge.
Hello! Our lesson is called “Graphs”. We will get acquainted with the concept of “Graphs”, learn how to depict them and solve problems on this topic.
II Presentation of new material.
The first work on graph theory belongs to Leonhard Euler (1736), although the term “graph” was first introduced in 1936 by the Hungarian mathematician Dénes König. Graphs are diagrams consisting of points and straight or curved segments connecting these points (examples of graphs are shown in Figure 1)
With the help of graphs, the solution of problems formulated in various fields of knowledge was often simplified: in automation, electronics, physics, chemistry, etc. With the help of graphs, diagrams of roads, gas pipelines, heat and electricity networks are depicted. Graphs help in solving mathematical and economic problems.
Graph – (from the Greek grapho – I write) is a means of visually representing the elements of an object and the connections between them. These are wonderful mathematical objects; with their help you can solve a lot of different, outwardly dissimilar problems.
A graph is some kind of information model
The graph consists of vertices or nodes connected by arcs or segments - edges. A line can be directed, that is, have an arrow (arc); if not directed, it has an edge. Two vertices connected by an arc or edge are called adjacent.
Examples of graphs (Slide 4, 5, 6)
Task 1 (Slide 7):
Space communication has been established between the nine planets of the solar system. Scheduled rockets fly on the following routes:
Earth - Mercury; Pluto - Venus; Earth - Pluto; Pluto - Mercury; Mercury - Venus; Uranus - Neptune; Neptune - Saturn; Saturn – Jupiter; Jupiter - Mars; Mars - Uranus.
Is it possible to fly on regular rockets from Earth to Mars?
Solution: Let's draw a diagram of the condition: we'll represent the planets as dots, and the rocket routes as lines.
Now it is immediately clear that it is impossible to fly from Earth to Mars.
Two vertices connected by an arc or edge are called adjacent. Each edge or arc is associated with a number. The number can indicate the distance between settlements, the time of transition from one peak to another, etc.
Task 2 (9 slide) – solution at the board. Masha came to the zoo and wants to see as many animals as possible. Which path should she take? Yellow, red, green?
Task 3 (11 slide) – solution at the board. Five football teams A, B, C, D, D must play matches against each other. Already played A with B, C, D; B with A, C, D. how many matches have already been played? How much time is left to play?
Presentation of graphs (Slide 12)
The graph can be presented as a list of arcs (AB; 7), graphically or using a table.
| Arc lists | Graphic form | Tabular form | ||||||||||||||||
| (AB; 7), |  |
|
III. Reinforcing materials: Students are asked to divide into groups and complete assignments. Working in small group, students discuss models based on the theoretical knowledge acquired at the beginning of the lesson. This ensures repetition and consolidation of the material.
Task 2 (Slide 13)
IV. Lesson summary
Guys, what new words did you learn today? (Graph, vertex of the graph, edges of the graph.)
What can the vertices of the graph represent? (Cities; objects that are; connected.)
What do the edges of the graph mean (paths, movements, directions)
Give an example of where in life we can meet them?
How are graphs depicted?
V. Homework. (Slide 15)
Graph theory is a branch of discrete mathematics that studies objects represented as individual elements (vertices) and connections between them (arcs, edges).
Graph theory originates from the solution of the problem of the Königsberg bridges in 1736 by the famous mathematician Leonard Euler(1707-1783: born in Switzerland, lived and worked in Russia).
Problem about the Königsberg bridges.
There are seven bridges in the Prussian town of Königsberg on the Pregal River. Is it possible to find a walking route that goes exactly once over each of the bridges and starts and ends in the same place?
A graph in which there is a route that starts and ends at the same vertex and passes along all the edges of the graph exactly once is calledEuler graph.
The sequence of vertices (maybe repeated) through which the desired route passes, like the route itself, is calledEuler cycle .
The problem of three houses and three wells.
There are three houses and three wells, somehow located on a plane. Draw a path from each house to each well so that the paths do not intersect. This problem was solved (it was shown that there is no solution) by Kuratovsky (1896 - 1979) in 1930.
The four color problem. Partitioning a plane into non-intersecting areas is called by card. Map areas are called adjacent if they have a common border. The task is to color the map in such a way that no two adjacent areas are painted with the same color. Since the end of the 19th century, a hypothesis has been known that four colors are enough for this. The hypothesis has not yet been proven.
The essence of the published solution is to try a large but finite number (about 2000) types of potential counterexamples to the four-color theorem and show that not a single case is a counterexample. This search was completed by the program in about a thousand hours of supercomputer operation.
It is impossible to check the resulting solution “manually” - the scope of enumeration is beyond the scope of human capabilities. Many mathematicians raise the question: can such a “program proof” be considered a valid proof? After all, there may be errors in the program...
Thus, we can only rely on the programming skills of the authors and believe that they did everything right.
Definition 7.1. Count G= G(V, E) is a collection of two finite sets: V – called many vertices and the set E of pairs of elements from V, i.e. EÍV´V, called many edges, if the pairs are unordered, or many arcs, if the pairs are ordered.
In the first case, the graph G(V, E) called unoriented, in the second – oriented.
EXAMPLE. A graph with a set of vertices V = (a,b,c) and a set of edges E =((a, b), (b, c))
EXAMPLE. A graph with V = (a,b,c,d,e) and E = ((a, b), (a, e), (b, e), (b, d), (b, c) , (c, d)),
If e=(v 1 ,v 2), еОЕ, then they say that the edge is e connects vertices v 1 and v 2.
Two vertices v 1,v 2 are called adjacent, if there is an edge connecting them. In this situation, each of the vertices is called incident corresponding edge .
Two different ribs adjacent, if they have a common vertex. In this situation, each of the edges is called incidental corresponding vertex .
Number of graph vertices G let's denote v, and the number of edges is e:
.
The geometric representation of the graphs is as follows:
1) the vertex of the graph is a point in space (on the plane);
2) an edge of an undirected graph – a segment;
3) an arc of a directed graph – a directed segment.
Definition 7.2. If in the edge e=(v 1 ,v 2) v 1 =v 2 occurs, then the edge e is called loop. If a graph allows loops, then it is called graph with loops or pseudograph .
If a graph allows more than one edge between two vertices, then it is called multigraph .
If each vertex of a graph and/or edge is labeled, then such a graph is called marked (or loaded ). Letters or integers are usually used as marks.
Definition 7.3. Graph G (V , E ) called subgraph (or part ) graph G(V,E), If V V, E E. If V = V, That G called spanning subgraph G.
Example 7 . 1 . Given an undirected graph.
Definition 7.4. The graph is called complete , If any its two vertices are connected by an edge. Complete graph with n vertices is denoted by K n .
Counts K 2 , TO 3, TO 4 and K 5 .
Definition 7.5. Graph G=G(V, E) is called dicotyledonous , If V can be represented as a union of disjoint sets, say V=AB, so each edge has the form ( v i , v j), Where v i A And v j B.
Each edge connects a vertex from A to a vertex from B, but no two vertices from A or two vertices from B are connected.
A bipartite graph is called complete dicotyledon count K m , n, If A contains m peaks, B contains n vertices and for each v i A, v j B we have ( v i , v j)E.
Thus, for everyone v i A, And v j B there is an edge connecting them.
K 12 K 23 K 22 K 33
Example 7 . 2 . Construct a complete bipartite graph K 2.4 and the full graph K 4 .
Unit graphn-dimensional cubeIN n .
The vertices of the graph are n-dimensional binary sets. Edges connect vertices that differ in one coordinate.
Example: 
The following practical puzzle was common among the residents of Königsberg: is it possible to cross all the bridges over the Pregolya River without passing over any of them twice? In 1736, the eminent mathematician Leonhard Euler became interested in the problem and, in a letter to a friend, provided a rigorous proof that it could not be done. In the same year, he proved a remarkable formula that relates the number of vertices, faces and edges of a polyhedron in three-dimensional space. The formula is mysteriously true for graphs that are called “planar”. These two results laid the foundation for graph theory and well illustrate the direction of its development to this day.
About the course
This course serves as an introduction to modern theory graphs A graph as a mathematical object turns out to be useful in many theoretical and practical problems. The point, perhaps, is that the complexity of its structure corresponds well to the capabilities of our brain: it is a visual and clearly structured structure, but, on the other hand, rich enough to capture many non-trivial phenomena. If we talk about applications, then, of course, large networks immediately come to mind: Internet, road map, coverage mobile communications etc. Search engines such as Yandex and Google are based on graph algorithms. In addition to computer science, graphs are actively used in bioinformatics, chemistry, and sociology. In our course, we will, of course, discuss classical problems, but we will also talk about more recent results and trends, for example, about extremal graph theory.
Format
The course consists of 7 training weeks and an exam. To successfully solve most test problems, it is enough to master the material covered in lectures. Seminars cover more complex tasks, which will be of interest to a listener already familiar with the basics of graph theory.
Information resources
- V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich. Lectures on graph theory. M.: Book house “Librokom”, 2009.
- A. A. Zykov. Finite graph theory. Novosibirsk: Nauka, 1969.
- M. Swami, K. Thulasiraman. Graphs, networks and algorithms. M.: Mir, 1984.
- M. Aigner, G. M. Ziegler. Proofs From THE BOOK. Fourth Edition. Springer, 2009.
- B. Bollobás. Modern Graph Theory. Springer, 1998.
- J. A. Bondy, U. S. R. Murty. Graph Theory. Springer, 2008.
Requirements
The material is presented from the very basics and accessible language. The purpose of this course is not only to introduce you to issues and methods of graph theory, but also to develop a culture of mathematical thinking among unprepared students. Therefore, the course is available to a wide range of students. To master the material, a good knowledge of mathematics will be enough. school level And basic knowledge combinatorics.
Course program
- The concept of a graph and types of graphs.
- Various Applications Counts: from the Königsberg Bridges to the Internet.
- Graph connectivity, subgraphs and vertex degree.
- Equivalent tree definitions.
- Planarity and the Kuratowski criterion
- Euler's formula.
- Chromatic number of a planar graph.
- Enumerating trees: Prüfer code and Cayley's formula.
- Formula for the number of unicyclic graphs.
- Euler cycles and the Euler criterion.
- Hamiltonian cycles. Dirac criterion and Chvatal criterion.
- Matchings. Theorem of Hall and Koenig.
- Extreme graph theory. Turan's theorem.
- An analogue of Turan's theorem for graphs on a plane.
- Ramsey's theory. Dating among six people.
- Determination of Ramsey number.
- Lower and upper bounds for Ramsey numbers.
Learning outcomes
Upon successful completion of the course, the student will become familiar with the concept of a graph, the types and various characteristics and properties of graphs. The listener will learn about the problem of regular colorings and the possibility of drawing a given graph on a plane without intersecting edges, and will also learn in different ways identify trees and list them. Finally, the listener will become familiar with the concepts of Euler and Hamiltonian cycles, matchings, and even touch on problems in extremal graph theory.