Graph theory irina prosvirnina. Definitions and examples. Paths and cycles презентация

Содержание

Definitions and examples  

Слайд 1Graph theory

Irina Prosvirnina

Definitions and examples
Paths and cycles


Слайд 2Definitions and examples
 


Слайд 3Definitions and examples
Euler (1707 – 1783) was born in Switzerland and

spent most of his long life in Russia (St Petersburg) and Prussia (Berlin).
He was the most prolific mathematician of all time, his collected works filling more than 70 volumes.



Слайд 4Definitions and examples
Like many of the very great mathematicians of his

era, Euler contributed to almost every branch of pure and applied mathematics.
He is also responsible, more than any other person, for much of the mathematical notation in use today.



Слайд 5Definitions and examples
What is a ‘graph’? Intuitively, a graph is simply

a collection of points, called ‘vertices’, and a collection of lines, called ‘edges’, each of which joins either a pair of points or a single point to itself.
A familiar example, which serves as a useful analogy, is a road map which shows towns as vertices and the roads joining them as edges.

Слайд 6Definitions and examples
 


Слайд 7Definitions and examples












 


Слайд 8Definitions and examples
 


Слайд 9Definitions and examples
 


Слайд 10Definitions and examples
 


Слайд 11Definitions and examples
Definition 2
The degree sequence of a graph is the

sequence of its vertex degrees arranged in non-decreasing order.

Слайд 12Definitions and examples












 


Слайд 13Definitions and examples












 


Слайд 14Definitions and examples












The degrees of the four vertices are given in

the following table.


Слайд 15Definitions and examples












 


Слайд 16Definitions and examples












A well known 3-regular simple graph is Peterson’s graph.

Two diagrams representing this graph are given in the figure.
In drawing diagrams of graphs we only allow edges to meet at vertices. It is not always possible to draw diagrams in the plane satisfying this property, so we may need to indicate that one edge passes underneath another as we have done in the figure.

Слайд 17Definitions and examples
 


Слайд 18Definitions and examples
Example 1
Since a complete graph is simple there are

no loops and each pair of distinct vertices is joined by a unique edge. Clearly a complete graph is uniquely specified by the number of its vertices.

Слайд 19Definitions and examples
 


Слайд 20Definitions and examples
Example 1
The complete graphs with three, four and five

vertices are illustrated in the figure.


Слайд 21Definitions and examples
 


Слайд 22Definitions and examples
 


Слайд 23Definitions and examples
 


Слайд 24Definitions and examples
 


Слайд 25Definitions and examples
 


Слайд 26Definitions and examples












 


Слайд 27Definitions and examples












 


Слайд 28Definitions and examples












 


Слайд 29Definitions and examples












 


Слайд 30Definitions and examples












 


Слайд 31Definitions and examples
 


Слайд 32Definitions and examples
Example 4
A complete graph has adjacency matrix with zeros

along the leading diagonal (since there are no loops) and ones everywhere else (since every vertex is joined to every other by a unique edge).

Слайд 33Definitions and examples
 


Слайд 34Definitions and examples
 


Слайд 35Paths and cycles
Using the analogy of a road map, we can

consider various types of ‘journeys’ in a graph.
For instance, if the graph actually represents a network of roads connecting various towns, one question we might ask is: is there a journey, beginning and ending at the same town, which visits every other town just once without traversing the same road more than once?
As usual, we begin with some definitions.












Слайд 36Paths and cycles
 


Слайд 37Paths and cycles
 


Слайд 38Paths and cycles
 


Слайд 39Paths and cycles
An edge sequence is any finite sequence of edges

which can be traced on the diagram of the graph without removing pen from paper. It may repeat edges, go round loops several times, etc.










Слайд 40Paths and cycles
Edge sequences are too general to be of very

much use which is why we have defined paths.











Слайд 41Paths and cycles
In a path we are not allowed to ‘travel

along’ the same edge more than once.









Слайд 42Paths and cycles
If, in addition, we do not ‘visit’ the same

vertex more than once (which rules out loops), then the path is simple.










Слайд 43Paths and cycles
The edge sequence or path is closed if we

begin and end the ‘journey’ at the same place.










Слайд 44Paths and cycles












 


Слайд 45Paths and cycles












 


Слайд 46Paths and cycles












 


Слайд 47Paths and cycles












 


Слайд 48Paths and cycles












 


Слайд 49Paths and cycles












 


Слайд 50Paths and cycles












 


Слайд 51Paths and cycles
 


Слайд 52Paths and cycles












 


Слайд 53Paths and cycles












 


Слайд 55Paths and cycles
 


Слайд 56Paths and cycles












 


Слайд 57Paths and cycles












 


Слайд 58Paths and cycles
 


Слайд 59Paths and cycles
In an intuitively obvious sense, some graphs are ‘all

in one piece’ and others are made up of several pieces.
We can use paths to make this idea more precise.









Слайд 60Paths and cycles
Definition 7
A graph is connected if, given any pair

of distinct vertices, there exists a path connecting them.








Слайд 61Paths and cycles
An arbitrary graph naturally splits up into a number

of connected subgraphs, called its (connected) components.
The components can be defined formally as maximal connected subgraphs.









Слайд 62Paths and cycles
 


Слайд 63Paths and cycles
The components of a graph are just its connected

‘pieces’.
In particular, a connected graph has only one component.
Decomposing a graph into its components can be very useful.
It is usually simpler to prove results about connected graphs and properties of arbitrary graphs can frequently then be deduced by considering each component in turn.









Слайд 64Paths and cycles
 


Слайд 65Paths and cycles
 


Слайд 66Paths and cycles
 


Слайд 67Paths and cycles












 


Слайд 68Paths and cycles
 


Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика