🗊Презентация Graph theory

Категория: Математика
Нажмите для полного просмотра!
Graph theory, слайд №1Graph theory, слайд №2Graph theory, слайд №3Graph theory, слайд №4Graph theory, слайд №5Graph theory, слайд №6Graph theory, слайд №7Graph theory, слайд №8Graph theory, слайд №9Graph theory, слайд №10Graph theory, слайд №11Graph theory, слайд №12Graph theory, слайд №13Graph theory, слайд №14Graph theory, слайд №15Graph theory, слайд №16Graph theory, слайд №17Graph theory, слайд №18Graph theory, слайд №19Graph theory, слайд №20Graph theory, слайд №21Graph theory, слайд №22Graph theory, слайд №23Graph theory, слайд №24Graph theory, слайд №25Graph theory, слайд №26Graph theory, слайд №27Graph theory, слайд №28Graph theory, слайд №29Graph theory, слайд №30Graph theory, слайд №31Graph theory, слайд №32Graph theory, слайд №33Graph theory, слайд №34Graph theory, слайд №35Graph theory, слайд №36Graph theory, слайд №37Graph theory, слайд №38Graph theory, слайд №39Graph theory, слайд №40Graph theory, слайд №41Graph theory, слайд №42Graph theory, слайд №43Graph theory, слайд №44
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Graph theory. Доклад-сообщение содержит 44 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Graph theory Irina Prosvirnina Labeled graphs Operations on graphs Intersection graphs Metrical characteristics of graphs König’s theorem
Описание слайда:
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.
Описание слайда:
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
Описание слайда:
Labeled graphs

Слайд 4


Unlabeled graph
Описание слайда:
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.
Описание слайда:
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
Описание слайда:
The labeled graphs with three points

Слайд 7


We see that the 4 different graphs with 3 points become 8 different labeled graphs.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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 .
Описание слайда:
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.
Описание слайда:
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 .
Описание слайда:
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
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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
Описание слайда:
A graph plus or minus a specific point or line

Слайд 17


A graph plus or minus a specific point or line
Описание слайда:
A graph plus or minus a specific point or line

Слайд 18


A graph plus or minus a specific point or line
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
Operations on graphs The union of two graphs.

Слайд 24


Operations on graphs The join of two graphs.
Описание слайда:
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).
Описание слайда:
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 .
Описание слайда:
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.
Описание слайда:
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 .
Описание слайда:
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
Описание слайда:
Two compositions of graphs

Слайд 30


Two compositions of graphs
Описание слайда:
Two compositions of graphs

Слайд 31


Operations on graphs The compositions and are obviously not isomorphic.
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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 .
Описание слайда:
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 .
Описание слайда:
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 .
Описание слайда:
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.
Описание слайда:
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 .
Описание слайда:
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.
Описание слайда:
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.
Описание слайда:
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
Описание слайда:
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.
Описание слайда:
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 .
Описание слайда:
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.
Описание слайда:
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.

Скачать

Теги Graph theory
Похожие презентации
Mypresentation.ru
Загрузить презентацию