1. В харчевне «Три пескаря» на первое предлагали борщ из свежей капусты и уху, на второе – куриные окорочка, жареную индейку и котлеты, на десерт – апельсиновое мороженое и компот. Сколько вариантов обедов можно получить из этого набора блюд, если каждый обед должен состоять из одного первого блюда, одного второго и одного десерта?
Путём<от А1 до Аn в графе называется такая последовательность рёбер, ведущая от А1 до Аn, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза.
2. Составьте различные последовательности рёбер, ведущих от вершины А1 к вершине А5.
Есть ли среди твоих последовательностей такая: А1А2; А2А4; А4А3; А3А2; А2А4; А4А5? Какие из последовательностей будут являться путями?
Вершина А1 называется началом пути; вершина Аn – конец пути. Путь, в котором начало и конец совпадают, называется циклом. Найди цикл на рисунке к задаче 2.
Число рёбер графа, выходящих из данной вершины, называется степенью вершины. Определи степень каждой вершины на рисунке.
Деревом называют граф, который не имеет циклов, то есть для каждой пары вершин графа существует единственный, соединяющий их, путь. Вершина дерева, степень которой равна единице, называется висячей вершиной. Назови висячие вершины на рисунке.
3. Проводится эксперимент: морскую свинку пускают в лабиринт:/p>
Сколькими способами морская свинка может попасть к пищи, если она не в один тупик не заходит более одного раза, причем, попав в тупик, возвращается на перекресток, с которого свернула в этот тупик. Какова длина самого короткого маршрута к пище и самого длинного маршрута?
4. Нарисуй «дерево»-схему розыгрыша Кубка, в котором участвуют 16 команд. Сколько туров будет проведено в розыгрыше Кубка? Сколько команд участвует в ¼ финала; в ½ финала? Сколько матчей придется сыграть командам для выявления обладателя Кубка?
5. Найти два пути, связывающие вершины А1 и А3.
6. Найдется ли путь от А1 до А8, содержащий все вершины графа:
Назовите пути наименьшей и наибольшей длины от А1 до А2 и от А1 до А7
7. Нарисуйте граф с семью вершинами и шестью рёбрами, не имеющий ни одного цикла.
8. Изобразите цикл с шестью рёбрами. Сколько у него вершин?
9. Из графа удалите часть рёбер так, чтобы новый граф был «деревом», содержащим все вершины графа.
10. При составлении расписания занятий учителя математики и русского языка высказали пожелание, чтобы их уроки были первыми; учителя истории, географии и биологии попросили поставить свои уроки вторыми; учителя физкультуры и музыки попросили поставить свои уроки третьими. Сколько вариантов расписания можно составить, если в день должно быть три урока? Сколько вариантов расписания получится, если в день будет проводиться четыре урока (четвёртым уроком может быть рисование или технология)?
11. Нарисуйте «дерево» к следующей схеме, которое бы показывало все возможные пути,
ведущие от вершины 1 к вершине 9 (двигаться можно только в направлении стрелок). Сколькими способами можно из пункта 1 попасть в пункт 9? Какой путь самый короткий? Какой самый длинный? Какова их длина?>
