№1 · Категории
1. Классификация элементов графа
Распределите термины теории графов по двум категориям: характеристики, относящиеся к отдельным вершинам, и характеристики, описывающие граф целиком.
Ф.И.
Класс
Графы позволяют наглядно описывать связи между объектами. Сегодня мы изучим их свойства, научимся строить модели задач и проверять графы на связность.
№1 · Категории
Распределите термины теории графов по двум категориям: характеристики, относящиеся к отдельным вершинам, и характеристики, описывающие граф целиком.
№2 · Задача
В группе из 10 десятиклассников каждый обменялся рукопожатием ровно с 3 другими. Возможно ли это? Если да, вычислите общее количество совершенных рукопожатий. Обоснуйте ответ с помощью леммы о рукопожатиях.
№3 · Кроссворд
Заполните сетку кроссворда, используя базовые определения темы.
По горизонтали
По вертикали
№4 · Краткий ответ
В полном графе каждая вершина соединена со всеми остальными вершинами ровно одним ребром. Известно, что степень каждой вершины в таком графе равна 7. Определите общее количество вершин в этом графе.
№5 · Примеры
Используя лемму о рукопожатиях, вычислите количество ребер в графе по заданному набору степеней его вершин.
№6 · Категории
Классифицируйте описанные графы на связные и несвязные.
№7 · Задача
На рисунке представлена схема дорожек в парке. Площадки обозначены буквами A, B, C, D, E. Можно ли совершить прогулку, пройдя по каждой дорожке ровно один раз? Ответ обоснуйте, проверив степени вершин.
Схема дорожек
№8 · Кроссворд
Решите кроссворд, посвященный более сложным понятиям теории графов.
По горизонтали
По вертикали
№9 · Краткий ответ
Граф состоит из 12 вершин и представляет собой объединение трех изолированных друг от друга циклов (в каждом цикле по 4 вершины). Сколько компонент связности имеет такой граф?
№10 · Примеры
Найдите сумму степеней всех вершин графа, если известно общее количество его ребер .
№1 · Термины
Выберите наиболее точное определение связного графа.
№2 · Подсчет
Рассмотрите модель полного графа . Сколько ребер в нем проведено?
Полный граф
№3 · Матрица
Заполните матрицу смежности для ориентированного графа, изображенного на рисунке. В ячейках ставьте 1, если ребро существует, и 0, если нет.
| От\К | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 |
№4 · Термины
Установите соответствие между термином теории графов и его описанием.
№5 · Связность
Является ли данный граф связным? Укажите количество компонент связности.
Исследуемый граф
№6 · Свойства
Отметьте, какие из утверждений о степенях вершин графа являются истинными.
№7 · Пропуски
Заполните пропуски в тексте о свойствах связных графов.
В теории графов — это последовательность вершин, в которой каждые две соседние соединены ребром. Если начальная и конечная вершины совпадают, такой путь называется . Если граф , то между любыми его вершинами можно построить маршрут.
№8 · Маршруты
Можно ли начертить фигуру, изображенную на рисунке, не отрывая карандаша от бумаги и не проводя по одной линии дважды? Обоснуйте ответ, используя степени вершин.
Схема фигуры
№9 · Исключение
Выберите описание графа, который НЕ может быть связным при заданных условиях.
№10 · Логика
В классе 15 учеников. Может ли быть так, что каждый из них обменялся рукопожатиями ровно с тремя другими учениками? Ответ подтвердите расчетом.
№1 · Теория
Выберите верное определение степени вершины в простом графе.
№2 · Матрицы
Дан граф с 4 вершинами и набором ребер . Заполните его матрицу смежности (1 — вершины соединены, 0 — нет).
| V1 | V2 | V3 | V4 | |
|---|---|---|---|---|
| V1 | ||||
| V2 | ||||
| V3 | ||||
| V4 |
№3 · Расчет
В графе 7 вершин, их степени равны: 3, 2, 2, 2, 1, 1, 1. Вычислите количество ребер в этом графе.
№4 · Свойства
Отметьте, верны ли данные утверждения о связных графах.
№5 · Построение
На клетчатом поле изобразите связный граф, имеющий 4 вершины со степенями 3, 1, 1, 1. Обозначьте вершины точками, а ребра — линиями.
Постройте: Поле для построения графа
№6 · Термины
Вставьте пропущенные слова в определения.
Граф называется , если между любой парой его вершин существует . Число ребер, выходящих из вершины, называется её .
+25 заданий в этом листе
Зарегистрируйтесь — и соберите свой рабочий лист по этой теме за минуту: заданий столько, сколько нужно.
№7 · Соответствие
Установите соответствие между термином и его описанием.
№8 · Логика
В классе 9 человек. Может ли быть так, что у каждого ровно 5 друзей в этом классе? Ответ обоснуйте с помощью теории графов.
№9 · Логика
Выберите набор чисел, который НЕ может быть последовательностью степеней вершин простого графа.
№10 · Полный граф
Найдите количество ребер в полном графе (в котором каждая из 6 вершин соединена с каждой другой). Запишите расчет.
№1 · Лефма о рукопожатиях
В графе 8 вершин, и степень каждой вершины равна 4. Вычислите количество ребер в этом графе.
№2 · Связность
Выберите утверждение, которое является определением связного графа.
№3 · Терминология
Заполните пропуски в определении графа.
Граф состоит из множества точек, называемых , и множества линий, соединяющих эти точки, которые называются .
№4 · Моделирование
В турнире участвуют 5 команд. Каждая команда должна сыграть с каждой по одному матчу. Сколько всего матчей будет сыграно в турнире? Решите задачу, представив её в виде полного графа.
Граф связей
№5 · Существование
Может ли существовать простой граф с 5 вершинами, степени которых равны 4, 4, 4, 4, 2?
№6 · Деревья
Заполните пропуски в утверждениях о свойствах деревьев.
Связный граф, не содержащий циклов, называется . Если в таком графе 12 вершин, то количество ребер в нем равно .
№7 · Анализ структуры
Рассмотрите граф, изображенный ниже. Вершины A, B, C, D образуют цикл, а вершина E соединена только с вершиной C.
1) Является ли граф связным?
2) Чему равна степень вершины C?
Схема графа
№8 · Теоретический тест
Выберите ложное утверждение о дереве с вершинами.
№9 · Экстремальные задачи
Заполните пропуски в формулах для произвольного простого графа с вершинами.
Максимально возможное число ребер в простом графе равно . Если граф имеет компонент связности, то минимально возможное число ребер в нем равно .
№10 · Доказательство
В шахматном турнире участвуют 15 человек. Может ли случиться так, что каждый из них к середине турнира сыграл ровно по 3 партии? Обоснуйте ответ.
№1 · Определения
Выберите верное определение связного графа.
№2 · Анализ графа
Рассмотрите изображение графа. Является ли он связным? Ответ обоснуйте, указав количество компонент связности.
Граф
№3 · Матрицы
Заполните матрицу смежности для неориентированного графа с вершинами , если известно, что в графе есть ребра: . Самопетли отсутствуют.
| A | B | C | D | |
|---|---|---|---|---|
| A | ||||
| B | ||||
| C | ||||
| D |
№4 · Вычисления
В графе 6 вершин, степени которых равны 3, 2, 2, 2, 1, 4. Вычислите общее количество ребер в этом графе.
№5 · Терминология
Заполните пропуски в определениях элементов графа.
Путь, проходящий через каждую вершину графа ровно один раз, называется путем. Связный граф, не содержащий циклов, называется .
№6 · Соответствие
Установите соответствие между названием типа графа и его определяющим свойством.
№7 · Задача
На рисунке изображена схема дорог между городами A, B, C, D, E. Числа над ребрами — длина дорог в км. Найдите длину кратчайшего пути из города A в город E.
Взвешенный граф
№8 · Логика
Определите истинность утверждений о свойствах связных графов.
№9 · Моделирование
Пять человек встретились и обменялись рукопожатиями. Известно, что каждый пожал руку ровно двоим. Изобразите это условие в виде графа (вершины — люди, ребра — рукопожатия). Может ли такой граф быть связным? Если да, приведите пример структуры.
Постройте: Заготовка для графа
№10 · Исключение
Выберите из списка описание графа, который ОБЯЗАТЕЛЬНО является несвязным.
Создайте уникальный лист по своей теме
Зарегистрируйтесь бесплатно — лист сохранится в личном кабинете, откуда его можно скачать в PDF и распечатать.
В листе 50 заданий: реши задачу, кроссворд, краткий ответ, реши примеры, множественный выбор, таблица, соединение, истина / Ложь, заполни пропуски, найти лишнее.
Да, задания ориентированы на школьную программу по вероятности и статистике для 10 класса по ФГОС.
Да. После регистрации лист открывается в конструкторе: задания можно заменить, перегенерировать или добавить новые.