Слайд 2Граф
Это совокупность двух множеств: вершин V и ребер E, между которыми определено
![Граф Это совокупность двух множеств: вершин V и ребер E, между которыми определено отношение инцидентности](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-1.jpg)
отношение инцидентности
Слайд 3Инцидентное ребро
Каждое ребро e из E ровно двум вершинам v', v'', которые
![Инцидентное ребро Каждое ребро e из E ровно двум вершинам v', v'', которые оно соединяет](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-2.jpg)
оно соединяет
Слайд 4Петля
Ребро называется петлей, если концевые вершины совпадают
![Петля Ребро называется петлей, если концевые вершины совпадают](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-3.jpg)
Слайд 5Ориентированное ребро
Ребро (v',v'') ориентированное, если имеет начало (v') и конец (v'')
![Ориентированное ребро Ребро (v',v'') ориентированное, если имеет начало (v') и конец (v'')](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-4.jpg)
Слайд 6Кратные ребра
Ребра, инцидентные одной паре вершин, называются параллельными или кратными
![Кратные ребра Ребра, инцидентные одной паре вершин, называются параллельными или кратными](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-5.jpg)
Слайд 7Неорграф
Граф, не содержащий ориентированные ребра, называется неографом.
![Неорграф Граф, не содержащий ориентированные ребра, называется неографом.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-6.jpg)
Слайд 8Орграф
Граф, содержащий ориентированные ребра , называется орграфом
![Орграф Граф, содержащий ориентированные ребра , называется орграфом](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-7.jpg)
Слайд 9Смежные вершины
Если ребро инцидентно,то вершина v' и ребро e называются инцидентными друг
![Смежные вершины Если ребро инцидентно,то вершина v' и ребро e называются инцидентными](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-8.jpg)
другу, а вершины v' и v'' называются смежными
Слайд 10Конечный граф
Граф конечный, если число вершин и ребер конечно
![Конечный граф Граф конечный, если число вершин и ребер конечно](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-9.jpg)
Слайд 11Пустой граф
Граф пустой, если множество ребер пусто
![Пустой граф Граф пустой, если множество ребер пусто](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-10.jpg)
Слайд 12Полный граф
Граф полный, если нет петель и кратных ребер, каждая пара вершин
![Полный граф Граф полный, если нет петель и кратных ребер, каждая пара вершин соединена ребром](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-11.jpg)
соединена ребром
Слайд 13Локальная степень вершины
Локальная степень вершины - число ребер ей инцидентных
![Локальная степень вершины Локальная степень вершины - число ребер ей инцидентных](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-12.jpg)
Слайд 14Лемма о рукопожатиях
В неографе сумма степеней всех вершин равна удвоенному числу ребер
![Лемма о рукопожатиях В неографе сумма степеней всех вершин равна удвоенному числу](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-13.jpg)
Петля дает вклад, равный 2 в степень вершины
Слайд 15Степени вершин в орграфе
В орграфе сумма входящих ребер всех вершин равна сумме
![Степени вершин в орграфе В орграфе сумма входящих ребер всех вершин равна](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-14.jpg)
исходящих ребер всех вершин и равна числу ребер графа
Слайд 16Равные графы
Графы равны, если множества вершин и инцидентных им ребер совпадают
![Равные графы Графы равны, если множества вершин и инцидентных им ребер совпадают](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-15.jpg)
Слайд 17Изоморфные графы
Графы, отличающиеся только нумерацией вершин и ребер
![Изоморфные графы Графы, отличающиеся только нумерацией вершин и ребер](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-16.jpg)
Слайд 18Способы задания графов
явное задание графа как алгебраической системы
геометрический
матрица смежности
матрица инцидентности
![Способы задания графов явное задание графа как алгебраической системы геометрический матрица смежности матрица инцидентности](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-17.jpg)
Слайд 19Матрица смежности
Матрица смежности - квадратная симметричная матрица
По горизонтали и вертикали - все
![Матрица смежности Матрица смежности - квадратная симметричная матрица По горизонтали и вертикали](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-18.jpg)
вершины
аij= число ребер, соединяющее вершины i,j
Слайд 20Матрица инцидентности
Матрица инцидентности-по вертикали указываются вершины, по горизонтали ребра
aij=1 если вершина
![Матрица инцидентности Матрица инцидентности-по вертикали указываются вершины, по горизонтали ребра aij=1 если](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-19.jpg)
i инцидентна ребру j, в противном случае aij=0
Если ребро - петля то aij=2
Слайд 21Маршрут
Маршрут - последовательность ребер, в которых каждые два соседних ребра имеют общую
![Маршрут Маршрут - последовательность ребер, в которых каждые два соседних ребра имеют общую вершину](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-20.jpg)
вершину
Слайд 22Цикл
Маршрут, в котором начало и конец совпадают,циклический
![Цикл Маршрут, в котором начало и конец совпадают,циклический](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-21.jpg)
Слайд 23Цепь
Маршрут в неографе, в котором все ребра разные - цепь
![Цепь Маршрут в неографе, в котором все ребра разные - цепь](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-22.jpg)
Слайд 24Путь
Маршрут в орграфе, в котором все дуги разные - путь
![Путь Маршрут в орграфе, в котором все дуги разные - путь](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-23.jpg)
Слайд 25Связные вершины
Вершины связанные, если существует маршрут из одной вершины в другую
![Связные вершины Вершины связанные, если существует маршрут из одной вершины в другую](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-24.jpg)
Слайд 26Пустой граф
Граф пустой, если множество ребер пусто
![Пустой граф Граф пустой, если множество ребер пусто](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-25.jpg)
Слайд 27Связанный граф
Связанный граф - если все его вершины связаны
![Связанный граф Связанный граф - если все его вершины связаны](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-26.jpg)
Слайд 28Плоский граф
Плоский граф - граф с вершинами, расположенными на плоскости и непересекающимися
![Плоский граф Плоский граф - граф с вершинами, расположенными на плоскости и непересекающимися ребрами](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-27.jpg)
ребрами
Слайд 29Изолированные вершины
Вершины графа, которые не принадлежат ни одному ребру, называются изолированными
![Изолированные вершины Вершины графа, которые не принадлежат ни одному ребру, называются изолированными](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-28.jpg)
Слайд 30Дерево
Связный граф без циклов, называется дерево
![Дерево Связный граф без циклов, называется дерево](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/914568/slide-29.jpg)