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

клик мыши!!!
Если есть мигающая стрелка, значит нужно нажатие левой

ПАРА ДВУХ КОНЕЧНЫХ МНОЖЕСТВ: МНОЖЕСТВО ТОЧЕК И МНОЖЕСТВО ЛИНИЙ, СОЕДИНЯЮЩИХ

Впервые понятие «граф» ввел в 1936 г. венгерский математик Денни Кёниг. но первая работа по теории графов принадлежала перу великого Леонарда Эйлера и была написана еще в 1736 г.

ГРАФОВ

ЭТО РЕБРО ИМ ИНЦИДЕНТНО. ДВЕ ВЕРШИНЫ ГРАФА НАЗЫВАЮТСЯ СМЕЖНЫМИ, ЕСЛИ

НА РИСУНКЕ СМЕЖНЫМИ ЯВЛЯЮТСЯ ВЕРШИНЫ A и B, A и C; СМЕЖНЫМИ ЯВЛЯЮТСЯ РЕБРА c и d, a и b.

ЕСЛИ ГРАФ ИМЕЕТ РЕБРО, У КОТОРОГО НАЧАЛО И КОНЕЦ СОВПАДАЮТ, ТО ЭТО РЕБРО НАЗЫВАЕТСЯ ПЕТЛЕЙ (у графа петля – q(C,C)).

ДВА РЕБРА НАЗЫВАЮТСЯ СМЕЖНЫМИ, ЕСЛИ ОНИ ИМЕЮТ ОБЩУЮ ВЕРШИНУ.

ВЕРШИНЫ И ОБОЗНАЧАЕТСЯ deg(A).
deg(A)= 3; deg(B) = 3; deg(C) =

ЕСЛИ ВЕРШИНЕ ИНЦИДЕНТНА ПЕТЛЯ, ОНА ДАЕТ ВКЛАД В СТЕПЕНЬ, РАВНЫЙ ДВУМ, ТАК КАК ОБА КОНЦА ПРИХОДЯТ В ЭТУ ВЕРШИНУ.

= 1
deg(B) = 1
deg(A) = 1
G, H, E, B, A

ЧИСЛО ЧЕТНОЕ, РАВНОЕ УДВОЕННОМУ ЧИСЛУ РЕБЕР ГРАФА:
ТЕОРЕМА
ЧИСЛО НЕЧЕТНЫХ ВЕРШИН

СЛЕДСТВИЕ

НЕВОЗМОЖНО НАЧЕРТИТЬ ГРАФ С НЕЧЕТНЫМ ЧИСЛОМ НЕЧЕТНЫХ ВЕРШИН.

ВЕРШИНА НАЗЫВАЕТСЯ ЧЕТНОЙ (НЕЧЕТНОЙ), ЕСЛИ ЕЕ СТЕПЕНЬ – ЧЕТНОЕ(НЕЧЕТНОЕ) ЧИСЛО.

ОДНИМ И ТОЛЬКО ОДНИМ РЕБРОМ.
ДОПОЛНЕНИЕМ ГРАФА НАЗЫВАЕТСЯ ГРАФ С ТЕМИ

ДОПОЛНЕНИЕ

ЧИСЛО РЕБЕР, ДЛЯ КОТОРЫХ ЭТА ВЕРШИНА ЯВЛЯЕТСЯ КОНЦОМ (НАЧАЛОМ).
СТЕПЕНИ ВХОДА

СТЕПЕНИ ВЫХОДА ВЕРШИН:

ОРГРАФ

ОРИЕНТИРОВАННЫЙ ГРАФ (ОРГРАФ) — ГРАФ, РЁБРАМ КОТОРОГО ПРИСВОЕНО НАПРАВЛЕНИЕ. НАПРАВЛЕННЫЕ РЁБРА ИМЕНУЮТСЯ ДУГАМИ.

вторая вершина предыдущего ребра совпадает с первой вершиной следующего, называется

HCDFD – МАРШРУТ ДЛИНОЙ 4.

маршрут называется замкнутым или циклом.
Если ребро

(t, s, p, r) – 4-ЦИКЛ
(t, s, u, r, t, s, p, r) – 8-ЦИКЛ
петля (q) – 1-ЦИКЛ

(t, s, p) – 3-ЦЕПЬ

– ПУТЬ, У КОТОРОГО СОВПАДАЮТ НАЧАЛО И КОНЕЦ.
(u, s, r,

Путь – упорядоченная последовательность ребер ориентированного графа, в которой конец предыдущего ребра

ПРОХОДЯТ ЧЕРЕЗ ЛЮБУЮ ИЗ ВЕРШИН НЕ БОЛЕЕ ОДНОГО РАЗА.
НЕОРИЕНТИРОВАННЫЙ ГРАФ

ТЕОРЕМА

ДЛЯ ТОГО, ЧТОБЫ СВЯЗНЫЙ ГРАФ ЯВЛЯЛСЯ ПРОСТЫМ ЦИКЛОМ, НЕОБХОДИМО И ДОСТАТОЧНО, ЧТОБЫ КАЖДАЯ ЕГО ВЕРШИНА ИМЕЛА СТЕПЕНЬ, РАВНУЮ 2.

, В ИЗОБРАЖЕНИИ КОТОРОГО НА ПЛОСКОСТИ РЕБРА ПЕРЕСЕКАЮТСЯ ТОЛЬКО В

ПЛАНАРНЫЕ ГРАФЫ

РЕБРА ГРАФА ТОЛЬКО ОДИН РАЗ.
ГРАФ, ОБЛАДАЮЩИЙ ЭЙЛЕРОВЫМ ЦИКЛОМ, НАЗЫВАЕТСЯ ЭЙЛЕРОВЫМ.
ТЕОРЕМА
ГРАФ

ТОЛЬКО ОДИН РАЗ.
ГРАФ, СОДЕРЖАЩИЙ ГАМИЛЬТОНОВ ЦИКЛ, НАЗЫВАЕТСЯ ГАМИЛЬТОНОВЫМ.
(C, D, A,

СТРОК(ВЕРШИНЫ) И m СТОЛБЦОВ(РЕБРА), В КОТОРОЙ:
bij = 1, ЕСЛИ ВЕРШИНА

ДЛЯ ОРИЕНТИРОВАННОГО ГРАФА:

ДЛЯ НЕОРИЕНТИРОВАННОГО ГРАФА:

bij = 1, ЕСЛИ ВЕРШИНА Vi ЯВЛЯЕТСЯ НАЧАЛОМ ДУГИ Xj
bij = 1, ЕСЛИ ВЕРШИНА Vj НЕ ИНЦИДЕНТНА ДУГЕ Xj
bij = -1, ЕСЛИ ВЕРШИНА Vi ЯВЛЯЕТСЯ КОНЦОМ ДУГИ Xj

A ПОРЯДКА n, В КОТОРОЙ:
aij = 1, ЕСЛИ (Vi, Vj)