'

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

Понравилась презентация – покажи это...





Слайд 0


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

Цепь - это маршрут, в котором нет повторения ребер. Например: V0-V2-V4-V3-V6-V7 Цепь, в которой все вершины различны, кроме, может быть, ее концов, называется простой. ?


Слайд 6

Путь – это ориентированная простая цепь Например: 1?2 ?3 ?5 ?6


Слайд 7

Простой цикл – это замкнутая простая цепь. Например: V0-V1-V2-V6-V3-V0


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

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


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

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


Слайд 16

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


Слайд 17

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


×

HTML:





Ссылка: