Презентация на тему Графы и их применение

из множества точек и множества отрезков, оба конца которых

принадлежат заданному множеству точек.
Степень вершины называется число ребер графа, которым принадлежит эта вершина.
Путь графе от А1 до Аn в графе называется такая последовательность ребер, ведущая от А1 до Аn, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза.
Цикл в графе называется путь, в котором совпадают его начальная и конечная вершины.
Граф называется несвязным, если существуют хотя бы две вершины несвязные путем
Граф называется деревом, если для каждой пары вершин существует единственный соединяющий их путь

Рис. 1

являются деревьями?
Найдите степени вершин в графе на рисунке 2.
На

рисунке 3 изображен граф. Назовите один из путей от A до F . Существует ли путь от A до F проходящий через все вершины графа?
Найдите в графе на рисунке 3 циклы, содержащие:
3 ребра;
6 ребер;

Найдите несвязные графы .

Рис. 2

задач, в которых надо найти
Все существующие решения
Самое короткое решение

или длинное решение
Разработать стратегию игры
И так далее.

пункта в пункт можно только в направлении стрелок. В

каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 9? У какого из путей наименьшая длина? У какого наибольшая длина?

2.
Длина наиболее продолжительного пути 7: 1 2 3 6

5 7 8 9.
Число путей 14

на пересечениях строк и столбцов таблиц, означают стоимость проезда

между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними.
Укажите таблицу, для которой выполняется условие: “Минимальная стоимость проезда
из А в B не больше 6”.
Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.

1)

2)

3)

4)

AC C B - 7
AC CE EB - 7

AC C B - 7
AE EC CB - 7

AC C B - 7
AC CE EB - 6

AD DC CB - 9
AD DC CE EB - 8

лежат две кучки камней, в первой из которых 3,

а во второй – 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 1 камень в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16 камней. Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.

3,18, ∑ 21

3,2, ∑ 5