Сколько рёбер в этом графе (см)?
У графа пять вершин имеют степень 5, шесть вершин — степень 6, семь вершин — степень 7. Сколько рёбер в этом графе?
Для начала отметим, что степень вершины графа (узла) это число ребер, которые соединяют эту вершину с другими вершинами. Понятно, что если у обычного графа две вершины, то степень каждой вершины 1, ребро только одно, если три вершины, то степень каждой равен 2, а ребер 2. И так далее, получается, что число ребер равно половине суммы всех степеней графа (так как при подсчете каждое ребро учитывается дважды). Сумма степеней данного графа равна 5*5 + 6*6 + 7*7 = 25+36+49=110. Значит ребер 55 (110/2). Ответ: 55.
графы — В графе каждая вершина имеет степень 3
В графе каждая вершина имеет степень 3. Всегда ли можно выбрать в нем несколько ребер так, чтобы в каждую его вершину входило ровно одно выбранное ребро?
задан 29 Окт ’18 16:39
1 ответ
Эту задачу иногда формулируют так: есть компания из 2n человек (легко видеть, что число вершин здесь должно быть чётным), где каждый имеет ровно трёх знакомых. Всегда ли можно разбить участников компании на пары знакомых?
Для многих графов (типа тетраэдра, куба, додекаэдра) ответ положительный. Один из «старейших» результатов в теории графов — теорема Петерсена, полученная ещё в XIX веке. Она даёт достаточное условие возможности такого разбиения.
Но в общем случае ответ отрицательный. Минимальный пример имеет 16 вершин. Строится он так: одна вершина графа находится в центре; пусть это O. Она соединена тремя отрезками с A1, A2, A3. Конструкция переходит в себя при повороте на 120 градусов.
Для каждой из вершин A=Ai строим пятиугольник ABCDE (все буквы — с одинаковыми индексами), где все стороны — рёбра графа. Добавляем две диагонали BD и CE.
Теперь все вершины имеют степень 3. Разбиение на пары невозможно. Действительно, O соединена с какой-то одной вершиной — скажем, A1. Тогда ни с A2, ни с A3 она не соединена. В итоге возникает пятиугольник, который больше ни с чем не связан, и его вершины на пары не разбить по причине нечётности их числа.
"Степень вершины и подсчет числа ребер графа". 7-й класс
Назад Вперёд
Загрузить презентацию (487 кБ)
Профиль класса: общеобразовательный.
Тип урока: изучение и первичное закрепление новых знаний.
- ученик знает понятия графа и мультиграфа, знаком с понятиями “вершина графа” (смежные вершины) и “ребро графа” (кратные ребра и петли);
- умеет приводить примеры использования графов в различных учебных предметах и повседневной жизни.
- закрепить понятие графа, сформировать представление о степени вершины графа (четная, нечетная вершины), сформулировать определение о связности графа, рассмотреть утверждение о количестве ребер графа и теорему о четности числа нечетных вершин графа;
- отработать навыки использования теоретических знаний для решения новых задач.
- развивать логическое мышление учащихся, способность к рассуждению, внимательность;
- формировать умение представлять информацию в виде графов.
- воспитывать культуру общения на уроке, взаимоуважение.
- Организационный момент (приветствие класса, подготовка к уроку, проверка домашнего задания, включающая повторение материала предыдущего урока);
- Теоретический материал (знакомство с темой предстоящего урока, объяснение нового материала и краткая запись в рабочую тетрадь новых теоретических сведений по теме урока);
- Закрепление материала (решение задач);
- Итоги урока (краткий вывод и домашнее задание).
Давайте вспомним основные понятия теории графов. Для этого проведем разминку по типу незаконченного предложения (Презентация, сл.: 2, 3, 4). Каждый ученик имеет карточки с пропущенными словами в предложение. Учитель зачитывает предложение, останавливаясь перед пропущенным словом, и выбирает ученика, который в свою очередь должен поднять карточку. Далее этот ученик читает дальше предложение, также останавливаясь перед пропущенным словом, и уже сам выбирает одноклассника для ответа и т. д. по цепочке.
Проверим в классе решение домашней задачи (Презентация, сл.: 5, 6, 7). Один ученик выходит к доске и рисует граф. Далее мы вместе проверяем ребра (дороги между городами), считаем количество выходящих ребер из каждой вершины и смотрим связи между городами.
Сегодня на уроке мы продолжим изучение графов, познакомимся с понятием “степень вершины графа” и сформулируем определение связности графа (обратим внимание на наш граф из домашнего задания и определим, является ли он связным или нет и почему). Рассмотрим утверждение о количестве ребер графа, и проверим в соответствие с этим утверждением, правильно ли мы посчитали количество ребер графа в домашней задаче. И рассмотрим теорему о четности числа нечетных вершин графа.
Количество ребер, выходящих из одной вершины, называют степенью этой вершины. Для петли будем считать, что это ребро выходит из вершины дважды (Презентация, сл. 8).
Запишем определение в рабочую тетрадь и зарисуем представленный граф, для данного графа посчитаем степень каждой вершины. Ребята смотрят на слайд и работают самостоятельно, далее вслух зачитаем степень каждой вершины.
Вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень, называется нечетной вершиной (Презентация, сл. 9).
Запишем определение в тетрадь и перечислим через запятую сначала четные вершины, а потом нечетные вершины для уже нарисованного графа. Проверим задание вслух.
Количество ребер графа равно половине суммы степеней его вершин. Пусть граф имеет n вершин, тогда число ребер равно:
(Презентация, сл. 10)
Запишем утверждение в рабочую тетрадь и посчитаем количество ребер графа в домашней задачке. Проверим ответ в классе. Рассмотрим задачу и ее решение на подсчет числа ребер графа без построения. (Презентация, сл. 11).
Сформулируем теорему о количестве вершин нечетной степени любого графа и запишем формулировку в рабочую тетрадь. (Презентация, сл. 12).
Теорема. Количество вершин нечетной степени любого графа всегда четно.
Доказательство: Количество ребер графа равно половине суммы степеней его вершин.
Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной.
А это возможно только в том случае, если граф содержит четное число нечетных вершин.
Разберем доказательство и проверим теорему на нашей домашней задачке.
Рассмотрим несколько задач.
Задача. В государстве 50 городов, из каждого города выходит 4 дороги. Сколько всего дорог в государстве.
Решение. Подсчитаем общее количество выходящих дорог из городов: 50 * 4 = 200. Однако, мы понимаем, что при подсчете каждая дорога посчитана 2 раза – она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 100.
Задача. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей?
Ответ. Нет (теорема о четности числа нечетных вершин).
Сегодня мы с вами познакомились с новыми определениями, связанными с понятием графа, рассмотрели утверждение, которое помогает быстро подсчитывать число ребер графа, и сформулировали теорему, которая значительно упрощает решение многих задач. В частности, поучительная сторона этой теоремы заключается в исследовании и ответе на вопрос, возможно или нет решение данной задачи, прежде чем приступать за ее решение.
В качестве домашнего задания ученики получать карточки с тремя задачами (Презентация, сл. 13).