Сколько ребер и вершин в данном графе

«Степень вершины и подсчет числа ребер графа». 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).

Основные определения теории графов

В графе ребро, концы которого совпадают, то есть [math]e=(v, v)[/math] , называется петлей (англ. loop).

Два ребра, имеющие общую концевую вершину, то есть [math]e_1=(v, u_1)[/math] и [math]e_2=(v, u_2)[/math] , называются смежными (англ. adjacent).

Если имеется ребро [math] (v, u) \in E [/math] , то говорят:

[math] v [/math] — предок (англ. direct predecessor) [math] u [/math] .
[math] u [/math] и [math] v [/math] — смежные.
Вершина [math] u [/math] инцидентна ребру [math] (v, u) [/math] .
Вершина [math] v [/math] инцидентна ребру [math] (v, u) [/math] .

Инцидентность (англ. incidence) — понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с [math] p [/math] вершинами и [math] q [/math] рёбрами называют [math] (p, q) [/math] -графом. [math] (1, 0) [/math] -граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины [math]u,~v[/math] нельзя соединить более чем одним ребром [math](u, v)[/math] . Поэтому часто используют другое определение.

Определение:

Ориентированным графом [math]G[/math] называется четверка [math]G = (V, E, \operatorname, \operatorname)[/math] , где [math]V[/math] и [math]E[/math] — некоторые множества, а [math]\operatorname, \operatorname : E \rightarrow V[/math] .

Данное определение разрешает соединять вершины более чем одним ребром. Такие рёбра называются кратными (иначе — параллельные, англ. multi-edge, parallel edge). Граф с кратными рёбрами принято называть мультиграфом (англ. multigraph). Если в мультиграфе присутствуют петли, то такой граф называют псевдографом (англ. pseudograph).

Теория: 03 Свойство суммы степеней вершин, сравнение графов

Для графа, изображенного на рисунке, определите степени вершин. Найдите сумму степеней вершин.

Сколько рёбер в данном графе?

Во сколько раз сумма степеней вершин больше количества рёбер?

Вершина	Степень вершины
\(\displaystyle \bf A\)
\(\displaystyle \bf B\)
\(\displaystyle \bf C\)
\(\displaystyle \bf D\)
\(\displaystyle \bf E\)
Сумма степеней

Граф содержит рёбер.

Сумма степеней вершин больше количества рёбер в раз(а).

Требуется найти степени всех вершин графа, сумму степеней, количество рёбер и ответить на вопрос, во сколько раз сумма степеней вершин больше количества рёбер.

Определение

Степенью (порядком, валентностью) вершины графа называется количество рёбер, исходящих из этой вершины.

Шаг 1. Определим по рисунку степени вершин графа и найдём сумму степеней вершин.

Степень вершины \(\displaystyle A\) равна \(\displaystyle \color\)

Видим, что из вершины \(\displaystyle A\) исходят \(\displaystyle \color\) ребра.

Степень вершины \(\displaystyle B\) равна \(\displaystyle \color\)

Видим, что из вершины \(\displaystyle B\) исходят \(\displaystyle \color\) ребра.

Степень вершины \(\displaystyle C\) равна \(\displaystyle \color\)

Из вершины \(\displaystyle C\) исходит \(\displaystyle \color\) ребро.

Степень вершины \(\displaystyle D\) равна \(\displaystyle \color\)

Из вершины \(\displaystyle D\) исходят \(\displaystyle \color\) ребра.

Степень вершины \(\displaystyle E\) равна \(\displaystyle \color\)

Из вершины \(\displaystyle E\) исходят \(\displaystyle \color\) ребра.

Сумма степеней вершин:

Вершина	Степень вершины
\(\displaystyle \bf A\)	\(\displaystyle 2\)
\(\displaystyle \bf B\)	\(\displaystyle 2\)
\(\displaystyle \bf C\)	\(\displaystyle 1\)
\(\displaystyle \bf D\)	\(\displaystyle 3\)
\(\displaystyle \bf E\)	\(\displaystyle 2\)
Сумма степеней	\(\displaystyle \color\)

Шаг 2. Определим количество рёбер графа.

Граф содержит \(\displaystyle \color\) рёбер.

Можем просто перечислить эти рёбра: \(\displaystyle A-B\,A-D\,B-E\,D-E\) и \(\displaystyle C-D\)

Шаг 3. Вычислим, во сколько раз сумма степеней вершин больше количества рёбер.

Таким образом, сумма степеней вершин графа больше количества его рёбер в \(\displaystyle 2\) раза.

Замечание / комментарий

Заметим, что каждое ребро графа имеет начало и конец. Значит, при подсчёте степеней вершин каждое ребро подсчитано дважды: для вершины, являющейся началом ребра, и для вершины, являющейся его концом.

Таким образом, будет верна теорема

Теорема

Сумма степеней всех вершин графа равна удвоенному количеству рёбер.

Теория графов: Определение ранга графа, связь с количеством ребер и примеры

В данной статье мы рассмотрим основные понятия и свойства теории графов, включая определение ранга графа, ребра и связь между рангом и количеством ребер, а также приведем примеры и иллюстрации для лучшего понимания материала.

Теория графов: Определение ранга графа, связь с количеством ребер и примеры обновлено: 11 ноября, 2023 автором: Научные Статьи.Ру

Помощь в написании работы

Введение

