Лекция 1 (1)

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

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

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

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

Виды графов

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

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

Порожденные подграфы
Заданный граф
Порожденные подграфы
Это графы получаемые из заданного графа в результате удаления 1 или нескольких вершин и всех инцидентных к ней/ним рёбер

G – граф исходный
H1, H2, H3 - три его подграфа
Назовите типы приведенных подграфов.

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

Регулярные графы
Каждый пустой граф является регулярным степени 0, а каждый полный граф Kn – регулярным степени (n-1).

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