Докажите что в любом графе число вершин нечетной степени четно

ОСНОВНЫЕ ТЕОРЕМЫ ТЕОРИИ ГРАФОВ

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

Теорема 3.1. Удвоенная сумма степеней вершин любого графа равна числу его ребер. Или: сумма степеней вершин любого графа равна УДВОЕННОМУ числу его ребер.

Доказательство. Пусть А₁, А₂, А₃, . A_n — вер­шины данного графа, a p(A₁), р(А₂), . p(A_n) – степени этих вершин. Подсчитаем число ребер, сходящихся в каждой вершине, и просуммируем эти числа. Это рав­носильно нахождению суммы степеней всех вершин. При таком подсчете каждое ребро будет учтено дважды (оно ведь всегда соединяет две вершины).

Теорема 3.2.Число нечетных вершин любого графа четно.

Доказательство. Пусть a₁, a₂, a₃, …, a_k— это сте­пени четных вершин графа, а b₁, b₂, b₃, …, b_m — степени нечетных вершин графа. Сумма a₁+a₂+a₃+…+a_k+b₁+b₂+b₃+…+b_mровно в два раза превышает число ребер гра­фа. Сумма a₁+a₂+a₃+…+a_kчетная (как сумма четных чисел), тогда сумма b₁+b₂+b₃+…+b_m должна быть четной. Это возможно лишь в том случае, если m — четное, то есть четным является и число нечетных вершин графа. чтд.

Эта теорема имеет немало любопытных следствий.

Следствие 1.Нечетное число знакомых в любой компании всег­да четно.

Следствие 2.Число вершин многогранника, в которых сходится нечетное число ребер, четно.

Следствие 3. Число всех людей, когда-либо пожавших руку дру­гим людям, нечетное число раз, является четным.

Теорема 3.3.Во всяком графе с nвершинами, где nбольше или равно 2, всегда найдутся две или более вершины с оди­наковыми степенями.

Доказательство. Если граф имеет nвершин, то каждая из них может иметь степень 0, 1, 2, . (n—1). Предположим, что в некотором графе все его вершины имеют различную степень, то есть, и покажем, что этого быть не может. Действительно, если р(А)=0, то это значит, что А — изолированная вершина, и поэтому в графе не найдется вершины Х со степенью р(Х)=n-1. В са­мом деле, эта вершина должна быть соединена с (n-1) вершиной, в том числе и с А, но ведь А оказалась изолированной. Следовательно, в графе, имеющем n вершин, не мо­гут быть одновременно вершины степени 0 и (n-1). Это значит, что из nвершин найдутся две, имеющие одинаковые степени. чтд.

Теорема 3.4.Если в графе с nвершинами (nбольше или равно 2) только одна пара имеет одинаковую степень, то в этом графе всегда найдется либо единственная изолированная вершина, либо единственная вершина, соединенная со всеми другими.

Доказательство данной теоремы мы опускаем. Остановимся лишь на некотором ее пояснении. Содержание этой теоремы хорошо разъясняется задачей: группа, состоящая из nшкольников, обменивается фотографиями. В некоторый момент времени выяс­няется, что двое совершили одинаковое число обме­нов. Доказать, что среди школьников есть либо один еще не начинавший обмена, либо один уже завершив­ший его.

Теорема 3.5.Если у графа все простые циклы четной длины, то он не содержит ни одного цикла четной длины.

Теорема 3.6.Для того, чтобы граф был эйлеро­вым, необходимо и достаточно, чтобы он был связным и все его вершины имели четную степень.

Теорема 3.7.Для того чтобы на связном графе можно было бы проложить цепь АВ, содержащую все его ребра в точности по одному разу, необходимо и достаточно, чтобы А и В были единственными нечет­ными вершинами этого графа.

Доказательство этой теоремы очень интересно и ха­рактерно для теории графов. Его также следует счи­тать конструктивным (обратите внимание на то, как •использована при этом теорема 3.6). Для доказательства к исходному графу присоеди­няем ребро (А, В); после этого все вершины графа станут четными. Этот новый граф удовлетворяет всем условиям теоремы 3.6, и поэтому в нем можно про­ложить эйлеров цикл Ψ. И если теперь в этом цикле удалить ребро (А, В), то останется искомая цепь АВ.чтд.

На этом любопытном приеме основано доказатель­ство следующей теоремы, которую следует считать обоб­щением теоремы 3.7.