Добро пожаловать на лекцию по Теории графов! В этой лекции мы будем изучать основные понятия и свойства графов. Графы являются важным инструментом в различных областях, таких как компьютерные науки, математика, социология и т.д. Мы начнем с определения ранга графа и ребра в графе, а затем рассмотрим связь между рангом графа и количеством ребер. В конце лекции мы рассмотрим примеры и иллюстрации, чтобы лучше понять эти понятия. Давайте начнем!

Нужна помощь в написании работы?

Мы — биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.

Определение ранга графа

Ранг графа – это количество вершин в наибольшей независимой множестве этого графа.

Независимое множество вершин – это такое множество вершин, в котором никакие две вершины не соединены ребром.

То есть, ранг графа показывает, сколько вершин можно выбрать из графа так, чтобы они не были связаны ребрами друг с другом.

Ранг графа обозначается символом “r”.

Например, если граф имеет ранг 3, это означает, что в нем можно выбрать 3 вершины, которые не будут связаны ребрами друг с другом.

Определение ребра в графе

Ребро в графе – это связь между двумя вершинами. Оно представляет собой линию или дугу, которая соединяет две вершины и указывает на наличие отношения или взаимодействия между ними.

Ребра в графе могут быть направленными или ненаправленными. В случае направленного ребра, оно имеет определенное направление, указывающее на то, какая вершина является начальной, а какая – конечной. В случае ненаправленного ребра, связь между вершинами является взаимной и не имеет определенного направления.

Ребра в графе могут быть также взвешенными или невзвешенными. В случае взвешенного ребра, каждому ребру присваивается числовое значение, называемое весом, которое может представлять, например, расстояние или стоимость связи между вершинами. В случае невзвешенного ребра, все ребра имеют одинаковый вес или вес не учитывается.

Ребра в графе могут быть представлены различными способами, например, линиями, стрелками, дугами или отрезками. Визуальное представление ребер зависит от спецификации графа и используемого графического представления.

Связь между рангом графа и количеством ребер

Ранг графа – это количество вершин, которые можно удалить из графа таким образом, чтобы он стал несвязным. Другими словами, ранг графа – это минимальное количество вершин, которые нужно удалить, чтобы разделить граф на две или более компоненты связности.

Количество ребер в графе также имеет важное значение. Количество ребер в графе определяет его плотность. Плотность графа – это отношение количества ребер к количеству возможных ребер в графе.

Существует связь между рангом графа и количеством ребер:

Если граф имеет ранг 0, это означает, что ни одну вершину нельзя удалить, чтобы разделить граф на две или более компоненты связности. В таком случае, граф должен быть полным, то есть каждая вершина должна быть связана с каждой другой вершиной. Количество ребер в полном графе с n вершинами равно n*(n-1)/2.
Если граф имеет ранг 1, это означает, что существует одна вершина, которую можно удалить, чтобы разделить граф на две или более компоненты связности. В таком случае, граф может быть представлен как две или более связанные компоненты, где каждая компонента может быть полным графом или иметь другую структуру. Количество ребер в таком графе может быть различным в зависимости от структуры компонент.
Если граф имеет ранг больше 1, это означает, что существует несколько вершин, которые можно удалить, чтобы разделить граф на две или более компоненты связности. В таком случае, граф может быть представлен как несколько связанных компонент, где каждая компонента может быть полным графом или иметь другую структуру. Количество ребер в таком графе также может быть различным в зависимости от структуры компонент.

Таким образом, ранг графа и количество ребер взаимосвязаны и определяют структуру и связность графа. Зная ранг графа и количество ребер, можно сделать выводы о его структуре и свойствах.

Примеры и иллюстрации

Давайте рассмотрим несколько примеров, чтобы лучше понять связь между рангом графа и количеством ребер.

Пример 1: Полный граф

Рассмотрим полный граф с 4 вершинами. В полном графе каждая вершина соединена с каждой другой вершиной ребром. В данном случае, у нас есть 4 вершины, и каждая вершина соединена с 3 другими вершинами. Таким образом, количество ребер в полном графе с 4 вершинами равно 6.

Полный граф

Пример 2: Дерево

Рассмотрим дерево с 5 вершинами. Дерево – это связный граф без циклов. В данном случае, у нас есть 5 вершин и 4 ребра. Количество ребер в дереве всегда на 1 меньше, чем количество вершин.

Дерево

Пример 3: Граф с несколькими компонентами

Рассмотрим граф с 2 компонентами: полным графом с 3 вершинами и простым циклом из 4 вершин. В данном случае, у нас есть 7 вершин и 9 ребер. Количество ребер в графе с несколькими компонентами может быть больше, чем количество вершин.

Граф с несколькими компонентами

Это лишь несколько примеров, которые помогут вам лучше понять связь между рангом графа и количеством ребер. Важно помнить, что ранг графа и количество ребер определяют структуру и связность графа, и их взаимосвязь может быть различной в зависимости от конкретного графа.

Таблица свойств графов

Свойство	Определение	Пример
Ранг графа	Максимальное количество независимых ребер в графе	Ранг графа G = 2
Ребро	Связь между двумя вершинами графа	Ребро (A, B)
Связь между рангом и количеством ребер	Ранг графа равен половине количества ребер	Ранг графа G = 2, количество ребер E = 4
Примеры и иллюстрации	Графы могут быть представлены в виде диаграмм или матриц смежности	Иллюстрация графа с вершинами A, B, C и ребрами (A, B), (B, C)

Заключение

Теория графов – это важная область математики, которая изучает свойства и отношения между объектами, представленными в виде графов. В этой лекции мы рассмотрели определение ранга графа и связь между рангом и количеством ребер. Надеюсь, что эта информация поможет вам лучше понять и применять теорию графов в своих исследованиях и задачах.