Лекция 1. Теория графов. Введение. Основные понятия и определения

Июль 29, 2022

Главная
Математика
Лекция 1. Теория графов. Введение. Основные понятия и определения

Содержание

2. Задача о Кенигсбергских мостах
3. Задача о 4-х красках Удивительный факт: любую политическую карту можно раскрасить всего четырьмя красками, причем так,
4. Некоторые используемые обозначения
5. Основные понятия и определения Графом G называется пара объектов G=(V,E) V – конечное множество элементов, называемых
6. Виды графов
7. Подграфы Заданный граф Подграфы
8. Остовный подграф (фактор, часть графа) Заданный граф Остовные подграфы Кол-во остовных подграфов
9. Порожденные подграфы Заданный граф Порожденные подграфы Это графы получаемые из заданного графа в результате удаления 1
10. Операция удаления вершины графа G - 5
11. Графы специального вида Полные графы Пустой граф с 4 вершинами
12. Регулярные графы Каждый пустой граф является регулярным степени 0, а каждый полный граф Kn – регулярным
13. Двудольные графы
15. Скачать презентацию

Слайд 2

Задача о Кенигсбергских мостах

Слайд 3

Задача о 4-х красках
Удивительный факт: любую политическую карту можно раскрасить всего

четырьмя красками, причем так, что соседние страны на ней не будут окрашены в один цвет.
Пронумеруем краски: 1 — красная, 2 — зеленая, 3 — синяя и 4 — желтая.

Слайд 4

Некоторые используемые обозначения

Слайд 5

Основные понятия и определения
Графом G называется пара объектов
G=(V,E)
V

– конечное множество элементов, называемых вершинами, V(G)={u,v,w,z}
E – конечное множество элементов, называемых рёбрами E(G) = {(u,v), (v,w), (u,w), (w,z)}

Слайд 6

Виды графов

Слайд 7

Подграфы
Заданный граф
Подграфы

Слайд 8

Остовный подграф (фактор, часть графа)
Заданный граф
Остовные подграфы
Кол-во остовных подграфов

Слайд 9

Порожденные подграфы
Заданный граф
Порожденные подграфы
Это графы получаемые из заданного графа

в результате удаления 1 или нескольких вершин и всех инцидентных к ней/ним рёбер

Слайд 10

Операция удаления вершины графа
G - 5

Слайд 11

Графы специального вида
Полные графы
Пустой граф с 4 вершинами

Слайд 12

Регулярные графы
Каждый пустой граф является регулярным степени 0, а каждый полный

граф Kn – регулярным степени (n-1).

Слайд 13

Двудольные графы