Маршрут, цепь, цикл Маршрутом называют последовательность вершин и ребер, в которой любые два соседних элемента инцидентны (т.е. соединены). Например:

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



Advertisements
Похожие презентации
ПРАВОСЛАВНЫЙ СВЯТО-ТИХОНОВСКИЙ БОГОСЛОВСКИЙ УНИВЕРСИТЕТ (БОГОСЛОВСКИЙ ФАКУЛЬТЕТ) Презентация по математике на тему: Элементы теории графов.
Advertisements

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

Маршрут, цепь, цикл

Маршрутом называют последовательность вершин и ребер, в которой любые два соседних элемента инцидентны (т.е. соединены). Например: V0-V1-V2-V4-V6-V3-V2-V4-V5-V1-V2-V3 В случае простого графа (графа без петель и кратных ребер) маршрут однозначно определяется последовательностью вершин или последовательностью ребер

Если вершины v 0 = v k, то маршрут называют замкнутым. Если вершины v 0 v k, то маршрут называют незамкнутым. Длиной маршрута называют число ребер в нем с учетом повторений. Например: длина маршрута V0-V1-V2-V4-V6-V3-V2-V4-V5-V1-V2-V3 равна11

Если маршрут в простом графе задан последовательностью вершин v 0, v 1,...,v k, то вершины v o,v k называют концами маршрута. Например: концами маршрута V0-V1-V5-V4-V2-V3 являются вершины V0,V3

Цепь - это маршрут, в котором нет повторения ребер. Например: V 0 -V 2 -V 4 -V 3 -V 6 -V 7 Цепь, в которой все вершины различны, кроме, может быть, ее концов, называется простой.

Путь – это ориентированная простая цепь Например:

Простой цикл – это замкнутая простая цепь. Например: V 0 -V 1 -V 2 -V 6 -V 3 -V 0

Контур – это простой ориентированный цикл. Например:

Леонард Эйлер ( ) Эйлеров путь (эйлерова цепь) это путь, проходящий по всем ребрам графа и притом только по одному разу. Эйлеров цикл это эйлеров путь, являющийся циклом.

Расстояние между вершинами, диаметр, мост

Расстояние между вершинами – это длина кратчайшей цепи, соединяющей эти вершины (сама такая цепь называется геодезической) Например: расстояние между вершинами V 1 и V 5 это длина геодезической цепи V 1 -V 2 -V 4 -V 5 Диаметр – это самая длинная геодезическая цепь.

Мост – это такое ребро е = ( u, v ) графа, удаление которого приводит к тому, что вершины u и v перестают быть связными. Например: на рисунке это ребра (2,4), (7,10), (11,12)

Точка сочленения, блок

Точка сочленения – это вершина графа v, удаление которой из графа увеличивает число компонентов связности.

Блок – связный граф, не имеющий точек сочленения. После удаления вершины V, граф распался на 3 блока

Спасибо за внимание!

Выполнили: Студенты группы 953 Вдовин Роман Матвеева Ольга Молодчикова Алена Источники: Учебник «Дискретная математика. Курс лекций» Палий И.А. irina-m.at.ua Материал из Википедии: статья «Эйлеров цикл»