Теорема 3.8. Если данный граф является связ­ным и имеет 2k вершин нечетной степени, то в нем можно провести k различных цепей, содержащих все его ребра в совокупности ровно по одному разу.

Теорема 3.9.Различных деревьев с n перенумерованными вершинами можно построить n n -2 .

По поводу доказательства этой теоремы сделаем одно замечание. Эта теорема известна, в основном, как вывод английского математика А. Кэли (1821—1895). Графы-деревья издавна привлекали внимание ученых. Се­годня двоичные деревья используются не только ма­тематиками, а и биологами, химиками, физиками и инженерами (подробнее об этом – в параграфе 6).

Теорема 3.10.Полный граф с пятью верши­нами не является плоским.

Доказательство. Воспользуемся формулой Эйлера: В-Р+Г=2, где В — число вершин плоского графа, Р — число его ре­бер, Г — число граней. Формула Эйлера справедлива для плоских связных графов, в которых ни один из многоугольников не лежит внутри другого. На рисунке 3.2, а изображен граф, к которому формула не применима — заштрихованный много­угольник находится внутри другого. Справа приведено изображение графа, к которому формула применима.

Эту формулу можно доказать методом математиче­ской индукции. Это доказательство мы опускаем. За­метим только, что формула справедлива и для пространственных многогранников. Пусть все пять вершин графа соединены друг с дру­гом (рис. 3.2). Замечаем, что на графе нет ни одной грани, ограниченной только двумя ребрами. Если че­рез φ₁обозначить число таких граней, то φ₂=0. Далее рассуждаем от противного, а именно: пред­положим, что исследуемый граф плоский. Это значит, что для него верна формула Эйлера. Число вершин в данном графе В=5, число ребер Р=10, тогда число граней Г=2-В+Р=2-5+10=7.

Это число можно представить в виде суммы: Г=φ₁+φ₂+φ₃+…, где φ₃ – число граней, ограниченных тремя ребрами, φ₄ — число граней, ограниченных че­тырьмя ребрами и т. д.

Ясно, что (3φ₃+3φ₄+3φ₅+…) < (3φ₃+4φ₄+ 5φ₅+…)или 3Г<2Р, но по условию, 2Р=20, а ЗГ=21; поэтому вывод, полученный при введенном нами предположе­нии (граф плоский), противоречит условию. Отсюда заключаем, что полный граф с пятью вершинами не является плоским. чтд.

Теорема 3.11. (Теорема Понтрягина-Куратовского)Граф является плоским тогда и только тогда, когда он не имеет в качестве подграфа полного графа с пятью вершинами.

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

Кратчайший путь в графе

Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

Курс повышения квалификации

Основы разработки онлайн-курса

• Сейчас обучается 62 человека из 24 регионов

Курс профессиональной переподготовки

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

• Сейчас обучается 77 человек из 32 регионов

Курс повышения квалификации

Особенности подготовки к сдаче ОГЭ по математике в условиях реализации ФГОС ООО

• Сейчас обучается 181 человек из 54 регионов

«Обзор традиционных и современных методик для формирования навыков арифметических вычислений в уме у младших школьников»

Рабочие листы и материалы для учителей и воспитателей

Более 2 500 дидактических материалов для школьного и домашнего обучения

Описание презентации по отдельным слайдам:

Предположим, что через определенный промежуток времени каждая бактерия либо делится на две новые, либо погибает. В скольких случаях n-ое поколение одной бактерии насчитывает ровно k потомков?

Закодировать 20 сообщений в виде последовательности длинной 12, состоящей из нулей и единиц;

Печатной схемой называют пластинку из какого-либо диэлектрика, на которой в виде металлических полосок вытравлены дорожки. Пересекаться дорожки могут только в определенных точках, куда устанавливаются необходимые элементы, их пересечение в других местах вызовет замыкание электрической цепи. Сконструируете печатную схему

Составить структурную формулу метана СН4;

Какой метод объединяет данные задачи?

Теория графов
Багаева Наталия Витальевна
15.11.2013

Приложении теории графов в различных отраслях наук
Графы и информация
Графы и химия

Графы и биология
(Кэли)
«Транспортные» задачи
Логические задачи
Обменные схемы
Графы и физика
(Кирхгоф)
Логистика

изучить теоретический материал по теме «Теория графов» и возможность его применения
Задачи:

