Графы. Основные понятия - презентация, доклад, проект скачать

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

Содержание ▲

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

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

Слайд 1

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

Графы. Основные понятия Определение 1. Графом называется произвольное множество элементов V и произвольное семейство E пар из V. Обозначение: G = (V, E). Определение 2. Если элементы из E рассматривать как неупорядоченные пары, то граф называется неориентированным, а пары называются рёбрами. Если же элементы из E рассматривать как упорядоченные, то граф ориентированный, а пары — дуги. Определение 3. Пара вида (a, a) называется петлёй, если пара (a, b) встречается в семействе E несколько раз, то она называется кратным ребром (кратной дугой).

Слайд 2

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

Определение 4. В дальнейшем условимся граф без петель и кратных рёбер называть неориентированным графом (или просто графом), граф без петель — мультиграфом, а мультиграф, в котором разрешены петли — псевдографом. Определение 4. В дальнейшем условимся граф без петель и кратных рёбер называть неориентированным графом (или просто графом), граф без петель — мультиграфом, а мультиграф, в котором разрешены петли — псевдографом. Определение 5. Две вершины графа называются смежными, если они соединены ребром. Определение 6. Говорят, что вершина и ребро инцидентны, если ребро содержит вершину. Определение 7. Степенью вершины (deg v) называется количество рёбер, инцидентных данной вершине. Для псевдографа полагают учитывать петлю дважды.

Слайд 3

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

Представление графов в ЭВМ 1. Матрица смежности вершин М : array [1..p, 1..p] of 0..1 2. Матрица инциденций Н :array [1..p, 1..q] of 0..1 (для орграфов Н :array [1..p, 1..q] of -1..1)

Слайд 4

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

3. Списки смежности 3. Списки смежности G : array [1..p] of *N N : record v : 1..p; n: *N endrecord 4. Массив дуг Е : array [1..q] of record b,е : 1..p endrecord

Слайд 5

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

Маршруты, циклы, цепи… Маршрут Если все рёбра различны, то маршрут называется цепью. Если все вершины (а значит, и рёбра) различны, то маршрут называется простой цепью. Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Число циклов в графе G обозначается z(G). Граф без циклов называется ациклическим. Для орграфов цепь называется путем, а цикл — контуром.

Слайд 6

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

Обход графа Вход: граф G(V, Е) Выход: последовательность вершин обхода.

Слайд 7

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

Алгоритм Алгоритм for v in V do x[v]: =0 { вначале все вершины не отмечены } end for T = {} выбор v in V{ начало обхода — произвольная вершина } v ->Т{ помещаем v в структуру данных Т ... } x[v]: = 1{ ... и отмечаем вершину v } repeat u Т { помещаем w в структуру данных Т ... } x[w] := 1 { ... и отмечаем вершину w } end if end for until T = {} T — стек, то обход поиском в глубину. Т —очередь, то обход поиском в ширину.

Слайд 8

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

Лабораторная работа Представление графов в ЭВМ Написать программу обработки информации о маршрутах автобусов Дано: N – количество маршрутов; М – количество остановок Для каждого маршрута указаны его остановки Внести информацию в компьютер Провести проверку возможности проезда из пункта А в пункт В (четные варианты – поиск в глубину, нечетные – в ширину)

Слайд 9

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

Компоненты связности графа

Слайд 10

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

Связные компоненты Граф неориентированный G(V,E) Вершины x1, x2 связные, если существует маршрут из x1 в x2 Каждый неориентированный граф распадается единственным образом на сумму непересекающихся компонент связности Пусть G – простой граф с p вершинами и k компонентами связности. Число ребер не более C(2,p-k+1)=(p-k+1)(p-k)/2