V-множество вершин, E- множество ребер Граф - G(V, Е). Л. Эйлер 1736 г. G(V, Е, f) V,E – множества, отображение инциденции f: Е V&V множества Е в V&V Основы.

Презентация:



Advertisements
Похожие презентации
ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ И ЕГО ЭЛЕМЕНТОВ. ГРАФОМ G = (V, X) НАЗЫВАЕТСЯ ПАРА ДВУХ КОНЕЧНЫХ МНОЖЕСТВ: МНОЖЕСТВО ТОЧЕК И МНОЖЕСТВО ЛИНИЙ, СОЕДИНЯЮЩИХ.
Advertisements

1. Основные понятия теории графов 1. Основные понятия теории графов 2. Степень вершины Введение 5. Ориентированные графы 6. Изоморфизм графов 7. Плоские.
Это раздел математики изучающий случайные события, находит зависимости между их появлениями, таким образом вычисляя вероятности их появлений.
Графы Лекция 2. Графы Неориентированным графом (графом) называется тройка (V, E, ), где V и E конечные множества и {X V : | X | = 2}. Ориентированным.
ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекции Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ, ХНУРЭ Компьютерная.
Домашнее задание «Применение графа» ВСПОМНИМ… Граф Простейшая модель системы.Отображает элементарный состав системы и структуру связей Сеть Граф с возможностью.
ВЫПОЛНИЛ: УЧЕНИК 11 КЛАССА «А» ЛОБЖА АРТЕМ ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ: ОУ СОШ 51 Образовательное учреждение: г. Комсомольск – на – Амуре, 2012 год.
ПРАВОСЛАВНЫЙ СВЯТО-ТИХОНОВСКИЙ БОГОСЛОВСКИЙ УНИВЕРСИТЕТ (БОГОСЛОВСКИЙ ФАКУЛЬТЕТ) Презентация по математике на тему: Элементы теории графов.
{ изоморфизм графов - подграф - планарный и плоский графы - укладка плоских графов - маршруты, связность и компоненты - метрические характеристики - Эйлеровы.
Основные ПОНЯТИЯ ТЕОРИИ ГРАФОВ. Граф И ЕГО СВОЙСТВА ПРИМЕРЫ ГРАФОВ.
Введение в теорию графов. ЗАДАЧА ПРОКЛАДКИ КОММУНИКАЦИЙ
Тема: Графы Преподаватель Белгородцева Н.А. Дискретная математика.
Сетевое планирование. Теория графов. Граф Граф это совокупность непустого множества вершин и множества пар вершин. Граф это совокупность непустого множества.
Маршрут, цепь, цикл Маршрутом называют последовательность вершин и ребер, в которой любые два соседних элемента инцидентны (т.е. соединены). Например:
Графы Волновой метод. Задание графов Пусть граф задан графически. Составить матрицу смежности и матрицу инцидентности для этого графа
Графы Граф – совокупность точек и линий, в которой каждая линия соединяет две точки. Точки – вершины графа Линии – рёбра графа Вершины, соединенные ребром,
Теория графов. Теория графов – обширный самостоятельный раздел дискретной математики. Используется при проектировании компьютерных сетей, трубопроводов,
Определение графа Фигура, образованная конечным набором точек плоскости и отрезков, соединяющих некоторые из этих точек, называется плоским графом, или.
Введение в теорию графов 11 класс Профиль Учитель информатики Тивякова Л.А., к учебнику Н.Д.Угриновича.
1 Основные понятия теории графов Леонард Эйлер, 1736 г. Кирхгоф – электрические цепи Кэли – органические изомеры Гамильтон – головоломки Д.Кениг, 1936.
Транксрипт:

V-множество вершин, E- множество ребер Граф - G(V, Е). Л. Эйлер 1736 г. G(V, Е, f) V,E – множества, отображение инциденции f: Е V&V множества Е в V&V Основы теории графов

V={A,В,С,D,F,Н,P} – множество точек, E={a,b,с,d,e,f,g,h,p,l} – множество линий f: Е V&V, определяется по закону f: a (H&H), b(P&F), c(B&C), d(A&B), e(P&F), f(B&H), g(B&H), h(A&H), p(A&B), l(A&B) Основы теории графов

Определение инцидентности. Пусть задан абстрактный граф G(V, Е, f). Если отображение f сопоставляет ребру е пару вершин (х 1 &х 2 ), т.е. f(e) = (х 1 &х 2 ), то ребро е инцидентно вершинам х 1 и х 2. «ребро е соединяет вершины x 1 и x 2 » «вершины x 1 и x 2 являются граничными точками ребра е». Если f(е) = (x&x), то ребро называется петлей в вершине х. Определение смежности. Две вершины x 1 и x 2 графа G(V, Е, f) называются смежными, если в графе существует ребро е, инцидентное этим вершинам. Два ребра графа называются смежными, если существует вершина, инцидентная обоим этим ребрам.

Степенью вершины графа называется количество инцидентных ей ребер (для петли степень подсчитывается дважды). Вершины графа называются четными или нечетными в зависимости от четности их степеней. Теорема 1. В любом конечном графе G(V, Е) количество нечетных вершин четно. Сумма степеней всех вершин равна удвоенному числу ребер графа: Q(x)=2|E| Основы теории графов

Операции разборки графа: 1) удаление ребра между двумя вершинами графа. 2) удаление вершины графа вместе со всеми инцидентными ребрами. Подграфом графа G называется такая его часть G 1, которая получается из графа G при помощи конечного числа операций разборки вида 2. Суграфом графа G называется такая его часть G 1, которая получается из графа G при помощи конечного числа операций разборки вида 1.