рассмотреть основные определения;
сформулировать и доказать основные теоремы, в т.ч. лемму «о рукопожатиях» ,
теоремы Кёнига, Оре, Холла

План лекции
Введение в теорию графов
1) основные определения;
2) виды графов;
II. Основные леммы и теоремы;
III. Применение «Теории графов» к решению задач

Определение
Графом называется геометрическая фигура состоящая из точек и соединяющих их линий. Точки называются вершинами. Стороны — ребрами

два ребра называются смежными, если они имеют общую вершину;
ребра называется петлей если его концы совпадают;
два ребра называют кратными если они соединяют одну и ту же пару вершин;
Определения
A
B
C
D
E
m
p
s
t
r
q
Пример:
Смежные ребра: DС и CA, CD и DB, DB и BA, BA и AC
Изолированная вершина: E
Кратные ребра: m и p
Петля: q
вершина называется изолированной, если она не является концом ни для одного ребра

степенью вершины A называют количество ребер, для которых она является концевой (петли считать дважды)
Обозначение: deg(A).
G
H
E
C
D
F
A
B
A
B
C
D
E
u
p
s
t
r
q
deg(E) = 0
deg(C) = 2
E – изолированная вершина
deg(G) = 1
deg(H) = 1
deg(E) = 1
deg(B) = 1
deg(A) = 1
deg(C) = 4
deg (D) = 2
G, H, E, B, A — висячие вершины
Определения
Пример:

Лемма о рукопожатиях
В любом графе сумма степеней всех вершин равна удвоенному числу ребер
Доказательство:
Если ребро соединяет две различные вершины графа, то при подсчете суммы степеней всех вершин мы учтем это ребро дважды;
Если ребро является петлей, то при подсчете суммы степеней всех вершин мы также учтем это ребро дважды;
В любом графе число вершин нечетной степени четно
Следствие
степенью вершины называют количество ребер, для которых она является концевой (петли считать дважды)
|=>
(по определению степени вершины)
ч.т.д

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

Пример:
Может ли в государстве, в котором из каждого города выходит 3 дороги быть ровно 100 дорог

Ответ: не может
Решение:
Города – вершины графа (k, kєN ). Степень кратности каждой вершины 3 =>

Дороги – ребра графа (p = 100)
По Лемме 3k = 2p. Если р = 100, то k =
Но kєN => p ≠ 100

Виды графов
Граф, состоящий из «изолированных» вершин, называется нулевым графом
Граф называется полным, если любые две его различные вершины соединены одним и только одним ребром.
Граф, в которых не построены все возможные ребра, называют неполным графом.
M
A
D
B
C
A
B
C
D
E
L
U
B
O
V

граф без кратных ребер и петель называется обыкновенным
если степени всех вершин графа равны, то граф называется однородным.
2
2
2
2
3
3
3
3
А
B
C
D
E
K
O
P
deg(A) = deg(B) = deg(C) = deg(D) = 2
deg(O) = deg(P) = deg(E) =deg(K) = 3
A
B
C
D
E
G
Виды графов

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

A
B
C
u
t
s
r
дуги
Начало дуги (A,B)
конец дуги(A,B)
Степенью входа (выхода) вершины орграфа называется число ребер, для которых эта вершина является концом (началом)
Степень входа вершин графа:
Орграф
Степень выхода вершин графа:

Связный граф
Если в графе две любые вершины соединены путем, то такой граф называется связным
M
S
D
O
C
A
B
C
D
связный граф
не связный граф

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

Определения
Максимальный связный подграф графа называется компонентной связности
Пример:
граф с 10 компонентами

Докажите, что граф с n вершинам, степень каждого из
которых не менее , связен.
Рассмотрим вершины A и B, не соединенные путем.
Вершина А соединена не менее чем с вершинами,
Вершина B также соединена не менее чем с (по условию)
Вершина А отлична от В ( иначе между ними существует путь)
Тогда в графе 1+1+ + вершин, то есть n+1.
Но по условию всего n вершин. Мы пришли к противоречию |=>
вершины соединены путем => граф связен. ч.т.д.

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

Определения
Паросочетание называется Совершенным, если оно покрывает все вершины графа, т. е. если каждая вершина графа G инцидентна некоторому ребру данного паросочетания.

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

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

Пример:
1) (А1 А4); (А4 А5)
2) (А1 А2); (А2 А4); (А4 А5).
3) (А1 А4); (А4 А2); (А2 А1); (А1 А3); (А3 А4); (А4, А5).
4) (А1 А4); (А4 А2); (А2 А1); (А1 А3); (А3 А5);

Циклом называется путь, в котором совпадают его начальная и конечная вершины.
Простым циклом в графе называется цикл, не проходящий ни через одну из вершин графа более одного раза.
Определения
Пример:

A
B
C
D
E
Циклы состоящие из 4 ребер:
(AB, BC, CE, EA), (CD, DA, AB, BC)
(DA,AB,BE, EC, CA, AE, ED)

Простые циклы: (EB, BC, CD, DE) и т.д.

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

Теорема Кенига
Граф является двудольным тогда и только тогда, когда он содержит более одной вершины и все его циклы имеют четную длину

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

Задача о деревенских свадьбах
Назначение на должность: имеются вакантные должности и претенденты на них, о каждом претенденте известно какие должности он может занять, требуется заполнить максимум вакансий
Выбор представителей: в парламенте есть несколько комиссий, член парламенты может заседать в нескольких комиссиях; нужно выбрать председателя каждой комиссии
Пример:

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

Теорема Холла о свадьбах
Доказательство:
Необходимость: Совершенное паросочетание Р в графе G можно рассмотреть как функцию, отображающую каждую вершину из Х в смежную ей вершину Y. По определению совершенного паросочетания эта функция является биекций, откуда |X|=|Y|. Более того, P отображает каждое подмножество M X в некоторое подмножество YM содержащие |M| элементов, являющихся смежными к вершинам из М вершин. Но тогда YM O(M) и |М|=| YM | |O(M)|
ч.т.д
X1
X2
X3
X4
X5
X6
Y5
Y4
Y3
Y2
Y1
Дан двудольный граф с долями X и Y. Совершенное паросочетание существует тогда и только тогда когда |Х| = |Y| и |O(M)| ≥ |M| для всякого M X

Достаточность
Пусть G – двудольный граф, для которого |X| = |Y| = n и выполнено условие (1). Докажем что в G существует паросочетание P, содержащие n ребер.
Проведем индукцией по n. В случае n = 1 (база). Единственная вершина из Х и единственная вершина из Y должны быть соединены ребром, чтобы условие (1) выполнялось. Но тогда можно взять Р = G.
Перейдем к шагу индукции: предположим, что для двудольных графов с меньшим чем n числом вершин в каждой доле утверждения теоремы верно. Возможно два случая

Эйлеровы графы
Граф является эйлеровым тогда и только тогда, когда он связный граф, имеющий все четные вершины

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

Определения
Эйлеровым циклом или эйлеровой цепью называется цикл, содержащий все ребра графа и притом по одному разу.
Если граф G(V,E) обладает эйлеровым циклом, то он связный и все его вершины четные.
Теорема №1
Теорема №2 (Эйлер)
Граф без изолированных вершин является эейлоровым, тогда и только тогда, когда он связен и степени всех вершин его четны

Гамильтоновы графы
Гамильтонов путем (циклом) графа называется путь ( цикл) проходящий через каждую вершину только один раз
Граф, содержащий гамильтонов цикл, называется гамильтоновым
Пример:
гамильтонов путь:
(C, D, A, B, M);
(B, A, D, C, F)
A
B
C
D
M
F

Предположим что существует граф G, который удовлетворяет условию теоремы, но не является гамильтоновым графом. Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов граф G1
Пусть u, v несмежные вершины в полученном графе G1. Если добавить ребро uv, появится гамильтонов цикл. Тогда путь (u, v) – гамильтонов.
Для вершин u,v выполняется неравенство:
deg u + deg v ≥ n
По принципу Дирихле всегда найдутся две смежные вершины t1 и t2 на пути (u, v) т.е. u…t1t2..v, такие что существует ребро ut2 и ребро ut1
|S|+|T| = deg u + deg v ≥ n, но |S|+|T| < n, тогда |S T| = |S|+|T|
Теорема (Оре)
Доказательство:
Пусть дан обыкновенный связный граф, содержащий n > 2 вершин, такой что сумма степеней любых двух несмежных вершин не меньше, чем n. Тогда граф гамильтонов.

