Презентация Graph theory онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Graph theory абсолютно бесплатно. Урок-презентация на эту тему содержит всего 44 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:44 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:2.03 MB
- Просмотров:83
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Graph theory
Irina Prosvirnina
Labeled graphs
Operations on graphs
Intersection graphs
Metrical characteristics of graphs
König’s theorem
№2 слайд
Содержание слайда: Labeled graphs
Definition 1
A graph is labeled when the points are distinguished from one another by names such as , .
For example, the two graphs and of the following
figures are labeled but is not.
№3 слайд
Содержание слайда: Labeled graphs
№4 слайд
Содержание слайда: Unlabeled graph
№5 слайд
Содержание слайда: Labeled graphs
Theorem 1 The number of labeled graphs with points is
Proof
All of the labeled graphs with three points are shown in the following figure.
№6 слайд
Содержание слайда: The labeled graphs with three points
№7 слайд
Содержание слайда: We see that the 4 different graphs with 3 points become 8 different labeled graphs.
№8 слайд
Содержание слайда: We see that the 4 different graphs with 3 points become 8 different labeled graphs.
To obtain the number of labeled graphs with points, we need only observe that each of the possible lines is either present or absent.
№9 слайд
Содержание слайда: Labeled graphs
To obtain the number of labeled graphs with points, we need only observe that each of the possible lines is either present or absent.
№10 слайд
Содержание слайда: Operations on graphs
A subgraph of is a graph having all of its points and lines in .
If is a subgraph of , then is a supergraph of .
A spanning subgraph is a subgraph containing all the points of .
For any set of points of , the induced subgraph is the maximal subgraph of with point set .
Thus two points of are adjacent in if and only if they are adjacent in .
№11 слайд
Содержание слайда: Operations on graphs
is a spanning subgraph of but is not; is an induced subgraph but is not.
№12 слайд
Содержание слайда: Operations on graphs
The removal of a point from a graph results in that subgraph of consisting of all points of except and all lines not incident with .
Thus is the maximal subgraph of not containing .
№13 слайд
Содержание слайда: Operations on graphs
On the other hand, the removal of a line from yields the spanning subgraph containing all lines of except .
Thus is the maximal subgraph of not containing
№14 слайд
Содержание слайда: Operations on graphs
The removal of a set of points or lines from is defined by the removal of single elements in succession.
№15 слайд
Содержание слайда: Operations on graphs
On the other hand, if and are not adjacent in , the addition of line results in the smallest supergraph of containing the line .
These concepts are illustrated in the following figures.
№16 слайд
Содержание слайда: A graph plus or minus a specific point or line
№17 слайд
Содержание слайда: A graph plus or minus a specific point or line
№18 слайд
Содержание слайда: A graph plus or minus a specific point or line
№19 слайд
Содержание слайда: Operations on graphs
There are certain graphs for which the result of deleting a point or line, or adding a line, is independent of the particular point or line selected.
A graph plus or minus a point or line.
№20 слайд
Содержание слайда: Operations on graphs
It was suggested by Ulam in the following conjecture that the collection of subgraphs — of gives quite a bit of information about itself.
Ulam's Conjecture Let have points and have points , with . If for each , the subgraphs and are isomorphic, then the graphs and are isomorphic.
№21 слайд
Содержание слайда: Operations on graphs
It is rather convenient to be able to express the structure of a given graph in terms of smaller and simpler graphs.
№22 слайд
Содержание слайда: Operations on graphs
Let graphs and have disjoint point sets and and line sets and respectively.
Their union has, as expected, and .
Their join is denoted and consists of and all lines joining with .
These operations are illustrated in the following figure.
№23 слайд
Содержание слайда: Operations on graphs
The union of two graphs.
№24 слайд
Содержание слайда: Operations on graphs
The join of two graphs.
№25 слайд
Содержание слайда: Operations on graphs
There are several operations on and which result in a graph whose set of points is the cartesian product .
These include the product (or cartesian product), and the composition (or lexicographic product).
№26 слайд
Содержание слайда: Operations on graphs
To define the product consider any two points and in .
Then and are adjacent in whenever and and are adjacent in or and and are adjacent in .
№27 слайд
Содержание слайда: Operations on graphs
The product of two graphs.
№28 слайд
Содержание слайда: Operations on graphs
The composition also has as its point set, and is adjacent with whenever and are adjacent in or and and are adjacent in .
№29 слайд
Содержание слайда: Two compositions of graphs
№30 слайд
Содержание слайда: Two compositions of graphs
№31 слайд
Содержание слайда: Operations on graphs
The compositions and are obviously not isomorphic.
№32 слайд
Содержание слайда: Operations on graphs
An especially important class of graphs known as cubes are most naturally expressed in terms of products.
The -cube is defined recursively by and .
Thus has points which may be labeled where each is either or .
Two points of are adjacent if their binary representations differ at exactly one place.
№33 слайд
Содержание слайда: Operations on graphs
Figure shows both the 2-cube and the 3-cube, appropriately labeled.
№34 слайд
Содержание слайда: Intersection graphs
Let be a set and a family of distinct nonempty subsets of whose union is .
The intersection graph of is denoted and defined by , with and adjacent whenever and .
Then a graph is an intersection graph on if there exists a family of subsets of for which .
№35 слайд
Содержание слайда: Intersection graphs
Theorem 1
Every graph is an intersection graph.
Proof
For each point of , let be the union of with the set of lines incident with .
Then it is immediate that is isomorphic with where .
№36 слайд
Содержание слайда: Metrical characteristics of graphs
A walk of a graph is an alternating sequence of points and lines beginning and ending with points, in which each line is incident with the two points immediately preceding and following it.
It is a trail if all the lines are distinct, and a path if all the points (and thus necessarily all the lines) are distinct.
If the walk is closed, then it is a cycle provided its n points are distinct and .
№37 слайд
Содержание слайда: Metrical characteristics of graphs
The length of a walk is , the number of occurrences of lines in it.
The girth of a graph , denoted , is the length of a shortest cycle (if any) in ;
the circumference is the length of any longest cycle.
Note that these terms are undefined if has no cycles.
№38 слайд
Содержание слайда: Metrical characteristics of graphs
The distance between two points and in is the length of a shortest path joining them if any; otherwise .
In a connected graph, distance is a metric; that is, for all points , and ,
, with if and only if .
№39 слайд
Содержание слайда: Metrical characteristics of graphs
A shortest path is often called a geodesic.
The diameter of a connected graph is the length of any longest geodesic.
№40 слайд
Содержание слайда: Metrical characteristics of graphs
The graph of the figure has girth , circumference , and diameter .
A graph to illustrate walks.
№41 слайд
Содержание слайда: König’s theorem
A bigraph (or bipartite graph) is a graph whose point set can be partitioned into two subsets and such that every line of joins with
№42 слайд
Содержание слайда: König’s theorem
Theorem (König’s theorem)
A graph is bipartite if and only if all its cycles are even.
Proof
If is a bigraph, then its point set can be partitioned into two sets and so that every line of joins a point of with a point of .
Thus every cycle in necessarily has its oddly subscripted points in say, and the others in , so that its length is even.
№43 слайд
Содержание слайда: Theorem (König’s theorem)
A graph is bipartite if and only if all its cycles are even.
Proof
For the converse, we assume, without loss of generality, that is connected (for otherwise we can consider the components of G separately).
Take any point , and let consist of and all points at even distance from while .
№44 слайд
Содержание слайда: Theorem (König’s theorem)
A graph is bipartite if and only if all its cycles are even.
Proof
Take any point , and let consist of and all points at even distance from while .
Since all the cycles of are even, every line of joins a point of with a point of .
For suppose there is a line joining two points of .
Then the union of geodesies from to and from to together with the line contains an odd cycle, a contradiction.
Скачать все slide презентации Graph theory одним архивом:
