Презентация на тему ГРАФ И ЕГО ЭЛЕМЕНТЫ. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

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

X) НАЗЫВАЕТСЯ ПАРА ДВУХ КОНЕЧНЫХ МНОЖЕСТВ: МНОЖЕСТВО ТОЧЕК И

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

РЕБРАМИ ГРАФА.
ПРИМЕРЫ ГРАФОВ

ГОВОРЯТ, ЧТО ЭТО РЕБРО ИМ ИНЦИДЕНТНО. ДВЕ ВЕРШИНЫ ГРАФА

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

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

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

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

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

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

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

ТЕОРЕМА

ЧИСЛО НЕЧЕТНЫХ ВЕРШИН ЛЮБОГО ГРАФА – ЧЕТНО.

СЛЕДСТВИЕ

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

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

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

ДОПОЛНЕНИЕ

ОРГРАФА НАЗЫВАЕТСЯ ЧИСЛО РЕБЕР, ДЛЯ КОТОРЫХ ЭТА ВЕРШИНА ЯВЛЯЕТСЯ

СТЕПЕНИ ВХОДА ВЕРШИН ГРАФА (см. рис.):

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

ОРГРАФ

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

в которой вторая вершина предыдущего ребра совпадает с первой

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, t) – 4-путь
(r, u) – 2-путь
(s, r, t) и (u, s, r) – 3-циклы

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

ЕСЛИ ОНИ ПРОХОДЯТ ЧЕРЕЗ ЛЮБУЮ ИЗ ВЕРШИН НЕ БОЛЕЕ

ТЕОРЕМА

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

ГРАФ G' , В ИЗОБРАЖЕНИИ КОТОРОГО НА ПЛОСКОСТИ РЕБРА

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

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

ТЕОРЕМА

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

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

(C, D, A, B, E) – гамильтонов путь

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

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

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

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

КВАДРАТНУЮ МАТРИЦУ A ПОРЯДКА n, В КОТОРОЙ:
aij = 1,