Планарные (плоские) графы
Граф G(V, E) называется планарным, если на плоскости его можно изобразить так, чтобы все пересечения его ребер являются вершинами графа G(V, E)
первоначальный
граф
изображенный иначе
Грань в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов.
Пример: (BAC), (CAE), (CDE)
A
B
C
D
E

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

Каждый из 102 учеников одной школы знаком не менее, чем с 68 другими. Докажите, что среди них найдутся четверо, имеющие одинаковое число знакомых
1) пусть верно обратное.
2) тогда для каждого числа от 68 до 101 имеется не более трех человек, имеющих такое же число знакомых.
3) имеется ровно 34 натуральных числа, начиная с 68 и заканчивая 101, а 102 = 3 ∙ 4. Это означает что для каждого числа от 68 до 101 есть ровно три человека, имеющие такое число знакомых
4) Но тогда количество людей, имеющих нечетное количество знакомых нечетно. (Л) | => верно обратное, т.е. среди учеников найдутся четверо, имеющие одинаковое число знакомых
Решение:
Пример:

Город Кенигсберг ( ныне Калининград) расположен на берегах реки Прегель и двух островах на этой реке. Части города соединены мостами. Спрашивается, можно ли, выйдя из какой либо точки города, пройти по каждому мосту ровно один раз и вернутся в исходную точку
Задача о кёнигсберских мостах

Решение:
Объекты – части города
Связи — мосты
Можно ли обойти данный граф пройдя по каждому ребру ровно один раз и вернуться и вернувшись в исходную вершину, то есть существует ли последовательность ребер графа со следующими свойствами:

любые два соседних ребра имеют общую вершину;
последнее ребро имеет общую вершину с первым;
каждое ребро графа встречается в последовательности ровно один раз

Дополнением графа G1 (V1,E1) называется граф множеством вершин которого является множество V1, а множеством его ребер является множество

Операции над графами
G2
G1
G3
Дополнение графа G1 графом G3, до графа G2
Объединением графов при условии, что
называется граф множеством вершин которого является множество а множеством его ребер является множество

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

Аналитический способ задания графов
Граф G(V,E) задан, если задано множество элементов V и отображение Е множества V в V. Отображение Е может быть как однозначным, так и многозначным. В общем случае на V и E никаких ограничений не накладывается.
Пусть дано множество < >, которое имеет мощность . Вместо
< >иногда пишут < >, < >.
Для того чтобы задать отображение Е на V или, что то же самое, отображение V в V, необходимо каждому элементу поставить в соответствие Е. Это подмножество обозначают через поэтому
Другой формой аналитического способа задания является задание графа как совокупности множества элементов V и подмножества упорядоченных пар
Подмножество множества пар декартова произведения эквивалентно бинарному отношению R, заданному на множестве V. Поэтому множество V и бинарное отношение R на множестве V также определяет некоторый граф G.

Способы задания графов

Геометрический способ
Множество элементов V графа G изображают кружками, это множество вершин. Каждую вершину соединяют линиями с теми вершинами , для которых выполняется условие . Множество линий, которое соответствует множеству упорядоченных пар , есть множество ребер графа.
Матричный способ
Квадратная матрица элементами которой являются нули и единицы, а также некоторое число m, называется матрицей смежности графа G(V,E) тогда и только тогда когда ее элементы образуются по следующему правилу: элемент стоящий на пересечении столбца, равен единице, если имеется ребро, идущие из вершины в вершину , и равен нулю в противном случае. Элемент равен единице, если при вершине имеется петля, и равен нулю в противном случае. Элемент равен некоторому числу m, где m – число ребер графа, идущее из вершины в вершину .
Пусть — вершины, а — ребра некоторого ориентированного графа G(V,E). Матрица размером (m x n), где называется матрицей инцидентности для ориентированного графа.

Краткое описание документа:

Граф, или неориентированный граф — это упорядоченная пара , где — это непустоемножество вершин или узлов, а — множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

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

Вершины и рёбра графа называются также элементами графа, число вершин в графе — порядком, число рёбер —размером графа.

Вершины и называются концевыми вершинами (или просто концами) ребра . Ребро, в свою очередь,соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть .

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

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

• подготовка к ЕГЭ/ОГЭ и ВПР
• по всем предметам 1-11 классов

Рабочие листы и материалы для учителей и воспитателей

Более 2 500 дидактических материалов для школьного и домашнего обучения