Графы и их применение

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

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

Рис. 1

степени вершин в графе на рисунке 2.
На рисунке 3 изображен

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

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

Рис. 2

которых надо найти
Все существующие решения
Самое короткое решение или длинное решение
Разработать

стратегию игры
И так далее.

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

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

продолжительного пути 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