Основы теории графов Пример операций разборки

Основы теории графов G(V, Е, f) V={А 1,А 2,…,А n } E={a 1,a 2,…,a n }. Конечная последовательность ребер графа a 1,a 2,…,a k (не обязательно различных) называется маршрутом длины k, если граничные точки двух соседних ребер последовательности совпадают. Маршрут называется замкнутым, если его начальная и конечная вершины совпадают. В противном случае маршрут незамкнутый. Цепь - незамкнутый маршрут, состоящий из последовательности различных ребер. Простая цепь - маршрут, который не проходит дважды через одну и ту же вершину. Цикл - замкнутый маршрут, состоящий из последовательности различных ребер. Простой цикл - маршрут, в котором начальная и конечная вершины совпадают, а все остальные вершины различны.

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

Основы теории графов Уникурсальные графы Задача Эйлера о кенигсбергских мостах Можно ли пройти по всем мостам, изображенным на рисунке, так, чтобы на каждом из них побывать лишь один раз и вернуться к тому месту, откуда началась прогулка?

Основы теории графов Уникурсальные графы Граф называется уникурсальным графом (или эйлеровой линией), если все его ребра можно включить либо в простой цикл, либо в простую цепь. Признаки уникурсальных графов: Лемма. Если связный граф имеет более двух нечетных вершин, то он не уникурсален. Теорема 1. Связный граф является эйлеровым циклом тогда и только тогда, когда он имеет только четные вершины. При этом начало и конец уникурсального пути совпадают и могут находиться в любой вершине графа. Теорема 2. Связный граф является эйлеровой цепью тогда и только тогда, когда он имеет ровно две нечетные вершины, а остальные вершины этого графа четны. При этом начало и конец уникурсального пути находятся в нечетных вершинах.

Основы теории графов Ориентированные графы G(V, Е, f) V={A,В,С,D,Р} E={a 1,a 2,…,a 12 }. Отображение инциденции: f: a 1 (A,B); a 2 (A,B); a 3 (B,C); a 4 (B,P); a 5 (P,C); a 6 (D,C); a 7 (D,C); a 8 (A,P); a 9 (P,D); a 10 (A,D); a 11 (D,D); a 12 (D,D).

В ориентированном графе параллельные дуги бывают двух типов: строго параллельные (одинаково ориентированные) нестрого параллельные (ориентированные по-разному).

Задача выбора кратчайшего маршрута Ответ:

Графовая модель образовательного учреждения Пользователи образовательных услуг (П). Преподаватели и сотрудники (работники) (Р). Инфраструктура (Б). Комплекс нормативно-правовых актов (Н). Информационные технологии (И).