Маршруты. Расстояния - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Маршруты. Расстояния. Доклад-сообщение содержит 19 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Дискретная математика Маршруты. Расстояния

Слайд 2

Описание слайда:

Маршруты Пусть G =(V, E) – н-граф. Маршрутом в графе G называется чередующаяся последовательность вершин и ребер где ребро инцидентно вершинам

Слайд 3

Описание слайда:

Маршруты Вершина - начальная вершина маршрута М, - конечная, - внутренняя вершина, маршрут соединяющий и . Дина маршрута – число его ребер.

Слайд 4

Описание слайда:

Маршруты Маршрут М называется цепью - если его ребра не повторяются, простой цепью – если его вершины не повторяются, маршрутом общего вида, если вершины и ребра повторяются.

Слайд 5

Описание слайда:

Маршруты Маршрут М называется циклическим, если начальная и конечная вершина совпадают. Замечание: совпадают, не значит повторяются.

Слайд 6

Описание слайда:

Маршруты Циклический маршрут М называется циклом - если его ребра не повторяются, простым циклом – если его вершины не повторяются (кроме начала и конца), маршрутом общего вида, если вершины и ребра повторяются.

Слайд 7

Описание слайда:

Маршруты М1 =(1, 2, 3, 4, 1, 3, 4, 5) – общ вида. М1 =(1, 2, 3, 4, 1, 5) – цепь М1 =(1, 2, 3, 4, 5) – простая цепь.

Слайд 8

Описание слайда:

Маршруты М1 =(1, 2, 3, 1, 2, 3, 1) – циклический маршрут общего вида. М1 =(1, 3, 4, 5, 6, 4, 1) – цикл (не пр) М1 =(1, 2, 3, 4, 1) – простой цикл.

Слайд 9

Описание слайда:

Расстояния в графе Расстоянием между вершинами a и b называется длина минимальной простой цепи, связывающей их. Расстояние обозначается d(a, b). Аксиомы метрики: 1) d(a, b) = d(b, a); 2) d(a, b) ≥ 0, d(a, b) = 0 ↔ a = b; 3) d(a, b) ≤ d(a, c) + d(c, b)

Слайд 10

Описание слайда:

Расстояния в графе

Слайд 11

Описание слайда:

Расстояния в графе ri – эксцентриситет i-ой вершины – расстояние от этой вершины до наиболее удаленной от нее вершины. ri = max d(vi,vj) по всем j от 1 до n

Слайд 12

Описание слайда:

Расстояния в графе Диаметр графа G – максимальное расстояние между вершинами графа d(G)= max d(vi,vj) по всем i и j от 1 до n. Или d(G)=max ri по всем i от 1 до n

Слайд 13

Описание слайда:

Расстояния в графе Центр графа G – это вершина, расстояние от которой до наиболее удаленной вершины – минмальное. Что бы найти центр, надо сначала найти радиус графа.