Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.

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



Advertisements
Похожие презентации
Графы Волновой метод. Задание графов Пусть граф задан графически. Составить матрицу смежности и матрицу инцидентности для этого графа
Advertisements

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

Теория графов Основные определения

Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных ребрами – ребро d между вершинами А и В, ребро e между вершинами В и С, ребро f между вершинами В и А, ребро g между вершиной С и С. – Как называется ребро е по отношению к ребру d? – Как называется ребро g?

Задание графов Пусть граф задан графически. Составить матрицу смежности и матрицу инцидентности для этого графа

Задание графов По матрице смежности построить граф abcd a0110 b1010 c1101 d0010

Задание графов Построить граф, если задана матрица инцидентности uvwx a1000 b1110 c0101 d001 1

Изоморфизм Показать, что следующие два графа изоморфны

Изоморфизм Изобразить все попарно неизоморфные 4- вершинные графы без петель и кратных ребер. Изобразить все попарно неизоморфные несвязные 5-вершинные графы, не имеющие петель, кратных ребер и изолированных вершин.

Изоморфизм и степень вершин Изобразить все попарно неизоморфные 6- вершинные графы без петель и кратных ребер со следующим набором степеней вершин (2, 2, 3, 3, 3, 5) Изобразить все попарно неизоморфные не имеющие петель и кратных ребер кубические графы с 6 вершинами (кубические – однородные (у которых все вершины – одинаковой степени) графы со степенью 3)

Изоморфизм Среди пар графов, изображенных на рисунке, найдите пары изоморфных и неизоморфных. Ответ обосновать.

Изоморфизм Среди пар графов, изображенных на рисунке, найдите пары изоморфных и неизоморфных. Ответ обосновать.

Изоморфизм Среди пар графов, изображенных на рисунке, найдите пары изоморфных и неизоморфных. Ответ обосновать.