Задача 1. Перенесите граф в тетрадь, запишите все возможные пути из А в К. Например: АГВК;…В ответ запишите количество всех

Задача 2. Развозчик пиццы из города V0 должен доставить товар в 7 городов, которые соединены дорогами (схема на графе) и

836.09K

Category: $mathematics$ mathematics

Путь и цикл

3.

Как в графе по рёбрам можно «пройти»
из вершины А в вершину В?
F
G
E
D
В
А
C

4.

Как в графе по рёбрам можно «пройти»
из вершины А в вершину В?
F
G
E
D
В
А
C
Из вершины А в вершину В можно «пройти»
разными способами: АСВ;

5.

Как в графе по рёбрам можно «пройти»
из вершины А в вершину В?
F
G
E
D
В
А
C
Из вершины А в вершину В можно «пройти»
разными способами: АСВ; АDFEB;

6.

Как в графе по рёбрам можно «пройти»
из вершины А в вершину В?
F
G
E
D
В
А
C
Из вершины А в вершину В можно «пройти»
разными способами: АСВ; АDFEB; ADCADCB; …

7.

F
G
E
D
В
А
C
Последовательность рёбер графа, соединяющих
вершины, называется путём из одной вершины в другую.

8.

Чем отличается путь ADCADCB
от путей АСВ и АDFEB?
F
G
E
D
В
А
C

9.

Чем отличается путь ADCADCB
от путей АСВ и АDFEB?
F
G
E
D
В
А
C
В путях АСВ и АDFEB вершины и рёбра не повторяются.

10.

F
G
E
D
В
А
C
Путь, в котором вершины и рёбра не повторяются,
называется простым путём или цепью.

11.

Граф, состоящий из одной − единственной цепи, − цепь.
F
E
G
В
Граф, состоящий из одной вершины, − цепь.
А

13.

Какими путями можно пройти без повторения
рёбер из вершины А в ту же вершину А?
F
G
E
D
В
А
C

14.

Какими путями можно пройти без повторения
рёбер из вершины А в ту же вершину А?
F
G
E
D
В
А
C
Из вершины А в вершину А можно пройти без
повторения рёбер разными путями: ADCA,

15.

Какими путями можно пройти без повторения
рёбер из вершины А в ту же вершину А?
F
G
E
D
В
А
C
Из вершины А в вершину А можно пройти без
повторения рёбер разными путями: ADCA, ADFEBCA,…

16.

F
G
E
D
В
А
C
Замкнутый путь, у которого начало и конец в одной
вершине, а рёбра и промежуточные вершины не
повторяются, называется циклом.

17.

Граф, состоящий из одного − единственного цикла, − цикл.
F
E
D
В
C
Граф, состоящий из одной вершины и одного ребра, − цикл.
G

19.

Какой граф называется связным?
Связный граф
Несвязный граф

20.

Какой граф называется связным?
Связный граф
Несвязный граф
Граф называется связным, если две любые
вершины в этом графе связаны путём.

22.

Упражнение №1
да
На рисунке изображён граф.
Является ли граф цепью?
нет

23.

Упражнение №1
да
На рисунке изображён граф.
Является ли граф цепью?

24.

Упражнение №1
да
На рисунке изображён граф.
Является ли граф цепью?

25.

Упражнение №1
да
На рисунке изображён граф.
Является ли граф цепью?

26.

Упражнение №1
да
На рисунке изображён граф.
Является ли граф цепью?

27.

Упражнение №1
да
На рисунке изображён граф.
Является ли граф цепью?

28.

Упражнение №2
да
На рисунке изображён граф.
Является ли граф цепью?
нет

29.

Упражнение №2
На рисунке изображён граф.
Является ли граф цепью?
нет

30.

Упражнение №3
да
На рисунке изображён граф.
Является ли граф цепью?
нет

31.

Упражнение №3
да
На рисунке изображён граф.
Является ли граф цепью?

32.

Упражнение №4
да
На рисунке изображён граф.
Является ли граф цепью?
нет

33.

Упражнение №4
На рисунке изображён граф.
Является ли граф цепью?
нет