1 Основные понятия теории графов Леонард Эйлер, 1736 г. Кирхгоф – электрические цепи Кэли – органические изомеры Гамильтон – головоломки Д.Кениг, 1936.

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



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

ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекции Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ, ХНУРЭ Компьютерная.
Тема: Графы Преподаватель Белгородцева Н.А. Дискретная математика.
{ изоморфизм графов - подграф - планарный и плоский графы - укладка плоских графов - маршруты, связность и компоненты - метрические характеристики - Эйлеровы.
Графы Волновой метод. Задание графов Пусть граф задан графически. Составить матрицу смежности и матрицу инцидентности для этого графа
1. Основные понятия теории графов 1. Основные понятия теории графов 2. Степень вершины Введение 5. Ориентированные графы 6. Изоморфизм графов 7. Плоские.
Глава III. ТЕОРИЯ ГРАФОВ Граф – диаграмма связей между объектами. Объекты представляются как вершины, или узлы графа, а связи как дуги, или рёбра. Многие.
V-множество вершин, E- множество ребер Граф - G(V, Е). Л. Эйлер 1736 г. G(V, Е, f) V,E – множества, отображение инциденции f: Е V&V множества Е в V&V Основы.
Сетевое планирование. Теория графов. Граф Граф это совокупность непустого множества вершин и множества пар вершин. Граф это совокупность непустого множества.
Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.
Теория графов Основные определения. Дуга Пусть имеется множество вершин V={V 1,V 2,…,V n } и пусть на нем задано бинарное отношение Г V×V, – V i Г V j.
Это раздел математики изучающий случайные события, находит зависимости между их появлениями, таким образом вычисляя вероятности их появлений.
Основные ПОНЯТИЯ ТЕОРИИ ГРАФОВ. Граф И ЕГО СВОЙСТВА ПРИМЕРЫ ГРАФОВ.
ПРАВОСЛАВНЫЙ СВЯТО-ТИХОНОВСКИЙ БОГОСЛОВСКИЙ УНИВЕРСИТЕТ (БОГОСЛОВСКИЙ ФАКУЛЬТЕТ) Презентация по математике на тему: Элементы теории графов.
Алгоритмы сканирования и обхода Лекция 3. Алгоритм сканирования графа Input: Орграф (граф) G и вершина s. Output: Множество R вершин, достижимых из s,
Графы Лекция 2. Графы Неориентированным графом (графом) называется тройка (V, E, ), где V и E конечные множества и {X V : | X | = 2}. Ориентированным.
Теория графов Основные определения. Дуга Пусть имеется множество вершин V={V 1,V 2,…,V n } и пусть на нем задано бинарное отношение Г V×V, – V i Г V j.
Эйлеровы графы. Гамильтоновы графы G.
Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.
Теория графов. Теория графов – обширный самостоятельный раздел дискретной математики. Используется при проектировании компьютерных сетей, трубопроводов,
Транксрипт:

1 Основные понятия теории графов Леонард Эйлер, 1736 г. Кирхгоф – электрические цепи Кэли – органические изомеры Гамильтон – головоломки Д.Кениг, 1936 Теория ориентированных и неориентированных графов

2 Неориентированные графы Вершины x и y смежныхе Х – множество вершин, U – множество ребер Ребра g и h смежныхе Вершина x и ребро g инцидентны - существует ребро, соединяющее эти вершины - существует вершина, являющаяся общим концом этих ребер - вершина x является концом ребра g

3 Неориентированные графы Утверждение 2 Количество вершин нечетной степени четно Вершина x изолированная, если она не имеет смежныхх вершин - степень вершины x ( количество ребер, инцидентных вершине x ) Утверждение 1

4 Неориентированные графы Граф есть пустой граф, если Обозначение: Граф есть полный граф, если все его вершины смежных Обозначение: Граф есть двудольный граф, если причем вершины каждой доли несмежныхх. Полный двудольный

5 Матрицы неориентированных графов Матрица смежности Матрица инцидентности

6 Матрица достижимости Матрица Oперации сложения и умножения xyx+yxy Матрица достижимости

7 Изоморфизм и планарность графов Графы и называются изоморфными, если существует биекция сохраняющая отношение смежности. Обозначение: Изоморфные графы

8 матрицы инцидентности и могут быть получены друг из друга перестановками строк и столбцов. Изоморфизм и планарность графов матрица смежности может быть получена из матрицы смежности одинаковыми перестановками строк и столбцов., причем : Теорема 1 Теорема 2

9 Изоморфизм и планарность графов Граф называется картой (плоским графом), если он изображен на плоскости без самопересечений ребер. Планарные графы Граф называется планарным, если существует изоморфная ему карта.

10 Изоморфизм и планарность графов планарен тогда и только тогда, когда в нем нет подграфа, который можно сжать до или Теорема (Понтрягина-Куратовского). Граф

11 Изоморфизм и планарность графов Пример непланарного графа

12 Граф называется связным, если Компоненты связности графа Компонента связности графа есть максимальный связный подграф этого графа - разбиение графа порожденное отношением достижимости на графе - число компонент связности