Эйлеровы графы. Гамильтоновы графы. 1 2 3 45 6 78 G.

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



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

1 Основные понятия теории графов Леонард Эйлер, 1736 г. Кирхгоф – электрические цепи Кэли – органические изомеры Гамильтон – головоломки Д.Кениг, 1936.
Это раздел математики изучающий случайные события, находит зависимости между их появлениями, таким образом вычисляя вероятности их появлений.
Сетевое планирование. Теория графов. Граф Граф это совокупность непустого множества вершин и множества пар вершин. Граф это совокупность непустого множества.
Теория графов Основные определения. Дуга Пусть имеется множество вершин V={V 1,V 2,…,V n } и пусть на нем задано бинарное отношение Г V×V, – V i Г V j.
ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекции Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ, ХНУРЭ Компьютерная.
NP-полнота Основные NP-полные задачи. Задача «Независимое множество» Условие. Задан граф G=(V,E) и целое число k. Вопрос. Существует ли независимое множество.
1. Основные понятия теории графов 1. Основные понятия теории графов 2. Степень вершины Введение 5. Ориентированные графы 6. Изоморфизм графов 7. Плоские.
Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.
Тема: Графы Преподаватель Белгородцева Н.А. Дискретная математика.
Теория графов: подграфы и деревья 11 класс Профиль Учитель информатики Тивякова Л.А., к учебнику автора Угриновича Н.Д.
Графы Граф – совокупность точек и линий, в которой каждая линия соединяет две точки. Точки – вершины графа Линии – рёбра графа Вершины, соединенные ребром,
Алгоритмы сканирования и обхода Лекция 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.
Раскраски графов Раскраска вершин Пусть Г (V,E,Ф) – граф, раскраска вершин Г в n цветов – отображение f : V {1,2,…,n } Правильная раскраска вершин графа.
Транксрипт:

Эйлеровы графы. Гамильтоновы графы

G

G

Уи́льям Ро́уэн Га́мильтон – (4 августа сентября 1865) выдающийся ирландский математик, механик и физик. Задача «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли

Достаточные условия гамильтоновости графа Теорема Дирака. Пусть G - неориентированный граф порядка n и m - минимальная степень его вершин. Если n3 и m n/2, то G - гамильтонов граф. Теорема Оре. Пусть G - неориентированный граф порядка n. Если n3 и deg(u)+deg(v) n для любых двух различных несмежных вершин u и v, то G - гамильтонов граф. Если неориентированный граф G содержит гамильтонов цикл, тогда в нём не существует ни одной вершины u со степенью u < 2. Необходимое условие гамильтоновости графа

Задание Построить эйлеров, квазиэйлеров, гамильтонов, квазигамильтонов графы порядка n=F+N, p>n, где F-количество букв в Вашей фамилии, N-количество букв в Вашем полном имени. Описать полученные графы матрицами смежности вершин, смежности ребер, инцидентности, Кирхгофа соответственно.