№1 · Теория графов
1. Вершины и рёбра графа
Заполните пропуски в определении.
Граф состоит из множества и множества , соединяющих некоторые пары вершин.
Ф.И.
Класс
Разберём, как задают графы и как находить степени вершин, пути, цепи и циклы. Начнём с теории, а затем решим несколько задач.
№1 · Теория графов
Заполните пропуски в определении.
Граф состоит из множества и множества , соединяющих некоторые пары вершин.
№2 · Способы задания
Заполните пропуск.
Перечисление пар вершин, соединённых рёбрами, называют заданием графа списком .
№3 · Степень вершины
Заполните пропуск в определении.
Степенью вершины называют количество , выходящих из этой вершины.
№4 · Степени вершин
Для неориентированного графа рёбра заданы списком: AB, AC, BD, CD, DE. Найдите степени вершин A и D.
Степень вершины A равна , а степень вершины D равна .
№5 · Путь
Рассмотрите граф с рёбрами AB, BC, CD, DE и AF. Заполните пропуски для пути A–B–C–D–E.
Путь A–B–C–D–E содержит ребра и имеет длину .
№6 · Цепь и путь
Заполните пропуски, используя граф с рёбрами AB, BC, CD, DA и AC.
Последовательность A–B–C–A является , потому что повторяет вершину A, но не является .
+6 заданий в этом листе
Зарегистрируйтесь — и соберите свой рабочий лист по этой теме за минуту: заданий столько, сколько нужно.
№7 · Цикл
В графе заданы рёбра AB, BC, CD, DA, DE. Укажите цикл и его длину.
Цикл имеет вид , а его длина равна .
№8 · Степени и связность
В неориентированном графе вершины A, B, C, D, E соединены рёбрами AB, AC, BD, CD, CE и DE. Найдите степени вершин B, C и E.
Степень вершины B равна , вершины C — , вершины E — .
№9 · Поиск цикла
Рассмотрите граф с рёбрами AB, BC, CD, DE, EA, AC и CE. Укажите один цикл длины 3, один цикл длины 5 и число рёбер, входящих в оба названных цикла.
Цикл длины 3: . Цикл длины 5: . Число общих рёбер этих циклов равно .
№10 · Анализ графа
В графе рёбра заданы так: AB, BC, CD, DA, AE, EF, FB, CG, GH, HC. Заполните пропуски, анализируя структуру графа.
Цикл A–B–C–D–A имеет длину . Цикл A–E–F–B–A имеет длину . Степень вершины C равна , а степень вершины A равна .
№11 · Кратчайший путь
В неориентированном графе рёбра имеют вид: AB, AC, BD, CD, CE, DE, EF, DF, FG. Найдите длину кратчайшего пути из вершины A в вершину G и запишите один из таких путей. Каждое ребро имеет длину 1.
Создайте уникальный лист по своей теме
Зарегистрируйтесь бесплатно — лист сохранится в личном кабинете, откуда его можно скачать в PDF и распечатать.
В листе 11 заданий: заполни пропуски, реши задачу.
Да, задания ориентированы на школьную программу по вероятности и статистике для 10 класса по ФГОС.
Да. После регистрации лист открывается в конструкторе: задания можно заменить, перегенерировать или добавить новые.